1. DBSCAN

DBSCAN은 "Density-Based Spatial Clustering of Applications with Noise"를 축약한 단어로 말 그대로 노이즈가 있는 데이터에 대해 밀도를 기반으로 공간 클러스터링을 하는 모델이다.

오늘은 DBSCAN의 알고리즘과 하이퍼 파라미터 설정 방법에 대해서 알아보고자 한다.

 

1. 알고리즘

2. 예제

3. 하이퍼 파라미터 설정

 

---

1. 알고리즘

기본 가정

"데이터를 군집으로 분리했을 때, 군집 내 밀도 ↑ / 군집 간 밀도 ↓"
이때, 밀도란 '정해진 반경 내에 데이터가 포함된 정도' 를 의미한다.

 

즉, DBSCAN은 군집 내에 데이터가 많이 밀집해있으면서, 군집 간에는 데이터 간 거리가 멀도록 군집화를 수행한다.

 

알고리즘

DBSCAN 알고리즘

Input：epsilon (반경), 반경 내 존재해야 하는 최소 샘플 수 (MinPts)

1: 모든 데이터에 대해 핵심 데이터와 비 핵심 데이터로 분할

2: 핵심 데이터 중 랜덤으로 하나를 선택하여 클러스터로 정의

3: 선택한 점을 중심으로 반경 내 핵심 데이터를 동일한 클러스터로 할당

4: 2에서 선택했던 점을 제외한 반경 내 핵심 데이터를 기준으로 3번째 과정을 반복

5: 모든 비 핵심 데이터에 대해 반경 내에서 가장 가까운 핵심 데이터의 클러스터로 할당

6: 모든 핵심 데이터에 클러스터를 할당할 때까지 위 과정을 반복

 

- 핵심 데이터 (core point) : 밀도가 높은 집합에 속하는 데이터

- 비 핵심 데이터 (non-core point): 그 외 데이터

  → 핵심 데이터를 중심으로 클러스터를 생성하는 알고리즘이다.

 

복잡한 글로 보는 것보다 예제를 통해 함께 살펴보고자 한다.

---

2. 예제

1) 먼저, 주어진 데이터에 대해서 핵심 데이터와 비핵심 데이터를 구분한다.

이때, 기준은 초기에 설정해준 반경 내 최소 샘플 수 (자기 자신 포함)으로 구분한다.

 

2) 핵심 데이터 중 랜덤으로 하나를 선택하여 클러스터로 정의한다.

3) 그 후, 선택한 점을 중심으로 반경 내 핵심 데이터를 동일한 클러스터로 할당한다.

 

4) 2)에서 선택했던 점을 제외한 반경 내 핵심 데이터를 기준으로 3번째 과정을 반복한다.

 

이 과정은 cluster 1로 할당된 데이터 주변에 모든 핵심 데이터가 cluster 1로 할당될 때까지 반복합니다.

 

5) 모든 비 핵심 데이터에 대해 반경 내에서 가장 가까운 핵심 데이터의 클러스터로 할당한다.

 

위 과정을 통해 cluster 1이 정의됩니다.

 

6) 모든 핵심 데이터에 클러스터를 할당할 때까지 위 과정을 반복한다.

남은 핵심 데이터들은 오른쪽에 위치해있으며, 이들도 위와 같이 동일한 과정을 반복해줍니다.

 

최종적으로, 기존에 아무런 군집도 없던 데이터들이 2개의 군집과 노이즈로 나뉘어진 것을 볼 수 있습니다!

 

정리하면,  DBSCAN에

- 핵심 데이터: 클러스터로 모두 할당이 되는 데이터

- 비 핵심 데이터: 클러스터에서 조금 떨어져 있는 데이터 (클러스터 O) / 노이즈 데이터 (클러스터 X)

로 구성된다.

 

DBSCAN의 장점과 단점을 한번 간단하게 살펴보자.

장점

- 사전 클러스터 개수를 설정하지 않아도 됨

