5 분 소요

이번 포스트는 Clustering (군집화) 대해 다룬다.

Clustering

Introduction

  1. Cluster가 무엇일까?

    • 아무 점 모음 X
    • 같은 cluster 안에서는 서로 비슷해야 함.
    • 다른 cluster에 있는 점들과는 달라야 함.

    내부적으로는 뭉쳐 있고, 외부와는 잘 구분되어야 함.

  2. Clustering 이란 무엇일까?

    • 주어진 데이터 포인트들을 k개의 그룹으로 나누는 것
    • 입력 : 데이터 집합
    \[D = \{x_1, ..., x_n\}\]
    • 출력 :
      • 각 점이 어느 군집에 속하는지
      • 각 군집의 중심 또는 대표 구조
    • Unsupervised Learning (비지도 학습)
      • 정답 Label이 없다.
      • 데이터만 보고 알아서 구조를 찾아야 한다.
  3. 좋은 Cluster란 무엇인가?
    • High intra-cluster similarity
      • 같은 cluster 안에 있는 점들끼리는 가까워야 한다.
    • Low inter-cluster similarity
      • 군집과 군집 사이에는 차이가 커야 한다.
    • Objective Function
      • 거리 기반 : 점들이 가까우면 같은 군집
      • 확률 기반 : 같은 분포에서 생성된 점이면 같은 군집
      • density 기반 : 조밀한 덩어리를 하나의 군집으로 봄
      • connectivity 기반 : 연결 구조가 비슷하면 같은 군집
  4. Clustering이 어디에 쓰이는가? (Application)
    • Data Summarization : cluster center를 대표값으로 사용
    • Image Color Reduction / Image Segmentation :
      • K가 커질수록 표현력이 좋아지고 압축 효과는 줄어든다.
      • 픽셀끼리 비슷한 색끼리 묶어, 이미지를 더 적은 색으로 압축하거나 영역별로 분할 가능

Centroid-based Clustering

K-Means Algorithm

각 군집을 대표하는 중심(Centroid) 기준으로 클러스터링 하는 방법

K-menas

  • 모든 데이터는 가장 가까운 중심에 할당된다.

  • K-means의 Objective Function

    • within-cluster distance 최소화
    \[\sum_{i=1}^n \sum_{\alpha=1}^k [z_i]_\alpha \, d_{i\alpha}\]
    • 자기가 속한 cluster 중심까지 거리만 더함.

  • 중심 (centroid) 정의 \(\mu_\alpha = \frac{\sum [z_i]_\alpha x_i}{\sum [z_i]_\alpha}\)

왜 어려운가?

  • non-convex, non-continuous

    • 최적해를 찾기 어렵다

  • Brute-Force 방법 (only 이론)

    • 모든 cluster 조합을 다 만들어보고
    • 각각 점수를 다 계산하여
    • 최소를 선택

    현실적으로 불가능 (Polynomial Time에 해결 X)

  • 근사 알고리즘 사용

Step 1. Assignment Step

  • 각 점을 가장 가까운 중심에 할당

    • 중심을 랜덤으로 선택 (결과에 엄청 영향을 준다.) \(\alpha = \arg\min_\alpha ||x_i - \mu_\alpha||^2\)

    • 각 데이터는 가장 가까운 중심으로 이동

    • Membership 표현

    \[[z_i]_\alpha = \begin{cases} 1 & \text{if belongs to cluster } \alpha \\ 0 & \text{otherwise} \end{cases}\]

Step 2. Refit Step

  • 각 cluster 중심을 다시 평균으로 계산 \(\mu_\alpha = \frac{\sum [z_i]_\alpha x_i}{\sum [z_i]_\alpha}\)

    • Cluster 중심 = 평균
    • 중심이 클러스터 내부로 이동 (더 중앙으로 가게 됨)

Step 3. 위 과정을 반복 (Convergence)

  • 언제 멈추냐
    • 중심이 더 이상 안 바뀔 때까지

