지난번 포스팅에서는 (1) 응집형 계층적 군집화(Agglomerative Hierarchical Clustering) 방법 5가지(단일연결법, 완전연결법, 평균연결법, 중심연결법, Ward연결법) 중에서, 오차제곱합의 증분으로 군집 간 (비)유사성을 측정해서 군집화를 하는 Ward 연결법에 대해서 알아보았습니다.

 

 

이번 포스팅부터는 (2) 분할적 군집화(Partitional Clustering) 기법 중에서 프로토타입 기반(Prototype-based)K-중심 군집화(K-centroid clustering)에 대해서 알아보도록 하겠습니다.

 

 

[ 분할적 군집 (Partitional Clustering, Non-hierarchical Clustering) ]

 

 

 

 

복습하는 차원에서 한번 더 복기를 하자면,

 

- 응집형 계층적 군집화(Agglomerative Hierarchical Clustering)은 각각의 객체에서 시작해서 유사성 척도(proximity measure)에 의거해 유사한 (거리가 짧은) 객체들을 Tree 형태의 계층적 군집으로 차근 차근 묶어가는 기법입니다. (a set of nested clusters organized as a hierarchical trees).  일단 한번 군집으로 묶이면 그 객체는 계속 그 군집에 속하게 되고 변동이 없으며, 계층 구조의 Tree에서 어느 수준을 기준으로 하느냐에 따라서 군집이 달라지게 됩니다.

 

- 분할적 군집화(Partitional Clustering)은 객체가 하나의 군집에 exclusive하게 속하도록 군집을 형성합니다. (A division data objects into non-overlapping subsets such that each data object is in exactly one subset). 분할 방법에는 프로토타입 기반(Prototype-based), 분포 기반(distribution-based), 밀도 기반(Density-based), 그래프 기반(Graph-based) 기법이 있습니다.

 

 

참고로,

- Hard clustering은 객체별로 어느 군집에 속할지를 명시적으로 할당하는 기법이며,

K-중심군집은 Hard clustering에 속합니다.

 

- Soft clustering은 각 객체가 어느 군집에 속할지를 가중치(weight)나 확률(probability)로서 가능성 정도를 나타내주는 기법으로서, Fuzzy Clustering과 혼합분포군집(Mixture Distribution Clustering)이 이에 속합니다.

 

 

 

이번 포스팅에서 소개할 분할적 군집화는 이중에서 프로토타입 기반(Prototype-based) 기법 중에서도 K-중심군집(K-centroid Clustering) 모형이 되겠습니다.

 

프로토타입 기반 군집화(Prototype-based Clustering)는 미리 정해놓은 각 군집의 프로토타입에 각 객체가 얼마나 유사한가 (혹은 가까운가)를 가지고 군집을 형성하는 기법입니다. 

 

K-중심군집에서는 연속형 데이터의 경우 평균(Mean)이나 중앙값(Median)을 그 군집의 프로토타입으로 하며, 이산형 데이터인 경우는 최빈값(Mode)이나 메도이드(Medoid)라고 해서 해당 군집을 가장 잘 표현할 수 있는 측도를 정해서 프로토타입으로 정하게 됩니다.

 

보통 군집분석을 공부한다고 했을 때 가장 많이 회자되고, 가장 처음에 배우는 기법이 아마도 'K-평균 군집화(K-means Clustering)이 아닐까 싶습니다.  그런데 앞서 소개드린 것처럼 군집분석 기법에는 정말 많은 알고리즘이 있습니다. K-평균 군집은 그 중에서도 일부에 해당하는 기법일 뿐이며, 프로토타잎도 데이터 형태에 따라서 '평균(Mean)'을 쓰는 K-means Clustering, '중앙값(Median)'을 쓰는 K-median Clustering, '메도이드(Medoid)'를 쓰는 K-medoid Clustering 등으로 세분화된다는 점은 알아두시면 좋겠습니다.  이들을 모두 묶어서 'K-중심군집(K-centroid Clustering)'이라고 합니다.

 

여기서 'K'는 '군집의 수(number of clusters)'를 나타내는 모수(parameter)로서, 분석가가 사전에 정해주어야 합니다.  참고로, 군집의 수 K를 미리 지정해주어야 하는 군집분석 기법으로는 이번 포스팅의 주제인 K-중심군집(K-centroid Clustering), 그리고 퍼지군집(Fuzzy Clustering), 혼합분포 군집(Mixture Distribution Clustering) 등이 있습니다.

 

군집의 수 K를 정하는 문제가 참 중요한데요, 좀 어렵고 애매한 부분이 있습니다.  저는 보통은 업에 대한 이해를 바탕으로 분석 목적을 감안하여 복수의 k를 지정해서 군집분석을 수행한 후에, 군집에 대한 profiling을 해보고, 가장 적합하다고 판단되는 k를 정하곤 했습니다.  다분히 분석가의 업에 대한 경험/이해도와 주관이 많이 들어가고, Biz 활용 목적과 현실적 제약조건도 고려해야 하며, 또 시행착오와 profiling을 통한 오랜 탐색이 필요한 접근법입니다. (Science가 아니라 Art?)^^;  

 

아래의 괄호안에 자료에 보니 계량적으로 최적의 k 를 찾아가는 기법이 소개되어 있습니다.  이 기법들을 여기서 소개하려면 얘기가 너무 길어지므로 pass하겠으며, 관심있는 분은 아래 링크한 위키글을 참고하시기 바랍니다. (군집 수 k 정하는 기법 참고 자료 ☞ https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set)

 

 

[ 군집의 수 K 정하기의 애미모호함 ?  어려움?? ]

 

 

 

 

이번 포스팅에서는 일반적으로 가장 많이 사용하는 'K-평균 군집(K-means Clustering)'에 대해서만 대표로 설명을 하도록 하겠습니다.

 

 

K-평균 군집(K-means Clustering)의 원리를 알아보면요,

 

1) 군집 내 응집도 최대화(maximizing cohesion within cluster) : 군집 內 중심(centroid)과 해당 군집의 각 객체 간 거리의 합 최소화

 

2) 군집 간 분리도 최대화(maxizing separation between clusters) : 각 군집의 중심(centroid) 間 거리 합 최대화 

 

의 두 가지 목적함수를 만족하는 해(解, solution)를 찾는 것입니다.

 

 

[ K-평균 군집의 개념 및 원리 (Concept and Principle of K-means Clustering) ]

 

 

 

