[군집] DBSCAN

◈  '군집' 목차 ◈

1. K-평균

2. DBSCAN

     DBSCAN 알고리즘에 대해 이해하고 사이킷런에서 DBSCAN을 구현해보자

3. HDBSCAN

4. 병합 군집

5. 평균-이동

6. BIRCH

7. 유사도 전파

8. 스펙트럼 군집

9. 가우시안 혼합 모델

10. 베이즈 가우시안 혼합 모델

---

1. DBSAN 알고리즘

이 알고리즘은 밀집된 연속 지역을 클러스터로 정의한다. 

 

step1

(자기 자신을 포함해) ∈(epsilon) 만큼의 이웃 내에 적어도 min samples 이 있다면 이를 핵심 샘플로 간주한다.

즉 핵심 샘플은 밀집된 지역에 있는 샘플이다.

 

step2

핵심 샘플의 이웃에 있는 모든 샘플은 동일한 클러스터에 속한다.

핵심 샘플의 이웃에 대해서도 ∈(epsilon) 거리 조사하여 이웃의 이웃으로 클러스터를 확장시킨다.

확장하다 보면 다른 핵심 샘플이 포함될 수도 있다.

결국 핵심 샘플의 이웃의 이웃은 계속해서 하나의 클러스터를 형성한다.

 

step3

더 이상 이웃이 없다면, 클러스터 할당이 안 된 다른 샘플에 대해서 step1 ~ step2 과정을 반복한다.

 

step4

클러스터링 완료 후, 핵심 샘플도 아니고 이웃도 아닌 샘플을 이상치로 판단한다. 

 

 

 

2. DBSAN 클래스

사이킷런에서 DBSCAN 클래스를 통해 DBSCAN 모델을 구현할 수 있다. 

 

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

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

 

DBSCAN의 몇 가지 속성을 살펴보면 다음과 같다.

lables_ 는 각 샘플이 속하는 클러스터 인덱스를 리턴한다.

이때 인덱스가 -1 인 샘플은 이상치로 판단한다.

core_sample_indicies 는 핵심 샘플의 인덱스이다.

components 는 핵심 샘플 데이터 자체를 저장해두었다. 

 

print(dbscan.labels_)    #array([0,2,-1,-1,0,0, ... ,3,2,3,3,4,2,6,3])
print(dbscan.core_sample_indicies)  #array([0,4,5,6,7,8,10,11 ... ])
print(dbscan.components) #arrya([[-0.02131724, 0.40601394], ... ])

 

epsilon 값을 증가시켜, 샘플의 이웃 범위를 넓히면 군집의 갯수가 줄어든다.

 

 

 

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

DBSCAN 알고리즘이 core 샘플이나 cluster centroid 와 같은 기준이 되는 값을 정해 놓고 새로운 샘플을 비교하는 것이 아니라, 입력된 데이터들간의 밀집도에 따라 클러스터가 구분지어지기 때문이다.

결국 DBSCAN 은 기존 샘플로 만든 모델 바탕으로 새로운 샘플 예측이 불가하다. 

 

 

새로운 샘플을 예측하기 위해서는 사용자가 필요한 예측기를 선택해야 한다.

KNeighborsClassifier 를 활용해 새로운 샘플을 예측하는 예제를 살펴보자. 

 

from sklearn.cluster import DBSCAN
from sklearn.neighbors import KNeighborsClassifier

dbscan = DBSCAN(eps=0.2, min_samples=10)
dbscan.fit(X) #core_sample_indicies_, components_, lables_ 에 값 저장됨

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

print(knn.predict(X_new))
print(knn.predict_prob(X_new))

 

위 예제에서는 핵심 샘플에 대해서만 훈련했지만, 모든 샘플에 대해서 훈련시킬 수도, 이상치를 제외하고 훈련시킬수도 있다. 선택은 최종 작업의 성능에 따라 결정된다. 

 

 

KNeighborsClassifier 의 kneighbors() 메소드를 통해 클러스터에서 멀리 떨어진 샘플을 이상치로 구분하도록 구현할 수 있다. kneighbors() 메소드는 새로운 샘플 X_new에 대해 훈련 세트 X 중 가장 가까운 K개 이웃의 거리와 인덱스를 반환한다. 

 

y_dist, y_idx = knn.kneighbors(X_new, n_neighbors=1)

y_pred = dbscan.labels_[core_sameple_indicies][y_pred_idx]
y_pred[y_dist < 0.2] = -1
print(y_pred.ravel())

 

DBSCAN은 매우 간단하지만 강력한 알고리즘이다.

클러스터 모양과 개수에 상관없이 감지할 수 있는 능력이 있다.

이상치에 안정적이고 하이퍼파라미터가 두 개 뿐이다. (eps, min_samples)

클러스터의 밀집도가 크게 다르면 모든 클러스터를 올바르게 잡아내는 것은 불가능하다.

계산 복잡도는 대략 샘플 개수에 선형적으로 증가한다.