다운로드
작성자: admin 작성일시: 2016-06-28 22:46:24 조회수: 5807 다운로드: 330
카테고리: 머신 러닝 태그목록:

K-Means 클러스터링

독립 변수의 특성이 유사한 데이터의 그룹을 클러스터(cluster)라고 한다. 주어진 데이터를 여러개의 클러스터로 구분하는 것을 클러스터링(clustering)이라고 한다. 만약 클러스터의 갯수가 $K$라면 클러스터링은 모든 데이터에 대해 각 데이터가 1번부터 $K$번 클러스터 중에 어떤 클러스터에 속하는지 예측하는 작업이다.

K-Means

K-Means 클러스터링 알고리즘은 가장 단순하고 빠른 클러스터링 알고리즘의 하나이다.

기본적인 방법은 다음과 같은 목적함수 값이 최소화될 때까지 클러스터의 중심(centroid) $\mu_k$과 각 데이터가 소속될 클러스터를 반복해서 찾는 것이다. 이 값을 inertia라고도 한다.

$$ J = \sum_{k=1}^K \sum_{i \in C_k} d(x_i, \mu_k) $$

이 식에서 $d$는 두 데이터의 비유사도(dissimilarity) 혹은 거리(distance)로 다음과 같이 정의한다.

$$ d(x_i, \mu_k) = || x_i - \mu_k ||^2 $$

세부 알고리즘은 다음과 같다.

  1. 임의의 중심값 $\mu_k$ 를 고른다. (보통 데이터 샘플 중의 하나를 선택)
  2. 중심에서 각 샘플 데이터까지의 거리를 계산
  3. 각 데이터 샘플에서 가장 가까운 중심을 선택하여 클러스터 갱신
  4. 다시 만들어진 클러스터에 대해 중심을 다시 계산하고 1 ~ 4를 반복한다.
In [1]:
X = np.array([[7, 5], [5, 7], [7, 7], [4, 4], [4, 6], [1, 4],
              [0, 0], [2, 2], [8, 7], [6, 8], [5, 5], [3, 7]])
plt.scatter(X[:, 0], X[:, 1], s=100)
plt.show()
In [2]:
from sklearn.cluster import KMeans

1회차

In [3]:
model1 = KMeans(n_clusters=2, init="random", n_init=1,
               max_iter=1, random_state=1).fit(X)
In [4]:
c0, c1 = model1.cluster_centers_
c0, c1
Out:
(array([ 6.6,  6.8]), array([ 2.71428571,  4.        ]))
In [5]:
model1.score(X)
Out:
-63.004081632653012
In [6]:
def plot_cluster(model, c0, c1):
    plt.scatter(X[model.labels_ == 0, 0],
                X[model.labels_ == 0, 1], s=100, marker='v', c='r')
    plt.scatter(X[model.labels_ == 1, 0],
                X[model.labels_ == 1, 1], s=100, marker='^', c='b')
    plt.scatter(c0[0], c0[1], s=200, c="r")
    plt.scatter(c1[0], c1[1], s=200, c="b")
    plt.show()
In [7]:
plot_cluster(model1, c0, c1)
In [8]:
def kmeans_df(model, c0, c1):
    df = pd.DataFrame(np.hstack([X,
                                 np.linalg.norm(X - c0, axis=1)[:, np.newaxis],
                                 np.linalg.norm(X - c1, axis=1)[:, np.newaxis],
                                 model.labels_[:, np.newaxis]]),
                      columns=["x0", "x1", "d0", "d1", "c"])
    return df
