DBSCAN 이해해보기

Clustering 관련 공부를 하다가 간단한 clustering 방법 중 하나인 DBSCAN에 대해서 글을 써보려고 한다.

요즘 구글링 해서 글을 찾아 읽는 것보다, 유튜브에서 잘 설명된 영상을 (존재한다면) 보고 공부하는 것을 선호한다.

이번 포스트는 이 영상을 보고 이해한대로 정리한 내용이다.

매우 매우 이해하기 쉽게 정리해주셨기 때문에 저 영상을 보는 것을 추천한다.

---

DBSCAN은 밀도 기반 군집화(density-based clustering)의 방법 중 하나이다. 밀도가 높은 곳에 클러스터를 형성하고, 밀도가 낮은 곳에는 클러스터를 형성하지 않고 해당 위치에 존재하는 점들을 outlier로 취급하게 된다.

다양한 클러스터링 방법들이 있는데, 가장 대표적인 k-means clustering과 DBSCAN을 비교했을 때 가장 큰 차이점 두 가지는 :

1. DBSCAN은 임의의 모양으로 클러스터를 형성할 수 있다. 반면에 K-means clustering은 원형으로만 클러스터가 형성된다.

2. DBSCAN에서는 어떤 클러스터에도 포함되지 않는 점들이 존재할 수 있다. (위에 설명에서 말한 outlier 또는 noise)

---

ε-neighborhood 

N_ε(p) 라고 정의하는데 , 간단하게 설명하면 p라는 점이 있을 때 p에서 최대 ε 만큼 떨어져 있는 모든 점들의 집합을 의미한다. p를 원의 중심이라고 하고, 원의 반지름이 ε일 때, 해당 원 안에 존재하는 모든 점들을 p의 ε-neighborhood라고 정의한다. 이때, 원의 중심에 위치하는 (여기서는 p) 점을 core point라고 정의하고, core point를 제외하고 원 안에 존재하는 (ε-neighborhood에 포함된) 점들을 모두 boarder point라고 정의한다. 

Directly Density-Reachable (DDR)

점 p가 점 q로부터 directly density reachable 하기 위해서는 다음과 같은 조건을 만족해야 한다 :

1. p가 q의 ε-neighborhood에 포함되어 있어야 한다.

2. N_ε(q) 의 크기가 사용자가 지정한 minimum point 보다 크거나 같아야 한다. = ε-neighborhood의 밀도가 높아야 한다.

이때, p와 q가 모두 core point라면 DDR는 symmetric 하지만, 한 점만 core point이고, 나머지 점이 boarder point인 경우 symmetric하지 않게 된다. 

Density Reachable (DR)

p_1, p_2, p_3, 총 3개의 점이 존재한다고 했을 때, p_2는 p_1으로부터 DDR이고, p_3는 p_2로부터 DDR이지만, p_3는 p_1로부터 DDR이 아닌 경우를 생각해보면, p_1에서부터 p_2, p_2에서 p_3로 DDR로 확장해 나갈 수 있다. 이런 경우 p_1과 p_3는 density reachable 하다고 정의할 수 있다.

이런 느낌?

Density Connected

마지막 개념. 점 p, v, q가 있다고 가정해 보자. 점 p가 점 v로부터 DR 이고, 점 q가 점 v로부터 DR 인 경우, 점 p와 점 q는 Density Connected라고 할 수 있다. 이때, p와 q가 boarder point라면 역이 성립하지 않는다. 그러므로 v가 p로부터 DR 이 성립하지 않고, v가 q로부터 DR 또한 성립하지 않는다. 

이런 느낌?

DBSCAN

위에서 설명한 개념들을 이해했다면 실제 DBSCAN 이 동작하는 방식은 매우 간단하다. 임의의 점에서 시작해서 Density Connected 된 점들을 모두 연결해서 하나의 클러스터를 구성한다. 더 이상 Density connected 된 점이 없다면, 접근하지 않은 다른 점으로 이동해서 동일한 작업을 반복한다. 

Density connected 되기 위해서는 ε-neighborhood 에 사용자가 지정한 만큼 충분히 많은 점들이 존재해야 하므로, 주변에 충분히 많은 점들이 없는 경우 (밀도가 낮은 경우), 클러스터를 구성하지 못하고 outlier 또는 noise로 구분하게 된다. 

추가적으로, DBSCAN은 어느 점에서 시작하던 상관없이 동일한 결과를 제공하게 된다. 

앞에서 이미 많이 언급했지만, DBSCAN을 수행하기 위해서는 2가지 파라미터를 사용자가 지정해줘야 하는데, 첫 번째는 ε-neighborhood를 구성하기 위한 ε의 크기와, ε-neighborhood를 만족시키기 위한 minimum point 를 지정해줘야 한다. 

많이 사용되는 예시

DBSCAN을 설명할 때 많이 사용되는 예시이다. 그림을 보면 각 색마다 클러스터를 형성했고, 색에 포함되지 않는 점들을 outlier로 분류된다.