즉, 군집분석은 결국 위의 두 목적함수에 대한 최적화 (optimization of global objective function) 문제임을 알 수 있습니다.  복잡도(complexity)를 살펴보면, 군집의 수가 k, 차원의 수가 d, 객체의 수가 n 일 때 입니다. (* 출처 : https://en.wikipedia.org/wiki/K-means_clustering)  기본적으로 객체의 수(n)가 많을 수록 시간이 오래걸리며, 특히 변수의 수(d)와 군집의 수(k)가 늘어날 수록 지수적으로 계산 시간이 증가함을 알 수 있습니다.  따라서 허접한 변수들 몽땅 때려넣고 군집화하라고 컴퓨터한테 일 시킬 것이 아니라, 똘똘하고 핵심적인 변수를 선별해서 차원을 줄인 후에 군집분석을 실행하는 것이 연산시간을 줄이는 측면에서나, 또 Biz. 목적에 맞게 잘 군집화가 되도록 하는 측면에서나 중요합니다.

 

 

다음으로, 'K-중심군집 알고리즘(K-centroid Clustering Algorithm)'에 대해서 알아보겠습니다.  알고리즘은 알고나면 허무할 정도로 정말 쉽습니다. ^^' 컴퓨터야 중심과 객체 간 거리를 반복적으로 계산하느라 죽어나겠지만 말이지요.

 

 

[ 'K-중심군집 알고리즘(K-centroid Clustering Algorithm) ]

 

 

0: Select number of clusters, K

 

1: Select K points as the initial centroids


2: Repeat


3:     Form K clusters by assigning all points
       to the closest centroid


4:     Recompute the centroid of each cluster


5: Until The centroids don't change 

 

 

0: 군집의 수 K 결정

 

1: K개 군집의 초기 중심 선정

 

2: Repeat

 

3:    객체와 K군집의 중심과 거리가 가장 가까운

      군집으로 각 객체를 할당

 

4:    객체와 새로 바뀐 K군집의 중심과의

      거리를 재계산

 

5: Until K군집 중심이 바뀌지 않을 때까지 반복

 

 

 

 

위 알고리즘을 도식화해서 예를 들어보면 아래와 같습니다. 매번의 반복(iteration) 마다 군집의 중심이 새로 계산되고, 새로 바뀐 중심과 각 객체간 거리가 다시 계산되면서 군집이 계속 동적으로 바뀌다가 더 이상 변동이 없이 수렴될 때까지 반복을 하게 됩니다. 

 

 

[ K-평균군집화의 개념적인 예시 (Conceptual exmaple of K-means Clustering) ]

 

 

 

위의 개념적 예시 그림에서도 짐작할 수 있듯이, 초기 중심값(initial centroid)가 바뀌면 군집 묶이는게 바뀔 수 있습니다.  이런 점때문에 B2C에서 고객세분화(customer segmentation)에 K-means clustering을 적용하게 되면 매번 군집화를 시도할 때마다 군집에 묶이는 고객이 달라질 수 있어서 문제가 될 소지가 있습니다.  (참고로, R에서 set.seed = 1234 처럼 set.seed() 함수를 사용하면 무작위수가 매번 실행때마다 동일하게 할 수 있음)

 

 

이번 포스팅은 K-평균 군집(K-means Clustering)을 다룬다고 했으므로, 중심(centroid)는 '평균(Mean)'이 되겠지요.

 

그리고 유사도(proximity, similarity)는 보통은 유클리드 거리(Euclidean distance,

) 혹은 유클리드 제곱 거리(SSE, SUM of Squared Error, R에서 사용하는 거리)를 사용합니다.  데이터 특성에 따라서 유사도 측도로서 적합한 Measure를 선택해서 분석하시면 되겠습니다. (☞ 유사도 측정 Distance Measures 참고 : http://rfriend.tistory.com/199)

 

거리를 가지고 유사성을 측정한다고 했는데요, 이러다 보니 K-평균군집(K-means Clustering)은 노이즈나 이상치에 민감(Sensitive to Noise and Outlier)한 단점이 있습니다.  평균보다는 중앙값이 이상치에 덜 민감하므로 이상치로 인한 왜곡이 우려되면 K-중앙값군집(K-median Clustering)이 대안이 될 수 있겠네요.  아니면 탐색적 분석 단계에서 이상치를 제거하는 것도 방법이 될 수 있겠고요.

 

 

마지막으로, 만약 여러 변수들의 계측 단위(scale)이 서로 다르다면 사전에 표준화(standardization)를 해줄 필요가 있습니다.  안그러면 측정 단위가 큰 특정 한, 두개의 변수에 의해 군집화가 휘둘릴 수 있기 때문입니다.  보통 표준정규분포로 z 표준화를 많이 사용합니다. (R의 scale() 함수)

 

 


 

 

K-중심 군집(K-Centroid Clustering) 이론에 대해서는 왠만큼 소개를 한듯 하니, 이제 데이터셋을 가지고 R script 를 써가면서 실습을 해보겠습니다.  R script 가 무척 짧아서 당황하실수도 있다는 점 미리 안내드립니다. ㅋㅋ

 

실습 데이터셋은 iris 입니다. 

Sepal.Length, Sepal.Width, Petal.Length, Petal.Width 의 4개의 변수를 가지고 있고, 150개의 관측치를 가지고 있는 데이터프레임입니다.

 

결측값은 없이 깨끗하네요.

 

측정 척도의 단위(scale)가 4개 변수 모두 길이를 재는 동일 단위이므로 iris 데이터셋의 경우 별도로 표준화르 할 필요는 없겠네요. 

 

> ##-----------------------------------
> ## K-centroid clustering
> ##-----------------------------------
> 
> # dataset : iris
> str(iris)
'data.frame':	150 obs. of  5 variables:
 $ Sepal.Length: num  5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
 $ Sepal.Width : num  3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
 $ Petal.Length: num  1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
 $ Petal.Width : num  0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
 $ Species     : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...
> head(iris)
  Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1          5.1         3.5          1.4         0.2  setosa
2          4.9         3.0          1.4         0.2  setosa
3          4.7         3.2          1.3         0.2  setosa
4          4.6         3.1          1.5         0.2  setosa
5          5.0         3.6          1.4         0.2  setosa
6          5.4         3.9          1.7         0.4  setosa
> 
> # checking missing value
> colSums(is.na(iris))
Sepal.Length  Sepal.Width Petal.Length  Petal.Width      Species 
           0            0            0            0            0

 

 

 

 

산포도(Scatter Plot)를 그려보면 아래와 같습니다.

 

> # scatter plot of iris
> panel.fun <- function(x, y, ...) {
+   horizontal <- (par("usr")[1] + par("usr")[2]) / 2; 
+   vertical <- (par("usr")[3] + par("usr")[4]) / 2; 
+   text(horizontal, vertical, format(abs(cor(x,y)), digits=2)) 
+ }
> 
> pairs(iris[1:4], 
+       pch = 21, bg = c("red","green3","blue")[unclass(iris$Species)], 
+       upper.panel=panel.fun, 
+       main = "Statter Plot of Iris Dataset")

 

 

 

 

K-means Clustering이 중심과의 거리를 가지고 군집을 묶는 방법이다보니, 위의 산포도를 보면 Petal.Length와 Petal.Width 의 두개의 변수를 가지고 군집화(Clustering)를 하는 것이 제일 좋을 것 같군요.(아마 Sepal.Width와 Petal.Length 의 두개 변수를 사용해서 K-means Clustering을 돌리면 좌측 상단의 두 Species가 반반씩 잘못 섞여서 군집화가 될겁니다. 왜 그럴지는 한번 생각해보시길...) 

 

Petal.Length와 Petal.Width 로 산점도를 그려보면 아래와 같습니다.

 

[plot 1 : original scatter plot]

 

 

> # Original Scatter Plot of Iris Petal.Length & Petal.Width 
> install.packages("ggplot2")
trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.3/ggplot2_2.1.0.zip'
Content type 'application/zip' length 2001758 bytes (1.9 MB)
downloaded 1.9 MB

package ‘ggplot2’ successfully unpacked and MD5 sums checked

The downloaded binary packages are in
	C:\Users\Administrator\AppData\Local\Temp\Rtmpi20q05\downloaded_packages
> library(ggplot2)
> iris_plot <- ggplot(data=iris, aes(x=Petal.Length, y=Petal.Width, colour=Species)) + 
+   geom_point(shape=19, size=4) + 
+   ggtitle("Original Scatter Plot of Iris Petal.Length & Petal.Width")
>   
> iris_plot
> # text annotation with Species Name
> iris_plot_2 <- iris_plot +
+   annotate("text", x=1.5, y=0.7, label="Setosa", size=5) + # text annotation
+   annotate("text", x=3.5, y=1.5, label="Versicolor", size=5) + 
+   annotate("text", x=6, y=2.7, label="Virginica", size=5)
> 
> iris_plot_2
> # adding shadowed box
> iris_plot_3 <- iris_plot_2 +
+   annotate("rect", xmin=0, xmax=2.6, ymin=0, ymax=0.8, alpha=0.1, fill="red") + 
+   annotate("rect", xmin=2.6, xmax=4.9, ymin=0.8, ymax=1.5, alpha=0.1, fill="green") + 
+   annotate("rect", xmin=4.8, xmax=7.2, ymin=1.5, ymax=2.7, alpha=0.1, fill="blue")
> 
> iris_plot_3

 

 

 

 

 

Noise나 이상값(outlier)는 없어보이므로 별도 전처리 없이 그대로 데이터 가져다 쓰면 되겠네요.

 

자, 이제 드디어 K-평균군집(K-means Clustering)을 R로 돌려보겠습니다.  군집의 개수 K = 3 으로 하겠습니다. (iris 품종으로 Setosa, Versicolor, Virginica 의 3종류가 있다고 우리가 이미 알고 있기 때문에 K 3으로 한 것임.  일반적으로 K-평균군집분석을 할 때 Y Label에 대해서 모르거나 없는 상태에서 비지도학습(Un-supervised Learning)으로서 데이터 속에 숨겨진 패턴을 컴퓨터 보고 한번 찾아보라고 마이닝을 시키게 됨.  다시 한번 말하지만, 이번 iris 데이터셋은 Y Lable을 알고 있는 상태에서 K-평균군집분석 결과를 좀더 이해하기 쉽도록 비교해서 보여주는 것 뿐이며, Y Lable 모른 채, 혹은 없는 상태에서 군집분석을 수행하게 됨)

 

K-평균군집의 R script는..... 음..... 아래 한줄이 끝입니다. -_- 

 

kmeans(dataset, k)  # k : number of clusters

 

> # K-means clustering with Petal.Length and Petal.Width
> iris_k_means <- kmeans(iris[,c("Petal.Length", "Petal.Width")], 3) 

 

 

 

K-평균군집의 객체 iris_k_means 를 호출하면 아래와 같이 K-평균 군집 결과를 일목요연하게 볼 수 있습니다. 

 

- K-means clustering with 3 clusters of sizes 50, 52, 48

   : 군집의 개수(k)가 3개, 군집 1/2/3별 크기가(개체 개수) 50개, 52개, 48개

- Cluster means

   : 군집 1/2/3 별 두개의 변수 Petal.Length, Petal.Width의 평균 좌표 

     (=> profiling 하기에 good!)

- Clustering vector

   : 각 개체별 군집 벡터
- Within cluster sum of squares by cluster

   : 각 군집의 중심(centroid)와 각 군집에 속한 개체간 거리의 제곱합

- Available components

   : 군집분석 결과의 구성요소
     => 필요한거 있으면 이 객체(object)를 indexing해서 쓰면 요긴함
 

 

> iris_k_means
K-means clustering with 3 clusters of sizes 50, 52, 48

Cluster means:
  Petal.Length Petal.Width
1     1.462000    0.246000
2     4.269231    1.342308
3     5.595833    2.037500

Clustering vector:
  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
 [52] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3
[103] 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3

Within cluster sum of squares by cluster:
[1]  2.02200 13.05769 16.29167
 (between_SS / total_SS =  94.3 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"        
[8] "iter"         "ifault"   

 

 

 

 

아래처럼 names() 함수를 써서 군집분석 결과의 객체들에 무엇이 있는지 확인해볼 수도 있습니다.

 

- cluster : 각 개체별 할당된 군집 번호, 1부터 k번까지 군집 숫자 

             (A vector of integers (from 1:k) indicating the cluster to which each point is allocated.)

- centers : 군집의 중심 (centroid) 좌표 행렬 (A matrix of cluster centres.)

- totss : 제곱합의 총합 (total sum of squares)

- withinss : 군집 내 군집과 개체간 거리의 제곱합 벡터.

               (Vector of within-cluster sum of squares, one component per cluster)

- tot.withinss : 군집 내 군집과 개체간 거리의 제곱합의 총합, 즉, sum(withinss)

                   (Total within-cluster sum of squares, i.e. sum(withinss))

- betweenss : 군집과 군집 간 중심의 거리 제곱합

                   (The between-cluster sum of squares, i.e. totss-tot.withinss)

- size : 각 군집의 개체의 개수 (The number of points in each cluster)

- iter : 반복 회수 (The number of (outer) iterations)

- ifault : 전문가용의 발생 가능한 알고리즘 문제의 indocator (?? 이거 뭔지 잘 모르겠음... -_-??)
           (integer: indicator of a possible algorithm problem – for experts)

 

> # objects of k-means clustering in R
> names(iris_k_means)
[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"        
[8] "iter"         "ifault"

 

 

 

 

그럼, 군집의 크기(객체의 개수)를 한번 확인해볼까요?  table() 함수를 써도 되고 size 객체를 가져다가 확인해도 됩니다. 두 가지 방법 모두 아래에 소개하였습니다.

 

> # cluster size > table(iris_k_means$cluster) 1 2 3 50 52 48


>
iris_k_means$size [1] 50 52 48 > > prop.table(iris_k_means$size) [1] 0.3333333 0.3466667 0.3200000

 

 

 

 

각 군집 1, 2, 3의 중심(centroid)도 확인해보겠습니다.

 

> # centroid of clusters
> iris_k_means$centers
  Petal.Length Petal.Width
1     1.462000    0.246000
2     4.269231    1.342308
3     5.595833    2.037500 

 

 

 

마지막으로, 각 개체들을 군집별로 색깔을 달리해서 산점도(scatter plot) 그려보겠습니다.  덤으로 각 군집의 중심(centroid)을 검정색 점으로 해서 덮입혀보았습니다.

 

위의 [plot 1 : original scatter plot]에서 iris species 로 색깔을 구분해서 그린 산점도와 아래의 군집(cluster)별로 색깔을 구분해서 그린 산점도가 거의 유사하지요?

 

> # Scatter plot of Iris' K-menas clusters
> cluster <- iris_k_means$cluster
> iris_k_means_x_y <- cbind(cluster, iris[,c("Petal.Length", "Petal.Width")])
> head(iris_k_means_x_y)
  cluster Petal.Length Petal.Width
1       1          1.4         0.2
2       1          1.4         0.2
3       1          1.3         0.2
4       1          1.5         0.2
5       1          1.4         0.2
6       1          1.7         0.4
> 
> sapply(iris_k_means_x_y, class)
     cluster Petal.Length  Petal.Width 
   "integer"    "numeric"    "numeric" 
> iris_k_means_x_y <- transform(iris_k_means_x_y, 
+                               cluster = as.factor(cluster))
> 
> sapply(iris_k_means_x_y, class)
     cluster Petal.Length  Petal.Width 
    "factor"    "numeric"    "numeric" 
> 
> 
> library(ggplot2)
> iris_k_means_x_y_plot <- ggplot(data=iris_k_means_x_y, 
+                                 aes(x=Petal.Length, y=Petal.Width, colour=cluster)) + 
+   geom_point(shape=19, size=4) + 
+   ggtitle("Scatter Plot of Iris' K-means clusters")
> 
> iris_k_means_x_y_plot
> 
> 
> # adding centroid points of cluster 1, 2, 3
>   # centers(centroids) by cluster 1, 2, 3
> iris_k_means_centers <- iris_k_means$centers
> iris_k_means_centers
  Petal.Length Petal.Width
1     1.462000    0.246000
2     4.269231    1.342308
3     5.595833    2.037500
> 
> iris_k_means_x_y_plot_2 <- iris_k_means_x_y_plot +
+   annotate("point", x = 1.462, y = 0.246, size = 6, color = "black") + 
+   annotate("point", x = 5.595, y = 2.037, size = 6, color = "black") + 
+   annotate("point", x = 4.269, y = 1.342, size = 6, color = "black") + 
+   
+   annotate("text", x=1.462, y=0.4, label="Cluster 1", size=5) + 
+   annotate("text", x=5.595, y=2.2, label="Cluster 2", size=5) + 
+   annotate("text", x=4.269, y=1.5, label="Cluster 3", size=5)
>  
> iris_k_means_x_y_plot_2

 

 

 

 

 

이상으로 K-중심 군집의 하나인 K-평균군집(K-means Clustering)에 대해서 알아보았습니다.

 

다음번 포스팅에서는 프로토타입 기반(Prototype-based) 군집분석의 두번째 기법으로 퍼지 군지(Fuzzy Clustering)에 대해서 알아보겠습니다.

 

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

 

 

[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 :

    https://en.wikipedia.org/wiki/K-means_clustering

    https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

   

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

응집형 계층적 군집화(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)에 대해서 알아보도록 하겠습니다.

 

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

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

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

 

 

 

응집형 계층적 군집화 알고리즘 중에서 프로토타입 기반(Prototype-based) 모형은 미리 정해놓은 각 군집의 프로토타입에 터이터가 얼마나 가까운가로 군집의 형태를 결정합니다. 프로토타입 기반 유사성 측도로서 두가지 방법인 (1-4) 중심 연결법 (centroid linkage method)과 (1-5) Ward 연결법 (Ward linkage method) 중에서 이번 포스팅에서는 (1-4) 중심 연결법에 대해서 소개하겠습니다.

 

 

 

 

중심 연결법(Centroid Linkage method)은 두 군집 간의 거리를 측정할 때 각 군집의 중심(centroid) 간의 거리를 사용합니다.  아래 그림의 왼쪽의 이미지를 참고하시기 바랍니다.

 

     

[ 프로토타입 기반 유사성 측정 (Prototype-based maesure of proximity) ]

 

[표기 (denotation) 설명]

- d(i+j, k) : 군집 i와 j가 합쳐진 새로운 군집 i+j (cluster i U j)와 군집 k 간의 거리(distance)

- μi+j : 군집 i와 r군집 j의 데이터를 가중평균(weighted average)을 이용해 계산한 새로운 중심
- ni : 군집 i의 데이터 개수,  nj : 군집 j의 데이터 개수

        

- 빨간점 : 각 군집의 중심(centroid)

 

 

 

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

 

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

 

 

 

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

 

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

 

 

 

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

 

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

 

 

 

 

 

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

 

 

 

  • 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) 이 됩니다.

 

여기서 부터 앞서 소개했던 그래프 기반(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) 구하기

 

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

 

 

 

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 중심 연결법에 의한 거리는 위의 [centroid coordinate of clusters - no.1] 의 중심 좌표를 가지고 유클리드 제곱거리로 구하면

d{(P1, P2), P5} = (1.5-5)^2 + (1-4)^2 = 21.25  가 됩니다.

 

[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) 간의 거리를 중심 연결법(centroid linkage method)으로 계산하여 수정한 거리행렬(distance matrix) 구하기

 

유클리드 제곱거리를 사용해서 군집의 중심(centroid) 간의 거리를 계산하였습니다.

 

[distance matrix - no.3]

 

 

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

 

 

7) 새로 합쳐진 군집 {P3, (P4, P5)} 의 중심(centroid)를 가중 평균을 사용해서 구하기

 

 

[centroid coordinate of clusters - no.3]

 

 

 

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

 

 

 

 

 

8) 군집 (P1, P2)와 {P3, (P4, P5)} 의 중심 간 거리를 중심 연결법(centroid link)으로 계산하여 수정한 거리 행렬(distance matrix) 구하기

 

 

 

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

 

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

 

 

 

 

이상의 '중심 연결법(centroid linkage method)'에 의한 응집형 계층적 군집화를 위한 R script는 아래와 같습니다.

 

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

 

 

 

 

 

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

 

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

 

 

 

 

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

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

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

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

 

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

 

 

 

 

이전 포스팅의 단일(최단) 연결법, 완전(최장) 연결법, 평균 연결법과 비교를 했을 때 평균 연결법과 유사한 정도의 군집 간 거리(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")
> 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")

 

 

 

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

 

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

 

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

군집 간 거리를 측정하는 방법에 따라서 여러가지 알고리즘이 있는데요, 지난번 포스팅에서는 응집형 계층적 군집화(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)에 대해서 알아보도록 하겠습니다.

 

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

 

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

군집 간 거리를 측정하는 방법에 따라서 여러가지 알고리즘이 있는데요, 지난번 포스팅에서는 응집형 계층적 군집화(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)에 대해서 알아보도록 하겠습니다.

 

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

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend 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

 

 

  • 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 의 두 거리 중에서 최소값(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]

 

 

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

 

 

 

 

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

 

 

 

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

 

 

 

이상의 '단일(최단) 연결법'에 의한 응집형 계층적 군집화를 위한 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의 세번째 예시)

 

>
> # number of clusters above distance's threshold
>   # exmaple 1) height threshold = 1
> height_threshold <- 1
> distance_over_height <- rev(hc_sl)$height >= height_threshold
>
> number_of_cluster <- sum(distance_over_height)+1
> number_of_cluster
[1] 5
>
>
>   # exmaple 2) height threshold = 3
> height_threshold <- 3
> distance_over_height <- rev(hc_sl)$height >= height_threshold
>
> number_of_cluster <- sum(distance_over_height)+1
> number_of_cluster
[1] 3
>
>   # exmaple 3) height threshold = 6
> height_threshold <- 6
> distance_over_height <- rev(hc_sl)$height >= height_threshold
>
> number_of_cluster <- sum(distance_over_height)+1
> number_of_cluster
[1] 2 

 

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

 

[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-2) '완전(최장) 연결법'(Complete linkage method, MAX)에 대해서 알아보도록 하겠습니다.

 

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

 

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

지난번 포스팅에서는 (구간식 또는 비율식 데이터 속성의 다변수일 경우의) 유사성, 비유사성 측도로서 다양한 거리의 정의에 대해서 알아보았습니다.

 

이번 포스팅에서는 하나의 예를 가지고 R을 사용하여 각 거리 종류별 거리를 계산, 비교해보도록 하겠습니다.

 

예로 사용할 데이터는 5명의 학생의 '선형대수(linear algebra)'와 '기계학습(machine learning)' 기말고사 시험성적입니다.  이 중에서 1번째와 2번째 학생(아래 산점도의 빨간점)의 선형대수와 기계학습 시험점수의 거리를 (1) 맨하탄 거리(manhattan distance), (2) 유클리드 거리(euclidean distance), (3) 표준화 거리(standadized distance), (4) 마할라노비스 거리(mahalanobis distance)로 계산해보도록 하겠습니다.

 

> ##----------------------------------
> ## Dis-similarity measure - Distance
> ##----------------------------------
> 
> # 'linear algebra' and 'machine learning' score per student
> st_1 <- c(70, 65)
> st_2 <- c(90, 95)
> st_3 <- c(65, 60)
> st_4 <- c(85, 90)
> st_5 <- c(60, 75)
> 
> st_all <- rbind(st_1, st_2, st_3, st_4, st_5)
> st_all
     [,1] [,2]
st_1   70   65
st_2   90   95
st_3   65   60
st_4   85   90
st_5   60   75
> 
> # scatter plot
> plot(st_all, xlab = "linear algebra", ylab = "machine learning", 
+      xlim = c(50, 100), ylim = c(50, 100), 
+      main = "scatter plot of final scores")
> 
> # adding student label
> text(st_all[,1], st_all[,2], labels = abbreviate(rownames(st_all)), 
+      cex = 0.8, pos = 1, col = "blue")
> 
> # marking student 1, student 2 with red point
> points(st_all[1,1], st_all[1,2], col = "red", pch = 19)
> points(st_all[2,1], st_all[2,2], col = "red", pch = 19)

 

 

 

 

 

1) 맨하탄 거리 (Manhattan distance)

 

dist(dataset, method = "manhattan") 함수를 사용하여 맨하탄 거리를 계산할 수 있습니다.

 

아니면 아래의 두번째 방법처럼 두 변수의 관측치별 차이 절대값을 더해주면 됩니다 ( <- 달랑 2개 관측치 거리를 계산하는 거니깐 이 방식도 사용할만 하지만요, 만약 관측치 학생 1,000 명의 거리를 구하는 것이라면요? ^^;  두 방식의 결과값 포맷이 조금 다르다는 점도 눈여겨 봐주세요.)

 

 

> ##-- Manhattan distance between 1st and 2nd student
> ## (1) dist(dataset, method = "manhattan") function
> dist_mht <- dist(st_all[1:2, ], method = "manhattan")
> dist_mht
     st_1
st_2   50
> 
> ##-- Manhattan distance between 1st and 2nd student
> ## (2) calculation
> dist_mht_2 <- abs(st_all[1,1] - st_all[2,1]) + abs(st_all[1,2] - st_all[2,2])
> dist_mht_2
st_1 
  50 

 

 

 

 

2) 유클리드 거리 (Euclidean distance)

 

dist(dataset, method = "euclidean") 함수를 사용하여 유클리드 거리를 계산할 수 있습니다.

 

 

> ##-- Euclidean distance between 1st and 2nd student
> dist_euclid <- dist(st_all[1:2, ], method = "euclidean")
> dist_euclid
         st_1
st_2 36.05551

 

 

 

 

 

3) 표준화 거리, 통계적 거리 (Standadized distance, Statistical distance)

 

