DBSCAN은 Density Based Spatial Clustering of Application with Noise 의 약자입니다. 한국어로 밀도 기반 클러스터링 정도로 번역할 수 있습니다.
K-means clustering 과의 차이점
클러스터링 하면 가장 입문처럼 사용하는 직관적이고 쉬운 방식이 K-means clustering 이 아닐까 합니다. 이 방법과는 다음의 두가지 정도 차이점이 생기는 것 같아요.
- 클러스터의 갯수를 정하지 않아도 된다.
- K-means clustering 이 잘 나누지 못하는 데이터의 형태도 분류가 가능하다.
K-means clustering 에 대해서는 다음 링크를 참고하시구요, 이 글에서는 어떤 방식이길래 이런 차이가 나는지 살펴 보죠.
K-means clustering 이해하기
클러스터링은 데이터를 분류한다는 뜻입니다. 쉽게 말하자면 비슷한 녀석들끼리 너네는 1번 그룹, 너네는 2번 그룹 이런 식으로 나누어 주는 거예요. 여러가지 방법이 많은데, 그 중 가장 기초가
depotceffio.tistory.com
알고리즘 동작 방식
여기서도 K-means clustering 과의 차이점이 나타납니다. K-means clustering 은 전체 데이터에 대해 틀을 잡고 중심점만 재계산해가면서 학습해 나가는데 반해, DBSCAN의 경우는 데이터 하나하나에 대해서 계산하는 과정을 반복하게 됩니다.
- 데이터들 중 아무거나 하나를 선택합니다.
- 선택한 데이터의 특정 반경 안에 몇개의 데이터가 있는지 확인합니다.
- 반경 안에 특정 이상 갯수의 데이터가 존재하면 그 데이터들은 하나의 클러스터로 지정합니다.
- 반경 안에 특정 이상 갯수의 데이터가 존재하지 않으면, 현재 선택한 데이터는 노이즈로 지정합니다.
여기까지가 하나의 루프입니다. 예를 들어 반경 안에 10개 이상의 데이터가 존재해야 한다고 지정했는데 실제로 살펴보니 12개의 데이터가 있었다고 하죠. 그러면 그 데이터들 전체를 하나의 클러스터로 간주합니다.
특정 반경 안에 일정한 갯수 이상의 데이터가 존재해야 한다는 개념 자체가 밀도가 높은 구간을 하나의 그룹으로 보겠다는 뜻이죠. 그래서 밀도 기반 클러스터링이라고 합니다. 이제 특정 이상 갯수의 데이터가 존재하는 경우와 그렇지 않은 경우로 나뉘었습니다.
여기서 더 후속 작업이 이루어질 것은, 3번의 반경 안에 특정 갯수 이상의 데이터가 존재하는 경우입니다. 4번과 같은 경우는 그냥 노이즈로 지정되고 끝이기 때문입니다. 3번의 내용을 자세히 살펴볼께요.
반경 안에 특정 갯수 이상의 데이터가 존재하는 경우
같은 클러스터로 묶인 데이터 중, 가장 먼저 선택한 데이터 이외의 다른 데이터로 같은 과정을 반복합니다. 다음과 같습니다.
- 클러스터 안의 데이터 중 아무거나 하나를 선택합니다. (최초로 선택했던 데이터는 제외)
- 선택한 데이터의 특정 반경 안에 몇개의 데이터가 있는지 확인합니다.
- 반경 안에 특정 갯수 이상의 데이터가 존재하면, 기존의 데이터와 새로 들어온 데이터를 모두 하나의 클러스터로 지정합니다.
- 반경 안에 특정 갯수 이상의 데이터가 존재하지 않으면 아무 일도 일어나지 않습니다.
첫번째 루프와 거의 비슷한데요, 차이점이라면 반경 안에 특정 갯수 이상의 데이터가 존재하지 않아도, 현재 선택된 데이터가 노이즈로 할당되지 않는다는 점입니다. 왜냐하면 지금 선택된 데이터들은 모두 어떤 클러스터에 할당된 적이 있는 포인트이기 때문에, 이 점 부근의 데이터가 별로 없다는 뜻은 이 포인트가 노이즈라는 게 아니라 클러스터의 제일 바깥쪽 정도라는 이야기가 되기 때문입니다.
이런 식으로 하나의 클러스터가 점점 확장되다 보면, 어떤 점도 더이상 클러스터를 확장할 수 없는 순간이 올 겁니다. 그러면 이제 다시 가본 적이 없는 점으로 가서 이 과정을 반복합니다. 그러다 보면 결국 전체 데이터에 대해 이 계산을 수행하게 될 겁니다.
예제로 이해하기
백문이 불여일견, 한번 코드로써 구현해 보았습니다. 코드가 길기 때문에, 조금 섹션을 나누어서 볼게요.
데이터 생성하기
일단 아래와 같이 데이터를 임의로 생성해 볼께요. 가우시안 분포를 가지는 데이터들의 덩어리를 여기저기 뿌리는 코드입니다.
# coding: utf-8
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN
num_data = 300
dimension = 2
data = np.random.randn(num_data, dimension)
offsets = np.array([[5,2], [-1,5], [2,3], [5,5], [-4,0], [4,-3],[6,8]])
# offsets = np.array([[6,8], [-6,-8], [-6,8], [6,-8]])
for offset in offsets:
data = np.append(data,np.random.randn(num_data, dimension)*1.2 + offset, axis=0)
fig = plt.figure(figsize=[6,6])
plt.scatter(data.T[0],data.T[1], s=6)
plt.grid()
plt.show()
위 코드를 실행하고 나면 아래와 같은 데이터를 플랏할 수 있습니다. 실제로는 7개의 덩어리로 나눈 데이터셋인데요, 이렇게 답을 알고 나면 사람 눈으로도 대충 어디쯤이 각각의 중심점을 이루고 어떻게 나누어야 할 지는 알 수 있을 것 같은 데이터입니다.
DBSCAN 학습결과
DBSCAN에는 사람이 정해줘야 하는 인자가 2개 있습니다. 이를 보통 튜닝한다고 하고, 이런 인자들을 하이퍼파라미터라고 부릅니다. 다음의 두개입니다.
- 같은 클러스터에 속하는 반경
- 반경 안에 속해야 할 데이터의 갯수
일단 시도는 반경 0.45에 데이터 갯수 20개 입니다. 다음의 코드와 결과를 보시죠.
eps = 0.45 # 하나의 클러스터라고 할 거리를 정함
min_samples = 20 # 최소한 이거 이상의 인자만 속하면 같은 클러스터로 봄
dbscan = DBSCAN(eps=eps, min_samples=min_samples)
cluster = dbscan.fit_predict(data)
cluster_number = list(set(list(cluster.tolist())))
clst_mu = []
for cn in cluster_number:
if cn != -1:
clst_mu.append(np.mean(data[np.where(cluster==cn)[0]], axis=0))
print(len(data[np.where(cluster==cn)[0]]))
clst_mu = np.array(clst_mu)
clustered = []
noises = data[np.where(cluster==-1)[0]]
for cn in cluster_number:
if cn != -1:
clustered.append(data[np.where(cluster==cn)[0]])
fig = plt.figure(figsize=[10,10])
plt.scatter(clst_mu.T[0],clst_mu.T[1], c='black', s=50)
plt.scatter(noises.T[0],noises.T[1], s=20, c='red')
for clustered_data in clustered:
plt.scatter(clustered_data.T[0],clustered_data.T[1], s=6)
plt.grid()
plt.show()
실제로 DBSCAN 알고리즘에 해당하는 코드는 2~3줄밖에 되지 않습니다. (sklearn 라이브러리) 하지만 시각화를 위한 코드들까지 모두 섞여 있어서 코드가 길어진 거구요, 결과는 아래와 같습니다.
위 이미지에서 빨간색 점들은 노이즈입니다. 그리고 까만색 점들은 클러스터의 중심점이구요, 파란색/초록색 등으로 표현된 각각의 색깔이 하나의 클러스터로 묶인 결과입니다.
일단 노이즈가 너무 많죠? 이 얘기는 어떤 클러스터에도 속하지 못하는 점이 이렇게 많다는 것이고, 반대로 말하면 같은 클러스터로 보기 위한 밀도가 굉장히 높다는 뜻이 됩니다. 노이즈를 방지하기 위해서 클러스터링을 위한 데이터 밀도를 조금 낮춰서 다시 한번 해볼께요. 같은 코드로, 반경 0.45에 데이터 갯수 10개로 해보겠습니다.
클러스터링 결과는 위 이미지와 같구요, 클러스터 갯수는 4개입니다. 일단 제 눈에는 도저히 잘 나누었다고 말할 수 있을 거 같지가 않고, 거기에다 노이즈도 여전히 꽤 많아 보입니다.
DBSCAN의 한계점
DBSCAN의 가장 큰 단점이라고 손꼽히는 것이 "잘 동작하지 않는다" 는 점이라고 합니다. 사실 어처구니가 없죠. 일단 동작은 해야 뭘 하지... 개념 상으로는 단순하고 뛰어나 보이는데, 실제 세계에서의 데이터가 그렇게 예쁘게 나누어져 있을 리도 없고 눈으로도 나눌 수 있을 것 같은 데이터도 제대로 못 나누는 걸 확인할 수 있습니다.
하지만 이 알고리즘도 sparse 한 데이터에서는 분명히 잘 작동합니다. 그렇다면 이러한 데이터에서는 효과적일 거 같아요.
- 데이터가 sparse 한 건 분명하다.
- 데이터를 눈으로 보기 힘들다 : 결국 몇개의 클러스터로 나눠야 할 지 알기 어렵다.
어떤 알고리즘도 만능은 없는 거 같습니다. 상황에 맞는 알고리즘을 선택하는 것도 결국은 경험이 좌우한다는 슬픈 결론이 될 거 같습니다.
댓글