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