데이터 마이닝. 계층적 군집화(Hierarchical Clustering)

계층적 군집화(Hierarchical Clustering)는 데이터 마이닝에서 사용되는 군집화 기법 중 하나로, 데이터의 계층 구조를 반영하여 데이터를 그룹화하는 방법입니다. 이 알고리즘은 데이터 포인트들이 서로 유사한 특성을 가진 그룹으로 계층적으로 조직되는 과정을 통해 군집을 형성합니다. 계층적 군집화는 데이터가 특정한 개수의 군집으로 나누어져야 한다는 가정을 하지 않으며, 트리 구조(덴드로그램)를 통해 군집 간의 관계를 시각적으로 표현할 수 있습니다.

목차

 계층적 군집화의 기본 개념

- 병합적 계층적 군집화(Agglomerative Hierarchical Clustering): 가장 일반적으로 사용되는 방법으로, 모든 데이터 포인트를 각각의 군집으로 시작하여, 가까운 군집들을 반복적으로 합쳐가면서 하나의 큰 군집으로 병합해 나가는 방식입니다.
- 분할적 계층적 군집화(Divisive Hierarchical Clustering): 데이터 전체를 하나의 군집으로 시작하여, 이를 점차적으로 분할하여 더 작은 군집들로 나누어가는 방식입니다. 병합적 방식과 반대의 과정입니다.
- 덴드로그램(Dendrogram): 계층적 군집화의 결과를 시각적으로 표현한 트리 구조로, 데이터 포인트들이 어떻게 군집으로 합쳐지거나 나뉘는지를 보여줍니다.

 

 계층적 군집화의 과정

- 병합적 계층적 군집화 과정

1. 초기화(Initialization):

   - 각 데이터 포인트를 개별 군집으로 간주하여 시작합니다. 이때, 데이터셋에는 n개의 데이터 포인트가 있으며, 초기에는 n개의 군집이 존재합니다.

2. 거리 계산(Distance Calculation):

   - 모든 군집 간의 유사도 또는 거리를 계산합니다. 일반적으로 유클리드 거리, 맨해튼 거리, 또는 코사인 유사도 등을 사용합니다.
   - 군집 간의 거리를 정의하는 방법으로는 다음과 같은 방법들이 있습니다:
     - 단일 연결법(Single Linkage): 두 군집의 가장 가까운 두 포인트 간의 거리를 사용.
     - 완전 연결법(Complete Linkage): 두 군집의 가장 먼 두 포인트 간의 거리를 사용.
     - 평균 연결법(Average Linkage): 두 군집 간의 모든 포인트 쌍의 평균 거리를 사용.
     - 중심 연결법(Centroid Linkage): 두 군집의 중심 간의 거리를 사용.

3. 군집 병합(Cluster Merging):

   - 가장 가까운 두 군집을 하나로 병합합니다. 이렇게 병합하면 군집의 수가 하나 줄어듭니다.

 

4. 반복(Iteration):

   - 남아있는 군집 간의 거리를 다시 계산하고, 가장 가까운 두 군집을 병합하는 과정을 반복합니다. 이 과정은 모든 데이터 포인트가 하나의 군집으로 병합될 때까지 계속됩니다.

 

5. 덴드로그램 생성(Dendrogram Creation):

   - 군집 병합 과정에서 생성된 계층적 구조를 덴드로그램으로 시각화합니다. 덴드로그램을 통해 사용자는 원하는 레벨에서 군집을 선택할 수 있습니다.

- 분할적 계층적 군집화 과정

- 분할적 계층적 군집화는 병합적 계층적 군집화의 반대 방식으로, 초기의 하나의 군집에서 시작하여 점차적으로 데이터를 분할해 나가는 방식입니다. 이 방식은 병합적 방법보다 덜 일반적으로 사용됩니다.

 계층적 군집화의 장점

- 군집의 수를 미리 설정할 필요 없음: k-평균 군집화와 달리, 계층적 군집화는 군집의 수를 사전에 정의할 필요가 없습니다. 사용자는 덴드로그램을 통해 적절한 군집 수를 선택할 수 있습니다.
- 계층 구조 제공: 덴드로그램을 통해 데이터 포인트 간의 계층적 관계를 시각적으로 이해할 수 있어, 데이터의 구조를 쉽게 분석할 수 있습니다.
- 비구형 군집 처리 가능: 계층적 군집화는 비구형 군집도 잘 처리할 수 있습니다.

 

 계층적 군집화의 단점

- 높은 계산 복잡도: 병합적 계층적 군집화는 모든 데이터 포인트 간의 거리를 계산하고 반복적으로 병합해야 하므로, 대규모 데이터셋에 대해서는 계산 비용이 매우 높아집니다.
- 이상치에 민감: 이상치가 포함될 경우, 전체 군집화 과정에 부정적인 영향을 미칠 수 있습니다.
- 병합 후 수정 불가능: 병합이 진행되면, 한 번 병합된 군집은 이후에 다시 분할되지 않기 때문에 초기 병합이 잘못되면 최종 결과에 큰 영향을 줄 수 있습니다.

 

 계층적 군집화의 응용 분야

- 생물학적 데이터 분석: 유전자 발현 데이터를 계층적으로 군집화하여 유전자 간의 관계를 분석할 때 사용됩니다.
- 문서 군집화: 뉴스 기사나 연구 논문과 같은 문서를 유사한 주제로 그룹화하는 데 사용됩니다.
- 소셜 네트워크 분석: 소셜 네트워크에서 유사한 사용자 그룹을 찾아내고, 그들의 관계를 시각화하는 데 사용됩니다.
- 이미지 분석: 이미지 내의 픽셀을 계층적으로 군집화하여 이미지 세그먼테이션이나 객체 인식을 수행할 수 있습니다.

 결론

계층적 군집화는 데이터의 계층적 구조를 이해하고, 데이터 간의 관계를 시각적으로 표현하는 데 유용한 방법입니다. 병합적 계층적 군집화가 가장 널리 사용되며, 데이터의 특성에 따라 다양한 거리 측정 방법과 연결 방법을 사용할 수 있습니다. 그러나 높은 계산 복잡도와 이상치에 대한 민감성 등의 단점도 있으므로, 적용 시에는 데이터의 규모와 특성을 고려한 신중한 접근이 필요합니다.