계층적 클러스터링과 DBSCAN
다양한 모양의 군집을 발견하다
K-Means가 실패하는 순간
앞 장에서 배운 K-Means는 강력하지만, 치명적인 가정이 하나 있습니다. 군집이 둥근 모양(구형)이라는 것입니다. 현실의 데이터는 초승달 모양, 고리 모양, 불규칙한 밀집 지역 등 다양한 형태를 가집니다.
고객이 두 개의 초승달처럼 얽혀 있다면? 매장이 도심과 외곽에 불균일하게 흩어져 있다면? K-Means는 이런 패턴을 제대로 잡아내지 못합니다. 이 장에서는 형태에 구애받지 않는 두 가지 클러스터링 기법을 배웁니다.
계층적 클러스터링은 데이터를 단계별로 합치거나 나누면서 트리 구조(덴드로그램)를 만들고, DBSCAN은 밀도가 높은 지역을 자동으로 찾아 군집의 수조차 미리 정하지 않아도 됩니다.
계층적 클러스터링: 아래에서 위로 합치기
계층적 클러스터링(Hierarchical Clustering)의 핵심 아이디어는 단순합니다. 처음에는 모든 점이 각자 하나의 군집입니다. 가장 가까운 두 군집을 찾아서 합치고, 이 과정을 반복합니다. 결국 모든 점이 하나의 군집이 될 때까지 계속합니다. 이것을 병합(agglomerative) 방식이라 합니다.
1. N개의 점 각각을 독립 군집으로 시작한다.
2. 모든 군집 쌍 사이의 거리를 계산한다.
3. 가장 가까운 두 군집을 하나로 합친다.
4. 군집이 1개가 될 때까지 2-3을 반복한다.
쉽게 말하면, 가장 친한 친구끼리 먼저 팀을 만들고, 팀끼리 다시 합치는 과정입니다.
연결 방법(Linkage): 두 군집 사이의 거리를 어떻게 잴 것인가?
단일 점이 아니라 군집 사이의 거리를 재야 하므로, 어떤 기준을 쓰느냐에 따라 결과가 달라집니다.
단일 연결 (Single)
두 군집에서 가장 가까운 점 쌍의 거리. 체인 효과(길게 늘어지는 군집)가 발생할 수 있습니다.
완전 연결 (Complete)
두 군집에서 가장 먼 점 쌍의 거리. 비교적 동글한 군집을 만드는 경향이 있습니다.
평균 연결 (Average)
두 군집에 속한 모든 점 쌍 거리의 평균. 단일과 완전의 절충안입니다.
완전 연결: d(A, B) = max d(a, b) (가장 먼 쌍)
평균 연결: d(A, B) = (1 / |A|*|B|) * Σ d(a, b)
실습 1: 병합 클러스터링 단계별 시각화
아래 캔버스에 30개의 점이 무작위로 생성됩니다. "한 단계 합치기" 버튼을 누를 때마다 가장 가까운 두 군집이 합쳐지는 과정을 직접 관찰하세요. 연결 방법을 바꿔보면 같은 데이터에서도 합쳐지는 순서가 달라지는 것을 확인할 수 있습니다.
덴드로그램 읽기: 높이와 절단선
계층적 클러스터링의 전체 과정은 덴드로그램(dendrogram)이라는 트리 그림으로 요약됩니다. 세로축은 합병 시점의 거리(높이)를 나타내고, 아래쪽에서 위로 올라갈수록 더 먼 군집들이 합쳐집니다.
실습 2: 절단 높이를 움직여 군집 수 조절하기
아래 슬라이더를 움직여 절단 높이를 바꿔보세요. 왼쪽 덴드로그램의 절단선과 오른쪽 산점도의 색이 동시에 바뀝니다.
DBSCAN: 밀도 기반 클러스터링
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 1996년 Ester 등이 제안한 알고리즘으로, 밀도가 높은 영역을 군집으로 정의합니다. K-Means처럼 군집 수를 미리 정할 필요가 없고, 임의의 형태의 군집을 찾을 수 있으며, 어디에도 속하지 않는 노이즈(이상치)를 자동으로 식별합니다.
핵심 개념: 세 종류의 점
핵심점 (Core Point)
반경 epsilon 안에 minPts개 이상의 이웃이 있는 점. 군집의 내부를 구성합니다.
경계점 (Border Point)
핵심점의 이웃이지만, 자신은 핵심점이 아닌 점. 군집의 가장자리입니다.
노이즈 (Noise)
핵심점도 아니고 어떤 핵심점의 이웃도 아닌 점. 어떤 군집에도 속하지 않습니다.
minPts: 핵심점이 되기 위한 최소 이웃 수 (자기 자신 포함)
N_eps(p) = { q in D | dist(p, q) <= eps } |N_eps(p)| >= minPts 이면 p는 핵심점
epsilon은 "동네의 반경"입니다. "이 집에서 반경 500m 안에 있는 집이 이웃"이라고 정의하는 것과 같습니다. epsilon이 크면 넓은 범위를 하나의 동네로 보고, 작으면 좁은 범위만 동네로 봅니다.
minPts는 "동네로 인정받으려면 최소 몇 가구가 있어야 하는가"입니다. minPts가 5이면 반경 안에 5가구 이상 있어야 그곳이 "동네의 중심(핵심점)"으로 인정됩니다. 이 두 값을 적절히 설정하는 것이 DBSCAN 성공의 열쇠입니다.
1. 임의의 미방문 점 p를 선택한다.
2. p의 epsilon-이웃을 구한다. minPts 이상이면 p는 핵심점 -- 새 군집 시작.
3. p의 이웃들을 모두 같은 군집에 넣고, 이웃 중 핵심점이면 그 이웃의 이웃도 확장.
4. minPts 미만이면 일단 노이즈로 표시 (나중에 다른 핵심점의 이웃이면 경계점으로 변경).
5. 모든 점을 방문할 때까지 반복.
쉽게 말하면, 사람이 붐비는 곳(핵심점)을 찾아서 연결된 붐비는 곳끼리 하나의 군집으로 묶는 것입니다.
실습 3: DBSCAN 파라미터 탐색기
다양한 형태의 데이터셋에서 epsilon과 minPts를 조절해보세요. 핵심점 주위에 epsilon 반경 원이 표시되며, 군집 결과가 실시간으로 바뀝니다. 노이즈 점은 회색 X로 표시됩니다.
실습 4: K-Means vs DBSCAN 비교
같은 데이터에 K-Means와 DBSCAN을 적용한 결과를 나란히 비교합니다. 비구형 데이터에서 두 알고리즘의 차이가 극적으로 드러납니다.
실습 5: 서울 매장 위치 군집 분석
프랜차이즈 본사가 서울 시내 50개 매장의 위치 데이터를 분석합니다. DBSCAN으로 자연스러운 매장 군집을 찾고, 고립 매장(노이즈)을 식별하여 물류 배송 권역 설정과 고립 매장 지원 전략을 수립할 수 있습니다.
세 가지 클러스터링 기법 비교
| 기준 | K-Means | 계층적 | DBSCAN |
|---|---|---|---|
| 군집 수 | 사전 지정 필요 | 나중에 절단선으로 결정 | 자동 결정 |
| 군집 형태 | 구형만 | 연결 방법에 따라 다양 | 임의 형태 |
| 노이즈 처리 | 불가 (모든 점 할당) | 불가 (모든 점 할당) | 자동 식별 |
| 주요 파라미터 | K (군집 수) | 연결 방법, 절단 높이 | epsilon, minPts |
| 시간 복잡도 | O(nKt) | O(n^2 log n) ~ O(n^3) | O(n log n) ~ O(n^2) |
| 대규모 데이터 | 적합 | 부적합 (메모리 문제) | 적합 (공간 인덱스 사용 시) |
| 적합한 상황 | 사전 지식이 있고 구형 군집 | 군집 계층 구조가 필요할 때 | 형태 불명, 이상치 존재 |
이 장의 핵심 정리
- 계층적 클러스터링은 데이터를 단계별로 합치며 덴드로그램을 생성하고, 절단 높이로 군집 수를 결정한다.
- 연결 방법(단일/완전/평균)에 따라 군집의 모양과 크기가 크게 달라진다.
- DBSCAN은 밀도가 높은 영역을 자동으로 군집으로 인식하며, 군집 수를 사전에 지정하지 않아도 된다.
- DBSCAN은 핵심점, 경계점, 노이즈의 세 가지 유형으로 점을 분류한다.
- K-Means는 구형 군집에 강하고, DBSCAN은 비구형 군집과 이상치 탐지에 강하다. 만능 알고리즘은 없다.
다음 장 예고: 군집 분석의 결과를 어떻게 평가할 것인가? 실루엣 분석, 군집 타당성 지표 등 군집의 품질을 측정하는 방법을 다룹니다.