DBSCAN

DBSCAN

---

DBSCAN은 밀도 기반의 대표적인 알고리즘이다

DBSCAN은 간단하고 직관적인 알고리즘으로 돼있음에도 데이터의 분포가 기하학적으로 복잡하 데이터 셋에도 효과적인 군집화가 가능하다.

다음과같은 형태의 데이터를 군집화 한다고 했을때, k-평균 알고리즘과 DBSCAN 의 결과를 비교해보자.

DBSCAN이 효과적인 군집화를 수행하고 있는것을 알 수 있다.

DBSCAN은 특정 공간 내에 데이터 밀도 차이를 기반알고리즘으로 하고 있어서 복잡한 기하하적 분포도를 가진 데이터 셋에 대해서도 군집화를 잘 수행한다.

DBSCAN을 구성하는 가장 중요한 두 가지 파라미터는 입실론(epsilon) 으로 표기하는 주변영역과 이 입실론 주변 영역에 포함되는 최소 데이터 개수 min points 이다.

• 입실론 주변 영역(epsilon) : 개별 데이터를 중심으로 입실론 반경을 가지는 원형의 영역이다.
• 최소 데이터 개수(min points) :개별 데이터의 입실론 주변 영역에 포함되는 타 데이터의 개수.
• 입실론 주변 영역 내에 포함되는 최소 데이터 개수를 충족시키는가 아닌가에 따라 데이터 포인트를 다음과 같이 정의 한다.

• 핵심 포인트 (Core Point) : 주변 영역 내에 최소 데이터 개수 이상의 타 데이터를 가지고 있는 데이터
• 이웃 포인트 (Neighbor Point): 주변 영역 내에 위치한 타 데이터
• 경계 포인트 (Border Point) : 주변 영역 내에 최소 데이터 개수 이상의 이웃 포인트를 가지고 있지 않지만, 핵심포인트를 이웃 포인트로 가지고 있는 데이터
• 잡음 포인터(Noise Point) : 최소 데이터 개수 이상의 이웃 포인트를 가지고 있지 않으며, 핵심 포인트로 가지고 있지 않는 데이터

1. 다음 그림과 같이8개의 데이터 셋에대해 입실론 반경에 포함될 최소 데이터를 4라고 가정하자. P 는 핵심포인트가 되고 P의 입실론 반경 내에 포함된 데이터를 이웃 데이터라고 한다.

2. 다음 으로 P2 데이터를 살펴보자. P2는 반경내에 2개의 데이터 밖에 가지지 못하므로 군집의 중심이 되는 핵심 포인트는 되지 못하지만, 앞의 점 P를 핵심 포이트로 하는 군집에 속하기 떄문에 P2를 경계포인트라고 한다.

3. P3는 epsilon 반경내에서 점 4개를가지고 있기 때문에 핵심 포인트가 된다.

4. 그런데 P3를 중심으로 하는 반경내에 다른 핵심포인트 P가 포함이 되어 있는데, 이 경우 core point P와 P3를 연결 되어있다고 하고 하나의 군집으로 묶이게 된다.

5. 마지막으로 아래 그림의 P4는 어떤 점을 중심으로 하더라도minPts = 4를 만족하는 범위에 포함되지 않는다.
   즉 어느 군집에도 속하지 않는 outlier이 되는데, 이를 noise point 라고한다.

이를 모두 정리하면 아래 그림이 나온다.

정리해서 이야기 하면, 점을 중심으로 epsilon 반경내에 minPts 이상수의 점이 있으면 그 점을 중심으로 군집이 되고 그 점을 core point라고 한다.

Core point 가 서로 다른 core point의 군집의 일부가 되면 그 군집을 서로 연결되어 있다고 하고 하나의 군집으로 연결을 한다.

군집에는 속하지만, 스스로 core point가 안되는 점을 border point라고 하고, 주로 클러스터의 외곽을 이루는 점이 된다.

 

DBSCAN 적용하기 – 붓꽃 데이터 셋

---

DBSCAN 알고리즘으로 붓꽃 데이터 셋을 군집화해 보자.
eps = 0.6 , min_samples = 8로 지정함. 일반적으로 eps 값은 1이하의 값을 설정 한다.

from sklearn.datasets import load_iris

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
%matplotlib inline

iris = load_iris()
feature_names = ['sepal_length','sepal_width','petal_length','petal_width']

# 보다 편리한 데이타 Handling을 위해 DataFrame으로 변환
irisDF = pd.DataFrame(data=iris.data, columns=feature_names)
irisDF['target'] = iris.target

from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps=0.6, min_samples=8, metric='euclidean')
dbscan_labels = dbscan.fit_predict(iris.data)