K-means의 한계

  • 구형 (Spherical) 가정
    • K-means는 거리 기반이라 동그란 cluster를 잘 잡는다.
    • 문제점 : 타원형, 길쭉한, 밀도 다른 cluster는 못잡음
  • feature scale
    • 스케일 큰 feature가 지배
  • Outlier에 매우 민감
    • 이상치 하나가 중심을 바꿔버린다.

  • 경계에 있는 점 표현하기가 어렵고, overlap 표현 불가

  • K를 미리 알아야 함.
    • 현실에서는 모른다.

K-Medoids Algorithm

K-means와의 차이로 공부

핵심 아이디어

  • cluster 중심이 “평균”이 아니라 실제 데이터 포인트

k-medoids

  • Medoid
    • cluster 안에서 다른 점들과의 총 거리가 가장 작은 실제 데이터

  • Objective Function \(\min \sum_{k=1}^{K} \sum_{x_i \in C_k} d(x_i, m_k)\)

    • 전체 거리 최소화

PAM (Partitioning Around Medoids) Algorithm

  • 초기화
    • k개의 데이터 포인트를 medoid로 선택
  • Assignment 단계
    • 각 점을 가장 가까운 medoid에 할당
  • Update
    • cluster 안에서 총 거리 최소가 되는 새로운 medoid로 선택
  • 반복
    • medoid 바꿔가면서 전체 거리 줄어드는지 확인

Choosing the Number of Cluster K

K-means는 잘 작동하는 알고리즘이지만, k를 미리 알아야 한다는 가장 큰 문제 존재

  • 데이터가 몇 개의 군집으로 나뉘는지 사전에 미리 알기 어렵다.
  • 그냥 많이 나누는 것이 아닌 의미 있게 나누는 적절한 군집 수 필요

단순히 K가 커지면.?

  • error가 줄어든다.
  • 각 점이 자기 cluster 중심에 최대한 가깝게 가도록 만들기

Objective 값이 작다고 해서 무조건 좋은 clustering은 아니다.

Elbow Method

  • k를 늘리면 error는 줄어들지만, 어느 순간부터 줄어드는 폭이 확 작아진다.
  • 그 지점이 최적의 K 값

elbow

과정

  1. k = 1,2,3,4,... 이렇게 바꿔가면서 K-means를 여러 번 돌림
  2. 각 K에 대해 objective value를 계산함
  3. 그래프로 그리고 감소가 급격하다가 완만해지는 지점 선택
  • 장점 : 계산이 비교적 쉽고, 직관적이고, 많이 사용
  • 단점 : elbow가 애매하거나, 그래프가 꺾이는 지점이 명확하지 않아서 사람의 주관이 들어감.

Silhouette Score

좋은 cluster

  • cluster 내부는 잘 뭉쳐 있어야 하고, 다른 cluster와는 잘 떨어져 있어야 함.

각 점에 대한 점수 계산 \(a(i)=\frac{1}{|C_i|-1}\sum_{x_j \in C_i, j\neq i} d(x_i,x_j)\)

  • a(i) : cohesion Score
    • 자기 군집 내부 평균 거리 : 작을 수록 좋다, 군집에 잘 어울린다는 뜻
\[b(i)=\min_{k\neq C_i}\left(\frac{1}{|C_k|}\sum_{x_j\in C_k} d(x_i,x_j)\right)\]
  • b(i) : Separation Score
    • 다른 군집과 얼마나 떨어져 있는가
      • 자기 cluster가 아닌 다른 cluster들 중에서
      • 가장 가까운 다른 cluster와의 평균 거리

Sihouette Score 공식 \(s(i)=\frac{b(i)-a(i)}{\max(a(i),b(i))}\)

  • b(i) 가 크고 a(i) 가 작아야 점수가 커진다.
  • 값 해석
    • s(i) = 1 : 매우 좋다.
    • s(i) = 0 : 애매하다.
    • s(i) < 0 : 오히려 다른 cluster에 가까운 점이다.
      • 잘못 배정됐을 가능성이 크다.

최종 cluster quality \(S=\frac{1}{n}\sum_{i=1}^{n}s(i)\)

  • 전체 데이터의 실루엣 평균을 구해서 그 clustering 전체의 품질 평가

Elbow Method vs Silhouette Score 비교

실루엣 스코어

Probabilistic Clustering

K-means / K-medoids의 한계

  • 구 모양 (spherical) 가정
    • 현실 데이터는 둥근 cluster 가정이 아니기에 못 잡음
  • 경계에 있는 데이터는 애매함

