DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 1996년 Martin Ester 등이 제안한 대표적인 밀도 기반 군집화 알고리즘입니다. 이 알고리즘은 두 가지 핵심 인자, 즉 이웃 반경(\( \varepsilon \) 또는 eps)과 최소 샘플 수(MinPts)를 활용하여 데이터 내의 고밀도 영역을 식별합니다. 이를 통해 어떤 형태의 군집이라도 효과적으로 찾아낼 수 있으며, 밀도가 낮은 영역의 점들은 자동으로 노이즈(이상치)로 분류하는 강점을 가집니다.
전통적인 거리 기반 알고리즘인 K-평균(K-Means)과 비교했을 때, DBSCAN은 다음과 같은 차별화된 이점을 제공합니다:
- 사전에 군집의 개수를 지정할 필요 없이, 데이터의 본질적인 구조에 따라 적절한 군집 수를 자동으로 결정합니다.
- 원형, 초승달형 등 비볼록(non-convex) 형태의 군집도 성공적으로 발견할 수 있습니다.
- 노이즈 데이터에 대한 강력한 내성을 가지며, 이상치를 효과적으로 분리해냅니다.
- 초기 값 선택에 덜 민감하여, 분석 결과의 안정성이 높습니다.
예를 들어, 스마트 시티의 센서 데이터를 분석할 때, DBSCAN은 교통량 패턴이나 환경 오염 수준과 같은 고밀도 영역을 기반으로 다양한 지역 특성 군집을 파악할 수 있으며, 동시에 이상 징후를 보이는 센서 데이터는 노이즈로 분류하여 관제 시스템의 효율성을 높일 수 있습니다.
DBSCAN 알고리즘 이해
핵심 개념
(1) 주요 파라미터
eps (\( \varepsilon \)): 특정 점의 이웃 반경을 정의하는 값입니다. 두 샘플이 이 반경 내에 있을 때 서로 이웃으로 간주됩니다. 이 파라미터는 군집의 범위와 밀도를 직접적으로 제어합니다.
- 작은 값은 군집이 과도하게 분할될 수 있습니다.
- 큰 값은 본래 분리되어야 할 군집들을 하나로 합칠 수 있습니다.
min_samples (MinPts): 코어 점(Core Point)으로 정의되기 위해 특정 점의 \( \varepsilon \)-이웃 내에 존재해야 하는 최소 샘플 수입니다. 이 인자는 특정 영역이 밀집 지역으로 인정되는 데 필요한 데이터 점의 최소 개수를 결정합니다.
- 일반적으로 3~10 사이의 값을 사용하며, 데이터셋의 크기와 차원에 따라 달라집니다.
- 데이터에 노이즈가 많을수록 더 큰 값을 선택하는 것이 좋습니다.
(2) 점의 분류
코어 점 (Core Point):
- \( \varepsilon \)-이웃 내에 최소 min_samples 이상의 샘플을 포함하는 점입니다.
- 군집을 형성하는 데 기반이 되는 중요한 점입니다.
- 예: 2차원 공간에서 어떤 점의 반경 0.3(\( \varepsilon \)=0.3) 내에 5개 이상의 점(min_samples=5)이 존재하는 경우.
경계 점 (Border Point):
- 자신은 코어 점이 아니지만, 어떤 코어 점의 \( \varepsilon \)-이웃에 속하는 점입니다.
- 군집의 가장자리에 위치하며, 코어 점 주변에 있지만 자체적으로는 충분한 밀도를 갖지 못합니다.
- 예: 어떤 점의 반경 0.3 내에 이웃이 3개뿐(min_samples=5)이지만, 다른 코어 점의 이웃에 포함되어 있는 경우.
노이즈 점 (Noise Point):
- 코어 점도 아니고 경계 점도 아닌 모든 점입니다.
- 알고리즘에 의해 이상치로 분류됩니다.
- 예: 어떤 점 주변에 충분한 이웃이 없으며, 어떤 코어 점의 이웃에도 속하지 않는 경우.
알고리즘 절차
1. 미방문 점 선택
- 데이터셋에서 아직 처리되지 않은 임의의 데이터 점을 선택합니다.
- 실제 구현에서는 재현성을 위해 종종 시드(seed) 값을 설정하기도 합니다.
2. 이웃 밀도 검사
- 선택된 점을 중심으로 \( \varepsilon \) 반경 내의 모든 점을 찾습니다.
- 조건 검사:
- 이웃 점의 수가 min_samples 이상인 경우:
- 해당 점을 코어 점으로 지정합니다.
- 새로운 군집을 생성하고, 이 점을 새 군집에 포함시킵니다.
- 그렇지 않은 경우:
- 일단 노이즈 점으로 임시 분류합니다 (추후 다른 군집의 경계 점이 될 수도 있습니다).
- 이웃 점의 수가 min_samples 이상인 경우:
3. 군집 확장
- 새롭게 발견된 코어 점에 대해, 그 \( \varepsilon \)-이웃 내의 모든 점들을 재귀적으로 처리합니다.
- 아직 분류되지 않은 이웃 점들은 현재 군집에 추가합니다.
- 만약 이웃 점 중 새로운 코어 점이 발견되면, 이 코어 점을 중심으로 군집 확장을 계속합니다.
- 이 과정은 일반적으로 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 방식으로 수행됩니다.
4. 반복
- 모든 데이터 점이 방문되고 분류될 때까지 1단계로 돌아가 다음 미방문 점을 선택하고 과정을 반복합니다.
장점 및 단점
장점
- 군집 개수 불필요 (K-Means와 비교):
- 데이터 자체의 밀도 구조를 통해 군집 수를 자동 결정합니다.
- 데이터 분포에 대한 사전 정보가 없을 때 매우 유용합니다.
- 임의 형태 군집 감지:
- 밀도 연결성을 기반으로 하므로, 원형이나 선형 등 복잡한 형태의 군집도 정확하게 찾아냅니다.
- 예: K-평균이 여러 조각으로 나눌 수 있는 고리형 데이터도 하나의 군집으로 인식합니다.
- 노이즈에 강인:
- 노이즈 점을 명시적으로 식별하고 분리하는 메커니즘을 가집니다.
- 예: 10%의 무작위 노이즈가 포함된 데이터셋에서도 안정적인 군집 결과를 보입니다.
단점
- 파라미터 (\( \varepsilon \), min_samples) 민감성:
- 결과가 파라미터 설정에 크게 좌우되므로, 적절한 값 조절이 필요합니다.
- k-거리 그래프와 같은 도구를 사용하여 최적의 파라미터를 추정할 수 있습니다.
- 밀도 차이 큰 데이터에 부적합:
- 단일 \( \varepsilon \) 값으로는 밀도가 크게 다른 영역을 동시에 처리하기 어렵습니다.
- 예: 매우 밀집된 군집과 매우 희박한 군집이 공존하는 데이터셋에서는 성능이 저하될 수 있습니다.
- 고차원 데이터 성능 저하 ("차원의 저주"):
- 고차원 공간에서는 거리 측정의 신뢰도가 낮아져 성능이 떨어집니다.
- 종종 차원 축소 전처리 과정이 요구됩니다.
- 계산 복잡성:
- 모든 점 쌍 간의 거리를 계산해야 하므로, 시간 복잡도는 \(O(n^2)\)에 가깝습니다. 대규모 데이터셋에서는 속도가 느릴 수 있습니다.
- KD-트리 같은 공간 인덱싱 기법을 사용하여 최적화할 수 있습니다.
Python을 활용한 DBSCAN 실습
sklearn.cluster.DBSCAN 클래스는 DBSCAN 알고리즘을 구현한 Scikit-learn 라이브러리의 핵심 구성 요소입니다.
class sklearn.cluster.DBSCAN(
eps=0.5, # 이웃 반경 (epsilon)
min_samples=5, # 코어 점의 최소 이웃 샘플 수 (MinPts)
metric='euclidean', # 거리 측정 방식
metric_params=None,
algorithm='auto', # 이웃 검색 알고리즘 ('auto', 'ball_tree', 'kd_tree', 'brute')
leaf_size=30, # 트리 기반 알고리즘의 리프(leaf) 크기
p=None, # 민코프스키 거리의 p 값 (p=2는 유클리드 거리)
n_jobs=None # 병렬 처리할 CPU 코어 수
)
주요 파라미터
| 파라미터 | 유형 | 기본값 | 설명 |
|---|---|---|---|
eps |
float | 0.5 |
이웃 반경. 이 거리 내에 있는 점들은 이웃으로 간주됩니다. |
min_samples |
int | 5 |
코어 점이 되기 위해 \( \varepsilon \)-이웃 내에 필요한 최소 샘플 수. |
metric |
str or callable | 'euclidean' |
거리 계산 방식 ('euclidean', 'manhattan', 'cosine' 등). 사용자 정의 함수도 가능합니다. |
algorithm |
str | 'auto' |
이웃 검색에 사용될 알고리즘 ('ball_tree', 'kd_tree', 'brute'). 'auto'는 데이터에 따라 최적의 방식을 선택합니다. |
leaf_size |
int | 30 |
BallTree 또는 KDTree 알고리즘에서 리프 노드의 최대 크기. |
p |
float | None |
민코프스키 거리의 차수. p=1은 맨해튼 거리, p=2는 유클리드 거리. |
n_jobs |
int | None |
병렬로 실행될 작업 수. -1은 모든 CPU 코어를 사용합니다. |
속성
| 속성 | 유형 | 설명 |
|---|---|---|
core_sample_indices_ |
ndarray | 코어 점들의 원본 데이터 인덱스 배열입니다. |
components_ |
ndarray | 코어 점들의 실제 좌표 값 (형태: [n_core_samples, n_features]). |
labels_ |
ndarray | 각 샘플에 할당된 군집 레이블 (노이즈는 -1). |
메서드
(1) fit(X)
- 기능: 입력 데이터
X에 DBSCAN 모델을 적합(fit)시킵니다. - 파라미터:
X: 입력 데이터 (형태[n_samples, n_features]).
- 반환:
self: 적합된 모델 인스턴스.
(2) fit_predict(X)
- 기능: 모델을 적합시킨 후, 각 샘플에 대한 군집 레이블을 즉시 반환합니다.
- 파라미터:
X: 입력 데이터 (형태[n_samples, n_features]).
- 반환:
labels: 각 샘플의 군집 레이블 (형태[n_samples]). 노이즈 점은-1입니다.
예제: DBSCAN 파라미터 튜닝 및 결과 분석
다음 예제에서는 datingTestSet2.txt 파일을 사용하여 DBSCAN의 파라미터를 최적화하고 군집 결과를 분석하는 과정을 보여줍니다. 실루엣 점수(silhouette score)를 활용하여 최적의 파라미터 조합을 탐색합니다.
import pandas as pd
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import numpy as np
# 1. 데이터 로드 및 전처리
# 'datingTestSet2.txt'는 탭으로 구분된 텍스트 파일이라고 가정합니다.
raw_data = pd.read_csv('datingTestSet2.txt', sep='\t')
scaled_features = StandardScaler().fit_transform(raw_data) # 데이터 표준화
# 2. DBSCAN 파라미터 후보 정의
# eps_options: 이웃 반경 후보 목록
eps_options = np.arange(0.3, 1.0, 0.1)
# min_pts_options: 코어 점의 최소 이웃 샘플 수 후보 목록
min_pts_options = np.arange(2, 8, 1)
optimal_params = {'eps': 0, 'min_samples': 0}
max_silhouette = -1 # 초기 실루엣 점수 최댓값
# 3. 그리드 탐색을 통한 최적 파라미터 찾기
print("DBSCAN 파라미터 그리드 탐색 시작...")
for current_eps in eps_options:
for current_min_pts in min_pts_options:
# DBSCAN 모델 생성 및 예측
db_model = DBSCAN(eps=current_eps, min_samples=current_min_pts)
cluster_labels = db_model.fit_predict(scaled_features)
# 유효한 군집이 2개 이상일 때만 실루엣 점수 계산 가능
if len(set(cluster_labels)) > 1:
score = silhouette_score(scaled_features, cluster_labels)
if score > max_silhouette:
max_silhouette = score
optimal_params['eps'] = current_eps
optimal_params['min_samples'] = current_min_pts
print(f"최적의 파라미터: {optimal_params}")
# 4. 최적 파라미터로 DBSCAN 재실행 및 결과 평가
final_db_model = DBSCAN(eps=optimal_params['eps'], min_samples=optimal_params['min_samples'])
final_labels = final_db_model.fit_predict(scaled_features)
# 군집 평가 지표 출력
print(f"\n최대 실루엣 점수: {max_silhouette:.4f}")
print(f"노이즈 점 비율: {sum(final_labels == -1) / len(final_labels):.4f}")
# 노이즈(-1)를 제외한 고유 군집 개수 계산
num_clusters = len(set(final_labels)) - (1 if -1 in final_labels else 0)
print(f"총 군집 개수: {num_clusters}")
다음은 K-거리 그래프를 통해 eps 파라미터의 초기값을 추정하고, 그 값을 기반으로 더 정교한 파라미터 튜닝과 시각화를 수행하는 예제입니다.
import pandas as pd
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
from sklearn.neighbors import NearestNeighbors
# 1. 데이터 로드 및 전처리
raw_data = pd.read_csv('datingTestSet2.txt', sep='\t')
scaled_features = StandardScaler().fit_transform(raw_data)
# 2. K-거리 그래프를 통한 eps 값 추정 함수
def visualize_k_distance_plot(data_matrix, k_value=4):
"""
K-거리 그래프를 그려 eps 파라미터 추정에 도움을 줍니다.
:param data_matrix: 스케일링된 데이터 행렬
:param k_value: min_samples의 후보값
"""
neighbors_model = NearestNeighbors(n_neighbors=k_value).fit(data_matrix)
distances, _ = neighbors_model.kneighbors(data_matrix)
# 각 점의 k번째 가장 가까운 이웃까지의 거리를 정렬
k_distances_sorted = np.sort(distances[:, -1])
plt.figure(figsize=(10, 6))
plt.plot(k_distances_sorted)
plt.xlabel('정렬된 데이터 포인트 인덱스', fontsize=12)
plt.ylabel(f'{k_value}번째 최근접 이웃 거리', fontsize=12)
plt.title('K-거리 그래프 (Eps 파라미터 선택)', fontsize=14)
plt.grid(True)
plt.show()
# min_samples의 후보값을 4로 설정하여 K-거리 그래프 시각화
print("K-거리 그래프를 통해 eps 값을 시각적으로 추정합니다. 그래프의 '급격한 변화점(elbow)'을 주목하세요.")
visualize_k_distance_plot(scaled_features, k_value=4)
# 3. 파라미터 튜닝 (K-거리 그래프 결과 기반으로 범위 조정)
# K-거리 그래프에서 관찰된 '급격한 변화점'을 기준으로 eps 후보 범위를 설정합니다.
eps_candidates = np.linspace(0.4, 1.2, 9) # 예를 들어, 0.4부터 1.2까지 9개 값
min_pts_candidates = [3, 5, 8, 12] # min_samples 후보군 (차원 수 + 1 또는 그 이상)
best_silhouette_score = -1
optimal_params_found = {}
print("\nDBSCAN 파라미터 정밀 튜닝 시작...")
for current_eps in eps_candidates:
for current_min_pts in min_pts_candidates:
db_model_tune = DBSCAN(eps=current_eps, min_samples=current_min_pts)
cluster_labels_tune = db_model_tune.fit_predict(scaled_features)
# 2개 이상의 군집이 형성되어야 실루엣 점수 계산 가능
if len(set(cluster_labels_tune)) > 1:
score = silhouette_score(scaled_features, cluster_labels_tune)
if score > best_silhouette_score:
best_silhouette_score = score
optimal_params_found = {'eps': current_eps, 'min_samples': current_min_pts}
# 4. 최적 파라미터로 모델 최종 학습 및 평가
final_db_model_optimal = DBSCAN(**optimal_params_found)
final_cluster_labels = final_db_model_optimal.fit_predict(scaled_features)
# 결과 출력
print(f"\n최적 파라미터: {optimal_params_found}")
print(f"최대 실루엣 점수: {best_silhouette_score:.4f}")
print(f"노이즈 점 비율: {sum(final_cluster_labels == -1) / len(final_cluster_labels):.4f}")
num_final_clusters = len(set(final_cluster_labels)) - (1 if -1 in final_cluster_labels else 0)
print(f"최종 군집 개수: {num_final_clusters}")
# 5. 군집 결과 시각화 (데이터가 2차원 또는 주성분 분석으로 2차원 축소된 경우)
# 실제 데이터의 차원이 2차원이 아닐 수 있으므로, 예시를 위해 0번째와 1번째 특성만 사용합니다.
if scaled_features.shape[1] >= 2:
plt.figure(figsize=(10, 7))
# 노이즈(-1)는 회색으로, 각 군집은 다른 색상으로 표시
unique_labels = set(final_cluster_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, 0.6] # 검은색, 투명도 0.6
class_member_mask = (final_cluster_labels == k)
xy = scaled_features[class_member_mask]
plt.scatter(xy[:, 0], xy[:, 1], c=[col], s=30, alpha=0.7,
edgecolor='k' if k != -1 else None, label=f'군집 {k}' if k != -1 else '노이즈')
plt.title('DBSCAN 군집 분석 결과', fontsize=14)
plt.xlabel('특성 1 (표준화)', fontsize=12)
plt.ylabel('특성 2 (표준화)', fontsize=12)
plt.legend()
plt.grid(True)
plt.show()
else:
print("\n데이터 차원이 낮아 (1차원) 산점도 시각화가 제한적입니다.")