irisDF['dbscan_cluster'] = dbscan_labels
irisDF['target'] = iris.target

iris_result = irisDF.groupby(['target'])['dbscan_cluster'].value_counts()
print(iris_result)

target  dbscan_cluster
0        0                49
        -1                 1
1        1                46
        -1                 4
2        1                42
        -1                 8
Name: dbscan_cluster, dtype: int64

먼저 dbscan_cluster 값을 살펴보자. 0과 1외에 특이하게 –1이 군집 레이블로 있는 것을 알 수있다. 군집 레이블이 –1인 것은 노이즈에 속하는 군집을 의미한다.

따라서 위 붓꽃 데이터 셋은 DBSCAN에서 0과 1 두 개의 군집으로 군집화 됐다.

DBSCAN으로 군집화 데이터 셋을 2차원 평면에서 표현하기 위해 PCA를 이용해 2개의 피처로 압축 변환환 뒤, 앞 예제에서 사용한 visualize_cluster_plot() 함수를 이용해 시각화 해보자.

visualize_cluster_2d() 함수 인자로 사용하기 위해 irisDF의 ‘ftr1’,‘ftr2’ 칼럼에 PCA로 변환된 피처 데이터 셋을 입력 함.

### 클러스터 결과를 담은 DataFrame과 사이킷런의 Cluster 객체등을 인자로 받아 클러스터링 결과를 시각화하는 함수  
def visualize_cluster_plot(clusterobj, dataframe, label_name, iscenter=True):
    if iscenter :
        centers = clusterobj.cluster_centers_

    unique_labels = np.unique(dataframe[label_name].values)
    markers=['o', 's', '^', 'x', '*']
    isNoise=False

    for label in unique_labels:
        label_cluster = dataframe[dataframe[label_name]==label]
        if label == -1:
            cluster_legend = 'Noise'
            isNoise=True
        else :
            cluster_legend = 'Cluster '+str(label)

        plt.scatter(x=label_cluster['ftr1'], y=label_cluster['ftr2'], s=70,\
                    edgecolor='k', marker=markers[label], label=cluster_legend)

        if iscenter:
            center_x_y = centers[label]
            plt.scatter(x=center_x_y[0], y=center_x_y[1], s=250, color='white',
                        alpha=0.9, edgecolor='k', marker=markers[label])
            plt.scatter(x=center_x_y[0], y=center_x_y[1], s=70, color='k',\
                        edgecolor='k', marker='$%d$' % label)
    if isNoise:
        legend_loc='upper center'
    else: legend_loc='upper right'

    plt.legend(loc=legend_loc)
    plt.show()

from sklearn.decomposition import PCA
# 2차원으로 시각화하기 위해 PCA n_componets=2로 피처 데이터 세트 변환
pca = PCA(n_components=2, random_state=0)
pca_transformed = pca.fit_transform(iris.data)
# visualize_cluster_2d( ) 함수는 ftr1, ftr2 컬럼을 좌표에 표현하므로 PCA 변환값을 해당 컬럼으로 생성
irisDF['ftr1'] = pca_transformed[:,0]
irisDF['ftr2'] = pca_transformed[:,1]

visualize_cluster_plot(dbscan, irisDF, 'dbscan_cluster', iscenter=False)

별표로 표시된 값은 모두 노이즈이다. PCA로 2차원으로 표현하면 이상치인 노이즈 데이터가 명확히 드러난다. DBSCAN을 적용할 때는 특정 군집 개수로 군집을 강제하지 않는 것이 좋다.

DBSCAN 알고리즘에 적절한 eps와 min_samples 파라미터를 통해 최적의 군집을 찾는게 중요하다.

일반적으로 eps 의 값을 크게 하면 반경이 커져 포함하는 데이터가 많아지므로 노이즈 데이터 개수가 작아진다.

min_samples를 크게 하면 주어진 반경 내에서 더 많은 데이터를 포함시켜야 하므로 노이즈 데이터 개수가 커지게 된다. 데이터 밀도가 더 커져야 하는데, 매우 촘촘한 데이터 분포가 아닌 경우노이즈로 인식하기 때문이다.

eps를 기존의 0.6 에서 0.8로 증가시키면 노이즈 데이터 수가 줄어든다.

from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps=0.8, min_samples=8, metric='euclidean')
dbscan_labels = dbscan.fit_predict(iris.data)

irisDF['dbscan_cluster'] = dbscan_labels
irisDF['target'] = iris.target

iris_result = irisDF.groupby(['target'])['dbscan_cluster'].value_counts()
print(iris_result)

