계층적 군집화(Hierarchical Clustering)
18 Apr 2017 | Clustering
이번 글에서는 계층적 군집화(Hierarchical Clustering)를 살펴보도록 하겠습니다. (줄여서 HC라 부르겠습니다) 이번 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
알고리즘 개요
HC란 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 개체 내지 그룹과 통합하여 군집화를 수행하는 알고리즘입니다. K-평균 군집화(K-means Clustering)와 달리 군집 수를 사전에 정하지 않아도 학습을 수행할 수 있습니다. 개체들이 결합되는 순서를 나타내는 트리형태의 구조인 덴드로그램(Dendrogram) 덕분입니다. 아래 그림과 같은 덴드로그램을 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됩니다.
학습 과정
HC를 수행하려면 모든 개체들 간 거리(distance)나 유사도(similarity)가 이미 계산되어 있어야 합니다. 거리측정 방법에 대해선 이곳을, (문서)유사도 측정법에 대해선 이곳을 참고하시면 좋을 것 같습니다. 주어진 학습데이터의 개체 수가 네 개이고 아래 그림처럼 거리 행렬을 이미 구해놨다고 가정해봅시다.
거리가 가까운 관측치들끼리 차례대로 군집으로 묶어보겠습니다. 거리가 가장 짧은 것이 2이고 이에 해당하는 개체는 A와 D이므로 먼저 A와 D를 하나의 군집으로 엮으면 좋겠네요. 표 왼쪽에 덴드로그램을 그릴 건데요, 덴드로그램의 높이는 관측치간 거리(2)가 되도록 합니다.
자 여기서 A와 D를 한 군집으로 엮었으니 거리행렬을 바꿔주어야 합니다. 다시 말해 개체-개체 거리를 군집-개체 거리로 계산해야 한다는 것이죠. 예컨대 ‘AD’와 ‘B’, ‘AD’와 ‘C’ 이렇게 거리를 구해야 한다는 말입니다. 그런데 군집-개체, 혹은 군집-군집 간 거리는 어떻게 계산해야 할까요? 여기엔 아래 그림처럼 여러가지 선택지가 존재합니다.
위 네 가지 방법 가운데 하나를 택했다고 가정하고 거리행렬을 업데이트했더니 AD와 C가 가장 인접해 있군요. 이번엔 이 둘을 이어줍시다.
그 다음 과정을 수행했더니 아래처럼 되었습니다.
분석 대상 관측치가 하나도 없으면 학습이 종료됩니다.
HC의 특징
이미 설명해 드린 것처럼 HC는 K-평균 군집화와 달리 사전에 군집수 $k$를 설정할 필요가 없습니다. 그도 그럴 것이 앞선 예에서 덴드로그램의 최상층을 끊어주면 $A, D, C$와 $B$로 두 개 군집이 도출됩니다. 위에서 두번째 층을 끊으면 $A, D$와 $C$, $B$ 이렇게 세 개 군집이 나옵니다. HC의 학습결과물인 덴드로그램을 적절한 수준에서 잘라주면 된다는 얘기입니다. 반면 HC의 계산복잡성은 $O(n^3)$로 K-평균 군집화보다는 무거운 편입니다.
이번 글에서는 계층적 군집화(Hierarchical Clustering)를 살펴보도록 하겠습니다. (줄여서 HC라 부르겠습니다) 이번 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
알고리즘 개요
HC란 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 개체 내지 그룹과 통합하여 군집화를 수행하는 알고리즘입니다. K-평균 군집화(K-means Clustering)와 달리 군집 수를 사전에 정하지 않아도 학습을 수행할 수 있습니다. 개체들이 결합되는 순서를 나타내는 트리형태의 구조인 덴드로그램(Dendrogram) 덕분입니다. 아래 그림과 같은 덴드로그램을 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됩니다.
학습 과정
HC를 수행하려면 모든 개체들 간 거리(distance)나 유사도(similarity)가 이미 계산되어 있어야 합니다. 거리측정 방법에 대해선 이곳을, (문서)유사도 측정법에 대해선 이곳을 참고하시면 좋을 것 같습니다. 주어진 학습데이터의 개체 수가 네 개이고 아래 그림처럼 거리 행렬을 이미 구해놨다고 가정해봅시다.
거리가 가까운 관측치들끼리 차례대로 군집으로 묶어보겠습니다. 거리가 가장 짧은 것이 2이고 이에 해당하는 개체는 A와 D이므로 먼저 A와 D를 하나의 군집으로 엮으면 좋겠네요. 표 왼쪽에 덴드로그램을 그릴 건데요, 덴드로그램의 높이는 관측치간 거리(2)가 되도록 합니다.
자 여기서 A와 D를 한 군집으로 엮었으니 거리행렬을 바꿔주어야 합니다. 다시 말해 개체-개체 거리를 군집-개체 거리로 계산해야 한다는 것이죠. 예컨대 ‘AD’와 ‘B’, ‘AD’와 ‘C’ 이렇게 거리를 구해야 한다는 말입니다. 그런데 군집-개체, 혹은 군집-군집 간 거리는 어떻게 계산해야 할까요? 여기엔 아래 그림처럼 여러가지 선택지가 존재합니다.
위 네 가지 방법 가운데 하나를 택했다고 가정하고 거리행렬을 업데이트했더니 AD와 C가 가장 인접해 있군요. 이번엔 이 둘을 이어줍시다.
그 다음 과정을 수행했더니 아래처럼 되었습니다.
분석 대상 관측치가 하나도 없으면 학습이 종료됩니다.
HC의 특징
이미 설명해 드린 것처럼 HC는 K-평균 군집화와 달리 사전에 군집수 $k$를 설정할 필요가 없습니다. 그도 그럴 것이 앞선 예에서 덴드로그램의 최상층을 끊어주면 $A, D, C$와 $B$로 두 개 군집이 도출됩니다. 위에서 두번째 층을 끊으면 $A, D$와 $C$, $B$ 이렇게 세 개 군집이 나옵니다. HC의 학습결과물인 덴드로그램을 적절한 수준에서 잘라주면 된다는 얘기입니다. 반면 HC의 계산복잡성은 $O(n^3)$로 K-평균 군집화보다는 무거운 편입니다.
Comments