[R 군집분석 (Cluster Analysis)] (1) 응집형 계층적 군집화 : (1-4) 중심 연결법 (Centroid Linkage Method)

군집 간 거리를 측정하는 방법에 따라서 여러가지 알고리즘이 있는데요, 지난번 포스팅에서는 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘 중에서 그래프 기반(Graph-based)의 (1-1) 단일(최단) 연결법 (single linkage method, MIN), (1-2) 완전(최장) 연결법 (complete linkage method, MAX), (1-3) 평균 연결법 (average linkage method) 에 대해 소개하였습니다.

 

 

 

응집형 계층적 군집화 알고리즘 중에서 프로토타입 기반(Prototype-based) 모형은 미리 정해놓은 각 군집의 프로토타입에 터이터가 얼마나 가까운가로 군집의 형태를 결정합니다. 프로토타입 기반 유사성 측도로서 두가지 방법인 (1-4) 중심 연결법 (centroid linkage method)과 (1-5) Ward 연결법 (Ward linkage method) 중에서 이번 포스팅에서는 (1-4) 중심 연결법에 대해서 소개하겠습니다.

 

 

 

 

중심 연결법(Centroid Linkage method)은 두 군집 간의 거리를 측정할 때 각 군집의 중심(centroid) 간의 거리를 사용합니다.  아래 그림의 왼쪽의 이미지를 참고하시기 바랍니다.

 

     

[ 프로토타입 기반 유사성 측정 (Prototype-based maesure of proximity) ]

 

[표기 (denotation) 설명]

- d(i+j, k) : 군집 i와 j가 합쳐진 새로운 군집 i+j (cluster i U j)와 군집 k 간의 거리(distance)

- μi+j : 군집 i와 r군집 j의 데이터를 가중평균(weighted average)을 이용해 계산한 새로운 중심
- ni : 군집 i의 데이터 개수,  nj : 군집 j의 데이터 개수

        

- 빨간점 : 각 군집의 중심(centroid)

 

 

 

이제 2차원 공간(2-dimentional space)에 5개의 점을 가지고 간단한 예를 들어서 설명을 해보겠습니다.

 

지난번 포스팅의 단일(최단) 연결법, 완전(최장) 연결법, 평균 연결법과 예시 데이터와 동일하며, 거리 계산 방법도 아래의 (1)번, (2)번까지는 똑같고, (3)번부터는 조금 다릅니다. 

 

 

 

1) 데이터셋 준비, 탐색적 분석

 

응집형 계층적 군집화이므로 처음에 아래의 5개의 점, 5개의 군집에서부터 시작합니다.

 

 

 

R script도 같이 제시하면서 설명하겠습니다.  먼저, 데이터 입력 및 plotting (↑ 위의 산점도 그래프) 입니다.

 

> ##-------------------------------------------- > ## (1) Agglomerative Hierarchical Clustering > ## (b) Prototype-based > ## (1-4) Centroid Linkage > ##-------------------------------------------- > > x <- c(1, 2, 2, 4, 5) > y <- c(1, 1, 4, 3, 4) > > xy <- data.frame(cbind(x, y)) > > xy x y 1 1 1 2 2 1 3 2 4 4 4 3 5 5 4 > > # scatter plot of xy > plot(xy, pch = 19, xlab = c("x coordinate"), ylab = c("y coordinate"), + xlim = c(0, 6), ylim = c(0, 6), + main = "scatter plot of xy") > > # adding student label > text(xy[,1], xy[,2], labels = abbreviate(rownames(xy)), + cex = 0.8, pos = 1, col = "blue") # pos=1 : at the bottom > > > # adding dotted line > abline(v=c(3), col = "gray", lty = 2) # vertical line > abline(h=c(3), col = "gray", lty = 2) # horizontal line

 

 

 

 

2) 유사성 측도로서 거리 행렬(Distance matrix) D 계산하기

 

거리 측도는 분석 목적, 데이터 특성에 맞게 선택해야 하는데요, 이번 예제에서는 '유클리드 제곱거리(squares of Euclidean distance)'를 사용하겠습니다. 

 

[distance matrix - no.1]

 

 

 

유클리드 제곱거리를 구하는 R script 입니다. dist(xy, method="euclidean") 에다가 뒤에 "^2"를 붙여서 제곱을 했습니다.

 

