Don Don - Average silhouette method

Silhouette coefficient

실루엣 계수는 아래와 같은 순서로 계산됩니다. 순서대로 살펴보겠습니다.

$i$ 번째 관측치가 속해있는 군집 내에 average dissimilarity $a_{i}$ 를 계산

$\begin{aligned} a (i) & = \frac{1}{| C_{I} | - 1} \sum_{j \in C_{I}, i \neq j} d (i, j) \\ w h e r e & C_{I} : I 관측치가 속해있는 군집 내 관측치의 수 \\ d (i, j) : i, j 사이의 거리(유클리디안 or 맨하탄 등등) \end{aligned}$

$a_{i}$ 는 compactness를 의미합니다(그림. 빨간선). 즉, 군집 내 밀도가 얼마나 높은지(군집 내 분산이 작은지)를 의미합니다. 단순히 잘 분리된 군집을 생각해보면 군집 내 밀도가 높을수록 잘 된 군집이라고 볼 수 있습니다. 따라서 $a_{i}$ 는 작을수록 좋습니다.

$i$ 번째 관측치가 속해있지 않은 군집에 대해서 $b_{i}$ 를 계산

$\begin{aligned} b (i) & = min_{J \neq I} \frac{1}{| C_{J} |} \sum_{j \in C_{J}} d (i, j) \\ w h e r e & C_{J} : j 관측치가 속해있는 군집 내 관측치의 수 \\ d (i, j) : i, j 사이의 거리(유클리디안 or 맨하탄 등등) \end{aligned}$

$b_{i}$ 는 seperation을 의미합니다(그림. 파란선). 즉, 군집 간 얼마나 멀리 떨어져있는지를 의미합니다. 단순히 잘 분리된 군집을 생각해보면 군집 간 거리가 멀수록 잘된 군집이라고 볼 수 있습니다. 따라서 $b_{i}$ 는 클수록 좋습니다.

$i$ 번째 관측치에 대해서 실루엣 계수 $S_{i}$ 계산

$\begin{aligned} S (i) & = \frac{b (i) - a (i)}{max (a (i), b (i))}, - 1 \leq S (i) \leq 1 \end{aligned}$

$S (i)$ 는 분모를 생략하면 $b (i) - a (i)$ 로 계산됩니다. $a_{i}$ 는 작을수록 좋고, $b_{i}$ 는 클수록 좋으므로, $b (i) - a (i)$ 는 클수록 좋습니다. 최대값은 $1$ 이 됩니다.

Average silhouette method

Average silhouette method에 대해 알아보겠습니다. 알고리즘의 대략적인 순서는 다음과 같습니다.

Practical Guide To Cluster Analysis in R

여기서 avg.sil은 위에서 구한 실루엣 계수의 평균을 의미합니다. 즉, 각 관측치별로 $S (i)$ 를 구하고, 평균을 취하면 avg.sil을 구할 수 있습니다.

Example

library(tidyverse)
library(factoextra)

df_iris <- scale(iris[, -5])

fviz_nbclust(df_iris, kmeans, method = "silhouette")

fviz_nbclust()에서는 avg.sil이 가장 높은 $k$ 를 최적의 $k$ 값으로 선정합니다.

km.res2 <- df_iris %>% 
  eclust("kmeans", k = 3, graph = F, nstart = 25) 
fviz_silhouette(km.res2)

  cluster size ave.sil.width
1       1   50          0.64
2       2   53          0.39
3       3   47          0.35

silhouette plot을 보면 빨간 점선으로 avg.sil이 표시되는 것을 볼 수 있습니다. 각 군집별 ave.sil.width를 평균내면 avg.sil과 같습니다. 오른쪽 끝에 실루엣 계수 값이 음수인 경우가 보입니다. 실루엣 계수가 음수라는 의미는 $a (i) > b (i)$ 라는 의미이므로, 관측치가 잘못된 군집에 할당되었다는 의미로 볼 수 있습니다.

sil <- km.res2$silinfo$widths[, 1:3]
neg_sil <- which(sil[, "sil_width"] < 0)
sil[neg_sil, ]

    cluster neighbor   sil_width
112       3        2 -0.01058434
128       3        2 -0.02489394

해당 관측치를 뽑아보면 112, 128번 index의 관측치인 것을 확인할 수 있습니다.

Warning

silhouette coefficient는 각 관측치별로 계산해야 하기 때문에 계산량이 많습니다. 데이터가 클 때는 주의가 필요합니다.

참고자료

https://en.wikipedia.org/wiki/Silhouette_(clustering)

https://www.datanovia.com/en/wp-content/uploads/dn-tutorials/book-preview/clustering_en_preview.pdf

Citation

BibTeX citation:

@online{don2022,
  author = {Don, Don and Don, Don},
  title = {Average Silhouette Method},
  date = {2022-10-08},
  url = {https://dondonkim.netlify.app/posts/2022-10-08-sillouette/silhouette.html},
  langid = {en}
}

For attribution, please cite this work as:

Don, Don, and Don Don. 2022. “Average Silhouette Method.” October 8, 2022. https://dondonkim.netlify.app/posts/2022-10-08-sillouette/silhouette.html.