계층적 군집과 DBSCAN — K-Means를 넘어서는 클러스터링 [10편]

계층적 군집과 DBSCAN

 

덴드로그램으로 보는 계층적 군집과 밀도 기반 DBSCAN을 비교합니다

목표: K-Means의 한계를 극복하는 계층적 군집과 DBSCAN 알고리즘을 학습하고, 각 알고리즘의 장단점을 비교합니다.

1. 계층적 군집(Hierarchical Clustering)이란?

계층적 군집은 데이터를 계층적인 트리 구조로 만드는 알고리즘입니다. K-Means와는 달리, 미리 클러스터 개수를 정할 필요가 없습니다.

두 가지 방식:

• 응집형(Agglomerative): 각 점에서 시작하여 점진적으로 병합. 상향식(Bottom-up) 접근
• 분열형(Divisive): 모든 점을 하나의 클러스터에서 시작하여 분할. 하향식(Top-down) 접근

우리는 주로 응집형 계층적 군집을 사용합니다. 이를 시각화한 그래프를 덴드로그램(Dendrogram)이라 합니다.

2. 거리 행렬 계산

계층적 군집의 첫 단계는 데이터 점들 사이의 거리를 모두 계산하는 것입니다. 이를 거리 행렬(Distance Matrix)이라 합니다.

import pandas as pd
from scipy.spatial.distance import pdist, squareform

# 거리 행렬 계산
row_dist = pd.DataFrame(squareform(pdist(df, metric='euclidean')),
                        columns=labels, index=labels)
print(row_dist)

팁: pdist()는 1차원 거리 배열을 반환하고, squareform()으로 2차원 행렬로 변환합니다.

3. 병합 군집과 덴드로그램

덴드로그램은 계층적 군집 과정을 시각화하는 트리 구조 그래프입니다. 가로축은 데이터 점, 세로축은 거리입니다.

덴드로그램 읽는 법:

• 아래에서 위로 올라갈수록 점들이 병합됨
• 높은 위치의 선을 자르면 적은 수의 클러스터 생성
• 낮은 위치의 선을 자르면 많은 수의 클러스터 생성

반응형

from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# 병합 군집 수행
row_clusters = linkage(df.values, method='complete', metric='euclidean')

# 덴드로그램 시각화
dendrogram(row_clusters, labels=labels)
plt.xlabel('Data Points')
plt.ylabel('Distance')
plt.title('Hierarchical Clustering Dendrogram')
plt.show()

주목: method 파라미터는 클러스터 간의 거리를 계산하는 방법입니다.

• complete: 두 클러스터의 최댓값 거리
• single: 두 클러스터의 최솟값 거리
• average: 두 클러스터의 평균 거리

4. scikit-learn AgglomerativeClustering

scikit-learn의 AgglomerativeClustering을 사용하여 더 간편하게 계층적 군집을 수행할 수 있습니다.

from sklearn.cluster import AgglomerativeClustering

# 계층적 군집 수행
ac = AgglomerativeClustering(n_clusters=2, metric='euclidean',
                              linkage='complete')
labels = ac.fit_predict(X)

print(f'클러스터 레이블: {labels}')
print(f'클러스터 개수: {len(set(labels))}')

5. DBSCAN (밀도 기반 클러스터링)

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 밀도를 기반으로 클러스터를 찾는 알고리즘입니다. 임의의 형태의 클러스터를 찾을 수 있으며, 노이즈를 자동으로 식별합니다.

DBSCAN의 핵심 개념:

• 핵심점(Core Point): 반경 eps 내에 min_samples 이상의 점을 가진 점
• 경계점(Border Point): 핵심점의 이웃이지만 자신은 핵심점이 아닌 점
• 노이즈(Noise): 어떤 핵심점의 이웃도 아닌 점

from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN

# 반달 모양 데이터 생성
X, y = make_moons(n_samples=200, noise=0.05, random_state=0)

# DBSCAN 클러스터링
db = DBSCAN(eps=0.2, min_samples=5, metric='euclidean')
y_db = db.fit_predict(X)

# 결과 확인
n_clusters = len(set(y_db)) - (1 if -1 in y_db else 0)
n_noise = list(y_db).count(-1)

print(f'클러스터 개수: {n_clusters}')
print(f'노이즈 점 개수: {n_noise}')

팁: DBSCAN에서 노이즈 점은 레이블 -1로 표시됩니다. eps(반경)와 min_samples는 데이터에 따라 조정해야 하는 중요한 파라미터입니다.

6. K-Means vs 계층적 군집 vs DBSCAN 비교

반달 모양 데이터(make_moons)는 K-Means와 계층적 군집이 실패하지만, DBSCAN은 완벽하게 성공합니다.

주목: 각 알고리즘의 특성을 정리하면 다음과 같습니다.

K-Means

• 장점: 빠르고 간단하며, 대규모 데이터에 적합
• 단점: 구형 클러스터만 잘 찾음, 임의의 형태 실패

계층적 군집

• 장점: 덴드로그램으로 시각화 가능, 계층 구조 파악
• 단점: 임의의 형태 클러스터에 약함, 계산 비용 높음

DBSCAN

• 장점: 임의의 형태 클러스터 감지, 노이즈 자동 식별
• 단점: eps와 min_samples 파라미터 튜닝 필요, 밀도 차이에 민감

# 세 알고리즘을 반달 데이터에 적용
from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN

X, _ = make_moons(n_samples=200, noise=0.05, random_state=0)

# K-Means
km = KMeans(n_clusters=2, init='k-means++', random_state=0)
y_km = km.fit_predict(X)
print('K-Means: 구형 클러스터만 감지 (실패)')

# 계층적 군집
ac = AgglomerativeClustering(n_clusters=2, linkage='complete')
y_ac = ac.fit_predict(X)
print('계층적 군집: 임의의 형태 감지 실패')

# DBSCAN
db = DBSCAN(eps=0.2, min_samples=5)
y_db = db.fit_predict(X)
print('DBSCAN: 반달 형태 완벽하게 감지 (성공)')

알고리즘 선택 가이드

• K-Means 사용: 구형의 균일한 크기 클러스터, 대규모 데이터, 빠른 처리 필요
• 계층적 군집 사용: 계층 구조 파악 필요, 클러스터 개수 미정, 중소규모 데이터
• DBSCAN 사용: 임의의 형태 클러스터, 노이즈 처리 필요, 밀도 기반 분석

핵심 정리

• 계층적 군집: 거리 행렬로부터 시작하여 점진적으로 클러스터를 병합합니다. 덴드로그램으로 시각화 가능합니다.
• 응집형 vs 분열형: 응집형은 상향식, 분열형은 하향식으로 진행됩니다.
• 거리 계산 방법: Complete, Single, Average 등의 링크 방법이 결과에 큰 영향을 미칩니다.
• DBSCAN: 밀도를 기반으로 임의의 형태 클러스터를 찾으며, 노이즈를 자동으로 식별합니다.
• DBSCAN 파라미터: eps(반경)와 min_samples는 신중하게 선택해야 합니다.
• 알고리즘 비교: 반달 모양처럼 복잡한 형태의 데이터에서는 DBSCAN이 가장 효과적입니다.

지금까지 K-Means, 계층적 군집, DBSCAN 세 가지 주요 클러스터링 알고리즘을 학습했습니다.

다음 편에서는 이를 실무 프로젝트에 어떻게 적용하는지 배웁니다.