밀도로 묶는 DBSCAN과 확률로 묶는 GMM

중심점 기반 클러스터링에는 두 가지 전제가 깔려 있다. K-Means는 각 점을 가장 가까운 중심점에 붙이기 때문에 경계가 늘 직선이 되고, 그래서 둥근 덩어리만 제대로 잡는다. 그리고 클러스터 개수 K를 입력으로 받으므로 덩어리가 몇 개인지 사람이 미리 정해 줘야 한다.

두 전제가 동시에 어긋나는 데이터는 드물지 않다.

위쪽은 K-Means에 K=2를 준 결과다. 마름모가 두 중심점이고 점선이 그 사이의 수직이등분선인데, 이 직선 하나가 경계의 전부다. 초승달 두 개를 위아래로 나누는 대신 대각선으로 갈라 버렸고, 각 클러스터에 두 초승달의 조각이 섞여 들어갔다. 아래쪽은 같은 데이터에 DBSCAN을 돌린 결과다. 초승달을 하나씩 통째로 잡았고, 끝자락에서 떨어져 나온 세 점은 어느 클러스터에도 넣지 않았다.

두 알고리즘은 서로 다른 방향으로 전제를 푼다. DBSCAN은 모양과 개수 가정을 둘 다 버리고 밀도만 본다. GMM은 둥글다는 가정을 타원까지 넓히고, 소속을 0과 1이 아니라 확률로 매긴다.

DBSCAN, 밀도가 이어지는 만큼 넓힌다

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 “이 근처에 점이 충분히 모여 있는가”만 묻는다. 판단에 필요한 값은 둘이다.

• eps: 이웃으로 칠 반경. 한 점에서 이 거리 안에 있는 점이 그 점의 이웃이다
• min_samples: 핵심점이 되기 위해 반경 안에 있어야 할 점의 최소 개수. sklearn에서는 자기 자신도 이 수에 포함된다

이 둘로 모든 점이 세 갈래로 나뉜다.

그림에서 왼쪽 원 안에는 자신을 포함해 여섯 점이 있으니 가운데 점은 핵심점이다. 주황 사각형은 자기 반경 안에 자신과 핵심점 둘뿐이라 핵심점 조건에 못 미치지만, 핵심점의 반경 안에 들어 있어 그 클러스터에 딸려 들어간다. 오른쪽 점은 반경 안이 비어 있고 다른 핵심점의 반경에도 안 걸리니 잡음이다.

클러스터를 만드는 절차는 이 분류에서 곧장 나온다. 아직 방문하지 않은 핵심점 하나를 골라 새 클러스터를 열고, 그 점의 이웃을 전부 클러스터에 넣는다. 새로 들어온 이웃 중에 핵심점이 있으면 그 점의 이웃도 다시 끌어온다. 더 끌어올 핵심점이 없을 때까지 이 연쇄를 반복하면 클러스터 하나가 끝나고, 남은 핵심점에서 다시 시작한다. K-Means처럼 중심에서 원형으로 퍼지는 것이 아니라 밀도가 이어지는 방향이면 어디로든 뻗어 나가기 때문에, 초승달이든 고리든 따라갈 수 있다.

eps는 k-distance 그래프로 고른다

DBSCAN에서 손이 가장 많이 가는 값이 eps다. 너무 작으면 대부분이 잡음이 되고, 너무 크면 전부 한 덩어리가 된다. 실전에서는 각 점의 $k$번째 최근접 이웃까지의 거리를 구해 오름차순으로 그린 뒤, 곡선이 급하게 치솟기 시작하는 지점의 y값을 후보로 삼는다. 그 아래는 이웃이 촘촘한 점들이고 위는 성긴 점들이다.

import numpy as np
from sklearn.neighbors import NearestNeighbors

k = 5  # min_samples와 같은 값
distances, _ = NearestNeighbors(n_neighbors=k).fit(X).kneighbors(X)
k_distances = np.sort(distances[:, -1])   # 이 곡선이 꺾이는 높이가 eps 후보

min_samples는 차원 수를 기준으로 잡는다. 최소한 n_features + 1은 되어야 하고, 경험적으로는 2 * n_features를 출발점으로 쓴다. 잡음이 많은 데이터라면 더 올린다. 2차원이면 4나 5에서 시작하면 대체로 무난하다.

밀도가 다른 덩어리가 섞이면 약하다

