출처: 이기용 교수님, 데이터마이닝및분석 수업
7장에서는 클러스터링이 무엇인지와 대표적인 클러스터링인 (1) K-means, (2) Agglomerative Hierarchical Clustering, (3) DBScan에 대해서 배웠다.
이번에 정리한 내용은 K-means 에 대한 내용이다.
순서대로 전반적으로 정리하자면,
- The Basic K-means Algorithm: 핵심은 각 점을 가장 가까운 centroid에 할당하여 K cluster를 형성하는 단계와 각 cluster의 centroid를 다시 계산하는 단계이다. 전자는 centroid 이 고정된 상황에서 나머지 점의 cluster를 찾는 것이고, 후자는 cluster 내 점들이 고정된 상황에서 centroid 값을 계산한다는 것이다.
- Convergence of K-means: 항상 수렴이 되긴 하지만, 최적의 해는 아니다.
- Assigning Points to the Closest Centroid: 사람의 판단 하에 proximity function을 설정하는 것이 가장 중요한데, 이 때 "가장 가까운(the closest)" 개념을 수량화하는 proximity measure가 필요하다.
- Centroids and Objective Functions: Centroids는 다양하게 정의될 수 있는데, 주로 클러스터 내의 평균 점을 의미한다. Objective Functions은 어떤 값을 최대화/최소할 할 것인지에 대한 클러스팅의 목표 표현이다.
- K-means Common Choices: 주로 사용하는 proximity measure로 Manhattan distance, Euclidean distance, Cosine similarity에 대한 설명한다.
- Choosing Initial Centroids: K-means의 초기점을 잡는 방식으로 각각 서로 다른 set of random initial centroids을 사용하여 multiple run 수행하는 방법이 있는데, 치명적인 단점으로 로컬 최소값만 달성된다.
- Other Techniques for initialization: 다른 방법으로 (1) Pre-clustering, (2) Selecting the farthest point, (3) K-means++ 방법이 있다.
- K-means++: K-means++ 의 알고리즘을 설명한다.
- Limitations of K-means: clusters의 크기가 다를 때, cluster의 밀도가 다를 때, non-globular 클러스터인 경우 문제가 생긴다.
- Strenghts and Weaknesses: K-means의 특징 및 장단점을 정리한 것이다.
이런 순서대로 전개된다.
K-means
: 가장 오래되고 널리 사용되는 clustering 알고리즘 중 하나
The Basic K-means Algorithm
- K점을 initial centroids으로 선택 (K는 user-specified parameter)
- Repeat [object function을 반복적으로 최적화하는 알고리즘: 전체 식을 최소화 하고자]
- 각 점을 가장 가까운 centroid에 할당하여 K cluster을 형성 → k개의 그룹이 형성
=> [ci가 고정된 상황에서 나머지 점 x들을 수정한다] - 각 cluster의 centroid을 다시 계산 → centroid(평균점)는 그 cluster 안의 x 평군, y평균
=> [점들 x가 고정된 상황에서 ci값을 수정한다] - Until centroid 가 거의 변경되지 않을 때까지(=membership이 바뀌는 애들이 없을 때까지) → 수렴
중단 원칙은 모든 membership이 고정될 때까지 이지만, 실제로 대용량의 데이터에서는 1~2%가 이동하는 건 무시하는 경우 많다.
목적 함수인 $\sum_{i=1}^{k}{\sum_{\begin{subarray}i\in Ci\\\end{subarray}}}dist(ci, x)^2$ 값을 최소화 하려면 → 각 점이 가까운 Ci로 cluster 되어야 한다.
- ci 와 x 값을 동시에 찾으려면 시간이 너무 오래 걸리기 때문에 찾을 수 없다.
- 두 변수를 한꺼번에 찾아야 하는데 step3 에서는 x를 찾고, step 4에서는 ci를 찾기 때문에 local minimum에 걸릴 수 있다.
- Step 3: minimize the SSE by assigning 𝐱 to the nearest ci
- Step 4: minimize the SSE by updating c given 𝐱 ∈ 𝐶
Convergence of K-means
proximity 함수와 centroids 유형의 여러 조합(combinations)에도 K-means는 항상 해(always converges) 로 수렴한다.
- K-means는 한 cluster에서 다른 cluster로 이동하는 점이 없는 상태에 도달 → 중심점은 변하지 X
- 수렴의 대부분은 초기 단계에서 발생하기 때문에, 종종 weaker end condition(ex. 점의 1%만 군집을 변경함)이 사용된다.
그러나 수렴이 되기는 하지만 항상 optimal cluster는 아니다. K-means는 local minimum 으로 수렴할 수 있다.
→ initial centroids에 따라 결과가 매우 달라진다.
Assigning Points to the Closest Centroid
: k-means를 돌리기 전, proximity function을 설정하는 것이 중요하다(사람의 판단).
: 가장 가까운 중심에 점을 할당하려면 "가장 가까운(cloest)" 개념을 수량화하는 근접 측정(proximity measure)이 필요하다.
예제
– Euclidean 공간에서의 clustering → (ex: (3, 1, 5), (2, 3, 4), ...)
(ex) Euclidean(L2) distance, Manhattan(L1) distance, ...
– 문서 클러스터링 → ex( (3, 2, 0, 0, ..., 5, 0), (1, 0, 0, 4, ..., 0, 2), .. )
(ex) cosine distance, the Jaccard coefficient, ...
Centroids and Objective Functions
Centorids
- 다양하게 정의할 수 있다
- proximity measure(근접 측도) 및 클러스터링 목표에 따라 다름
- (ex) the mean of points in the cluster → (평균 x점, 평균 y점)
Objective Fuctions
- 클러스터링의 목표 표현 → 어떤 값을 최대화/최소화 할 것인지
- clustering의 quality 측정
- (ex) k-means의 목적함수: 가장 가까운 centroid 까지의 각 점의 제곱 거리 최소화
예제
$\sum_{i=1}^{k}{\sum_{ \begin{subarray}{l} i\in Ci\\ \end{subarray}}}dist(ci, x)^2$
- 1부터 k개의 클러스터에서 Ci번째 클러스터에 대해 그 안의 모든 점과 중심점 사이의 거리
$Ci = {1\over mi}{\sum_{ \begin{subarray}{l} i\in Ci\\ \end{subarray}}}x$
- Objective fuction: Minimize the sum of the squared error (SSE) 중심점과 해당 점의 거리의 제곱의 합 최소화
- SSE 값을 최소로 하는 Centroid 값 ⇒ 결국, cluster의 mean of points가 된다.
예제2: 문서 data 와 cosine similarity 측정
- 문서 데이터가 문서 용어로 표현된다고 가정 → matrix (ex: x = (0, 3, 2, 0, 0, ...))
- distance는 유사할수록 score가 낮아지지만, consine similarity는 유사할수록 score가 올라간다.
$\sum_{i=1}^{k}{\sum_{ \begin{subarray}{l} i\in Ci\\ \end{subarray}}}cos(ci, x)$
*제곱을 사용해도 상관없으나, 유사도의 경우는 잘 안씀.
$Ci = {1\over mi}{\sum_{ \begin{subarray}{l} i\in Ci\\ \end{subarray}}}x$
- Objective fuction: Maximize the cohesion of the clusters
응집도(Cohesion): 얼마나 닮아 있는가 - cohesion의 값을 최대로 하는 Centroid 값 ⇒ 결국, cluster의 mean of points가 된다.
K-means: Common Choices
- 제곱을 취하는 것의 의미는 penalty를 크게 주고 싶기 때문
Choosing Initial Centroids
📌 K-means의 취약점
(1) k값 찾기
(2) initial point의 설정 (초기값을 눈으로 보고 알수 없으므로)
: 적절한 initial centroids 을 선택하는 것이 K-means의 핵심 단계이다.
: 일반적인 접근 방식은 initial centroids 를 randomly 선택하는 것 → 결과 cluster는 종종 poor 하다.
다음 아래의 사진은 초기 centroids를 랜덤으로 선택했을 때, cluster 결과에 대한 예제이다.
- good initial centroids
→ 모든 initial centroids이 하나의 natural cluster 안에 있지만, 우리는 optimal(최소 SSE) clustering 을 얻는다.
- poor initial centroids
→ 모든 initial centroids이 더 잘 분포되어 있는 것처럼 보이지만, 우리는 suboptimal clustering을 얻는다.
Limits of Random Inititalization 를 해결하는 one technique
- 방법) 각각 서로 다른 set of random initial centroids을 사용하여 multiple run 수행 → 그런 다음 최소 SSE가 있는 clusters을 선택 (여러 번 돌려보고 SSE 가 가장 좋은 값 찾기)
- 단점) 여러 번 돌리기 때문에 시간이 오래 걸리고, k 값이 크면 잘 안 돌아간다.
- 단순하지만 이 전략은 잘 작동하지 않을 수 있다. → data set 및 찾는 number of clusters 에 따라 다름
- good exmaple (클러스터 쌍당 두 개의 초기 중심)
- Bad example (클러스터 쌍에 대해 하나의 초기 중심만)
– 클러스터 수가 증가함에 따라, 하나 이상의 클러스터 쌍이 initial centroids 을 하나만(only one) 가질 가능성이 증가한다.
– 이 경우 pairs of clusters 이 clusters within a pair 보다 멀리 떨어져 있기 때문에 K-means 은 pairs of clusters 사이에 centroids을 재배포(redistribute)하지 않는다.
– 따라서 로컬 최소값만 달성된다. → 아무리 여러번 돌려도 local minimum에 도달할 수 밖에 없을 수도 있다.
Other Techniques for Initialization
(1) Pre-clustering
- 점의 sample(표본)을 추출한다 → 계층적 클러스터링(hierarchical clustering)을 사용하여 K개의 클러스터를 추출한다 → 이러한 군집의 중심을 초기 중심으로 사용
- 원본 데이터 중에서 일부만 샘플링 → 샘플링 데이터에 대해 계층적 클러스터링 기법 사용 → K개의 클러스터가 완성될 때까지 묶어 나감.
- 접근법은 종종 잘 작동하지만, 다음과 같은 경우에만 실용적입니다
- sample(표본) 상대적으로 작다(예: 수백에서 수천) → 데이터 샘플이 많아지면 계층적 클러스터링이 오래 걸려서 잘 안 돌아가기 때문
- K는 샘플 크기에 비해 상대적으로 작다 → 샘플이 작다 보니까 K도 큰 숫자까지 커버 불가능하다
(2) Selecting the farthest point(가장 먼 지점 선택)
- 첫 번째 점은 random으로 선택(또는 모든 점의 중심 선택) → 그 다음은 이미 선택한 초기 중심에서 가장 먼 점을 선택
- 이런 방식으로, 우리는 well separated 초기 중심의 집합을 얻을 수 있다.
- 점이 몰리는 것을 막고, 최대한 퍼뜨리려는 의도
- 이 접근법은 종종 sample of the points에 적용된다
- outlier가 껴있는 경우 → 그 값이 선택되고 다음 점들은 이상한 점들이 잡힐 가능성이 크다 → 제대로 안 돌아감
- 현재 중심점에서 가장 먼 점을 찾는 비용 절감
(3) K-means ++
- 무조건 멀다고 선택하는 것이 아니고, 멀면 선택할 확률을 높이는 것
K-means++
: K-means을 초기화하는 새로운 접근 방식이 최근 개발되었다. 가장 먼 점을 선택하는 방법과 유사.
: 실제로 SSE가 낮다는 점에서 훨씬 더 나은 클러스터링 결과를 생성한다.
K-means++ initialization 알고리즘
- 첫 번째 중심의 경우, 한 점을 random 하게 선택한다
- for i=2 to k do
- 가장 가까운 중심에 대한 각 점의 거리 d(x) 계산 → 기존의 centroid 중에 나랑 가장 가까운 거리 찾기
- 각 점에 각 점의 $d(x)^2$에 비례하는 확률 할당 → $d(x)^2$의 전체 합 구하기
- weighted probabilites을 사용하여 나머지 점에서 새 중심 선택 → $d(x)^2$/전체 합 으로 확률 정하기
- end for
- 확률로 뽑기 때문에 outliers를 거르는 데 도움이 된다.
- k-means와 동일하지만, ‘**초기값을 잡는 방법’**만 다르다.
Limitations of K-means
: K-means은 군집이 non-spherical shapes 이거나 widely different sizes or densities (크기 또는 밀도가 크게 다른) 경우 natural clusters을 탐지하는 데 어려움이 있다.
(1) clusters의 다른 size
큰 클러스터가 깨짐.
(2) clusters의 다른 density
클러스터의 밀도를 고려하지 않고 거리의 절댓값으로만 측정하기 때문에
(3) non-globular cluster
non-globular 군집이 있는 경우 → 두 cluster가 mixed 된다
Why do these difficulties arise?
- K-means objective function은 찾으려는 군집의 모양과 일치하지 않는다 → 모양과 함수가 mismatch
- K-means objective function은 크기와 밀도가 동일한 globular clusters 또는 well separated 된 클러스터에 의해 최소화됨
→ k-means를 사용하려면 (1) 클러스터의 모양이 원 (2) 각각의 클러스터의 크기가 비슷 (3) 각각 클러스터의 밀도가 비슷해야 잘 나눠진다.
Strengths and Weaknesses
strengths
- 단순하며 다양한 데이터 유형에 사용 가능
- 상당히 효율적이기 때문에 여러 번의 실행(multiple runs)을 수행이 가능
→ quite efficient(속도 빠른 편)
weaknesses
- non-globular 클러스터는 처리할 수 없다
- 크기와 밀도가 다른 클러스터를 처리할 수 없다 → 특히 density 보다 size가 더 중요하다(size가 다르면 잘 못 찾는다)
- 특이치가 포함된 데이터를 군집화하는 데 문제가 있음
- center(centroid) 개념이 있는 데이터로 제한됨
- (ex) {(3, 1, 5, 4), (2, 1, 3, 2)} vs. {{"데이터", "데이터", "과학"}}
