Measures of Cluster Validity
Unsupervised measure, Internal index
- goodness of a clustering structure w/o respect to external information
- Cluster Cohesion (compactness, tighness)
- Cluster Seperation (isolation)
Supervised measure, External index
- which cluster labels match externally supplied class labels
- Entropy
Relative measure
- Compare two different clustering results
- unsupervised/supervised measure 모두 적용 가능
Unsupervised Cluster Evaluation
Cohesion and Seperation
\begin{align*} \text{Cluster SSE} &= \sum_{\mathbf{x} \in C_i} dist(\mathbf{c}_i, \mathbf{x})^2 \\ &= \cfrac{1}{2 m_i}\sum_{\mathbf{x} \in C_i} \sum_{\mathbf{y} \in C_i} dist(\mathbf{x}, \mathbf{y})^2 \end{align*}
\begin{align*} \text{Total SSB} &= \sum_{i=1}^{K} m_i dist(\mathbf{c}_i, \mathbf{c})^2 \\ &= \cfrac{1}{2K} \sum_{i=1}^{K} \sum_{j=1}^{K} \cfrac{m}{K} dist(\mathbf{c}_i, \mathbf{c}_j)^2 \end{align*}
SSE를 최소화하는 것은 SSB를 최대화하는 것과 동일하다.
Silhouette Coefficient
cohesion과 seperation을 모두 고려하는 지표이다.
하지만 클러스터 전체가 아니라 각 data point에 대한 지표이다.
$i$번째 object에 대하여 $a_i,\ b_i$를 계산하고 실루엣 계수를 구한다.
$a_i$: 같은 클러스터 내의 모든 다른 object들과의 평균거리
$b_i$: 다른 클러스터 내의 모든 다른 object들과의 평균거리의 최솟값
\[ s_i = \cfrac{(b_i - a_i)}{\max(a_i, b_i)} \]
$s_i$의 범위는 $[-1, 1]$이고, $1$에 가까울 수록 (클러스터링의 결과가) 좋다는 뜻이다.
($a_i$가 $0$에 가까우면 $s_i = b_i / b_i = 1$에 가까워진다.)
border에 가까울 수록 $s_i$는 작아진다.
1번 클러스터(오렌지색)의 $s_i$의 최솟값은 다른 클러스터의 $s_i$의 최솟값보다 크다.
Proximity Matrix
correlation을 이용한 cluster validity 계산방법이다.
Proximity Matrix, Incidence Matrix 2개의 행렬을 이용한다. (matrix is symmetric)
높은 correlation은 same cluster를 의미한다.
그러나 density/contiguity based cluster에는 적합하지 않다.
Good cluster라면, 같은 클러스터 내의 correlation은 매우 높고 다른 클러스터끼리의 correlation은 낮을 것이다.
Determining the Correct Number of Clusters
분명히 10개의 클러스터가 존재하고 k-mean 알고리즘을 통해 클러스터 개수 K에 따른 SSE 그래프를 그려보자.
K값이 증가할 수록 SSE는 감소한다. 그러나 K=10 이후에는 SSE의 향상도가 나아지지않는다. 따라서 적절한 클러스터 개수는 K=10이 된다.
Clustering Tendency
이전까지 소개한 지표들은 클러스터링이 수행된 이후에 얼마나 잘 클러스터링 되었는지 알아보았다.
clustering tendency는 데이터 자체가 클러스터링이 될 수 있는지 판단하는 지표를 알아보자.
즉 클러스터링 알고리즘을 수행하기 이전에 사용할 수 있는 지표이다.
전체 data space에서 랜덤하게 $p$개의 데이터를 생성하고(not real data point, artificial points) \, 실제 data point에서 $p$개의 sample을 추출한다. 그리고 가장 가까운 이웃 거리(nearest neighbor distance)를 구한다.
$u_i$: artificial point에서 구한 nearest neighbor distance
$w_i$: sample point에서 구한 nearest neighbor distance
자주 사용되는 지표는 Hopkins statistic $H$이다.
\[ H = \cfrac{\sum_{i=1}^{p}w_i }{ \sum_{i=1}^{p} u_i + \sum_{i=1}^{p}w_i } \]
$H$가 $0$에 가까우면 highly cluster된 것이고, $H$가 $1$에 가까우면 clustering tendency가 거의 없다는 것이다.
즉 sample point(real data)끼리는 clustering되어 값이 작고, artificial point에서의 거리가 크면 $H$의 값은 작아지는 것이다. 반대로 $u_i \approx = 0$이면 원래 데이터가 거의 균등하게 (uniformly spread) 분포한다는 것이다.
Note: $H$의 threshlold는 정하기 나름이나, $0.5$가 threshold로 본다.
Supervised Measures for Cluster Validity
Classification-oriented measures
LA Document dataset에서 K-mean 알고리즘을 수행한 결과이다. $i$-clss에 속한 $j$-cluster에 대한 확률을 $p_{ij}$라 하면 $p_{ij} = \frac{m_{ij}}{m_j}$이다.
이때 entropy는 $e_j = \sum_{i=1}^{L} p_{ij} \log_2 p_{ij}$ ($L$은 class 개수이다)
total entropy는 $e = \sum_{i=1}^{K} \frac{m_i}{m} e_j$ 이다.
purity는 $purity_{j}=\max p_{ij}$이고 전체 purity는 $\sum_{i=1}^{K} \frac{m_i}{m}purity_{j}$
(6개의 클러스터 중에서) 3번째 클러스터가 낮은 entropy, 높은 purity를 가지므로 좋은 클러스터라고 할 수 있다.
Similarity-oriented measures
ideal cluster similarity matrix와 ideal class similarity matrix를 이용할 수 있다.
5개의 data point $p_1, \dots, p_5$에 대하여 클러스터($C$)와 class($L$)가 다음과 같다고 하자.
$C_1 = \{p_1, p_2, p_3 \},\ C_2 = \{p_4, p_5 \}, \quad L_1 = \{ p_1, p_2\},\ L_2 = \{p_3, p_4, p_5 \}$
binary similarity를 이용할 수 있다. (예: Jaccard coefficient)
Assessing the Significance of Measures
위에서 구한 다양한 measure를 어떻게 해석하는지 생각해보자.
예를 들어 어떤 evaluation 결과가 $10$일 때, good/fair/poor 인지 어떻게 판단할 수 있을까?
random chance에 기반하여 값을 비교할 수 있다.
'스터디 > 인공지능, 딥러닝, 머신러닝' 카테고리의 다른 글
| [CS224w] Theory of GNNs (2) - Neighbor Aggregation, GIN (Graph Isomorphism Network) (0) | 2023.06.17 |
|---|---|
| [CS224w] Theory of GNNs (1) - Local Neighborhood Structures, Computational Graph (0) | 2023.06.14 |
| [CS224w] Dataset Split (0) | 2023.05.29 |
| [Clustering] Density-Based Methods, DBSCAN (0) | 2023.05.25 |
| [CS224w] Training Graph Neural Networks (0) | 2023.05.24 |
