군집 분석[Cluster Analysis] 분할방법- K-means

n 개의 객체를 가진 데이터 집합 D와 군집 수로 k가 주어진다면,

분할 알고리즘은 객체들을 나누어 k개의 군집으로 나눈다.

결과적으로 군집 내의 객체들은 유사하고, 다른 군집의 객체들끼리는 그렇지 않도록하는 것이 최종목적이 되겠다.

 

가장 잘 알려진 일반적인 분할 방법은 k-means와 k-mediods 이다.

k-평균, k-중앙객체 라고도 한다.

 

먼저 k-means에 대해 살펴보자.

k-means는 개괄적으로 표현하자면, 간단하지만 단점이 좀 있는 클러스터링 방법이다.

그도 그럴것이 초기값으로 k가 주어져야만 하고, 초기 설정값에 따라서 클러스터링 결과가 많이 바뀌기 때문에 여러가지 방면에서

약점이 있다.

 

상세하게 조금씩 살펴보자.

 

진행 순서는 다음과 같다.

 

1. 군집의 평균이나 중심값으로 객체들에서 k를 임의로 추출한다.

2. 남겨진 객체들은 객체와 군집 평균에 기초해서 가장 가까운, 유사한 군집에 할당이 된다.

3. 각 군집 내에서 새로운 평균을 구한다.

4. 위의 과정을 임계값이나 기준함수가 수렴할때까지 반복한다.

 

4에서의 기준으로는 주로 제곱오차(squared - error)가 사용된다고 한다.

 

E는 데이터베이스에서 모든 객체들의 ㅣ제곱오차를 합한것

p는 주어진 객체를 뜻하는 공간의 점

mi는 군집 Ci의 평균

 

알고리즘으로 정리해보자.

Input : k , D (=n개의 객체를 포함하는 데이터 집합)

output : k 개의 클러스터 집합

 

Method :

 (1) D로부터 임의로 k개의 객체들을 초기 클러스터 중심으로써 선택한다.

 (2) Repeat

 (3)          클러스터 내의 객체들의 평균 값에 근거해서 가장 유사한 객체들을 클러스터에 (재)할당한다.

 (4)          클러스터 평균값을 업데이트한다.(즉, 각 클러스터의 객체들의 평균값을 계산한다.)

 (5) Until  바뀌지 않을 때 까지.

 

앞에서도 언급했지만, k-means는 제법 단점이 많다.

정리해보면

1. 크기가 매우 다른 군집을 찾는 데는 적절하지 않다.

2. 작은 수의 데이터(혼자 저 멀리 떨어진 데이터)가 평균값 계산시에 영향을 미쳐 잡음이나 이상치 데이터에 민감하다.

3. k를 미리 정해야 한다.

 

이러한  k-means의 단점을 보완하기위해 k-medoids나 EM(Expectation - Maximization), k-최빈값(k-modes)등의 알고리즘이 있다.

이러한 알고리즘에 대해서는 차후 살펴보도록 하자.