ML/Clustering DBSCAN

Posted on | In

[ML/Clustering] DBSCAN (Density Based Spatial Clustering of Applications with Noise)

DBSCAN은 간단하고 직관적인 알고리즘으로 되어 있음에도 데이터의 분포가 기하학적으로 복잡한 데이터 세트에도 효과적인 군집화가 가능하다. 원모양을 가진 데이터 세트를 군집화를 수행할때 유용하다.
특정공간내에 데이터 밀도 차이 기반 알고리즘을 이용해 복잡한 기하학적 분포도를 가진 데이터 세트에서도 군집화를 잘 수행한다.

✔ 군집화가 어떻게 진행되는지 자세히 알아보자
특정 입실론 반경내에 포함될 최소 데이터 세트를 6개로 가정하자

  1. 1번 데이터를 기준으로 입실론 반경내에 포함된 데이터 7개(자신포함)로 최소 6개 이상을 만족하므로 1번 데이터는 CorePoint다.

  2. 다음으로 2번 데이터 역시 입실론 반경내에 7개 데이터를 가지고 있으므로 CorePoint다.
    CorePoint의 이웃 데이터가 CorePoint인 경우, 직접 접근이 가능하다.

  3. 특정 Core Point에서 직접 접근이 가능한 다른 Core를 서로 연결하면서 군집화를 구성한다.
    이렇게 점차적으로 근집 영역을 확장해나가는것이 DBSCAN이다.

  4. 3번째 데이터의 경우 입실론 반경내에 최소 데이터를 가지고 있지 않고 이웃데이터로 핵심데이터를 가지고 있기에 Border Point다. 그리고 5번데이터의 경우 핵심포인트 또한 이웃데이터로 가지고 있지 않기에 Noise Point라 한다.

DBSCAN은 이처럼 입실론 주변 영역의 최소 데이터를 포함하는 밀도 기준을 충족하는 CorePoint를 연결하면서 군집화를 구성한다.

입실론 영역 내에 포함되는 최소 데이터 개수를 충족시키는가 아닌가에 따라 데이터 포인트를 다음과 같이 정의한다.

  • 입실론 주변영역 (epsilon)
    개별 데이터를 중심으로 입실론 반경을 가지는 원형의 영역

  • 최소 데이터 개수 (min points)
    핵심포인트가 되기 위해 입실론주변영역에 포함되어야하는 데이터 최소 개수(자신 포함)

  • 핵심포인트 (Core Point)
    주변 영역내에 최소 데이터 개수 이상의 타 데이터를 가지고 있을 경우 해당데이터를 핵심포인트라고 한다.

  • 이웃포인트 (Neighbor Point)
    주변 영역 내에 위치한 타 데이터를 이웃 포인트라고 한다.

  • 경계포인트 (Border Point)
    주변 영역 내에 최소 데이터 개수 이상의 이웃포인트를 가지고 있지않지만 핵심포인트를 이웃포인트로 가지고있는데이터를 경계포인트라고한다.

  • 잡음포인트 (Noise Point)
    최소 데이터개수 이상의 이웃포인트를 가지고 있지 않으며, 핵심포인트도 이웃포인트로 가지고 있지않는 데이터를 잡음 포인트라고 한다.

Tutorial

DBSCAN의 경우 다른 군집알고리즘과 다르게 노이즈(-1 label)를 뱉는다.
원형 데이터에서 성능이 매우 좋다. iris dataset을 clustering 했을때와 원형 데이터를 clustering 했을때 확연한 성능차이가 난다.

1
2
3
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.6,min_samples=8,metric='euclidean')
dbscan_label = dbscan.fit_predict(iris.data)

Practice

Reference

  • 파이썬 머신러닝 완벽가이드 서적