DBSCAN — 군집 수를 몰라도 밀도로 경계를 찾는 알고리즘
DBSCAN이 Eps·MinPts로 Core/Border/Noise 포인트를 구분해 군집을 형성하는 원리, 파라미터 선정법, 시간복잡도, OPTICS·HDBSCAN 등 변형과 실제 활용 사례를 정리한다.
2026-08-13 · 최초 발행 2025-05-23
몇 개의 군집으로 나눌지 미리 알 수 없는 데이터가 있다. K-Means는 이런 상황에 약하지만, 1996년 Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu가 제안한 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 클러스터 수를 사전에 지정하지 않고도 데이터 포인트의 밀도만으로 군집을 형성한다.
Core·Border·Noise로 나누는 기준
DBSCAN은 두 개의 파라미터로 군집을 정의한다. **Eps(ε)**는 이웃을 정의하는 반경이고, MinPts는 클러스터 형성을 위한 최소 포인트 수다.
이 두 파라미터를 기준으로 모든 데이터 포인트는 다음 유형으로 나뉜다.
- Core Point: 반경 Eps 내에 MinPts 이상의 다른 포인트를 갖는 포인트
- Border Point: Core Point는 아니지만 Core Point의 이웃인 포인트
- Noise Point: Core Point도 아니고 Border Point도 아닌 포인트
군집이 뻗어나가는 절차
DBSCAN은 다음 단계로 작동한다.
- 임의의 포인트 P를 선택한다.
- P의 Eps 반경 내 이웃 포인트를 찾는다.
- 이웃 포인트 수가 MinPts 이상이면 P를 Core Point로 설정하고 새 클러스터를 시작한다.
- 이웃의 모든 포인트를 재귀적으로 방문하여 같은 클러스터에 할당한다.
- 모든 포인트가 처리될 때까지 1~4를 반복한다.
강점과 한계
클러스터 수를 사전에 지정할 필요가 없고, 임의 모양의 클러스터를 발견할 수 있으며, 노이즈에 강건하고 이상치 감지 능력을 갖췄다. 대용량 데이터베이스에도 적합한 확장성이 있다.
반면 밀도가 다양한 클러스터를 처리하기 어렵고, 고차원 데이터에서는 성능이 떨어진다. Eps와 MinPts 파라미터 선택이 결과에 큰 영향을 미치며, 병렬 처리 구현도 복잡하다.
Eps와 MinPts는 어떻게 정하나
Eps 값을 선정하는 일반적인 방법은 K-거리 그래프를 활용하는 것이다.
- 각 포인트에 대해 K번째 가장 가까운 이웃까지의 거리를 계산한다.
- 거리를 오름차순으로 정렬하여 그래프로 표시한다.
- 그래프에서 급격한 변화(elbow point)가 발생하는 지점을 Eps로 선택한다.
MinPts는 일반적으로 데이터 차원(D)을 고려해 MinPts ≥ D+1을 권장한다. 2차원 데이터라면 최소 4 이상으로 설정하고, 노이즈 감지 능력을 강화하려면 더 큰 값(10~20)을 쓸 수 있다.
sklearn으로 밀도 군집을 돌려보면
from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
# 데이터 생성
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# DBSCAN 모델 생성 및 학습
dbscan = DBSCAN(eps=0.3, min_samples=5)
clusters = dbscan.fit_predict(X)
# 결과 시각화
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis', marker='o', s=50)
plt.title('DBSCAN Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.colorbar(label='Cluster Label')
plt.grid(True)
plt.show()
# 클러스터 통계
n_clusters = len(set(clusters)) - (1 if -1 in clusters else 0)
n_noise = list(clusters).count(-1)
print(f'클러스터 수: {n_clusters}')
print(f'노이즈 포인트 수: {n_noise}')시간 복잡도와 최적화
일반적인 구현의 시간 복잡도는 O(n²)(n은 데이터셋의 포인트 수)이지만, R-tree·KD-tree 같은 공간 인덱싱 구조를 쓰면 O(n log n)으로 개선된다. 대규모 데이터셋에서는 근사 알고리즘이나 병렬 처리 버전을 쓰는 것이 권장된다.
공간 인덱싱 활용은 R-Tree·KD-Tree 등으로 근접 이웃 검색을 가속화해 시간 복잡도를 O(n²)에서 O(n log n)으로 개선한다. 병렬 처리 구현은 각 코어 포인트 탐색 과정을 병렬화해 대규모 데이터셋 처리 속도를 높인다. 근사 알고리즘 적용은 LSH(Locality-Sensitive Hashing)를 활용해 정확도를 약간 희생하는 대신 처리 속도를 대폭 개선한다.
밀도가 다른 클러스터를 위한 변형
**OPTICS(Ordering Points To Identify the Clustering Structure)**는 DBSCAN의 확장 버전으로 다양한 밀도의 클러스터를 처리할 수 있다. 고정된 Eps 대신 클러스터 추출을 위한 순서를 계산해, 밀도 기반 클러스터링의 계층적 구조를 제공한다.
**HDBSCAN(Hierarchical DBSCAN)**은 클러스터의 계층적 구조를 제공하는 DBSCAN의 확장 버전이다. 다양한 밀도의 클러스터링이 가능하고 Eps 파라미터가 필요 없으며, 계층적 클러스터 구조를 제공한다.
**DENCLUE(DENsity-based CLUstEring)**는 영향력 함수를 사용해 밀도를 수학적으로 모델링하는 방식으로, 노이즈 처리 능력이 강화되고 복잡한 분포의 클러스터도 식별할 수 있다.
지리 공간 분석부터 생물정보학까지
지리 공간 데이터 분석에서는 지리정보시스템(GIS)에서 도시 밀집 지역 식별, 교통 혼잡 지점 탐지 등에 DBSCAN이 쓰인다. 서울시는 DBSCAN을 활용해 유동인구 데이터를 분석, 상권 형성 패턴과 밀집 지역을 식별해 도시 계획에 반영했다.
이상치 탐지에서는 금융 사기 탐지, 네트워크 침입 감지 등에서 정상 패턴과 다른 이상 행동을 감지하는 데 활용된다. 대형 신용카드 회사들은 DBSCAN 기반 알고리즘으로 고객의 비정상적인 소비 패턴을 감지해 카드 도용 사고를 예방한다.
이미지 처리 및 컴퓨터 비전에서는 이미지 내 객체 세분화, 패턴 인식 등에 DBSCAN이 쓰인다. 의료 영상에서 종양과 같은 이상 조직을 자동으로 식별하는 시스템에 DBSCAN이 적용되어 의사의 진단을 보조한다.
생물정보학에서는 유전자 발현 데이터 분석, 단백질 구조 분석 등에 DBSCAN이 활용된다. 암 연구에서는 DBSCAN을 통해 유사한 유전자 발현 패턴을 가진 환자 그룹을 식별해 맞춤형 치료법 개발에 기여했다.
운영 관점에서 볼 것들
데이터 품질 관리 과정에서는 이상치 식별에, 데이터 통합 과정에서는 중복 데이터 군집화에 DBSCAN을 쓸 수 있다. 비즈니스 인텔리전스 관점에서는 고객 세분화 전략 수립과 행동 패턴 기반 사용자 그룹 식별로 마케팅 전략을 개선하는 데 활용된다. 데이터 아키텍처 관점에서는 대용량 데이터 환경에서의 효율적인 DBSCAN 구현 설계와 분산 처리 환경에서의 최적화 방안이 과제가 되며, 보안·컴플라이언스 관점에서는 이상 패턴 감지를 통한 보안 위협 식별과 데이터 접근 패턴 분석을 통한 내부자 위협 탐지에도 쓰인다.