지난번 포스팅에서는 공간데이터에 대하여 DBSCAN 알고리즘으로 밀도 기반 군집화하는 방법을 소개하였습니다.


k-means 군집분석의 경우 입력 모수(input parameter)로서 '군집의 개수 k'를 결정하는 것이 어려움이라면, DBSCAN 은 입력 모수로서 '(a) 점으로 부터의 반경 Eps (Epsilon)'와 '(b) Eps 내 최소 점의 개수 기준인 MinPts' 를 결정하는 것이 중요하고도 어려운 문제 중에 하나입니다.


그런데 무슨 연립방정식 풀듯이 이론적으로 증명된 DBSCAN의 입력모수 MinPts 와 Eps 를 구할 수 있는 공식 같은 것, 객관적인 통계량 같은 것은 없습니다. 다만 MinPts와 Eps를 결정하는데 도움을 받을 수 있는 주관적인 Heuristic method 가 있을 뿐입니다.


이번 포스팅에서는 밀도 기반 군집분석 DBSCAN 의 입력 모수 Eps, MinPts 를 결정하는 Heuristic 방법 (Determining the Parameters Eps and MinPts) 을 소개하겠습니다.


(1) MinPts 결정하는 Heuristic 방법: ln(n)

(2) Eps 결정하는 Heuristic 방법: elbow (knee) method using sorted k-dist plot





  (1) DBSCAN에서 MinPts 결정하는 Heuristic 방법


MinPts 는 한 점으로부터 반경 Eps 인 원을 그렸을 때 그 점이 코어 점 (core points), 군집이 되기 위해 Eps 안에 필요한 최소한의 점 개수를 말합니다.


MinPts 가 만약 너무 작은 수이면 잡음(noise)으로 구분되어야 할 점들 마저도 코어 점(core points)나 또는 경계점(border points)로 잘못 구분이 되어 원래 데이터셋 내의 군집 개수보다 더 많은 수의 군집이 형성될 수가 있으므로 주의가 필요합니다.


MinPts 를 결정할 때는 데이터 특성과 구조에 대해서 잘 알고 있는 업 전문가 (domain expert) 의견을 반영할 필요가 있습니다.  그런데 현실은 데이터 분석을 할 때 업 전문가가 없을 수도 있고, 있더라도 MinPts를 잘 결정할 수 없을 수도 있으므로 Heuristic 방법을 알아 둘 필요가 있습니다.


DBSCAN의 원 논문(참조 [1])에서는 2차원 데이터에 대해 실험을 해보니 MinPts 가 4개와 5개 이상 간의 k-dist plot (아래 설명 예정) 의 큰 변동이 없는 반면에 MinPts 가 점점 커질 수록 연산량(computation)이 상당히 커지므로 2차원 데이터에서는 MinPts = 4 개로 하는 것을 권장하고 있습니다.


2차원보다 많은 변수를 가지고 있는 데이터셋의 경우 MinPts = 2 * dim 을 추천하는 논문(참조 [2])도 있습니다.


데이터셋별로 데이터의 구조나 객체의 개수 n이 서로 다를 수 있으므로, 데이터셋별 객체 개수 n 특성을 감안해서 MinPts를 결정하는 Heuristic 방법으로 ln(n) 을 사용할 수 있습니다.(참조 [3]) 여기서 n 은 데이터 개수 (number of points in database) 를 말합니다.




  (2) DBSCAN에서 Eps 결정하는 Heuristic 방법

       : Elbow (Knee) method using sorted k-dist plot


DBSCAN의 원 논문(참조 [1])에서는 아래의 sorted k-dist graph 를 그린 후 Elbow method 를 사용해서 첫번째 계곡(first "valley") 지점의 점이 구분 기준점(threshold point)이 되고, 이 기준점의 왼쪽은 잡음(noist), 기준점의 오른쪽은 군집으로 구분하고, 꺽이는 부분의 k-dist 를 Eps 로 결정하는 Heuristic 방법을 소개합니다.




sorted k-dist graph 를 그리는 방법은, 먼저 MinPts 를 k개라고 했을 때, 하나의 점으로부터 k개의 가장 가까운 점들 간의 거리,k_NN (k-Nearest Neighbor)의 거리 k-dist 를 구해고, k-dist 를 내림차순으로 정렬하여, X축은 정렬된 점들 별로 Y축에는 k-dist 를 그려줍니다.

(단, R의 dbscan 패키지에서는 k-dist 가 오름차순으로 정렬이 된 sorted k-dist plot 을 그려줘서 원 논문과는 그래프의 좌우가 반대입니다.)



R의 factoextra 패키지에 내장되어 있는 multishapes 데이터셋을 가지고 R의 dbscan 패키지를 사용해서 최적의 Eps 모수 값을 결정해보겠습니다.


예제 데이터셋 multishapes 은 아래의 산점도처럼 크기가 다른 원 고리형 2개, 선형 2개, 원형 1개의 5개 군집과 잡음들로 구성이 되어있습니다.



## factoextra for visualizing clusters
if(!require(devtools)) install.packages("devtools")
devtools::install_github("kassambara/factoextra")

library(factoextra)
data("multishapes", package = "factoextra")

## multishapes dataset
str(multishapes)
# 'data.frame':    1100 obs. of  3 variables:
#   $ x    : num  -0.804 0.853 0.927 -0.753 0.707 ...
# $ y    : num  -0.853 0.368 -0.275 -0.512 0.811 ...
# $ shape: num  1 1 1 1 1 1 1 1 1 1 ...


## scatter plot

df <- multishapes[, 1:2]
plot(df, main="multishapes dataset")




다음으로 위에서 설명했던 sorted k-dist plot 을 R의 dbscan 패키지의 kNNdistplot(data, k) 함수를 사용해서 k=5로 지정하고 그려보겠습니다. (k-dist 의 오름차순 기준으로 정렬이 되어서 원 논문과는 반대 모양임.)


sorted k-dist plot 에서 꺽이는 팔꿈치(elbow) 부분의 점이 threshold point 가 되겠습니다. 아래의 예처럼 비교적 눈에 띄게 구분이 되는 경우도 있고, 어디를 꺽인 팔꿈치 (혹은 무릎 knee) 부분인지 콕 집기가 애매한 데이터셋도 있습니다. (객관적이라기 보다는 다분히 주관적입니다.)


이 기준점을 기준으로 왼쪽까지는 군집(clusters)에 속하는 점들이 되겠고, 오른쪽 부터는 잡음 점(noise points)로 간주합니다. 그리고 이 기준점(threshold point)의 k-NN distance 를 최적의 Eps로 결정하면 됩니다. 이렇게 하면 k-dist(p) 와 같거나 작은 값을 가지는 점들은 모두 코어 점(core points)가 됩니다.


아래 예에서는 꺽이는 팔꿈치 부분의 점의 5-NN distance (k-dist(p)) 가 0.15 이므로 Eps 를 0.15로 하면 되겠네요.  (k 를 4 ~ 7 까지 바꾸어 가면서 sorted k-dist plot 을 그려보니 k가 커질수록 elbow 지점의 Eps 가 조금씩 커지기는 하는데요, 큰 차이는 없네요.)



## Determining the optimal Eps value using k-dist plot & elbow method

library(dbscan)


dbscan::kNNdistplot(df, k=5)
abline(h = 0.15, lty = 2)





위에서 sorted k-dist plot 의 elbow mothod 로 구한 최적의 Eps = 0.15 값을 사용하고  MinPts = 5 로 입력 모수를 결정해서 DBSCAN 알고리즘 군집화 및 시각화를 해보겠습니다.



## DBSCAN clustering
set.seed(1004)
db <- dbscan::dbscan(df, eps = 0.15, minPts = 5)

## or using fpc package
# library(fpc)
# db <- fpc::dbscan(df, eps = 0.15, MinPts = 5)


## Plot DBSCAN results
library("factoextra")
fviz_cluster(db, df, stand = FALSE, frame = FALSE, geom = "point")





이외에도 OPTICS: Ordering Points To Identify the Clustering Structure 알고리즘을 이용하는 방법, MinPts 와 Eps 를 변화시켜가면서 잡음의 비율(percentage of noises)의 민감도 분석 (sensitivity analysis) 을 하는 방법도 있으나 이번 포스팅에서는 자세히 설명하지는 않겠습니다.


이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요!  :-)


[Reference]

* [1] Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96

* [2] Erich Schubert, Jorg Sander, Martin Ester, Hans Peter Kriegel, Xiaowei Xu, 2017, "DBSCAN Revisited: Why and How You Should (Still) Use DBSCAN

* [3] Chossing eps and minpts for DBSCAN (R)? : https://stackoverflow.com/questions/12893492/choosing-eps-and-minpts-for-dbscan-r

* [4] DBSCAN in R : http://www.sthda.com/english/wiki/wiki.php?id_contents=7940




Posted by R Friend Rfriend

댓글을 달아 주세요

  1. 열심남 2021.01.01 22:18 신고  댓글주소  수정/삭제  댓글쓰기

    DBACAN 저도 이번에 논문 쓰면서 같이 공부했었는데. 좋은 내용이네요. 전 DBSCAN으오 이상치를 찾는걸 해보았습니다.

이번 DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 알고리즘에 대한 포스팅은 Martin Ester, el.al, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise"[1]  논문을 참조하여 작성하였습니다.


군집분석은 공간 데이터(spatial data)의 그룹, 구조, 구성요소 등을 식별 (class identification)하는 과업에 활용될 수 있습니다. 하지만 대용량의 공간 데이터에 대한 군집화는 다음의 3가지 요건을 충족시킬 수 있어야 합니다.


(1) 대용량 데이터를 다룰 때 적당한 입력 모수에 대한 선험적 지식이 종종 알려져있지 않으므로, 입력 모수(input parameter)를 결정하기 위해 필요한 업 지식은 최소화되어야 하고 (minimal requirements of domain knowledge),

