MathClassification

Clustering

study

클러스터링

주어진 데이터 집합을 유사한 데이터들의 그룹으로 나누는 것을 클러스터링(clustering)이라고 하고, 이렇게 나누어진 유사한 데이터들의 그룹을 클러스터(cluster)라고 한다.

클러스터링은 분류 문제와 달리 특정한 독립변수와 종속변수의 구분도 없고 학습을 위한 목푯값(target value)도 필요로 하지 않는 비지도학습(unsupervised learning)의 일종이다.

클러스터링 방법

대부분의 클러스터링 방법들도 예측모형처럼 특정한 목표함수의 값을 최소화 혹은 최대화하긴 하지만, 예측모형과 달리 명확하게 주어진 목표함수가 없기 때문에, 목표함수의 정의 및 최적화 방법이 각기 다른 다양한 클러스터링 방법이 존재한다. 아래 소개하는 방법들이 많이 사용되는 클러스터링 방법이다.

  • K-means
  • DBSCAN
  • Spectral Clustering
  • Affinity Propagation
  • 계층적 클러스터링(Hierarchial Clustering)

클러스터링 방법마다 사용법과 모수 등이 다르다. 예를 들어 K-means, Spectral Clustering 등은 클러스터의 개수를 미리 지정해주어야 하지만, DBSCAN이나 Affinity, Propagation 등은 클러스터의 개수를 지정할 필요가 없다. 다만 다른 종류의 모수값을 지정해줘야 하는데 이 값에 따라 클러스터의 개수가 달라질 수 있다.

다음은 몇 가지 예제 데이터에 이 클러스터링 방법들을 적용한 결과다. 같은색상의 데이터는 같은 클러스터로 분류된 것이다. 각 방법마다 특성이 다르기 때문에 클러스터링 목적과 데이터의 유형에 적합한 방법을 선택해 사용해야 한다. 또한 지정된 모수값에 따라 성능이 달라질 수 있다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from sklearn.datasets import *
from sklearn.cluster import *
from sklearn.preprocessing import StandardScaler
from sklearn.utils.testing import ignore_warnings

np.random.seed(0)
n_samples = 1500
blobs = make_blobs(n_samples=n_samples, random_state=8)
X, y = make_blobs(n_samples=n_samples, random_state=170)
anisotropic = (np.dot(X, [[0.6, -0.6], [-0.4, 0.8]]), y)
varied = make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=170)
noisy_circles = make_circles(n_samples=n_samples, factor=.5, noise=.05)
noisy_moons = make_moons(n_samples=n_samples, noise=.05)
no_structure = np.random.rand(n_samples, 2), None
datasets = {
    "같은 크기의 원형": blobs, 
    "같은 크기의 타원형": anisotropic, 
    "다른 크기의 원형": varied, 
    "초승달": noisy_moons, 
    "동심원": noisy_circles, 
    "비구조화": no_structure
}

plt.figure(figsize=(11, 11))
plot_num = 1
for i, (data_name, (X, y)) in enumerate(datasets.items()):
    X = StandardScaler().fit_transform(X)

    two_means = MiniBatchKMeans(n_clusters=3)
    dbscan = DBSCAN(eps=0.15)
    spectral = SpectralClustering(n_clusters=3, affinity="nearest_neighbors")
    ward = AgglomerativeClustering(n_clusters=3)
    affinity_propagation = AffinityPropagation(damping=0.9, preference=-200)
    clustering_algorithms = (
        ('K-Means', two_means),
        ('DBSCAN', dbscan),
        ('Spectral Clustering', spectral),
        ('Hierarchical Clustering', ward),
        ('Affinity Propagation', affinity_propagation),
    )

    for j, (name, algorithm) in enumerate(clustering_algorithms):
        with ignore_warnings(category=UserWarning):
            algorithm.fit(X)
        if hasattr(algorithm, 'labels_'):
            y_pred = algorithm.labels_.astype(np.int)
        else:
            y_pred = algorithm.predict(X)
        plt.subplot(len(datasets), len(clustering_algorithms), plot_num)
        if i == 0:
            plt.title(name)
        if j == 0:
            plt.ylabel(data_name)
        colors = plt.cm.tab10(np.arange(20, dtype=int))
        plt.scatter(X[:, 0], X[:, 1], s=5, color=colors[y_pred])
        plt.xlim(-2.5, 2.5)
        plt.ylim(-2.5, 2.5)
        plt.xticks(())
        plt.yticks(())
        plot_num += 1

plt.tight_layout()
plt.show()

클러스터링 성능기준

클러스터링의 경우 분류문제에 비해 성능기준을 만들기가 어렵다. 원래 데이터가 어떻게 클러스터링되어있는지를 보여주는 정답(groundtruth)이 있는 경우에도 쉽지 않다. 따라서 아래 제시된 예시를 비롯해 다양한 성능기준들이 사용되고 있다.

  • Adjusted Rand Index
  • Adjusted Mutual Information
  • Silhouette Coefficient

1) Adjusted Rand Index

