K-Means Algorithm

K-Means 알고리즘은 Centroid model들 중 하나이고 실행하기 이전에 K를 명시해야 하며 K개 군집을 뜻한다 목적은 각 군집 내에 있는 데이터의 차이를 최소로 하고, 군집간의 차이는 최대로 만드는 일이다 (유유상종). 알고리즘은 지역적인(지정된 K개 에서) 최적의 해결책을 찾는 휴리스틱(무작위시작에서 실험적 반복을 통해 조금씩 성능을 향상시키는 과정)과정을 사용한다. 최종적으로는 군집내 동질성의 향상을 목표로 한다.

K-Means 알고리즘은 크게 2가지 파트로 나뉜다.

1. 초기값설정

2. 반복단계

1. 초기값설정

KNN (최근접이웃)과 마찬가지로 K 평균은 다중 속성공간의 좌표로 속성값을 다룬다. (오해하진 말자 KNN과 K평균은 카테고리가 다르다. 단지 K라는 글자만 같을뿐이다.)  첨언을 하면 최근접은 일명 게으른 학습이라 불리우는데 새로운 데이터가 들어왔을때 주위의 예제간의 거리를 모두 계산하여 시간이 많이 걸린다. 이걸 좀 더 이론적으로 말하면 추상화가 일어나지 않는다고 한다. 특정 모델이 없기 때문에 추상화(피쳐를 뽑아내는 것)가 없고 따라서 어떤 모수가 없는 비모수 기법이다. 사설이 길어졌는데 말하고자 하는 요지는 knn은 새로운 데이터가 들어올 시예제간의 거리를 모두 계산하지만 K-means 알고리즘에서는 각 군집중앙간의 거리만을 계산하면 되므로 덜 게으르다. KNN에 대해 모른다면 그냥 넘어가자. KNN에 대해서는 추후 포스팅을 하겠다.

군집 중앙으로, 속성 공간에서 K개의 점을 선택해 시작한다. 이 K개의 점들은 훈련데이터에서 무작위로 선택한다. 사실 이 초기 중앙을 선택(갯수를 정하는 것이 아님, 중앙을 어떻게 선택하느냐의 문제를 말함)하는 몇 가지 방법들이 있다. 하나는 속성(변수)공간에서 임의의 점을 선택하는 방법이고 다른 하나는 각 예제들을 군집으로 무작위로 묶고 알고리즘 변경단계로 바로 가는것이다. 후자는 같은 K개의 초기 중앙 갯수를 잡아도 결과가 다르게 나올 수가 있다. 즉 최종군집에 특정 편향을 가져다 줄수가 있다.

초기 군집 중앙을 선택한 후 다른 예제는 거리 함수에 따라 가장 가깝거나 유사한 군집중앙으로 지정된다. 여기서 거리함수는 유클리드거리를 주로 사용하지만, 맨하튼이나, 민코우스키 거리도 가끔 사용한다. 이렇게 각 예제와 군집 중앙들 사이의 거리를 구해 예제와 가장 가까운 군집 중앙을 선택해 그 해당 군집에 포함시킨다. 

보로노이 다이어그램 보로노이 다이어그램은 어떤 시드 점(seed point)들과의 거리에 따라서 평면을 분할한 그림으로서, 평면위에 주어진 시드 점 p1, p2, ..., pn에 대한 보로노이 다이어그램은 평면위의 점들이 어떤 pi와 가장 가까운지에 따라서 영역을 분할한 다이어그램을 말합니다. 참고 : http://darkpgmr.tistory.com/96

위에 설명 되어 있지만 보로노이 다이어그램은 다른 군집 중앙보다 가까운 "영역"을 나타낸다. 여기서 만나는 각 꼭지점들은 해당 인접 영역들의 군집중앙으로부터 가장 먼거리에 있다.  따라서 초기 K 평균 시드가 나타나는 영역을 쉽게 볼 수 있다. 

2. 반복 

이렇게 초기 지정 단계는 완료가 됐다. 다음 단계는 현재 군집에 지정된 점들의 평균(Mean)인 중앙점이라는 새로운 지점으로 초기 중앙을 옮긴다. 새롭게 옮겨진 중앙에 따라 군집 경계가 조정된다. 이렇게 경계가 다시 재지정되면 예제간의 이동이 일어날 것이다. 각 군집에 새로운 예제가 들어오가나 나가므로 각 군집의 전체 평균은 변할 것이고, 이는 곧 군집중앙점의 이동으로 이어진다. 이렇게 이동이 되면 다시 군집경계가 조정이 될 것이다. 이 일련의 과정을 계속 반복하여 더이상 재지정되는 점이 없게 된다면 이 알고리즘은 멈추고, 군집지정을 마친다.

학습군집은 각 예제에 대한 군집지정을 보고하거나, 최종 군집 중앙점들의 좌표를 보고할 수 있다. 

여기서 한가지 의문이 든다. 그런데 초기값(초기군집갯수)는 어떻게 정해지는 것일까?

K-Means 알고리즘의 고질적인 문제는 바로 이 K의 갯수 설정이다. 이를 어떻게 설정하느냐에 따라 매우 다른 결과를 얻을 것이다. K가 매우 크다면 군집의 동질성을 향상이 되겠지만 동시에 데이터에 대한 과적합화가 될 위험이 있다.

이에 관련해서는 2가지 방법이 존재한다. 한가지 방법은 이상적으로 올바른 그룹에 대한 사전지식이 있고 이 정보를 사용해 K를 정하는 방법이다. 예를 들어 영화를 군집할때에는 아카데이상에서 고려하는 장르의 개수, 초대할 연구의 학문적 분야 개수같이 통상적으로 정해진 군집들을 사용하기도 하고, 사업요구나 분석동기에 따라 군집 개수를 정하기도 한다. 예를들어 마케팅 부서가 3가지 구분된 광고를 만들기 위한 자원을 가지면 잠재적인 고객이 3가지 매력중 하나에 이끌릴 수 있게 k=3으로 설정하는 것이다. 

두번째 방법은 사전지식이 없다면 엘보우 기법이란 통계적 기법을 사용하는 것이다. 엘보우 기법으로 알려진 기술은 여러가지 k 값에 대해 군집 변경 내의 동질 성과 이질성을 측정하는 측정하는 방법이다.

그룹내의 동질성과 군집갯수간의 그래프		그룹내의 이질성과 군집갯수 간의 그래프

군집 내 동질성(between groups sum of squares)은 군집(k, Number of Cluster)가 증가할 수록 증가하고, 마찬가지로 그룹 내 이질성(혹은 Wtihin groups sum of squares)은 점차 감소한다. 각 예제에서는 각 군집에서 계속 증가하는 것을 볼 수 있지만, 그 목적은 동질성을 최대로 높이고 이질성을 최대로 낮추는 데 있다. 어떤 점에서 절감하는 즉 미분해보았을때 절대값 기울기가 1 이하인..?  k를 찾는다. 사실 이 적정한 k 를 찾는데 실험을 통해서 찾는 방법 즉 휴리스틱적인 방법을 쓰는것은 커다란 데이터셋에서는 시간이 많이 걸리기 때문에 한계가 있다. 따라서 엄격하게 k 의 갯수를 정하기 보다는 사전지식을 통한 k 값을 정해 편의성을 도모하는 경우가 더 많다.