[ML] 비지도학습 - DBSCAN

1. DBSCAN 개요

Reference[1]

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 데이터가 밀집되어 있는 영역을 클러스터로 보고, 희소 영역(밀도가 낮은 부분)을 노이즈로 간주하는 밀도 기반 군집화 알고리즘이다. DBSCAN은 임의의 형태의 클러스터를 찾을 수 있고, 노이즈를 제거하거나 탐지하는 용도로 활용이 가능하여 다른 클러스터링 기법에 비해 우수한 면이 있다.

 

2. Theorem

DBSCAN 알고리즘의 구현을 위해 정리해야할 몇가지 이론(혹은 정의)이 있는데, 정리하면 다음과 같다.

2-1. ε-neighborhood

어떤 점 p를 기준으로, 데이터셋 D 안에 있는 점들 중, 거리(dist)가 ε 이하인 점들의 집합을 ε-이웃(ε-neighborhood)이라 하며, p 주변에 반지름 ε인 원을 그렸을 때 원안에 들어오는 모든 점들이 ε-이웃(ε-neighborhood)이 된다. 그림으로 정리해보면 아래와 같다.

Reference[2]

 

2-2. Directly Density-Reachable

한 점 p가 q로부터 Directly Density-Reachable하다는 것은, q의 ε반경 안에 존재하는 점이 일정 개수(MinPts) 이상 있을 때를 의미한다. 여기서 ε반경과 일정 개수(MinPts)는 하이퍼파라미터로 사용자가 직접 정해주어야하는 값이며, 이를 수식으로 정리하면 다음과 같다. p가 q의 ε반경 안에 존재해야하고[1], ε반경에 포함되는 점의 개수가 MinPts이상이어야 한다[2].

[1]

[2]

2-3. Density Reachable

점 p가 q로부터 Density Reachable하다는 것은, Directly Density-Reachable로 연결된 체인이 존재한다는 것을 의미한다. 즉 p와 q사이에 p1, p2, p3, ... , pn이 있으며, p1은 q로부터 Directly Density-Reachable하고, p2는 p1으로부터 Directly Density-Reachable하고 ... p는 pn으로부터 Directly Density-Reachable한 체인이 존재한다면, p는 pn으로부터 Density Reachable하다고 할 수 있다. 정리하자면 단방향으로의 연결성에 대한 정의인 셈

 

2-4. Density Connected

Density Connected는 Density Reachable 개념을 양방향으로 확장한 개념으로, 어떤 기준점 o가 있고, o로부터 Density Reachable한 점들을 모두 모았을 때, p와 q가 포함되어 있다면, p와 q는 Density Connected라 한다. 2-2에서 2-4의 내용을 그림으로 정리하면 아래와 같다.

Reference[3]

2-5. Cluster & Noise

DBSCAN은 아래의 2가지를 만족하는 서브셋을 클러스터로 정의한다. 

1. 최대성(Maximality)

* 클러스터 C에 속한 임의의 점 p로부터 Density Reachable한 모든 점은 반드시 C에 포함되어야 한다.

 

2. 연결성(Connectivity)

* 클러스터 내 임의의 두점 p,q는 서로 Density Connected 관계에 있어야 한다. 즉, 임의의 점에 대해 Density Reachable한 데이터들 중, 클러스터 내 다른 모든 점들과 Density Reachable한 점들을 한번더 솎아낸다는 의미. 이렇게되면 결국 모든 점들에 대해 임의로 2개 포인트를 뽑았을 때, 서로 Density Connected 관계가 된다.

 

예를들어, p와 Density Reachable한 데이터들과 q와 Density Reachable한 점들을 모두 뽑아놓고, 뽑은 점들 중 p,q 양쪽과 Density Reachable한 점들만 남겨 클러스터로 묶는 상황을 생각해볼 수 있다.

 

3. Noise

어떠한 클러스터에도 속하지 못한 데이터들은 노이즈(Outlier)로 간주된다.

 

