지난번 포스팅에서는 범주형 특성 데이터, 텍스트 문서의 거리를 측정하는 지표 중에서 


 - 자카드 거리 (Jaccard distance)


 - 코사인 거리 (Cosine distance)


에 대해서 알아보았습니다. 


이번 포스팅에서는 두 문자열의 거리(distance between two strings of characters), 비유사도(dissimilarity)를 측정하는데 사용하는 편집 거리(edit distance), 혹은 다른 이름으로 Levenshtein metric 에 대해서 알아보겠습니다. 


편집거리(edit distance)는 데이터 항목이 놓인 순서(order)가 중요한 문자열(strings of characters, 예: 주소, 전화번화, 이름 스펠링)이나 서열(sequence, 예 : 염색체 염기서열)의 (비)유사도를 측정하는데 유용하게 사용할 수 있습니다. 


편집거리 (edit distance, Levenshtein metric) 는 두 문자열에서 하나의 문자열을 다른 문자열과 똑같게 만들기 위해서 최소로 필요로 하는 편집 회수(문자 추가, 제거, 위치 변경)를 계산합니다. 


아래에 간단한 예를 들어서 설명해보겠습니다. 



[ 편집 거리 예시 (example of edit distance, Levenshtein Metric) ]




아래처럼 사람 이름을 입력한 두 개의 문자열이 있다고 가정해보겠습니다. 

  • 문자열 1 (character string 1): Shawn Henry
  • 문자열 2 (character string 2): Shan Hennyy


'문자열 2'를 편집해서 '문자열 1'로 변환할 때 필요한 최소한의 조치를 생각해보면, 


(편집 조치 1) '문자열 2'의 4번째 위치에 'w'를 추가 (insert a 'w')

(편집 조치 2) '문자열 2'의 8번째 위치에 'n'을 'r'로 교체 (replace an 'n' with a 'r')

(편집 조치 3) '문자열 2'의 10번째 위치에 있는 'y'를 삭제 (delete the last 'y')


와 같이 3번의 편집 조치가 필요합니다.  따라서 '문자열 1'과 '문자열 2'의 편집 거리는 3입니다. 



'문자열 1'을 편집해서 '문자열 2'로 변환할 때 필요한 최소한의 조치를 생각해보면, 


(편집 조치 1) '문자열 1'의 4번째 위치의 'w'를 삭제 (delete a 'w')

(편집 조치 2) '문자열 1'의 9번째 위치의 'r'을 'n'으로 교체 (replace a 'r' with an 'n')

(편집 조치 3) '문자열 1'의 11번째 위치에 'y'를 추가 (insert an 'y')


이므로, 이렇게 계산해도 역시 '문자열 1'과 '문자열 2'의 편집 거리는 3입니다. 





이제 R 의 stringdist package를 사용해서 편집 거리 (edit distance, Levenshtein metric)를 계산해보겠습니다. 


(1) stringdist 패키지 설치 및 불러오기



# installing and loading of stringdist package

install.packages("stringdist")

library(stringdist)

 




(2) 문자열 편집 거리(edit distance, Levenshtein metric) 계산: stringdist()


문자열 "shawn henry"와 "shan hennyy", "show hurry" 문자열 간의 편집거리를 각각 계산해보겠습니다. 



> # to compute string edit distances

> # default method is 'osa', which is Optimal string alignment, (restricted Damerau-Levenshtein distance)

> stringdist(c("shawn henry"), c("shan hennyy", "show hurry"))

[1] 3 4

 



"shawn henry"와 "show hurry"의 편집거리를 계산하기 위해, 'show hurry'를 'shawn henry'로 변환하기 위한 최소 편집 조치를 살펴보면


(편집 조치 1) 'o'를 'a'로 변경 =>  shaw hurry

(편집 조치 2) 'n'을 추가   => shawn hurry

(편집 조치 3) 'u'를 'e'로 변경 => shawn herry

(편집 조치 4) 'r'을 'n'으로 변경 => shawn henry  (끝)


이므로, 편집거리는 4가 됩니다. 




(3) 여러개의 문자열 간의 편집 거리 (edit distance) 계산 결과를 행렬로 만들기: stringdistmatrix()


R stringdist 패키지에 들어있는 간단한 예제를 인용해서 예를 들어보겠습니다. 



> # to compute a dist object of class dist

> # => can be used by clustering algorithms such as stats::hclust

> stringdistmatrix(c("foo","bar","boo","baz"))

  1 2 3

2 3    

3 1 2  

4 3 1 2

> str_dist_mat <- as.matrix(stringdistmatrix(c("foo","bar","boo","baz")))

> str_dist_mat

  1 2 3 4

1 0 3 1 3

2 3 0 2 1

3 1 2 0 2

4 3 1 2 0

 




(4) 가장 유사한 문자열의 위치 찾기: amatch()


stringdist 패키지에는 'hello' 문자열과 편집 거리(edit distance, Levenshtein metric)가 가장 짧은 문자열의 위치를 찾아주는 amatch() 함수가 있습니다.  아래 예처럼 maxDist=2 라고 설정하면 편집 거리가 2를 넘어서는 문자열은 무시하게 됩니다.  동일 최소 편집거리 문자열이 여러개 있으면 앞에 위치한 문자열의 위치를 제시해줍니다. 



> # Approximate string matching

> # amatch returns the position of the closest match of x in table

> # by default, the OSA algorithm is used 

> # : Optimal string aligment (restricted Damerau-Levenshtein distance)

> amatch(c("hello"),c("hillu","hala","hallo", "hi"),maxDist=2)

[1] 3

 


- 'hello' 문자열과 'hillu' 문자열 간 편집 거리는 2 ('i'를 'e'로 교체, 'u'를 'o'로 교체), 

- 'hello' 문자열과 'hala' 문자열 간의 편집 거리는 3 ('a'를 'e'로 교체, 'l' 추가, 'a'를 'o'로 교체, 단, maxDist=2 이므로 고려 대상에서 제외됨), 

- 'hello' 문자열과 'hallo' 문자열 간의 편집 거리는 1 ('a'를 'e'로 교체)


이므로 편집 거리가 가장 짧은 'hallo' 의 3 을 반환합니다. 



