Hierarchical Clustering

✔ Clustering 종류

• Flat clustering : 일반적인 clustering
• Hierarchical clustering : 계층적으로 상하 관계가 있는 Clustering
• Hard clustering : 하나의 문서는 하나의 cluster에 속해있음
• Soft clustering : 하나의 문서가 여러개의 cluster에 속할 수 있다.

※ 지금 알아볼 것은 Hierarchical clustering이고 top-down과 bottom-up 방식이 있다.

 

🔍 Hierarchical Agglomerative Clustering (HAC)

• bottom-up 방식 : 맨 아래의 문서부터 위로 올라가는데, 맨 아래부터 각 문서가 하나의 cluster로 가정하고 위로 올라갈수록 더 큰 cluster로 묶는다.
  
• 문서들을 유사도에 따라 점층적으로 묶어서 올라간다.

• 최종 결과를 dendrogram이라고 부른다.
• K-means에서는 cluster 갯수를 미리 정해주어야 하는 어려움이 있었는데, HAC는 그러지 않아도 된다.

✔ Cluster 묶을 때 유사도 구하는 법

• ※ 각 cluster는 하나의 문서로 이루어져 있으므로, 처음에는 가까운 문서끼리 2개씩 묶는다.
• single-link (Maximum similarity)
  • 두 클러스터에서 가장 가까운 문서의 유사도를 cluster의 유사도로 사용
  • 결과적으로 작은 클러스터들이 많이 생겨서 균형이 좋지 않은 dendrogram이 나온다.
  • chaining 문제가 발생할 수 있다.
• complete-link (Minimum similarity)
  • 두 클러스터에서 가장 먼 문서의 유사도를 cluster의 유사도로 사용
  • banlance가 좋은 dendrogram이 나온다.
  • 이상치가 있을 때 효과적이지 않다.
• centroid 방법 (Average intersimilarity) : 모든 pair의 유사도의 평균을 cluster의 유사도로 사용 (두 클러스터의 centroid의 거리과 같다)
• Group average (Average intrasimilarity) : average intersimilarity에서 같은 cluster 안의 pair도 포함하여 평균을 계산

🔍 Divisive Clustering

• top-down 방식이다.
• 처음엔 하나의 cluster이고, 점점 쪼갠다.
• 분할 할때는 K-means 알고리즘을 사용한다.

✔ Bisecting K-means 알고리즘

• 대표적 top-down clustering
• 처음에 두 그룹으로 분리하고, 두 그룹 중 크기가 더 큰 것을 우선적으로 분리한다.
• 원하는 갯수로 이루어진 cluster가 될 때까지 과정을 반복한다.
• 장점 : 원하는 갯수까지만 분류하기 때문에 HAC보다 빠르다.
• 단점 : k-means 특성상 centroid를 임의로 정하기 때문에 centroid 선택에 따라 결과가 달라진다.

✔ 용도에 따른 사용

• 빠른 속도의 결과를 내야할 때 : 1순위.flat clustering 사용, 2순위. bisecting k-means 사용
• k 숫자를 정하기 어려울 때 : HAC 사용
• 항상 일정한 결과를 얻기를 원할 때 : HAC 사용
• 계층 구조의 결과가 필요할 때 : HAC 사용