K-means Clustering (K-평균 군집화)

K-means Clustering

K-means에서 K는 클러스터의 개수를 의미하고 means는 평균을 의미한다.

말 그대로 주어진 데이터를 k개의 클러스터로 묶는 알고리즘이다.

 

Basic Algorithm

1: Select K points as initial centroids
2: Repeat
3:   Form K clusters by assigning each point to its closest centroid
4:   Recompute the centroid of each cluster
5: Until Centroids do not change

k-means의 과정은 다음과 같다

 

1) k개의 initial centroid를 랜덤하게 선정한다.

2) 각 point들을 가장 가까운 centroid에 할당하여 k개의 클러스터를 형성한다.

3) 각 클러스터의 centroid의 재계산한다.

4) 업데이트된 centroid에 모든 점을 다시 할당한다.

5) centroid가 거의 움직이지 않을 때까지 위의 과정을 반복한다.

 

 

How to select K?

그렇다면 k는 어떻게 선정해야할까? 적절한 initial centroid를 잡는 것은 k-means의 주요 문제이다. 하지만 초기값을 잡는 방법은 아무도 모르기 때문에 k값을 바꿔가면서 centroid까지의 평균거리의 변화 추이를 살펴볼 수 밖에 없다.

 

 

limits of Random Initialization

하지만 random하게 initial centroid를 잡는 방식은 매우 간단하지만 데이터셋이나 클러스터의 개수에 따라 잘 작동하지 않는 경우가 발생한다. 만약 초기의 centroid가 한쪽에 몰려 있다면 2개로 나뉘어야할 cluster가 하나로 통합되고, centroid가 더이상 움직이지 않아 local minimum에 빠지게 된다.

 

Tech for Initialization

k를 뽑는 방법은 2가지가 존재한다.

 

1) Pre-clustering

data point를 샘플링하여 hierarchical clustering을 이용하여 클러스터링한 후, K개의 cluster를 추출해낸다. 하지만 이러한 방식은 샘플이 비교적 작거나 샘플크기에 비교해서 k개가 작을 때 잘 작동하지 않는다. 그러므로 k가 클수록 k보다 더 많은 양의 샘플을 뽑아야 한다.

 

 

2) Selecting the farthest point

• 첫번째 centroid는 랜덤하게 뽑는다
• 두번째 centroid는 첫번째  centroid와 거리가 가장 먼 것으로 선택한다

 

이러한 방식은 첫번째 centroid와 분리된 centroid를 설정할 수 있다는 장점이 있으나 가장 먼 centroid를 뽑으니 outlier를 뽑을 수 있다는 단점이 존재한다. 또한, 모든 점마다 거리를 구해야하므로 오버헤드가 발생한다.

 

 

K-means++

1: For the first centroid, pick one of the points at random
2: for i =2 to K do
3:   Compute the distance of each point to its closest centroid
4:   Assign each point a prob proportional to each point's d(x)^2
5:   Pick a new centroid from the remaining points using these prob
6: end for

 

k-means ++의 과정은 다음과 같다

 

1) 첫번째 centroid를 랜덤하게 선정한다.

2) 각 point와 가장 가까운 centroid와의 거리를 계산한다 → d(x)

3) 거리의 제곱에 비례하는 확률을 할당한다  →  거리가 멀수록 할당될 확률이 높아짐 (확률이므로 확률이 높아도 할당되지 않을 수 있음)

 

Strengths and Weeknesses of K-means

 

장점

• 간단하며 대부분의 거리측정방식에 적용가능하다
• 연산이 간단하므로 여러번 수행해도 속도가 빠르다
• centroid를 재계산할 때 점들은 클러스터를 이동할 수 있으므로 k를 잘못 잡더라도 나중에 수정 가능하다

 

단점

• k를 처음부터 예측하기가 어렵다
• 아웃라이어에 취약하다

• centroid는 거리 개념일때만 사용할 수 있으므로 string인 경우 centroid를 사용할 수 없다
• non-globular한 모양은 클러스터링이 잘 되지 않는다 → k-means는 centroid와 가까운 점들의 집합이므로 아래 그림과 같은 예시에는 적합X