(Adjusted) Rand Index를 구하려면, 데이터가 원래 어떻게 클러스터링되어있는지에 대한 정답이 있어야 한다. $N$ 개의 데이터 집합에서 $i, j$ 두 개의 데이터를 선택했을 때 그 두 데이터가 같은 클러스터에 속하면 1, 다른 데이터에 속하면 0이라고 하자. 이 값들을 $N\times N$ 행렬 $T$ 로 나타내자.

예를 들어 $\{0,1,2,3,4\}$라는 5개의 데이터 집합에서 $\{0,1,2\}$가 한 클러스터, $\{3,4\}$가 한 클러스터라면 정답행렬 $T$ 는 아래와 같은 행렬이 된다.

1
2
3
4
5
6
7
groundtruth = np.array([
    [1, 1, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 1],
])

이제 해당 데이터 집합에 대해 클러스터링을 진행한 결과를 행렬 $C$ 라고 하자. 클러스터링이 정확하게 이루어졌다면 $C$ 는 정답행렬 $T$ 와 같은 값을 가져야 한다. 만약 클러스터링 결과 $\{0,1\}$ 과 $\{2, 3, 4\}$ 로 분류되었다면 $C$ 는 아래와 같은 행렬이 된다.

1
2
3
4
5
6
7
clusters = np.array([
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 1, 1],
])

행렬 $T$ 와 $C$ 를 비교하여, 값이 같은 원소의 자리에는 1, 다른 원소의 자리에는 0으로 표시한 행렬을 incidence matrix 라고 하며 $R$ 로 표시한다. 즉, 정답인 경우 1, 틀린 경우 0이 된다.

위 예제에서 incidence matrix를 구하면 다음과 같다.

1
2
incidence = 1 * (groundtruth == clusters)
incidence

Rand Index 는 이 incidence matrix에서 전체 원소 개수 중에 1의 개수 즉 정답인 쌍의 개수의 비율로, 예측문제의 정확도(accuracy)에 해당한다.

1
2
rand_index = np.sum(incidence) / np.prod(incidence.shape)
rand_index

Rand Index는 0에서 1사이 값을 가지고, 1일 때 가장 성능이 좋은 것이다. 이 rand index 의 문제점은, 무작위로 클러스터링을 한 경우에도 어느 정도 좋은 값이 나올 가능성이 높다는 점이다. 이를 해결하기 위해 무작위 클러스터링에서 생기는 rand index의 기댓값을 원래의 값에서 빼서 기댓값과 분산을 재조정한 것이 Adjusted Rand index이다. Adjusted rand index는 무작위클러스터링의 경우 0이 나올 확률이 높고, 경우에 따라 음수가 나올 수도 있다.

adjusted Rand index를 계산하려면 우선 contingency table을 만들어야 한다. contingencey table은 정답과 클러스터링 결과가 같은 데이터의 개수를 나타낸 것이다.

정답이 $r$ 개의 클러스터를 갖고 클러스터링 결과는 $s$ 개의 클러스터를 가진다고 가정할 때,

contingency table은 아래와 같이 그려진다.

  • $n_{ij}$ : 정답에서는 클러스터 $T_i$ 에 속하고 클러스터링 결과에서는 $C_j$ 에 속하는 데이터의 수
  • $a_i = \sum^s_{j=1} n_{ij}$
  • $b_j = \sum^r_{i=1}n_{ij}$

여기서 adjusted Rand index값은 아래와 같이 구할 수 있다.

위에서 예로 들었던 타원형 데이터 예제에 대해 여러가지 클러스터링 방법을 적용하였을때 adjusted Rand index 값을 계산해보면 DBSCAN과 Spectral Clustering의 값이 높게 나오는 것을 확인할 수 있다. scikit-learn 패키지의 metrics.cluster 서브패키지는 adjusted_rand_score 명령을 제공한다.

1
2
3
4
5
6
7
8
9
10
11
12
from sklearn.metrics.cluster import adjusted_rand_score

X, y_true = anisotropic
X = StandardScaler().fit_transform(X)
for name, algorithm in clustering_algorithms:
    with ignore_warnings(category=UserWarning):
        algorithm.fit(X)
    if hasattr(algorithm, 'labels_'):
        y_pred = algorithm.labels_.astype(np.int)
    else:
        y_pred = algorithm.predict(X)
    print("{:25s}: ARI={:5.3f}".format(name, adjusted_rand_score(y_true, y_pred)))

2) Adjusted Mutual Information

mutual information은 두 확률변수간의 상호 의존성을 측정한 값이다.

클러스터링 결과가 이산확률변수라고 가정했을 때, 위 경우에서처럼 정답이 r개의 값을 갖는 이산확률변수이고 클러스터링 결과는 s개의 값을 갖는 이산확률변수라고 하자.

전체 데이터 수를 $N$ 이라고 하면 이산확률변수 $T$ 와 $C$ 의 분포는 아래와 같이 추정할 수 있다.

​ - $|T_i|$ : 클러스터 $T_i$ 에 속하는 데이터 수

​ - $|C_j|$ : 클러스터 $C_j$ 에 속하는 데이터 수

이 때 $T$ 와 $C$ 의 결합확률분포는 다음처럼 추정된다.

