[R 군집분석 (Cluster Analysis)] (1) 응집형 계층적 군집화 : (1-5) Ward 연결법 (Ward Linkage Method)
R 분석과 프로그래밍/R 군집분석(Clustering) 2016. 7. 16. 12:29응집형 계층적 군집화(agglomerative hierarchical clustering) 방법 중에서
- 지난번 포스팅에서는 중심 연결법 (Centroid Linkage Method)를 다루었으며,
- 이번 포스팅에서는 Ward 연결법 (Ward Linkage Method) 에 대해서 알아보겠습니다.
(참고로, Ward는 이 방법을 제시했던 학자인 Joe H. Ward 의 이름을 딴 것입니다)
그동안의 응집형 계층적 군집화에서 다루었던 연결법들로 단일 연결법(single linkage), 완전 연결법(complete linkage), 평균 연결법(average linkage), 중심 연결법(centroid linkage)은 모두 '유클리드 제곱거리(euclidean squared distance)'에 기반해서 군집을 형성하는 방법들 이었습니다.
반면에, 이번에 소개하는 Ward 연결법(ward linkage)은 두 군집 간의 유사성을 두 군집이 합쳐졌을 때의 오차 제곱합(ESS : error sum of squares)의 증가분에 기반해서 측정합니다. (Similarity of two clusters is based on the increase in squared error when two clusters are merged). 즉, 거리 행렬(distance matrix)를 구할 때 오차제곱합의 증분(increase of ESS)을 두 군집 사이의 거리로 측정하게 됩니다.
단일 연결법이 노이즈나 이상치(noise and outlier)에 민감한 반면에, Ward 연결법은 노이즈나 이상치에 덜 민감한 장점이 있습니다. 그리고 Ward 연결법은 비슷한 크기의 군집끼리 묶어주는 경향이 있습니다.
중심 연결법과 Ward 연결법의 유사성 측정 수식이 비슷한데요, 중심 연결법의 유사성 측도 대비 Ward 연결법에는 가중값이 추가되었다는 점이 다릅니다. (분자는 같고, 분모가 서로 다름)
기본 컨셉은 다음번 포스팅의 프로토타입 기반 분할적 군집화의 하나인 "K 평균 군집화(K-means clustering)"와 유사한 측면이 있습니다.
예제를 가지고 풀어보면서 설명을 이어가 보겠습니다.
(미리 말씀드리자면, 손으로 푼 결과와 R로 계산한 결과가 서로 다르게 나왔습니다. 어디서 차이가 생기는 건지 파악을 못했습니다. 혹시 이 블로그를 보시고 제가 잘못 계산한 부분을 찾으셨다면 댓글로 알려주시면 감사하겠습니다. ㅜ_ㅜ)
1) 데이터셋 준비, 탐색적 분석
응집형 계층적 군집화이므로 처음에 아래의 5개의 점, 5개의 군집에서부터 시작합니다.
R script도 같이 제시하면서 설명하겠습니다. 먼저, 데이터 입력 및 plotting (↑ 위의 산점도 그래프) 입니다.
> ##-------------------------------------------- > ## (1) Agglomerative Hierarchical Clustering > ## (b) Prototype-based > ## (1-5) Ward 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 > my_par = par(no.readonly = TRUE) > par(mfrow = c(1, 1)) > 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 계산하기
각 데이터를 군집으로 하는 첫번째 단계에서는 ESS의 증분은 '유클리드 제곱거리(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) 이 됩니다.
(여기까지는 중심 연결법과 동일)
[centroid coordinate of clusters - no.1]
아래의 부분집합그림에 보면 군집 (P1, P2) 의 중심(centroid) 위치에 노란색 별이 추가되었습니다.
4) 군집(P1, P2)와 P3, P4, P5 간 Ward 연결법(Ward linkage method)으로 계산한 수정된 거리행렬(distance matrix) 구하기
한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 Ward 연결법에 의한 거리는 위의 [centroid coordinate of clusters - no.1] 의 중심 좌표를 가지고 ESS 증분으로 구하면
d{(P1, P2), P5} = {(1.5-5)^2 + (1-4)^2}/(1/2 + 1/1) = (12.25 + 9)/(3/2) = 21.25*2/3 = 14.17 이 됩니다.
[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) 간의 거리를 Ward 연결법(Ward linkage method)으로 계산하여 수정한 거리행렬(distance matrix) 구하기
[distance matrix - no.3]
- 개체 P3와 군집 (P4, P5)의 거리가 '4.3'로서 가장 가까우므로
→ P3과 (P4, P5)를 새로운 군집으로 묶어줍니다(merge). 반복(repeat)을 거듭할 수록 군집이 줄어서 이제 2개가 되었습니다.
7) 새로 합쳐진 군집 {P3, (P4, P5)} 의 중심(centroid)를 가중 평균을 사용해서 구하기
[centroid coordinate of clusters - no.3]
여기까지 진행한 군집화 결과를 반영해 수정한 부분집합그림은 아래와 같습니다.
8) 군집 (P1, P2)와 {P3, (P4, P5)} 의 중심 간 거리를 Ward 연결법(Ward linkage method)으로 계산하여 수정한 거리 행렬(distance matrix) 구하기
- 마지막으로 두개 남은 군집 (P1, P2)와 {P3, (P4, P5)}를 묶어줍니다(merge).
→ 드디어 반복(repeat)을 거듭한 끝에 군집이 1개로 줄어들었습니다.
→ 종료 (End)
마지막 군집이 병합된 이후의 수정된 부분집합그림은 아래와 같습니다.
이상의 'Ward 연결법(Ward linkage method)'에 의한 응집형 계층적 군집화를 위한 R script는 아래와 같습니다.
> # Agglomerative Hierarchical Clustering : Centroid Linkage method > hc_ward <- hclust(dist(xy)^2, method="ward.D") > hc_ward Call: hclust(d = dist(xy)^2, method = "ward.D") Cluster method : ward.D Distance : euclidean Number of objects: 5
|
9) 덴드로그램(Dendrogram)으로 응집형 계층적 군집화(by Ward 연결법) 결과 확인해보기
아래 덴드로그램의 y축이 바로 군집 간 거리 (Ward 연결법으로 구한) 를 나타냅니다.
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_ward) > plot(hc_ward, hang = -1) # hang = -1 : line from the bottom
|
rev() 함수를 사용하면 군집 모델에 대한 정보를 알 수 있습니다.
- $method : 연결 방법(linkage method)
- $height : 군집 간 거리(distance between clusters)
- $merge : 군집 간 병합 순서 (merge sequence)
> # custering information > rev(hc_ward) $dist.method [1] "euclidean" $call hclust(d = dist(xy)^2, method = "ward.D") $method [1] "ward.D" $labels NULL $order [1] 1 2 3 4 5 $height [1] 1.000000 2.000000 8.666667 28.333333 $merge [,1] [,2] [1,] -1 -2 [2,] -4 -5 [3,] -3 2 [4,] 1 3
|
군집 간 유사성 측도로서 'ESS 증분'을 사용해서 거리 행렬을 손으로 푼 결과와 R로 계산한 결과가 서로 다르게 나왔습니다. 어디서 차이가 생기는 건지 파악을 못했습니다. 혹시 이 블로그를 보시고 제가 잘못 계산한 부분을 찾으셨다면 댓글로 알려주시면 감사하겠습니다. ㅜ_ㅜ
[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) "Data Mining Cluster Analysis : Basic Concepts and Algorithms", Tan, Steinbach, Kumar, 2004
(5) Wikipedia
- ward method : https://en.wikipedia.org/wiki/Ward%27s_method
계층적 군집화 방법 중 분리형(Top-down) 방식의 다이아나 방법(DIANA method)는 복잡도가 너무 높아 실제 많이 사용하지 않는 알고리즘이므로 별도 포스팅하지 않고 건너뛰겠습니다.
다음번 포스팅에서는 (2) 분할적 군집화(Partitional clustering) 알고리즘의 (2-1) 프로토타입 기반(Prototype-based) 군집화 중에서 (2-1-1) K-평균 군집화(K-means clustering)에 대해서 알아보도록 하겠습니다.
이번 포스팅이 도움이 되었다면 아래의 '공감 ~♡'를 꾸욱 눌러주세요.
