PAM (Partitioning Around Medroid)

PAM은 K-medoid clustering이 가장 일반적으로 실현화된 것이다. 그렇다면 일단 먼저 K-medoids에 대해 알아보자. 이 알고리즘은 k-means 알고리즘과 관련된 군집 알고리즘이고 medoidshift 알고리즘이다. k-means 와 k-medoids 알고리즘 둘다 나누는 일을 하고(즉 데이터셋을 군집들로 쪼갠다는 의미)또한 한 군집 안에 있는 포인트들과 그 군집의 중심점 사이의 거리를 최소화 하려고한다. k-means 알고리즘과는 다르게(한 군집의 평균을 중심점으로 잡음), k-medoids는 데이터 포인트들을 중심점(medoids 또는 exemplars라고 함)으로 선택한다.

k-medoid는 n개의 객체의 데이터셋을 priori(사전에 k를 정해주는것을 말함)를 아는 k개의 클러스터들로 묶는 하나의 classical partioning techique 이다. 여기서 k를 정하는 방법은 silhouette 방법으로 정한다. (클러스터링의 평가척도에 대해서는 후에 포스팅을 따로 하겠지만 클러스터링 자체가 비지도학습이기 때문에(사전가정이 없다.) 사후적검증 방법으로 검증을 하여 경험적으로 가장 군집이 잘 나뉘어진 k를 정할 수 밖에 없는데 이러한 사후적검증방법으로의 예로는 silhouette와 Dunn index를 들 수 있다.) 여기서 실루엣(silhouette)기법만 보면 

여기서 a(i)는 개체i와 같은 군집내에 있는 다른 개체들간의 평균거리(비유사도)를 나타낸다, b(i)는 개체i와 다른 군집에 있는 개체들사이의 평균거리(비유사도)중 가장 작은 값이다.

s(i)가 1에 가깝기 위해서는 a(i)<<b(i)가 되어야 한다. s(i)가 1에 가까워질수록 군집화가 잘된것이고, 반대로 -1에 가까울수록 군집화가 잘 안된것인데, a(i)가 작을수록 군집안의 결집성이 높은것이고 b(i)가 클수록 군집끼리가 멀다는 말이므로 군집끼리의 잘 구분되었다는 의미이다.  

medoid 는 한 클러스터의 개체인데, 이 개체가 속한 클러스터 내에서의 다른 모든 개체들과의 평균 거리(혹은 비유사도)가 가장 작은 개체를 말한다. 다시말해 클러스터 안에서 가장 중심에 위치한 데이터 포인트를 말한다.

k-medoids는 노이즈나 이상치에 대해 k-means보다 강건하다. 왜냐하면, 노이즈나 이상치가 있는 데이터에서 이에 영향을 받는 평균과의 유클리디안 거리의 제곱합을 계산하는것 대신에 중앙값에 가까운 (실제 중앙값은 아님에 주의하라) 기준데이터 포인트를 잡고 pariwise하게 거리를 잰 합이 최소가 되기 때문이다.

이제 PAM에 대해서 알아보자 PAM은 전역최적의 해를 찾지 않는 Greedy search이다. 그러나 exhaustive search(하나하나씩 다 계산해서 찾아보는것)보다는 더 빠르다. 이것은 다음과 같이 작동한다.

1. 초기화 : n개의 데이터포인트들 중에서 k 개를 (k<n) 비복원임의추출하여 medoids로 삼는다.

2. 각각의 data point를 가장 가까운 medoid에 포함시킨다.

3. configureation 비용이 줄어들 때까지만, 각 m개의 medoid와 각 z개의 non-medoid에 대해서,

1. m을 z로 바꾸고, 비용을 즉 medoid와 데이터 포인트들간의 거리의 합을 재계산한다.

2. 만약 다음의 거리값의 전체 비용이 위 과정에서 증가한다면 m에서 z으로의 swap을 멈춘다. 

voronoi iteration방법 알고리즘으로는 (일반적으로 k-means에도 많이 쓰이는 방법)

1. 초기medoids를 선택한다.

2. cost가 감소 할때까지 다음을 반복한다.

1. 각 클러스터에서, 클러스터안의 데이터끼리의 거리들의 합을 최소화하는 포인트를 medoid로 정한다.

2. 이전스텝에서 결정된 가장 가까운 medoid로 부터 정의된 클러스터에 각 점을 재조정한다.

참고문헌 : https://en.wikipedia.org/wiki/K-medoids