지난 포스트에서 다루었던 K-Means는 데이터 간의 거리를 이용해 군집을 나누는 방법이라면, 이번 포스트에서 다룰 DBSCAN (Density-Based Spectral Clustering of Application with Noise)는 데이터가 세밀하게 모여있는 밀도가 높은 곳을 뭉치는 군집 방법으로서 서로 이웃한 데이터들을 군집에 반복적으로 포함시키기 때문에 일반적으로 원형 형태 군집으로 나타나는 거리 기반 군집화에 비해 불특정한 모양의 군집 형성이 가능합니다.
위 그림은 sklearn.datasets 모듈의 make_moons 함수를 이용한 가상 데이터를 K-Means와 DBSCAN을 이용하여 군집화 한 결과로 K-Means는 거리 기반으로 두 군집이 명확히 구분되지 않으나 DBSCAN은 밀도 기반으로 명확히 구분되는 것을 알 수 있습니다. 특히, DBSCAN은 미리 군집 개수 $k$를 지정할 필요가 없이 지정 거리 (eps), 최소 샘플 개수 (min_samples) 만으로 알아서 군집을 찾는 알고리즘입니다.
DBSCAN
DBSCAN의 원리는 데이터가 놓여 있는 공간 상에서 데이터가 많이 모여있는, 밀도가 높은 지역을 군집화하고 비교적 밀도가 낮아 비어있는 지역을 경계로 다른 군집과 구분하는 것입니다. 따라서 밀도가 높은 지역끼리 군집이 형성되어 $k$를 설정할 필요가 없습니다.
먼저, 임의로 선정한 하나의 데이터 샘플에서 지정 거리 (eps) 안에 최소 샘플 개수 (min_samples) 만큼 들어있으면 이 데이터 샘플을 core point 로 설정합니다. 그후 해당 거리안에 있는 샘플에 대해서 지정 거리 (eps) 안에 최소 샘플 개수 (min_samples) 만큼 들어있으면 마찬가지로 이 샘플도 core point 로 설정하고 해당 샘플들을 같은 군집으로 편입합니다.
만약 해당 거리안에 있는 샘플에 대해서 지정 거리 (eps) 안에 최소 샘플 개수 (min_samples) 만큼 들어있지 않다면 core point는 되지 못하지만 군집에는 속해 있으므로 군집의 경계가 되는 border point가 됩니다. 또한 지정 거리 안에 샘플이 없어 어느 군집에도 할당되지 못한다면 noise point로 처리됩니다. 이러한 방식으로 core point 가 없을 때까지 클러스터가 확장하고 그 다음 방문하지 않은 지역에 대해 같은 로직을 반복합니다.
정리하면, 데이터 샘플에서 지정 거리 (eps) 안에 최소 샘플 개수 (min_samples) 만큼 들어있으면 그 샘플을 중심으로 군집이 형성되고 core point가 서로 다른 core point 군집의 일부가 되면서 군집이 밀도 기반으로 확장하는 형태를 취합니다. 군집에는 속하지만 core point가 아닌 점을 border point라 하며 어느 군집에도 속하지 않는 점을 noise point라 합니다.
전체 알고리즘은 다음과 같습니다. 알고리즘의 출력인 label y는 데이터가 어떤 군집에 할당되었는지 나타내는 변수로 y가 같다면 두 데이터가 같은 군집이라는 것을 뜻합니다.
In python
파이썬에서는 sklearn.cluster 모듈의 DBSCAN 함수로 쉽게 구현할 수 있습니다. DBSCAN의 eps, min_samples 파라미터는 디폴트로 각각 0.5, 5로 설정되어 있으며 noise point일 경우 -1 라벨로 표현됩니다. 특히, border point의 경우 클러스터 core point의 이웃으로 중복될 수가 있어 어디서부터 클러스터가 확장하느냐에 따라 할당된 군집이 달라질 수 있습니다.
지정거리 (eps) 가 증가하면 하나의 클러스터에 많은 데이터가 포함되어 클러스터가 커지지만 여러 클러스터가 합쳐질 수도 있습니다. 지정거리를 매우 작게 하면 모든 포인트가 noise point로 설정되어 -1이 되버리게 됩니다. 또한 최소 샘플 개수는 조밀하지 못한 지역의 데이터가 noise point가 될 것인지 클러스터에 속할 것인지를 결정하게 됩니다.
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
X, y = make_moons()
y_pred = DBSCAN(min_samples=5, p=2).fit_predict(X)
import matplotlib.pyplot as plt
X_0 = X[y_pred==0]
X_1 = X[y_pred==1]
plt.scatter(X_0[:,0], X_0[:,1], c='black')
plt.scatter(X_1[:,0], X_1[:,1], c='blue')
참조
'Machine Learning Tasks > Clustering' 카테고리의 다른 글
| Clustering - Performance (1) (0) | 2021.05.11 |
|---|---|
| Clustering - Hungrian Algorithm (2) | 2021.05.11 |
| Clustering - Learning Discrete Representations via Information Maximizing Self-Augmented Training (0) | 2021.05.03 |
| Clustering - 군집 개수 정하기 (0) | 2021.04.25 |
| Clustering - K-Means (0) | 2021.04.25 |