(2) 공간데이터의 형태는 구형, 옆으로 퍼진 형태, 선형, 가늘고 긴 형태 등 다양할 수 있으므로, 임의의 형태의 군집 탐색 가능 (discovery of clusters with arbitrary shape)해야 하고,

(3) 단지 수천개의 객체를 가진 작은 데이터셋 뿐만이 아니라, 대용량 공간데이터에 대해서도 효율적으로 군집화 연산이 가능해야 함.


이번에 소개하는 DBSCAN 알고리즘은 위의 3가지 대용량 공간 데이터에 대한 군집화 조건을 모두 만족합니다. DBSCAN 알고리즘은 이론과 현실 문제 적용에서의 우수성을 인정받아서 2014년에 ACM SIGKDD 데이터마이닝 컨퍼런스에서 상을 받기도 했습니다.


아래의 시각화는 여러가지 모양과 형태의 데이터셋들에 대해 다양한 군집분석 알고리즘을 적용하여 그 결과를 비교한 것입니다. 아래 10개의 군집화 알고리즘 중에서 DBSCAN의 군집화 결과가 데이터셋의 형태에 상관없이 매우 좋은 군집화 결과를 보여주고 있습니다. DBSCAN은 군집에 속하지 않는 잡음(noise), 이상치(outlier) 도 탐지를 할 수 있어서 anomaly detection 에도 쓸 수가 있습니다.


* 출처: https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html#sphx-glr-auto-examples-cluster-plot-cluster-comparison-py



자, 이제 DBSCAN 에 대한 본문으로 들어갈 볼까요?


(1) DBSCAN 알고리즘 정의

(2) k-means vs. DBSCAN 군집화 알고리즘 비교

(3) R을 이용한 DBSCAN 군집화 (예시)




  (1) DBSCAN 알고리즘 정의


DBSCAN 알고리즘을 정의하는데 필요한 기본 용어들을 먼저 살펴보겠습니다.


(정의 1) 반경 Eps 내 이웃점 (Eps-neighborhood of a point)

: 공간 데이터베이스에 속한 점들 중에서 두 점 p와 q의 거리가 반경 Eps() 이내인 점


* D : 데이터베이스(Database), 데이터셋

* dist(p, q) :점 p와 q 의 거리(distance)


이때, 분석가가 입력해줘야 하는 모수로서,

* Eps (Epsilon, 엡실론): 점 p 로 부터의 반경

* MinPts : 최소 기준 점 개수 (minimum number of points)


DBSCAN 알고리즘은 밀도 기반(Density-Based)라고 했는데요, 이때 데이터 점의 밀도(density)는 하나의 점으로 부터 반경 Eps 이내에 점이 몇 개나 있는지로 측정합니다.



(정의 2) 코어 점(core points), 경계 점(border points)


* 코어 점 (core points) : 군집 내 점 (points inside of the cluster), 한 점으로 부터 반경이 Eps 인 원을 그렸을 때 그 원 안에 이웃점(Eps-neighborhood of a point)MinPts 이상의 점이 있는 점.

* 경계 점 (border points) : 군집의 경계에 있는 점 (points on the border of the cluster)


* 출처: [1] Martin Ester, el.al



(정의 3) 직접적으로 밀도(기반)-도달가능한 (directly density-reachable)


점 p가 점 q 반경 Eps 이내에 있는 이웃점에 속하고, 점 q의 반경 Eps 이내 이웃점의 개수가 MinPts 이상일 때 점 p는 점 q 로 부터 직접적으로 밀도(기반)-도달가능하다고 합니다.


(a)

(b) (core point condition)


위의 figure 2 에서 점 p는 점 q로 부터 직접적으로 밀도(기반)-도달가능합니다. 하지만 점 q는 점 p로 부터 직접적으로 밀도(기반)-도달가능하지 않습니다. 왜냐하면 점 p는 코어 점(core point)의 조건을 충족시키지 못하기 때문입니다.



(정의 4) 밀도(기반)-도달가능한 (density-reachable)


만약 연쇄적인 점들 들이 있고, 점이 점 로 부터 직접적으로 밀도(기반)-도달가능하다면(directly density-reachable), 점 p는 점 q로 부터 반경 Eps 내 MinPts 조건 하에 밀도(기반)-도달가능(density-reachable)하다고 합니다.


(정의 3)의 '직접적으로 밀도(기반)-도달가능'은 대칭적(symmetric)인 반면에, (정의 4)의 '밀도(기반)-도달가능'은 비대칭적(asymmetric)입니다.



(정의 5) 밀도(기반)-연결된 (density-connected)


만약 두 점 p와 q가 모두 어떤 점 o 로 부터 반경 Eps 내 MinPts 조건 하에 밀도(기반)-도달가능(density-reachable)하다면 점 p는 점 q와 반경 Eps 내 최소 점 개수 MinPts 조건 하에 밀도(기반)-연결되었다고 합니다. 

(다르게 말하면, p 가 o의 친구이고, q도 o의 친구이면, p와 q는 친구 o를 통해 서로 연결되었다고 보면 됩니다.)



(정의 6) 군집 (cluster)


드디어 이제 DBSCAN 알고리즘이 군집(cluster)를 어떻게 정의하는지 말해볼 때가 왔군요. 위의 정의(1)~(5)까지의 용어와 개념을 사용하여 군집을 정의해보면, "군집은 밀도(기반)-도달가능한 최대치의 밀도(기반)-연결된 점들의 집합이다 (A cluster is defined to be a set of density-connected points which is maximal with respect to density-reachablility.)" 라고 할 수 있겠습니다.



* 출처: [1] Martin Ester, el.al

D를 공간 점들의 데이터베이스(데이터셋) 라고 하고, C 를 군집(Cluster) 라고 했을 때 군집 C는 반경 Eps와 최소 점 개수 MinPts 조건이 주어졌을 때, 아래의 (a) 최대의 밀도(기반)-도달가능 조건과 (b) 연결성 조건을 만족하는 D의 비어있지 않은 부분집합이라고 할 수 있습니다.


(a) Maximality wrt. Density-reachability


(b) Connectivity



(정의 7) (잡음, noise)


잡음 점은 군집에 속하지 못하는 점. 즉, 코어 점도 아니고 경계 점도 아닌 점을 말합니다.



분석의 목적이 군집화라면 잡음점을 무시하거나 제거하면 되구요, 만약 분석의 목적이 군집화가 아니라 anomaly detection, outlier detection 이라면 잡음 점(noises)들이 주요 관심사가 되겠습니다.



DBSCAN 알고리즘의 군집화 절차는 아래와 같이 정리할 수 있습니다.


입력 모수(input parameters)로서, 점으로 부터의 (a) 반경 Eps와 (b) Eps 반경 내 최소 점 개수 기준인 MinPts 조건이 주어졌을 때,


(1) 공간 데이터셋으로부터 초기값(seed)으로서 코어 점(core points)의 조건을 만족하는 임의의 점을 선택합니다.

(2) 초기값으로 부터 밀도(기반)-도달가능한 점들을 뽑아서 코어 점(core points)과 경계 점(border point)을 구분하고, 이에 속하지 않은 점들을 잡음(noises)으로 구분합니다. 

(3) 반경 Eps 인 원 주위에 있는 코어 점들을 서로 연결합니다.

(4) 연결된 코어 점들을 하나의 군집으로 정의합니다.

(5) 모든 경계점들을 어느 하나의 군집으로 할당합니다. (만약 경계점 중에 여러 군집에 걸쳐있는 경우는 반복 과정에서 먼저 할당된 군집으로 할당함.)



왼쪽의 그림은 Wikipedia에 소개된 내용인데요, 원 논문의 그림보다 좀더 이해하기 쉬울거 같아서 한번 더 소개합니다.


점으로 부터의 반경이 Eps 이고 MinPts = 4 라고 했을 때,


점 A를 포함해서 가운데의 빨간점 6개는 코어 점(core points) 입니다.


그리고 코어점은 아니지만 코어점과 연결 가능한 노란색 점 B, C 는 경계점(border points) 입니다.


그리고 코어 점도 아니고 경계 점도 아닌 파란색 점 N 은 잡음(noise) 점이 되겠습니다.


군집화의 과정은 각 점들을 순회하면서 재귀적(recursive)으로 도달가능, 연결가능을 평가하면서 진행이 됩니다.







  (2) k-means Clustering vs. DBSCAN 군집화 알고리즘 비교


k-means 와 DBSCAN 군집화 알고리즘을 아래의 표에 비교해서 정리해보았습니다. 유사성(혹은 비유사성 거리) 기반의 k-means 대비, 밀도 기반의 DBSCAN 의 경우 분석가가 미리 군집의 개수 (k)를 입력해주지 않아도 되고, 잡음/이상치에도 견고하며, 계산 복잡도도 상대적으로 작습니다. 게다가 군집으로 찾아낼 수 있는 모양도 구형, 원형, 길게 늘어선 형태, 선형 등 임의의 모양에 대해서 비교적 잘 군집화를 하고, 잡음/이상치도 별도로 구분을 해낼 수 있습니다. 이래저래 DBSCAN이 k-means 대비 우수한 점이 많습니다.





  (3) R을 이용한 DBSCAN 군집화 (예시)


DBSCAN 분석을 위한 R코드는 참조 [3] 사이트의 코드를 거의 그대로 사용하였습니다.


예제로 사용할 데이터셋으로 중앙이 비어있는 원형, 선형, 구형 등 다양한 형태의 군집과 잡음으로 구성된, factoextra 패키지에 내장되어 있는 multishapes 데이터셋을 사용하겠습니다.



## factoextra for visualizing clusters
if(!require(devtools)) install.packages("devtools")
devtools::install_github("kassambara/factoextra")