GMM (Gaussain Mixture Model)

  • 타원형 cluster 표현 가능
    • covariance (분산 + 방향) 사용
    • 기울어진 cluster 표현 가능
  • cluster마다 다른 퍼짐
    • 어떤 cluster는 넓고, 좁고 표현 가능
  • 확률 기반 할당 : 더 현실적인 모델링

핵심 아이디어

  • 데이터는 여러 개의 Gaussian (정규분포)의 섞임으로 만들어진다.
    • probabilistic (확률 기반)
    • generative (데이터 생성 모델)

GMM

  • Soft Clustering
    • x -> cluster 1 (70%)
    • x -> cluster 2 (30%)

수식 : 각 cluster를 Gaussian (정규분포)로 본다. \(x_i \sim \mathcal{N}(\mu_\alpha, \Sigma_\alpha)\)

  • mean : cluster 중심
  • Covariance : cluster 모양 결정
    • 작은 covariance : 뭉쳐 있다.
    • 큰 covariance : 퍼져 있다.
    • correlated : 상관 있다. 기울어진 타원

Dataset = Gaussians의 혼합물 \(p(x) = \sum_{\alpha=1}^{k} \pi_\alpha \mathcal{N}(x | \mu_\alpha, \Sigma_\alpha)\)

  • mixing coefficient : 각 cluster의 비율 \(\sum \pi_\alpha = 1\)

Step 1. cluster 선택

Step 2. 해당 Gaussian에서 샘플링

Cluster Membership Assignment \(p(c_\alpha | x_i) = \frac{p(x_i | \mu_\alpha, \Sigma_\alpha)\pi_\alpha} {\sum_l p(x_i | \mu_l, \Sigma_l)\pi_l}\)

  • 이 점이 cluster a 일 확률
    • 분자 : 그 cluster일 likelihood x 그 cluster 비율
    • 분모 : 전체 확률 (normalization)
  • Goal : 데이터를 가장 잘 설명하는 Gaussian들을 찾기

EM Algorithm (Expectation-Maximization)

GMM의 파라미터를 어떻게 구할까?

전체 알고리즘 흐름

  1. 초기화
  2. E-step (확률 계산)
  3. M-step (파라미터 업데이트)
  4. 반복 (convergence까지)

E-Step (Expectation Step) \([z_i]_\alpha = p(c_\alpha | x_i) = \frac{p(x_i|\mu_\alpha,\Sigma_\alpha)\pi_\alpha}{\sum_l p(x_i|\mu_l,\Sigma_l)\pi_l}\)

  • 이 데이터가 클러스터 a일 확률
    • 가까운 cluster이면 확률이 올라가고
    • 큰 cluster 이면 확률이 높아짐

M-Step (Maximization Step)

  • E-Step에서 구한 확률을 이용하여 모델 파라미터 업데이트 \(\mu_\alpha = \frac{\sum_i [z_i]_\alpha x_i}{\sum_i [z_i]_\alpha}\)

    • weighted 평균

  • 공분산 업데이트 \(\Sigma_\alpha = \frac{\sum_i [z_i]_\alpha (x_i-\mu_\alpha)(x_i-\mu_\alpha)^T}{\sum_i [z_i]_\alpha}\)

  • mixing coefficient \(\pi_\alpha = \frac{1}{n}\sum_i [z_i]_\alpha\)

-> 확률이 높은 데이터를 더 많이 반영

장점

  • Soft Assignment : 확률 기반으로 더 현실적
  • Elliptical Cluster 가능 : Covariance 방향 더 퍼짐 표현
  • Overlapping cluster 가능 : 겹쳐도 OK

단점

  • 여전히 K 가 필요
  • Gaussian 가정
    • 실제 데이터는 항상 Gaussian이 아니다.
  • 초기값 민감 (local optimum 문제)

Summary

  • K-means vs K-medoids vs GMM
특징 K-means K-medoids GMM
대표값 평균 실제 데이터 Gaussian
할당 hard hard soft
모양 원형 거리 기반 타원
이상치 약함 강함 중간
목표 거리 최소화 거리 최소화 likelihood 최대화

참고