* reference: stringdist package manual ( https://cran.r-project.org/web/packages/stringdist/stringdist.pdf)



많은 도움이 되었기를 바랍니다. 


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



Posted by R Friend R_Friend

예전 포스팅에서는 연속형 변수들 간의 거리를 측정하는 Measure로서 맨하탄 거리, 유클리드 거리, 표준화 거리, 마할라노비스 거리 등에 대해서 소개하였습니다. 


이전 포스팅에서는 명목형 데이터를 원소로 가지는 두 집합 X, Y의 특징들 간의 공통 항목들의 비율 (교집합의 개수 / 합집합의 개수)을 가지고 두 집합 간 유사성을 측정하는 Jaccard Index 와 (1 -  Jaccard Index)로 두 집합 간 거리(비유사성)을 측정하는 Jaccard Distance에 대해서 알아보았습니다. 


이번 포스팅에서는 문서를 유사도를 기준으로 분류 혹은 그룹핑을 할 때 유용하게 사용할 수 있는 코사인 거리(Cosine Distance)에 대해서 소개하겠습니다. 


코사인 거리를 계산할 때는 먼저 문서(Document, Text)에 포함된 단어들을 단어별로 쪼갠 후에, 단어별로 개수를 세어 행렬로 만들어주는 전처리가 필요합니다. (대소문자 처리라든지, 일상적으로 쓰이는 별로 중요하지 않은 단어 처리라든지... 이게 좀 시간이 오래걸리고, 단어 DB랑 처리 노하우가 필요한 부분입니다)


이번 포스팅에서는 이런 전처리가 다 되어있다고 가정하고, 코사인 거리 (혹은 코사인 유사도)의 정의와 계산 방법, R로 자동계산하는 방법을 소개하는데 집중하겠습니다. 


아래의 '참고 1'에서와 같이 코사인 유사도(Cosine Similarity)는 두 개의 문서별 단어별 개수를 세어놓은 특징 벡터 X, Y 에 대해서 두 벡터의 곱(X*Y)을 두 벡터의 L2 norm (즉, 유클리드 거리) 의 곱으로 나눈 값입니다. 


그리고 코사인 거리(Cosine Distance)는 '1 - 코사인 유사도(Cosine Similarity)' 로 계산합니다. 

(유사도 측정 지표인 Jaccard Index 와 비유사도 측정 지표인 Jaccard Distance 와 유사합니다)



[ 참고 1 : 코사인 유사도 (Cosine Similarity) vs. 코사인 거리 (Cosine Distance) ]





위의 공식만 봐서는 쉽게 이해가 안갈 수도 있을 것 같은데요, 아주 간단한 예를 가지고 좀더 자세하게 설명해 보겠습니다. 


Document 1, Document 2, Document 3 라는 3개의 문서가 있다고 해보겠습니다. 

그리고 각 문서에 'Life', 'Love', 'Learn' 이라는 3개의 단어가 포함되어 있는 개수를 세어보았더니 다음과 같았습니다. 



[ Table 1 : 3개의 문서별 단어별 출현 회수 (number of presence by words in each documents) ]


                           Corpus 

 Text

Life

Love 

Learn 

 Document 1

 1

0

 Document 2

 4

7

 Document 3

 40

70 

30

(예 : Document 2에서는 'Life'라는 단어가 4번, 'Love'라는 단어가 7번, 'Learn'이라는 단어가 3번 출현함(포함됨))



위의 'Table 1'의 각 문서별 출현하는 단어별 회수를 특징 벡터로 하는 벡터를 가지고 'Document 1'과 'Document 2' 간의 코사인 거리(Cosine Distance)를 사용해서 각 문서 간 비유사도를 계산해보겠습니다. 



[ 참고 2 : 'Document 1'과 'Document 2' 간의 코사인 거리 (cosine distance b/w doc. 1 and doc. 2) ]





코사인 거리(Cosine Distance)를 계산할 때 사용하는 코사인 유사도(Cosine Similarity) 의 분자, 분모를 보면 유추할 수 있는데요, 두 특징 벡터의 각 차원이 동일한 배수로 차이가 나는 경우에는 코사인 거리는 '0'이 되고 코사인 유사도는 '1'이 됩니다. 


위의 'Table 1'의 예에서 'Document 2'와 'Document 3'의 각 단어 (Life, Love, Learn)별 출현 회수가 동일하게 '10배'씩 차이가 나고 있는데요, 바로 이런 경우를 말하는 것입니다. Document 23 가 Document 2보다 쪽수가 더 많고 두꺼워서 각 단어별 출현 빈도는 더 높을 지 몰라도 각 단어가 출현하는 비율은 좀더 얇은 Document 2나 더 두꺼운 Document 3가 동일(유사)하므로 두 문서는 유사한 특성을 가지고 있다고 코사인 거리는 판단하는 것입니다. 이처럼 단위에 상관없이 코사인 거리를 사용할 수 있으므로 꽤 편리하고 합리적입니다. 



[ 참고 3 : 'Document 2'과 'Document 3' 간의 코사인 거리 (cosine distance b/w doc. 2 and doc. 3]





이제부터는 R의 proxy package의 dist(x, method = "cosine") 함수를 사용해서 코사인 거리를 구하는 방법을 소개합니다



(1) proxy 패키지를 설치하고 불러오기



## installing and loading proxy package

install.packages("proxy")

library(proxy)

 




(2) 문서별 단어별 출현 회수를 특징 벡터로 가지는 행렬 (Term Document Matrix) 만들기


위에서 설명했던 3개 문서의 'Life', 'Love', 'Learn'의 3개 단어 예제를 그대로 사용합니다. 



> # making Term Document Matrix

> Doc_1 <- c(1, 0, 5)

> Doc_2 <- c(4, 7, 3)

> Doc_3 <- c(40, 70, 30)

> Doc_corpus <- rbind(Doc_1, Doc_2, Doc_3) # matrix

> colnames(Doc_corpus) <- c("Life", "Love", "Learn")

> Doc_corpus

      Life Love Learn

Doc_1    1    0     5

Doc_2    4    7     3

Doc_3   40   70    30

 




(3) proxy 패키지의 dist(x, method = "cosine") 함수로 코사인 거리 계산하고, as.matrix() 함수를 사용해서 코사인 거리 계산 결과를 행렬로 반환하기



> # calculating cosine distance between documents using proxy package

> cosine_dist_Doc_mat <- as.matrix(dist(Doc_corpus, method = "cosine"))

> cosine_dist_Doc_mat

          Doc_1     Doc_2     Doc_3

Doc_1 0.0000000 0.5668373 0.5668373

Doc_2 0.5668373 0.0000000 0.0000000

Doc_3 0.5668373 0.0000000 0.0000000

 





proxy package를 사용하지 않을 거면, 위의 '참고 1'의 공식을 사용하여 아래처럼 함수를 직접 짜서 코사인 거리를 계산할 수도 있습니다. 참고하세요. 



> # cosine distance function

> cosine_Dist <- function(x){

+   as.dist(1 - x%*%t(x)/(sqrt(rowSums(x^2) %*% t(rowSums(x^2))))) 

+ }

> cosine_Dist(Doc_corpus)

          Doc_1     Doc_2

Doc_2 0.5668373          

Doc_3 0.5668373 0.0000000

 



많은 도움이 되었기를 바랍니다. 


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


다음 포스팅에서는 문자열 편집거리(edit distance, Levenshtein metric)에 대해서 알아보겠습니다. 



Posted by R Friend R_Friend

연속형 변수에 대한 비유사성 측도(dissimilarity measure)로서 매우 다양한 측도가 있는데요, 예전 포스팅에서 맨하탄 거리(Manhattan distance), 유클리드 거리(Euclidean distance), 표준화 거리(Standardized distance), 마할라노비스 거리(Mahalanobis distance) 에 대해서 알아보았습니다. (=> http://rfriend.tistory.com/199 , http://rfriend.tistory.com/201)


이번 포스팅에서는 범주형 데이터에 대해서 비유사성을 측정하는 지표로 Jaccard distance 를 소개하겠습니다. 


Jaccard distance 는 비교 대상의 두 개의 객체를 특징들의 집합(sets of characteristics)으로 간주합니다. 기본 개념이나 표기법이 집합론(set theory)에 기반을 두고 있습니다. 


Jaccard Index는 유사성 측도이고, 1에서 Jaccard Index값을 뺀 Jaccard distance는 비유사성 측도입니다. 


특징들의 두 개의 집합 X, Y가 있다고 했을 때, Jaccard Index는 집합 X와 집합 Y의 교집합(Intersection)의 원소의 개수()를 집합 X와 집합 Y의 합집합(Union)의 원소의 개수()로 나눈 값입니다.   따라서 Jaccard Index는 0~1 사이의 값을 가집니다. 


참고로, 표기는 집합론에서는 원소의 개수를 나타낼 때 사용하는 표기법이며, 다 아시겠지만, 는 교집합, 는 합집합을 의미합니다. 

Jaccard Distance 는 1 에서 Jaccard Index를 뺀 값입니다. ()


만약 두 집합의 합집합과 교집합이 서로 비슷하다면 자카드 지수는 거의 1에 근접(즉, 매우 유사)할 것이구요, 자카드 거리는 거의 0에 근접(즉, 매우 거리가 가깝다는 뜻, 즉 유사)할 것입니다. 


자카드 거리는 "두 집합에 공통으로 공유되는 항목은 중요한 반면에, 두 집합에서 모두 존재하지 않는 항목에 대해서는 무시해도 되는 상황, 문제"에 적합한 비유사성 측도입니다. 비교 대상이 되는 두 집합의 합집합, 교집합에 해당되는 않는 항목(item)은 그냥 제껴버리고 무시해버립니다. 


그 동안 군집분석을 소개하면서 비유사성 측도로서 거리(Distance)를 사용해왔는데요, 여기서도 Jaccard Distance를 가지고 예를 들어서 소개하고, R 로 실습도 해보겠습니다.  



[그림 1] 자카드 지표 & 자카드 거리 (Jaccard Index & Jaccard Distance)





이해를 쉽게 하기 위해서 아주 간단한 예를 하나 들어보겠습니다. 


5개의 상자가 있는데요, 거기에는 빨강, 노랑, 파랑 색깔의 공이 들어있다고 해봅시다. 그리고 각 상자별로 들어있는 공의 색깔을 가지고 상자들 끼리의 비유사성을 Jaccard 거리로 재보도록 하겠습니다. 



 -. 상자 1 = {노랑}

 -. 상자 2 = {노랑}

 -. 상자 3 = {빨강, 노랑, 파랑}

 -. 상자 4 = {빨강, 노랑}

 -. 상자 5 = {파랑}

 



(1) '상자 1'과 '상자 2'의 합집합(union)의 개수는 |{노랑}| = 1 이구요, 교집합(intersection)의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 2) = 1 - (1/1) = 0 입니다. 


(2) '상자 1'과 '상자 3'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3 이구요, 교집합의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 3) = 1 - (1/3) = 약 0.667 입니다. 


(3) '상자 1'과 '상자 4'의 합집합의 개수는 |{빨강, 노랑}| = 2 이며, 교집합의 개수는 |{노랑}| =  1 이므로, 자카드 거리(상자 1, 상자 4) = 1 - (1/2) = 0.5 입니다. 


(4) '상자 1'과 '상자 5'의 합집합의 개수는 |{노랑, 파랑}| =  2 이며, 교집합의 개수는 |{NA}| = 0 이므로, 자카드 거리(상자 1, 상자 5) = 1 - (0/2) = 1 입니다. 


(5) '상자 3'과 '상자 4'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3 이구요, 교집합의 개수는 |{빨강, 노랑}| = 2 이므로, 자카드 거리(상자 3, 상자 4) = 1 - (2/3) = 약 0.333 입니다. 


(6) '상자 3'과 '상자 5'의 합집합의 개수는 |{빨강, 노랑, 파랑}| = 3, 교집합의 개수는 |{파랑}| =  1 이므로, 자카드 거리(상자 3, 상자 5) = 1 - (1/3) = 약 0.667 입니다. 


(7) '상자 4'와 '상자 5'의 합집합의 개수는 |{빨강, 노랑, 파랑}| =  3 이며, 교집합의 개수는 |{NA}| = 0 이므로, 자카드 거리(상자 4, 상자 5) = 1 - (0/3) = 1 입니다. 






이를 R의 proxy package를 사용해서 풀어보겠습니다. 


먼저 proxy package를 설치하고 불러오도록 합니다. 



#===========================================

# distance(dissimilarity) calculation using proxy package

#===========================================


> install.packages("proxy")

> library(proxy)

 




proxy package는 2017년 초에 CRAN에 등록이 된 따끈따근한 패키지인데요, 총 49개의 proximity 지표(similarity measures, distance measures) 가 들어있습니다. 



> # show available proximities

> pr_DB

An object of class "registry" with 49 entries.

> summary(pr_DB)

* Similarity measures:

Braun-Blanquet, Chi-squared, Cramer, Dice, Fager, Faith, Gower, Hamman, Jaccard,

Kulczynski1, Kulczynski2, Michael, Mountford, Mozley, Ochiai, Pearson, Phi, Phi-squared,

Russel, Simpson, Stiles, Tanimoto, Tschuprow, Yule, Yule2, correlation, cosine, eDice,

eJaccard, simple matching


* Distance measures:

Bhjattacharyya, Bray, Canberra, Chord, Euclidean, Geodesic, Hellinger, Kullback,

Levenshtein, Mahalanobis, Manhattan, Minkowski, Podani, Soergel, Wave, Whittaker,

divergence, fJaccard, supremum





proxy package의 Jaccard 클래스에 대해서 간략한 설명을 살펴보면 아래와 같습니다. binary 형태의 데이터에 대한 (비)유사성 척도라고 되어 있습니다.  그리고 (FALSE, FALSE) pairs 에 대해서는 고려하지 않고 무시하며, 비교 대상의 두 객체 집합의 합집합과 교집합을 비교한다고 되어 있습니다. 


> names(pr_DB)

 [1] "get_field"              "get_fields"             "get_field_names"       

 [4] "set_field"              "entry_exists"           "get_entry"             

 [7] "get_entries"            "get_entry_names"        "set_entry"             

[10] "modify_entry"           "delete_entry"           "n_of_entries"          

[13] "get_field_entries"      "get_permissions"        "restrict_permissions"  

[16] "seal_entries"           "get_sealed_entry_names" "get_sealed_field_names"


> pr_DB$get_entry("Jaccard")

      names Jaccard, binary, Reyssac, Roux

        FUN R_bjaccard

   distance FALSE

     PREFUN pr_Jaccard_prefun

    POSTFUN NA

    convert pr_simil2dist

       type binary

       loop FALSE

      C_FUN TRUE

    PACKAGE proxy

       abcd FALSE

    formula a / (a + b + c)

  reference Jaccard, P. (1908). Nouvelles recherches sur la distribution florale. Bull.

            Soc. Vaud. Sci. Nat., 44, pp. 223--270.

description The Jaccard Similarity (C implementation) for binary data. It is the proportion

            of (TRUE, TRUE) pairs, but not considering (FALSE, FALSE) pairs. So it compares

            the intersection with the union of object sets.

 




위의 상자 5개의 공 색깔 예제를 R로 실습해 보기 위해서 아래 처럼 5개의 행(row)은 상자를 나타내고, 3개의 열(column)은 색깔(순서대로 빨강, 노랑, 파랑)을 나타내는 걸로 하겠습니다. 그리고 각 상자별 빨강, 노랑, 파랑 색깔의 공이 있으면 ' 1(TRUE)'을 입력하고, 공이 없으면 '0(FALSE)'을 입력해서 행렬(matrix)을 만들어보겠습니다. proxy package가 타카드 거리를 계산할 수 있도록 binary 형태의 데이터셋을 만드는 것입니다. 



> # making binary dataset as a matrix

> x <- matrix(c(0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1), 

+             byrow = TRUE, 

+             ncol = 3)

> x

     [,1] [,2] [,3]

[1,]    0    1    0

[2,]    0    1    0

[3,]    1    1    1

[4,]    1    1    0

[5,]    0    0    1 





dist(x, method = "Jaccard") 함수를 사용해서 Jaccard distance를 계산해보겠습니다.  위의 예에서 손으로 푼 결과와 동일한 값들이 나왔습니다. 



> # Jaccard distance

> dist(x, method = "Jaccard")

          1         2         3         4

2 0.0000000                              

3 0.6666667 0.6666667                    

4 0.5000000 0.5000000 0.3333333          

5 1.0000000 1.0000000 0.6666667 1.0000000

 




아래처럼 cross Jaccard distances 를 계산하려면 dist(x, x, method = "Jaccard") 처럼 행렬 x 를 두번 입력해주면 됩니다. 



> # cross Jaccard distances

> dist(x, x, method = "Jaccard")

     [,1]      [,2]      [,3]      [,4]      [,5]     

[1,] 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

[2,] 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

[3,] 0.6666667 0.6666667 0.0000000 0.3333333 0.6666667

[4,] 0.5000000 0.5000000 0.3333333 0.0000000 1.0000000

[5,] 1.0000000 1.0000000 0.6666667 1.0000000 0.0000000

 




proxy package에 비해서는 조금 비효율적이기는 하지만 stats package 의 dist(x, method = "binary")함수를 사용해서도 Jaccard distance를 계산할 수 있습니다. 



> # using stats package (less efficient than proxy package)

> as.matrix(stats::dist(x, method = "binary"))

          1         2         3         4         5

1 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

2 0.0000000 0.0000000 0.6666667 0.5000000 1.0000000

3 0.6666667 0.6666667 0.0000000 0.3333333 0.6666667

4 0.5000000 0.5000000 0.3333333 0.0000000 1.0000000

5 1.0000000 1.0000000 0.6666667 1.0000000 0.0000000

 



많은 도움 되었기를 바랍니다. 

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


다음번 포스팅에서는 코사인 거리(Cosine Distance),  문자열 편집 거리(edit distance, Levenshtein metric)를 알아보겠습니다. 




Posted by R Friend R_Friend

지난번 포스팅에서는 분할적 군집화(Partitional Clustering) 중에서 프로토타입 기반(Prototype-based)의 군집화 기법인 K-중심 군집(K-Centroid Clustering)에 대해서 알아보았습니다.

 

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

 

퍼지 군집 (Fuzzy Clustering)은 혼합 분포 군집(Mixture Distribution Clustering)과 함께 "Soft Clustering"이라고도 하는데요, 각 관측치가 (단 하나의 군집에만 속하는 것이 아니라) 여러 군집에 속할 수 있으며, 이를 각 군집에 속할 가능성(possibility), 확률(probability)로 제시해줍니다.

(가령, 관측치 3번은 군집 1 속할 가능성이 0.7, 군집 2에 속할 가능성이 0.3)

 

 

[ Partitional Clustering > Prototype-based > Fuzzy Clustering ]

 

 

 

 

퍼지 군집에 대해 자세히 살펴보기 전에 먼저 퍼지 논리(Fuzzy Logic)에 대해서 간략히 살펴보겠습니다.

 

Fuzzy를 영어사전에서 찾아보면 '애매 모호함' 이라는 뜻입니다. 

 

(뜻이) (be) vague (idea), obscure, fuzzy, inexplicit, puzzling, ambiguous (meaning), hazy (notion), dim (memory), doubtful, evasive, equivocal, elusive

 

Fuzzy Set Theory, Fuzzy Logic은 '애매 모호한 대상을 다루는 논리'입니다. 

 

고전 논리 연산(Boolean Logic)에서는 1(참, Truth) 아니면 0(거짓, False), 모 아니면 도, 아군 아니면 적군으로 단순 명쾌하게 구분을 합니다.

 

반면에 Fuzzy 논리(Fuzzy Logic)에서는 진리값(Truth Value)이 0~1 사이의 실수값(real nummber between 0 and 1)으로 확장하여 소속도(degrees of membership)에 대한 애매모호한 정도, 가능성의 정도(degrees of possibility)를 표현합니다.

 

 

[ Boolean Logic vs. Fuzzy Logic ]

 

 

 

위의 '키(Height)'를 예를 들어보면요, 고전 논리(Boolean Logic)에서는 키 175 cm 를 기준으로 해서, 175cm 미만은 키가 작은 집단 ('0', short group), 175cm 이상은 '키가 큰 집단' ('1', tall group)으로 구분하고 있습니다.  따라서 고전 논리에 따르면 키 174.999cm인 사람은 '키가 작은 집단'('0', short group)에 속하게 되며, 키 175.001 cm인 사람 (키 174.999 cm인 사람보다 단지 0.002 cm 큼)은 '키가 큰 집단' ('1', tall group)에 속하게 됩니다. 0.002 cm 차이가 두 사람이 속하는 그룹을 나누었는데요, 뭔가 불합리하다는 생각이 들지요?

 

반면에, 퍼지 논리 (Fuzzy Logic)에서는 소속도(degrees of membership)의 가능성(Possibility)을 진리 값(Truth Value)이 0~1 사이의 연속된 실수값으로 확장해서 나타내준다고 했지요?! 위의 키 예를 살펴보면요, 174.999 cm 인 사람이 '키가 큰 집단'에 속할 가능성이 0.499 이고 & '키가 작은 집단'에 속할 가능성(possibilty)이 0.501 입니다.  키가 175.001 cm 인 사람이 '키가 큰 집단'에 속할 가능성이 0.501 이고 & '키가 작은 집단'에 속할 가능성은 0.499 입니다. 

 

키나 몸무게, 나이, 시력, 청력... 등 연속된 개념에 대해서는 아무래도 고전 논리(Boolean Logic)보다는 퍼지 논리(Fuzzy Logic)이 애매 모호함의 정도(degrees)를 나타내기에 더 적합해 보입니다.  사실, 인간이 사용하는 용어, 표현, 개념의 "상당 부분이 애매모호한것 같습니다" (<= 이 표현 자체가 바로 애매 모호함 그 자체이지요. "상당 부분"? "같습니다"?).  퍼지 논리, 퍼지 집합론(Fuzzy set theory)을 이용하면 컴퓨터가 인간이 생각하고 표현하는 애매 모호함을 인식하고 연산할 수 있습니다.  

 

 

군집분석으로 다시 돌아와서 생각해보면요, K-중심 군집(K-Centroid Clustering)에서는 각 관측치가 특정 군집에 속하거나('1') 혹은 아니거나('0')의 둘 중 하나였습니다(each data point can only belong to exactly one cluster)반면에, 퍼지 군집(Fuzzy Clustering)에서는 퍼지 이론(Fuzzy set theory)에 기반해서 각 관측치가 여러 군집에 동시에 속할 수 있으며(data points can potentially belong to multiple clusters), 각 군집별로 속할 가능성(degrees of possibility, probability)을 제시해줍니다.

 

 

[ Soft Clustering compared to Hard(Non-fuzzy) Clustering ]

 

 

 

관측치 중에서 각 군집과 군집의 중간 사이에 위치해서 특정 군집에 할당하기에 애매 모호한 관측치가 많이 있는 데이터셋이라면 '집단에 속할 가능성'을 나타내주는 퍼지 군집(Fuzzy Clustering)이 '단순 무식하게 여기 아니면 저기'로 배타적으로(exclusively) 나누어주는 K-중심군집(K-Centroid Clustering)보다 상대적으로 더 적합하다고 볼 수 있습니다.  (연산량이 많아지는 단점이 있긴 합니다만, 요즘엔 컴퓨팅 파워가 높으므로 예전 대비 문제가 덜 한편이죠)

 

 

개념에 대해 소개했으니, 이제 알고리즘으로 한단계 내려가 보겠습니다.

 

퍼지 군집 알고리즘으로 가장 많이 사용되는 것으로 Fuzzy C-means(FCM) Clustering Algorithm 입니다. FCM 알고리즘은 1973년 J.C.Dunn이 개발하였고, 1981년 J.C.Bezdek 이 발전시켰습니다. (* source : https://en.wikipedia.org/wiki/Fuzzy_clustering)  이번 포스팅에서는 Fuzzy C-means Clustering Algorithm을 가지고 설명하겠습니다.

 

Fuzzy C-means Clustering Algorithm은 K-means Algorithm 과 매우 유사합니다.  군집 내 관측치들 간의 유사성을 최대화하고 (즉, 군집의 중심과 관측치 간 거리의 합을 최소화), 군집 간 비유사성을 최대화 (즉, 군집의 중심 간 거리의 합을 최대화) 하는 최적 해(optimal solution)를 반복적인 연산을 통해 찾는 개념은 똑같습니다.  K 개의 군집을 분석가가 사전적으로 지정해주는 것도 같습니다.  유사성의 측도로서 거리(distance)를 사용하는 것도 같습니다 (정확히는 비유사성(dis-similarity)의 측도).

 

다만, 퍼지 군집에서는 각 관측치가 특정 군집에 속할 가능성, 가중치 w 를 계산하는 것이 다를 뿐입니다. (아래에는 군집 개수를 K로 통일해서 Fuzzy K-means Clustering 으로 사용하겠음)

 

 

[ Fuzzy K-means Clustering Algorithm ]

 

 

1. Choose a number of clusters, K.

2. Assign randomly to each point coefficients for being in the clusters.

3. Repeat

  - Compute the centroid for each cluster.
  - For each point, compute its coefficients of

  being in the clusters.

 

4. until

  the algorithm has converged

  (that is, the coefficients' change between

  two iterations is no more than the given

  sensitivity threshold)
 

 

1. 군집의 개수 K를 선택함

 

2. 각 관측치가 특정 군집에 속할 가중치
  (가능성) 값을 무작위로 할당함

 

3. Repeat

 - 각 군집의 중심을 계산함

 - 각 관측치에 대해 특정 군집에 속할
  가중치(가능성) 값을 다시 계산함

 

4. until

 알고리즘이 수렴할 때까지 반복함

 (즉, 3번의 2개 반복에서 더이상 가중치 값의
 변화가 주어진 민감도 기준치 미만일 때)

 

 

 

 

위의 알고리즘 내용을 수식으로 표현하기 전에 표기법부터 정리해보죠. 군집화를 하려고 하는 데이터셋 집합이 m개의 변수, n개의 관측치, K개의 군집이 있고, 각 군집에 속할 가능성을 가중치 값 w 로 표기한다고 하면 아래와 같습니다.  

 

[ 표기법 (Notation) ]

 

 

 

퍼지 군집 모형은 아래 두 개의 분할 조건을 만족합니다.

 

1) 데이터 가 각 군집 에 속할 가능성의 가중값 합은 1이다. (즉, 확률 합이 1)

  

    ---- (식 1)

 

2) 각 군집 는 하나 이상의 데이터가 0이 아닌 가중값을 가지며, 그 군집의 모든 가중값이 1이 될 수는 없다. (모두 0이거나 모두 1이면 군집분석 효용성 없음)

 

   ---- (식 2)

 

 

 