표준화 거리는 2가지 방법을 사용해서 계산해보겠습니다.

  (1) 데이터를 표준화한 후에 -> 유클리드 거리 계산

  (2) 

 

'2.501805' 로서 두 가지 계산 방법의 결과가 똑같습니다.

 

> ##-- Standadized distance > # (way 1) standadization -> euclidean distance > st_all [,1] [,2] st_1 70 65 st_2 90 95 st_3 65 60 st_4 85 90 st_5 60 75 > mean(st_all[,1]); sd(st_all[,1]) [1] 74 [1] 12.94218 > mean(st_all[,2]); sd(st_all[,2]) [1] 77 [1] 15.24795 > > # standadization of st_1's score > z_st_1 <- (st_all[,1] - mean(st_all[,1]))/sd(st_all[,1]) > z_st_1 st_1 st_2 st_3 st_4 st_5 -0.3090670 1.2362679 -0.6954007 0.8499342 -1.0817344 > > # standadization of st_2's score > z_st_2 <- (st_all[,2] - mean(st_all[,2]))/sd(st_all[,2]) > z_st_2 st_1 st_2 st_3 st_4 st_5 -0.7869910 1.1804865 -1.1149039 0.8525736 -0.1311652 > > z_st_all <- cbind(z_st_1, z_st_2) > z_st_all z_st_1 z_st_2 st_1 -0.3090670 -0.7869910 st_2 1.2362679 1.1804865 st_3 -0.6954007 -1.1149039 st_4 0.8499342 0.8525736 st_5 -1.0817344 -0.1311652 > > # euclidean distance between 1st and 2nd student's standadized score > dist_z_st_all <- dist(z_st_all[1:2, ], method = "euclidean") > dist_z_st_all st_1 st_2 2.501805 > > # ======================================================================= > # (way 2) [(X-Y)'D^-1(X-Y)]^1/2

