[데이터 마이닝] DBSCAN과 밀도 기반 클러스터링

1. 밀도 기반 클러스터링 (Density-based clustering)

클러스터링 알고리즘은 크게 중심 기반 (center-based) 알고리즘과 밀도 기반 (density-based) 알고리즘으로 나눌 수 있다. 중심 기반 알고리즘의 가장 대표적인 것으로는 k-means clustering이 있으며, 밀도 기반 알고리즘에는 DBSCAN$^{[1]}$이 있다.

중심 기반 클러스터링 알고리즘은 "동일한 클래스에 속하는 데이터는 어떠한 중심을 기준으로 분포할 것이다"라는 가정을 기반으로 한다. 이와 다르게 밀도 기반 알고리즘은 "동일한 클래스에 속하는 데이터는 서로 근접하게 분포할 것이다"라는 가정을 기반으로 동작한다. 아래의 [그림 1]은 중심 기반 클러스터링 알고리즘 (k-means clustering)과 밀도 기반 클러스터링 알고리즘 (DBSCAN)의 클러스터링 결과를 보여준다.

[그림 1] Two moons 데이터셋에 대한 k-means clustering과 DBSCAN의 군집화 결과 (같은 색의 데이터는 같은 클래스에 군집되었다는 것을 의미함).

중심 기반 클러스터링 알고리즘은 클러스터의 중심을 기준으로 가까운 데이터들을 클러스터에 포함시키기 때문에 원의 형태로 클러스터의 모양이 형성된다. 반면에 밀도 기반 클러스터링 알고리즘은 서로 이웃한 데이터들을 같은 클러스터에 포함시키기 때문에 불특정한 모양의 클러스터가 형성된다. 따라서 [그림 1]과 같이 Gaussian 분포가 아닌, 불특정한 분포를 따르는 데이터에 대해서는 밀도 기반 클러스터링 알고리즘을 활용하는 것이 적절하다.

2. DBSCAN

밀도 기반 클러스터링 알고리즘인 DBSCAN은 기존의 중심 기반 클러스터링 알고리즘인 k-means clustering과 비교할 때 다음과 같은 장단점을 갖고 있다.

• (+) k-means clustering과 다르게 클러스터의 수를 지정할 필요가 없으며, 알고리즘이 자동으로 클러스터의 수를 찾는다.

• (+) 원 모양의 클러스터뿐만 아니라, 불특정한 모양의 클러스터도 찾을 수 있다.

• (+) 클러스터링을 수행하는 동시에 노이즈 데이터도 분류할 수 있기 때문에 outlier에 의해 클러스터링 성능이 하락하는 현상을 완화할 수 있다.

• (-) k-means clustering은 데이터의 수에 대해 linear time complexity 갖지만, DBSCAN은 quadratic time complexity를 갖는다.

• (-) 데이터가 입력되는 순서에 따라 클러스터링 결과가 변한다.

• (-) 알고리즘이 이용하는 거리 측정 방법에 따라 클러스터링 결과가 변한다.

• (-) 데이터의 특성을 모를 경우에는 알고리즘의 적절한 hyper-parameter를 설정하기가 어렵다.

3. DBSCAN의 동작

DBSCAN은 각각의 데이터들에 대해 이웃한 데이터와의 밀도를 계산하면서 불특정한 모양의 클러스터를 생성한다. 따라서, DBSCAN을 정의하기 위해서는 이웃한 데이터와 클러스터에 대한 정의가 필요하다. 이를 위해 DBSCAN의 hyper-parameter로 주어지는 주변 거리 $\epsilon$과 최소 이웃 데이터의 수 $n_c$를 기반으로 아래와 같은 개념들을 정의한다.

• 이웃 데이터: 어떠한 데이터 $\textbf{x}$와의 거리가 $\epsilon$ 보다 가깝거나 같은 데이터를 $\textbf{x}$의 이웃 데이터라고 한다.

• 핵심 데이터: 이웃 데이터의 수가 $n_c$보다 많거나 같은 데이터를 핵심 데이터라고 한다.

• 외곽 데이터: 핵심 데이터는 아니지만, 어떠한 핵심 데이터의 이웃 데이터인 것을 말한다.

• 노이즈 데이터: 핵심 데이터도 아니며, 외곽 데이터도 아닌 것을 말한다. 즉, 거리 $\epsilon$ 이내에 $n_c$개 미만의 데이터가 있으며, 그 데이터들 모두 핵심 데이터가 아닐 경우를 노이즈 데이터라고 한다.

DBSCAN은 위에서 정의된 개념을 바탕으로 주어진 데이터에 대해 밀도를 기반으로 개수와 형태가 정해지지 않은 클러스터들을 형성하고, 노이즈 데이터를 분류하는 알고리즘이다. 클러스터링 알고리즘을 적용하고자 하는 데이터 $\mathcal{X}$와 알고리즘의 hyper-parameter인 $\epsilon, n_c$에 대해 DBSCAN의 전체 동작은 아래의 [알고리즘 1]과 같다.

위의 [알고리즘 1]의 7, 14번째 줄에 있는 $SCAN$ 함수는 주어진 데이터 $\textbf{x}$의 이웃 데이터들인 $\mathcal{X}_\textbf{x}$를 찾는 연산으로써, 아래의 [알고리즘 2]와 같이 정의된다.

알고리즘의 출력인 label $\textbf{y}$는 데이터가 어떠한 클러스터에 군집되었는지를 나타내는 변수로써, 만약 두 데이터의 $\textbf{y}$ 값이 같다면 두 데이터는 같은 클러스터에 군집되었다는 것을 의미한다. [알고리즘 1]의 DBSCAN은 먼저 5번째 줄과 같이 주어진 데이터 포함된 데이터 $\textbf{x}$를 하나 선택한다. 그다음, $SCAN$ 연산을 통해 $\textbf{x}$의 이웃 데이터 $\textbf{z}$를 찾는다. 만약 $\textbf{x}$의 이웃 데이터의 수가 $n_c$보다 크거나 같다면 $\textbf{x}$는 핵심 데이터로 분류되고, 새로운 클러스터가 형성된다 (8 ~ 10번째 줄). 이때 $\textbf{x}$의 이웃 데이터인 $\textbf{z}$ 또한 $\textbf{x}$와 같은 클러스터에 배정된다 (13번째 줄). 그다음, 다시 $SCAN$ 연산을 통해 $\textbf{z}$의 이웃 데이터를 찾고, $\textbf{z}$가 핵심 데이터로 분류될 경우에는 $\textbf{z}$의 이웃 데이터를 또한 $\textbf{x}$와 같은 클러스터에 배정한다 (14 ~ 17번째 줄).

참고 문헌

[1] Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD 96). AAAI Press. pp. 226–231.