퍼지 군집을 하는 원리가 '군집 내 유사성 최대화 (즉, 관측치와 퍼지 군집 중심과의 거리 합 최소화)', '군집 간 비유사성 최대화 (즉, 군집의 중심 간 거리 합 최대화)' 하는 것이라고 했습니다 (K-means clustering 과 원리 동일). 

 

'군집 내 유사성 최대화 (즉, 관측치와 퍼지 군집 중심과의 거리[d(xi, ck)] 합 최소화)'를 달리 표현하면 '퍼지 군집 내 오차 제곱 합(SSE : Sum of Squared Error) 최소화'라고 할 수 있습니다.

 

  ---- (식 3)

 

위의 식에서 p는 1보다 큰 상수로서, 가중값의 정도를 조절하는 매개변수(parameter) 입니다. p 값이 1이면 K-means Clustering과 결과가 비슷해집니다. (K-means Clustering을 Fuzzy Clustering의 특수한 경우이며,  Fuzzy Clustering이 더 포괄적이라고 생각할 수 있습니다.)

 

위의 (식 3)에서 SSE를 최소로 하는 각 군집의 평균 를 구하기 위해서 (식 3)을 에 대해 편미분(partial derivative with respect to ) 한 후 '0'으로 놓고 연립방정식을 풀면 아래와 같은 해를 얻습니다.  (K-means clustering 에서 각 군집의 중심 평균을 구할 때는 해당 군집의 관측치 값만 사용하는데 반해서, Fuzzy K-means Clustering 에서는 전체 관측치에다가 각 군집에 속할 가능성인 가중치를 곱한 값을 사용함)

 

   ---- (식 4)

 

 

 

 

