[ML] 밀도 기반 클러스터링(DBSCAN, density-based spatial clustering of applications with noise)

---

밀도 기반 클러스터링 (DBSCAN)

 

K-평균과 계층적 클러스터링은 거리를 기반으로 클러스터링을 했다면 DBSCAN은 밀도를 기반으로 클러스터링을 한다. 데이터의 밀집 영역(dense region) 내에서 그룹을 찾는 것이다. 밀도가 낮은 샘플은 노이즈로 간주하는 특징이 있다.

먼저 몇가지 개념을 알아야 하는데 $ \epsilon $-이웃($\epsilon$-neighborhood)은 각 샘플 $ x $ 에 대해 반경 $ \epsilon $ 이내에 있는 이웃 샘플들의 집합이다. 즉 $ \epsilon $ 은 이웃을 결정하는 거리이다. 최소샘플 수(minPts)는 이웃 내 최소 점 개수이다.

DBSCAN은 각 샘플에 특별한 레이블을 부여한다. 핵심점(core point)은 자신의 $ \epsilon $-이웃 크기가 최소 샘플 수 이상인 샘플이다. 경계점(border point)은 핵심점의 $ \epsilon $- 이웃 안에 있으나 자신은 핵심점 조건을 만족하지 못하는 샘플이고, 노이즈(noise)는 핵심점의 $ \epsilon $-이웃에도 속하지 않는 샘플로 클러스터에 속하지 않는다.

절차는 다음과 같다.

1. 아직 방문하지 않은 샘플 $ x $ 하나를 선택하여 $ \epsilon $-이웃을 탐색한다.
2. $ \epsilon $-이웃 크기가 최소샘플 수(minPts) 이상이면 새로운 클러스터를 생성하고, 그 샘플을 핵심점으로 클러스터에 추가한다.
3. 핵심점의 $ \epsilon $-이웃에 있는 모든 이웃 샘플을 클러스터에 할당하고 이웃 중 새로운 핵심점이 있으면 그 이웃까지 확장한다. 즉 밀도 도달 가능(density-reachable)한 샘플들을 수집한다.
4. $ \epsilon $-이웃 크기가 최소샘플 수(minPts) 미만이면 해당 샘플을 노이즈로 표시하나, 나중에 다른 핵심점의 이웃으로 포함될 수 있다.
5. 모든 샘플이 방문되어 클러스터 확장이 완료될 때까지 1-4를 반복한다.

클러스터 모양에 제약이 없다. 즉 임의 형태(arbitary shape) 클러스터를 발견할 수 있다. 덕분에 K-평균과 다르게 아래와 같은 클러스터를 효과적으로 분리하며, 노이즈 역시 처리한다. 또한 K-평균과 다르게 클러스터 개수를 사전에 정의할 필요가 없다.

참고로 K-평균으로 클러스터링하면 다음과 같이 분할된다.

단 $ \epsilon $ 과 최소샘플 수(minPts) 파라미터 설정에 민감하고, 데이터 밀도가 크게 다른 영역이 섞여 있을 경우 적절한 파라미터를 찾기 어렵다. 고차원 데이터에서는 거리 기반 탐색 비용이 크고, 밀도 차이가 완화되어, 즉 차원의 저주가 있어 성능이 떨어질 가능성이 높다.