In [9]:
kmeans_df(model1, c0, c1)
Out:
x0 x1 d0 d1 c
0 7.0 5.0 1.843909 4.400835 0.0
1 5.0 7.0 1.612452 3.771537 0.0
2 7.0 7.0 0.447214 5.231381 0.0
3 4.0 4.0 3.820995 1.285714 1.0
4 4.0 6.0 2.720294 2.377617 1.0
5 1.0 4.0 6.260990 1.714286 1.0
6 0.0 0.0 9.476286 4.833978 1.0
7 2.0 2.0 6.648308 2.123724 1.0
8 8.0 7.0 1.414214 6.077728 0.0
9 6.0 8.0 1.341641 5.176477 0.0
10 5.0 5.0 2.408319 2.494893 0.0
11 3.0 7.0 3.605551 3.013575 1.0
In [10]:
def calc_new_centroid(model):
    c0_new = (X[model.labels_ == 0, 0].mean(), X[model.labels_ == 0, 1].mean())
    c1_new = (X[model.labels_ == 1, 0].mean(), X[model.labels_ == 1, 1].mean())
    return c0_new, c1_new
In [11]:
calc_new_centroid(model1)
Out:
((6.333333333333333, 6.5), (2.3333333333333335, 3.8333333333333335))

2회차

In [12]:
model2 = KMeans(n_clusters=2, init="random", n_init=1,
               max_iter=2, random_state=1).fit(X)
In [13]:
c0, c1 = model2.cluster_centers_
c0, c1
Out:
(array([ 6.33333333,  6.5       ]), array([ 2.33333333,  3.83333333]))
In [14]:
model2.score(X)
Out:
-59.222222222222157
In [15]:
plot_cluster(model2, c0, c1)
In [16]:
kmeans_df(model2, c0, c1)
Out:
x0 x1 d0 d1 c
0 7.0 5.0 1.641476 4.810290 0.0
1 5.0 7.0 1.424001 4.139914 0.0
2 7.0 7.0 0.833333 5.639641 0.0
3 4.0 4.0 3.419714 1.674979 1.0
4 4.0 6.0 2.386304 2.733537 0.0
5 1.0 4.0 5.890199 1.343710 1.0
6 0.0 0.0 9.075302 4.487637 1.0
7 2.0 2.0 6.247222 1.863390 1.0
8 8.0 7.0 1.740051 6.491447 0.0
9 6.0 8.0 1.536591 5.550275 0.0
10 5.0 5.0 2.006932 2.910708 0.0
11 3.0 7.0 3.370625 3.236081 1.0
In [17]:
calc_new_centroid(model2)
Out:
((6.0, 6.4285714285714288), (2.0, 3.3999999999999999))

3회차

In [18]:
model3 = KMeans(n_clusters=2, init="random", n_init=1,
               max_iter=3, random_state=1).fit(X)
In [19]:
c0, c1 = model3.cluster_centers_
c0, c1
Out:
(array([ 6.        ,  6.42857143]), array([ 2. ,  3.4]))
In [20]:
model3.score(X)
Out:
-52.280816326530697
In [21]:
plot_cluster(model3, c0, c1)
In [22]:
kmeans_df(model3, c0, c1)
Out:
x0 x1 d0 d1 c
0 7.0 5.0 1.743794 5.249762 0.0
1 5.0 7.0 1.151751 4.686150 0.0
2 7.0 7.0 1.151751 6.161169 0.0
3 4.0 4.0 3.146102 2.088061 1.0
4 4.0 6.0 2.045403 3.280244 0.0
5 1.0 4.0 5.558593 1.166190 1.0
6 0.0 0.0 8.793551 3.944617 1.0
7 2.0 2.0 5.967600 1.400000 1.0
8 8.0 7.0 2.080031 6.997142 0.0
9 6.0 8.0 1.571429 6.095900 0.0
10 5.0 5.0 1.743794 3.400000 0.0
11 3.0 7.0 3.053937 3.736308 0.0
In [23]:
calc_new_centroid(model3)
Out:
((5.625, 6.5), (1.75, 2.5))

4회차

In [24]:
model4 = KMeans(n_clusters=2, init="random", n_init=1,
                max_iter=4, random_state=1).fit(X)