library(factoextra)
data("multishapes", package = "factoextra")

## multishapes dataset
str(multishapes)
# 'data.frame':    1100 obs. of  3 variables:
#   $ x    : num  -0.804 0.853 0.927 -0.753 0.707 ...
# $ y    : num  -0.853 0.368 -0.275 -0.512 0.811 ...
# $ shape: num  1 1 1 1 1 1 1 1 1 1 ...

plot(multishapes$x, multishapes$y)


 



k-means clustering 과 DBSCAN clustering 알고리즘을 비교해보기 위해, 위의 multishapes 데이터셋에 대해 군집의 개수 k=5로 해서 k-means 군집화를 해보겠습니다.


k-means 군집화의 경우, (1) 상단에 위치한 중앙이 비어있는 원형 군집 2개를 제대로 구분하지 못하고 있고, (2) 좌측 하단에 위치한 선형 2개 군집도 제대로 구분하지 못하고 있으며, (3) 우측 하단의 물방울 형태 군집도 잡음/이상치가 섞여서 군집화가 되었습니다. 전혀 만족스럽지 않은 군집화 결과네요.



##-- k-means clustering plot
df <- multishapes[, 1:2]
set.seed(1004)
km.res <- kmeans(df, centers=5, nstart = 25)
fviz_cluster(km.res, df, frame = FALSE, geom = "point")





이번에는 DBSCAN 알고리즘으로 입력 모수로서 Eps = 0.15, MinPts = 5 로 하여 multishapes 데이터셋에 대해 군집화를 해보겠습니다.


R의 fpc 패키지나 dbscan 패키지를 사용하여 DBSCAN 알고리즘으로 군집화를 할 수 있습니다. 아래 예시에서는 fpc 패키지를 사용하였으며, 패키지명::함수명() 형태로서 fpc::dbscan(data, eps, MinPts) 으로 패키지 이름을 명시적으로 입력해주었습니다.


아래 표(참조 [4])는 프로그래밍 언어별 DBSCAN 을 할 수 있는 패키지들을 비교한 것입니다.  R 의 dbscan 패키지가 지원하는 기능 면에서는 가장 강력하네요. R fpc 패키지는 dbscan 에만 특화된 simple 한 패키지이구요.




##-- DBSCAN using fpc or dbscan package
install.packages("fpc")
library(fpc)


## Compute DBSCAN using fpc package
set.seed(1004)
db <- fpc::dbscan(df, eps = 0.15, MinPts = 5)


## or
# install.packages("dbscan")
# library(dbscan)

# dbscan(data, eps, MinPts = 5, scale = FALSE,
#        method = c("hybrid", "raw", "dist"))




마지막으로 factoextra 패키지의 fviz_cluster() 함수로 DBSCAN 군집화 결과를 시각화해보았습니다.


DBSCAN 군집화 결과를 보면, (1) 상단에 위치한 중앙이 비어있는 원형 군집 2개를 잘 구분하였고, (2) 좌측 하단에 위치한 선형 2개 군집도 제대로 구분하였으며, (3) 우측 하단의 물방울 형태 군집도 잘 군집화하였을 뿐만 아니라, (4) 잡음/이상치도 잘 구분하였습니다. 매우 만족스러운 군집화 결과네요!


## Plot DBSCAN results
library("factoextra")
fviz_cluster(db, df, stand = FALSE, frame = FALSE, geom = "point")

## or
#plot(db, df, main = "DBSCAN", frame = FALSE)



 




DBSCAN 군집화 결과 객체에서 cluster 속성에 각 관측치별 속한 군집 정보가 들어있습니다. cluster '0'은 잡음/이상치를 의미합니다. 아래 예제에서는 무작위로 50개 관측치를 샘플링해서 그 관측치들이 무슨 군집으로 할당이 되었는지 프린트해보았습니다.



## Print DBSCAN
print(db)
# dbscan Pts=1100 MinPts=5 eps=0.15
# 0   1   2   3  4  5
# border 31  24   1   5  7  1
# seed    0 386 404  99 92 50
# total  31 410 405 104 99 51


names(db)
# [1] "cluster" "eps"     "MinPts"  "isseed"


# Cluster membership. Noise/outlier observations are coded as 0
# A random subset is shown
db$cluster[sample(1:1089, 50)]
# [1] 2 2 1 1 0 2 4 1 2 1 4 1 2 2 1 4 2 3 2 1 1 5 2 1 5 1 2 1 3 1 1 4 2 3 2 1 2 1 1 3 2 1 2 1 2 1 1 1 1 4




[Reference]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

[Reference]

* Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD-96



출처: https://rfriend.tistory.com/588 [R, Python 분석과 프로그래밍의 친구 (by R Friend)]

* [1] Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, 1996, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise"

(pdf download: https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf )

* [2] DBSCAN at Wikipedia: https://en.wikipedia.org/wiki/DBSCAN

* [3] DBSCAN in R : http://www.sthda.com/english/wiki/wiki.php?id_contents=7940

* [4] R dbscan package: https://cran.r-project.org/web/packages/dbscan/vignettes/dbscan.pdf


다음번 포스팅에서는 DBSCAN 알고리즘의 입력 모수인 Eps, MinPts 를 결정하는 휴리스틱 방법을 소개하겠습니다.


이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요! :-)



Posted by R Friend Rfriend

댓글을 달아 주세요

지난번 포스팅에서는 분할적 군집분석(Partitioning clustering)에서 군집의 개수 k를 결정하는 3가지 방법 (계층적 군집분석 덴드로그램, Elbow method, Silhouettes method)을 소개하였습니다.

군집분석 결과를 현장에 적용하려면 각 군집의 특성을 이해하고, 군집별로 차별화된 대응 전략을 도출할 수 있어야만 합니다. 이번 포스팅에서는 군집분석 결과를 해석하는 3가지 방법을 소개하겠습니다.

(1) 군집별 변수별 중심 좌표 (Center Points by Clusters)
(2) 군집별 변수별 평행 좌표 그림 (Parallel Coordinates Plot by Clusters)
(3) (차원축소 후) 군집별 산점도 (Scatter Plot by Clusters using Reduced Dimension)



  (0) 샘플 데이터 준비 : USArrests {datasets}


예제로 사용할 샘플 데이터는 R datasets 패키지에 내장되어있는 USArrests 데이터셋을 사용하겠습니다. 미국 내 50개 주별 범죄율 관련된 살인(murder), 폭행(assault), 도시인구(UrbanPop), 강간(rape) 의 4개 변수 통계 데이터가 들어있습니다.

군집분석은 변수별 척도에 민감하므로 scale() 함수를 사용해서 표준화(standardization)를 해주었습니다.


## importing USArrests dataset from {datasets}
data(USArrests)

dim(USArrests)
# [1] 50  4

head(USArrests)
# Murder Assault UrbanPop Rape
# Alabama      13.2     236       58 21.2
# Alaska       10.0     263       48 44.5
# Arizona       8.1     294       80 31.0
# Arkansas      8.8     190       50 19.5
# California    9.0     276       91 40.6
# Colorado      7.9     204       78 38.7


## standardization (scaling)
USArrests_scaled <- data.frame(scale(USArrests))

head(USArrests_scaled)
# Murder   Assault   UrbanPop         Rape
# Alabama    1.24256408 0.7828393 -0.5209066 -0.003416473
# Alaska     0.50786248 1.1068225 -1.2117642  2.484202941
# Arizona    0.07163341 1.4788032  0.9989801  1.042878388
# Arkansas   0.23234938 0.2308680 -1.0735927 -0.184916602
# California 0.27826823 1.2628144  1.7589234  2.067820292
# Colorado   0.02571456 0.3988593  0.8608085  1.864967207





  (1) 군집별 변수별 중심 좌표 (Center Points by Clusters)


표준화한 USArrests 데이터셋에 대해 k-means 의 군집개수 k=4 로 해서 군집분석을 하고, 4개의 군집에 대해 해석(interpretation, profiling)을 해보겠습니다.


군집분석 결과를 해석하는 가장 쉽고 또 직관적인 방법은 각 군집별로 군집화에 사용했던 변수들의 중심 좌표를 살펴보는 것입니다.


R 의 군집분석 결과에는 군집별 중심좌표로서 군집별 변수별 평균('Cluster means') 정보가 군집분석 결과 객체의 "centers" attributes에 계산되어 저장되어 있습니다.



## -- (1) Centers per Clusters
## K-means clustering
set.seed(1004)
kmeans_k4 <- kmeans(USArrests_scaled, centers = 4)


## attributes of k-means clustering results

names(kmeans_k4)
# [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
# [6] "betweenss"    "size"         "iter"         "ifault"



## center points per variables

kmeans_k4$centers
# Murder    Assault   UrbanPop        Rape
# 1 -0.9615407 -1.1066010 -0.9301069 -0.96676331
# 2  0.6950701  1.0394414  0.7226370  1.27693964
# 3  1.4118898  0.8743346 -0.8145211  0.01927104
# 4 -0.4894375 -0.3826001  0.5758298 -0.26165379




그런데 kmeans_k4$centers 로 조회한 4개 각 군집의 변수별 중심 좌표 (평균) 은 여기서는 표준화한 후의 데이터에 대한 변수별 평균입니다. 표준화하기 전의 원래 데이터의 군집별 변수별 중심 좌표 (평균)을 알고 싶으면, 아래의 예시처럼 원래의 데이터에 군집화 결과 변수를 추가해주고(미국 주 이름별로 이미 정렬이 된 상태이기 때문에 merge가 아니라 그냥 칼럼을 추가해주었습니다.), 각 군집별 변수별 평균을 구해주면 됩니다.


## add 'cluster' to the original dataset

USArrests$cluster <- kmeans_k4$cluster
head(USArrests)