> # covariance : cov()

> cov_st_all <- cov(st_all)

> cov_st_all

      [,1]  [,2]
[1,] 167.5 165.0
[2,] 165.0 232.5

> Diag <- rbind(c(cov_st_all[1,1], 0), + c(0, cov_st_all[2,2])) > Diag [,1] [,2] [1,] 167.5 0.0 [2,] 0.0 232.5 > > dist_stand <- sqrt(t(st_all[1,] - st_all[2,])%*%solve(Diag)%*% + (st_all[1,] - st_all[2,])) > dist_stand # exactly the same with the above result [,1] [1,] 2.501805

 

 

 

 

 

4) 마할라노비스 거리 (Mahalanobis distance) 

마할라노비스 거리는 아래 식을 사용해서 계산해보겠습니다.

 

 

 

> ##-- Mahalanobis distance
> # covariance : cov()
> cov_st_all <- cov(st_all)
> cov_st_all
      [,1]  [,2]
[1,] 167.5 165.0
[2,] 165.0 232.5
> dist_mahal <- sqrt(t(st_all[1,] - st_all[2,])%*%solve(cov_st_all)%*%
+                      (st_all[1,] - st_all[2,]))
> dist_mahal
         [,1]
[1,] 1.975854

 

 

 

위에서 계산한 4가지 방법별 거리 계산 결과를 종합하면 아래와 같습니다.

