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

지난번 포스팅에서는 군집분석의 유형과 알고리즘 종류, 그리고 유사성 측도로서의 거리에 대해서 알아보았습니다.

이번 포스팅에서는 세부적인 분석 알고리즘의 첫번째로서, 각 데이터에서 시작해서 유사한(즉, 가까운) 데이터끼리 순차적으로 군집을 묶어나가는 응집형 계층적 군집화 (Agglomerative Hierarchical Clustering, "Bottom-up") 알고리즘에 대해서 알아보겠습니다. 

(↔ 참고로, 분리형(Divisive) 계층적 군집화 알고리즘은 하나의 군집에서 시작해 Top-down으로 군집을 나누어가서 각 데이터가 하나의 군집이 될 때까지 분화 반복)

응집형 계층적 군집화 알고리즘은 아래와 같습니다. 거리 행렬을 가지고 군집 간 유사성을 측정해서 모든 데이터가 하나의 군집으로 응집/병합될 때까지 반복적으로 군집화를 수행합니다.

위의 알고리즘에 보면 유사성 행렬(proximity matrix), 거리 행렬(distance matrix)가 나오는데요, 지난번 포스팅에서 소개했었던 다양한 거리 측도 중에서 데이터 특성, 분석 목적에 맞는 거리 측도를 선택해서 가능한 모든 쌍의 데이터 간 거리를 계산하면 됩니다. (유사성 측도로 거리를 사용하면 => "거리가 짧을 수록 유사하다"고 해석)

응집형 계층적 군집화 방법에는 "군집 간 거리를 측정하는 방법"에 따라서 여러가지가 있습니다. 이번 포스팅에서는 그래프 기반(Graph-based)의 연결법으로 '단일(최단) 연결법 (Single linkage method)'를 소개하겠습니다. 그래프 기반 연결법은 각 데이터를 Node로 하고, Nodes 간 연결(connectivity)한 선을 Link or Arc로 하며, 이들 Link or Arc 의 길이를 가지고 거리를 측정합니다.

"단일 연결법(Single linkage method)"은 "최단(MIN) 연결법"이라고도 하며, 다른 군집에 속한 가장 가까운 두 점 사이의 거리를 군집 간의 거리로 측정하는 방법입니다. 

아래 그림은 군집 k와 군집 i+j (← 군집 i와 군집 j가 합쳐진 새로운 군집) 간의 거리를 단일(최단) 연결법으로 구할 때의 이미지입니다.

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

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

아래의 5개의 점 하나 하나가 각 군집(cluster)이 되겠습니다.  응집형 계층적 군집화이므로 처음에 아래의 5개의 점, 5개의 군집에서부터 시작합니다.

데이터셋에 결측값 없고, 산점도를 그려보니 이상값/특이값(outlier)도 없어 보이는군요.

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

> ##--------------------------------------------
> ## (1) Agglomerative Hierarchical Clustering 
> ##    (1-1) Single Linkage, MIN
> ##--------------------------------------------
> 
> 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

3) 군집 (P1, P2)와 개체 P3, P4, P5 간의 거리를 단일(최단) 연결법으로 수정한 거리행렬 구하기

단일(최단) 연결법은 다른 군집에 속한 가장 가까운 두 점의 거리를 군집 간 거리로 측정하는 방법이므로 아래의 계산 절차를 따릅니다. 

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 거리는 d(P1, P5)=25, d(P2, P5)=18 의 두 거리 중에서 최소값(MIN)인 '18'이 됩니다.  아래 거리행렬의 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개로 줄었습니다.

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

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

[distance matrix - no.3]

이상의 '단일(최단) 연결법'에 의한 응집형 계층적 군집화를 위한 R script는 아래와 같습니다.  너무 짧다고 놀라지 마세요. ㅋㅋ 

위에서 알고리즘 설명한다고 개난리를 쳤는데요, R로는 단 1줄이면 끝납니다.

(설명자료 쓰고 그리는데는 토요일 반나절 투자, R script 짜는데는 5분... )

> # Agglomerative Hierarchical Clustering : Single Linkage method (MIN)
> hc_sl <- hclust(dist(xy)^2, method="single")
> hc_sl

Call:
hclust(d = dist(xy)^2, method = "single")

Cluster method   : single 
Distance         : euclidean 
Number of objects: 5

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

덴드로그램(Dendrogram)은 (a) '무슨 군집과 무슨 군집이 서로 묶였는지 (서로 유사한지, 근접한지)', (b) '어떤 순서로 차례대로 묶여갔는지', (c) '군집 간 거리는 얼마나 되는지'를 알 수 있는 매우 유용한 그래프입니다.

아래 덴드로그램의 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_sl)
> plot(hc_sl, hang = -1) # hang = -1 : line from the bottom

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

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

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

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

> # custering information
> rev(hc_sl)
$dist.method
[1] "euclidean"

$call
hclust(d = dist(xy)^2, method = "single")

$method
[1] "single"

$labels
NULL

$order
[1] 1 2 3 4 5

$height
[1] 1 2 5 8

$merge
     [,1] [,2]
[1,]   -1   -2
[2,]   -4   -5
[3,]   -3    2
[4,]    1    3

위의 rev() 함수 결과의 객체를 indexing 해서 군집 간 특정 거리를 기준(threshold)으로 해서 기준거리 이상인 군집의 개수를 알아보겠습니다.

예를 들어서 군집 간 거리가 '6' 이상인 군집은 위의 덴드로그램에서 보면 군집(P1, P2)와 군집 {P3, (P4, P5)}의 2개가 있습니다. (아래 R script의 세번째 예시)

이상으로 (1) 응집형 계층적 군집화 : (1-1) 단일(최단) 연결법(Single link, MIN) 소개를 마치도록 하겠습니다. 다 쓰고 보니 스크롤 압박이 상당히 심한...블로그에는 부적절한 글이 되어버렸습니다. ㅜ_ㅠ