R, Python 분석과 프로그래밍의 친구 (by 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 ]

위의 알고리즘 내용을 수식으로 표현하기 전에 표기법부터 정리해보죠. 군집화를 하려고 하는 데이터셋 집합이 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

[ 데이터셋 ]

[ 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)에 의해서 구했습니다.

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

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

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)

( * 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 해서 사용하면 유용합니다.

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

응집형 계층적 군집화(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로 계산한 결과가 서로 다르게 나왔습니다. 어디서 차이가 생기는 건지 파악을 못했습니다.  혹시 이 블로그를 보시고 제가 잘못 계산한 부분을 찾으셨다면 댓글로 알려주시면 감사하겠습니다. ㅜ_ㅜ)

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

유클리드 제곱거리를 구하는 R script 입니다. dist(xy, method="euclidean") 에다가 뒤에 "^2"를 붙여서 제곱을 했습니다.

> # proximity matrix : squares of euclidean distance matrix for 6 points
> dist(xy, method = "euclidean")^2
   1  2  3  4
2  1         
3 10  9      
4 13  8  5   
5 25 18  9  2

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

3) 군집(P1, P2)의 중심 구하기

[centroid coordinate of clusters - no.1]

아래의 부분집합그림에 보면 군집 (P1, P2) 의 중심(centroid) 위치에 노란색 별이 추가되었습니다.

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

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

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

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

> ##--------------------------------------------
> ## (1) Agglomerative Hierarchical Clustering 
> ##   (b) Prototype-based
> ##    (1-4) Centroid Linkage
> ##--------------------------------------------
> 
> x <- c(1, 2, 2, 4, 5)
> y <- c(1, 1, 4, 3, 4)
> 
> xy <- data.frame(cbind(x, y))
> 
> xy
  x y
1 1 1
2 2 1
3 2 4
4 4 3
5 5 4
> 
> # scatter plot of xy
> plot(xy, pch = 19, xlab = c("x coordinate"), ylab = c("y coordinate"), 
+      xlim = c(0, 6), ylim = c(0, 6), 
+      main = "scatter plot of xy")
> 
> # adding student label
> text(xy[,1], xy[,2], labels = abbreviate(rownames(xy)), 
+      cex = 0.8, pos = 1, col = "blue") # pos=1 : at the bottom
> 
> 
> # adding dotted line
> abline(v=c(3), col = "gray", lty = 2) # vertical line
> abline(h=c(3), col = "gray", lty = 2) # horizontal line

> # proximity matrix : squares of euclidean distance matrix for 6 points
> dist(xy, method = "euclidean")^2
   1  2  3  4
2  1         
3 10  9      
4 13  8  5   
5 25 18  9  2

> # Agglomerative Hierarchical Clustering : Centroid Linkage method
> hc_cent <- hclust(dist(xy)^2, method="centroid")
> hc_cent

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

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

> # dendrogram
> my_par = par(no.readonly = TRUE)
> par(oma = c(0, 0, 1, 0))
> par(mfrow = c(1, 2))
> plot(hc_cent)
> plot(hc_cent, hang = -1) # hang = -1 : line from the bottom

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

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

$method
[1] "centroid"

$labels
NULL

$order
[1] 1 2 3 4 5

$height
[1]  1.00000  2.00000  6.50000 11.80556

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

> # comparison of height among linkage methods
> hc_sl <- hclust(dist(xy)^2, method="single")
> hc_cl <- hclust(dist(xy)^2, method="complete")
> hc_avg <- hclust(dist(xy)^2, method="average")
> hc_cent <- hclust(dist(xy)^2, method="centroid")
> 
> # dendrogram
> my_par = par(no.readonly = TRUE)
> par(oma = c(0, 0, 1, 0))
> par(mfrow = c(1, 4))
> plot(hc_sl, main = "Single Linkage")
> plot(hc_cl, main = "Complete Linkage")
> plot(hc_avg, main = "Average Linkage")
> plot(hc_cent, main = "Centroid Linkage")

군집 간 거리를 측정하는 방법에 따라서 여러가지 알고리즘이 있는데요, 지난번 포스팅에서는 응집형 계층적 군집화(agglomerative hierarchical clustering) 알고리즘 중에서 (1-1) 단일(최단) 연결법 (single linkage method, MIN) 에 대해 소개하였습니다.

