[AI] DBSCAN(density-based spatial clustering of applications with noise)

들어가며

이번 글에서는 군집 알고리즘들 중 k-평균과 함께 인기있는 알고리즘인 DBSCAN에 대해 알아보겠다

이름만 들었을 때는 뭘 의미하는지 감도 안잡혔는데

density-based spatial clustering of applications with noise의 약어라는 것을 알고

밀도를 고려해서 클러스터를 찾는 것이라는 느낌 정도만 왔다

밑에서 자세히 알아보도록 하겠다

 

DBSCAN

DBSCAN은 밀집해 있는 연속된 지역을 클러스터로 정의한다

핵심 아이디어는 아래와 같다

1. 알고리즘이 각 샘플에서 거리가 ε 내에 샘플이 몇 개 있는 지 세고 이 지역을 샘플의 ε-이웃이라고 정의한다

2. ε-이웃 내에 적어도 min_samples개의 샘플이 있다면 이 샘플을 핵심 샘플로 지정한다

3. 핵심 샘플의 이웃 샘플들은 모두 동일한 클러스터에 속하고 이웃 샘플역시 핵심 샘플이 될 수 있으며

    핵심 샘플의 이웃의 이웃이 계속 이어져 하나의 클러스터를 형성한다

4. 핵심 샘플이 아니고 이웃도 아닌 샘플은 이상치로 간주한다

 

이 알고리즘은 임의의 모양을 가진 클러스터를 식별하는 능력이 뛰어나고

클러스터끼리 밀집적으로 잘 구분되는 형태의 데이터를 가질 때 좋은 성능을 낸다

 

사이킷런의 DBSCAN 클래스를 통해 이 알고리즘을 사용할 수 있다

클러스터의 개수를 미리 지정할 필요 없다는 것이 특징이다

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=1000, noise=0.05, random_state=42)
dbscan = DBSCAN(eps=0.05, min_samples=5)
dbscan.fit(X)

알고리즘 학습 결과는 labels_변수에 저장되어 있고

핵심 샘플은 components_에 저장되어 있고 핵심 샘플의 인덱스는 core_sample_indices에 있다

dbscan.labels_[:10]
array([ 0,  2, -1, -1,  1,  0,  0,  0,  2,  5])

dbscan.components_
array([[-0.02137124,  0.40618608],
       [-0.84192557,  0.53058695],
       [ 0.58930337, -0.32137599],
       ...,
       [ 1.66258462, -0.3079193 ],
       [-0.94355873,  0.3278936 ],
       [ 0.79419406,  0.60777171]])

dbscan.core_sample_indices_[:10]
array([ 0,  4,  5,  6,  7,  8, 10, 11, 12, 13])

군집 결과는 아래와 같다

7개의 클러스터가 생성된 것이 보이고 X로 표시된 이상치로 판단된 지점이 많다

초승달 데이터인만큼 클러스터가 2개로 나뉠 것을 예상했지만

예상했던 결과와 달라 eps( ε ) 범위를 조금 더 크게 지정하면 다음과 같다

클러스터가 2개로 잘 분리된 군집을 볼 수 있다

갈색과 하늘색 영역은 핵심 샘플들의 ε-이웃 범위를 연결하여 형성된 영역이다

 

DBSCAN 클래스는 predict() 를 제공하지 않고 fit_predict()만 제공한다

이 말은 새로운 샘플에 대해서는 예측을 할 수 없다는 의미이다

클러스터의 중심도 없고 클러스터 경계에 대한 수식이 없고

단순히 밀도가 연결된 영역이기에 새로운 샘플이 들어왔을 때

어느 클러스터라고 딱 말할만한 판정 능력은 부족하다

 

그래서 일반적으로 예측기가 필요한 경우

다른 분류 알고리즘의 예측기와 함께 조합하여 사용한다

DBSCAN으로 나온 label을 다른 분류 알고리즘의 훈련 레이블처럼 사용한다

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=50)
knn.fit(dbscan.components_, dbscan.labels_[dbscan.core_sample_indices_])

DBSCAN의 핵심 샘플들만 학습하여 밀도 구조를 학습시킨다

(핵심 샘플들만이 아니라 모든 샘플에 대해서도 훈련시킬 수 있다)

이후 새로운 샘플을 주면된다

X_new = np.array([[-0.5, 0], [0, 0.5], [1, -0.1], [2, 1]])
knn.predict(X_new)
array([1, 0, 1, 0])

마치며

오늘은 DBSCAN의 작동 방식과 특징들에 대해 공부해보았다

이 알고리즘은 간단하지만 복잡한 형태의 클러스터 모양과 개수를 잡아내는 강력한 알고리즘이다

이상치도 잘 잡아내며 하이퍼파라미터가 2개(eps, min_samples)뿐이여서 사용도 편리하다

하지만 클러스터 간의 밀집도가 다르거나 해당 클러스터가 아닌 부분이 저밀도가 아닌 경우 이상하게 잡아낼 수 있다

 

처음에는 DBSCAN이 k-평균보다 나은거같다고 생각했지만

고차원 데이터에서 성능이 안좋아진다고 하고 위에서 봤듯이 predict()가 제공되지 않기에

이 점이 꽤나 큰 디메리트로 작용하여 실무에서는 k-평균이 더 많이 쓰이고

위에서 다룬 것처럼 DBSCAN과 k-평균을 조합하여 사용한다고 한다