DBSCAN 차근차근 이해하기

이 글이 도움되셨다면 광고 클릭 부탁드립니다 : )

오늘은 클러스터링 방법 중에 널리 사용되는 DBSCAN에 대해 정리해보겠습니다.
성능이 괜찮다하니 그냥 무작정 코드만 갖다 쓰다가 이건 왜 predict가 안되는 걸까 의문이 생겨 DBSCAN이 어떻게 군집을 형성하는지 찾아보았는데요. 작은 개념부터 차근차근 살펴보도록 하겠습니다.

---

0. DBSCAN?!

DBSCAN(Density-based spatial clustering of application with noise) 이름 그대로 밀도기반 클러스터링 방법 입니다.
비계층적 군집화 방법에는 크게 distance-based 방법과 density-based 방법이 있는데, 군집분석을 하면 가장 처음 접하는 k-means clustering은 distance-based 방법이고 DBSCAN은 density-based 방법에 속한다고 볼 수 있습니다.

 

1. Ideas

DBSCAN은 두 가지 아이디어로 시작하게 됩니다. 아래 두가지 아이디어를 바탕으로 DBSCAN은 밀도가 높은 포인트들을 을 군집으로 묶고 밀도가 낮은 포인트를 노이즈로 분류하는 방향으로 각 step이 진행됩니다.

1. 군집은 밀도가 높은 데이터 집합이다.
2. 노이즈 포인트들의 밀도는 굉장히 낮을 것이다.

2. Definitions

DBSCAN을 이해하는데 필요한 parameter와 개념에 대해 살펴보겠습니다.

Parameters

• $\epsilon$ : 데이터 포인트에서의 반경
• $minPts$ : 군집 생성에 필요한 최소 데이터 포인트 수

 

Directly density reachable

q는 p로부터 directly density reachable하다는 정의는 1) q는 p의 $\epsilon$ 반경이내에 존재(reachability, 서로 연결됨) 2) p는 $\epsilon$ 반경이내 minPts보다 많은 데이터 존재(core point condition, 높은 밀도) 를 의미합니다.
만약 q와 p 모두 core point이면 symmetric하게 directly density reachable 하게 됩니다.

Density reachable

q는 p로부터 density reachable하다는 것은 directly density reachable한 r과 같은 포인트의 체인으로 연결된다는 것을 의미합니다. 위 그림에서 r은 p로 부터 directly density reachable하고 q는 r로부터 directly density reachable 하니, q는 p로부터 density reachable하게 됩니다.

Density connected

q는 p로부터 density connected하다는 것은 q와 p사이의 어떤 o 라는 point로 부터 각 각 density reachable하다는 의미입니다. 이런 개념이 필요한 이유는 p와 q는 둘 다 border point($\epsilon$ 반경이내 minPts보다 적은 데이터 존재)라서, density reachable만으로는 양쪽의 border point를 연결할 수가 없기 때문에(o는 p로부터 density reachable하지 않음) connected 개념이 필요하다고 합니다.

위와 같은 reachability와 connectivity 컨셉을 바탕으로 cluster와 noise를 정의하게 됩니다.

3. Algorithmic steps for DBSCAN

A cluster C w.r.t. ε and MinPts is a non empty subset of D (the whole set of objects or instances) satisfying
Maximality - For all objects p, q ε D : if p ε C and if q is density-reachable from p w.r.t ε and MinPts then q ε C.
Connectivity - For all objects p, q ε C : p is density-connected to q w.r.t. ε and MinPts.

DBSCAN은 어떠한 임의의 점을 시작으로 density reachable될 수 있는 점을 점차 확대해나가며 cluster를 형성합니다. 그러다가 더이상 density reachable될 수 있는 점이 없으면 clustering을 멈추고, 새로운 점으로 이동해 새로운 cluster를 만들고 위의 작업을 반복하고 어디에도 포함되지 않는 데이터 포인트들은 noise로 취급합니다.

step 별로 살펴보면,

1. 임의로 point p를 하나 선정한다.
2. p로부터 density reachable한 모든 point q를 찾는다.
3. p가 core point인 경우, cluster를 형성한다.
4. p가 border point인 경우, density reachable한 점이 없기 때문에 다른 point로 새 시작한다.
5. 위 step을 반복한다.

 

4. Advantages & Disadvantages

장점

1. 임의의 형태의 클러스터를 찾을 수 있다
- k-means와 같은 거리기반 방법은 중심을 기준으로 원 형태로 군집형성하는 경향을 보임
2. 어떤 클러스터에도 할당되지 않는 값(noise)가 존재한다.
3. 클러스터 개수를 사전에 정해주지 않아도 된다.

단점

1. 정해줘야하는 parameter는 여전히 존재한다.
2. 다른 밀도의 군집이 존재하면 밀도가 높은 군집만 생성되고 상대적으로 밀도가 낮은 군집은 노이즈처리하는 경향이 있다.

5. Python

python에서 sklearn.cluster 모듈을 활용하면 손쉽게 DBSCAN 방법론을 적용해볼 수 있습니다.
자세한 내용은 아래 scikitlearn 페이지 참고 부탁드립니다.
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

sklearn.cluster.DBSCAN

 

---

참고한 사이트
https://www.geeksforgeeks.org/ml-dbscan-reachability-and-connectivity/

ML | DBSCAN reachability and connectivity - GeeksforGeeks

https://laptrinhx.com/cluster-analysis-with-dbscan-density-based-spatial-clustering-of-applications-with-noise-2247351631/

Cluster Analysis with DBSCAN : Density-based spatial clustering of applications with noise

https://sites.google.com/site/dataclusteringalgorithms/density-based-clustering-algorithm

Data Clustering Algorithms - Density based clustering algorithm