계보적 방법(Hierarchical Clustering)

앞에서 군집화 기법에 대해 정리를 할때 언급했었던 계보적 방법이다.

개념적인 부분은 앞의 부분과도 겹치지만 다시한번 살펴보자.

확실히 영어가 더 인식하기에 편하다.

 

Hierarchical Clustering

 

계보적 군집화는 병합적 방법과 분할적 방법으로 나뉜다.

ㆍ병합적 계보적 군집화(Agglomerative) : 상향식 방법, 각 객체를 자신의 군집에 배치하고, 그 원자 군집들을 더 큰 군집으로 만들어 간다. 모든 객체가 하나의 군집이 되거나, 종료조건을 만족하면 종료, 대부분의 군집화 방법(유사성에 대한 정의만 다름)

ㆍ분할적 계보적 군집화(Divisive) : 병합적 방법과 반대, 하향식, 모든 객체를 하나의 군집으로 여기면서 시작, 각 객체가 하나의 군집을 형성하게 될때까지, 혹은 적절한 개수의 군집이 얻어지거나, 가까운 군집간의 거리가 어떤 한계거리를 넘어서는 등의 종료조건을 만족할때까지 군집을 세분화함.

 

예를 들어보자.

 

위의 그림을 보면 5개의 객체 a, b, c, d, e에 대해 병합적 방법과 분할적 방법을 표현한 것이다.

그림이 직관적이라 이해하기는 쉬울 듯하다.

먼저 병합적(AGNES)방법부터 상세하게 살펴보자.

순서는 다음과 같다.

각 객체를 가각의 군집으로 배치한다. 군집들은 어떤 기준에 따라서 단계적으로 병합이 되는데, 이때의 기준을 예로 들면 유클리드 거리를 들어 가장 가깝게 위치한 군집끼리 병합하는 것이 기준이라고 할 수 있다.

객체 모두가 결과적으로 하나의 군집을 형성하여 합쳐질때까지 반복을 수행한다.

 

다음은 분할적(DIANA) 방법이다.

객체 모두를 하나의 초기 군집으로 형성하기 위해 사용한다.

군집은 군집의 가장 가까이 이웃해 있는 객체들 간의 최대 유클리드 거리와 같은 기준을 사용하여 분할한다.

즉, 유클리드가 거리가 크다(위치상으로 멀리있다)는 것을 기준으로해서 먼저 분할을 수행하는 것이다.

 

--------

병학적, 분할적 계보적 군집화는 종료조건으로 적절한(필요한 만큼의)군집 수를 정할수 있다. 

 

계보적 기법에 대한 문서를 읽다보면 위의 그림과 같은 그림을 자주 볼수 있다. 이러한 트리구조를 가지는 덴드로그램(Dendrogram)을 통해서 계보적 군집화를 쉽게 표현한다.

 

앞에서 언급했던 군집간의 거리를 측정하는데 기준이 되는 측도는 다음과 같이 4가지가 있다.

 

앞에 단어들을 통해 대충은 유추를 할 수 있을 것이다.

세부적인 설명을 하자면 |p-p'|는 두 객체간의 거리이고, mi는 군집 Ci의 평균, ni는 Ci에 있는 객체의 수이다.

 

이 측도중에 최소거리(Minimum distance)를 사용하게 되면, 최단 인접 군집화 알고리즘이라고 한다.

또는 최소신장트리 알고리즘(Minimal Spanning Tree Algorithm) 이라고도 한다.