visualize_cluster_plot(dbscan, irisDF, 'dbscan_cluster', iscenter=False)

target  dbscan_cluster
0        0                50
1        1                50
2        1                47
        -1                 3
Name: dbscan_cluster, dtype: int64

노이즈 군집인 –1이 3개 밖에 없다. 기존에 eps가 0.6일 때 노이즈로 분류된 데이터 셋은 eps 반경이 커지면서 Cluster 1에 소속됐다. 이번에는 eps를 기존 0.6으로 유지하고 min_samples를 16으로 늘려보다 .

dbscan = DBSCAN(eps=0.6, min_samples=16, metric='euclidean')
dbscan_labels = dbscan.fit_predict(iris.data)

irisDF['dbscan_cluster'] = dbscan_labels
irisDF['target'] = iris.target

iris_result = irisDF.groupby(['target'])['dbscan_cluster'].value_counts()
print(iris_result)
visualize_cluster_plot(dbscan, irisDF, 'dbscan_cluster', iscenter=False)

target  dbscan_cluster
0        0                48
        -1                 2
1        1                44
        -1                 6
2        1                36
        -1                14
Name: dbscan_cluster, dtype: int64

노이즈 데이터가 기존보다 많이 증가함을 알 수 있다.

DBSCAN 적용하기 – make_circles() 데이터 세트

---

이번에는 복잡한 기하학적 분포를 가지는 데이터 셋에서 DBSCAN과 타알고리즘을 비교해보자 .먼저 make_circles() 함수를 이용해 내부 원과 외부 원 형태로 돼있는 2차원 데이터 셋을 만들어 보자.

make_circles() 는 오직 2개의 피처만을 생성하므로 별도의 피처 개수를 지정할 필요 가 없다.

파라미터 noise 는 노이즈 데이터 셋의 비율이며, factor는 외부 원과 내부 원의 scale 비율이다

from sklearn.datasets import make_circles

X, y = make_circles(n_samples=1000, shuffle=True, noise=0.05, random_state=0, factor=0.5)
clusterDF = pd.DataFrame(data=X, columns=['ftr1', 'ftr2'])
clusterDF['target'] = y

visualize_cluster_plot(None, clusterDF, 'target', iscenter=False)

make_circles() 는 내부 원과 외부 원으로 구분되는 데이터 셋을 생성함을 알 수 있다.

DBSCAN이 이 데이터 셋을 군집화한 결과를 보기 전에 먼저 K-평균과 GMM은 어떻게 이 데이터셋을 군집화 하는지 확인해 보자. 먼저 K-평균으로 make_circles() 데이터 셋을 군집화해 보자.

# KMeans로 make_circles( ) 데이터 셋을 클러스터링 수행. 
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=2, max_iter=1000, random_state=0)
kmeans_labels = kmeans.fit_predict(X)

clusterDF['kmeans_cluster'] = kmeans_labels

visualize_cluster_plot(kmeans, clusterDF, 'kmeans_cluster', iscenter=True)

위, 아래 군집 중심을 기반으로 위와 아래 절반으로 군집화됐다. 거리 기반 군집화로는 위와 같이 데이터가 특정한 형태로 지속해서 이어지는 부분을 찾아내기 어렵다.
다음으로 GMM을 적용해 보자.

# GMM으로 make_circles( ) 데이터 셋을 클러스터링 수행. 
from sklearn.mixture import GaussianMixture

gmm = GaussianMixture(n_components=2, random_state=0)
gmm_label = gmm.fit(X).predict(X)
clusterDF['gmm_cluster'] = gmm_label

visualize_cluster_plot(gmm, clusterDF, 'gmm_cluster', iscenter=False)

GMM 도 앞 절의 일렬로 늘어선 데이터 셋에서는 효과적으로 군집화 적용이 가능 했으나 , 내부와 외부의 원형으로 구성된 더 복잡한 형태의 데이터 셋에서는 군집화가 원하는 방향으로 되지 않았다.
이제 DBSCAN으로 군집화를 진행해 보자.

# DBSCAN으로 make_circles( ) 데이터 셋을 클러스터링 수행. 
from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps=0.2, min_samples=10, metric='euclidean')
dbscan_labels = dbscan.fit_predict(X)
clusterDF['dbscan_cluster'] = dbscan_labels

visualize_cluster_plot(dbscan, clusterDF, 'dbscan_cluster', iscenter=False)

DBSCAN으로 군집화를 진행했을때 내부원과 외부 원으로 잘 군집이 형성 된 것을 알 수 있다.

 

본문 내용은 파이썬 머신러닝 완벽 가이드 (권철민 저)을 요약정리한 내용입니다.