DBSCAN의 약점은 eps가 데이터 전체에 하나뿐이라는 데서 나온다. 촘촘한 덩어리와 성긴 덩어리가 한 데이터에 같이 있으면, 촘촘한 쪽에 맞춰 eps를 줄이면 성긴 덩어리가 통째로 잡음이 되고, 성긴 쪽에 맞춰 늘리면 촘촘한 덩어리들이 하나로 합쳐진다. 하나의 반경으로 여러 밀도 수준을 동시에 담을 방법이 없다.

HDBSCAN은 이 문제를 겨냥한 확장이다. 고정된 eps 하나를 쓰는 대신 여러 밀도 수준에서 클러스터 계층을 만들고, 그중 밀도 변화에 가장 오래 버티는 클러스터를 골라낸다. 정할 값도 min_cluster_size 하나로 줄어든다. sklearn 1.3부터 sklearn.cluster.HDBSCAN으로 들어와 있어 별도 설치도 필요 없다.

from sklearn.cluster import HDBSCAN

labels = HDBSCAN(min_cluster_size=15).fit_predict(X)

밀도 기반 클러스터링을 실무에 쓸 생각이라면 DBSCAN보다 HDBSCAN을 먼저 시도해 보는 편이 낫다. 차원이 높아지면 둘 다 약해지는데, 거리 자체가 변별력을 잃기 때문이라 알고리즘을 바꾸는 것으로는 해결되지 않는다. 차원을 먼저 줄이고 들어가야 한다.

GMM, 소속을 확률로 매긴다

K-Means와 DBSCAN은 한 점을 정확히 한 클러스터에 넣는다. 하지만 경계가 흐릿한 데이터에서는 그 강제 할당이 정보를 지운다. 프리미엄 고객 성향이 6할, 일반 고객 성향이 4할인 고객을 어느 한쪽에 밀어 넣으면 “애매하다”는 사실 자체가 사라진다.

GMM(Gaussian Mixture Model)은 데이터가 여러 개의 가우시안 분포에서 섞여 나왔다고 본다. 전체 밀도는 각 컴포넌트 밀도의 가중합이다.

$p(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k), \qquad \sum_{k=1}^{K} \pi_k = 1$

컴포넌트 $k$는 세 가지를 가진다. 중심 $\mu_k$, 퍼짐과 방향을 담은 공분산 $\Sigma_k$, 전체에서 차지하는 비율 $\pi_k$다. K-Means의 클러스터가 중심점 하나만 가지는 것과 대비된다. 공분산이 있으니 축이 기울어진 길쭉한 덩어리도 표현할 수 있고, $\pi_k$가 있으니 크기가 다른 덩어리도 다룰 수 있다.

무엇을 표현할 수 있는지는 covariance_type이 정한다.

아래로 갈수록 추정할 파라미터가 줄어든다. full은 컴포넌트마다 $d(d+1)/2$개의 공분산 값을 추정해야 해서, 차원이 높거나 표본이 적으면 행렬이 특이해지기 쉽다. sklearn이 대각 성분에 reg_covar=1e-6을 더해 두는 것도 이 때문이다. 차원 대비 표본이 부족하면 diag부터 시작하는 쪽이 안전하다.

EM 알고리즘

파라미터를 모르면 각 점이 어느 컴포넌트에서 나왔는지 알 수 없고, 각 점의 출처를 모르면 파라미터를 추정할 수 없다. EM(Expectation-Maximization)은 이 순환을 한쪽씩 번갈아 푼다.

E단계에서는 현재 파라미터를 그대로 두고, 점 $x_i$가 컴포넌트 $k$에서 나왔을 사후 확률을 계산한다. 이 값을 responsibility라고 부른다.

$r_{ik} = \frac{\pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}$

M단계에서는 이 responsibility를 가중치로 삼아 파라미터를 다시 맞춘다. $N_k = \sum_i r_{ik}$를 컴포넌트 $k$가 끌어모은 유효 표본 수라고 보면,

$\mu_k = \frac{1}{N_k}\sum_i r_{ik}\, x_i, \qquad \pi_k = \frac{N_k}{n}$

이고 공분산도 같은 가중치로 계산한다. 두 단계 모두 로그 가능도를 낮추지 않기 때문에 값은 단조 증가하고, K-Means와 마찬가지로 지역 최적에서 멈춘다.

구조가 K-Means와 겹치는 것은 우연이 아니다. K-Means의 할당 단계가 E단계에 대응하고 평균 갱신이 M단계에 대응하는데, 차이는 responsibility가 0과 1 중 하나로 굳어져 있다는 점뿐이다. 실제로 모든 공분산을 같은 $\sigma^2 I$로 묶고 $\sigma^2$를 0으로 보내면 responsibility가 가장 가까운 컴포넌트에 1로 쏠려 GMM은 K-Means가 된다. sklearn의 GaussianMixture가 기본적으로 K-Means 결과로 초기화(init_params='kmeans')하는 것도 이 관계 때문이다.

