Unsupervised learning

Unsupervised Learning

비지도 학습 : 라벨 없는 데이터에서 잠재된 구조(패턴·규칙)를
설명할 수 있는 함수를 찾아내는 것

비지도 학습의 범주

• 클러스터링
  : 레이블 없이 데이터들을 서로 비슷한 그룹으로 묶기

• 차원 축소(Dimension Reduction)
  : 고차원 데이터를 저차원 공간에 임베딩

• 표현 학습(Representation Learning)
  : 원시 데이터를 머신러닝에 유용한 특징(feature)으로 변환

• 생성 모델(Generative Model)
  : 주어진 훈련 데이터의 확률 분포 p(x)를 학습해서,
  그 분포를 따르는 새로운 샘플을 만들어내는 모델

Clustering

레이블 없이(unlabeled) 오직 입력 데이터만으로
데이터가 어떤 그룹(클러스터)들로 나뉘어 있는지를 학습

대표 기법:
K-means
Gaussian Mixture Model
Spectral Clustering

K-means의 기본 아이디어

목표 : 같은 그룹 내 샘플 간 거리는 작게(Intra-group variation ↓),
그룹 간 거리는 크게(Inter-group variation ↑) 만드는 것

• K개의 클러스터 중심(centroid)을 무작위로 선정
• 각 샘플 x를 $\underset{k}{\arg \min} \|\mathbf{x} - \boldsymbol{\mu}_k\|^2$로 가장 가까운 중심 ${\mu}_k$에 할당
• 각 클러스터에 속한 점들의 평균을 새 중심으로 업데이트
• 할당→재계산 과정을 클러스터 할당이 더 이상 바뀌지 않을 때까지 반복

Similarity Metric

클러스터 간 유사도(혹은 거리)를 측정하는 방법

세 가지 유형 :

Centroid-based Distance

클러스터에 속해 있는 모든 데이터 포인트들의 좌표를
평균(average) 내서 나온 한 가상 좌표 = 그 클러스터의 중심(centroid)

클러스터-샘플 거리 : $d(C_i, \mathbf{x}) = \|\boldsymbol{\mu}_i - \mathbf{x}\|$

Minimum/Maximum Pairwise Distance

두 클러스터 $C_i$와 $C_j$ 사이의 거리를
클러스터 내의 모든 가능한 점 쌍 $(x \in C_i, y \in C_j)$ 에 대해
각각의 점 대 점 거리 $∥x−y∥$를 계산한 다음,
그 중에서 가장 작은 값 또는 가장 큰 값을 대표 거리로 삼음

• 최소 거리 (single-link)

  $d_{\text{min}}(C_i, C_j) = \min_{x \in C_i, y \in C_j} \|x - y\|$

  두 클러스터 중 가장 가깝게 붙어 있는 점 쌍의 거리

• 최대 거리 (complete-link)

  $d_{\text{max}}(C_i, C_j) = \max_{x \in C_i, y \in C_j} \|x - y\|$

  가장 먼 점 쌍의 거리

Distribution-based Measures

클러스터 $C_i$ 안에 있는 점들이 어떤 밀도 함수 $P_i(x)$를 따른다고 가정하고
두 클러스터가 얼마나 다른 분포를 갖고 있는지를 수치로 재는 방법

두 분포 P와 Q가 얼마나 다른지 재는 지표로 KL 발산을 사용 :

Jensen–Shannon Divergence (JSD)도 사용 가능

Clustering Examples

이미지 분할을 위한 K-Means

사진에서 배경, 사람, 사물 등의 영역을 자동으로 구분(segmentation)하는 경우

각 픽셀을
$[R,G,B]$ 색상값이나 $[위치_x,위치_y,색상]$ 등의 벡터로 표현
원하는 클러스터 수 K를 정하고 K-Means를 실행
K가 작으면(ex. 2) 배경·전경 정도로만 분리,
K가 크면(ex. 10) 더 세밀하게 색·질감·객체별 영역이 나뉨

K-means

초기화

분할하고 싶은 클러스터 수 K를 정하고
데이터 공간에 무작위로 K개의 초기 중심점을 찍음

할당 단계 (Assign)

각 데이터 포인트(●)를 가장 가까운 중심에 할당

중심 재계산 단계 (Update)

각 클러스터에 속한 점들의 평균 위치를 계산해,
거기에 중심(×)을 이동시킴

$C_i$ : i번째 클러스터에 할당된 점들의 집합

반복 및 수렴 (그림 d)

할당↔이동 반복 → 손실(내부 거리 합) 수렴

cost function이 수렴(converge)하는 이유

1. μ 고정 → 클러스터 할당 $C$ 최적화

클러스터 내 제곱거리 합이 작아짐

2. C 고정 → 중심 μ 최적화

클러스터에 속한 점들의 평균으로 중심을 옮기면 제곱거리 합이 더 줄어듦

Discussion

시간 복잡도(Time Complexity)

• 할당 단계 (Assign)
  각 점마다 K개의 중심까지 거리를 계산 → O(KN)

• 중심 재계산 단계 (Update)
  각 클러스터별로 할당된 점들의 평균을 내기 위해
  모든 점을 한 번만 훑음 → O(N)

Remark

라벨 없는(raw) 데이터를 유용한 형태로 바꿔 주는 비지도 학습

PCA (Principal Component Analysis)

: 고차원 데이터에서 가장 큰 분산(variance)을 설명하는
저차원 부분 공간을 찾아냄

→ 차원을 줄여서 데이터를 더 잘 이해·시각화

K-means 알고리즘