Clustering - Performance (1)

지난 포스트

[Machine Learning/Unsupervised Learning] - Clustering - Hungrian Algorithm

---

지난 포스트에서는 clustering 의 결과 할당된 군집 번호를 라벨과의 정확도가 최대화가 되도록 재할당하는 Hungarian Algorithm 에 대하여 알아봤습니다. 이번 포스트에서는 데이터에 대한 라벨이 없고 순수히 clustering 결과의 성능을 측정하기 위한 다양한 방법들을 알아보도록 하겠습니다.

Silhouette score

Silhouette score 는 지난 포스트에서 cluster 의 개수를 판단하는 지표로서 소개해드렸는데요, clustering 의 성능을 평가하는데도 사용됩니다. Silhouette score 는 특정 데이터 샘플과 같은 군집 내의 다른 데이터 샘플들과의 평균 거리인 $a$와 가장 가까운 다른 군집 내의 다른 데이터 샘플들과의 평균 거리인 $b$로 다음과 같이 정의됩니다.

$s = \frac{b-a}{max(a,b)}$

전체 데이터의 silhouette score 는 각 데이터의 silhouette score 의 평균으로 정의되며 -1과 1사이의 값을 가지면서 1에 가까울수록 군집화가 잘 되었다고 판단합니다. 파이썬에서는 sklearn.metrics 모듈의 silhouette_score 함수로 쉽게 구할 수 있습니다. 주의할 점은 $b$를 정의해야 하기 때문에 군집의 개수가 최소 2개 이상이어야 한다는 점입니다.

from sklearn import metrics
from sklearn.metrics import pairwise_distances
from sklearn import datasets
X, y = datasets.load_iris(return_X_y=True)

from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.silhouette_score(X, labels, metric='euclidean')

 

Calinski-Harabasz index

Calinski-Harabasz index 는 Variance Ratio 라고도 알려져 있는 방법으로 $n_E$개의 데이터를 가지고 있는 데이터셋 $E$에 대해 between-clusters dispersion mean 과 within-cluster dispersion 의 비율로 다음과 같이 정의됩니다.

$s = \frac{tr(B_k)}{tr(W_k)}\times \frac{n_E -k}{k-1}$

여기서 $tr(B_k)$ 와 $tr(W_K)$는 Equation 1과 같이 정의되며 $C_q$는 군집 $q$의 데이터, $c_q$는 $q$의 중심, $c_E$는 전체 데이터셋 $E$의 중심입니다.

Equation 1

Equation 1의 $W_k$의 $(x-c_q)(x-c_q)^T$는 각 군집별 covariance matrix 로 이를 모든 군집에 대해 trace 를 취하는 것은 각 데이터가 속한 군집 중심으로부터 얼마나 떨어져있는지에 대한 분산으로 볼 수 있습니다. (within-cluster dispersion) 마찬가지로 $trace(B_k)$는 전체 데이터셋 중심에 대해 각 군집 중심이 얼마나 떨어져 있는지에 대한 분산으로 볼 수 있습니다. $s$에서 $\frac{n_E-k}{k-1}$ 을 곱하는 것은 표본으로부터 분산의 편향되지 않은 추정치를 얻기 위해서라고 볼 수 있습니다. (unbiased estimator)

이것도 마찬가지로 파이썬에서 sklearn.metrics 모듈의 calinski_harabasz_score 함수로 쉽게 구할 수 있습니다. Silhouette score 와 마찬가지로 값이 높을수록 더 군집이 잘 되었다고 판단하며 최대값이 정해져 있지 않습니다. (보통 몇백 단위가 출력됩니다.)

from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.calinski_harabasz_score(X, labels)

 

Davies-Bouldin index

Davies-Bouldin index 는 특정 군집 $c_i$와 그것과 가장 유사한 $c_j$ 사이의 평균 거리로 계산되어 Silhouette score 보다 계산량이 적고 간단합니다. $s_i$ 는 $c_i$ 의 평균 크기 (군집 내에 속한 데이터와 군집 중심간의 평균 거리), $d_{ij}$ 는 $c_i, c_j$ 의 중심 간의 거리라하고 $R_{ij}$를 Equation 2와 같이 정의합니다.

Equation 2

최종적인 Davies-Bouldin index 는 Equation 3고 같이 구합니다.

Equation 3

$R_{ij}$ 가 $i$에 대해 최대가 되는 $j$는 군집 중심간의 거리가 가장 짧은 ($d_{ij}$)가 될 것이고 모든 군집에 대한 평균이 바로 Davies-Bouldin index 가 됩니다. 따라서 다른 metric 과 반대로 $DB$ 가 작을수록 군집이 더 잘되었다고 판단하고 최소값은 0이 되게 됩니다. (각 데이터 자체가 군집인 경우)

파이썬에서는 sklearn.metrics 모듈의 davies_bouldin_score 함수에 구현되어 있습니다.

from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.davies_bouldin_score(X, labels)

 

홍머스 정리

• sklearn.metrics 에 정의되어 있는 라벨 없이 군집 성능을 평가하는 방식은 (silhouette, calinski-harabasz, davies-bouldin) 모두 거리 기반으로 군집이 명확히 분리되어 있는 경우에 높은 점수를 주고 DBSCAN 에서와 같은 비선형적 군집에 대해서는 점수가 낮은 경향을 보임.

참조

• scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation

---

다음 포스트

[Machine Learning/Unsupervised Learning] - Clustering - Performance (2), Total Sum of Squares