[클러스터링] k-medoid Algorism(k-중앙자 알고리즘)

k-medoid Algorism (k-중앙자 알고리즘)

클러스터링은 데이터 객체 집합을 다수의 그룹으로 쪼개는 작업을 말한다. 유사성과 비슷한 정도는 대상을 정의하는 속성 값을 통해 계산하며 주로 거리 측정법을 사용한다.

k-means는 평균값을 구하는 연산을 수행하기 때문에 잡음이나 이상치(아웃라이어)에 민감하다. 이러한 단점을 해결하기 위해 나온것이 k-medoids 알고리즘이다. k-medoids는 클러스터의 대표값으로 오브젝트의 중심점을 구하는 것이 아니라, 오브젝트 중에서 클러스터를 대표할 수 있는 가장 가까운 대표 오브젝트를 뽑는다. 대표로 뽑히지 않은 나머지 오브젝트는 가장 가까운 대표 오브젝트를 따라 해당 클러스터에 배정한다. 이러한 분할 알고리즘은 불일치의 총합을 최소화 하는 원칙에 따라 각 오브젝트 p와 p가 속한 대표 오브젝트사이의 차이를 절대오차(Absolute criterion) 기준으로 결정한다.

k-means의 경우 평균을 대표값으로 가져가기 때문에 분산을 기준으로 알고리즘이 진행되는것에 반해 k-medoid는 중앙값을 대표값으로 가져가므로 위 처럼 절대오차를 기준으로 알고리즘이 진행되게 된다.
k-medoid 알고리즘을 가장 일반적으로 실현화한 것중 대표적인것은 PAM(Partitoning Around Medoid) 알고리즘이 있다.

k-means Algorism과의 비교

중앙값은 평균에 비해 이상치에 영향을 덜 받기 때문에 k-medoid가 k-means보다 안정적이다. 그러나 k-medoid 알고리즘의 경우 kmeans에 비해 계산복잡도가 훨씬 높기 때문에 훨씬 느리며 이는 비용과 직결된다. 즉 작은 데이터에서는 잘 작동하나 대규모 데이터를 다룰때는 적절하지 않다는것이다. 이를 위해 CLARA(clustering LARge Application)라 불리는 표본기반(sample-based)방법이 제시되었다. PAM이 전체 데이터를 고려하는데 반해 CLARA는 전체 중앙자를 계산한다. 데이터에서 일부 데이터만을 대표값으로 뽑아낸 후 PAM 알고리즘 방식으로 샘플안에서 최적의 중앙값을 계산한다.


<출처 : 데이터 마이닝 개념과 기법>