> # proximity matrix : squares of euclidean distance matrix for 6 points > dist(xy, method = "euclidean")^2 1 2 3 4 2 1 3 10 9 4 13 8 5 5 25 18 9 2

 

 

• P1과 P2의 거리가 '1'로서 가장 가까우므로 (즉, 유사하므로) 
  → (P1, P2)를 새로운 군집으로 묶어줍니다(merge). 이제 군집이 처음 5개에서 4개로 줄었습니다.

 

2차원 데이터에 대해서는 아래처럼 부분집합그림(Nested cluster diagram)을 그려볼 수 있습니다.

 

 

 

(여기까지는 단일 연결법, 완전 연결법, 평균 연결법과 동일합니다)

 

 

 

3) 군집(P1, P2)의 중심 구하기

 

새로 묶인 군집(P1, P2)의 중심(centroid)을 가중평균을 이용해서 구해보면

μ(P1+P2) = {1*(1, 1) + 1*(2, 1)}/(1+1) = {(1, 1) + (2, 1)}/2 = (1.5, 1) 이 됩니다.

 

여기서 부터 앞서 소개했던 그래프 기반(Graph-based)의 군집 간 거리측정법인 (1-1) 단일 연결법, (1-2) 완전 연결법, (1-3) 평균 연결법과 확연히 차이가 나기 시작하는 부분입니다.  그래프 기반 방법에서는 중심(Centroid)라는 개념이 없었구요, 프로토타입 기반 방법 중에서 중심 연결법에서는 프로토타입으로 군집의 중심(Centroid)을 가지고 군집 간 거리를 측정합니다.

 

[centroid coordinate of clusters - no.1]

 

 

 

아래의 부분집합그림에 보면 군집 (P1, P2) 의 중심(centroid) 위치에 노란색 별이 추가되었습니다.

 

 

 

 

4) 군집(P1, P2)와 P3, P4, P5 간 중심 연결법(centroid linkage method)으로 계산한 수정된 거리행렬(distance matrix) 구하기

 

중심 연결법을 이용한 군집 간 거리는 두 군집 중심의 유클리드 제곱거리를 사용합니다.

 

 

 

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 중심 연결법에 의한 거리는 위의 [centroid coordinate of clusters - no.1] 의 중심 좌표를 가지고 유클리드 제곱거리로 구하면

d{(P1, P2), P5} = (1.5-5)^2 + (1-4)^2 = 21.25  가 됩니다.

 

[distance matrix - no.2]

 

 

• P4과 P5의 거리가 '2'로서 가장 가까우므로  
  → (P4, P5)를 새로운 군집으로 묶어줍니다(merge). 이제 군집이 처음 5개에서 3개로 줄었습니다.

 

 

5) 새로운 군집 (P4, P5)의 중심(centroid) 구하기

 

[centroid coordinate of clusters - no.2]

 

 

 

수정된 2차원 부분집합그림은 아래와 같습니다. (P1, P2) 군집에 이어 두번째로 (P4, P5) 군집이 묶였습니다.  노란색 별은 군집의 중심(centroid)를 의미합니다.

 

 

 

 

 

6) 군집 (P1, P2), P3, (P4, P5) 간의 거리를 중심 연결법(centroid linkage method)으로 계산하여 수정한 거리행렬(distance matrix) 구하기

 

유클리드 제곱거리를 사용해서 군집의 중심(centroid) 간의 거리를 계산하였습니다.

 

[distance matrix - no.3]

 

 

• 개체 P3와 군집 (P4, P5)의 거리가 '6.5'로서 가장 가까우므로 
  → P3과 (P4, P5)를 새로운 군집으로 묶어줍니다(merge). 반복(repeat)을 거듭할 수록 군집이 줄어서 이제 2개가 되었습니다. 

 

 

7) 새로 합쳐진 군집 {P3, (P4, P5)} 의 중심(centroid)를 가중 평균을 사용해서 구하기

 

 

[centroid coordinate of clusters - no.3]

 

 

 

여기까지 진행한 군집화 결과를 반영해 수정한 부분집합그림은 아래와 같습니다.

 

 

 

 

 

8) 군집 (P1, P2)와 {P3, (P4, P5)} 의 중심 간 거리를 중심 연결법(centroid link)으로 계산하여 수정한 거리 행렬(distance matrix) 구하기

 

 

 

