계층적 군집(Hierarchical Clustering)

계층적 군집

계층적 군집은 데이터를 가까운 집단부터 순차적이며 계층적으로 군집화하는 방식이다.

트리구조를 통해 각 데이터들을 순차적, 계층적으로 비슷한 그룹과 묶어 클러스터링을 진행한다고 이해하면 된다. 

계층적 구조로 인해 클러스터 혹은 군집의 개수를 미리 정하지 않아도 되지만 매번 지역 최소값(local minimu)을 찾아가는 방법을 활용하기 때문에 클러스터링의 결과값이 전역 최소값(global minimum)이라고 해석하기는 어렵다. 

 

조금 더 쉽게 이야기하자면 계층적 군집은 가장 처음에 모든 군집이 하나의 데이터만을 가진다. 따라서 최초에는 데이터 개수만큼 군집이 존재하지만 군집을 합치면서 최종적으로 하나의 군집만 남게 되는 방식이다. 

이로 인해 합체 군집화라고도 한다.  

 

계층적 군집의 결과는 보통 Dendrogram 형태로 표현하여 쉽게 확인이 가능하며, 시각적으로 파악이 가능하다. 

 

 

계층적 군집의 장단점

장점

• 클러스터의 개수는 계층 구조를 보고 조정이 가능하기때문에 유연성이 높다. 미리 클러스터의 개수를 정할 필요가 없다. 
• 클러스터링 된 과정과 결과를 한 눈에 확인 가능해 클러스터 간의 관계 파악이 가능하다. 클러스터 간의 비교 분석에 용이하다. 
• 이상치는 다른 클러스터와 계층적으로 별도 분리되어 있을 가능성이 크기 때문에 이상치 제거에 활용이 가능하다. 

단점

• 계산 복잡도가 큰 편이다. 특히, 모든 데이터셋 간의 거리를 비교해야하기 때문에 데이터셋의 크기가 클수록 계산 복잡도가 늘어난다. 
• 데이터 포인트 전체를 고려하기 때문에 데이터의 삭제, 추가, 변경에 민감하다. 

계층적 군집은 연산 시간이 크다는 단점을 가지고 있어서 대용량 데이터 분석에 적용하기는 힘들지만 계층 시각화 및 군집 간 관계 파악 등이 가능해 초기 데이터 분석 시 적은 양의 데이터로 사용하기 좋은 기법이다. 

 

 

계층적 군집 거리 측정법 

계측정 군집화를 하려면 우선 모든 군집 간 거리를 측정해야 한다.

군집 간 거리를 측정하는 방법은 아래와 같다. 

 

비계층적 거리 측정법

• 중심 거리(centroid, 중앙 중심법)
  두 군집의 중심점을 정의한 다음 두 중심점의 거리를 군집간의 거리로 정의한다.  
  
  
• 단일 거리(single, 최단 거리법)
  데이터 사이의 거리를 측정해 가장 작은 값을 구한다. 최소 거리 방법이라고도 한다.  
  조금 더 쉽게 설명하자면 생성된 군집들 사이 중심과 거리가 가까운 데이터끼리 비교해 가장 가까운 데이터끼리 군집한다.  
  
  
• 완전 거리(complete, 최장 거리법)
  데이터 사이의 거리를 측정해서 가장 큰 값을 구한다. 최장 거리 방법이라고도 한다. 
  조금 더 쉽게 설명하자면 생성된 군집들 사이 중심과 거리가 먼 데이터끼리 비교해 가장 가까운 데이터끼리 군집한다.  
  
  
• 평균 거리(average, 평균 기준법)
  데이터 사이의 거리를 측정해 평균을 구해 가까운 데이터끼리 군집한다. 

계층적 거리 측정법

계층적 거리 측정법은 계층적 군집화에서만 사용할 수 있는 방법이다.

즉, 이전 단계에서 이미 어떤 두 개의 군집이 하나로 합쳐진 적이 있다고 가정하여 이 정보를 사용하는 측정법으로 비계층적 거리 측정법에 비해 계산량이 적어 효율적이다. 

