DBSCAN과 GMM: 밀도·확률 기반 클러스터링 비교

[Core Point]     eps 반경 안에 min_samples 이상의 이웃이 있는 점
                 → 밀도가 높은 영역의 중심. 클러스터의 핵심이다

[Border Point]   스스로는 core point가 아니지만,
                 어떤 core point의 eps 반경 안에 포함된 점
                 → 클러스터 가장자리에 속한다

[Noise Point]    어떤 core point의 eps 반경에도 포함되지 않는 점
                 → 어디에도 속하지 않는 이상치. -1로 레이블된다

eps=1.0, min_samples=4

        ●   ●
     ●  ★  ●        ○         ·
        ●
                   ○   ○

★ = Core point (반경 안에 점이 5개 → ≥ 4)
● = Border point (core point의 이웃이지만, 자신의 이웃은 4개 미만)
○ = Border point (근처 core point가 있다면)
·  = Noise point (어떤 core point의 반경에도 포함 안 됨)

# 의사코드
for each point p in dataset:
    neighbors(p) = {q in dataset | distance(p, q) <= eps}
    if len(neighbors(p)) >= min_samples:
        mark p as CORE

1. 미방문 core point p를 고른다 → 새 클러스터 C 시작
2. p의 eps-이웃을 모두 C에 넣는다
3. 이웃 중 core point가 있으면, 그 점의 이웃도 C에 추가 (재귀적 확장)
4. 더 이상 확장할 core point가 없으면 C 완성
5. 아직 미방문 core point가 남아 있으면 1로 돌아간다

시간 복잡도:
- 일반: O(n²) — 모든 점 쌍의 거리를 계산
- KD-tree/Ball-tree 사용 시: O(n log n) — sklearn은 자동으로 적절한 자료구조 선택

from sklearn.neighbors import NearestNeighbors
import numpy as np
import matplotlib.pyplot as plt

# k = min_samples로 설정 (보통 min_samples = 2 * n_features)
k = 4
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X)
distances, _ = nn.kneighbors(X)

# k번째 이웃까지의 거리를 오름차순 정렬
k_distances = np.sort(distances[:, -1])

plt.figure(figsize=(8, 4))
plt.plot(k_distances)
plt.xlabel('Points (sorted)')
plt.ylabel(f'{k}-distance')
plt.title('k-distance Graph')
plt.axhline(y=0.3, color='r', linestyle='--', label='eps 후보')
plt.legend()
plt.show()

클러스터 A (고밀도)          클러스터 B (저밀도)

  ● ● ● ● ●                ○       ○
  ● ● ● ● ●
  ● ● ● ● ●                    ○
  ● ● ● ● ●                ○       ○
  ● ● ● ● ●

import hdbscan

clusterer = hdbscan.HDBSCAN(min_cluster_size=15, min_samples=5)
labels = clusterer.fit_predict(X)

# 각 클러스터 할당에 대한 확신도(probability)도 제공
probabilities = clusterer.probabilities_

K-Means (하드 할당)          GMM (소프트 할당)
──────────────────           ──────────────────
점 A → 클러스터 1              점 A → 클러스터 1: 0.92, 클러스터 2: 0.08
점 B → 클러스터 2              점 B → 클러스터 1: 0.15, 클러스터 2: 0.85
점 C → 클러스터 1              점 C → 클러스터 1: 0.51, 클러스터 2: 0.49  ← 경계 위의 점

K-Means 클러스터:             GMM 컴포넌트:
원형만 가능                    타원형도 가능

    ● ● ●                      ●  ●
   ● ● ● ●                   ●  ●  ●  ●
  ● ● ★ ● ●                ●  ●  ★  ●  ●
   ● ● ● ●                   ●  ●  ●
    ● ● ●                       ●  ●

  (★ = 중심)                 (★ = 평균, 타원 = 공분산)

r(i, k) = pi_k * N(x_i | mu_k, Sigma_k) / sum_j(pi_j * N(x_i | mu_j, Sigma_j))

# N_k = 컴포넌트 k에 할당된 데이터의 가중합
N_k = sum_i(r(i, k))

# 새 평균: responsibility로 가중 평균
mu_k = sum_i(r(i, k) * x_i) / N_k

# 새 공분산: responsibility로 가중된 편차 행렬
Sigma_k = sum_i(r(i, k) * (x_i - mu_k)(x_i - mu_k)^T) / N_k

# 새 혼합 가중치
pi_k = N_k / n