위의 (식 3)에서 SSE를 최소로 하는 가중값 를 구하기 위해서 (식 3)을 에 대해 편미분(partial derivative with respect to ) 한 후 '0'으로 놓고 연립방정식을 풀면 아래와 같은 해를 얻게 됩니다.

 

     ---- (식 5)

 

 

 

p 값이 커지면 커질수록 각 군집의 평균이 전체 평균에 가까워져서 한 군집으로 데이터를 분류하는 것이 점점 더 모호(fuzzier)해집니다. 일반적으로 위의 (식 5)의 가중값 의 재계산식을 간편히 하기 위해 p=2를 많이 사용합니다.

 

p=2 를 (식 5)에 대입하면 (식 5)가 아래와 같이 계산하기 용이하게 정리됩니다.

 

       ---- (식 6)

 

 

위의 (식 6)의 분자를 살펴보면, 관측치 가 군집 에 속할 가능성, 가중치 는 관측치 와 군집의 중심 의 거리(distance) 제곱에 반비례함을 알 수 있습니다. 즉 관측치와 군집의 중심 간 거리가 짧을 수록 (즉, 유사할 수록, 그 군집에 속할 가능성이 높을 수록) 는 커지게 됩니다. 

(* 출처 : 이정진)

 

이때 분모는 각 데이터와 군집 1 ~ K 까지의 거리 제곱의 역수의 합이며, 이것으로 분자(특정 군집 K와 관측치 간의 거리 제곱의 역수)를 나누어주게 되면 여러 군집에 속하는 가중값의 합이 1이 되도록 해주는 표준화 상수 역할을 하게 됩니다.

 


 