3. Pseudo Code

따라서 알고리즘을 정리해보면, 아래의 Pseudo Code와 같다. 전달인자로는 데이터셋과 epsilon, MinPts를 넣어주어야 한다.

Reference[4]

 

4. DBSCAN  구현하기

sklearn에서는 DBSCAN함수를 지원하고 있다. 함수의 세부 전달인자 등의 자세한 설명은 아래의 사이킷런 홈페이지에서 확인할 수 있다.

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

DBSCAN

주로 활용할 인자는 epsilon값과 MinPts로, epsilon 반경과 반경 내 최소 점의 수를 사용자가 하이퍼파라미터로 전달해주어야한다. 거리로는 보통 유클리디안 거리를 활용하므로, 특별한 경우를 제외하곤 따로 인자를 전달하지 않아도 디폴트 설정으로 유클리디안 거리가 지정되어 있다. 

from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps, min_samples)
dbscan.fit(X)
labels = db.labels_  # Cluster Label (-1: Noise)

다음과 같이 모듈을 임포트해오고, epsilon값과 MinPts값을 전달하여 모델을 생성해준 후, fit을 통해 군집화를 수행할 수 있다. label은 노이즈 데이터는 -1, 그 외의 데이터는 양수값이 할당되므로 그래프 뽑거나 할 때 이를 활용하면 된다.

import matplotlib
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
plt.rcParams['font.family'] = 'Times New Roman'

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

dbscan = DBSCAN(eps=0.2, min_samples=5)
dbscan.fit(X)

labels = dbscan.labels_ 

plt.figure(figsize=(9, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="rainbow", edgecolors="k")
plt.title("DBSCAN", fontsize=20)
plt.show()

예를들어, make_moons를 통해 반달모양 데이터 셋을 생성해주고, 이를 DBSCAN으로 군집화해줄 수 있다. dbscan.fit(X)를 통해 군집화되며, 할당된 레이블로 그래프를 뽑아보면 아래와 같이 2개의 클러스터로 군집화된 것을 확인할 수 있다. K-means Clustering이 반달모양 데이터를 올바르게 군집화해내지 못했던 것과 대조적이다.

 

 

이때 적절한 eps와 MinPts값을 하이퍼파라미터로 전달해주어야 하는데, eps값을 좀 더 작게 설정하고 클러스터별 그래프를 다시 뽑아보면 아래와 같다.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
plt.rcParams['font.family'] = 'Times New Roman'

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

dbscan = DBSCAN(eps=0.1, min_samples=5)
dbscan.fit(X)
labels = dbscan.labels_ 

labels_num = np.unique(labels)
colors = plt.cm.rainbow(np.linspace(0, 1, len(labels_num)))

plt.figure(figsize=(9, 6))

for k, col in zip(labels_num, colors):
    if k == -1:
        col = 'black'
        label_name = "Noise"
    else:
        label_name = f"Cluster #{k+1}"
    mask = (labels == k)
    plt.scatter(X[mask, 0], X[mask, 1],
                color=col, edgecolors='k', s=50, label=label_name)

plt.title("DBSCAN", fontsize=20)
plt.legend()
plt.show()

군집화가 잘되고 안되고는 상황에 따라 다르겠지만, 원래 의도와는 달리 클러스터가 여러개로 나뉘었고, 노이즈로 분류된 데이터도 꽤나 많아졌다. 이처럼 하이퍼파라미터 최적화가 DBSCAN에서도 주요한 쟁점인 셈.

 

 

 

Reference

[1] : https://en.wikipedia.org/wiki/DBSCAN

[2] : https://towardsdatascience.com/a-practical-guide-to-dbscan-method-d4ec5ab2bc99

[3] : https://levelup.gitconnected.com/dbscan-a-density-based-clustering-algorithm-110b726fd6fe

[4] : https://www.researchgate.net/figure/Pseudocode-of-the-DBSCAN-algorithm_fig2_325059373