카테고리 없음

2. 군집화 (Clustering) - 알고리즘

wonpick 2023. 5. 7. 22:02

1. 군집화란?

유사한 속성들을 갖는 관측치들을 묶어 전체 데이터를 몇 개의 군집으로 나누는 것. 

좋은 군집화는 동일한 군집에 소속된 데이터는 서로 유사하게(inter-class similarity), 상이한 군집에 소속된 데이터는 서로 다르게(intra-class dissimilarity) 군집화하는 것이다.

 

Inter class similarity Intra-class similarity
  • Class간의 분산
  • Differ is better
  • Centroid/Border 간 거리가 멀수록
  • Class 내부의 분산
  • Similar is better
  • 분산의 값이 작을 수록
  • Centroid-border간 거리가 가까울 수록

 

2. 군집화 수행 시 주요 고려사항

  1. 어떤 거리 척도를 사용하여 유사도를 측정할 것인가?
  2. 어떤 군집화 알고리즘을 사용할 것인가?
  3. 어떻게 최적의 군집수를 결정할 것인가?
  4. 어떻게 군집화 결과를 측정 / 평가할 것인가?

오늘은 이 중 군집화 알고리즘에 대해서 다뤄보겠다.

 

3 . 군집화 알고리즘 

1. 계층적 군집화(Hierarchical Clustering)

예시: Agglomerative Clustering, Divisive Clustering

  • Hierarchical Agglomerative Clustering, HAC (상향식 알고리즘)
    • 시작시 각 포인트를 하나의 클러스터로 간주하고, 가장 가까운 클러스터들을 하나로 묶어가며 클러스터의 개수를 줄여나가는 방식. 이때 거리 계산 방식에 따라 Single linkage, Complete linkage, Average linkage, Ward's method 등 다양한 방식을 사용할 수 있다. 각 단계에서 클러스터의 개수를 줄여나가며, 최종적으로 모든 포인트들이 하나의 클러스터로 묶이는 시점까지 진행된다.
  • Hierarchical Divisive Clustering, HDC (하향식 알고리즘)
    • 시작시 모든 포인트들을 하나의 클러스터로 간주하고, 클러스터를 분할해나가는 방식. 이후, 각 클러스터를 다시 두 개의 하위 클러스터로 분할하는 과정을 반복하여, 클러스터의 개수를 증가시켜가는 방식. 상향식 알고리즘과 달리 클러스터의 개수를 늘려가며 군집화를 수행하는 방식이기 때문에, 일반적으로 상향식 알고리즘보다 더 많은 계산 리소스를 필요로 한다.

 

2. 분리형 군집화(Disjunctive Clustering)

서로 겹치지 않는(disjunctive) 클러스터를 생성하는 방법이다. 이는 분류 문제에서의 클래스(class)와 개념적으로 유사하며, 각 클러스터는 다른 클러스터와 서로 배타적이다. 군집 개수를 사전에 설정함.

- 각각의 관측값들은 최소한 하나의 군집에는 속해야 한다.
- 하나의 관측값은 하나의 군집에만 속한다. 중복되지 않는다. 
- K평균 클러스터링은 군집화 내의 variation이 작으면 작을수록 좋은 클러스터링이다. 

예시: K-Means Clustering, K-Medoids Clustering

  • K-Means Clustering: 클러스터의 개수를 미리 정하고, 초기 클러스터 중심값을 설정하여 각 포인트가 가장 가까운 클러스터에 속하게 하며 클러스터의 중심값을 업데이트하는 방식
    • 클러스터의 중심점으로 평균(mean)값을 사용
    • 각 클러스터 내의 모든 데이터 포인트와 클러스터 중심점 간의 거리를 최소화하는 방식으로 클러스터를 구성
    • 이상치(outlier)에 민감함.
  • K-Medoids Clustering: K-Means Clustering과 유사하지만, 클러스터 중심값이 포인트(medoid)들 중에서 선택되는 대표 포인트로 설정되는 방식
    • 각 클러스터 내에서 중심점으로 선정된 데이터 포인트와 클러스터 내의 모든 데이터 포인트 간의 거리를 최소화하는 방식으로 클러스터를 구성.
    • 클러스터의 중심점은 데이터 포인트 중에서 가장 대표성이 높은 포인트로 선정되며, 이 값을 중심으로 클러스터를 형성 함.
    • 계산 비용이 높아 대용량 데이터 셋에서 시간이 오래 걸릴 수 있다. 

3. 자기조직화 지도 (Self-Organizing Map (SOM))

비정형 데이터를 처리하고 분석하는 데에 사용되는 인공신경망 기반의 군집화 알고리즘이다. 이미지 분류, 텍스트 분류, 음성 인식, 통계 분석 등의 분야에서 활용되고 있다.

예시: Kohonen SOM, SOMP(SOM with Positive Constraints), Growing SOM 등

  • Kohonen SOM(가장 기본적인 형태의 SOM 모델)
    • 2차원 격자 형태의 인접한 뉴런들을 사용하여 입력 데이터를 특정 토폴로지 상에 매핑하는 방식. 이 모델은 뉴런 간의 가중치를 초기화하고, 입력 데이터와의 거리를 기반으로 가장 가까운 뉴런을 선정하여 가중치를 업데이트하는 과정을 반복하며 학습한다. 
  • SOMP(SOM with Positive Constraints)
    • 데이터 분포의 특성을 고려하여 뉴런 간의 거리를 계산하는 방식을 개선한 모델. SOMP는 데이터 간의 상호작용을 고려하여 클러스터링 결과를 개선할 수 있다.
  • Growing SOM
    • 초기에는 더 적은 수의 뉴런을 사용하여 시작하고, 학습 과정에서 더 많은 뉴런이 동적으로 추가되는 방식으로 동작한다. 이 모델은 SOM의 복잡도를 조정할 수 있어, 더 정확한 클러스터링 결과를 얻을 수 있다는 장점이 있다.

4. 분포 기반 군집화

분리형 군집화와는 다르게 군집 개수를 사전에 설정하지 않고, 밀도 기반으로 형성하기 때문에 밀도가 높은 부분을 더 자연스럽게 클러스터링 할 수 있다.

예시: DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

  • DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
    • DBSCAN은 데이터의 밀도(density)를 기반으로 클러스터를 형성
    • 기본적으로 밀도가 높은 지역을 하나의 클러스터로 형성하고, 밀도가 낮은 지역은 이상치(outlier)로 분류
    • 각 데이터 포인트의 이웃들을 검사하면서 군집을 형성하며, 이 때 이웃의 밀도가 일정 기준(threshold)을 넘어야 군집에 속할 수 있게 된다.  K-Means와 같은 거리(distance) 기반 군집화 알고리즘과 달리, 군집의 모양이 유연하게 변할 수 있으며, 이상치(outlier) 데이터를 잡음으로 처리하므로 더욱 자연스럽게 클러스터링 가능
    • 따라서 군집 개수를 알 수 없는 데이터셋에서 사용 가능하며 밀도가 높은 데이터셋에서 좋은 성능을 보임
    • 하지만 그만큼 계산 비영이 높아 대규모 데이터셋에서는 부적합함.