군집화(Clustering)는 레이블이 없는 데이터에서 유사한 특성을 가진 객체들을 그룹으로 묶는 대표적인 비지도 학습 기법입니다. 그중에서도 K-Means와 DBSCAN은 가장 널리 사용되는 두 알고리즘으로, 군집을 정의하는 방식과 작동 원리에서 큰 차이를 보입니다. 이번 글에서는 두 알고리즘의 개념과 특징을 살펴보고, 주요 차이점을 표로 정리해 보겠습니다.
K-Means란?
K-Means 클러스터링은 대표적인 분할(partitioning) 기반 군집화 알고리즘입니다. 데이터셋의 모든 데이터를 새롭게 형성된 K개의 군집 중 하나에 배정하며, 각 데이터 포인트는 거리(distance) 또는 유사도(similarity) 측정 기준에 따라 가장 가까운 군집에 할당됩니다.
K-Means에서는 객체가 가장 가까운 중심(center)에 배정되는 방식으로 동작합니다. 또한 cannot-link 제약 조건(특정 객체들이 같은 군집에 함께 속하지 못하도록 하는 제약)을 정의할 수 있으며, 이 경우 일반적인 '최근접 중심 할당' 방식을 '적용 가능한 가장 가까운 중심 할당' 방식으로 수정하여 사용합니다.
객체들이 순차적으로 중심에 배정될 때, 각 단계마다 지금까지의 할당 결과가 cannot-link 제약 조건을 위반하지 않도록 확인합니다. 즉, 객체는 가장 가까운 중심에 배정되되, 해당 배정이 제약 조건을 준수하는 방향으로 이루어집니다.
DBSCAN이란?
DBSCAN은 'Density-Based Spatial Clustering of Applications with Noise'의 약자로, 밀도(density) 기반 군집화 알고리즘입니다. 이 알고리즘은 충분히 높은 밀도를 가진 영역들을 군집으로 묶어내며, 노이즈가 포함된 공간 데이터베이스에서도 임의의 모양을 가진 군집까지 발견할 수 있습니다. DBSCAN은 군집을 '밀도 연결(density-connected)된 점들의 최대 집합'으로 정의합니다.
밀도 기반 군집이란 밀도 도달 가능성(density-reachability) 관점에서 최대가 되는, 밀도 연결된 객체들의 집합을 의미합니다. 어떤 군집에도 속하지 않는 객체는 모두 노이즈(noise)로 간주됩니다.
DBSCAN은 데이터베이스 내 모든 점의 ε-이웃(ε-neighborhood)을 검사하는 방식으로 군집을 찾아냅니다. 어떤 점 p의 ε-이웃에 MinPts보다 많은 점이 포함되어 있다면, p를 핵심(core) 요소로 하는 새로운 군집이 생성됩니다. 이후 DBSCAN은 이러한 핵심 요소로부터 밀도 도달 가능한 객체들을 반복적으로 수집하며, 이 과정에서 여러 밀도 도달 가능한 군집이 병합될 수도 있습니다. 더 이상 어떤 군집에도 새로운 점을 추가할 수 없게 되면 프로세스가 종료됩니다.
K-Means vs DBSCAN 주요 차이점 비교
| K-Means | DBSCAN |
|---|---|
| 일반적으로 모든 객체를 군집에 배정합니다. | 노이즈로 판단된 객체는 제외합니다. |
| 프로토타입(대표점) 기반의 군집 개념이 필요합니다. | 밀도 기반의 군집 개념이 필요합니다. |
| 구형(globular)이 아닌 군집이나 크기가 서로 다른 여러 군집을 다루는 데 어려움을 겪습니다. | 다양한 크기와 구조의 군집을 처리할 수 있으며, 노이즈나 이상치(outlier)의 영향을 크게 받지 않습니다. |
| 평균이나 중앙값처럼 명확한 중심(centroid)을 가지는 데이터에 적합합니다. | 전통적인 유클리드 밀도 개념에 기반한 밀도 정의가 해당 데이터에 의미 있게 적용될 수 있어야 합니다. |
| 문서 데이터처럼 희소(sparse)하고 고차원인 데이터에도 사용할 수 있습니다. | 전통적인 유클리드 밀도 정의가 고차원 데이터에서 잘 작동하지 않기 때문에, 이런 데이터에서는 일반적으로 성능이 좋지 않습니다. |
| 기본 K-Means 알고리즘은 모든 군집이 평균은 다르지만 공분산 행렬이 동일한 구형 가우시안 분포에서 나온다고 가정하는 통계적 군집화 접근법(혼합 모델, mixture models)과 유사합니다. | 데이터의 분포에 대해 어떠한 사전 가정도 하지 않습니다. |
마무리
정리하면, K-Means는 구현이 간단하고 계산 속도가 빨라 명확한 중심을 가진 데이터에 적합한 반면, DBSCAN은 군집의 개수를 미리 정할 필요가 없고 임의 형태의 군집과 노이즈 처리에 강점을 가집니다. 따라서 데이터의 특성과 분석 목적에 따라 적절한 알고리즘을 선택하는 것이 성공적인 군집 분석의 핵심입니다.