Clustering - 군집 개수 정하기

이전 포스트에서 군집화의 대표 알고리즘 K-Means에 알아보았습니다. K-Means의 대표적인 특징으로는 군집의 개수 $k$를 미리 설정해주어야 하는 것이었는데요. 데이터에 대한 사전 지식이나 나눌 그룹의 수를 미리 정의한 경우에는 괜찮지만 그러한 배경이 없는 경우 군집화가 비지도 학습이라 정답이 없기 때문에 일반적인 성능평가 방법을 이용할 수 없습니다. 어떻게 군집 알고리즘에 대한 성능평가를 내려 $k$를 적절하게 설정할 수 있을까요? 

Elbow method

가장 대표적인 방법으로 지난 포스트에서 다루었던 inertia 를 이용하는 방법입니다. Inertia는 각 군집 별 오차의 제곱의 합으로 군집 내 분산으로 정의할 수 있는데, 일반적으로 $k$가 증가하면 샘플이 할당된 센트로이드에 가까워져 inertia가 줄어들게 됩니다. Elbow 방법은 inertia가 빠르게 변하는 지점을 최적의 $k$로 설정하는 것입니다.

지난 포스트의 예제처럼 sklearn.datasets의 make_blobs 함수로 3개의 군집을 형성하는 가짜 데이터를 생성하고 군집의 개수에 따라 inertia를 그려보겠습니다.

from sklearn.cluster import KMeans

import matplotlib.pyplot as plt

inertia = []
for i in range(1, 11):
    kmeans_plus = KMeans(n_clusters=i, init='k-means++')
    kmeans_plus.fit(X)
    inertia.append(kmeans_plus.inertia_)

plt.plot(range(1, 11), inertia, marker='o')
plt.xlabel('Number of clusters')
plt.ylabel('Inertia')
plt.show()

위 그림을 보면 $k$가 증가할수록 inertia가 감소하는 것을 볼 수 있으며, $k=3$ 일때 inertia가 급격히 감소한 것을 볼 수 있으므로 $k=3$ 으로 설정합니다.

Silhouette

Elbow 방법은 군집 내 분산을 보는 것으로서 급격히 꺾이는 지점을 보여줍니다. 하지만 그래프가 애매하게 완만하다면 급격히 꺾이는 지점을 명확히 정할 수는 없습니다. 특히 다음 경우와 같이 3개의 군집을 형성되었지만 군집끼리 어느 정도 붙어있는 경우 $k=2$ 일때 inertia가 급격히 꺾이게 되며 이러한 경우는 잘못된 $k$의 선택을 유발합니다.

즉, elbow 방법은 명확하게 한 군집의 개수를 선택하기가 쉽지 않고 군집 내의 분산만 고려하다보니 잘못된 $k$의 선택을 유발합니다. 이때 조금 더 나은 방법으로 Silhoutte coefficient 를 사용할 수 있습니다.

Silhoutte 계수를 정하기 위해서 특정 샘플과 그 샘플이 속한 군집의 데이터들의 평균 거리와 그 샘플이 속하지 않은 다른 군집의 모든 데이터들과의 평균 거리의 최소값을 계산합니다. 먼저 샘플 $i$와 그 객체가 속한 군집의 데이터들과의 거리를 모두 계산하여 해당 군집의 비유사성 $a(i)$을 계산합니다. Equation 1의 $g(x_i)$는 $x_i$가 속한 군집을 말하며 $d$는 거리로 Euclidean이나 Manhatten 거리를 말합니다..

Equation 1

다음으로 샘플이 속하지 않은 다른 군집의 모든 데이터들과의 평균 거리의 최소값 $b(i)$을 계산합니다. 간단히 말하면 $b(i)$는 속하지 않은 가장 가까운 군집에 속한 데이터들의 평균 거리를 말합니다. Equation 2의 $g_k$는 $x_i$가 속하지 않은 다른 군집을 말합니다.

Equation 2

$a(i), b(i)$를 정의한 이후 Silhoutte 계수 $s(i)$를 Equation 3과 같이 정의하고 모든 데이터에 대해 계산한 후 평균을 내어 해당 군집 개수에 대한 Silhoutte 계수로 사용합니다. Equation 3을 보았을 때 군집이 잘 된 경우라면 $a(i)$가 $b(i)$보다 작아야 하므로 $s(i)$가 1에 가까울수록 $x_i$가 올바른 군집으로 할당되었다고 볼 수 있습니다. 결과적으로 군집 개수를 변화시키면서 평균 Silhoutte 계수가 최대가 되는 군집 개수를 선택합니다. 

Equation 3

파이썬에서는 sklearn.metrics 모듈의 silhouette_samples(X, label (군집 결과)) 함수를 통해 쉽게 계산할 수 있습니다. (sklearn.metrics 모듈의 silhouette_score(X, 군집 결과) 함수를 이용하면 바로 평균 Silhouette 계수를 구할 수 있습니다.)

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples

import numpy as np
import matplotlib.pyplot as plt

silhouette_vals = []
for i in range(2, 11):
    kmeans_plus = KMeans(n_clusters=i, init='k-means++')
    pred = kmeans_plus.fit_predict(X)
    silhouette_vals.append(np.mean(silhouette_samples(X, pred, metric='euclidean')))

plt.plot(range(2, 11), silhouette_vals, marker='o')
plt.xlabel('Number of clusters')
plt.ylabel('Silhouette')
plt.show()