- 이상치 발견이 가능함

- 임의의 모양을 갖는 클러스터를 탐색할 수 있음

 

https://hongl.tistory.com/142 그림 참고

 

위 사진처럼 K-means는 중심점을 기준으로 원의 형태로 클러스터가 구성되지만 DBSCAN은 여러 모양을 갖는 클러스터를 생성할 수 있다.

 

단점

- 고차원 데이터에서는 잘 작동하지 않음

- Sparse Data에 대한 결과가 좋지 않음

---

3. 하이퍼 파라미터 설정

DBSCAN에서 설정해줘야 하는 파라미터는 epsilon (반경)과 MinPts (반경 내 존재해야하는 최소 샘플 수)로 총 2개입니다. 한 논문에서는 이 두 파라미터를 어떻게 정할지에 대한 방법을 제안하였다.

 

A density-based algorithm for discovering cluster in large spatial databases with noise (Ester et al., 1996)

 

이 논문에서는 thinnest cluster라는 용어가 등장한다. 

- thinnest cluster: 데이터 내 존재하는 가장 낮은 밀도를 갖는 클러스터

 

→ 최종적으로  thinnest cluster의 특성을 통해 데이터 내 밀도를 파악하고 이를 활용해 다른 클러스터를 식별하고자 함

 

논문에서 제안한 탐색 방법은 다음과 같다.

하이퍼 파라미터 탐색 방법

Input: parameter(k)

1: 모든 데이터에 대해 k번째로 가장 가까운 데이터와의 거리 계산 (k-dist)

2: k-dist에 따라 내림차순으로 정렬

3: sorted-k-dist 분포를 생성함 (x축: 정렬된 데이터의 index, y축: k-dist)

4: 그래프가 꺾이는 지점인 elbow point를 찾으면 Epsilon = k-dist, Minpts = k가 된다.

 

sorted k-dist graph에서 elbow point를 기준으로 클러스터와 노이즈를 구분한다.

 

이때, 2차원 상에서는 k = 4 사용을 권장한다.

(k를 4와 5로 뒀을 때, 클러스터 결과의 큰 변동이 없고, k가 커질수록 연산량이 매우 커짐)

 

 

DBSCAN Revisited: Why and How You Should (Still) Use DBSCAN (Schubert et al., 2017)
: 3차원 이상의 데이터에서 k는 MinPts = 2 * dimension로 설정

 

- 하이퍼 파라미터 설정 예제

 

예제에 대해 위 방법을 통해 하이퍼 파라미터를 설정하고 군집화 결과를 확인하고자 한다.  이때, 2차원 데이터이므로 k = 4로 설정한다. 

이때, elbow point인 2번과 함께 1번과 3번을 기준으로 세웠을 때, 어떤 군집화 결과가 나타나는지 함께 확인하고자 한다.

 

1번의 경우 대체로 클러스터는 하나이며, 이에 속하지 않는 노이즈는 단 두개임을 알 수 있습니다.

2번은 elbow point로 3개의 군집화 결과가 나타나며 그 군집에서 멀리 떨어져있는 파란 점들은 노이즈로 들어갔음을 알 수 있습니다.

3번은 더 기준이 빡빡하여 클러스터는 30개이지만, 대부분의 데이터가 노이즈로 들어간 것을 확인할 수 있습니다.

 

결과적으로 elbow point인 2번의 군집화 결과가 가장 적절한 군집화 결과임을 확인할 수 있습니다.

 

위 예제에 대한 코드는 다음과 같다.

'''

DBSCAN

'''

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.metrics.pairwise import euclidean_distances
from sklearn.cluster import DBSCAN

# 예제 데이터 생성
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(
    n_samples=750, centers=centers, cluster_std=0.4, random_state=0
)




'''

전처리 작업

'''


# Standard Scaling
X = StandardScaler().fit_transform(X)

