[ML] DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN은 밀도 기반의 군집화 알고리즘으로, 데이터 포인트의 밀집된 영역을 군집으로 식별하고, 밀도가 낮은 데이터 포인트는 노이즈로 간주하는 방식입니다. DBSCAN의 목표는 데이터의 밀집 영역을 찾아내어, 군집의 크기나 형태에 구애받지 않고 유연하게 군집화를 수행하는 것입니다.

https://mrinalyadav7.medium.com/dbscan-algorithm-c894701306d5

---

DBSCAN의 특징

• 밀도 기반 군집화: DBSCAN은 데이터 포인트의 밀도를 기준으로 군집을 형성합니다. 즉, 일정 밀도 이상의 영역을 하나의 군집으로 묶습니다.
• 노이즈 처리: 밀도가 낮은 데이터 포인트는 노이즈로 간주되며, 군집에서 제외됩니다. 이를 통해 군집화 과정에서 노이즈나 이상치를 효과적으로 처리할 수 있습니다.
• 유연한 군집 형성: DBSCAN은 군집의 크기나 형태에 구애받지 않고, 데이터의 밀도에 따라 유연하게 군집을 형성할 수 있습니다. 이는 데이터가 비정형적인 형태를 가질 때 특히 유용합니다.
• 비교적 간단한 구현: DBSCAN 알고리즘은 비교적 간단하고, 구현이 용이하여 다양한 데이터셋에 적용할 수 있습니다.

---

DBSCAN의 기본 원리

밀도 기준 (Density Criteria)

• DBSCAN은 두 개의 주요 하이퍼파라미터를 사용합니다:
  • ϵ(epsilone): 데이터 포인트 간의 최대 거리로, 이 거리 이내의 데이터 포인트들을 하나의 군집으로 묶습니다.
  • 최소 포인트 수 (MinPts): 군집을 형성하기 위해 필요한 최소 데이터 포인트 수입니다. 이는 해당 영역이 군집으로 간주되기 위한 최소 밀도를 결정합니다.

핵심 포인트 (Core Point)

• 반경 ϵ(epsilone) 이내에 최소 MinPts 이상의 데이터 포인트가 있는 데이터 포인트를 핵심 포인트로 정의합니다.
• 핵심 포인트는 군집의 중심 역할을 합니다.

경계 포인트 (Border Point)

• 반경 ϵ(epsilone) 이내에 MinPts 이상의 데이터 포인트는 없지만, 핵심 포인트의 반경 ϵ(epsilone) 내에 위치한 데이터 포인트를 경계 포인트로 정의합니다. 경계 포인트는 군집에 속하지만, 군집을 확장하지는 않습니다.

노이즈 포인트 (Noise Point)

• 핵심 포인트와 경계 포인트 모두에 해당하지 않는 데이터 포인트는 노이즈 포인트로 정의됩니다.
• 이러한 포인트들은 군집에 속하지 않습니다.

---

DBSCAN의 군집 형성과정

초기화

• 모든 데이터 포인트를 방문하지 않은 상태로 초기화합니다.

군집 확장

• 방문하지 않은 데이터 포인트를 선택하여, 해당 포인트가 핵심 포인트인지 확인합니다.
• 만약 핵심 포인트라면, 반경 ϵ(epsilone) 내의 모든 데이터 포인트를 포함하여 새로운 군집을 형성합니다.
• 경계 포인트는 기존 군집에 포함되며, 노이즈 포인트는 군집에 포함되지 않습니다.

반복

• 모든 데이터 포인트가 방문될 때까지 군집 확장 과정을 반복합니다. 이 과정이 끝나면 데이터셋 전체의 군집화가 완료됩니다.

---

DBSCAN의 장, 단점

https://towardsdatascience.com/how-to-use-dbscan-effectively-ed212c02e62

DBSCAN의 장점

1. 군집 수 미리 지정 불필요: DBSCAN은 군집의 수를 사전에 지정할 필요가 없습니다. 군집의 수는 데이터의 밀도에 따라 자동으로 결정됩니다.
2. 노이즈 데이터 처리: DBSCAN은 노이즈 데이터를 효과적으로 처리하여 군집에서 제외할 수 있습니다. 이는 다른 군집화 알고리즘과 비교해 큰 장점입니다.
3. 다양한 군집 형태: DBSCAN은 데이터의 군집 형태가 구형(spherical)이 아니어도 유연하게 군집화할 수 있습니다. 비정형적인 군집 구조를 가진 데이터에 대해 효과적으로 작동합니다.
4. 확장성: DBSCAN은 군집의 크기나 밀도에 관계없이 유연하게 적용 가능하며, 다양한 데이터셋에 사용할 수 있습니다.

DBSCAN의 단점

1. 하이퍼파라미터 설정 어려움: ϵ(epsilone)과 MinPts의 값을 설정하는 것이 어렵습니다. 이 값들이 잘못 설정되면 군집화 결과가 부정확할 수 있습니다.
2. 밀도 변화에 민감: 데이터의 밀도가 균일하지 않을 경우, DBSCAN의 군집화 성능이 저하될 가능성이 있습니다. 밀도가 크게 변하는 영역에서는 군집이 제대로 형성되지 않을 수 있습니다.
3. 고차원 데이터에서의 성능 저하: 고차원 데이터에서는 거리 계산이 어려워 성능이 저하될 수 있습니다. 고차원 공간에서는 데이터 포인트 간의 거리가 매우 비슷해지는 경향이 있어, 군집을 잘 구분하기 어려울 수 있습니다.

---

DBSCAN Example Code

# 필요한 라이브러리 임포트
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

# Iris 데이터셋 로드
iris = load_iris()
X = iris.data
y = iris.target

# 데이터 표준화
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# DBSCAN 모델 생성 및 학습
dbscan = DBSCAN(eps=0.5, min_samples=2)
labels = dbscan.fit_predict(X_scaled)

# 클러스터링 결과 시각화 (첫 번째 두 특징 공간 사용)
plt.figure(figsize=(10, 7))
unique_labels = set(labels)
colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        col = [0, 0, 0, 1]  # 노이즈는 검정색으로 표시

    class_member_mask = (labels == k)
    xy = X_scaled[class_member_mask]

    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=10)

plt.title('DBSCAN Clustering of Iris Dataset (eps=0.5, min_samples=2)')
plt.xlabel('Feature 1 (Standardized)')
plt.ylabel('Feature 2 (Standardized)')
plt.show()