어제 번역을 하면서 오랜만에 duda의 pattern classification책을 펼쳐 봤다.
워낙에 이 바닥에서는 알아주는 책이지만 사실 이 책 통독은 하지 못했다. 하지만  필요한 부분을 찾아보는 용도로 주로 쓴다.  ^^;

어제는 EM 알고리즘을 오랜만에 살펴봤다.

내가 아는 EM 알고리즘은 기본적으로 미지의 분포 파라메터를 주어진 데이터를 가지고 예측을 하고 그 예측값을 다시 주어진 데이터를 기반으로 기대치를 최대화 시키는 파라메터를 구하는 이런 과정을 반복하면서 최적 파라메터를 얻는 방법이다.

이 추정할 파라메터가 여러개 있어서 그 기대치를 최대화 하여 파라메터를 조절해 가는게 바로 EM 알고리즘을 이용한 클러스터링이다.

k-means도 마찬가지지만 EM도 초기 클러스터의 개수를 정해줘야 하는 단점이 있다.

하지만 k-fold cross validation 방법으로 적절한 클러스터 개수를 찾을 수 있다.

두 가지 방법 모두 1개의 클러스터로부터 출발한다.

일단 주어진 클러스터 개수에서 데이터를 10개로 쪼개 9개로 클러스터를 구성하고 1개로 클러스터 중심점과의 거리를 제어 10번의 평균을 구한다.  EM의 경우에는 우도(likelihood)가 (혹은 숫자의   under flow를 피하기 위해 로그 우도를 구하던가…) 거리 측정의 방법이 될 것이다.
이 후에 클러스터를 2개로 올린다. 그리고 1개의 클러스터의 경우 처럼 평균 거리와 우도를 구해서 이전 클러스터링 실험과 비교를 한다.
클러스터를 늘릴 수록 이전보타 클러스터 중심에서의 평균 거리가 짧아질 것이고 EM의 경우에는 우도가 커질 것이다. 여기서 잊지 말아야 할 부분은 평균거리가 짧아졌다고 해서 그리고 우도가 커진다고 해서 결코 좋은게 아니라는 것이다. 자칫 잘못하면 과적합이 일어나기 때문이다. 사실 데이터 개수만큼의 클러스터가 존재하면 정말 최소 평균거리와 최대 우도가 나올 것이다.

그래서 우도나 평균 거리의 변화량이 급격히 변화되는 시점이 적절한 클러스터 개수의 할당 지점이 될 수 있을 것이다.

예를 들어 아래와 같은 그래프를 보자.

x축을 클러스터의 개수, y축을 클러스터와 데이터간의 평균 거리라고 하면 몇 개의 클러스터가 가장 적합할 것으로 보이는가?
아마도 2개  정도가 적합해 보인다. 4~6 까지 가면 큰 성능 변화가 없이 클러스터만 늘리게 된다.

EM 알고리즘의 경우 로그 우도로 하면 위와 비슷한 그래프가 나올 것이다. (y축의 스케일은 다르겠지만…)

이 최적 클러스터를 구하는 작업 자체가 많은 리소스를 먹지만 이렇게라도 최적 클러스터 개수를 구할 수 있다면 정말 해볼만한 일이 아닐까 한다.
클러스터링은 그 결과물 자체가 데이터에 대한 새로운 패턴 인식을 하게 해준다. 게다가 클러스터의 개수만 가지고서도 그 입력으로 사용된 데이터셋의 특징을 알 수 있다.

k-means, EM 알고리즘… 그리고 알맞은 k개수 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.