확률을 받아서 무엇을 하나

from sklearn.mixture import GaussianMixture

gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42).fit(X)

probs = gmm.predict_proba(X)              # (n, 3) 소속 확률
uncertain = probs.max(axis=1) < 0.7       # 어느 쪽도 확신하지 못한 점
print(uncertain.sum(), probs[uncertain][:3].round(3))

predict가 주는 레이블은 이 확률의 argmax일 뿐이다. 값을 통째로 받으면 “어디에도 확신이 없는 점”을 골라낼 수 있고, 이 목록은 그대로 검토 대상이 된다. 사람에게 레이블링을 맡길 샘플을 고르는 능동 학습(active learning)이 대표적인 용처다.

컴포넌트 수는 엘보우나 실루엣 대신 정보 기준으로 정한다. 로그 가능도 $\ln\hat{L}$에 파라미터 수 $p$에 대한 벌점을 붙인 값이다.

$\text{AIC} = -2\ln\hat{L} + 2p, \qquad \text{BIC} = -2\ln\hat{L} + p\ln n$

$n$이 8보다 크면 $\ln n > 2$이므로 BIC의 벌점이 더 무겁고, 그만큼 컴포넌트 수를 적게 고른다. 둘 중 하나를 기본으로 쓴다면 BIC 쪽이 무난하다. covariance_type을 바꾸면 $p$가 통째로 달라지니, 공분산 타입까지 같이 놓고 BIC를 비교하면 두 선택을 한 번에 정리할 수 있다.

scores = []
for k in range(1, 8):
    for ct in ('full', 'tied', 'diag', 'spherical'):
        gmm = GaussianMixture(n_components=k, covariance_type=ct, random_state=42).fit(X)
        scores.append((gmm.bic(X), k, ct))

print(min(scores))   # (BIC, 컴포넌트 수, 공분산 타입)

셋 중 무엇을 고를까

선택은 결국 데이터에 대한 가정을 고르는 일이다. 덩어리가 둥글고 크기가 비슷하다고 믿으면 K-Means, 밀도가 높은 곳이 곧 클러스터라고 믿으면 DBSCAN, 데이터가 몇 개의 가우시안에서 섞여 나왔다고 믿으면 GMM이다. 셋이 배타적인 것도 아니다. K-Means로 대략의 구조를 훑고, DBSCAN으로 잡음 후보를 걸러낸 뒤, GMM으로 경계의 불확실성을 재는 식으로 이어 붙일 수 있다.

마치며

DBSCAN과 GMM은 K-Means가 놓치는 것을 각각 다른 쪽에서 집어낸다. DBSCAN은 클러스터가 무슨 모양인지, 몇 개인지에 대한 가정을 아예 버리고 밀도만 본 덕에 초승달도 고리도 따라가고 잡음까지 골라낸다. 대신 밀도가 균일하다는 새 가정을 떠안았고, 그 가정이 깨지는 자리에서 HDBSCAN이 필요해진다.

GMM은 반대로 가정을 더 정교하게 만드는 쪽이다. 중심점 하나로 요약하던 클러스터를 평균과 공분산과 비율을 가진 분포로 바꾸고, 그 대가로 소속 확률을 얻는다. 확률이 있으면 “이 점은 어디에도 확신이 없다”는 판정이 가능해지는데, 하드 클러스터링에서는 애초에 표현할 수 없는 정보다.

정답이 없는 문제라서 어떤 알고리즘이 옳았는지 채점할 방법도 없다. 남는 것은 내가 세운 가정이 이 데이터에 맞았는지 확인하는 일뿐이고, 그래서 결과를 뜯어보는 시간이 알고리즘을 고르는 시간보다 길어진다.

함께 보면 좋은 글

• K-Means 클러스터링 : 중심점을 옮겨가며 수렴하는 절차와 K를 고르는 기준
• 이상 탐지 : DBSCAN이 잡음으로 떼어내는 점들을 정면으로 다루는 문제
• t-SNE와 UMAP : 클러스터링 결과를 2차원에 펼쳐 눈으로 확인하는 방법
• 나이브 베이즈 : 같은 가우시안 가정을 레이블이 있는 문제에 쓰는 경우

참고자료

• Ester et al., A Density-Based Algorithm for Discovering Clusters (KDD 1996)
• scikit-learn, Clustering
• scikit-learn, Gaussian Mixture Models
• Bishop, Pattern Recognition and Machine Learning, Ch. 9