군집화(Clustering)

군집화란?

• 비지도학습의 대표적인 기술로 x에대한 레이블이 지정 되어있지 않은 데이터를 그룹핑하는 분석 알고리즘
• 데이터들의 특성을 고려해 데이터 집단(클러스터)을 정의하고 데이터 집단의 대표할 수 있는 중심점을 찾는 것으로 데이터 마이닝의 한 방법
• 클러스터란 비슷한 특성을 가진 데이터들의 집단으로 데이터의 특성이 다르면 다른 클러스터에 속함
• K-Means Clustering, Mean Shift, DBSCAN, Gaussian Mixture Model 등이 있음

1. K-Means Clustering

• 군집 중심점(centroid)라는 특정한 임의의 지점을 선택해 해당 중심에 가장 가까운 포인트들을 선택하는 거리 기반 군집화기법
• 다른 알고리즘에 비해 비교적 쉽고 간결하여, 일반적으로 군집화에서 가장 많이 사용되는 알고리즘
• 초기 클러스터의 수를 직접 결정해야하며 성능에 많은 영향을 끼침
• K-Means Clustering 알고리즘의 과정
  1. K개의 임의의 중심점(centroid)을 배치
  2. 각 데이터들을 가장 가까운 중심점으로 할당(일종의 군집을 형성)
  3. 군집으로 지정된 데이터들을 기반으로 해당 군집의 중심점을 업데이트
  4. 더이상 중심점이 업데이트 되지 않을 때까지 과정 2, 3을 반복
• K-Means Clustering의 초기화 기법
  • 무작위 분할 기법
  • Forgy 초기화 기법
  • MacQueen 기법
  • Kaufman 기법

K-Means Clustering의 예시

2. Mean Shift

• Sliding Window의 반경(정해진 시야)내에서 데이터의 분포가 높은 곳으로 단계적으로 중심점이 이동하는 군집화 기법
• K-Means Clustering과 유사하지만 거리 중심이 아니라 데이터가 모여있는 밀도가 가장 높은쪽으로 군집 중심점을 이동하면서 군집화를 수행함
• 데이터 간의 거리가 아닌 데이터의 분포도를 이용해 군집 중심점을 결정
• K-Means와 다르게 군집의 개수를 사전에 지정하지 않아도 되며, 비교적 이상치의 영향이 크지 않음
• 데이터셋의 형태를 특정 형태, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능Mean Shift 알고리즘의 과정
  1. Sliding Window의 크기를 정의하고, 중심점(centroid)를 임의로 설정
  2. 정해진 크기의 window 안에서 데이터의 분포가 높은 방향으로 중심점을 이동
  3. Sliding Window가 중첩될 경우, 데이터 분포도가 높은 window를 유지
  4. Cluster의 이동이나 변화가 없을 때까지 과정 2, 3을 반복

Sliding Window의 이동 과정과 Mean Shift Clustering의 예시

3. DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

• 데이터의 분포가 세밀하게 몰려 있어서 밀도가 높은 부분을 중심으로 데이터 그룹핑을 하는 밀도 기반 군집화 기법
• 군집의 개수를 사전에 지정하지 않아도 되며, 군집과 노이즈(Noise) 데이터를 구분할 수 있음
• 복잡한 기하학적 분포도를 가진 데이터를 군집화 할 수 있음
• 데이터의 밀도가 다양한 경우 적합하지 않음
• DBSCAN 알고리즘의 과정
  1. 데이터를 군집하기 위한 반경(Epsilon)을 정의
  2. 반경 내에서 군집과 이상치를 구분하기 위한 MinPoints를 정의
  3. 임의의 point의 반경 내에 MinPoints 이상의 데이터가 존재하는 지 확인
  4. 만약 존재한다면 이웃 데이터를 군집 내에 포함시키고 군집 내 속한 다른 point에 대해 과정 3, 4를 반복
  5. 모든 데이터에 과정 3, 4를 반복하여 군집 데이터와 노이즈 데이터를 구분

Core Point의 예시

 

Border Point와 Noise Point의 예시

• Ex) Epsilon = 100, MinPoints = 4일 경우
  • P1의 주변 반경 내에 4개 이상의 데이터가 존재하므로 군집이 형성되며 Core Point로 지정
  • P2 역시 같은 이유로 Core Point로 지정되며 P1과 P2는 서로 군집의 일부가 되므로 하나의 군집으로 연결
  • P3의 경우 주변에 2개의 데이터만 존재하므로 Border Point로 지정되고 주변 P2 군집에 포함
  • P4의 중심으로 어떤 데이터도 포함되지 않고 주변 군집에 포함되지 못해 어느 군집에도 속하지 못하므로 Noise Point로 지정

DBSCAN의 예시

4. EM Clustering using Gaussian Mixture Model(GMM)

• 군집 모양을 정의하기 위해 평균, 분산을 활용하고 타원의 형태로 군집화하는 기법
• K-Means에 비해 구현할 수 있는 군집의 모양이 유연함
• 복수의 군집내에 포함된 데이터에 대해 어느 군집에 속할 확률 분포를 알 수 있음
  • 데이터 A가 군집 1에 속할 확률 X와 군집 2에 속할 확률 Y의 형태로 분석 가능
  • K-Means의 경우 군집 1에 속하거나 군집 2에 속하는 yes or no의 분석을 수행
• 다른 알고리즘에 비해 비교적 계산이 복잡하고 느림
• 현실에 존재하는 복잡한 데이터 분포가 K개의 가우시안 분포를 혼합하여 표현
• 혼합 가우시안 분포(Gaussian Mixture)에서 개별 유형의 가우시안 분포 K개를 추출하고 각 데이터가 어느 분포에 속하는지를 추정, K개의 개별 가우시안 분포가 각 K개의 군집이 됨

K = 3일 때, Gaussian Mixture

• GMM에는 두 가지의 추정이 필요
  • 개별 가우시안 분포 곡선을 추정
  • 현재 데이터가 어느 분포에 속할 것인지 확률 분포를 추정
• EM Clustering using Gaussian Mixture Model의 과정
  1. 군집의 개수를 지정
  2. 임의의 Gaussian Distribution Parameter를 설정
  3. 모든 데이터에 대해 각각의 군집에 속할 확률을 계산
  4. 각각의 군집에 속한 데이터를 통해 Gaussian Distribution Parameter를 업데이트
  5. 각 군집의 parameter가 변화하지 않을 때까지 과정 3, 4를 반복

EM Clustering Using GMM의 예시

참고사이트

https://daebaq27.tistory.com/49

[머신러닝/ML] 군집화 (Clustering)

 

https://brunch.co.kr/@mnc/10

[ML101]#8.Clustering (2)