간단한 예제를 가지고 Fuzzy K-means Clustering을 반복 수행해보겠습니다. 

 

n = 4 (관측치 4개),

m = 2 (변수 2개),

K = 2 (군집 2개),

p = 2 (가중치 계산 상수 parameter),

군집 중심과 관측치간의 거리는 유클리드 제곱 거리(Squared euclidean distance) 인

 

간단한 예제이며, 엑셀로 수식 걸어서 반복 수행하였습니다. (아래 첨부한 엑셀 파일 참조하세용~)

Fuzzy_Clustering_example.xlsx

 

 

[ 데이터셋 ]

data x1 x2
obs 1 -1 -2
obs 2 -2 -1
obs 3 1 3
obs 4 3 2

[ x1, x2 축 기준 관측치 산점도 ]

 

 

무작위로 obs 2, obs 4에 군집 1 가중값(wi1)으로 0.8, 군집 2 가중값(wi2)으로 0.2를 할당하고, obs 1, obs 3에는 군집 1 가중값(wi1)으로 0.2, 군집 2 가중값(wi2)으로 0.8을 할당하였습니다. (각 관측치의 모든 군집이 가중값 합의 1이 되어야 하므로 군집 1 가중값이 정해지면 나머지 군집 2의 가중값은 1-wi1 으로 자동으로 정해짐)

 

