[K-Medoids] PAM (Partitioning Around Medoids)

PAM (Partitioning Around Medoids)

PAM은 cluster를 대표하는 것으로 real object를 이용한다.

 

방법

1. initial : 랜덤하게 k개의 object를 선택한다. (random seed)
2. tc 계산 : seed 중 1개($i$), seed가 아닌 object 중 1개($j$)를 선택하고 total swapping cost $TC_{ih}$를 계산한다.
   • total swapping cost : i 대신 h를 쓸 때 전체적인 badness(distance)의 변화
   • $TC_{ih} < 0$ → i 대신 h를 사용한다.
3. reassign : seed가 아닌 object를 가장 가까운 seed와 같은 cluster로 묶는다.
4. 수렴할 때 까지 2-3의 과정을 반복한다.

 

Total Swapping Cost

i대신 h를 선택할 때의 cost(badness)의 합이다.

non-seed인 모든 j에 대해서 i 대신 h를 새로운 seed로 선택했을 때의 distance의 합이다.

새로 바뀐 거리가 더 멀어지면 양수가 되고, 새로 바뀐 거리가 더 가까워지면 음수가 된다.

 

TC = i 대신 h를 선택했을 때의 distance - 기존의 distance

 

$TC_{ih} = \sum _j ^{} C_{jih}$

* 기존에 j가 i에 속했을 때 : $C_{jih} = d(j, h) - d(j, i)$

* 기존에 j가 t에 속했을 때 : $C_{jih} = d(j, t) - d(j, i)$

 

j는 변경 전에는 i 또는 t, 변경 후에는 h 또는 t에 속할 수 있으므로 총 4가지 경우가 발생할 수 있다.

 

장점

k-means에 비해 noise나 outlier에 대해 robust(잘 견디는)하다.

medoid는 mean에 비해 outlier나 다른 extreme value에 대해 영향을 적게 받기 때문이다.

 

단점

Cost가 n에 대해 cost가 2차로 증가한다.

따라서 적은 데이터에 대해서는 잘 작동하지만 scalability가 약하다.

 

time cost = $O(i \times k \times (n-k)^2)$

* n : 전체 object 수

* k : cluster 수 → 주로 작음

* i : iteration 수 → 주로 작음

 

이를 극복하기 위해서 CLARA(Clustering LARge Application)과 같은 방법을 이용한다.