[R 군집분석 (Cluster Analysis)] (1) 응집형 계층적 군집화 : (1-3) 평균 연결법(Average linkage method)

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

 

이번 포스팅에서는 응집형 계층적 군집화 알고리즘 중에서 그래프 기반(Graph-based) 방법의 세번째로 (1-3) 평균 연결법 (average linkage method)에 대해서 알아보겠습니다.

 

 

 

 

 

 

평균 연결법은 서로 다른 군집 간의 모든 짝을(pair-wise) 이룬 점들의 평균 거리로 유사성을 측정합니다.

아래의 그래프 기반 군집 간 유사성 측정(graph-based mesaures of cluster proximity) 방법으로서 (1-1) 단일(최단) 연결법, (1-2) 완전(최장) 연결법과 (1-3) 평균 연결법의 수식, 그리고 도식을 보면 서로의 차이점을 이해할 수 있을 것입니다.

 

 

 

 

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

 

지난번 포스팅의 단일(최단) 연결법, 완전(최장) 연결법 예시 데이터와 동일하며, 거리 계산 방법도 아래의 (1)번, (2)번까지는 똑같고, (3)번부터는 조금 다릅니다. 위의 수식 처럼 평균 개념이 들어가 있어서 단일 연결법, 완전 연결법 대비 조금 복잡한 감이 있습니다.

 

 

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

 

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

 

 

 

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

 

> ##-------------------------------------------- > ## (1) Agglomerative Hierarchical Clustering > ## (1-3) Average 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"를 붙여서 제곱을 했습니다.(이해, 설명 편의를 위해... 유클리드 거리로 하면 매번 squared root 씌우는 것이 귀찮아서요.) 

 

> # 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)와 개체 P3, P4, P5 간의 거리를 평균 연결법(average linkage method)으로 수정한 거리행렬(distance matrix) 구하기

 

평균 연결법은 다른 군집 간의 모든 짝을 이룬 점들의 평균 거리로 유사성을 측정하는 방법이므로 아래의 계산 절차를 따릅니다. 

 

 

 

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 평균 연결법에 의한 거리는 

d{(P1, P2), P5} = {d(P1, P5) + d(P2, P5)}/(2*1) = (25 + 18)/2 = 43/2 = 21.5

가 됩니다.

 

 

단일(최단) 연결법으로 하면 MIN값인 18 이 되며, 완전(최장) 연결법으로 하면 MAX값인 25가 되는 반면에, 평균 연결법으로 하면 단일 연결법과 완전연결법의 평균 지점인 21.5가 되었습니다.  (MIN 값이든 MAX값이든 Average 값이든 간에 이상값, 특이값에 민감하다는 점은 유의해야 겠습니다)

 

 

아래 거리행렬의 d(P3, P4), d(P3, P5), d(P4, P5)는 위의 거리행렬 [distance matrix - no.1]에서 계산한 결과를 그대로 가져다가 썼습니다.

 

[distance matrix - no.2]

 

 

 

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

 

수정된 2차원 부분집합그림은 아래와 같습니다. (P1, P2) 군집에 이어 두번째로 (P4, P5) 군집이 묶였습니다.

 

 

 

 

4) 군집(P1, P2)와 군집(P4, P4), 개체 P3 간의 거리를 평균 연결법(average linkage method)으로 수정한 거리행렬(distance matrix) 구하기

 

군집 간 거리 계산 방법은 동일하게 '평균 거리'를 계산하면 됩니다.

 

[distance matrix - no.3]

 

 

 

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

 (여기까지도 군집 묶이는 순서가 이전의 단일(최단) 연결법, 완전(최장) 연결법과 결과가 같습니다. 예제를 급하게 만들었더니 그만...^^;  서로 좀 다른게 있어야지 실감을 할텐데요... ^^;;;  그래도 군집 간 거리는 단일 연결법과 완전 연결법의 중간 즈음, 즉 MIN과 MAX사이의 평균값으로 바뀌었음을 알 수는 있습니다. ^^;;;;;)

 

 

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

 

 

 

 

5) 군집(P1, P2)와 군집{P3, (P4, P5)} 간의 거리를 평균 연결법으로 수정한 거리행렬 구하기

 

군집 간 평균 연결법을 사용한 거리 계산은 아래와 같습니다.  조금 복잡해 보일 수도 있는데요, 단순 사칙연산의 연속입니다.

 

 

 

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

 

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

 

 

 

 

이상의 '완전(최장) 연결법'에 의한 응집형 계층적 군집화를 위한 R script는 아래와 같습니다.  역시 단 한줄로 짧습니다.

 

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

 

 

 

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

 

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

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

 

아래 덴드로그램의 Height가 위에서 수기로 계산한 군집 간 거리와 일치하지요?  가령, 가장 마지막에 병합된 군집 (P1, P2)와 군집 {P3, (P4, P5)} 간의 거리가 손으로 계산한 거리가 13.83이었으며, 아래 덴드로 그램도 14에서 조금 못미치고 있습니다.

 

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

 

 

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

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

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

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

 

> > # custering information > rev(hc_avg) $dist.method [1] "euclidean" $call hclust(d = dist(xy)^2, method = "average") $method [1] "average" $labels NULL $order [1] 1 2 3 4 5 $height [1]  1.00000  2.00000  7.00000 13.83333 $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") > > # dendrogram > my_par = par(no.readonly = TRUE) > par(oma = c(0, 0, 1, 0)) > par(mfrow = c(1, 3)) > plot(hc_sl, main = "Single Linkage") > plot(hc_cl, main = "Complete Linkage") > plot(hc_avg, main = "Average Linkage")

 

 

이상으로 (1) 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘의 (1-3) 평균 연결법(Average 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-4) 중심 연결법(Centroid linkage method)에 대해서 알아보도록 하겠습니다.

 

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