[Clustering] Partitioning Methods, K-Means Clustering, PAM, k-Medoids Clustering

Basic Concepts of Partitioning Methods

Partitioning method는 $n$개의 object(데이터)를 $k$개의 partition(이자 cluster)으로 분할하는 것을 의미한다.

• 각 group(cluster, partition)은 최소 하나의 object를 포함해야한다.
• 각 object는 정확히 하나의 group(cluster, partition)에만 속한다.

Initial partitioning으로 시작하여, iterative relocation technique를 이용하여 partitioning을 향상시킨다.

 

대표적으로 k-means, k-medoids, PAM 알고리즘이 속한다.

K-Means Clustering

(1) 데이터 $D$에서 임의로 $k$개의 object를 선택하여 초기 클러스터 센터(initial cluster center)로 삼는다.

(2) 각 object들을 가장 유사한 cluster로 (re)assign한다. 이때 object들의 mean을 기준으로 한다.

(3) 각 cluster마다 cluster mean 값을 업데이트한다.

(4) criterion function이 수렴할때까지 (2)~(3)을 반복한다.

K-means clustering

 

Evaluation Criterion

대표적으로 sum of the square error를 사용한다.

$p$는 cluster $C_i$에 속하는 data point이고, $m_i$를 cluster $C_i$의 mean이라 할 때 $SSE$는 다음과 같다.

\[ SSE = \sum_{i=1}^{k} \sum_{p \in C_i} dist^2(m_i, p) \]

 

Effect of Choosing Initial Centroids

그러나 초기 cluster center를 이상하게 잡으면 최종 cluster center가 우리가 기대한 대로 되지 않을 수 있다.

Effect of Choosing Initial Centroids

 

반응형

Limitations of K-means clustering

k-means clustering은 매우 효율적이라는 장점을 갖는다.

object개수, cluster 개수, 반복횟수를 각각 $n,\ k,\ t$라 할 때 시간복잡도가 $O(tkn)$이다. (그리고 일반적으로 $k, t \ll n$ 이므로 $n$의 영향이 제일 크다.)

그리고 대부분 local optimal에서 반복문이 종료된다.

 

그러나 아래와 같은 많은 단점이 존재한다.

• continuous space에서만 적용할 수 있다. (local optimal이 global optimal임이 보장되지 않음)
• 클러스터 개수인 $k$를 직접 지정해야 한다.
• non-convex shape, 클러스터 크기나 (different sizes), 밀도가 다르면(different density) 적절하지 않다.
• noisy하거나 outlier에 매우 민감하다. (sensitive to noisy data and outliers). 데이터 분포를 왜곡하기 때문.

Limitations of k-Means: Non-Convex Shapes

Limitations of k-Means: Different Sizes

Limitations of k-Means: Different Density

K-Medoids Clustering

특히 mean을 이용하기 때문에 극단값들이 데이터 분포를 왜곡할 여지가 존재한다.

따라서 mean 대신에 medoid를 이용한다.

Note: Medoid는 cluster 내에서 가장 중앙에 위치한 object이다.

The concept of Medoids

PAM (Partitioning Around Medoids)

PAM 알고리즘은 k-medoid를 구현하는 대표적인 알고리즘이다. 

(1) $k$개의 medoid를 임의로 초기화한다. 

(2) 나머지 object들을 가장 가까운 medoid로 할당한다.

(3) 랜덤하게 non-medoid object를 $O_{random}$이라 한다.

(4) 만약 quality가 좋아지면 $O$와 $O_{random}$을 swap한다.

 

K-medoids by PAM algorithm

small data set에서는 잘 동작하지만, large data set에서는 computational complexity 때문에 scale 문제가 존재한다.

시간복잡도가 $O(k(n-k)^2)$이다.

 

CLARA, CLARANS 알고리즘은 PAM을 향상시킨 알고리즘이다.