지난 글에서는 클러스터링의 두 가지 종류(분할 군집과 계층적 군집)와 클러스터링의 활용 분야에 대해 알아보았다. 이번 글에서는 분할 군집(Partition Clustering)의 대표 주자 K-Means 클러스터링의 원리, 단점과 극복 방안, 클러스터링 평가법에 대해 알아본다.
■ K-Means 클러스터링
K-Means 클러스터링은 대표적인 분할 군집 기법이다. 각 군집은 중심(centroid)을 갖고, 그 중심에 가장 가까운 데이터 포인트끼리 묶어 군집화하는 과정이다. 이 때 군집의 숫자인 ‘K’는 연구자가 직접 설정해야한다. K-Means는 상당히 간단한 알고리즘이다.
스텝으로 나눠서 설명하자면,
1. 먼저 데이터 산점도에서 K개의 중심을 랜덤하게 선정한다.
2. 그 중심에 가까운 데이터를 군집으로 분류한다.
3. 중심에서 각 데이터 포인트까지의 거리를 계산하여 평균을 낸 뒤, 중심을 평균점으로 이동한다.
4. 이동된 중심을 기준으로 다시 가까운 데이터 포인트를 군집으로 할당한다.
5. 3번~4번을 반복한다. 언제까지? 데이터 포인트가 다른 군집으로 재할당되지 않거나 중심이 더이상 이동하지 않을 때, 그리고 SSE(Sum of squared errors, 오차제곱합)이 최소화될 때! 관련 순서의 도식은 다음 블로그를 참고하면 좋겠다.
이때 SSE를 구하는 것이 가장 일반적이다. 여기서 오차(즉 error)란 각 데이터와 가장 가까운 군집의 중심과의 거리를 말한다.
위의 그림에서 빨간색 점을 군집의 중심이라고 해보자. 왼쪽과 오른쪽 군집 중에 어떤 것이 더 좋은 군집일까? 당연히 각 데이터와 중심이 가까운 오른쪽 클러스터링이 더 좋다. 즉, SSE를 최소화하는 군집이다.
■ K-Means의 단점 = K!
그러나 K-Means가 완벽한 솔루션은 아니다. K-Means의 단점 중의 하나는 K를 연구자가 설정해야하고, K의 중심은 랜덤하게 분포된다는 것이다.
위와 같이 시작하는 중심점이 운 나쁘게- 시작되었다고 치자. 그 중심에 맞게 군집을 할당하고 그 군집 내 평균점으로 이동한다한들(그림의 오른쪽), 좋은 군집이 아니란 것을 한 눈에 알 수 있다.
■ K-Means의 단점을 극복하는 방법 – 적절한 K의 숫자와 시작 위치를 찾아라!
K의 시작 위치가 랜덤하다는 단점을 극복하는 방법으로는, 여러 차례 분석하는 방법이 있다. K의 숫자는 변경하지 않고 여러 번 시작점을 옮겨보며 SSE가 가장 작은 값을 갖는 군집을 선택하여 아웃라이어를 제거하는 방식이다.
K의 적절한 숫자를 찾기 위한 방법 역시 단순 노가다! 바로, K의 값을 작은 값으로 시작해서 하나씩 늘려가면서 결과값을 비교해보는 것이다. (경험적으로 K값은 1~10 사이에 있다.) 연구자들은 여러 알고리즘을 통해 자동으로 K값을 찾는데, 대표적으로 Knee value(elbow value라고도 한다)가 있다. 그래프의 무릎에 있다고 해서 knee 값이다. ankle value라고 해야 더 맞을 것 같은데..
위와 같이 적절한 K 값을 구할 수 있다. 실제 파이썬으로 돌려보는 것은 다음 글의 연습으로 다뤄볼까 한다. 아무튼 K 값이 늘어나도 SSE의 개선이 가장 줄어드는 포인트인 knee value(위 그림에서는 K가 6이 될 때 기울기가 감소한다)를 찾아 K 값을 정할 수 있다.
■ K-Means의 또 다른 단점과 극복 방법 – 아웃라이어를 잡아라!
앞서서 K-Means의 단점과 이를 극복하는 방법에 대해 알아보았다. 그러나 극복되지 않는 K-Means의 한계점이 아직 남았다. 바로 아웃라이어(Outlier)에 취약하다는 점이다. 우리는 아래와 같이 아웃라이어 1개 데이터때문에 군집의 중심이 바뀌는 것을 원하지 않는다.
아웃라이어에 취약하다는 K-Means의 단점을 극복하려면 중심에서 먼 데이터를 애초에 없애버리는 방식이 있다. 이 때 제거하고자 하는 데이터가 진짜 아웃라이어인지 주의해서 확인할 필요가 있다. 즉, 아웃라이어일 가능성이 높은 데이터를 여러번 관찰해보고 없앨 것을 추천한다. 물론 원데이터에 조작을 가하는 것이므로 최선보다는 차선책이다.
또 다른 방법으로는 랜덤 샘플링(random sampling)이 있다. 만약 데이터 사이즈가 크다면 아웃라이어를 선택한 확률이 매우 떨어질 것을 이용한 방식이다. 랜덤 샘플링을 통해 데이터를 추출하면 좀 더 빠르게 모델을 만들 수 있다는 장점도 있다. 그러나 이 역시 데이터의 사이즈가 작다면 취할 수 없다.
마지막 방법은 K-Medoids 라는 K-Means의 변형 형태를 사용하는 것이다. Medoids는 각 클러스터의 평균이 아닌 중앙값(median)을 사용한다. 알고 있다시피 중앙값은 아웃라이어에 영향을 덜 받는다.
■ 클러스터링 평가하기
다시 한 번, 클러스터링의 목적을 되새겨보자. 군집 내 데이터끼리의 거리는 작게(즉 cohesion은 크게) 군집끼리의 거리는 크게(즉 seperation은 크게)!
Cohesion a(x)란 같은 군집 내에 있는 모든 데이터(벡터값)의 평균 거리 x를 의미한다. 이 a(x)가 작다는 것은 군집내 응집력이 높다는 것을 의미한다. 반면, Separation b(x)는 먼저 특정 데이터와 해당 데이터가 속하지 않는 다른 군집의 모든 데이터 지점 간 거리의 평균을 계산한다. 그중 가장 작은 거리 값이 x가 된다. 즉, 데이터와 가장 가까운 이웃에 위치한 군집을 선택했음을 의미한다.
실루엣 값(Silhouette) s(x)와 실루엣 계수(Silhouette coefficient)을 공식으로 표현하면 다음과 같다.
식은 좀 더 쪼개서 생각해보자. 가장 이상적인 케이스를 생각해보면 쉬운데, 모든 데이터가 하나의 점에 위치하는, a(x)가 0이 되는 군집이다. 이 때 공식에 대입하면 (b(x) – 0)/(b(x)) = 즉 1이 나온다. 이렇게 a(x)값이 0에 가깝거나 b(x)값이 무한대에 가깝게 커질수록, 다시 말해 각 군집 사이의 거리가 아주 멀고 군집 내 데이터의 거리가 작을수록 군집 분석의 성능이 좋음을 알 수 있다.
실루엣 값은 -1에서 1까지 존재한다. 실루엣 값이 0일 경우에는 이 군집에 있나 저 군집에 있나 변별력이 없다는 것을 의미한다. 당연히 -1에 가까울수록 군집 분석의 결과가 나쁘다는 것을 의미한다.
실루엣 계수로는 앞서 knee value처럼 K의 개수를 선택할 때 참고할 수도 있다. 이때는 실루엣 계수가 가장 커지는 K 값을 찾으면 된다. (vs. knee value는 가장 기울기가 감소하는 지점을 선택한다는 것을 유념하자.)