#3-(6) 군집 알고리즘 : 병합 군집

※ 이 글의 내용은 O'REILLY의 <파이썬 라이브러리를 활용한 머신러닝> 책을 기반으로 한다.

군집 알고리즘 : 병합 군집

• 병합 군집

 - 병합 군집(Agglomerative Clustering) : 각각의 데이터 포인트를 하나의 클러스터로 지정하고, 지정된 개수의 클러스터가 남을 때까지 가장 비슷한 두 클러스터를 합쳐 나가는 알고리즘. 두 클러스터를 합쳐 나가는 방식에는 모든 클러스터 내의 분산을 가장 작게 증가시키는 두 클러스터를 합치는 방식(Ward), 클러스터 포인트 사이의 평균 거리가 가장 짧은 두 클러스터를 합치는 방식(Average), 클러스터 포인트 사이의 최대 거리가 가장 짧은 두 클러스터를 합치는 방식(Complete) 등이 있다. Ward 방식이 대부분의 데이터 세트에 알맞게 동작한다.

 - 초기에는 각 포인트가 하나의 클러스터이다. 그 다음 가장 가까운 두 클러스터가 합쳐지기 시작한다. 클러스터가 성장하면서 점점 더 멀리 있는 (다른 클러스터보다는 가까운) 데이터를 포함시키고, 지정해준 클러스터 개수가 되면 성장(병합)을 멈춘다. 이러한 병합 군집 알고리즘의 작동 특성상 새로운 데이터 포인트에 대해서는 예측을 할 수 없다.

 - 병합 군집은 계층적 군집(Hierarchical Clustering)을 만든다. 군집이 반복하여 진행되면 모든 포인트는 하나의 포인트를 가진 클러스터에서 시작하여 마지막 클러스터까지 이동하게 된다. 즉, 작은 클러스터들이 모여 큰 클러스터를 이루는 계층적 구조를 가지는 것이다.

• 계층적 군집

 - 계층적 군집(Hierarchical Clustering) : 계층적 군집이란 계층적 트리 모형을 이용하여 개별 데이터 포인트들을 순차적, 계층적으로 유사한 클러스터로 통합하여 군집화를 수행하는 알고리즘이다. k-평균 군집 알고리즘과는 달리 클러스터의 개수를 사전에 정하지 않아도 학습을 수행할 수 있다. 계층적 군집에는 개개의 포인트를 순차적으로 병합하는 상향식의 병합 군집 방식(Agglomerative Clustering), 전체를 하나의 클러스터로 하여 그것을 분할해 나가는 하향식의 분할 군집 방식(Divisive Clustering)이 있다.

 - 덴드로그램(Dendrogram) : 덴드로그램은 계층 군집을 시각화하는 도구로서, 다차원 데이터 세트를 처리할 수 있다. 계층적 군집에서 클러스터의 개수를 지정해주지 않아도 학습을 수행할 수 있는 것은 개체들이 결합되는 순서를 나타내는 트리 형태의 구조인 덴드로그램 덕분이다. 덴드로그램에서 가지의 길이는 합쳐진 클러스터가 얼마나 멀리 떨어져 있는지를 보여준다.

 - 덴드로그램을 가로 선으로 분할하면 클러스터를 임의로 나눌 수 있다. 즉 군집화를 하기 전에 클러스터의 개수를 정해주어야 하는 k-평균 군집 알고리즘과는 달리, 병합 군집같은 계층척 군집 알고리즘은 계층적으로 군집화를 완료한 후에 사용자가 시각화된 덴드로그램을 보고 클러스터를 나눌 수 있는 것이다. 그러나 k-평균 군집과 마찬가지로, 계층적 군집에서도 데이터 간의 거리를 기반으로 하기 때문에 복잡한 형상의 데이터 세트는 구분하지 못한다.