​ - $|T_i \cap C_j|$: 클러스터 $T_i$ 와 $C_j$ 모두에 속하는 데이터의 개수

확률변수 $T, C$ 의 mutual information은 아래와 같이 정의된다.

만약 두 확률변수가 서로 독립이면 mutual information의 값은 0이며, 이 값이 mutual information이 가질 수 있는 최소값이다. 두 확률변수간의 의존성이 강할수록 값이 커진다. 그런데 클러스터의 개수가 많아질수록 값이 증가하므로 올바른 비교가 어렵다. 따라서 각 경우에 따른 mutual information 기대값을 빼서 재조정한 것이 adjusted mutual information 이다.

다음은 위에서 예로 들었던 타원형 데이터 예제에 대해 여러가지 클러스터링 방법을 적용했을 때 adjusted mutual information 값을 계산한 결과이다. scikit-learn 패키지의 metrics.cluster 서브패키지는 adjusted_mutual_info_score 명령을 제공한다.

1
2
3
4
5
6
7
8
9
10
11
12
from sklearn.metrics.cluster import adjusted_mutual_info_score

X, y_true = anisotropic
X = StandardScaler().fit_transform(X)
for name, algorithm in clustering_algorithms:
    with ignore_warnings(category=UserWarning):
        algorithm.fit(X)
    if hasattr(algorithm, 'labels_'):
        y_pred = algorithm.labels_.astype(np.int)
    else:
        y_pred = algorithm.predict(X)
    print("{:25s}: ARI={:5.3f}".format(name, adjusted_mutual_info_score(y_true, y_pred)))

3) 실루엣 계수

지금까지는 데이터의 클러스터링에 대한 정답을 알고 있는 경우였다. 하지만 이런 정답정보가 없다면 어떻게 클러스터링 결과를 판단할 수 있을까? 실루엣 계수(Silhouette coefficient) 는 이러한 경우에 클러스터링 성능을 판단하기 위한 기준의 하나이다.

우선 모든 데이터쌍 $(i, j)$ 에 대해 거리(distance) 혹은 비유사도(dissimilarity) 를 구한다. 이 결과를 이용해 모든 데이터 $i$ 에 대해 다음 값을 구한다.

  • $a_i$ : $i $ 와 같은 클러스터에 속한 원소들의 평균 거리
  • $b_i$ : $i$ 와 다른 클러스터 중 가장 가까운 클러스터까지의 평균 거리

이 때 실루엣 계수는 다음과 같이 정의된다.

만약 데이터 $i$ 에 대해 같은 클러스터의 데이터가 다른 클러스터의 데이터보다 가깝다면 실루엣 계수는 양수가 된다. 하지만 만약 다른 클러스터의 데이터가 더 가깝다면 실루엣 계수가 음수가 되는데, 이 때는 클러스터링이 잘못된 경우로 보면 된다. 실루엣 계수가 클수록 좋은 클러스터링이라고 볼 수 있다.

실루엣 계수는 클러스터의 개수를 사용자가 정해주어야 하는 경우 큰 도움이 된다. 앞서 예로 들었던 3개의 원형데이터에 대해 KMean 방법으로 클러스터 개수를 바꿔가면서 클러스터링 결과를 살펴보자.

Scikit-learn 패키지의 metrics 서브패키지에 제공되는 silhouette_samples명령을 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from sklearn.metrics import silhouette_samples

X = StandardScaler().fit_transform(blobs[0])

colors = plt.cm.tab10(np.arange(20, dtype=int))

plt.figure(figsize=(6, 8))
for i in range(4):
    model = KMeans(n_clusters=i + 2, random_state=0)
    cluster_labels = model.fit_predict(X)
    sample_silhouette_values = silhouette_samples(X, cluster_labels)
    silhouette_avg = sample_silhouette_values.mean()
    
    plt.subplot(4, 2, 2 * i + 1)
    y_lower = 10
    for j in range(i + 2):
        jth_cluster_silhouette_values = sample_silhouette_values[cluster_labels == j]
        jth_cluster_silhouette_values.sort()
        size_cluster_j = jth_cluster_silhouette_values.shape[0]
        y_upper = y_lower + size_cluster_j
        plt.fill_betweenx(np.arange(y_lower, y_upper),
                          0, jth_cluster_silhouette_values,
                          facecolor=colors[j], edgecolor=colors[j])
        plt.text(-0.05, y_lower + 0.5 * size_cluster_j, str(j + 1))
        plt.axvline(x=silhouette_avg, color="red", linestyle="--")
        plt.xticks([-0.2, 0, 0.2, 0.4, 0.6, 0.8, 1])
        plt.yticks([])
        plt.title("실루엣 계수 평균: {:5.2f}".format(silhouette_avg))
        y_lower = y_upper + 10
        
        
    plt.subplot(4, 2, 2 * i + 2)
    plt.scatter(X[:, 0], X[:, 1], s=5, color=colors[cluster_labels])
    plt.xlim(-2.5, 2.5)
    plt.ylim(-2.5, 2.5)
    plt.xticks(())
    plt.yticks(())
    plt.title("클러스터 수: {}".format(i + 2))

plt.tight_layout()
plt.show()

Share