이번 포스팅에서는 응집형 계층적 군집화 알고리즘 중에서 그래프 기반(Graph-based) 방법의 두번째로 (1-2) 완전(최장) 연결법 (complete linkage method, MAX)에 대해서 알아보겠습니다.

단일(최단) 연결법이 군집 간 거리를 잴 때 다른 군집의 점들 중에서 가장 가까운 두 점 간의 거리를 사용하였다면, 완전(최장) 연결법은 반대로 '다른 군집의 점들 중에서 가장 멀리 떨어진 두 점 간의 거리를 가지고 군집 간 거리를 잽니다. 

아래의 가운데 그림은 군집 k와 군집 i+j (← 군집 i와 군집 j가 합쳐진 새로운 군집) 간의 거리를 완전(최장) 연결법으로 구할 때의 이미지인데요, 보시면 금방 이해할 수 있을 것입니다.

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

> # proximity matrix : squares of euclidean distance matrix for 6 points
> dist(xy, method = "euclidean")^2
   1  2  3  4
2  1         
3 10  9      
4 13  8  5   
5 25 18  9  2

> # Agglomerative Hierarchical Clustering : 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> ##--------------------------------------------
> ## (1) Agglomerative Hierarchical Clustering 
> ##    (1-1) Single Linkage, MIN
> ##--------------------------------------------
> 
> x <- c(1, 2, 2, 4, 5)
> y <- c(1, 1, 4, 3, 4)
> 
> xy <- data.frame(cbind(x, y))
> 
> xy
  x y
1 1 1
2 2 1
3 2 4
4 4 3
5 5 4
> 
> # scatter plot of xy
> plot(xy, pch = 19, xlab = c("x coordinate"), ylab = c("y coordinate"), 
+      xlim = c(0, 6), ylim = c(0, 6), 
+      main = "scatter plot of xy")
> 
> # adding student label
> text(xy[,1], xy[,2], labels = abbreviate(rownames(xy)), 
+      cex = 0.8, pos = 1, col = "blue") # pos=1 : at the bottom
> 
> 
> # adding dotted line
> abline(v=c(3), col = "gray", lty = 2) # vertical line
> abline(h=c(3), col = "gray", lty = 2) # horizontal line

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

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

[distance matrix - no.1]

유클리드 제곱거리를 구하는 R script 입니다. dist(xy, method="euclidean") 에다가 뒤에 "^2"를 붙여서 제곱을 했습니다.(이해, 설명 편의를 위해...) 

> # proximity matrix : squares of euclidean distance matrix for 6 points
> dist(xy, method = "euclidean")^2
   1  2  3  4
2  1         
3 10  9      
4 13  8  5   
5 25 18  9  2

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

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

한개만 예를 들자면, 군집 (P1, P2)와 개체 P5 간의 거리는 d(P1, P5)=25, d(P2, P5)=18 의 두 거리 중에서 최소값(MIN)인 '18'이 됩니다.  아래 거리행렬의 d(P3, P4), d(P3, P5), d(P4, P5)는 위의 거리행렬 [distance matrix - no.1]에서 계산한 결과를 그대로 가져다가 썼습니다.

[distance matrix - no.2]

• P4과 P5의 거리가 '2'로서 가장 가깝군요. 
  → (P4, P5)를 새로운 군집으로 묶어줍니다(merge). 이제 군집이 처음 5개에서 3개로 줄었습니다.

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

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

[distance matrix - no.3]

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

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

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

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

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

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

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

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

아래 덴드로그램의 y축이 바로 군집 간 거리 (단일(최소) 연결법으로 구한) 를 나타냅니다.

plot(x, hang = -1) 옵션을 설정하면 아래 그램의 오른쪽 덴드로그램처럼 군집 묶어주는 선이 y=0 부터 시작합니다.

> # dendrogram
> my_par = par(no.readonly = TRUE)
> par(oma = c(0, 0, 1, 0))
> par(mfrow = c(1, 2))
> plot(hc_sl)
> plot(hc_sl, hang = -1) # hang = -1 : line from the bottom

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

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

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

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

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

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

$method
[1] "single"

$labels
NULL

$order
[1] 1 2 3 4 5

$height
[1] 1 2 5 8

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

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

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

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

지난번 포스팅에서는 군집분석(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).

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

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

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)를 사용합니다.

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

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

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

 * 그림 출처 : 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) 군집분석에에는 어떤 유형이 있나?  어떻게 구분할 수 있나?