Clustering - Performance (2), Total Sum of Squares

지난 포스트

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

---

지난 포스트에서 라벨 없이 clustering 의 성능 평가를 위한 지표들인 silhouette score, calinski-harabasz index, davies-bouldin index 에 대해 알아봤습니다. Clustering 의 목적 자체가 전체 데이터셋 중 비슷한 데이터끼리는 같은 군집으로 비슷하지 않은 데이터끼리는 서로 다른 군집끼리는 구별되도록 묶는 알고르짐이기에 대표적인 지표들인 silhouette score, calinski-harabasz index 는 서로 모양은 다르지만 clustering 의 성능 평가를 위해서 1) 각 군집이 얼마나 잘 뭉쳐져 있는지 (compactness), 2) 각 군집이 서로 떨어져 있는지 (separation) 을 측정하게 됩니다. 

Compactness 를 측정하기 위해서 보통 각 군집에 속한 데이터와 군집의 중심간의 거리로 계산된 분산을 사용하는데요 이 분산이 낮으면 해당 군집이 잘 뭉쳐져 있다고 판단합니다. Separation 을 측정하기 위해서는 각 군집 중심 별 거리나 전체 데이터셋의 중심과 각 군집 중심간의 분산을 이용해 이 값이 크면 각 군집 별로 잘 구분되었다고 판단합니다.

Calinski-harabasz index 의 경우에 대입해보면 calinski-harabasz index 는 cluster 간의 분산과 (separation) cluster 내부의 분산의 (compactness) 비율로 clustering 성능을 판단하게 되는데요, 이를 일반적으로 확장하면 separation 을 나타내는 cluster 간의 분산과 compactness 를 나타내는 cluster 내 분산은 전체 데이터셋의 분산으로 정의할 수 있습니다.

Total sum of squares

Total sum of squares 는 전체 데이터셋의 분산 $\sum_{i=1}^n (x_i - \bar{x})^2$ 로 정의되고 이것은 compactness 를 나타내는 SSE(within-cluster sum, Sum of Square Error) 와 separation 을 나타내는 SSB(Between group of Sum of Sqaures) 의 합으로 나타낼 수 있습니다.

SSE 는 각 군집에 속한 데이터의 군집의 중심간의 거리의 합으로 $K$개의 cluster 에 대해서 $\sum_{k=1}^K \sum_{i=1}^{n_k} z_{ik} (x_i - \bar{x}_k)^2$ 로 정의되며 $n_k$는 $k$ 군집에 속한 데이터 개수이며 $\bar{x}_k$는 $k$ 군집의 평균입니다. $z_{ik}$는 indicator function 으로 $x_i$가 $k$ 군집에 속하면 1, 아니면 0을 출력합니다. SSB 는 전체 데이터셋의 중심과 군집 중심간의 거리의 합으로 $\sum_{k=1}^K n_k (\bar{x}_k-\bar{x})^2$ 로 정의됩니다. 따라서 TSS (Total Sum of Squares) 는 다음과 같이 정의됩니다.

$TSS = SSE + SSB$

$\sum_{i=1}^n (x_i - \bar{x})^2$ = $\sum_{k=1}^K \sum_{i=1}^{n_k} z_{ik} (x_i - \bar{x}_k)^2$ + $\sum_{k=1}^K n_k (\bar{x}_k-\bar{x})^2$

Proof

이것을 어떻게 증명할 수 있을까요? 먼저 위 식을 보면 전체 데이터셋의 분산이 군집 내 분산과 군집 간 분산의 합으로 이루어져 있는 것으로 보아 확률론의 law of total variance를 이용하여 전체 데이터셋의 분산을 다음과 같이 분해하고, 군집 $k$에 따른 데이터 $x$의 확률을 $p(x|k) = \sum_i \frac{z_{ik}}{n_k}\delta (x-x_i)$로 두고 군집 확률을 $p(k)=\frac{n_k}{n}$ 으로 두어 증명할 수 있습니다.

$Var[X] = E[Var[X|K]]+Var[E[X|K]]$

Law of total variance는 linear regression 에서의 종속변수 $Y$와 설명변수 $X$에 의한 $E[Y|X]=aX+b$ 경우에 대해서도 적용할 수 있는 것이 $Y$의 분산이 설명변수 $X$로부터 설명된 분산 ($Var[E[X|K]]$) 과 설명되지 못한 분산 (에러, $E[Var[X|K]]$) 으로 나누어진다는 것입니다.

---

다른 방법으로는 $\sum_i z_{ik}=n_k, \sum_k z_{ik}=1$ 을 이용하여 $\sum_{i=1}^n (x_i - \bar{x})^2$ 를 쭉 풀어쓰는 방법이 있습니다. 먼저 $\sum_{i=1}^n (x_i - \bar{x})^2=\sum_i \sum_k z_{ik} (x_i-\bar{x})^2$ 로 풀어쓰고 $(x_i-\bar{x})^2$ 부분을 $(x_i -\bar{x}_k+\bar{x}_k -\bar{x})^2$로 다음과 같이 풀이할 수 있습니다.

https://stats.stackexchange.com/questions/147007/a-proof-of-total-sum-of-squares-being-equal-to-within-cluster-sum-of-squares-and

 

홍머스 정리

• Clustering 에서 전체 데이터셋의 분산 (TSS) 은 군집 내 분산과 (SSE) 군집 간 분산 (SSB) 의 합으로 나타낼 수 있다. (엄밀히 말하면 분산이 아닌 중심과 데이터 간의 거리의 합)
• Clustering 성능 평가는 군집끼리 잘 뭉쳤는지 (compactness) 군집 간 잘 벌어져있는지 (separation) 의 비율이나 합으로 평가한다.

참조

• stats.stackexchange.com/questions/147007/a-proof-of-total-sum-of-squares-being-equal-to-within-cluster-sum-of-squares-and