대표적인 비계층형 클러스터링 기법으로서 k-means가 알려져 있다.

k-means는 빌드할 클러스터 수 k를 입력으로 제공해야 하지만 최적의 k 값은 시행착오하면서 찾아야 합니다.

이 k 를 자동 추정하기 위한 수법으로서 엘보법이라고 하는 수법이 있습니다.

k-means법이란?

주어진 데이터를 k개의 클러스터로 분할하는 비계층적 클러스터링 기법입니다.

k-means의 동작 이미지는 아래의 페이지가 굉장히 알기 쉽습니다.
K-means 방법을 D3.js로 시각화 해 보았습니다.

k-means의 이미지는 ↑와 같은 느낌이지만, 수학적으로는 이하의 식을 최소화하는 문제로서 정식화할 수 있습니다.

\sum_{i=1}^{k}\sum_{p\in C_{i}}(p-c_{i})^2

여기서 $k$는 클러스터 수, $C_{i}$는 $i$번째 클러스터에 포함된 데이터 포인트 집합, $c_{i}$는 $C_{i}$의 중심입니다.

또한 이 값을 SSE(Sum of Squared errors of prediction)이라고 합니다.

엘보법이란?

엘보법에서는 클러스터 수를 바꾸면서 위의 SSE 을 계산하고 결과를 그림으로써 최적(이라고 생각되는) 클러스터 수를 추정하는 방법입니다.

클러스터 수를 바꾸면서 SSE를 계산하고 그림으로 표시하면 예를 들면 다음과 같은 그래프가 됩니다.


가로축에 클러스터 수, 세로축에 SSE를 나타내면 팔꿈치(팔꿈치)와 같이 포키와 구부러진 장소가 있는 것을 알 수 있습니다.
위의 예에서는 클러스터 수 = 4의 점에서 그래프가 포키와 구부러져 있네요.

엘보법에서는 이러한 점을 찾아 최적의 (라고 생각되는) 클러스터 수를 추정합니다.

sklearn.cluster.KMeans

scikit-learn의 k-means 용 클래스 를 살펴보면 다음과 같은 설명이 있습니다.

Attributes:
inertia_ : float
Sum of squared distances of samples to their closest cluster center.

맞습니다.
이 값을 사용하면 한 번에 SSE에 액세스할 수 있습니다.

소스 코드

전문은 여기에 있습니다 (jupyter notebook).
이번에는 제 이해를 위해 위의 inertia_를 사용하여 계산한 SSE를 다른 방법으로도 계산하여 실수가 없는지 확인했습니다.
실제로 엘보법으로 SSE를 계산하는 것은 다음 부분입니다.

# エルボー法で最適なクラスタ数を探索する
sse = np.zeros((max_cluster_num,))     # Sum of Square Error（クラスタ内誤差平方和）
se = np.zeros((max_cluster_num,))      # Sum of Error（クラスタ内誤差和）
inertia = np.zeros((max_cluster_num,)) # scikit-learnにより自動計算するクラスタ内誤差平方和
for i in range(max_cluster_num):
    cluster_num = i + 1
    kmeans = KMeans(n_clusters=cluster_num)
    # 各データがどのクラスタに所属するか
    pred = kmeans.fit_predict(data_array)
    inertia[i] = kmeans.inertia_

    # 各データが自身の所属するクラスタ中心からどれだけ離れているか調べる
    transforms = kmeans.transform(data_array)    
    distances = np.zeros((data_array.shape[0]))
    for index in range(len(transforms)):
        distances[index] = transforms[index,pred[index]]

    se[i] = np.sum(distances)
    sse[i] = np.sum(distances**2)

결과

이번에 사용한 데이터는 이하의 2차원 데이터입니다.
정규 분포로 적당한 파라미터를 지정해 5 클러스터가 되도록(듯이) 했습니다.


SSE를 계산하여 도시한 결과가 이쪽.


클러스터 4 근처에서 포키와 접혀 있네요.
이번의 경우는 실제로는 클러스터수 5가 정답입니다만, 분석하는 데이터가 2차원(혹은 3차원)으로 가시화 가능한 것은 드물다고 생각합니다.
데이터가 어떤 형태를 하고 있는지 모른다고 하는 전제로 생각하면 클러스터수 4라고 하는 추정은 아무튼 좋은 결과는 아닐까요.

최적일 것으로 추정한 클러스터 수 프라마이 1씩(3, 4, 5)의 결과를 도시해 보았습니다.


나란히 보면 클러스터수 5가 최적인 것은 명확합니다만, 클러스터수 3의 결과와 클러스터수 4의 결과를 비교하면 어쩐지 이번의 결과가 된 것도 납득할 수 있는 생각이 듭니다.

실수 등이 있으면 꼭 지적하십시오.