# 데이터 분포 확인하기
df = pd.DataFrame(X, columns = ["X1", "X2"])

plt.figure()
plt.scatter(df["X1"], df["X2"], edgecolor = "black",
            facecolor = "black")
plt.xticks(fontsize = 13)
plt.yticks(fontsize = 13)
plt.xlabel("X1", fontsize = 13)
plt.ylabel("X2", fontsize = 13)
plt.tight_layout()


'''

Thinnest cluster 탐색

: 모든 데이터에 대해 k번째로 가까운 데이터와의 거리를 계산하고
  이를 정렬
  -> elbow point가 잘 보이는 k 선정

* 일반적으로 k = 4로 선정

'''

# k를 조정해가면서 그래프 그리기
k_result_dic = {}

fig, ax = plt.subplots(figsize = (12, 6), ncols = 3, nrows = 2)

row, col = 0, 0
for k in range(2, 8):

    k_dist = np.sort(euclidean_distances(df.values, df.values), axis = 1)
    k_result = np.array([x[k-1] for x in k_dist])
    
    
    ax[row][col].set_title("k = %d"%k, fontsize = 14, fontweight = "bold")
    ax[row][col].scatter(range(len(k_result)), np.sort(k_result)[::-1],
                         marker = ".", facecolor = "None", edgecolor = "black")
    
    k_result_dic[k] = k_result
    ax[row][col].tick_params(axis = "both", labelsize = 12)
    ax[row][col].set_ylabel("%d-dist"%k, fontsize = 12)
    col += 1
    if col == 3:
        row = 1; col = 0
plt.tight_layout()


# k번째 데이터와의 거리 계산
k = 4
k_dist = np.sort(euclidean_distances(df.values, df.values), axis = 1)
k_result = np.array([x[k] for x in k_dist])


# elbow point: 70
# 3가지 경우 고려: 70 기준 이보다 더 작은 k_dist, 더 큰 k_dist 선정
fig, ax = plt.subplots(figsize = (6, 4))
ax.set_title("k = %d"%k, fontsize = 14, fontweight = "bold")
ax.scatter(range(len(k_result)), np.sort(k_result)[::-1],
                         marker = ".", facecolor = "None", edgecolor = "black")
ax.tick_params(axis = "both", labelsize = 12)
ax.set_ylabel("%d-dist"%k, fontsize = 12)
ax.axvline(10, color = "red")
ax.axvline(70, color = "red")
ax.axvline(700, color = "red")

plt.tight_layout()


# 그래프 결과대로 정렬
k_dist_result = np.sort(k_result)[::-1]

i = 0
fig, ax = plt.subplots(figsize = (15, 4), ncols = 3)

for k_d in [10, 70, 700]:
    eps = k_dist_result[k_d]
    
    print(eps)
    
    
    dbscan = DBSCAN(eps = eps, min_samples = k).fit(df.values)
    df.loc[:, "result"] = dbscan.labels_
    
    cmap = plt.cm.Spectral
    
    # k_dist에 따라 클러스터링 결과 시각화
    sns.scatterplot(data = df, x = "X1", y = "X2", hue = "result",
                        palette = "dark", legend = False, ax = ax[i])
    
    ax[i].set_title("Cluster: %d (noise: %d)"%(len(df.result.unique())-1, len(df[df.result == -1])), 
                    fontweight = "bold", fontsize = 15)
    ax[i].tick_params(axis = "both", labelsize = 12)
    ax[i].set_xlabel("X1", fontsize = 12)
    ax[i].set_ylabel("X2", fontsize = 12)
    print(df.result.values)
    print(len(df.result.unique()))
    print(round(eps, 4))
    i+=1
    
plt.tight_layout()

---

오늘은 군집화 기법인 DBSCAN 알고리즘과 하이퍼 파라미터 설정 방법에 대해서 정리해봤다.

다음 포스트에서는 SOM 군집화 기법에 대한 알고리즘에 대해서 알아보고자 한다.