MLDSS: K-Means Clustering, MIA CH10

Grouping unlabeled items using k-means clustering

K-Means clusetring

K-Means clustering은 데이터를 K 개의 클러스터로 분류한다. 각 클러스터에 속한 아이템의 MEANcentroid 가 되어 분류의 주요 기준으로 사용된다. 전체 공간에 뿌려진 아이템들은 가장 가까운 센트로이드에 속하게 되고, 센트로이드는 자기 아이템의 평균으로 갱신된다. (센트로이드 정하기 -> 센트로이드 업데이트) 를 변화가 없을때까지 반복하면 된다.

Distance metric

아이템과 센트로이드가 얼마나 멀리 있는가를 정의해야 한다. 얼마나 비슷한가로 말을 바꾸면 Similarity metric 이 된다.
일단 가장 직관적인 유클리드 거리를 써 보자.

Read data

책에 있…는건 참고만 해서 한번 만들어 봅시다. 일단 pandas 를 한번 써봅시다.

In [1]:
import pandas as pd

def load_data_set(fname):
    d = pd.read_table(fname, sep='\t', header=None, dtype=np.float64)
    return d
    
df = load_data_set('machinelearninginaction/Ch10/testSet.txt')
df.plot(x=0, y=1, kind='scatter', marker='o', title='rawdata')
Out[1]:
<matplotlib.axes.AxesSubplot at 0x3c91810>

euclidean distance

당연히 누가 구현해 놨겠지. scipy 의 cdist 함수는 두 개의 벡터 A, B 를 받아서 AxB 의 모든 페어에 대한 계산 결과를 2차원 배열로 리턴한다. 이게 어디에 좋은지는… 아래에 구현할 K-Means 를 보면 안다. 반복문 깊이 하나를 이 함수가 해결해줄 수 있다.

In [2]:
from scipy.spatial.distance import cdist

dist_euclid = lambda x, y: cdist(x, y, metric="euclidean")
dist_euclid([[0,0], [3,2]], [[1,1], [5.3, 2.3]])
Out[2]:
array([[ 1.41421356,  5.77754273],
       [ 2.23606798,  2.3194827 ]])

Initial centroids

여기선 그냥 랜덤하게 정한다. 이걸 좀 똑똑하게 하면 요새 많이들 쓴다는 KMeans++ 이 된다. 참고로 scikit-learn 의 KMeans 구현에 init 함수를 지정할 수 있는데 기본값이 k-means++ 이다. ^1

In [3]:
def initial_centroids(data_set, k):
    centroids = np.mat(np.zeros((k, len(data_set.axes))))
    for j, x in enumerate(data_set):
        centroids[:, j] = np.reshape([np.random.uniform(data_set[x].min(), data_set[x].max()) for _ in range(k)], (k, 1))
    return centroids

centroids = initial_centroids(df, 3)
scatter(df[0], df[1], marker='o')
scatter(centroids[:,0].getA1(), centroids[:,1].getA1(), c='red', s=80, marker='x')
title('Initial random centroids')
Out[3]:
<matplotlib.text.Text at 0x40aef10>

Implement K-Means

모든 아이템의 클러스터 번호 할당이 변화가 없을때까지 돌린다. 아래 함수에서 np.meannp.median 으로 바꾸면 K-Median Clustering 이 되는데, 여기서 사용하는 샘플 데이터에는 결과가 좋지 않았다. 데이터/문제 특성을 많이 타겠지.

