R, Python 분석과 프로그래밍의 친구 (by R Friend)

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

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

> ##--------------------------------------------
> ## (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

> # 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

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

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) 구하기

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

> # 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 

> # 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

> # 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

> # 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")

이제 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

> # 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

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

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

> # 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 

> # 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
> 
 

> # 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")

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

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

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

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

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

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

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

[distance matrix - no.1]

> # 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

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]

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

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

이상의 '완전(최장) 연결법'에 의한 응집형 계층적 군집화를 위한 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

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

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