K-Means                         GMM (EM)
───────                         ────────
Assignment: 가장 가까운 중심    E-step: 각 컴포넌트 확률 계산
→ 0 또는 1 (하드)               → 0~1 사이의 실수 (소프트)

Update: 할당된 점의 평균        M-step: 가중 평균·공분산 업데이트
→ 중심만 이동                   → 평균 + 공분산 + 가중치 모두 업데이트

AIC = -2 * log_likelihood + 2 * k
BIC = -2 * log_likelihood + k * log(n)

여기서 k = 모델의 파라미터 수, n = 데이터 수

from sklearn.mixture import GaussianMixture
import numpy as np

bics = []
aics = []
K_range = range(1, 10)

for k in K_range:
    gmm = GaussianMixture(n_components=k, random_state=42)
    gmm.fit(X)
    bics.append(gmm.bic(X))
    aics.append(gmm.aic(X))

best_k = K_range[np.argmin(bics)]
print(f"BIC 기준 최적 컴포넌트 수: {best_k}")

from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN, KMeans
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
import numpy as np

# 반달 데이터 생성
X, y_true = make_moons(n_samples=300, noise=0.08, random_state=42)
X = StandardScaler().fit_transform(X)

# K-Means
kmeans = KMeans(n_clusters=2, random_state=42, n_init=10)
km_labels = kmeans.fit_predict(X)

# DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=5)
db_labels = dbscan.fit_predict(X)

# 시각화
fig, axes = plt.subplots(1, 3, figsize=(15, 4))

axes[0].scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', s=15)
axes[0].set_title('Ground Truth')

axes[1].scatter(X[:, 0], X[:, 1], c=km_labels, cmap='viridis', s=15)
axes[1].set_title('K-Means (K=2)')

mask = db_labels != -1
axes[2].scatter(X[mask, 0], X[mask, 1], c=db_labels[mask], cmap='viridis', s=15)
axes[2].scatter(X[~mask, 0], X[~mask, 1], c='gray', s=10, alpha=0.5, label='Noise')
axes[2].set_title(f'DBSCAN (clusters: {len(set(db_labels) - {-1})})')

plt.tight_layout()
plt.show()

K-Means 결과:                 DBSCAN 결과:
수직 분할 (틀림)               반달 분리 (정확)

  ▓▓▓▓ | ░░░░                 ▓▓▓▓▓▓▓▓
  ▓▓▓▓ | ░░░░                 ░░░░░░░░░░
      ▓▓ | ░░                     ░░░░░░
        ▓ | ░                 ▓▓▓▓▓▓▓▓
                              (▓, ░ = 서로 다른 클러스터)

from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(n_neighbors=5)
nn.fit(X)
distances, _ = nn.kneighbors(X)
k_distances = np.sort(distances[:, -1])

plt.figure(figsize=(8, 4))
plt.plot(k_distances)
plt.xlabel('Points (sorted by distance)')
plt.ylabel('5-distance')
plt.title('k-distance Graph for eps Selection')
plt.grid(True, alpha=0.3)
plt.show()

# 엘보 지점을 읽어서 eps에 반영

from sklearn.datasets import load_iris
from sklearn.mixture import GaussianMixture
from sklearn.decomposition import PCA
import numpy as np

# Iris 로드 + PCA로 2D 축소 (시각화용)
iris = load_iris()
X_iris = iris.data
y_iris = iris.target

pca = PCA(n_components=2)
X_2d = pca.fit_transform(X_iris)

# GMM 피팅
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42)
gmm.fit(X_2d)

# 하드 레이블 & 소프트 확률
labels = gmm.predict(X_2d)
probs = gmm.predict_proba(X_2d)

# 불확실한 점 찾기 (최대 확률이 0.7 미만)
uncertain = probs.max(axis=1) < 0.7
print(f"불확실한 점: {uncertain.sum()}개 / {len(X_2d)}개")
print(f"불확실한 점의 확률 분포 예시:")
print(probs[uncertain][:5].round(3))

import matplotlib.pyplot as plt

bics = []
K_range = range(1, 8)

for k in K_range:
    gmm = GaussianMixture(n_components=k, covariance_type='full', random_state=42)
    gmm.fit(X_2d)
    bics.append(gmm.bic(X_2d))

plt.figure(figsize=(8, 4))
plt.plot(K_range, bics, 'bo-')
plt.xlabel('Number of Components')
plt.ylabel('BIC')
plt.title('BIC Score by Number of Components')
plt.grid(True, alpha=0.3)
plt.show()

print(f"BIC 최소: k={K_range[np.argmin(bics)]}")