K-means란

K-means Algorithm 작동 방식


위와 같이 랜덤으로 k개의 cluster centroids $\mu$을 초기화합니다.
(실제 K-means에서는 랜덤으로 Training data을 $\mu$로 선택합니다.)


각 $\mu$와 가까운 데이터에 해당 cluster을 할당합니다. 위 그림에서는 빨간색 $\mu$와 가까운 데이터라면 빨강색이 할당되었고 그 반대로 파랑색이 가까운 데이터는 파랑색이 할당되었습니다.


각 Cluster에 소속된 점들의 평균을 구하여 $\mu$의 위치를 이동시킵니다.


최적화가 될 때까지 이것을 반복하게 됩니다.

다음과 같은 알고리즘 형태를 갖고 있습니다.

$Randomly \enspace initialize \enspace K \enspace cluseter \enspace centriods \enspace \mu_1, \mu_2, …, \mu_k \in \mathbb{R}^{n}$

$Repeat \enspace \{$

$for \enspace i=1 \enspace to \enspace m$

$\enspace \enspace \enspace c^{(i)} = index \enspace(from \enspace 1 \enspace to \enspace k) \enspace of \enspace cluster \enspace centroids \enspace closet \enspace to \enspace x^{(i)}$

$\enspace for \enspace k=1 \enspace to \enspace K$

$\enspace \enspace \enspace \mu_{k} = average \enspace of \enspace points \enspace assigned \enspace to \enspace cluster \enspace k$

$\}$

첫 번째 for문을 Cluster Assignment Step라고 부르며, 데이터에 가장 가까운 cluster가 파악하여 할당하는 것이며, $\underset{k}{min}\left | x^{i}-u_k \right |^{2}$에서 가장 낮은 $k$을 선택하여 $c^{(i)}$에 할당하게 됩니다.

예를 들어 $x^1 - \mu_1 = A$와 $x^1 - \mu_2 = B$ 두 식에서 A와 B 값을 비교하여 A값이 더 낮다면 1이 할당되어 $c^{(1)}$가 됩니다.

두 번째 for문을 Move Centroids Step라고 부르며, Centroids을 옮기는 것을 의미하며, 예를 들어 $\mu_2$에 $x^1,x^3,x^6,x^{10}$가 할당되었다면 $c^1=c^3=c^6=c^{10}=2$가 됩니다. 그리고 이것을 계산하면 $\mu_2 = \frac{1}{4}[x^1+x^3+x^6+x^{10}]$가 됩니다.

할당된 point가 없다면 해당 centroid는 제거하는 것(K-1개 Cluster 생성)이 일반적이지만 반드시 K가 필요시 새로 random할당합니다.

Optimization Objective

K-means의 Cost함수는 다음과 같습니다.

  • $c^{(i)}$: $x^{(i)}$에 할당된 cluster {1,2,…,K} index
  • $\mu_{c^{(i)}}$: $x^{(i)}$에 할당된 cluster의 cluster centroid

optimization objective은 다음과 같습니다.

k-means의 Cost함수는 Distortion cost 함수라고도 불리웁니다.

Cluster assignment step는 $c^{1},…,c^{m}$에 대한 cost을 minimization(최소화)합니다. 이 단계에서는 가까운 cluster에 데이터 위치를 할당해야하기 때문입니다.

마찬가지로 두 번째 단계, Move Centroids Step는 $\mu_{1},…,\mu_{k}$에 대한 clustering cost을 최소화하는 단계입니다. Distortion을 최소화하는 centroid의 최적의 위치는 주어진 데이터 위치들의 mean postion(중심위치 혹은 평균값)입니다.

K-means는 두 단계를 최소화하는 계산이기 때문에 반복횟쉬가 증가함에 따라 항상 감소하거나 값이 일정하게 됩니다. 예들 들어 다음과 같은 이미지를 보겠습니다.


위와 같은 cost함수의 형태를 갖고 있다면 code에 bug가 무조건 있다는 것입니다. K-means에서는 cost가 증가하는 것이 불가능하기 때문입니다.

Random Initialization

centroid을 무작위로 추출하는 방법은 다양하지만 가장 권장되는 방법을 소개하겠습니다.

  • $K<m$을 만족해야함
  • 무작위로 Training example을 K 개 Pick
  • K개 Pick한 example을 $\mu_{1},…,\mu_{k}$에 초기화(할당)

K-means에는 Local optima와 Global optima가 존재하는데 Local optima와 Global optima을 이미지를 통해 알아보겠습니다. 먼저 Global optima 이미지를 보겠습니다.


다음은 Local optima입니다.


K-means가 다른 중심에 수렴하거나 Local optima에 빠질 수 있습니다. 즉 Random Initialization에 따라 다른 결과를 가지게 되는데 이를 해결할 방법은 Random Initialization을 여러번 하는 것입니다.

$For \enspace i=1 \enspace to \enspace 100 \{$

$\enspace \enspace k-menas \enspace algorithm$

$\}$

위와 같이 Random Initialization을 여러 번 수행하며, 일반적으로 50~100회 수행하는 것은 local optima에 갇히지 않도록 하는 흔한 일입니다. 그중 가장 낮은 cost을 주는 clustering을 선택합니다.

일반적으로 multiple random initialization의 함정은 clusets가 2~10 사이의 작은 경우에 도움이 된다는 것입니다. 10개 초과하는 clusters 경우 multiple random initialization이 Distortion cost 함수를 향상시키는데 도움이 될 가능성이 적습니다.

Choosing the Number of Clusters

클러스터 수를 선택하는 방법에 대해 소개하겠습니다.

  • 데이터를 수동으로 시각화하여 cluster 수 선택
    데이터를 시각화하여 Cluster 수를 짐작할 수 있습니다. 다음 이미지의 경우에는 3개의 cluster을 가질 수 있습니다.

  • 때때로 Dataset에 있는 cluster가 얼마나 있는지 모호하며 그런 경우 목표를 기반으로 cluster의 수를 선택하거나 Dataset으로 부터 추출해야하는 목적을 잘 수행하는 cluster 수를 선택,
    예를 들어 Dataset에서 T-shirt 사이즈를 결정해야하는 것이 목적이라면 몸무게와 키를 고려하여 S,M,L 사이즈로 묶을 수 있습니다. 다음 이미지를 통해 확인하겠습니다.

  • Elbow Method: 이 방법에서 cluster 최적의 수는 elbow(팔꿈치, 꺽인점)가 발생하는 지점을 의미합니다. 다음 이미지에서 B의 Elbow 지점이 최적의 cluster의 수 입니다. 하지만 이 방법은 항상 작동하는 것은 아닙니다. A와 같이 elbow 지점이 명확하지 않거나 J함수의 변화가 대체로 부드러운 경우 elbow 지점을 찾을 수 없습니다.


Reference

Coursera - Machine Learning (Andrew Ng) K-Means Clustering

Leave a comment