In [4]:
def KMeans(data_set, k, dist_func=dist_euclid, init=initial_centroids):
    colors = plt.cm.rainbow(np.linspace(0, 1, k))
    centroids = init(data_set, k)
    cluster_ids = [-1]*len(data_set)
    step=0
    while True:
        step+=1
        dist_matrix = dist_func(data_set, centroids)
        new_cluster_ids = pd.DataFrame(dist_matrix).idxmin(1).values

        if (new_cluster_ids == cluster_ids).all():
            break

        cluster_ids = new_cluster_ids
            
        figure()
        for c in range(k):
            cluster_data_set = data_set[cluster_ids==c]
            centroids[c,:] = np.mean(cluster_data_set)
            
            title('Step #%d' % step)
            scatter(cluster_data_set[0], cluster_data_set[1],
                    marker='o', color=colors[c])
            ct = centroids[c,:].getA1()
            scatter(ct[0], ct[1], s=80, marker='x', color='red')
            
    return {'cluster_ids': cluster_ids,
            'centroids': centroids}
            
print KMeans(df, 4)
{&apos;cluster_ids&apos;: array([1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
       0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2,
       3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1,
       2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0]), &apos;centroids&apos;: matrix([[-3.38237045, -2.9473363 ],
        [ 2.6265299 ,  3.10868015],
        [-2.46154315,  2.78737555],
        [ 2.80293085, -2.7315146 ]])}

Bisecting K-Means

귀찮으므로 자세한 설명은 생략한다. Hiearchical clustering 의 바이너리 스플릿에 k=2 를 준 K-Means 를 사용한다고 보면 된다. 처음에 전체 데이터에 대해 2-Means 를 실행하고, 두 클러스터 중 SSE(Sum of Squared Error, or Residual Squared Error)^2 가 더 큰 클러스터에 대해 다시 2-Means 를 실행. 2-Means 를 한번 실행할 때마다 클러스터 개수가 하나씩 늘어나고, 전체 클러스터 수가 K 가 될때까지 이 작업을 반복한다.

Is it good really?

Bisecting K-Means 는 이 책을 공부하며 처음 들었다. Sh. 님이 검색해주신 논문들에 의하면 일반적으로 K-Means 보다는 좋다고 한다. Refined 라는 수식어가 붙은 경우도 있는데, 이는 Bisecting K-Means 의 결과를 초기 센트로이드로 놓고 다시 K-Means 를 실행하는 경우다.

그런데 관련 논문들이 K-Means 가 아니라 K-Means++ 과 비교하진 않고 있는 점이 좀 아쉽다.

… 그냥 K-Means++ 쓰면 안될까요?

What’s different?

그냥 공간의 분할에 대한 내 느낌을 적어보자면, K-Means 는 기본적으로 보로노이 다이어그램 모양으로 공간을 분할한다. 아래는 Scikit-learn 의 예제 코드 를 빌려온 것이다.

In [5]:
print(__doc__)

from time import time
import numpy as np
import pylab as pl

from sklearn import metrics
from sklearn.cluster import KMeans
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
from sklearn.preprocessing import scale

np.random.seed(42)

digits = load_digits()
data = scale(digits.data)

n_samples, n_features = data.shape
n_digits = len(np.unique(digits.target))
labels = digits.target

sample_size = 300

print("n_digits: %d, \t n_samples %d, \t n_features %d"
      % (n_digits, n_samples, n_features))


print(79 * '_')
print('% 9s' % 'init'
      '    time  inertia    homo   compl  v-meas     ARI AMI  silhouette')


def bench_k_means(estimator, name, data):
    t0 = time()
    estimator.fit(data)
    print('% 9s   %.2fs    %i   %.3f   %.3f   %.3f   %.3f   %.3f    %.3f'
          % (name, (time() - t0), estimator.inertia_,
             metrics.homogeneity_score(labels, estimator.labels_),
             metrics.completeness_score(labels, estimator.labels_),
             metrics.v_measure_score(labels, estimator.labels_),
             metrics.adjusted_rand_score(labels, estimator.labels_),
             metrics.adjusted_mutual_info_score(labels,  estimator.labels_),
             metrics.silhouette_score(data, estimator.labels_,
                                      metric='euclidean',
                                      sample_size=sample_size)))

