k-medoids(중앙객체) 방법과 CLARANS

 

이것은 각막셀카!

 

아... 군집분석도 타이핑하려니 귀찮다.. 앞으로 생략..

 

----------------------------------------------------

 

앞에서 포스팅했듯이 k-means는 평균값을 구하는 연산을 수행하기 때문에 잡음이나 이상치에 민감하다고 했다.

이러한 단점을 해결하기 위해서 나온것이 k-medoids 알고리즘이다.

 

K-medoids 알고리즘의 핵심은 평균을 구하는 대신에 군집을 대표하는 실제 객체를 선택하는 것이다.

나머지 객체들은 가장 유사한 대표 객체들로 군집화 된다.

즉, K-means에서 평균을 계산해서 평균값을 기준으로하여 가장 가까운 객체들은 특정 군집에 할당을 했다면,

K-medoids는 실제로 존재하는 객체들 중에 하나를 선택하여 대표 객체로 선정하고 이 객체를 중심으로하여서 나머지 객체들을 군집에

할당한다는 의미이다.

 

K-means의 절대오류 기준과 같이 여기서도 동일하게 임계점을 정해두는데, 그 공식은 위의 공식과 같다.

여기서 p는 군집 Cj에서 주어진 객체를 대표하는 공간상의 객체이다. oj는 군집 Cj의 대표객체이다.

말이 어려운가?

p는 한 군집내에서 비교대상이 되는 (1번의 반복 내에서 계속 바뀌는) 객체이고

oj는 한 군집내에서 비교기준이 되는 (1번의 반복 내에서는 바뀌지 않는) 객체이다. 

반복적으로 수행을 하다보면 각 대표객체들이 실제의 중앙객체(modoids)가 된다.

 

결과는 K-means와 동일하니 대충 의미는 이해하리라 생각한다.

k-modoids는 군집화를 수행할때 다음과 같이 크게 4가지 경우가 발생할 수 있다.

Case 1. 현재 대표객체 oj에 어떤 객체 p가 속해있는경우, 만약 Oj가 Orandom으로 대체되고 p가 Oi에 가장 가까운 개체라면 p는 Oi에 재배치 된다.

Case 2. 현재 대표객체 oj에 어떤 객체 p가 속해있는경우, 만약 Oj가 Orandom으로 대체되고 p가 Orandom에 가장 가까운 개체라면 p는 Orandom에 재배치 된다.

Case 3. 현재 대표객체 oi에 어떤 객체 p가 속해있는경우, 만약 Oj가 Orandom으로 대체되더라도 p가 Oi에 가장 가까운 개체라면 p는 Oi에 유지된다.

Case 4. 현재 대표객체 oi에 어떤 객체 p가 속해있는경우, 만약 Oj가 Orandom으로 대체되고 p가 Orandom에 가장 가까운 개체라면 p는 Orandom에 재배치 된다.

 

써놓고 보니 참 당연한 소리를 하고 있지만, 이러한 경우가 발생할 수 있다는 것을 알아두자.

 

 

PAM(Partitioning around Medoids)는 초기에 소개된 K-medoids 알고리즘이다.

초기 설정으로 K개의 대표객체를 임의적으로 선정한 후 더 좋은 결과를 얻기위해 반복적인 연산을 수행한다.

 

 

알고리즘은 위와 같다.

그렇지만 내가 좋아하는 우리말로 정리해보자.

입력은 K-means와 같이 클러스터 갯수 k 넣어줘야되고, 데이터세트인 D를 넣어주면된다.

출력은 역시나 K개의 군집이다.

Method:

(1)  데이터세트 D에서 각 군집을 대표할 임의의 K 개의 객체들을 선택한다.

(2) Repeat

(3)     남아있는 각 객체들은 가장 근접한 대표객체가 속한 클러스터에 할당한다.

(4)     임의적으로 비대표 객체 Orandom을 선택한다.

(5)     대표 객체 Oj와 Orandom을 교환에 대한 총 비용을 계산한다.(S)

(6)     만약 S < 0 라면 Oj와 Orandom 값을 바꿔 새로운 k 대표객체의 집합을 형성한다.

(7) Until 안바뀔 때까지 

 

 

앞에서도 설명했지만, K-modoids는 K-means에 비해 잡음, 이상치의 처리가 강하지만

역시나 초기에 k를 지정해주어야하고 처리비용이 k-means에 비해 고비용이라는 단점도 존재한다.

 

[2013-04-11] 추가사항

무작위로 선정할 객체 O는 전체 객체에서 선정하는 것이 아니라, 클러스터링이 수행 된 후 각 클러스터 내에서 무작위로 다시 선정한다.

 

-------------------------------

다음으로 살펴볼 기법은 CLARANS 기법이다.

뭔가 품격있어보이는듯한 느낌의 이름이다..

 

CLARANS 기법을 쉽게 이해하기 위해서 통계학의 표본분석을 생각하면 가장 쉽다.

대규모의 데이터베이스에서의 분할 방법인데, DB 전체를 모두 분할하기에는 규모가 너무 크기 때문에, 원본 DB에서 표본을 추출하고 추출한 표본으로부터 가장 좋은 군집을 출력한다.

 

CLARA의 효율성은 표본의 크기에 의존한다.

또한 PAM(K-medoids 방법의 대표격) 기법이 주어진 객체 중 좋은 k개의 중앙객체를 찾았다면, CLARA는 데이터잡합에서 추출해낸 표본들 중에서 K개의 중앙객체를 찾는다.

개념적인 내용만 기억해두면 되므로, 표본분석을 개념으로 잡고 알아두도록 하자.