[R 군집분석 (Cluster Analysis)] (1) 응집형 계층적 군집화 : (1-2) 완전(최장) 연결법(complete link, MAX)

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

 

 

이번 포스팅에서는 응집형 계층적 군집화 알고리즘 중에서 그래프 기반(Graph-based) 방법의 두번째로 (1-2) 완전(최장) 연결법 (complete linkage method, MAX)에 대해서 알아보겠습니다.

 

 

 

 

 

단일(최단) 연결법이 군집 간 거리를 잴 때 다른 군집의 점들 중에서 가장 가까운 두 점 간의 거리를 사용하였다면, 완전(최장) 연결법은 반대로 '다른 군집의 점들 중에서 가장 멀리 떨어진 두 점 간의 거리를 가지고 군집 간 거리를 잽니다. 

 

아래의 가운데 그림은 군집 k와 군집 i+j (← 군집 i와 군집 j가 합쳐진 새로운 군집) 간의 거리를 완전(최장) 연결법으로 구할 때의 이미지인데요, 보시면 금방 이해할 수 있을 것입니다.

 

 

 

 

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

(지난번 포스팅의 단일(최단) 연결법 예시 데이터와 동일하며, 거리 계산 방법도 아래의 (1)번, (2)번까지는 똑같고, (3)번부터는 매우 유사함. 단일연결법을 정확히 이해했다면 이번 완전연결법은 그야말로 누워서 떡먹기임)

 

 

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

 

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

(결측값, 이상값/특이값 여부 check)

 

 

 

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

 

> ##-------------------------------------------- > ## (1) Agglomerative Hierarchical Clustering > ## (1-2) Complete Linkage, MAX > ##-------------------------------------------- > > 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 간의 거리를 완전(최장) 연결법으로 수정한 거리행렬 구하기

 

완전(최장) 연결법은 다른 군집에 속한 가장 멀리 떨어져 있는 두 점의 거리를 군집 간 거리로 측정하는 방법이므로 아래의 계산 절차를 따릅니다. 

 

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 거리는 d(P1, P5)=25, d(P2, P5)=18 의 두 거리 중에서 최대값(MAX)인 '25'가 됩니다.(↔ 단일(최단) 연결법은 최소값(MIN)을 거리로 채택).  단일(최단) 연결법 대비 군집-군집(개체) 간 거리가 더 길어졌습니다.

 

아래 거리행렬의 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개로 줄었습니다.

 

(※ 혹시 완전(최장) 연결법이므로 이 단계에서 최장(가장 큰) 값을 가지고 군집을 묶는 것으로 혼돈하시면 안됩니다.  최장 거리(MAX)는 거리행렬(distance matrix) 구하는 단계에서 사용했구요, 새로운 군집 merge할 때는 서로 가까운 점들 끼리 묶어주어야 합니다. 공교롭게도 아래의 부분집합그림이 이전 포스팅의 단일연결법의 결과와 같습니다. ^^; 거리의 길이는 완전(최장) 연결법이 더 멀리 떨어진 것으로 좀 달라졌구요.)

 

 

 

 

 

 

4) 군집(P4, P5)와 군집(P1, P2), P3 간의 거리를 완전(최장) 연결법으로 수정한 거리행렬 구하기

 

군집 간 거리 계산 방법은 동일하게 '최대값(MAX)'을 찾으면 됩니다.

 

[distance matrix - no.3]

 

 

 

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

 (여기까지도 군집 묶이는 순서가 이전의 단일(최소) 연결법과 결과가 같습니다. 예제를 급하게 만들었더니 그만...^^;  서로 좀 다른게 있어야지 실감을 할텐데요... ^^;;;)

 

 

 

 

 

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

 

 

 

 

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

 

 

 

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

 

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

 

 

 

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

 

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

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

 

이전 포스팅의 단일(최단) 연결법 대비 완전(최장) 연결법으로 구한 군집 간 거리(R 결과에서는 Height로 표기)가 더 길게 계산되었음을 알 수 있습니다.

 

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

 

 

 

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

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

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

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

 

> # custering information > rev(hc_cl) $dist.method [1] "euclidean" $call hclust(d = dist(xy)^2, method = "complete") $method [1] "complete" $labels NULL $order [1] 1 2 3 4 5 $height [1] 1 2 9 25 $merge [,1] [,2] [1,] -1 -2 [2,] -4 -5 [3,] -3 2 [4,] 1 3

 

 

이상으로 (1) 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘의 (1-2) 완전(최장) 연결법(complete linkage method, MAX) 에 대해서 알아보았습니다.

 

[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) 알고리즘의 그래프 기반(Graph-based) 군집 간 거리 측정법으로 (1-3) 평균 연결법(Average linkage method)에 대해서 알아보도록 하겠습니다.

 

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