K-medoids Clustering Algorithm

해당 포스팅은 위키피디아 의 내용을 본인이 이해하기 쉽게 풀어쓴 내용을 담고 있습니다. 부정확한 정보가 포함 될 수 있으며, 좀더 정확한 정보를 확인하고자 하시는 분은 위키피디아 및 다른 사이트를 참조해주시기 바랍니다.

 

 

 

K-medoids 클러스터링 알고리즘은 K-means와 흡사하다.

다만 K-means가 임의의 좌표를 중심점으로 잡는 반면 K-medoids는 실제 점 하나를 중심점으로 잡아서 계산을 수행한다.

약간의 계산상의 차이가 있지만 대체적으로 유사한 부분이 많다.

 

K-medoids의 대표적인 방법은 Partitioning Around Medoids(PAM) 알고리즘인데 이에 대해서 살펴보도록하자.

전체적인 단계는 다음과 같다.

K-medoids의 단계

 

1. 초기화 : n개의 데이터 포인트에서 임의로 k개의 중심점을 지정한다.

2. 가장 가까운 중심점에 각각의 데이터  포인트를 할당한다.(여기서 가깝다는 의미는 유클리디안이나 자카드 계수와 같이 점과 점사이의 거리를 계산하는데 필요한 척도를 말하는 것으로 연구에 따라 달라질 수 있다.)

3. 각각의 중심점 m에 대해서

    3.1. 각각의 중심점이 아닌 데이터 포인트 O를 임의로 지정한다.

    3.2. m와 O에 대해 각각의 총 비용을 계산한 뒤 비교한다.

4. m과 O 중에 낮은 비용을 가지는 것을 다음 중심점으로 정한다.

5. 2~4번 단계를 중심점이 변하지 않을 때까지 반복한다.

 

X1	2	6
X2	3	4
X3	3	8
X4	4	7
X5	6	2
X6	6	4
X7	7	3
X8	7	4
X9	8	5
X10	7	6

 

위와 같이 데이터 포인트가 위치한다고 하자.

 

 

이제 상세하게 한번 살펴보자.

 

우선 k개의 중심을 초기화하자. 여기서는 임의로 2개의 포인트를 잡는데

X2와 X8을 중심으로 잡아 각각 C1, C2라고 명명한다.

 

각 데이터 객체들을 우리가 지정한 C1, C2와 계산해서 가장 가까운 중심점 클러스터에 할당해보자.

그러면 결과가 다음과 같이 나올 것이다.

 

 

Cluster₁ = {(3,4)(2,6)(3,8)(4,7)}

Cluster₂ = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}

 

그러면 위와 같이 클러스터 구성이 된다.

여기서 최종 비용은 다음과 같이 계산한다.

각 포인트의 비용 계산은 Manhattan Distance를 사용한다.

맨해튼 거리를 잠깐 살펴보면

P = (p1, p2, ....pn), Q = (q1, q2, ...., qn)일 때

거리를 구해보면 |p1 - q1| + |p2 - q2|로 거리를 구할 수 있다.

그리 어렵지 않은 내용이다.

 

 

 

다음단계에서는 임의로 O라는 데이터포인트를 중심점으로 잡고 계산을 해보자.

아래의 그림과 같이 중심점을 다시 잡고 계산을 수행한다.

 

공식은 앞과 동일하다.

구해보면

total cost = 3 + 4+ 4+ 2+ 2 + 1 + 3 + 3 = 22이다.

앞에는 20이었는데 여기서는 22다. 즉, 비용이 더 많이 든다는 이야기이다.

따라서 임의로 잡은 O는 적절한 중심점이 아니라는 뜻이다.

그러니까 기존의 중심점 C2는 그대로 유지되고 다시 다른 임의의 O를 잡아서 동일한 연산을 수행한다.

 

확실히 K-means보다는 좀더 나은 성능을 보여줄 것으로 예상되지만 진행되는 알고리즘을 보면

연산비용이 많이 나올것으로 보인다.

K-means는 단순히 거리 계산해서 재할당만 하면 되는 것이었는데, 이 방식은 지속적으로 총 비용 계산하고 바꾸는 과정을 반복하므로 프로그래밍을 할 때에도 좀더 많은 노력이 필요할 것으로 보인다.