관측치가 군집 에 속할 가능성인 가중값  는 (식 6)에 의해서, 군집 의 중심  는 (식 4)에 의해서 구했습니다.

 

 

1st iteration

data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)
^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.2

-0.04

-0.08

0.12

0.8

-0.64

-1.28

0.14

obs 2

0.8

-1.28

-0.64

0.12

0.2

-0.08

-0.04

0.16

obs 3

0.2

0.04

0.12

0.15

0.8

0.64

1.92

0.14

obs 4

0.8

1.92

1.28

0.12

0.2

0.12

0.08

0.09

new centroid
(new mean)

 

0.47

0.50

 

 

0.03

0.50

 

 

 

가중값 가 수렴할 때까지 위 계산을 반복을 합니다.

(위의 표 'Fuzzy K-means Clustering Algorithm' 참조)

 

 

2nd iteration

data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)
^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.46

-0.22

-0.43

0.09

0.54

-0.29

-0.57

0.18

obs 2

0.43

-0.37

-0.19

0.10

0.57

-0.64

-0.32

0.21

obs 3

0.52

0.27

0.82

0.21

0.48

0.23

0.68

0.11

obs 4

0.56

0.95

0.63

0.14

0.44

0.58

0.38

0.08

new centroid
(new mean)

 

0.63

0.84

 

 

-0.12

0.16

 

 

 

3rd iteration
data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)
^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.34

-0.11

-0.23

