[R] 군집분석 군집의 개수 k 결정 방법 (Determining the number of clusters, k)

군집분석 중에서 k-means clustering, k-median clustering, k-medoid clustering, fuzzy k-means clustering, Gaussian mixture model clustering 등의 알고리즘은 군집의 개수 k를 미리 정해주어야 합니다.

그런데 군집분석이 정답 Y가 없는 상태에서 데이터 구조/군집을 탐색하고 마이닝하는 비지도학습(unsupervised learning)이다 보니 최적의 군집의 개수 k를 결정하고 군집 결과를 평가하는 것이 다분히 주관적인 편입니다. 해당 업과 데이터에 대해서 잘 아는 SME(Subject Matter Expert)의 지식과 경험, 그리고 활용 목적을 고려한 주관적인 의견을 반영하여 최종결정하는 것이 필요하고 중요합니다.

단, 이때 주관적인 경험과 지식에만 의존하는 것이 아니라, 군집의 개수 k를 선택하는데 있어 계량적인 데이터 분석 수치와 시각화의 도움을 받을 수 있다면 좀더 쉽고 또 보다 데이터 구조와 특성을 잘 반영한 의사결정을 할 수 있을 것입니다. (물론, 이마저도 정답이 없다보니 분석가의 주관적인 평가와 판단이 들어가게 되고, 명확한 판단을 내리기가 애매한 경우도 생길 수 있습니다.)

이번 포스팅에서는 군집의 개수 k 를 미리 정해주어야 하는 알고리즘에서 군집의 개수 k를 결정하고 선택하는데 도움을 받을 수 있는 3가지 방법(Determining the number of clusters)에 대해서 알아보겠습니다.

(1) 계층적 군집분석의 덴드로그램 시각화를 이용한 군집의 개수 결정
     (Hierarchical Clustering: Dendrogram)

(2) 팔꿈치 방법을 이용한 군집의 개수 결정 (The Elbow Method)

(3) 실루엣 방법을 이용한 군집의 개수 결정 (The Silhouette Method)

0. 샘플 데이터 USArrests {datasets} 불러오기 및 전처리

