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

지난번 포스팅에서는 공간데이터에 대하여 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

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

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개 군집과 잡음들로 구성이 되어있습니다.

다음으로 위에서 설명했던 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 가 조금씩 커지기는 하는데요, 큰 차이는 없네요.)

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

이외에도 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

이번 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 군집화 (예시)

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)으로 도달가능, 연결가능을 평가하면서 진행이 됩니다.

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

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 한 패키지이구요.

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

## 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개 관측치를 샘플링해서 그 관측치들이 무슨 군집으로 할당이 되었는지 프린트해보았습니다.

각 클러스터별로 요약통계량 (가령, 평균)을 계산해서 profiling 해보면 클러스터의 특징을 파악하는데 많은 도움이 될 것입니다. 아래 코드는 dplyr 패키지의 group_by() 와 summarise() 함수를 사용해서 각 DBSCAN Cluster 별로 x, y 변수의 평균을 구해본 것입니다. 

# summary statistics by Cluster membership
library(dplyr)
df %>% 
  group_by(db$cluster) %>% 
  summarise(x_mean = mean(x, rm=TRUE), 
            y_mean = mean(y, rm=TRUE))

# `db$cluster`   x_mean  y_mean
# <dbl>    <dbl>   <dbl>
#   1            0  0.0604  -1.10  
# 2            1  0.00419 -0.0394
# 3            2  0.00275 -0.0119
# 4            3 -0.754   -2.01  
# 5            4 -0.669   -2.99  
# 6            5  0.991   -2.50

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

(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 를 결정하는 휴리스틱 방법을 소개하겠습니다.

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

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