# Murder Assault UrbanPop Rape cluster
# Alabama      13.2     236       58 21.2       3
# Alaska       10.0     263       48 44.5       2
# Arizona       8.1     294       80 31.0       2
# Arkansas      8.8     190       50 19.5       3
# California    9.0     276       91 40.6       2
# Colorado      7.9     204       78 38.7       2


library(dplyr)
USArrests %>%
  group_by(cluster) %>%
  summarise(murder = mean(Murder),
            assault = mean(Assault),
            urbanpop = mean(UrbanPop),
            rape = mean(Rape))


# # A tibble: 4 x 5
# cluster murder assault urbanpop  rape
# <fct>    <dbl>   <dbl>    <dbl> <dbl>
#   1 1         3.6     78.5     52.1  12.2
# 2 2        10.8    257.      76    33.2
# 3 3        13.9    244.      53.8  21.4
# 4 4         5.66   139.      73.9  18.8





  (2) 군집별 변수별 평행 좌표 그림 (Parallel Coordinates Plot by Clusters)


다변량 데이터셋으로 군집분석을 했을 때 다수 변수들에 대해 관측치 개개의 값들이 군집별로 어떻게 다른지를 보려면 평행 좌표 그림을 사용할 수 있습니다.


GGally 패키지의 ggparcoord() 함수를 이용해서 ggplot2 기반의 군집별 변수별 평행좌표그림 (parallel coordinates plot)을 그려보겠습니다.


표준화하기 전의 원본 데이터를 사용하고, scale = "std" 를 해주면 알아서 각 변수들을 표준화해줍니다.

(혹은 표준화한 데이터를 바로 사용해도 됩니다).


단, 관측치 개수가 너무 많으면 하나의 평행좌표그림에 모든 관측치를 표현할 경우 서로 겹쳐보여서 군집 특성을 파악하는 것이 힘들 수도 있습니다.


ggplotly 패키지의 ggplotly() 함수를 사용하면 interactive plot 을 그려서 군집별로 하이라이트해서 좀더 수월하게 그래프를 볼 수도 있습니다. (저는 R 4.02 버전을 쓰고 있는데요, 이 버전에서는 ggplotly 가 지원이 안된다고 나오네요 -_-;)



## Parallel Coordinates Plot
install.packages("GGally")
library(GGally)

USArrests$cluster <- as.factor(USArrests$cluster)

p <- ggparcoord(data = USArrests,
                columns = c(1:4),
                groupColumn = "cluster",
                scale = "std") +
  labs(x = "Violent Crime Rates by US State",
       y = "value in scaled",
       title = "Parallel Coordinates Plot by Cluster")

p




## Interactive plot using ggplotly

install.packages("ggplotly")
library(ggplotly)
ggplotly(p)

 




  (3) (차원축소 후) 군집별 산점도 (Scatter Plot by Clusters using Reduced Dimension)


다변량 데이터셋으로 분할적 군집분석(partitioning clustering)한 결과를 2차원의 평면에 군집별로 색깔과 모양을 달리해서 산점도로 표현을 할 수 있다면 군집별 특성을 이해하는데 도움이 될 것입니다.


다변량 변수를 2차원으로 차원축소하는데 요인분석(factor analysis), 주성분분석(principal component analysis, PCA) 등을 사용합니다.


k-means 군집분석한 결과를 R의 Factoextra 패키지의 fviz_cluster() 함수를 사용하면 주성분분석(PCA) 으로 다변량을 2차원으로 축소해주고, 이를 군집별로 색깔과 모양을 달리하여 R ggplot2 기반의 세련된 시각화를 해줍니다.


아래 예의 경우 Dim1 (62%), Dim2 (24.7%) 라고 되어있는데요, 이는 전체 분산 중 가로 축 Dim1 이 62%를 설명하고, 세로 축 Dim2 가 24.7% 를 차지한다는 뜻입니다. USArrests 데이터셋의 경우 '살인(murder)', '폭행(assault)', '강간(rape)'의 3개 변수가 "범죄"와 관련이 있어서 Dim1에 의해 많이 설명이 되고, 나머지 변수인 '도시인구(UrbanPop)'가 Dim2에 의해 설명이 되겠네요.

(* 주성분분석 참조 : https://rfriend.tistory.com/61 )



## fviz_silhouette:Visualize Silhouette Information from Clustering
install.packages("factoextra")
library(factoextra)


# Visualize kmeans clustering
fviz_cluster(kmeans_k4, USArrests_scaled, ellipse.type = "norm")+
  theme_minimal()




[ R factoextra package Reference ]

* https://rpkgs.datanovia.com/factoextra/index.html

* https://cran.r-project.org/web/packages/factoextra/factoextra.pdf



혹은 다변량 데이터셋에서 군집을 구분해서 잘 설명해줄 수 있는 대표적인 변수 2개만 선택해서 ggplot2로 직접 2차원 산점도를 그릴 수도 있습니다.

이번 USArrests 데이터셋의 경우 '살인(murder)', '폭행(assault)', '강간(rape)'의 3개 변수가 "범죄"와 관련이 있으므로 이중에서 '살인(murder)' 변수를 하나 뽑고, 나머지 변수인 '도시인구(UrbanPop)'를 나머지 하나로 선택해서 2차원 산점도를 그려보겠습니다.


## Scatter plot by Murder and UrbanPop by clusters
library(ggplot2)
library(repr)
options(repr.plot.width=12, repr.plot.height=12)


set.seed(1004)
km_4 <- kmeans(USArrests_scaled, centers = 4)


cluster_num <- as.factor(km_4$cluster)
city_name <- rownames(USArrests_scaled)

ggplot(data=USArrests_scaled, aes(x=Murder, y=UrbanPop, colour=cluster_num)) +
  geom_point(shape=19, size=4) +
  ggtitle("Scatter Plot of USArrests") +
  theme(plot.title = element_text(size = 20, face = "bold")) +
  annotate("text", x = USArrests_scaled$Murder, y = USArrests_scaled$UrbanPop+0.1,
           label=city_name, size = 5, color="gray") +
  annotate("point", x = km_4$centers[1,1], y = km_4$centers[1,3], size = 6, color = "black") +
  annotate("point", x = km_4$centers[2,1], y = km_4$centers[2,3], size = 6, color = "black") +
  annotate("point", x = km_4$centers[3,1], y = km_4$centers[3,3], size = 6, color = "black") +
  annotate("point", x = km_4$centers[4,1], y = km_4$centers[4,3], size = 6, color = "black") +
  annotate("text", x = km_4$centers[1,1], y = km_4$centers[1,3]+0.2, label="cluster 1", size = 8) +
  annotate("text", x = km_4$centers[2,1], y = km_4$centers[2,3]+0.2, label="cluster 2", size = 8) +
  annotate("text", x = km_4$centers[3,1], y = km_4$centers[3,3]+0.2, label="cluster 3", size = 8) +
  annotate("text", x = km_4$centers[4,1], y = km_4$centers[4,3]+0.2, label="cluster 4", size = 8)




이상으로 위의 (1) 군집별 중심 좌표 (평균), (2) 군집별 다변량 변수별 평행 좌표 그림, (3) (차원 축소 후) 군집별 산점도를 통해 군집 1 ~ 4 번까지의 특성을 파악해 본 결과,


* 군집 1 : 범죄(살인, 폭행, 강간)도 낮고, 도시인구수도 낮은 도시군 (예: Vermont, Wisconsin 등)

* 군집 2 : 범죄도 높고, 도시인구수도 높은 도시군 (예: New York, Flolida 등)

* 군집 3 : 범죄는 높고, 도시인구수는 낮은 도시군 (예: Mississippi, South Carolina 등)

* 군집 4 : 범죄는 낮고, 도시인구수는 높은 도시군 (예: Utah, Massachusetts 등)


으로 해석할 수 있겠네요.

이번 포스팅이 많은 도움이 되었기를 바랍니다.
행복한 데이터 과학자 되세요. :-)


Posted by R Friend Rfriend

댓글을 달아 주세요

군집분석 중에서 k-means clustering, k-median clustering, k-medoid clustering, fuzzy k-means clustering, Gaussian mixture model clustering 등의 알고리즘은 군집의 개수 k를 미리 정해주어야 합니다.


그런데 군집분석이 정답 Y가 없는 상태에서 데이터 구조/군집을 탐색하고 마이닝하는 비지도학습(unsupervised learning)이다 보니 최적의 군집의 개수 k를 결정하고 군집 결과를 평가하는 것이 다분히 주관적인 편입니다. 해당 업과 데이터에 대해서 잘 아는 SME(Subject Matter Expert)의 지식과 경험, 그리고 활용 목적을 고려한 주관적인 의견을 반영하여 최종결정하는 것이 필요하고 중요합니다.


단, 이때 주관적인 경험과 지식에만 의존하는 것이 아니라, 군집의 개수 k를 선택하는데 있어 계량적인 데이터 분석 수치와 시각화의 도움을 받을 수 있다면 좀더 쉽고 또 보다 데이터 구조와 특성을 잘 반영한 의사결정을 할 수 있을 것입니다. (물론, 이마저도 정답이 없다보니 분석가의 주관적인 평가와 판단이 들어가게 되고, 명확한 판단을 내리기가 애매한 경우도 생길 수 있습니다.)


이번 포스팅에서는 군집의 개수 k 를 미리 정해주어야 하는 알고리즘에서 군집의 개수 k를 결정하고 선택하는데 도움을 받을 수 있는 3가지 방법(Determining the number of clusters)대해서 알아보겠습니다.


(1) 계층적 군집분석의 덴드로그램 시각화를 이용한 군집의 개수 결정
     (Hierarchical Clustering: Dendrogram)

(2) 팔꿈치 방법을 이용한 군집의 개수 결정 (The Elbow Method)

(3) 실루엣 방법을 이용한 군집의 개수 결정 (The Silhouette Method)






  0. 샘플 데이터 USArrests {datasets} 불러오기 및 전처리


예제로 사용할 데이터는 R의 datasets 패키지에 내장되어 있는, 미국 주별 폭력적인 범죄 비율("Violent Crime Rates by US State)의 통계를 포함한 USArrests 데이터셋입니다. 이 데이터셋은 1973년 미국의 50개 주 별로 10만 명당 살인(Murder), 폭행(Assault), 강간(Rape) 체포 건수와 도시 인구 비율 (Percent Urban Population)의 네 개의 변수로 구성되어 있습니다.


## importing USArrests dataset from {datasets}
data(USArrests)

dim(USArrests)
# [1] 50  4

head(USArrests)
# Murder Assault UrbanPop Rape
# Alabama      13.2     236       58 21.2
# Alaska       10.0     263       48 44.5
# Arizona       8.1     294       80 31.0
# Arkansas      8.8     190       50 19.5
# California    9.0     276       91 40.6
# Colorado      7.9     204       78 38.7




군집분석을 할 때 변수별 척도가 다를 경우 큰 척도의 변수 값에 군집의 결과가 휘둘릴 수 있으므로, 먼저 scale() 함수를 이용해서 표준화(standardization)를 해주었습니다.



## standardization (scaling)
USArrests_scaled <- data.frame(scale(USArrests))

head(USArrests_scaled)
# Murder   Assault   UrbanPop         Rape
# Alabama    1.24256408 0.7828393 -0.5209066 -0.003416473
# Alaska     0.50786248 1.1068225 -1.2117642  2.484202941
# Arizona    0.07163341 1.4788032  0.9989801  1.042878388
# Arkansas   0.23234938 0.2308680 -1.0735927 -0.184916602
# California 0.27826823 1.2628144  1.7589234  2.067820292
# Colorado   0.02571456 0.3988593  0.8608085  1.864967207

 



다음으로, 표준화한 데이터에 대해서 50개의 각 주별 쌍의 유사도 행렬 (proximity matrix)로서 유클리드 거리 행렬 (Euclidean distance matrix) 을 dist(method = "euclidean") 함수를 사용해서 계산하였습니다. 자, 이제 군집분석을 위한 데이터셋 준비가 다 되었네요.



# calculating the euclidean diatance matrix
dist_eucl <- dist(USArrests_scaled, method = "euclidean")

dist_eucl
# Alabama    Alaska   Arizona  Arkansas California  Colorado Connecticut
# Alaska         2.7037541                                                               
# Arizona        2.2935197 2.7006429                                                     
# Arkansas       1.2898102 2.8260386 2.7177583                                           
# California     3.2631104 3.0125415 1.3104842 3.7636409                                 
# Colorado       2.6510673 2.3265187 1.3650307 2.8310512  1.2876185                      
# Connecticut    3.2152975 4.7399125 3.2628575 2.6076395  4.0663898 3.3279920            
# Delaware       2.0192927 3.6213633 1.9093696 1.8003239  3.0737852 2.5547456   1.7568475
# Florida        2.2981353 2.9967642 1.7493928 3.3721968  2.0250039 2.4458600   4.4700701
# Georgia        1.1314351 2.8194388 2.7871963 2.2117614  3.3780585 2.8649105   3.9738227
# Hawaii         3.3885300 4.5301340 3.2621208 2.9723097  3.6589083 2.8233524   1.3843291
# Idaho          2.9146623 4.0580555 3.5210071 1.7687255  4.4879436 3.4767685   1.6354214
# Illinois       1.8734993 3.2670626 1.0825512 2.4626424  1.9117469 1.7898322   2.7400560

-- 이하 생략함 --

 




  (1) 계층적 군집분석의 덴드로그램 시각화를 이용한 군집의 개수 결정
     (Hierarchical Clustering: Dendrogram)


계층적 군집분석(hierarchical clustering)에는 군집과 군집 간의 거리를 측정하는 다양한 연결법(linkage method)으로서, 단일연결법, 완전연결법, 평균연결법, 중심연결법, Ward연결법 등이 있습니다. 그중에서 Ward 연결법(Ward Linkage Method)에 의한 계층적 군집분석을 해보고, 이 결과를 덴드로그램(Dendrogram)으로 시각화를 해보겠습니다.


덴드로그램을 시각화 한 후에 왼쪽의 높이(Height) 축을 기준으로, 위에서 아래로 높이를 이동하면 군집의 개수가 1개, 2개, 4개, 6개, 8개, ..., 50개, 이런 식으로 변하게 됩니다.


이때 군집 간 높이의 차이가 큰 군집의 개수를 선택하면 군집 내 응집력은 높고, 군집간 이질성이 큰 적절한 군집을 구할 수 있습니다. 아래의 예의 경우 군집의 개수가 2개 또는 4개가 적당해 보이네요.


다만, 이 방법은 (a) 데이터 개수가 많을 경우 (가령, 수십만개, 수백만개) 군집화 시간이 오래걸리고, 덴드로그램으로 시각화가 거의 불가능할 수 있습니다. (b) 통계량을 산출하는게 아니고 덴드로그램 시각화 결과를 보고 분석가의 판단에 의지하다보니 다분히 주관적입니다.



set.seed(1004) # for reproducibility
hc_ward <- hclust(dist_eucl, method="ward.D")

# 덴드로그램
plot(hc_ward)





  (2) 팔꿈치 방법을 이용한 군집의 개수 결정 (The Elbow Method)


다음으로는 비계층적 군집분석(nonhierarchical clustering, partitioning clustering) 중에서 k-means 군집분석(또는 k-median, k-medoids 등)의 k를 다르게 바꾸어가면서 군집화를 했을 때, 군집의 수 k별 "군집 내 군집과 개체 간 거리 제곱합의 총합 (tot.withinss: Total within-cluster sum of squares)" 의 그래프가 팔꿈치 모양으로 꺽이는 지점의 k 를 최적 군집의 개수를 선택하는 방법이 팔꿈치 방법(The Elbow Method) 입니다.


군집 Gi의 중심 측도가 평균인 경우,


Total Within-Cluster Sum of Squares

tot.withinss =



아래의 USArrests 데이터셋 예의 경우 군집의 개수가 4개일 때 Total within-cluster sum of squares 가 팔꿈치 모양으로 꺽이고, 군집 k가 5개 이상일 때부터는 tot.withinss의 변화가 매우 작으므로, 군집의 개수를 4개로 하는 것이 가장 좋아보이네요. (분석가의 주관적인 요소가 들어가긴 합니다. ^^;)



# find the optimal number of clusters using Total within-cluster sum of squares
tot_withinss <- c()

for (i in 1:20){
  set.seed(1004) # for reproducibility
  kmeans_cluster <- kmeans(USArrests_scaled, centers = i, iter.max = 1000)
  tot_withinss[i] <- kmeans_cluster$tot.withinss
}

plot(c(1:20), tot_withinss, type="b",
     main="Optimal number of clusters",
     xlab="Number of clusters",
     ylab="Total within-cluster sum of squares")






또는, 군집의 개수 k 별로 전체 분산(Total Variance) 중에서 그룹 간 분산(Between-Group Variance)의 비율로 계산(F-test 라고도 함)하는 "설명된 분산의 비율(the Percentage of Variance Explained)"을 계산하여 시각화한 후에, 팔꿈치 모양으로 꺽이는 지점의 군집의 개수 k를 선택하는 방법을 사용할 수 도 있습니다. (이 경우 위의 그룹 내 분산(Within-cluster Sum of Squares)을 사용했을 때와는 그래프 모양이 반대가 됩니다.)





## the percentage of variance explained as a function of the number of clusters
## Percentage of variance explained is the ratio of the between-group variance to the total variance,
## also known as an F-test.
r2 <- c()

for (i in 1:20){
  set.seed(1004) # for reproducibility
  kmeans_cluster <- kmeans(USArrests_scaled, centers = i, iter.max = 1000)
  r2[i] <- kmeans_cluster$betweenss / kmeans_cluster$totss
}

plot(c(1:20), r2, type="b",
     main="The Elbow Method - Percentage of Variance Explained",
     xlab="Number of clusters",
     ylab="Percentage of Variance Explained")







  (3) 실루엣 방법을 이용한 군집의 개수 결정 (The Silhouette Method)


Peter J. Rousseeuw 는 "Silhouettes: a grapical aid to the interpretation and validation of cluster analysis" (1987) 라는 논문에서 분할적 군집분석(partitioning clustering)의 결과를 시각화하여 해석하고 평가할 수 있는 지표로서 실루엣(Silhouette)을 제안하였습니다.


실루엣을 계산하기 위해서 먼저 아래의 용어를 정의합니다. (아래의 논문 예시 그림 참조)


군집 A가 객체 i와 다른 객체들을 포함하고 있을 때,


a(i) = 군집 A 내의 객체 i 와 군집 A 내의 다른 객체들 간의 평균 비유사성 (즉, 거리 (distance))

        (average dissimilarity of i to all other objects of A)


d(i, C) = 군집 A 내의 객체 i와 다른 군집 C에 속한 모든 객체와의 평균 비유사성 (즉, 거리)

        (average dissimilarity of i to all objects of C)


b(i) = d(i, C) 의 최소값 =



* source: Reter J. Rousseeuw (1987)



실루엣은 아래 공식을 보면 알 수 있는 것처럼, 밀집성(tightness)와 분리성(separation)의 비교에 기반한 지표로서, 실루엣은 어떤 객체가 군집 안에 잘 놓여 있는지, 그리고 어떤 객체는 단지 군집들 사이의 어딘가에 놓여있는지를 보여줍니다.




전체 군집분석의 실루엣들을 하나의 그래프에 모아서 보여줌으로써, 데이터 구성과 형상의 개요(overview of the data configuration)군집들의 상대적인 질(the relative quality of the clusters)을 평가할 수 있습니다.


평균 실루엣 폭(the average silhouette width)은 군집화 결과에 대한 타당성(validity)을 평가하고, 또 적절한 군집 개수를 선택(to select an 'appropritate' number of clusters)하는데 활용할 수 있습니다.


실루엣은 -1 <= s(i) <= 1 사이의 값을 가집니다. 위 공식에 의하면 "실루엣 값이 1에 가까우면 다른 군집과의 거리보다 동일 군집 내 객체 간 거리가 가깝다는 뜻이므로 객체 i가 잘 군집화가 되었다는 의미"입니다. (이와 반대로 실루엣 값이 -1에 가까우면 객체 i의 군집화가 잘못되었다는 뜻입니다.)


만약 대부분의 객체가 높은 실루엣 값을 가진다면 군집의 구성이 적절하게 잘 되었다고 평가할 수 있습니다. 반면 많은 객체들이 낮거나 혹은 음(-)의 실루엣 값을 가진다면 군집 구성이 너무 많거나 또는 너무 적은 수의 군집을 가졌기 때문이라고 판단할 수 있습니다.

(아래 예에서는 군집4 에 정렬된 객체들의 뒷부분에 낮은 실루엣 값, 또는 음의 실루엣 값을 가진 객체들이 여러개 보이네요.)



## fviz_silhouette: Visualize Silhouette Information from Clustering
install.packages("factoextra")
library(factoextra)


# K-means clustering
set.seed(1004)
km.res <- kmeans(USArrests_scaled, centers = 4)

# Visualize silhouhette information
library("cluster")
sil <- silhouette(km.res$cluster, dist(USArrests_scaled))
fviz_silhouette(sil)





이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요. :-)


[Reference]

* Determining the number of clusters in a data set
   : https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

* Silhouette (Clustering): https://en.wikipedia.org/wiki/Silhouette_(clustering)

* Peter J. Rousseeuw, Journal of Computational and Applied Mathematics 20 (1987), "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis"



Posted by R Friend Rfriend

댓글을 달아 주세요

그동안 연속형(continuous), 이분형(binary), 서열형(ordinal), 명목형(nominal) 변수별 다양한 유사성(Similarity) 측정, 혹은 비유사성(Dis-similarity)으로서 거리(Distance) 측정 방법을 여러개의 포스팅에 각각 나누어서 연재하였습니다.


그러면, 만약 여러개의 변수가 있는 데이터셋에 연속형, 이분형, 서열형, 명목형 변수가 혼합되어 섞여있다면 어떻게 유사성, 혹은 비유사성을 측정해야 할까요?


이처럼 여러 데이터 유형의 변수가 섞여있으면, 각 유형의 변수별로 유사성(혹은 비유사성, 거리)을 평가한 다음에, 이를 합하거나 평균을 내주면 됩니다.


이때 각 유형 변수별 유사성 척도는 특정 유형의 변수의 영향력이 동일하게 작용하도록 [0, 1] 사이의 값을 사용합니다. 이전 포스팅에서 살펴보았듯이 이분형(binary), 명목형(nominal), 서열형(ordinal) 변수의 유사성 (혹은 비유사성 거리) 값은 0 ~ 1 사이의 값을 가집니다.


반면, 연속형 변수의 거리 (가령, 맨하탄 거리, 유클리드 등)의 값은 [0, 1] 사이의 값이 아니므로, 각 연속형 변수의 범위(range = Xmax - Xmin)로 거리를 나누어 줌으로써 연속형 변수의 정규화된 거리가 [0, 1] 사이의 값으로 변환을 해준 후에 다른 범주형 변수의 거리와 더해주거나 평균을 내주면 됩니다.


아래의 예에서는 "이분형(binary) 변수"인 성별, "연속형(continuous) 변수"인 연령과 용돈, "명목형(nominal) 변수"인 직업, "서열형(ordinal) 변수"인 직업만족도의 5개 변수에 대해 관측치 1, 2, 3의 3명 간 비유사성인 거리(distance)를 계산해보겠습니다.




먼저, 성별은 이분형(이진형, binary) 변수이므로 두 관측치의 값이 같으면 거리는 '0', 두 관측치의 값이 다르면 거리는 '1'이 됩니다. (만약 유사성을 평가하는 거라면 반대로 두 관측치의 값이    같으면 유사성은 '1', 두 관측치의 값이 다르면 유사성은 '0'이 됩니다.)


위 예에서 dist_gender(x1, x2) 는 관측치 ID 1번과 ID 2번 관측치의 성별(gender) 이분형 변수에 대한 거리를 계산한 것으로서, ID 1번은 "남성"이고 ID 2번은 "여성"으로서 서로 다르므로 거리는 '1'이 됩니다. 반면, dist_gender(x1, x3) 는 관측치 ID 1번과 ID 3번 모두 "남성"으로서 서로 같으므로 거리는 '0'이 됩니다.


다음으로 연령(age)과 용돈(allowance)은 연속형(continuous) 변수로서, 두 관측치 간 거리를 계산했을 때의 값이 [0, 1] 사이의 값으로 정규화될 수 있도록 연령의 범위(range), 용돈의 범위로 맨하탄 거리(두 값 차이의 절대값)를 나누어주었습니다.


직업(job) 변수는 명목형(nominal) 변수이므로, 두 관측치의 값이 서로 같으면 거리는 '0', 서로 다르면 거리는 '1'이 됩니다. (유사성은 이와 반대임). 따라서 관측치 ID 1, ID 2, ID 3번이 모두 서로 간에 직업이 다르므로 관측치 쌍별 직업의 거리는 모두 '1'이 됩니다.


다음으로, 직업 만족도(job satisfaction)는 서열형(ordinal) 변수로서, 정규화한 순위(normalized rank)를 사용해서 [0, 1] 사이의 거리 값을 계산해줍니다.


마지막으로, 위의 혼합형(연속형, 이분형, 명목형, 서열형) 변수 5개(p=5)에 대해 두 관측치 간 각 변수별 거리를 계산한 값들을 평균하여 모든 변수를 종합하는 평균 거리를 계산하면,




입니다.


관측치 (ID 1번, ID 3번)이 평균 거리가 0.27 로서 (ID 1번, ID 2번)의 거리 0.54, (ID 2번, ID 3번)의 거리 0.62 대비 상대적으로 거리가 짧으므로 서로 유사하다고 평가할 수 있겠네요.


위의 이론적인 부분들을 R의 사용자 정의 함수로 표현해보면 아래와 같습니다.



# =======================================
# Distance measure for mixed variables
# : continuous, binary, ordinal, nominal
# =======================================


## 3 objects with variables of gender, age, allowance, job, and job_satisfaction
id <- c(1, 2, 3)
gender <- c('M', 'F', 'M')
age <- c(41, 24, 43)
allowance <- c(350000, 400000, 320000)
job <- c('consultant', 'designer', 'officier')
job_satisfaction <- c(4, 5, 3)


## range of continuous variable (age, allowance)

age_range <- 50
allowance_range <- 400000


## max rank of ordinal variable (job satisfaction)

max_rank <- 5

## Distance for Binary variable
dist_binary <- function(xi, xj){
  d = 0
  if (xi != xj){d = 1}
  return(d)
}

## Distance for Continuous variable
dist_continuous <- function(xi, xj, x_rng){
  d = abs(xi - xj)/x_rng
  return(d)
}

## Distance for Nominal variable
dist_nominal <- function(xi, xj){
  d = 0
  if (xi != xj){d = 1}
  return(d)
}

## Distance for Ordinal variable
dist_ordinal <- function(xi, xj, max_rank){
  d = abs(xi-xj)/(max_rank-1)
  return(d)
}

## Average of Distance for Mixed variables
dist_avg <- function(xi_id, xj_id, age_range, allowance_range, max_rank){
  d_gender = dist_binary(gender[xi_id], gender[xj_id])
  d_age = dist_continuous(age[xi_id], age[xj_id], age_range)
  d_allowance = dist_continuous(allowance[xi_id], allowance[xj_id], allowance_range)
  d_job = dist_nominal(job[xi_id], job[xj_id])
  d_job_satisfaction = dist_ordinal(job_satisfaction[xi_id], job_satisfaction[xj_id], max_rank)
  d_all <- c(d_gender, d_age, d_allowance, d_job, d_job_satisfaction)
  d_avg = mean(d_all)
 
  # print for detailed information
  print(paste0("**==== Distance of ID", xi_id, " and ID", xj_id, " ====**"))
  print("-----------------------------------------")
  print(paste0("Distance of Gender (Binary):", d_gender))
  print(paste0("Distance of Age (Continuous):", d_age))
  print(paste0("Distance of Allowance (Continuous):", d_allowance))
  print(paste0("Distance of Job(Nominal):", d_job))
  print(paste0("Distance of Job Satisfaction(Ordinal):", d_job_satisfaction))
  print("-----------------------------------------")
  print(paste0("Average Distance of ID", xi_id, " and ID", xj_id, ": ", d_avg))
  print("-----------------------------------------")
 
  return(d_avg)
}

## Distance b/w ID 1 and ID 2
dist_avg(1, 2, age_range, allowance_range, max_rank)
# [1] "**==== Distance of ID1 and ID2 ====**"
# [1] "-----------------------------------------"
# [1] "Distance of Gender (Binary):1"
# [1] "Distance of Age (Continuous):0.34"
# [1] "Distance of Allowance (Continuous):0.125"
# [1] "Distance of Job(Nominal):1"
# [1] "Distance of Job Satisfaction(Ordinal):0.25"
# [1] "-----------------------------------------"
# [1] "Average Distance of ID1 and ID2: 0.543"
# [1] "-----------------------------------------"
# [1] 0.543


## Distance b/w ID 1 and ID 3
dist_avg(1, 3, age_range, allowance_range, max_rank)
# [1] "**==== Distance of ID1 and ID3 ====**"
# [1] "-----------------------------------------"
# [1] "Distance of Gender (Binary):0"
# [1] "Distance of Age (Continuous):0.04"
# [1] "Distance of Allowance (Continuous):0.075"
# [1] "Distance of Job(Nominal):1"
# [1] "Distance of Job Satisfaction(Ordinal):0.25"
# [1] "-----------------------------------------"
# [1] "Average Distance of ID1 and ID3: 0.273"
# [1] "-----------------------------------------"
# [1] 0.273


## Distance b/w ID 2 and ID 3
dist_avg(2, 3, age_range, allowance_range, max_rank)
# [1] "**==== Distance of ID2 and ID3 ====**"
# [1] "-----------------------------------------"
# [1] "Distance of Gender (Binary):1"
# [1] "Distance of Age (Continuous):0.38"
# [1] "Distance of Allowance (Continuous):0.2"
# [1] "Distance of Job(Nominal):1"
# [1] "Distance of Job Satisfaction(Ordinal):0.5"
# [1] "-----------------------------------------"
# [1] "Average Distance of ID2 and ID3: 0.616"
# [1] "-----------------------------------------"
# [1] 0.616

 



이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요! :-)



Posted by R Friend Rfriend

댓글을 달아 주세요

  1. 이소영 2020.12.30 10:23  댓글주소  수정/삭제  댓글쓰기

    블로그 잘 보고 있습니다.
    위에서 연속형 변수의 범위(range)라는게 뭔가요?? 표준화 거리에서의 분산(표준편차)를 의미하는건가요??

    • R Friend Rfriend 2020.12.30 10:39 신고  댓글주소  수정/삭제

      안녕하세요.

      연속형 범위의 범위는 range = max - min 값을 말하는 것이었습니다.
      이렇게 되면 맨하탄거리를 정규화한 dist(Xi, Xj) = |Xi - Xj|/(Xmax-Xmin) 의 값은 0~1 의 값으로 정규화가 되기 때문에, 다른 유형의 변수들(이분형, 명목형, 서열형)의 거리와 같이 '0~1' 사이 값으로 scale이 동일 구간으로 변환이 된 것이므로 어느 하나의 변수에 크게 영향을 좌지우지하지 않게 할 수 있습니다.

      본문에서는 연속형변수에 대해 맨하탄거리를 변수의 범위로 나누어 주어서 정규화해주었는데요,

      만약 연속형변수에 대해 표준화 유클리드거리나 마할라노비스거리 등을 사용하였다면 범주형 변수(이분형, 명목형, 서열형)의 거리와 scale을 [0, 1] 사이 값으로 맞추기 위해서 연속형 변수의 표준화 유클리드 거리나 마할라노비스 거리 계산된 값을 마지막에 [0, 1] 범위로 정규화( =(거리-거리min)/(거리max-거리min) )해주면 되겠습니다.

군집분석 연재하다가 다른 주제 포스팅하느라 잠시 옆길로 샌다는게... 시간이 참 많이 흘러서... 정말 오랜만에 군집분석(Clustering) 관련 포스팅하네요. ^^;

이전 포스팅에서는 연속형 변수에 대한 (비)유사성 측정 척도(https://rfriend.tistory.com/199)로서 맨하탄 거리(Manhattan distance), 유클리드 거리(Euclid distance), 표준화 거리(Standardized distance), 마할라노비스 거리(Mahalanobis distance) 등에 대해서 소개를 하였습니다.


그리고 범주형 자료에 대한 유사성 척도로서 자카드 거리, 코사인 거리, 편집거리 등에 대해서도 다루었는데요, 중복이 있긴 하지만 한번더 종합적으로 정리를 해보고, 연속형과 범주형 자료가 섞여있는 혼합 자료에 대한 유사성 측정하는 방법과 예도 소개할 겸 해서 이번 포스팅을 써봅니다.


이번 포스팅에서는 범주형 데이터(Categorical Data)로서 이분형 (binary), 서열형 (ordinal), 명목형 (nominal) 데이터에 대한 유사성 측정 척도를 소개하고, 다음번 포스팅에서는 연속형과 범주형 혼합 자료의 유사성 측정 방법에 대해 소개하겠습니다.


일반적으로 비유사성(Dis-similarity) 척도로서 거리(Distance)를 많이 사용하며, 거리가 짧을 수록 유사하고, 거리가 멀 수록 유사하지 않다고 평가합니다. 유사성(Similarity)은 비유사성(Dis-similarity) 척도인 거리의 역수 (=1-거리) 로 계산합니다. (본 포스팅에서는 유사성 척도, 비유사성 척도/ 거리가 수시로 번갈아가면서 사용을 하는데요, 혼돈하지 마시기 바랍니다.)


(1) 이분형 (이진형) 변수의 유사성 측정 (Similarity measures for Binary variable)

(2) 서열형 변수의 유사성 측정 (Similarity measures for Ordinal variable)

(3) 명목형 변수의 유사성 측정 (Similarity measures for Nominal variable)



(1) 이분형 (이진형) 변수유사성 측정 (Similarity measures for Binary variable)


범주형 자료 중에서 클래스로 두 개의 값 (보통 '0'과 '1', [0, 1] with 1 = identity) 만을 가지는 자료를 이분형 (이진형) 변수 (Binary variable) 라고 합니다. 


이분형 (이진형) 자료 변수에 대한 유사성 척도 (또는 비유사성 척도, 거리)로 Hamming distance (Simple matching), Jacard Co-efficient (Asymmetric binary attributes), Russel-Rao, Kulczynski-2, Ochiai measure, Dice similarity, Tanimoto similarity 등 여러가지 측정 척도가 있습니다. 이중에서 이번 포스팅에서는 Hamming distance, Jacard Co-efficient 에 대해서 자세히 설명하겠습니다.



(1-1) Hamming distance (Simple matching)


정보이론에서 Hamming distance 는 같은 길이의 두 문자열(two strings of equal length)을 대상으로 대응하는 기호가 서로 다른 위치의 개수를 말합니다. 다른말로 하면, 하나의 문자열을 다른 문자열과 동일하게 하기 위해 변경시켜야만 하는 최소한의 문자열 대체 회수를 의미합니다.


Hamming distance는 두개의 순열 사이의 편집거리(edit distance)를 측정하는 여러가지 문자열 측정 지표 중에서 하나입니다. Hamming distance는 미국의 수학자인 Richard Hamming의 이름을 따서 지어진 이름입니다.


Hamming distance function단순 매칭 계수 (Simple Matching Coefficient) 라고도 하며, 값이 다른 경우의 비율을 의미합니다.


관측치의 k번째 변수가 이진형 자료일 때, 단순 매칭 방법은 두 변수의 값이 같으면 1, 다르면 0으로 표현합니다.



따라서 이 변수가 0과 1로 치환되어 있다면 단순매칭에 의한 유사성은 아래처럼 표현할 수 있습니다.



p개의 이분형(이진형) 변수를 가지는 두 개의 관측치의 값을 비교하여 집계한 분할표(contingency table)를 작성하면 아래의 표와 같이 표현할 수 있습니다.



이 분할표에 대해서 해밍 거리(Hamming distance), 또는 단순 매칭 계수 (Simple matching coefficient) 는 서로 다른 값을 가지는 변수 개수의 비율이므로 다음의 식으로 표현할 수 있습니다. (거리는 dist() 또는 d() 로 표기합니다.)



반대로, 단순 매칭에 의한 유사성은 서로 같은 값을 가지는 변수 개수의 비율이므로 위의 식에서 분자가 바뀐 아래의 식으로 표현할 수 있습니다. (유사성은 sim() 으로 표기합니다.)





(1-2) Jacard Co-efficient (Asymmetric binary attributes)


자카드 거리는 어느 하나의 상태가 다른 상태보다 더 중요하거나 더 값진 비대칭(asymmetric) 인 경우에 사용합니다. 편의상 상태 '1'을 더 중요하거나 값진 상태 (일반적으로 드물게 발생하고 희소한 상태) 를 나타낼 때 사용합니다.


위의 해밍 거리 (또는 단순 매칭 계수)에서는 두 관측치 Xi, Xj의 분할표에서 a, b, c, d 의 모든 경우를 포함하였다면, Jacard Co-efficient 는 두 관측치 Xi, Xj 가 모두 '0'인 'd'의 경우는 무시하고 나머지 a, b, c 만을 가지고(비대칭적으로) 비유사성인 거리나 혹은 유사성을 측정하게 됩니다.





(자카드 거리 계수, 자카드 유사성 척도에서는 분모에서 모두가 '0'인 d 는 무시되어 빠져있습니다.)




위의 해밍 거리(Hamming distance)와 자카드 계수 (Jacard coefficient) 를 3명의 사람에 대해 증상을 진단한 6개의 변수를 가진 간단한 예를 들어서 계산을 하여 비교해보겠습니다.




위의 이분형 변수 자료를 Feaver, Cough 증상이 Y(Yes)인 경우는 1, N(No)인 경우는 0으로 치환하고, Test-1 ~ Test-4에서 P(Positive)인 경우는 1, N(Negative)인 경우는 0으로 치환하면 아래와 같은 자료를 얻습니다. 


그리고 이 자료를 사용하여 Lee와 Jung, Lee와 Hong, Jung과 Hong 별 쌍의 분할표(contingency table)를 작성합니다.


마지막으로 위의 (1)과 (2)에서 소개한 해밍 거리(Hamming Distance), 자카드 계수(Jacard Co-efficient) 공식에 분할표의 값을 대입해주면 됩니다.




거리가 작을 수록 더 관측치 간에 두 유사하다고 평가할 수 있으므로, Hamming distance와 Jacard Co-efficient 모두 가장 작은 Lee와 Jung의 두 명의 환자가 다른 두 쌍의 환자들 보다 더 유사하다고 판단할 수 있겠네요.


물론, 이번 예제의 경우 증상이 있고(Y)/없고(N), 테스트 결과의 양성(P)/음성(N)을 다룬, 변수의 값의 중요성이 다른 비대칭적(asymmetric)인 자료에 해당하므로 Jacard Co-efficient 를 사용하는게 더 적합하겠네요.




  (2) 서열형 변수의 유사성 측정 (Similarity measures for Ordinal variable)


서열형 척도(Ordinal scale)는 1 < 2 < 3 < 4 < 5 처럼 "순서(Order)가 있는" 범주형 자료의 척도를 말합니다. 예를 들면, 설문조사를 할 때 '1 (매우 불만족) < 2 (다소 불만족) < 3 (보통) < 4 (다소 만족) < 5 (매우 만족)' 과 같이 만족도를 조사하는 문항의 척도라든지, '-2 (매우 동의하지 않음), -1 (동의하지 않음), 0 (무관심), 1 (동의함), 2 (매우 동의함)' 과 같은 비교 지수, 또는 우선순위 rank,  배열 순서 등에서 서열형 척도를 사용합니다.


서열형 변수의 유사성을 측정하는 방법에는 Normalized Rank Transformation, Spearman Distance, Footrule Distance, Kendall Distance, Cayley Distance, Hamming Distance, Ulam Distance, Chebyshev/ Maximum Distance, Minkowski Distance 등 여러가지가 있습니다.


이중에서 이번 포스팅에서는 이해하기에 직관적이고 계산이 간편해서 많이 사용되는 Normalized Rank Transformation 방법을 소개하겠습니다.


등급이나 순위 등의 질적 변수(qualitative variable)인 서열형 변수는 정규화(normalization)를 통해서 양적 변수(quantititive variable)로 변환할 수 있습니다. 일단 정규화를 통해 서열형 변수를 양적변수로 변환을 하고 나면, 양적변수의 거리 계산 방법을 사용하는 원리입니다.


서열형 척도로 관측된 두 관측치의 거리를 계산하기 위해 다음의 두 단계를 거쳐서 변환을 하고, 이어서 연속형 변수에서 사용하는 거리 계산(가령, 유클리드 거리)을 하면 됩니다.



(a) 순서형 값(ordinal value)을 순위(rank)로 변환 (이때 순위(rank) r = 1 to R)

(b) 순위(rank)를 [0, 1] 사이의 값을 가지도록 정규화 (normalization)

    

(c) 정규화된 서열형 변수 X 에 대하여 연속형 변수 거리 계산 함수 적용하여 거리 계산

  p 개의 서열형 변수가 있다고 했을 때,


  • 유클리드 거리 (Euclidean distance)


  • 맨해턴 거리 (Manhattan distance)



서열형 변수의 유사성(similarity)비유사성 척도인 거리의 역수 개념이므로 1 에서 거리를 빼주어서 계산합니다.




매장 별 고객만족도를 -2 (매우 불만족) < -1 (불만족) < 0 (보통) < 1 (만족) < 2 (매우 만족) 의 5단계 서열형 척도로 설문조사한 자료가 있다고 해보겠습니다. 아래의 예처럼 Shop A, B, C 의 3개 매장에 대해서 설문문항 S1, S2, S3 의 3개 질문항목을 조사했다고 했을 때 각 매장별 거리를 구해보겠습니다.







  (3) 명목형 변수의 유사성 측정 (Similarity measures for Nominal variable)


명목형 변수는 (서열형 변수와는 다르게) "순서(Order)가 없는" 범주형 자료를 말합니다.


명목형 변수의 유사성은 두 변수의 값이 같으면 1, 다르면 0으로 평가합니다.




따라서 p개의 명목형 변수가 있다고 했을 때, 두 관측치에서 m개의 변수 값이 서로 같다면 거리와 유사성은 아래와 같습니다. (즉, Hamming distance 와 동일)






다음번 포스팅에서는 혼합형 변수의 유사성 (혹은 비유사성 거리)을 평가하는 방법과 R 로 유사성 혹은 거리를 계산하는 방법/ 코드 (https://rfriend.tistory.com/584)를 소개하겠습니다.



[Reference]

* Hamming distance: https://en.wikipedia.org/wiki/Hamming_distance

* Jacard Coefficient similarity
 : https://t4tutorials.com/jaccard-coefficient-similarity-measure-for-asymmetric-binary-variables/

* Normalized rank for ordinal data
 : https://people.revoledu.com/kardi/tutorial/Similarity/Normalized-Rank.html

* 전치혁 저, "데이터마이닝 기법과 응용", 한나래



이번 포스팅이 많은 도움이 되었기를 바랍니다.

행복한 데이터 과학자 되세요! :-)



Posted by R Friend Rfriend

댓글을 달아 주세요

  1. R초보 2020.12.07 06:51 신고  댓글주소  수정/삭제  댓글쓰기

    r에대해 초보다보니 포스팅 잘보고 갑니다. 혹시 purrr에 대해서도 궁금한데 포스팅 해주시면 감사할것같아요 ㅎㅎ map함수 apply 함수들같은거요

    • R Friend Rfriend 2020.12.07 15:52 신고  댓글주소  수정/삭제

      안녕하세요.

      이미 purrr 패키지까지 알고 계신거라면 R 초보가 아니실거 같습니다. ^^

      포스팅하고 싶은 주제는 너무나 많은데 직장인이다 보니 항상 시간이 없어서 제대로 포스팅을 못하고 있습니다.

      purrr 도 매우 유용한 패키지이니 언젠가는 포스팅을 하고 싶기는 한데요, 그게 언제가 될지는 잘 모르겠습니다.

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


 - 자카드 거리 (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 Rfriend

댓글을 달아 주세요

예전 포스팅에서는 연속형 변수들 간의 거리를 측정하는 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

 



위의 코사인 거리 계산 결과를 세로로 긴 형태 (long format) 로 저장하려면 아래의 for loop 문과 indexing을 사용한 코드를 참고하시기 바랍니다.



n <- ncol(cosine_dist_Doc_mat) # number of columns
col_nm <- colnames(cosine_dist_Doc_mat) # column names
r <- 1 # row position number
cosine_dist_long <- data.frame() # blank data.frame to store the results

for (i in 1:(n-1)) {
  for (j in (i+1):n){
    cosine_dist_long[r, 1] <- col_nm[i]
    cosine_dist_long[r, 2] <- col_nm[j]
    cosine_dist_long[r, 3] <- cosine_dist_Doc_mat[i, j]
    r <- r+1
  }
}

cosine_dist_long
# V1    V2        V3
# 1 Doc_1 Doc_2 0.5668373
# 2 Doc_1 Doc_3 0.5668373
# 3 Doc_2 Doc_3 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 Rfriend

댓글을 달아 주세요

  1. 소셜 그래프게임 2017.06.26 16:41  댓글주소  수정/삭제  댓글쓰기

    흐미 한 7번 읽으니까 이해되네요
    아 진짜..할수록 어려운 개념들이 나오니 힘드네요
    잘보고 갑니다!

  2. ks 2021.01.29 18:12  댓글주소  수정/삭제  댓글쓰기

    안녕하세요? 주인장님, 궁금한게 있어서 답글 남겨요.
    코사인 거리가 행렬로 표현이 되었는데 혹시 아래처럼 보여질 방법이 있을까요?
    doc1 doc2 0.566
    doc1 doc3 0.566
    doc2 doc3 0.000

    • R Friend Rfriend 2021.01.29 21:45 신고  댓글주소  수정/삭제

      안녕하세요 ks님,

      질문하신 내용에 대해서 블로그 포스팅의 본문에 for loop 문을 사용한 코드를 추가하였습니다. 위의 본문 참고하시기 바랍니다.

    • ks 2021.01.30 06:44  댓글주소  수정/삭제

      감사합니다. 그간 작성하신 내용으로 공부 중인데 큰 도움이되요~

연속형 변수에 대한 비유사성 측도(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 Rfriend

댓글을 달아 주세요

지난번 포스팅에서는 분할적 군집화(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 Rfriend

댓글을 달아 주세요

  1. 임수형 2020.05.25 14:23  댓글주소  수정/삭제  댓글쓰기

    감사합니다. 대학온강으로 데이터마이닝 듣는데 개념 도움이 많이 되네요

  2. DS 2020.06.11 11:54  댓글주소  수정/삭제  댓글쓰기

    블로그가 정말 정리가 잘되어있네요! 계층적 군집을 활용할지 분할적 군집을 활용하지 결정하는 것은 업의 경험에 기반하여 군집의 계층 유무에 대한 가설을 잡고 가는건가요? 비즈니스 특성상, 군집에 계층 있을 것 같다는 등의..

    • R Friend Rfriend 2020.06.11 12:56 신고  댓글주소  수정/삭제

      안녕하세요.
      블로그 좋게 봐주셔서 감사합니다. :-)

      계층적 군집분석과 분할적 군집분석 중 어느것을 사용할지는 결정할 때 말씀하신 것처럼 업의 경험에 기반한 계층 유무에 대한 가설도 중요합니다.

      그리고 분석 목적이 계층적 구조에 대한 탐색이 필요한지, 계층의 수준과 군집의 개수를 유연하게 선택하는게 필요한지도 중요한 고려요인이 될 것입니다.

      그리고 또 하나 고려할게 데이터 크기 입니다. 데이터 크기가 너무 크면 계층적 군집분석을 하기가 힘들어지고, 나중에 덴드로그램으로 시각화하기도 힘들어지기 때문에 빅데이터라면 어쩔 수 없이 분할적 군집분석을 해야하는 경우도 있습니다.