예제로 사용할 데이터는 R의 datasets 패키지에 내장되어 있는, 미국 주별 폭력적인 범죄 비율("Violent Crime Rates by US State)의 통계를 포함한 USArrests 데이터셋입니다. 이 데이터셋은 1973년 미국의 50개 주 별로 10만 명당 살인(Murder), 폭행(Assault), 강간(Rape) 체포 건수와 도시 인구 비율 (Percent Urban Population)의 네 개의 변수로 구성되어 있습니다.

## importing USArrests dataset from {datasets} data(USArrests) dim(USArrests) # [1] 50  4 head(USArrests) # Murder Assault UrbanPop Rape # Alabama      13.2     236       58 21.2 # Alaska       10.0     263       48 44.5 # Arizona       8.1     294       80 31.0 # Arkansas      8.8     190       50 19.5 # California    9.0     276       91 40.6 # Colorado      7.9     204       78 38.7

군집분석을 할 때 변수별 척도가 다를 경우 큰 척도의 변수 값에 군집의 결과가 휘둘릴 수 있으므로, 먼저 scale() 함수를 이용해서 표준화(standardization)를 해주었습니다.

## standardization (scaling) USArrests_scaled <- data.frame(scale(USArrests)) head(USArrests_scaled) # Murder   Assault   UrbanPop         Rape # Alabama    1.24256408 0.7828393 -0.5209066 -0.003416473 # Alaska     0.50786248 1.1068225 -1.2117642  2.484202941 # Arizona    0.07163341 1.4788032  0.9989801  1.042878388 # Arkansas   0.23234938 0.2308680 -1.0735927 -0.184916602 # California 0.27826823 1.2628144  1.7589234  2.067820292 # Colorado   0.02571456 0.3988593  0.8608085  1.864967207

다음으로, 표준화한 데이터에 대해서 50개의 각 주별 쌍의 유사도 행렬 (proximity matrix)로서 유클리드 거리 행렬 (Euclidean distance matrix) 을 dist(method = "euclidean") 함수를 사용해서 계산하였습니다. 자, 이제 군집분석을 위한 데이터셋 준비가 다 되었네요.

# calculating the euclidean diatance matrix dist_eucl <- dist(USArrests_scaled, method = "euclidean") dist_eucl # Alabama    Alaska   Arizona  Arkansas California  Colorado Connecticut # Alaska         2.7037541                                                                # Arizona        2.2935197 2.7006429                                                      # Arkansas       1.2898102 2.8260386 2.7177583                                            # California     3.2631104 3.0125415 1.3104842 3.7636409                                  # Colorado       2.6510673 2.3265187 1.3650307 2.8310512  1.2876185                       # Connecticut    3.2152975 4.7399125 3.2628575 2.6076395  4.0663898 3.3279920             # Delaware       2.0192927 3.6213633 1.9093696 1.8003239  3.0737852 2.5547456   1.7568475 # Florida        2.2981353 2.9967642 1.7493928 3.3721968  2.0250039 2.4458600   4.4700701 # Georgia        1.1314351 2.8194388 2.7871963 2.2117614  3.3780585 2.8649105   3.9738227 # Hawaii         3.3885300 4.5301340 3.2621208 2.9723097  3.6589083 2.8233524   1.3843291 # Idaho          2.9146623 4.0580555 3.5210071 1.7687255  4.4879436 3.4767685   1.6354214 # Illinois       1.8734993 3.2670626 1.0825512 2.4626424  1.9117469 1.7898322   2.7400560 -- 이하 생략함 --

(1) 계층적 군집분석의 덴드로그램 시각화를 이용한 군집의 개수 결정      (Hierarchical Clustering: Dendrogram)

계층적 군집분석(hierarchical clustering)에는 군집과 군집 간의 거리를 측정하는 다양한 연결법(linkage method)으로서, 단일연결법, 완전연결법, 평균연결법, 중심연결법, Ward연결법 등이 있습니다. 그중에서 Ward 연결법(Ward Linkage Method)에 의한 계층적 군집분석을 해보고, 이 결과를 덴드로그램(Dendrogram)으로 시각화를 해보겠습니다.

덴드로그램을 시각화 한 후에 왼쪽의 높이(Height) 축을 기준으로, 위에서 아래로 높이를 이동하면 군집의 개수가 1개, 2개, 4개, 6개, 8개, ..., 50개, 이런 식으로 변하게 됩니다.

이때 군집 간 높이의 차이가 큰 군집의 개수를 선택하면 군집 내 응집력은 높고, 군집간 이질성이 큰 적절한 군집을 구할 수 있습니다. 아래의 예의 경우 군집의 개수가 2개 또는 4개가 적당해 보이네요.

다만, 이 방법은 (a) 데이터 개수가 많을 경우 (가령, 수십만개, 수백만개) 군집화 시간이 오래걸리고, 덴드로그램으로 시각화가 거의 불가능할 수 있습니다. (b) 통계량을 산출하는게 아니고 덴드로그램 시각화 결과를 보고 분석가의 판단에 의지하다보니 다분히 주관적입니다.

set.seed(1004) # for reproducibility hc_ward <- hclust(dist_eucl, method="ward.D") # 덴드로그램 plot(hc_ward)

(2) 팔꿈치 방법을 이용한 군집의 개수 결정 (The Elbow Method)

다음으로는 비계층적 군집분석(nonhierarchical clustering, partitioning clustering) 중에서 k-means 군집분석(또는 k-median, k-medoids 등)의 k를 다르게 바꾸어가면서 군집화를 했을 때, 군집의 수 k별 "군집 내 군집과 개체 간 거리 제곱합의 총합 (tot.withinss: Total within-cluster sum of squares)" 의 그래프가 팔꿈치 모양으로 꺽이는 지점의 k 를 최적 군집의 개수를 선택하는 방법이 팔꿈치 방법(The Elbow Method) 입니다.

군집 Gi의 중심 측도가 평균인 경우,

Total Within-Cluster Sum of Squares

tot.withinss =

아래의 USArrests 데이터셋 예의 경우 군집의 개수가 4개일 때 Total within-cluster sum of squares 가 팔꿈치 모양으로 꺽이고, 군집 k가 5개 이상일 때부터는 tot.withinss의 변화가 매우 작으므로, 군집의 개수를 4개로 하는 것이 가장 좋아보이네요. (분석가의 주관적인 요소가 들어가긴 합니다. ^^;)

# find the optimal number of clusters using Total within-cluster sum of squares tot_withinss <- c() for (i in 1:20){   set.seed(1004) # for reproducibility   kmeans_cluster <- kmeans(USArrests_scaled, centers = i, iter.max = 1000)   tot_withinss[i] <- kmeans_cluster$tot.withinss } plot(c(1:20), tot_withinss, type="b",      main="Optimal number of clusters",      xlab="Number of clusters",      ylab="Total within-cluster sum of squares")

또는, 군집의 개수 k 별로 전체 분산(Total Variance) 중에서 그룹 간 분산(Between-Group Variance)의 비율로 계산(F-test 라고도 함)하는 "설명된 분산의 비율(the Percentage of Variance Explained)"을 계산하여 시각화한 후에, 팔꿈치 모양으로 꺽이는 지점의 군집의 개수 k를 선택하는 방법을 사용할 수 도 있습니다. (이 경우 위의 그룹 내 분산(Within-cluster Sum of Squares)을 사용했을 때와는 그래프 모양이 반대가 됩니다.)

## the percentage of variance explained as a function of the number of clusters ## Percentage of variance explained is the ratio of the between-group variance to the total variance, ## also known as an F-test. r2 <- c() for (i in 1:20){   set.seed(1004) # for reproducibility   kmeans_cluster <- kmeans(USArrests_scaled, centers = i, iter.max = 1000)   r2[i] <- kmeans_cluster$betweenss / kmeans_cluster$totss } plot(c(1:20), r2, type="b",      main="The Elbow Method - Percentage of Variance Explained",      xlab="Number of clusters",      ylab="Percentage of Variance Explained")

(3) 실루엣 방법을 이용한 군집의 개수 결정 (The Silhouette Method)

Peter J. Rousseeuw 는 "Silhouettes: a grapical aid to the interpretation and validation of cluster analysis" (1987) 라는 논문에서 분할적 군집분석(partitioning clustering)의 결과를 시각화하여 해석하고 평가할 수 있는 지표로서 실루엣(Silhouette)을 제안하였습니다.

실루엣을 계산하기 위해서 먼저 아래의 용어를 정의합니다. (아래의 논문 예시 그림 참조)

군집 A가 객체 i와 다른 객체들을 포함하고 있을 때,

a(i) = 군집 A 내의 객체 i 와 군집 A 내의 다른 객체들 간의 평균 비유사성 (즉, 거리 (distance))

        (average dissimilarity of i to all other objects of A)

d(i, C) = 군집 A 내의 객체 i와 다른 군집 C에 속한 모든 객체와의 평균 비유사성 (즉, 거리)

        (average dissimilarity of i to all objects of C)

b(i) = d(i, C) 의 최소값 =

* source: Reter J. Rousseeuw (1987)

실루엣은 아래 공식을 보면 알 수 있는 것처럼, 밀집성(tightness)와 분리성(separation)의 비교에 기반한 지표로서, 실루엣은 어떤 객체가 군집 안에 잘 놓여 있는지, 그리고 어떤 객체는 단지 군집들 사이의 어딘가에 놓여있는지를 보여줍니다.

전체 군집분석의 실루엣들을 하나의 그래프에 모아서 보여줌으로써, 데이터 구성과 형상의 개요(overview of the data configuration)와 군집들의 상대적인 질(the relative quality of the clusters)을 평가할 수 있습니다.

평균 실루엣 폭(the average silhouette width)은 군집화 결과에 대한 타당성(validity)을 평가하고, 또 적절한 군집 개수를 선택(to select an 'appropritate' number of clusters)하는데 활용할 수 있습니다.

실루엣은 -1 <= s(i) <= 1 사이의 값을 가집니다. 위 공식에 의하면 "실루엣 값이 1에 가까우면 다른 군집과의 거리보다 동일 군집 내 객체 간 거리가 가깝다는 뜻이므로 객체 i가 잘 군집화가 되었다는 의미"입니다. (이와 반대로 실루엣 값이 -1에 가까우면 객체 i의 군집화가 잘못되었다는 뜻입니다.)

만약 대부분의 객체가 높은 실루엣 값을 가진다면 군집의 구성이 적절하게 잘 되었다고 평가할 수 있습니다. 반면 많은 객체들이 낮거나 혹은 음(-)의 실루엣 값을 가진다면 군집 구성이 너무 많거나 또는 너무 적은 수의 군집을 가졌기 때문이라고 판단할 수 있습니다.

(아래 예에서는 군집4 에 정렬된 객체들의 뒷부분에 낮은 실루엣 값, 또는 음의 실루엣 값을 가진 객체들이 여러개 보이네요.)

## fviz_silhouette: Visualize Silhouette Information from Clustering install.packages("factoextra") library(factoextra) # K-means clustering set.seed(1004) km.res <- kmeans(USArrests_scaled, centers = 4) # Visualize silhouhette information library("cluster") sil <- silhouette(km.res$cluster, dist(USArrests_scaled)) fviz_silhouette(sil)

이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요. :-)

[Reference]

* Determining the number of clusters in a data set
   : https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

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

* Peter J. Rousseeuw, Journal of Computational and Applied Mathematics 20 (1987), "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis"