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

댓글을 달아 주세요

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

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

  2. Tamy 2021.04.22 01:22  댓글주소  수정/삭제  댓글쓰기



    혹시 STING 군집 분석 한번 다루어 주실 수 있을 까요?
    무지 하게 많이 다 찾아 보는데 번역이 불가능 한 부분이 많이 있어 애먹네요 ㅠㅠ

    더구나 .. 비전공(체대생)이라 어렵네요..
    이곳에서 많은 정보로 받고 있어 혹여 블로그 주인님은 혹시 저보다 더 잘 설명해 줄 것 같아 남겨 봅니다.

    • Rfriend 2021.04.22 10:33 신고  댓글주소  수정/삭제

      안녕하세요 Tamy님.

      먼저, 제 블로그 좋게 봐주셔서 감사드립니다.

      제가 직장인이다보니 요즘에 너무 바빠서 블로그 포스팅을 자주 못하고 있습니다. 제가 STING 군집분석 알고리즘에 대한 포스팅을 언제 작성할 수 있을지 말씀을 못드리겠네요. 죄송합니다. ㅜ_ㅜ

  3. 곰돌이청청 2021.05.12 15:36  댓글주소  수정/삭제  댓글쓰기

    안녕하세요.^^ DBSCAN 좋은 포스팅 감사드립니다

    k-dist graph 작성하신 글에 대하여 제가 이해한 것이 맞는지 여쭙고 싶습니다.

    "sorted k-dist graph 를 그리는 방법은, 먼저 MinPts 를 k개라고 했을 때, 하나의 점으로부터 k개의 가장 가까운 점들 간의 거리, 즉 k_NN (k-Nearest Neighbor)의 거리 k-dist...."

    이 부분에서 질문이 있습니다. k=3이라고 하였을 때, 3-dist 값은 어떤 data point에서 3번째로 가까운 점과의 거리를 의미하는 것이 맞는것이지요^^ㅎㅎ



    • Rfriend 2021.05.16 20:08 신고  댓글주소  수정/삭제

      안녕하세요.

      생각하고 계신 것이 맞습니다. k=3 이라고 했을 때 3-dist 값은 3번째로 가까운 점과의 거리를 의미합니다.

      댓글이 한참 늦어서 죄송합니다. 프로젝트 하는 중에 핸드폰으로 댓글 질문을 보기는 했는데요, 퇴근하고 깜빡했습니다. ^^;

  4. 동짓 2022.02.14 16:16  댓글주소  수정/삭제  댓글쓰기

    선생님 안녕하세요!

    게시물 보고 질문이 있어 댓글 드립니다. :)

    혹시 군집분석 및 DBSCAN 분석 수행 시 set.seed = 난수를 설정해주는 이유가 있을까요?

    또한 난수의 수를 1004개로 지정하셨는데 그 이유가 있을까요?

    감사합니다!

  5. 동짓 2022.02.14 16:16  댓글주소  수정/삭제  댓글쓰기

    선생님 안녕하세요!

    게시물 보고 질문이 있어 댓글 드립니다. :)

    혹시 군집분석 및 DBSCAN 분석 수행 시 set.seed = 난수를 설정해주는 이유가 있을까요?

    또한 난수의 수를 1004개로 지정하셨는데 그 이유가 있을까요?

    감사합니다!

    • Rfriend 2022.02.14 19:41 신고  댓글주소  수정/삭제

      안녕하세요.

      K-means 군집분석을 예로 들면, “초기 k개의 중심점을 임의를 난수를 발생”시켜서 생성한 후에 관측치들간의 거리를 계산해서 그룹핑과 재할당, 중심점 재계산 등의 반복 작업을 진행하면서 수렴할때까지 반복합니다. 초기 난수를 발생시킬때 set.seed 로 초기값을 부여해주면 매번 실행할때마다 동일한 난수를 발생시킬수 있어서 동일한 결과를 보장받을 수 있습니다. 이것을 재현가능성(reproducibility)라고 합니다.
      난수 초기값은 아무 숫자나 입력해주면 됩니다. 저는 “1004”가 한국어 발음으로 “천사”여서 그냥 습관적으로 써요. 아무 숫자나 가능합니다.

    • 동짓 2022.02.15 16:41  댓글주소  수정/삭제

      아 동일한 결과값을 보장하기 위함이였군요 ㅠㅠ
      감사합니다!!