맨하탄 거리가 가장 길고 > 유클리드 거리 > 표준화 거리 > 마할라노비스 거리 순으로 나왔네요.

 

> ## overall
> dist_all <- cbind(dist_mht[1], dist_euclid[1], dist_stand, dist_mahal)
> dist_all
     [,1]     [,2]     [,3]     [,4]
[1,]   50 36.05551 2.501805 1.975854
> 
> barplot(dist_all, 
+         col = "blue", 
+         names.arg =  c("manhattan", "euclidean", "standadized", "mahalanobis"), 
+         main = "Distance between st_1 and st_2's score")

 

 

 

이상으로 군집분석 들어가기 전에 기초 체력을 다지는 의미에서 비유사성 측도로서의 거리(distance)에 대해서 알아보았습니다.

 

다음번 포스팅에서는 본격적으로 군집분석 세부 내용으로 들어가 보겠습니다. 첫 테잎은 '계층적 군집(hierarchical clustering) 모형'이 끊는 것으로 해보겠습니다.

 

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

 

 

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

지난번 포스팅에서는 군집분석(Cluster Analysis)의 개념과 유형에 대해서 알아보았습니다.

 

군집분석은 데이터를 유사한 혹은 동질의 군집(cluster)으로 묶어주는 것이라고 했었는데요, 그렇다면 "유사하다"(Similarity) 혹은 "유사하지 않다"(Dis-similarity)를 어떻게 측정할 수 있을지에 대한 방법이 이번 포스팅의 주제입니다.

 