0.05

0.66

-0.44

-0.88

0.55

obs 2

0.32

-0.21

-0.10

0.06

0.68

-0.92

-0.46

0.63

obs 3

0.66

0.44

1.31

0.56

0.34

0.12

0.35

0.06

obs 4

0.65

1.28

0.86

0.33

0.35

0.36

0.24

0.05

new centroid
(new mean)

 

1.30

1.70

 

 

-0.78

-0.66

 

 

 

4th iteration
data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.09

-0.01

-0.02

0.03

0.91

-0.83

-1.66

1.94

obs 2

0.08

-0.01

-0.01

0.04

0.92

-1.69

-0.84

2.02

obs 3

0.90

0.82

2.45

0.86

0.10

0.01

0.03

0.04

obs 4

0.88

2.31

1.54

0.74

0.12

0.05

0.03

0.05

new centroid
(new mean)

 

1.94

2.48

 

 

-1.45

-1.44

 

 

 

5th iteration
data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.02

0.00

0.00

0.03

0.98

-0.96

-1.93

2.00

obs 2

0.02

0.00

0.00

0.04

0.98

-1.93

-0.97

2.00

obs 3

0.96

0.92

2.75

0.83

0.04

0.00

0.01

0.04

obs 4

0.94

2.65

1.77

0.77

0.06

0.01

0.01

0.05

new centroid
(new mean)

 

1.98

2.51

 

 

-1.49

-1.49

 

 

 

6th iteration

data

cluster 1

cluster 2

weight
wi1

wi1^2*xi
(x1, x2)

1/d(xi, c1)^2

weight
wi2

wi2^2*xi
(x1, x2)

1/d(xi, c2)
^2

obs 1

0.02

0.00

0.00

0.03

0.98

-0.97

-1.93

2.00

obs 2

0.02

0.00

0.00

0.04

0.98

-1.93

-0.97

2.00

obs 3

0.96

0.91

2.74

0.82

0.04

0.00

0.01

0.04

obs 4

0.94

2.67

1.78

0.78

0.06

0.01

0.01

0.05

new centroid
(new mean)

 

1.98

2.51

 

 

-1.49

-1.49

 

 

 

5번째 반복과 6번째 반복의 가중값의 변화가 거의 없으므로 (즉, 수렴하였으므로) 퍼지 군집 알고리즘을 종료합니다.

 

결과적으로 obs 1 과 obs 2 는 군집 2 (cluster 2)에 속하고, obs 3 과 obs4 는 군집 1로 분류가 되었습니다.

(obs 1의 w11 = 0.02, w12 = 0.98,

 obs 2의 w21 = 0.02, w22 = 0.98,

 obs 3의 w31 = 0.96, w32 = 0.04,

 obs 4이 w41 = 0.94, w42 = 0.06  이므로)

 

위에 제시한 예제의 산점도를 보면 obs 1과 obs 2가 서로 인접해 있으며, obs 3과 obs 4가 서로 인접해 있으므로 군집화가 제대로 된 셈이네요. 

 

비록 처음에 무작위로 가중값을 부여했을 때 obs 1과 obs 3을 군집2로 가중치를 0.8 할당, obs 2와 obs 4를 군집1로 가중치를 0.8 할당하였습니다만, 6차례의 반복을 거치면서 각 관측치별 가중치도 새로 계산하고, 군집 1과 군집 2의 중심(K-평균)도 새로 계산하면서 군집화(clustering)을 반복하다보니 인접한(유사한) 관측치끼리 군집으로 잘 묶였습니다.

 

처음에 가중값 부여할 때 무작위로 한다고 했는데요, 여기서 무작위로 부여하는 숫자가 바뀌면 (무작위 이므로 뭐가 될지 모름 -_-;) 물론 군집화의 결과가 바뀔 수 있다는 점은 알고 계시구요. (K-means clustering 도 초기 중심값이 무작위로 할당되다보니 분석 돌릴 때마다 군집화 결과가 바뀔 수 있다는 건 동일함)

 

아래에 R 예제에서는 초기 rational starting point를 행렬로 입력할 수 있는 기능이 있으므로, 관측값별 초기 가중값을 합리적으로 부여할 수 있는 상황이라면 이용할 만 하겠습니다.

 

 


 

R의 'fclust' Package를 가지고 위에서 소개했던 예제에 대해서 Fuzzy clustering을 수행해보겠습니다.

 

1) 먼저, fclust Package 를 설치하고 로딩해보겠습니다.

 

> ##---------------------------------------------
> ## Fuzzy K-means Clustering : R fclust Package
> ##---------------------------------------------
> install.packages("fclust")
trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.3/fclust_1.1.2.zip'
Content type 'application/zip' length 197520 bytes (192 KB)
downloaded 192 KB

package ‘fclust’ successfully unpacked and MD5 sums checked

The downloaded binary packages are in
	C:\Users\Administrator\AppData\Local\Temp\RtmpkzHe81\downloaded_packages
> library(fclust)

 

 

 

 

2) Dataset 준비

 

  위의 이론 설명에서 사용했던 2개 변수(x1, x2), 4개 관측치 예제 데이터를 똑같이 사용하겠습니다.

 

> # dataset
> x1 <- c(-1, -2, 1, 3)
> x2 <- c(-2, -1, 3, 2)
> x1_x2_d.f <- data.frame(x1, x2)
> x1_x2_d.f
  x1 x2
1 -1 -2
2 -2 -1
3  1  3
4  3  2

 

 

 

 

3) rational starting point Matrix U

 

위의 이론 설명에서 사용했던 값을 그대로 사용해서요, 관측값 1번이 군집1에 속할 가중값은 0.2, 군집2에 속할 가중값은 0.8, ... , 관측값 4번이 군집1에 속할 가중값이 0.8, 군집2에 속할 가중값은 0.2 의 초기값을 행렬(Matrix)로 만들었습니다.  이걸 아래의 FKM() 함수의 startU 옵션의 할당값으로 지정해줄겁니다.

 

> # rational starting point Maxtix U
> rational_starting_point <- matrix(c(0.2, 0.8, 0.2, 0.8, 0.8, 0.2, 0.8, 0.2), 
+                                   nrow = 4, ncol = 2, byrow = F)
> rational_starting_point
     [,1] [,2]
[1,]  0.2  0.8
[2,]  0.8  0.2
[3,]  0.2  0.8
[4,]  0.8  0.2

 

 

 

 

4) Fuzzy K-means Clustering using FKM() function of fclust package

 

