[클러스터링] DBSCAN (밀도 기반 클러스터링)

1. DBSCAN이란?

DBSCAN(Density-based spatial clustering of applications with noise)

밀도 기반의 클러스터링은 점이 세밀하게 몰려 있어서 밀도가 높은 부분을 클러스터링 하는 방식이다. 쉽게 설명하면, 어느점을 기준으로 반경 x내에 점이 n개 이상 있으면 하나의 군집으로 인식하는 방식이다.

 

Scikit-Learn 라이브러리 사용시 -> sklearn.cluster.DBSCAN

 

2. DBSCAN의 원리

• 기준점 부터의 거리 epsilon값과, 이 반경내에 있는 점의 수 minPts를 인자로 전달
  P반경 내 5개의 점이 있기 때문에 군집으로 판단하여 P는 core point가 된다.

• 회색점 P2의 경우 점 P2를 기반으로 epsilon 반경내의 점이 3개 이기 때문에, minPts=4에 미치지 못하기 때문에, 군집의 중심이 되는 core point는 되지 못하지만, 앞의 점 P를 core point로 하는 군집에는 속하기 때문에 이를 boder point (경계점)이라고 한다

• P3는 epsilon 반경내에 점 4개를 가지고 있기 때문에 core point가 된다

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

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

• 최종 군집 결과
  점을 중심으로 epsilon 반경내에 minPts 이상수의 점이 있으면 그 점을 중심으로 군집이 되고 그 점을 core point라고 한다. Core point 가 서로 다른 core point의 군집의 일부가 되면 그 군집을 서로 연결되어 있다고 하고 하나의 군집으로 연결을 한다.
  군집에는 속하지만, 스스로 core point가 안되는 점을 border point라고 하고, 주로 클러스터의 외곽을 이루는 점이 된다.
  그리고 어느 클러스터에도 속하지 않는 점은 Noise point가 된다

최종 군집

• DBSCAN의 장점
  많이 사용되는 K-MEANS와 비교시 클러스터 수를 지정하지 않아도 되는 장점이 있으며, 실제 데이터의 밀도에 따라서 클러스터링이 되기 때문에 군집이 겹치지 않는다. 또한 노이즈 개념때문에 이상치에 대응이 가능하다.

DBSCAN과 KMEANS의 차이

3. 소스 코드

Github : https://github.com/Byeongin-Jeong/clustering.git

# 라이브러리 import
import pandas as pd
import mglearn
import plotly.graph_objs as go
from plotly.offline import init_notebook_mode, iplot
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
from sklearn.cluster import DBSCAN
import random
init_notebook_mode(connected=True)

# Importing the dataset
df = pd.read_csv('data/DBSCAN_data_2ea.csv')
df.tail()

# 차원 데이터를 바탕으로 좌표 데이터 추출(x, y, z)
cols = df.columns[1:]
pca = PCA(n_components = 3)
df['x'] = pca.fit_transform(df[cols])[:, 0]
df['y'] = pca.fit_transform(df[cols])[:, 1]
df['z'] = pca.fit_transform(df[cols])[:, 2]
df.tail()

# 좌표 데이터 스케일 축소(좌표 범위가 크기 때문)
def conv(i):
    return [int(df[i:i+1]['x']), int(df[i:i+1]['y']), int(df[i:i+1]['z'])]

convlist = []
for ldx in range(0, len(df)):
    convb = conv(ldx)
    convlist.append(convb)

rawpoint = StandardScaler().fit_transform(convlist)

# Data Traning (**esp**(기준점부터의 거리) = 0.2, **min_samples**(반경내 있는 점의수) = 20)
# 학습과 동시에 클러스터링 결과가 출력된다.
db = DBSCAN(eps=0.2, min_samples=20)
y_pred = db.fit_predict(rawpoint)
df["cluster"] = y_pred

clusternum = max(y_pred)

print ("clusterNum: {}".format(clusternum))
df.head()

# 2D 그래프 출력
mglearn.discrete_scatter(rawpoint[:, 0], rawpoint[:, 1], y_pred, markers='o')

# 클러스터링 제외된 데이터 ID 추출
df.loc[df['cluster'] == -1].head()

# 3D 출력 함수 (클러스터링이 되지 않은 Noise point는 빨간색으로 표시)
def gettrace(cl_result, cluster_num):
    if cluster_num == -1:
        r = 255
        g = 0
        b = 0
    else:
        r = random.randrange(50,255)
        g = random.randrange(50,255)
        b = random.randrange(50,255)

    return go.Scatter3d(x = [x[0] for x in cl_result[cluster_num]],
                        y = [y[1] for y in cl_result[cluster_num]],
                        z = [z[2] for z in cl_result[cluster_num]],
                        mode='markers',
                        marker=dict(
                            color="rgba({0}, {1}, {2}, 0.5)".format(r, g, b),
                            size=5,
                            symbol='circle',
                            line = dict(width = 1, color = "rgb(0,0,0)"),
                        opacity=0.9
                        ))

# 3D 그래프로 출력 가능하도록 데이터 가공
cluster_result = {}
for i, c in enumerate(y_pred):
    cluster_result.setdefault(c, [])
    cluster_result[c].append(rawpoint[i])

# 3D 데이터 출력
data = []
for idx in range(-1, clusternum +1):
    if idx in cluster_result:
        data.append(gettrace(cluster_result, idx))

iplot(data)

4. 분석

• load Data 확인

• 다차원 데이터를 기반으로 좌표 데이터 생성

• 학습 후 클러스터링 개수와 데이터 확인

• 2D 그래프 출력 결과

2D 그래프에서 확인한 클러스터 결과

• 3D 그래프 출력 결과

3D 그래프에서 확인한 클러스터 결과

• DBSCAN 클러스터링의 경우 밀도 분포 클러스터링이기 때문에 학습 조건이 성립하지 못할 경우 클러스터링에서 제외가 된다.(3D에서 빨간점으로 표시)
  클러스터링에서 제외된 데이터(Noise Point)는 일반적인 데이터로 볼수 없기 때문에 이상 데이터로 추측 할 수 있다.
  DBSCAN의 경우 범위내 데이터 개수와 범위 값에 따라 클러스터링이 될수도 있고 제외 될수도 있기 때문에 상황에 따라 조정이 필요하다.

5. 결론

DBSCAN의 경우는 밀도기반 군집 모델이기 때문에 사용자가 정의한 범위와 개수에 의해 클러스터링 개수가 정해지고, 조건에 만족하지 못한 데이터는 클러스터링에서 제외가 된다.
정상 데이터의 경우 데이터 대부분이 크게 벗어나지 않은 범위 내에서 밀집되어 있을 것이고, 이상 데이터의 경우 정상 데이터 범위 밖에 나타날 것이다. 그럴 경우 클러스터링에서 제외가 되기 때문에 이상 데이터를 분류하는데 가능성이 있다.
다만, 비정상 데이터가 클러스터링 조건 범위 이상 발생한다면 비정상 데이터도 정상 데이터와 동일하게 군집이 될 가능성과 반대로 비정상 데이터가 밀집 되어 있고 정상인 데이터가 추 후에 나타난다면 정상인 데이터를 클러스터링에서 제외 되기 때문에 정상 범위 데이터의 수집이 중요하다.