K-Means는 데이터를 살펴보기도 전에 한 가지 짜증 나는 질문을 던집니다. 바로 '클러스터 (cluster)가 몇 개인가?'입니다. k=3을 선택하면, 그것이 진실인지 여부와 상관없이 세상을 기쁘게 세 개로 나누어 버립니다. 계층적 군집화 (Hierarchical clustering)는 이를 뒤집습니다. 숫자를 미리 결정하는 대신, 군집화의 '전체' 계보를 한 번에 구축하고, 나중에 그림을 읽음으로써 선택할 수 있게 해줍니다.

저는 여기서 처음부터 직접 구현하여 브라우저에서 실행되는 버전을 만들었습니다:

🌳 https://dev48v.infy.uk/ml/day25-hierarchical-clustering.html

아이디어: 가장 가까운 두 개를 계속 병합하기

일반적인 방식은 응집형 (agglomerative, bottom-up) 방식이며, 루프는 당황스러울 정도로 단순합니다:

1. 모든 점을 각각 하나의 클러스터로 시작합니다. 24개의 점이 있다면, 24개의 클러스터가 됩니다.
2. 가장 가까운 두 클러스터를 찾아 하나로 합칩니다. 이들이 결합된 거리를 기록합니다.
3. 단 하나의 클러스터가 남을 때까지 반복합니다.

이것은 n-1번의 병합이며, "누가, 어떤 높이에서 병합되었는가"에 대한 목록이 모델의 전부입니다. 하나의 큰 클러스터에서 시작하여 재귀적으로 분할하는 top-down 방식의 사촌 격인 분할형 (divisive) 방식도 있지만, 비용이 훨씬 많이 들기 때문에 거의 아무도 사용하지 않습니다.

연결 (Linkage): "가장 가까운 클러스터"란 대체 무엇을 의미하는가?

두 '점' 사이의 거리는 명확합니다. 하지만 두 '클러스터' 사이의 거리는 선택의 문제이며, 이는 모든 것을 바꿉니다:

• 단일 연결 (single) — 가장 가까운 두 구성원 사이의 거리입니다. 길고 구불구불하며 비볼록 (non-convex) 형태인 모양에 좋지만, "체이닝 (chaining)" 현상을 겪습니다. 즉, 길을 잃은 점들의 다리 하나가 두 개의 분리된 덩어리를 하나의 지저분한 덩어리로 붙여버릴 수 있습니다.
• 완전 연결 (complete) — 가장 '먼' 두 구성원 사이의 거리입니다. 조밀하고 콤팩트하며 크기가 균일한 클러스터를 생성하며 체이닝에 저항합니다.
• 평균 연결 (average) — 클러스터 간의 모든 쌍에 대한 평균입니다. 합리적인 절충안이며, 생물학에서 인기가 있습니다 (UPGMA).
• Ward (Ward's method) — 클러스터 내 총 분산 (variance)을 가장 적게 증가시키는 쌍을 병합합니다. 대략적으로 둥근 덩어리들에 대해 보통 가장 깔끔한 결과를 보여주며, 제가 가장 먼저 선택할 기본값입니다.

동일한 데이터, 서로 다른 연결 방식 (linkage), 그리고 진정으로 다른 트리 (tree)들입니다. 데모를 통해 네 가지 방식을 모두 전환하며 덴드로그램 (dendrogram)이 재배열되는 모습을 관찰할 수 있습니다.

덴드로그램 (dendrogram): 실제로 읽을 수 있는 트리

모든 병합은 하나의 가로 막대가 되며, 이 막대의 **높이는 두 그룹이 결합된 거리 (distance)**를 의미합니다. 낮은 막대는 "이들이 매우 유사했다"는 것을 의미합니다. 높은 막대는 "서로 다른 두 그룹을 억지로 합쳤다"는 것을 의미합니다. 따라서 트리에서 수직 간격이 큰 지점이 바로 자연스러운 군집 경계 (cluster boundaries)가 존재하는 곳입니다.

트리 자르기 (Cutting the tree)

여기에 핵심이 있습니다. 덴드로그램은 비밀리에 가능한 모든 군집 (cluster)의 수를 포함하고 있습니다. 가로로 **절단선 (cut line)**을 그려서 군집 수를 선택합니다. 절단선 아래의 모든 것은 하나의 평면적인 군집으로 합쳐지고, 위쪽의 모든 것은 분리된 상태로 남습니다. 낮게 자르면 수많은 작은 군집들이 생기고, 높게 자르면 몇 개의 큰 군집으로 병합됩니다.

데모에서는 산점도 (scatter plot)와 덴드로그램이 연결되어 있습니다. 절단선을 드래그하면 해당 높이의 평면 군집에 맞춰 점들의 색상이 즉시 변경됩니다. 절단선을 가장 큰 간격까지 내리면 세 개의 덩어리가 깔끔하게 나타납니다. 이것이 바로 비결입니다. $k$를 정하기 전에 구조를 먼저 확인하고, 그 후에 $k$를 선택하는 것입니다.

어디에서 잘라야 할까요? 세 가지 정직한 답변이 있습니다: 가장 높은 수직 간격(연속된 병합 높이 사이의 가장 큰 도약)에서 자르기, 이미 알고 있는 목표 군집 수가 있다면 그 수에 맞춰 자르기, 또는 몇 가지 후보 절단선을 실루엣 계수 (silhouette coefficient)로 점수화하여 가장 좋은 것을 유지하기입니다.

K-Means와 비교했을 때의 장점은?

• 사전에 $k$를 정할 필요가 없습니다. 전체적인 계층 구조를 파악한 후 나중에 결정하면 됩니다.
• 결정론적 (Deterministic)입니다. 무작위 재시작 (random restarts)이 없으며, 매 실행마다 동일한 결과가 나옵니다.
• 단일 연결 (single linkage) 방식을 사용하면 K-Means가 절대 분리할 수 없는 형태(사슬, 고리 모양 등)를 추적할 수 있습니다.

단점은 비용입니다. 거리 행렬 (distance matrix)을 위해 $O(n^2)$의 메모리가 필요하며, 단순한 병합 루프의 경우 최대 $O(n^3)$의 시간이 소요됩니다. 이는 수백 개에서 수천 개의 데이터 포인트에는 괜찮지만, 수백만 개에는 비실용적입니다. 데이터가 너무 많다면 K-Means, DBSCAN, 또는 BIRCH를 사용하거나, 샘플에 대해서만 계층적 군집화를 수행하십시오.

실제 코드에서

실제 운영 환경에서는 이를 직접 구현(hand-roll)하지 않습니다. SciPy가 이 모든 과정을 수행합니다:

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster

Z = linkage(X, method="ward")          # 전체 병합 트리 (full merge tree)
...

해당 페이지는 세 개의 탭을 통해 이를 설명합니다: LOOK (실시간 산점도 + 슬라이더로 절단하는 덴드로그램 (dendrogram)), UNDERSTAND (병합 루프에서 네 가지 연결 방식 (linkages) 및 복잡도에 이르는 10단계 과정), 그리고 BUILD (그 이면에 있는 약 70줄의 순수 JS 코드와 SciPy 버전).

연결 방식 (linkage) 선택기와 절단선 (cut line)을 가지고 직접 테스트해 보세요. 동일한 데이터 포인트에 대해 Single 방식과 Ward 방식을 비교해 보는 것이 연결 방식 (linkage)이 왜 중요한지 체감할 수 있는 가장 빠른 방법입니다:

🌳 https://dev48v.infy.uk/ml/day25-hierarchical-clustering.html

MachineLearningFromZero의 일부입니다. 🌐 https://dev48v.infy.uk