이번에 살펴볼 거리 측도는 데이터와 데이터간 (비)유사성을 보는 군집분석뿐만이 아니라 변수와 변수간 관계를 보는 다변량 통계 분석에서도 기본기가 되는 중요한 내용이므로 유심히 보시기 바랍니다.  

 

데이터 간의 비유사성(Dis-similarity)거리(Distance)를 가지고 주로 측정하며, 유사성(Similarity)은 비유사성과 반비례의 관계에 있다고 보면 됩니다.  거리 말고 상관계수(Correlation coefficient)를 쓰기도 하는데요(→ collaborative filtering에서 상관계수 사용함), 이번 포스팅에서는 거리만 설명하도록 하겠습니다.

 

거리는 데이터의 속성, 구조에 따라서 적합한 것을 사용해야 하는데요, 이번 포스팅에서는 다중 변수의 구간식(Interval data type) 또는 비율식(Ratio data type) 데이터 속성에 대한 비유사성 측도로서 '거리'(Distance as a dis-similarity mesaure)척도로서,

 

  (1) 맨하탄 거리 (Manhattan distance)

  (2) 유클리드 거리 (Euclid distance)

  (3) 표준화 거리 (Standardized distance)

  (4) 마할라노비스 거리 (Mahalanobis distance)

 

에 대해서 소개하겠습니다.  이밖에 확장 자카르드 계수(Extended Jaccard Coefficient), 상관계수(Correlation Coefficient), 브레그만 거리(Bregman Divergence)는 생략합니다.

 

[ 표기 관련 (denotation) ]

- 두 변수값 x와 y비유사성 척도로서 거리(distance) 는 d(x, y) 또는 간단히 d 로 표기함

 

 

[ 거리 척도 (Distance measures) ]

 

 

 

(1) 맨하탄 거리 (Manhattan distance)

 

 

맨하탄 거리는 뉴욕의 택시가 출발지에서 도착지로 갈 때 빌딩을 피해 동, 서, 남, 북의 격자 모양의 도로를 직선으로 갈 때의 거리(즉, 가로 블록 + 세로 블록 절대합)를 본따서 이름을 붙힌 거리입니다. ("Manhattan distance" is a rectilinear distance, named after the number of blocks north, south, east, or west a taxicab must travel on to reach its destination on the grid of streets in parts of New York City. - from Wikipedia -).  물리적인 길거리를 생각하면 쉽습니다. 자동차가 아무리 마음이 급하다고 길과 길 사이에 있는 빌딩(방해물, obstacle)을 뚫고 대각선으로 지나갈 수는 없는 노릇이며, 좋으나 싫으나 아래 그림처럼 빌딩을 피해 '도로'가 놓여진 한계 안에서 '최단 route'를 찾는 수밖에 없습니다. (<= 바로 이런 상황의 데이터를 분석해야할 때 맨하탄 거리를 사용하면 됩니다)

 

다른 말로 "City block distance", "Chessboard distance", "Chebyshev distance" 라고도 합니다. 서양 체스의 Rook move (상/하/좌/우, 동/서/남/북 방향으로만 이동 가능)를 생각하면 됩니다.

 

두 점의 값(starting point -> destination)에 대한 맨하탄 거리(Manhattan Distance)를 그림과 수식으로 나타내면 아래와 같습니다.  그래프 이론(Graph theory)에서는 두 지점의 거리를 '최단 경로(shortest route)'로 정의하는데요, 아래 그림에서 보면 각 도러의 블록별 단위거리가 동일하다고 하면 최단경로가 route 1, route 2, route 3, .... 많습니다 (좌에서 우로 8번 & 하에서 상으로 7번 경로 조합인 모든 route).

 

 

맨하탄 거리(Manhattan distance)는 민코우스키 거리(Minkowski distance)에서 r=1 인 거리이기도 합니다.  r=2 (2-norm distance) 인 경우는 유클리드 거리 (Euclidean distance) 입니다.

 

 

For a point (x1, x2, ...,xm) and a point (y1, y2, ...,ym), Minkowski distance is...

 

 

 

 

 

(2) 유클리드 거리 (Euclidean distance)

 

