클러스터링 - 계층적 군집화 동작 원리, 장단점

이번 포스팅은 클러스트링 중에 첫 번째로 계층적 군집화에 대해 알아보도록 하겠습니다. 계층적 군집이란 용어 그대로 순차적으로 계층을 만들면서 그룹을 만드는 방법입니다. 클러스트링 방법 중에 빈번하게 사용되는 알고리즘은 아니지만 특정 업무에서는 활용이 가능한 방법입니다. 

 

 

계층적 군집화(Hierarchical Clustering)

Hierarchical Clustering은 계층적 트리 모형을 이용하여 개별 개체들을 순차적, 계층적으로 유사한 개체끼리 군집과 통합을 합니다. 장점 중에 하나로 덴드로그램(Dentrogram)을 통해 시각화 가능합니다. 

• Dendrogram : 개체/군집들이 결합되는 순서를 나타내는 트리형태의 구조로 시각화 표현
• 트리의 높낮이가 유사도 거리를 의미함(낮을수록 높음)
• 군집(cluster) 개수를 지정하지 않고 결과를 보고 내 맘대로 잘라서 군집

개층적 군집화

계층적 군집화 동작 원리

1. 최초 유사도 계산
2. 모든 개체를 독집적인 군집으로 가정
3. 가장 가까운 두 군집을 하나로 병합
4. 유사도 업데이트
5. 단 하나의 군집이 남을 때까지 반복

 

군집간의 유사도(거리) 측정 방법

• 최단 최단(단일) 연결법 : 
  • 두 군집사이의 거리 최솟값으로 측정
  • 사슬모양으로 생길 수 있음, 고립된 군집을 찾는데 중점을 둠
• 최장(완전) 연결법 :
  • 두 군집사이의 거리를 최대값으로 측정
  • 군집들의 내부 응집성에 중점을 둠
• 중심 연결법 :
  • 두 군집의 중심 간의 거리 측정
  • 군집 결합할 때, 새로운 군집의 평균은 가중평균을 통해 구함
• 평균 연결법(average linkage) :
  • 모든 항목에 대한 거리 평균 구함
  • 계산량이 불필요하게 많아질 수 있음
• 와드 연결법 :
  • 군집 내의 오차제곱합에 기초하여 군집 수행
  • 크기가 비슷한 군집끼리 병합되는 경향 있음

군집간의 유사도 측정 방법

장점

• 사전에 군집의 수를 정하지 않아도 수행 가능
• 덴드로그램 생성 후 적절한 수준에서 자르면 그에 해당하는 군집화 결과 생성
• 특정분야(domain)에서는 이 dendrogram이 유의미한 계통체계(taxonomies)를 표현하기도 함
• 예를 들어, 광고 타겟에 대해 카테고리화 가능

단점

• 계층적 클러스터링의 최대 문제점은 greedy algorithm이라는 점인데, 이유는 한 번 병합이 되거나 분리된 군집은 다시 되돌릴 수 없음
• 군집 간의 거리를 어떻게 계산하는지에 따라 노이즈와 아웃라이어에 취약함
• 복잡한 군집을 다루지 못하는 등의 한계를 있음, 이 단점 때문에 많이 사용하지 않음
• 계층적 클러스터링은 상대적으로 계산 비용이 더 높음 - Proximity matrix를 사용하기 때문에 데이터 포인트가 천 개라면 그 제곱인 백만 번을 계산해야 함

살펴봤듯이 계층적 군집화 방법은 군집 중에서 가장 유사도가 높은 혹은 거리가 가까운 군집 두 개를 선택하여 하나로 합쳐가는 방법을 말한다. 그래서 합체 군집화(agglomerative clustering)라고 불리기도 합니다. 이 방법은 데이터 포인트나 개체를 유사성을 기반으로 계층적으로 그룹화하고 시각적으로 표현하는 데 사용됩니다. 활용 분야는 생물학 및 유전학, 소셜 네트워크 분석, 문서 군집화 등에 사용하고 있습니다.