Clustering - Performance (3), S_Dbw

이전 포스트

[Machine Learning/Unsupervised Learning] - Clustering - Performance (1)

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

---

Clustering 의 중요한 목적은 비슷한 데이터끼리는 뭉치게 하고 (compactness) 덜 비슷한 데이터끼리는 떨어지게끔 (separation) 묶어주는 것입니다. 이에따라 clustering 의 성능을 평가하는 여러 지표에서는 각 군집의 compactness, 군집 간 separation 을 동시에 고려해주게 되는데요. 이번 포스트에서 살펴볼 내용은 intra-cluster variance (compactness), inter-cluster density (separation) 을 고려한 clustering 성능 지표 S_Dbw 입니다.

S_Dbw

먼저 군집 $c_i$의 분산을 다음과 같이 정의합니다. ($n_i$는 $c_i$에 속한 데이터 개수이며 $\bar{x}_i$는 $c_i$의 중심입니다.) 이후 각 클러스터의 분산의 평균을 $stdev=\frac{1}{c}\sqrt{\sum_{i=1}^c \Vert\sigma(c_i)\Vert}$ 와 같이 정의하고 이를 전체 데이터의 분산 $\sigma (S)$로 정의합니다.

$\sigma(c_i) = \frac{1}{n_i} \sum_i^{n_i} (x_i - \bar{x}_i)^2$

Formulation

Separation 을 고려하기 위해 inter-cluster density 를 정의합니다. 이는 cluster 사이에 있는 영역의 density 와 cluster 자체의 density 를 비교하는 것으로서 다음과 같이 정의합니다.

$Dens bw(c) = \frac{1}{c(c-1)}\sum_{i=1}^c \sum_{j=1, j\neq i}^c \frac{density(u_{ij})}{max\{density(v_i), density(v_j)\}}$

$u_{ij}$는 $c_i, c_j$ 의 중심 $v_i, v_j$ 를 공간 상에서 이었을 때의 중심점이고 $density(u_{ij})$ 는 $u_{ij}$ 근방에 있는 이웃점의 개수로서 $density(u_{ij})=\sum_{l=1}^{n_{ij}} f(x_l, u_{ij})$ 이고 $n_{ij}$는 $c_i, c_j$에 속하는 모든 점을 말합니다. $u_{ij}$의 이웃점의 개수 $density(u_{ij})$는 $f$로부터 정해지고 $f(x, u)$는 $u$를 중심으로 위에서 정의한 $stdev$ 반지름을 가진 hypersphere 안에 $x$가 존재하면 1, 바깥에 존재하면 0을 나타내는 indicator 함수입니다. 즉, $u$를 중심으로 $stddev$ 거리 안에 얼마만큼의 데이터가 존재하는지 세는 함수입니다. (당연히 $x$의 모든 차원이 공정한 거리 계산을 위해 정규화가 선행되어야 합니다.)

Compactness 를 고려하기 위해 각 군집의 분산의 평균인 average scattering 을 계산합니다. 이는 전체 데이터셋의 분산 $\sigma(S)$에 대해 다음과 같이 계산합니다.

$Scat(c) = \frac{1}{c}\sum_{i=1}^c \Vert\sigma(v_i)\Vert / \Vert\sigma(S)\Vert$

최종적으로 S_Dbw 는 다음과 같이 정의됩니다.

S_Dbw = $Scat(c) + Dens bw(c)$

S_Dbw 의 첫 번째 항 $Scat(c)$ 는 $c$개의 군집이 흩어져 있는 정도를 나타내는 것으로 낮을 수록 군집들이 compact 하다는 것을 나타냅니다. 두 번째 항 $Dens_bw(c)$는 군집 사이에 평균적으로 얼마만큼의 데이터가 존재하는지에 대한 척도로 이 값이 낮을 수록 군집 사이의 밀도가 군집 자체의 밀도보다 낮다는 것이므로 군집끼리 잘 separation 되었다는 것을 나타냅니다. 종합하면 S_Dbw 는 값이 낮을수록 좋습니다.

Cases