In [25]:
c0, c1 = model4.cluster_centers_
c0, c1
Out:
(array([ 5.625,  6.5  ]), array([ 1.75,  2.5 ]))
In [26]:
model4.score(X)
Out:
-47.625
In [27]:
plot_cluster(model4, c0, c1)
In [28]:
kmeans_df(model4, c0, c1)
Out:
x0 x1 d0 d1 c
0 7.0 5.0 2.034853 5.814852 0.0
1 5.0 7.0 0.800391 5.550901 0.0
2 7.0 7.0 1.463087 6.914658 0.0
3 4.0 4.0 2.981715 2.704163 1.0
4 4.0 6.0 1.700184 4.160829 0.0
5 1.0 4.0 5.257435 1.677051 1.0
6 0.0 0.0 8.595966 3.051639 1.0
7 2.0 2.0 5.778462 0.559017 1.0
8 8.0 7.0 2.427061 7.701461 0.0
9 6.0 8.0 1.546165 6.950719 0.0
10 5.0 5.0 1.625000 4.100305 0.0
11 3.0 7.0 2.672195 4.670385 0.0
In [29]:
calc_new_centroid(model4)
Out:
((5.625, 6.5), (1.75, 2.5))

5회차

In [30]:
model5 = KMeans(n_clusters=2, init="random", n_init=1,
                max_iter=5, random_state=1).fit(X)
In [31]:
c0, c1 = model5.cluster_centers_
c0, c1
Out:
(array([ 5.625,  6.5  ]), array([ 1.75,  2.5 ]))
In [32]:
model5.score(X)
Out:
-47.625
In [33]:
plot_cluster(model5, c0, c1)
In [34]:
kmeans_df(model5, c0, c1)
Out:
x0 x1 d0 d1 c
0 7.0 5.0 2.034853 5.814852 0.0
1 5.0 7.0 0.800391 5.550901 0.0
2 7.0 7.0 1.463087 6.914658 0.0
3 4.0 4.0 2.981715 2.704163 1.0
4 4.0 6.0 1.700184 4.160829 0.0
5 1.0 4.0 5.257435 1.677051 1.0
6 0.0 0.0 8.595966 3.051639 1.0
7 2.0 2.0 5.778462 0.559017 1.0
8 8.0 7.0 2.427061 7.701461 0.0
9 6.0 8.0 1.546165 6.950719 0.0
10 5.0 5.0 1.625000 4.100305 0.0
11 3.0 7.0 2.672195 4.670385 0.0
In [35]:
calc_new_centroid(model5)
Out:
((5.625, 6.5), (1.75, 2.5))

K-Means++

K-Means++ 알고리즘은 최초의 중심값을 설정하기 위한 알고리즘이다.

  1. 중심값을 저장할 집합 $M$ 준비
  2. 일단 하나의 중심 $\mu_0$를 랜덤하게 선택하여 $M$에 넣는다.
  3. $M$에 속하지 않는 모든 샘플 $x_i$에 대해 거리 $d(M, x_i)$를 계산. $d(M, x_i)$는 $M$안의 모든 샘플 $\mu_k$에 대해 $d(\mu_k, x_i)$를 계산하여 가장 작은 값 선택
  4. $d(M, x_i)$에 비례한 확률로 다음 중심 $\mu$를 선택.
  5. $K$개의 중심을 선택할 때까지 반복
  6. K-Means 알고리즘 사용

예: Iris

In [36]:
from mpl_toolkits.mplot3d import Axes3D
from sklearn.cluster import KMeans
from sklearn import datasets

np.random.seed(5)
centers = [[1, 1], [-1, -1], [1, -1]]
iris = datasets.load_iris()
X = iris.data
y = iris.target


def plot_iris_cluster(model):
    fig = plt.figure()
    ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
    model.fit(X)
    labels = model.labels_
    ax.scatter(X[:, 3], X[:, 0], X[:, 2], c=labels.astype(
        np.float), s=100, cmap=mpl.cm.jet)
    ax.w_xaxis.set_ticklabels([])
    ax.w_yaxis.set_ticklabels([])
    ax.w_zaxis.set_ticklabels([])
    ax.set_xlabel('Petal width')
    ax.set_ylabel('Sepal length')
    ax.set_zlabel('Petal length')
    plt.show()
In [37]:
model3 = KMeans(n_clusters=3)
plot_iris_cluster(model3)