유클리드 거리는 두 점을 잇는 가장 짧은 직선 거리입니다.  아래 그림을 예로 들면, 헬리콥터를 타고 x 지점에서 y지점으로 날아간다고 했을 때 x와 y 지점 사이에 아무리 많은 빌딩(방해물)이 있더라도 상관없이 최단 직선 코스로 날아갈 수 있다고 연상하면 쉽게 이해할 수 있을 것입니다. 창공을 나는 새의 관점(from a bird's eye view)으로 본 거리입니다.  (↔ 위의 택시를 타고 가는 맨하탄 거리와의 차이를 비교해보세요)

 

서양 체스로 치면 상, 하, 좌, 우, 대각선 어느 방향으로나 이동이 자유로운 King move 나 Queen move 를 생각하면 되겠네요. (↔ 맨하탄 거리는 Rook move)

 

m차원 유클리드 공간 (Euclidean space ) 에서 두 점 (x1, x2), (y1, y2)의 거리는 피타고라스 정리(Pythagorean theorem)에 의해서 아래 그림에서 제시한 공식으로 구할 수 있습니다. 

 

 

민코우스키 거리(Minkowski distance)에서 r=2 (2-norm distance) 인 거리가 바로 유클리드 거리 (Euclidean distance) 입니다

 

 

 

 

만약 세 점 (x1, x2, x3), (y1, y2, y3) (in three-space) 간의 거리는 어떻게 구하면 될까요?  이 또한 피타고라스 정리에 의해서 아래처럼 유클리드 거리 공식으로 구하면 됩니다.

 

 

아주 많은 분석에서 유클리드 거리를 사용하며, 그렇다보니 대부분 '거리'하면 '유클리드 거리'를 가장 먼저 떠올리게 되곤 합니다.  그만큼 친숙하고도 아주 유용한 거리 개념입니다.

 

그런데 유클리드 거리에도 한가지 고려해야 할 점이 있습니다.  만약 두 변수의 분산, scale이 서로 다르다면 어떻게 될까요?  ☞ 표준화 거리에 대해서 얘기할 시간이군요.

 

 

 

 

(3) 표준화 거리 (Standardized distance)

 

 표준화 거리는 각 변수를 해당변수의 표준편차(standard deviation)로 척도 변환한 후에 유클리드 거리를 계산한 거리입니다.  표준화를 하게 되면 척도(scale)의 차이, 분산의 차이로 인한 왜곡을 피할 수 있습니다.  

표준화 거리는 다른 말로 통계적 거리 (Statistical distance) 라고도 합니다.

 

 

 

표준화 거리를 이용하여 한 점에서 거리가 같은 점들의 집합을 구하면 표본평균을 중심으로 좌표축에 장축(major axis)과 단축(minor axis)이 반듯하게 놓인 타원(Ellipse) 또는 타원체를 이루게 됩니다. 변수가 2개인 경우 두 개체간의 표준화 거리를 구하면 타원의 중심은 각 변수의 평균값이 위치한 곳이 되며, 아래 그림과 같은 형태로 그려져 각 변수의 평균점을 중심으로 하는 타원이 됩니다. ("R 다변량 통계분석", 김재희)

 

 

 

 

 

(4) 마할라노비스 거리 (Mahalanobis distance)

 

마할라노비스 거리는 변수의 표준편차와 더불어 변수 간 상관성(correlation)까지 고려한 거리측도입니다. (참고로, 마할라노비스(Prasanta Chandra Mahalanobis, 29 June 1893 – 28 June 1972) 는 인도의 과학자 겸 응용통계학자로서 '마할라노비스 거리'를 제안한 분입니다.)

 

 

 

한 점에서 마할라노비스 거리가 같은 점들의 집합을 구하면 표본평균을 중심으로 축이 회전된 타원체(rotated ellipse)를 이루게 됩니다. 변수간의 상관성이 있을 때의 거리 측도로서 방향성을 고려하여 아래의 그림과 같이 회전된 축을 생각할 수 있습니다. ("R 다변량 통계분석", 김재희)

(↔ 바로 앞의 그림 '표준화 거리를 이용해 구한 한점에서 거리가 같은 점들의 집합 : 타원'과 비교해보세요)

 

 

 

맨하탄 거리와 유클리드 거리는 그래도 제법 접해봤을 기회가 있었을 것 같은데요, 표준화 거리와 마할라노비스 거리는 낯설기도 하고 수식도 선형대수 표기법이 나오고 해서 이해하기가 좀 어려울것 같습니다. 

 

수식을 자세히 보시면 SVD(Singular Value Decomposition), 특이값 분해(축 rotation -> scale 변환 -> 축 rotation)와 비슷함을 알 수 있습니다.

 

다변량통계분석 하는 분이라면 Hotelling's T-squared 통계량 수식과 매우 유사함을 알 수 있을거예요. 마할라노비스 거리를 1/n 로 나누어주면 Hotelling's T-squared 통계량이 됩니다. 재미있죠? ^^

 

다음번 포스팅에서는 간단한 예를 들어서 유클리드 거리, 표준화 거리, 마할라노비스 거리를 설명하고, R script 도 소개하도록 하겠습니다.

 

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

 

[Reference]

(1) Distance from Wikipedia (https://en.wikipedia.org/wiki/Distance)

(2) "R 다변량 통계분석", 김재희 지음, 교우사

(3) Mahalanobis distance from Wikipedia (https://en.wikipedia.org/wiki/Mahalanobis_distance)

 

참고로, 명명식(Norminal) 데이터에 대한 비유사성 척도로는 단순일치계수(Simple Matching Coefficient, SMC), 자카드 계수(Jaccard Coefficient, JC), 문서 비유사도 측정에 코사인 거리(cosine distance), 문자열 편집 거리(edit distance, Levenshtein metric)를 사용합니다.  순서식(Ordinal) 데이터에 대한 비유사성 척도로는 순위상관계수(Rank Correlation Coefficient)를 사용합니다.

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend

이번 포스팅에서는 Y값에 대한 Label이 없는 비지도학습(unsupervised learning)의 두번째 기법으로 '군집분석 (Cluster Analysis, Clustering)'에 대해서 소개하도록 하겠습니다.

 

1) 군집분석(cluster analysis)이란?

 

군집분석이란 데이터가 속해 있는 군집을 모르는 상태에서(Y값 label 없음) 유사한 혹은 동질의 데이터끼리 군집(cluster)로 묶어 주는 분석기법입니다.

 

 

 

 사자성어 중에 보면

 

"유유상종(類類相從)", "끼리 끼리 모인다"라는 말이 있는데요, 군집분석을 잘 나타내는 말 같습니다.

 

 

서양 속담에도 비슷한 것이 있습니다.

 

"Birds of a feather flock together"

 * 그림 출처 : http://www.winglish.com/free/asp/mrwin_default_com.asp?j_num=6

 

 

군집분석은 유의미하거나 유용한 데이터의 구조를 파악하여 활용(clustering for utility)하거나, 데이터의 구조를 이해(understanding)하는 목적으로 분석 초기 탐색적 분석 단계에서 아주 많이 활용하곤 합니다.  

 

군집분석은 마케팅, 심리학, 사회학, 통계, 패턴 인식, 기계학습, 데이터마이닝 등에 다방면에 사용됩니다. 마케팅, CRM에 종사하는 분들은 고객세분화(cutomer segmentation) 하는데 군집분석 & 프로파일링 (customer clustering & profiling) 에 대해서 들어보았거나 시도를 해봤을 것 같습니다.  

 

(1) 군집분석으로 고객세분화를 먼저 수행하고 (un-supervised learning) -> (2) Decision Tree를 사용해서 군집분석을 통해 만든 군집들을 분류(Classification, supervised learning)하는 모델을 만드는 semi-supervised learning approach를 취하는 것도 생각해 볼 수 있을 것입니다.

 

데이터가 X와 Y의 2차원으로만 구성되어 있다면 산점도(scatter plot)을 그려서 눈으로 확인해보는 것만으로도 데이터셋에 내재한 패턴, 군집 유무, 데이터 간 관계를 어림짐작할 수 있습니다.  3차원도 (좀 보기에 헷갈리기는 하지만) 3D plot을 그려서 눈으로 확인할 수 있습니다. 하지만 4차원 이상 넘어가면 사람 눈으로 군집 유무 여부를 확인, 판단하는게 어려워집니다. 이때 군집분석을 활용하면 좋겠지요?!  개별 나무를 몰라도 (데이터셋에 대한 사전지식이 없어도) 숲에 대한 조감도(군집)를 찾을 수 있다니 군집분석은 참 유용한 데이터 마이닝 (숨은 지식, 패턴 캐내기) 기법입니다.

 

 

 

2) 군집분석의 원리(Principal of custer analysis)는?

 

군집분석은 데이터가 어떤 군집에 속해있는지 알 수 있는 Y값 Label이 없는 상태에서 진행된다고 하였으므로 지도학습(supervised learning)처럼 명쾌한 모델성능평가가 쉽지가 않습니다.  군집을 몇 개로 하느냐에 따라서도 군집화가 영향을 많이 받기도 하는데요, 보통은 데이터 내 군집이 몇 개 있는지 모르는 경우가 많습니다.

 

그렇다면 군집분석에서 모델 생성, 평가는 무슨 기준으로 하는 것일까 하는 의문이 들 것입니다. 군집분석에서는 주로 응집도(cohesion)분리도(separation) 척도를 많이 사용하는 편인데요, 군집분석을 컴퓨터가 이해하도록 수식, 척도를 가지고 군집화의 원리를 나타내보면

 

      (1) 군집 內 응집도를 최대화하고, (maximizing cohesion within cluster,
                                                    i.e. minimizing sum of distance b/w x and y) 

  (2) 군집 間 분리도를 최대화하도록 (maximizing separation between clusters)

 

군집을 형성한다는 것입니다.

 

 

 

 

 

군집분석 알고리즘의 근간에는 최적화(optimization) 개념이 들어있음을 알 수 있습니다.

 

Graph-based clustering과 Prototype-base clustering 의 두 가지 approach별로 나누어서 응집도(cohesion)와 분리도(separation)의 개념을 수식과 시각화로 같이 나타내면 아래와 같습니다.

 

 

 (2-a) 그래프 기반 응집도와 분리도 (Graph-based view of cohesion and separation)

 

 

 

 

 (2-b) 프로토타입 기반 응집도와 분리도 (Prototype-base view of cohesion and separation)

 

아래에 군집의 중심(centroid)을 기준으로 군집 내 데이터와 중심 간 거리를 가지고 응집도를, 군집 중심 간의 거리를 가지고 분리도를 나타내보았습니다. 

 

 

 

 

3) 군집분석에에는 어떤 유형이 있나?  어떻게 구분할 수 있나?

 

 군집분석을 구분할 수 있는 기준이 여러개 있을 수 있는데요, 한 군집 안에 부분군집이 있느냐 없느냐에 따라서 계층적 군집(hierarchical clustering)분할적 군집(partitional clustering)으로 나눌 수 있습니다. 계층적 군집은 한 군집 안에 부분군집이 있는 반면, 분할적 군집은 군집간 부분집합이나 중복없이 상호 배타적으로(exclusive) 존재합니다. 아래 그림의 이미지를 참고하시면 이해하기 쉬울거예요.   

 

 

 

 

   (3-a) 계층적 군집분석 (Hierarchical Clustering)

 

