[Cluster Analysis] Partitioning Algorithm

Partitioning Algorithm

n개의 object를 가지는 database D를 k개의 cluster로 나누는 작업이다.

조합이 무수히 많기 때문에 clustering ↔ evaluate의 과정을 반복한다.

 

Distance의 제곱이 최소가 되는 clustering 결과를 선택한다.

 

Practically

가능한 모든 조합에 대해 거리의 합을 구하면 되기 때문에 개념적으로는 간단하다.

그러나 현실적으로 가능한 경우의 수가 많기 때문에 모든 조합을 고려하여 global optimal을 찾는 것은 불가능하다.

 

따라서 cluster에 속하는 object와 대표 object까지의 거리를 cluster의 badness로 삼고 모든 cluster의 badness가 최소가 되는 조합을 찾는다.

 

대표적인 방법

Algorithm	대표 Object
K-Means	centroid
K-Medoids	medoid
PAM(Partition Around Medoids)	medoid
CLARA(Clustering LARge Applications)	medoid