fclust Package이 FKM() 함수의 매개변수 및 옵션에 대해서 소개하자면 아래와 같으며, 데이터셋(행렬 또는 데이터 프레임) 할당해주는 X, 군집의 개수를 지정해주는 k, 퍼지 매개변수(parameter) m (위의 '식 5'번의 p) 에 대해서만 옵션을 설정해보겠으며, 나머지는 default 설정 그대로 사용하겠습니다.

(같은 척도의 데이터이므로 표준화 필요 없음. default 가 no standardization)

 

 Arguments

 Description

 X

 Matrix or data.frame 

 k

 Number of clusters (default: 2)

 m

 Parameter of fuzziness (default: 2) 

 (위 이론 부분의 '식 5'번의 p 이며, p=2 이면 '식 6'번처럼 계산이 간단해짐)

 RS

 Number of (random) starts (default: 1)

 stand

 Standardization: if stand=1, the clustering algorithm is run using standardized data (default: no standardization) 

 startU

 Rational starting point for the membership degree matrix U

 (default: no rational start) 

 conv

 Convergence criterion (default: 1e-9) 

 maxit

 Maximum number of iterations (default: 1e+6) 

( * source : Paolo Giordani, Maria Brigida Ferraro)

 

 

퍼지군집 분석 결과는 아래와 같습니다.

 

> # Fuzzy K-means clustering with FKM() fuctnion of fclust package > x1_x2_FKM <- FKM(X = x1_x2_d.f, # Matrix or data.frame + k = 2, # Number of clusters (default: 2) + m = 2, # Parameter of fuzziness (default: 2) + startU = rational_starting_point)
> # startU : Rational starting point for the membership degree matrix U
>
>


>
# Fuzzy K-means clustering results > x1_x2_FKM Fuzzy clustering object of class 'fclust' Number of objects: 4 Number of clusters: 2 Closest hard clustering partition: 1 2 3 4 2 2 1 1 Membership degree matrix (rounded): Clus 1 Clus 2 1 0.02 0.98 2 0.02 0.98 3 0.95 0.05 4 0.96 0.04 Available components: [1] "U" "H" "clus" "value" "cput" "iter" "k" "m" "stand" "Xca" [11] "X" "call"

 

 

 

 

 

R의 fclust Package 의 FKM() 함수로 퍼지 군집화를 한 결과와, 위에서 엑셀을 가지고 6번 반복해서 푼 결과가 일치함을 알 수 있습니다. (obs3, obs4의 degree of membership, ie, weight 가 소숫점 두째자리에서 약간 다르기는 하지만 무시할만 합니다. 엑셀로는 반복을 6번하고 멈추었는데요, R은 14번 반복을 했네요.  이는 R fclust Package의 수렴 기준(Convergence criterion)의 default 값이 '1e-9' 으로서 매우 매우 작기 때문에 반복을 좀더 많이 했습니다.

 

> x1_x2_FKM$iter # number of iteration Start 1 14

 

 

 

fclust Package FKM() 함수의 분석결과 객체에 대해 소개하자면 아래와 같으며, 필요한 정보는 indexing 해서 사용하면 유용합니다.

 

fclust Package

FKM() object value 

Description 

 U

 Membership degree matrix

 H

 Prototype matrix

 clus

 Matrix containing the indices of the clusters

 where the objects are assigned (column1) and

 the associated membership degrees (column 2)

 value

 Vector containing the loss function values for the RS starts 

 cput

 Vector containing the computational times (user times) for the RS starts 

 iter

 Vector containing the numbers of iterations for the RS starts 

 k

 Number of clusters (군집의 수)

 m

 Parameter of fuzziness (위 식5번의 p와 동일)

 stand

 Standardization (Yes if stand=1, No if stand=0) 

 Xca

 Data used in the clustering algorithm (standardized data if stand=1)

 X

 Raw data

 call  Matched call (함수 다시 호출하기)

( * source : Paolo Giordani, Maria Brigida Ferraro)

 

 

예를 들어, 소속 정도의 가중값을 알고 싶다면 'U' 객체를 indexing 해오면 됩니다.

 

> # Membership degree matrix
> x1_x2_FKM$U
      Clus 1     Clus 2
1 0.01684418 0.98315582
2 0.01734390 0.98265610
3 0.95397165 0.04602835
4 0.96353078 0.03646922

 

 

 

 

각 퍼지 군집의 중심 위치도 궁금하지요?  이때 쓰는게 'H' 객체입니다.  Cluster 1 은 x1 중심좌표가 '2.008850', x2 중심좌표가 '2.493750' 으로서 우상단에 위치하고 있으며, Cluster 2는 x1 중심좌표가 '-1.493918', x2 중심좌표는 '-1.492924' 로서 좌하단에 위치하고 있군요.

 

> # Prototype matrix : H
> x1_x2_FKM$H
              x1        x2
Clus 1  2.008850  2.493750
Clus 2 -1.493918 -1.492924

 

 

 

 

변수가 2개인 2차원 데이터이므로 산점도 그래프로 그려보면 좀더 명확하게 이해할 수 있겠네요.  아래의 그래프를 보면 2개의 군집별로 색깔이 다르게 나와있구요, '*' 표시는 각 군집의 중심을 의미합니다. 바로 위해서 x1_x2_FKM$H 로 indexing했던 바로 그 좌표값입니다.

 

> # Fuzzy K-means Clustering plot
> plot(x1_x2_FKM)

 

 

 

이상으로 퍼지 군집(Fuzzy K-means Clustering Algorithm)에 대한 소개를 마치겠습니다.

 

 

다음번 포스팅에서는 '혼합분포군집(Mixture Distribution Clustering)' 모형에 대해서 알아보겠습니다.

 

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

 

[Reference]

- Michael Negnevitsky, "인공지능 개론(Artificial Intelligence)' (2nd Edition), 한빛아카데미, 2013

- 이정진, "R, SAS, MS-SQL을 활용한 데이터마이닝", 자유아카데미, 2011

- Fuzzy C-means Clustering Algorithm : https://en.wikipedia.org/wiki/Fuzzy_clustering

- R fuzzy clusterin package 'fclust' : Paolo Giordani, Maria Brigida Ferraro,  https://cran.r-project.org/web/packages/fclust/fclust.pdf

 

 

Posted by R Friend R_Friend

지난번 포스팅에서는 (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

   

 

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)에 대해서 알아보도록 하겠습니다.

 

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

 

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)에 대해서 알아보도록 하겠습니다.

 

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

 

 

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)에 대해서 알아보도록 하겠습니다.

 

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

 

 

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)에 대해서 알아보도록 하겠습니다.

 

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

 

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)에 대해서 알아보도록 하겠습니다.

 

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

 

 


Posted by R Friend R_Friend