📂머신러닝

계층적 군집화

알고리즘

Input

$p$ 차원의 데이터 $N$개와 거리 $d$가 주어져있다고 하자.

---

Step 1.

각각의 점을 하나의 군집으로 생각한다. 가장 가까운 두 군집을 하나의 군집으로 묶는다.

---

Step 2.

다시 가장 가까운 두 군집을 하나의 군집으로 묶는다.

---

Step 3.

마지막으로 하나의 군집이 남을 때까지 반복한다.

---

Output

각 데이터들이 어떤 군집에 속하는지와 군집 사이의 거리를 반환한다.

---

• 이렇게 얻은 오른쪽의 트리 구조의 그림을 덴드로그램이라 한다.

설명¹

군집화 알고리즘에 속하는 비지도학습법이다. 트리 그림을 보면 알 수 있듯이 계층적으로 표현되는 군집을 만들어내는 것이 특징이다. 트리를 끊는 곳에 따라서 원하는 수의 군집을 얻을 수 있다.

$k$ 평균 균집화와의 가장 큰 차이점은, 군집의 수를 정해주지 않아도 군집화가 가능하다는 점이다. 따라서 결과가 항상 일정하다.

장단점

구분해야하는 군집의 수와 초기값에 의존하지 않으므로 항상 같은 결과를 내놓는다. 반면에 시간 복잡도가 $O(n^{3})$로 높은 편이다.²

사용되는 거리함수

군집간의 거리를 재는 방식에 따라 위와 같이 다른 군집 결과를 얻는다.

군집 내의 각 원소들이 다른 군집 내의 원소들에 비교해 상대적으로 서로 가까울 때, 군집이 컴팩트^compact하다고 한다. 각각의 군집들이 컴팩트하고, 다른 군집들로부터 잘 떨어져있으면 아래의 세 방법 모두 비슷한 결과를 낸다고 한다.

$G, H$를 주어진 두 군집, $i \in G$, $j \in H$라고 하자.

단일 연결^{SL, Single Linkage}

두 군집 사이의 모든 원소들 사이의 거리 중에서 가장 짧은 거리를 택한다. 최근접-이웃 기술^{nearest-neighbor technique} 이라고도 한다.

$$ d_{\text{SL}}(G, H) = \min\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$

완전 연결^{CL, Complete Linkage}

SL과는 반대로, 두 군집 사이의 모든 원소들 사이의 거리 중에서 가장 긴 거리를 택한다. 최원-이웃 기술^{furtherest-neighbor technique}이라고도 한다.

$$ d_{\text{CL}}(G, H) = \max\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$

그룹 평균^{GA, Group Average}

이름 그대로 모든 쌍의 거리의 평균을 군집 사이의 거리로 택한다. $N$을 각 군집에 포함된 원소의 수라고 할 때,

$$ d_{\text{GA}}(G, H) = \dfrac{1}{N_{G} N_{H}} \sum\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$