• 마지막으로 두개 남은 군집 (P1, P2)와 {P3, (P4, P5)}를 묶어줍니다(merge).  
  → 드디어 반복(repeat)을 거듭한 끝에 군집이 1개로 줄어들었습니다. 
      → 종료 (End) 

 

마지막 군집이 병합된 이후의 수정된 부분집합그림은 아래와 같습니다.

 

 

 

 

이상의 '중심 연결법(centroid linkage method)'에 의한 응집형 계층적 군집화를 위한 R script는 아래와 같습니다.

 

> # Agglomerative Hierarchical Clustering : Centroid Linkage method > hc_cent <- hclust(dist(xy)^2, method="centroid") > hc_cent Call: hclust(d = dist(xy)^2, method = "centroid") Cluster method : centroid Distance : euclidean Number of objects: 5

 

 

 

 

 

9) 덴드로그램(Dendrogram)으로 응집형 계층적 군집화(by 중심 연결법) 결과 확인해보기

 

아래 덴드로그램의 y축이 바로 군집 간 거리 (평균 연결법으로 구한) 를 나타냅니다.

plot(x, hang = -1) 옵션을 설정하면 아래 그램의 오른쪽 덴드로그램처럼 군집 묶어주는 선이 y=0 부터 시작합니다.

 

> # dendrogram > my_par = par(no.readonly = TRUE) > par(oma = c(0, 0, 1, 0)) > par(mfrow = c(1, 2)) > plot(hc_cent) > plot(hc_cent, hang = -1) # hang = -1 : line from the bottom

 

 

 

rev() 함수를 사용하면 군집 모델에 대한 정보를 알 수 있습니다.

 - $method : 연결 방법(linkage method)

 - $height : 군집 간 거리(distance between clusters)

 - $merge : 군집 간 병합 순서 (merge sequence)

 

> # custering information > rev(hc_cent) $dist.method [1] "euclidean" $call hclust(d = dist(xy)^2, method = "centroid") $method [1] "centroid" $labels NULL $order [1] 1 2 3 4 5 $height [1] 1.00000 2.00000 6.50000 11.80556 $merge [,1] [,2] [1,] -1 -2 [2,] -4 -5 [3,] -3 2 [4,] 1 3

 

 

 

이전 포스팅의 단일(최단) 연결법, 완전(최장) 연결법, 평균 연결법과 비교를 했을 때 평균 연결법과 유사한 정도의 군집 간 거리(R 결과에서는 Height로 표기)로 계산되었네요.

 

> # comparison of height among linkage methods > hc_sl <- hclust(dist(xy)^2, method="single") > hc_cl <- hclust(dist(xy)^2, method="complete") > hc_avg <- hclust(dist(xy)^2, method="average") > hc_cent <- hclust(dist(xy)^2, method="centroid") > > # dendrogram > my_par = par(no.readonly = TRUE) > par(oma = c(0, 0, 1, 0)) > par(mfrow = c(1, 4)) > plot(hc_sl, main = "Single Linkage") > plot(hc_cl, main = "Complete Linkage") > plot(hc_avg, main = "Average Linkage") > plot(hc_cent, main = "Centroid Linkage")

 

 

이상으로 (1) 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘의 프로토타입 기반 (1-4) 중심 연결법(Centroid linkage method) 에 대해서 알아보았습니다.

 

[Reference]

(1) "Introduction to Data Mining", Pang-Ning Tan(Michigan State University), Michael Steinbach(University of Minnesota), Vipin Kumar(University of Minnesota), Addison-Wesley Companion Book

(2) "Clustering Algorithm", Ana Fred, INSTITUTO SUPERIOR TECNICO, Universidade Techica de Lisboa, 2009

(3) "R, SAS, MS-SQL을 활용한 데이터마이닝", 이정진 지음, 자유아카데미, 2011

(4) Wikipedia
    - cluster analysis : https://en.wikipedia.org/wiki/Cluster_analysis

    - hierarchical clustering : https://en.wikipedia.org/wiki/Hierarchical_clustering 

 

 

다음번 포스팅에서는 (1) 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘의 프로토타입 기반(Prototype-based) 군집 간 거리 측정법으로 (1-5) Ward 연결법(Ward linkage method)에 대해서 알아보도록 하겠습니다.

 

이번 포스팅이 도움이 되었다면 아래의 '공감 ~♡'를 꾸욱 눌러주세요.