계층적 군집분석은 (3-a-1) 개별 데이터에서 시작해서 유사한 데이터끼리 군집으로 차근차근 묶어가는 기법인 응집형 방법 (Aggolomerative, Bottom-up method)과, 응집형과는 반대로 (3-a-2) 모든 데이터를 하나의 군집에 속한다고 놓고, 차근차근 세부 군집으로 나누어가는 분리형 방법 (Divisive, Top-down method) 으로 구분할 수 있습니다.

 

 

일반적으로 군집 간 합치기와 분할은 greedy manner (각 단계별 국소 최적해를 찾아가는 휴리스틱 최적화 알고리즘) 에 의해서 결정이 됩니다. 일반적인 경우 응집형(agglomerative) 군집화의 복잡도(complexity)는 으로서 큰 규모의 데이터셋에 적용하기에는 시간이 너무 오래 걸려서 무리일 수 있습니다. 일부 특별한 경우로, 단일(최단) 연결(single-linkage (SLINK)), 완전(최장) 연결법(complete-linkage, CLINK)는 복잡도가 로서 최적의 효과적인 응집형 방법으로 알려져 있습니다. 모든 관측치를 상호배타적으로 탐색하는 경우의 분리형(divisive) 군집화는 복잡도가 으로서 아주 끔찍한 수준입니다. ^^; (from Wikipedia)

앞으로 연재할 때 복잡도가 어마무시 높은 분리형 군집화는 제외하도록 할께요.  

 

응집형(Agglomerative) 방법에는 군집간 거리 척도와 연결법에 따라서 단일(최단) 연결법 (Single Linkage Method), 완전(최장) 연결법 (Complete Linkage Method), 평균 연결법 (Average Linkage Method), 중심 연결법 (Centroid Linkage Method), Ward 연결법 (Ward Linkage Method)이 있습니다.

분리형(Divisive) 방법에는 DIANA 방법(DIANA algorithm)이 있습니다.

 

 

 

 

  (3-b) 분할적 군집분석 (Partitional Clustering, Non-Hierarchical clustering)

 

분할적 군집(Partitional clustering) 방법에는 거리 기반 군집화 (distance-based clustering), 밀도 기반 군집화(density-based clustering), 신경망 기반 군집화 (neural network-based clustering) 등이 있습니다.

 

(3-b-1) 프로토타입 기반(Prototype-based) 군집화 기법에는 K-중심 군집(K-centroid clustering), 퍼지 군집(Fuzzy clustering)

 

(3-b-2) 분포 기반(Distribution-based) 군집화에는 혼합분포 군집(Mixture distribution clustering)이 있습니다.

 

(3-b-3) 밀도 기반(Density-based) 군집화 기법에는 중심 밀도 군집(Center density clustering), 격자 기반 군집(Grid-based clustering), 커넬 기반 군집(Kernel-based clustering) 등이 있습니다.

 

(3-b-4) 그래프 기반(Graph-based) 군집화에는 코호넨 군집(Kohenen clustering) 이 있습니다.

 

 

 

보통 군집분석 공부한다고 하면 'K-means clustering' 알고리즘 공부하고 끝내는 경우가 있는데요 (좀더 공부한다면 계층적 군집화 일부...), 위에 제시한 것처럼 군집분석 기법/알고리즘이 상당히 많이 있습니다. 분석 기법이 많다보니 뭘 써야하나 혼란스러울 수 있는데요, 군집분석 알고리즘별로 데이터 특성과 구조, 분석 목적에 맞게 보다 적절한 알고리즘이 있습니다. 따라서 분석가는 각 알고리즘의 개념, 특성, 장점과 단점을 알고 있어야 하고, 분석 목적, 데이터 특성에 맞게 잘 선택해서 사용할 줄 알아야 하겠습니다.

 

위에서는 분석 기법 이름만 구조를 잡아서 나열을 했는데요, 앞으로 하나씩 차근차근 알고리즘 설명과 예시, 그리고 R script를 풀어보도록 하겠습니다.  

 

 

[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) Wikipedia

 

 

다음번 포스팅에서는 기초체력을 다지고 시작한다는 의미에서 군집분석에서 유사성(similarity), 비유사성(dis-similarity)의 척도에 대해서 알아보도록 하겠습니다.

 

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

 

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by R Friend R_Friend


티스토리 툴바