• 중앙값 거리(median)
  중심거리 방법의 변형이다.
  중심거리 방법처럼 군집의 중심점의 거리를 군집간의 거리라고 한다. 하지만 군집의 중심점을 계산하는 방법이 다르다.
  군집 A와 군집 B를 결합해 군집 C가 생겼다면 군집 C의 중심점을 새로 계산하지 않고 군집 A와 군집 B의 중심점의 평균을 사용한다. 따라서 해당 군집의 모든 데이터를 평균하여 중심점을 구하는 것보다 계산이 빠르다.  
  
  
• 가중 거리(weighted)
  가중 거리를 사용하기 위해서는 어떤 두 개의 군집이 합쳐져서 하나의 군집이 만들어졌는지 알아야한다.
  군집 A와 군집 B를 결합해 군집 C가 생겼을 경우 군집 D와 군집 C의 거리는 군집 C를 구성하는 원래 군집인 군집 A와 군집 B와 군집 D 사이의 두 거리 평균을 사용한다. 

  

• 와드 거리(ward)
  가중 거리 방법의 변형이다. 군집 D와 군집 C의 거리를 구할 때 가중 거리 방법처럼 군집 A와 군집 B와 군집 D 사이의 두 거리를 구하는 것은 같지만 원래의 군집 A와 군집 B의 거리가 너무 가까우면 군집 D와의 거리가 더 먼 것으로 인식한다. 

  

 

계층적 군집 과정

계층적 군집은 각 데이터 포인트 간의 거리나 유사도를 계산해, 작은 단위부터 클러스터링을 진행하면서 전체 데이터 포인트가 하나의 클러스터를 구성할 때까지 클러스터링을 반복적으로 진행하는 방식을 사용한다.

1. 각 데이터 포인트를 개별 클러스터로 고려한다. 
   총 데이터가 N개 존재한다고 했을 때, 각 포인트 1개씩 가지고 있는 N개의 클러스터 형성
2. 클러스터 간 Distance Matrix(거리행렬) 계산한다. 
   각 클러스터 간 거리 혹은 유사도를 계산한다. 
   클러스터 간 거리나 유사도를 계산하는 방법은 많지만 보통 유클리드 거리 계산법을 사용한다. 
3. 가장 비슷한 2개의 클러스터를 하나의 클러스터로 병합(merge)한다. 
   앞서 구현한 Distance Matrix(거리행렬)을 기반으로 가장 유사하거나 혹은 거리가 가까운 클러스터들을 하나의 클러스터로 연결한다.
   즉, 가장 가까운 거리에 있는 두 데이터 포인트를 묶어서 클러스터를 형성한다. 
4. 변경된 클러스터를 고려해 Distance Matrix(거리행렬)을 재계산한다.   
   새로운 클러스터가 생성되었기 때문에 Distance Matrix(거리행렬)의 업데이트가 필요하다. 
   새로 구성된 클러스터는 2개의 데이터 포인트를 가지고 있기 때문에 Distance Matrix(거리행렬)를 어떻게 구할 것인지 정의가 필요하다.
   • Distance Matrix(거리행렬) 구하는 방법
     • 단일 거리
     • 완전 거리 
     • 평균 거리
     • 와드 거리  
5. 3단계에서 4단계를 클러스터가 1개로 합쳐질 때까지 반복한다.

 

 

계층적 군집 코드 공부

https://github.com/DIB-PP/Machine-Learning

GitHub - DIB-PP/Machine-Learning

 

 

 

 

 

 

 

참고 자료

• https://aboutnlp.tistory.com/61
• https://devhwi.tistory.com/10
• https://datascienceschool.net/03%20machine%20learning/16.04%20%EA%B3%84%EC%B8%B5%EC%A0%81%20%EA%B5%B0%EC%A7%91%ED%99%94.html
• https://mangastorytelling.tistory.com/entry/%EB%8D%B0%EC%9D%B4%ED%84%B0-%EC%82%AC%EC%9D%B4%EC%96%B8%EC%8A%A4-%EC%8A%A4%EC%BF%A8-%EA%B3%84%EC%B8%B5%EC%A0%81-%EA%B5%B0%EC%A7%91%ED%99%94-hierarchical-clustering
• https://preservsun.tistory.com/entry/%EA%B3%84%EC%B8%B5%EC%A0%81-%EA%B5%B0%EC%A7%91-%EB%B6%84%EC%84%9D-%EB%B0%A9%EB%B2%95
• https://data-make.tistory.com/90