Chap 10 Clustering - K-Means Clustering

 

Supervised vs Unsupervised Learning

 

Supervised Learning : X와 Y를 모두 알고 있는 경우

 

Unsupervised Learning : X만 알고 있는 경우 

 

그림1

 

 

Clustering

 

Clustering은 데이터 셋에서 하위 그룹이나 군집을 찾는 기술들을 의미합니다.

 

좋은 clustering은 그룹 내에서의 관측치는 비슷하지만 그룹들끼리는 매우 다른 것을 의미합니다.

 

예를 들어, n명의 유방암 환자들에게서 p 측정값을 수집한다고 하면, 데이터를 clustering 하여 다른 모르는 유형의 암을 발견할 수 있습니다.

 

 

Different Clustering Methods

 

많고 다른 유형의 Clustering 방법들이 있습니다.

 

가장 많이 사용되는 두 개를 살펴보겠습니다.

 

K-Means Clustering 

Hierachical Clustering 

 

 

K-Means Clustering

 

K-means clustering을 수행하기 위해서는 원하는 clusters K의 수를 지정해야 합니다.

 

K-means 알고리즘은 각 관측값을 정확하게 K clusters 중 하나로 할당합니다.

 

그림2

 

 

How does K-Means work?

 

데이터 셋을 K clusters로 분할하기를 원합니다. 

 

$C_{1}, ..., C_{K}$

 

각 관측치는 적어도 K clusters 중 하나에 속해야 합니다.

 

The clusters는 겹치지 않습니다. 관측치가 하나 이상의 cluster에 속하는 일은 없습니다.

 

최소한의 "within-cluster-variation"을 갖는 것이 목표입니다. 즉, cluster 안의 요소들은 가능한 비슷해야 합니다.

 

각 cluster의 관측치 사이에서 the sum of all the pair-wise squared Euclidean distances을 최소화시키는 방법이 있습니다.

 

$minimize_{C_{1},..., C_{k}} = {\sum_{k=1}^{K}\frac {1}{\mid C_{k} \mid}\sum_{i, i' \in C_{K}}\sum_{j = 1}^{p}(x_{ij} - x_{i'j})^{2}}$

 

 

K-Means Algorithm

 

Initial Step : 임의로 각 관측치를 K clusters 중 하나로 할당합니다.

 

Cluster의 할당이 변화를 멈출 때까지 반복합니다.

 

각각의  K clusters에 대해 cluster centroid를 계산합니다. 관측치의 평균이 $k^{th}$ cluster에 할당된다면 The $k^{th}$ cluster centroid입니다.

 

The cluster에 각 관측치를 할당하는 것은 어느 centroid가 가장 가까운지에 따릅니다.

('closest'는 Euclidean distance를 사용해서 정의됩니다.) 

 

 

An Illustration of the K-Means Algorithm

 

그림3

 

 

Local Optimums

 

The K-means 알고리즘은 "local optimums"에 빠질 수 있어 최상의 solution을 찾지 못할 수 있습니다.

 

랜덤으로 알고리즘을 여러 번 시행해 좋은 solution을 찾을 수 있는 시작 지점을 발견하는 것이 중요합니다.   

 

그림4