다양한 데이터 상황에 대해 silhouette score (S), calinski-harabasz index (CH), S_Dbw 가 최적의 군집 수를 얼마나 잘 결정할 수 있는지 살펴보겠습니다. 먼저 Figure 1과 같이 군집은 명확하지만 noise 데이터가 껴 있는 경우입니다.

Figure 1

최적의 군집 개수는 5개인 것을 알 수 있습니다. Table 1의 결과를 보면 S_Dbw, S 는 최적의 군집 수를 잘 찾아냈지만 CH의 경우는 제대로 찾지 못한 것을 알 수 있습니다. 지난 포스트에서의 CH를 떠올려보면 $CH=\frac{SSB}{SSE}\frac{n-K}{K-1}$ 이고 ($K$는 군집 개수입니다.) $K$가 일정하다면 CH는 $SSB/SSE$에 의해 정해지게 됩니다. Noise 데이터가 삽입됨으로써 $SSE$가 급격하게 증가하게 되어 CH 값이 낮아지는 불안정한 상황이 발생하고 이것이 최적의 군집 수를 정하는데 영향을 미쳤다고 생각할 수 있습니다.

Table 1

두 번째 경우는 몇개의 군집끼리 매우 가까워 subcluster 를 이루는 Figure 2와 같은 상황입니다. Figure 2의 4개의 군집은 서로 너무 붙어있으니 subcluster 라고 할 수 있겠네요. 이 상황에 대해서 각 군집수에 따른 clustering 인덱스 값은 Table 2와 같습니다.

Figure 2

Table 2

Table 2를 보면 최적의 군집 수는 5이지만 S의 경우는 제대로 찾지 못한 것을 볼 수 있습니다. 이는 silhouette score (S)는 separation 을 고려하기 위해 해당 군집에서 가장 가까운 다른 군집과의 거리 $b$를 사용하는데, 이로 인해 군집 수가 3일때 subcluster 들이 하나의 cluster 로 고려되어 $b$가 최대가 되기 때문입니다.

마지막으로 살펴볼 경우는 군집의 분포가 같은 사이즈가 아닌 skewed 분포를 가지는 Figure 3의 경우입니다. 이런 경우에는 K-Means 같이 같은 크기만큼 군집하려고 하는 알고리즘은 거의 동작하지 않습니다. 군집 수에 따른 clustering 인덱스 값은 Table 3과 같습니다. 

Figure 3

Table 3

Table 3을 보면 CH를 제외하고는 다른 인덱스들은 최적의 군집 수 3을 찾은 것을 볼 수 있습니다. 왜 그럴까요? CH는 $\frac{SSB}{SSE}\frac{n-K}{K-1}=(TSS/SSE - 1)((n-K)/(K-1))$ 로 표현되고 $TSS$가 데이터셋에 대해 일정하다는 것을 감안했을 때 CH는 K-Means 와 같이 $SSE$에만 의존적이게 됩니다. 따라서 군집 수가 더 많을때 값이 더 올라가게 됩니다. 정리하면 각 데이터 상황마다 한계가 있는 다른 인덱스들과 다르게 항상 최적의 군집 수를 찾는 인덱스는 S_Dbw 임을 알 수 있습니다.

In python

다른 인덱스와 다르게 S_Dbw 는 scikit-learn 패키지에는 없고 "s-dbw" 라는 파이썬 패키지를 따로 설치해주어야 합니다. ("pip install s-dbw") 파라미터로는 다른 인덱스들과 마찬가지로 정규화된 입력 데이터 "X"와 군집 결과 "labels"가 필요합니다. 더불어 "labels"가 -1일 경우 noise 데이터로 취급되고 "alg_noise" 라는 매개변수를 통해 이 noise 데이터를 어떻게 취급할지 정할 수 있습니다.

from s_dbw import S_Dbw
score = S_Dbw(X, labels, centers_id=None, method='Tong', alg_noise='bind',
centr='mean', nearest_centr=True, metric='euclidean')

 

참조

• pypi.org/project/s-dbw/
• datamining.rutgers.edu/publication/internalmeasures.pdf
• S_Dbw paper