bench_k_means(KMeans(init='k-means++', n_clusters=n_digits, n_init=10),
              name="k-means++", data=data)

bench_k_means(KMeans(init='random', n_clusters=n_digits, n_init=10),
              name="random", data=data)

# in this case the seeding of the centers is deterministic, hence we run the
# kmeans algorithm only once with n_init=1
pca = PCA(n_components=n_digits).fit(data)
bench_k_means(KMeans(init=pca.components_, n_clusters=n_digits, n_init=1),
              name="PCA-based",
              data=data)
print(79 * '_')

###############################################################################
# Visualize the results on PCA-reduced data

reduced_data = PCA(n_components=2).fit_transform(data)
kmeans = KMeans(init='k-means++', n_clusters=n_digits, n_init=10)
kmeans.fit(reduced_data)

# Step size of the mesh. Decrease to increase the quality of the VQ.
h = .02     # point in the mesh [x_min, m_max]x[y_min, y_max].

# Plot the decision boundary. For that, we will assign a color to each
x_min, x_max = reduced_data[:, 0].min() + 1, reduced_data[:, 0].max() - 1
y_min, y_max = reduced_data[:, 1].min() + 1, reduced_data[:, 1].max() - 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

# Obtain labels for each point in mesh. Use last trained model.
Z = kmeans.predict(np.c_[xx.ravel(), yy.ravel()])

# Put the result into a color plot
Z = Z.reshape(xx.shape)
pl.figure(1)
pl.clf()
pl.imshow(Z, interpolation='nearest',
          extent=(xx.min(), xx.max(), yy.min(), yy.max()),
          cmap=pl.cm.Paired,
          aspect='auto', origin='lower')

pl.plot(reduced_data[:, 0], reduced_data[:, 1], 'k.', markersize=2)
# Plot the centroids as a white X
centroids = kmeans.cluster_centers_
pl.scatter(centroids[:, 0], centroids[:, 1],
           marker='x', s=169, linewidths=3,
           color='w', zorder=10)
pl.title('K-means clustering on the digits dataset (PCA-reduced data)\n'
         'Centroids are marked with white cross')
pl.xlim(x_min, x_max)
pl.ylim(y_min, y_max)
pl.xticks(())
pl.yticks(())
pl.show()
Automatically created module for IPython interactive environment
n_digits: 10, 	 n_samples 1797, 	 n_features 64
_______________________________________________________________________________
init    time  inertia    homo   compl  v-meas     ARI AMI  silhouette
k-means++   0.72s    69432   0.602   0.650   0.625   0.465   0.598    0.146
   random   0.64s    69694   0.669   0.710   0.689   0.553   0.666    0.147
PCA-based   0.05s    71820   0.673   0.715   0.693   0.567   0.670    0.150
_______________________________________________________________________________

Bisecting K-Means 는 공간을 보로노이 다이어그램과는 좀 다른 모양으로 자르는 것 같다. 공간 분할 트리랑 비슷한 느낌?

Spherical distance

책에 있는 실습 부분은 별다를게 없다. 다만, 지구 위의 두 점 사이의 거리를 구하는 부분을 이해하는데 좀 시간이 걸렸다. 책에서는 Spherical law of cosines 를 알면 된다고 하는데, 내가 학교 다닐때 이걸 배운적이 없다. 혹은 배웠다는 사실도 까먹었거나.

  • (경도, 위도) 로 주어진 좌표를 (x, y, z)의 3차원 좌표로 변환
  • (x, y, z) 의 두 좌표의 최단거리는 구의 GreatCircle 위에 있다.
  • 내적의 정의에 따라 두 좌표의 내적은 Unit sphere에서의 코사인 값이다.
  • 그러므로 내적값의 arccos 를 구하고 구의 반지름을 곱하면 끝.

Spherical distance 혹은 Great Circle Distance 등으로 검색하면 계산 과정을 상세하게 볼 수 있다.

Comments