선형대수와 통계학으로 배우는 머신러닝 - Chap11 비지도 학습

K-평균 클러스터링

K-means clustering: N개의 데이터를 K개의 클러스터로 나누는 클러스터링 기법
각 데이터 포인트와 각 그룹 평균 간의 거리를 구한 후 가장 가까운 클러스터로 배정하는 방법
k번째 클러스터의 평균을 이고 각 데이터는 I차원에 있음
x=(x1, …, xI)

k-means clustering algorithm

1. 그룹 평균 초기화
   주로 랜덤으로 그룹의 평균을 설정
2. 그룹 할당
   각 데이터 포인트와 각 그룹의 평균까지의 거리를 계산하고 가장 가까운 그룹으로 속하게 하는 것

n번째 데이터 포인트 xn과 각 그룹 평균 사이의 거리를 측정한 후 가장 가까운 그룹으로 할당한다는 의미

3. 평균 업데이트 (모든 데이터 포인트가 어떤 그룹에 속하는지 구할 수 있음)

지시함수 rkn을 사용해 그룹의 평균을 업데이트

4. 반복
   2,3단계 반복. (2단계에서 바뀌는게 없을때까지)

k means clustering은 가중치를 주지 않아 클러스터 간 데이터의 밀도 차이가 있을 경우 클러스터링이 잘 되지 않는 단점

계층 클러스터링

Hierarchical clustering algorithm: 데이터 간 계층을 기반으로 데이터 간 병합 또는 분할을 통해 해당 데이터 포인트가 속할 그룹 결정

• 병합 계층 클러스터링 (agglomerative hierarchical clustering)
• 분할 계층 클러스터링 (divisive hierarchical clustering)

병합 계층 클러스터링: 개별 데이터 포인트를 하나의 클러스터로 설정하고 시작하는 방법
시작값은 N개의 클러스터로 시작해서 각 클러스터간 유사도가 높을 경우에 하나의 클러스터로 합침

분할 계층 클러스터링: 전체 데이터 셋을 하나의 클러스터로 놓고 시작
마지막에는 클러스터가 데이터 개수만큼 분리됨

계층 군집 알고리즘의 결과는 dendrogram으로 시각화 할 수 있음

병합 계층 클러스터링에 사용되는 알고리즘: 연결방법 (linkage method)

• 단일 연결: 가장 가까운 거리에 있는 데이터를 이용하는 연결. 클러스터 쌍에서 가장 비슷한 샘플 간 거리 계산 후 거리가 가장 작은 두 클러스터 합침
• 완전 연결: 가장 먼 거리에 있는 데이터를 이용하는 연결방법. 가장 비슷하지 않은 샘플을 비교하여 합침

단일 연결

데이터 5개 존재한다고 가정
각 데이터 포인트별 거리 행렬 D 5x5를 구함

행렬에서 가장 작은 원소 값은 d53이 2로 가장 거리가 짧음

d(35)1 = min{d31, d51} = min{3,13}=3
…

이런 방식으로 클러스터간 거리를 구하고 거리 행렬을 업데이트 (4x4 행렬로 변환됨)

완전 연결

완전연결도 마찬가지로 가장 거리가 가까운 클러스터를 먼저 합침
그리고 새로운 클러스터와 다른 클러스터간 거리를 구할때 이때는 최솟값이 아닌 최댓값을 이용

d(35)1 = max{d31, d51} = max{3,13}=13

Ward’s 계층 클러스터링

xi는 각 데이터 포인트, x bar는 클러스터의 중심

DBSCAN

Density-Based Sparticl Clustering of Applications with Noise: 전체 공간에서 데이터가 가장 밀집된 영역을 찾음
그리고 그 밀집된 영역이 하나의 클러스터가 되고, 밀집도가 낮은 영역이 외부 영역으로 구분
기본 거리 측정 방식: 유클리드 거리
dbscan은 클러스터 개수를 사전에 정하지 않아도 됨
반경, 최소한의 데이터 포인트 개수가 하이퍼 파라미터

특정 데이터 포인트에서 eps 반경 내에 데이터 개수가 min_samples 이상 포함된다면 해당 데이터 포인트는 핵심 포인트로 지정
클러스터에는 속하지만 핵심 포인트가 아닌 데이터 포인트는 경계 포인트

데이터 포인트 종류: 핵심 포인트, 경계 포인트, 노이즈 포인트

eps-neighborhood of a point: 반경 eps 내 존재하는 데이터 개수
directly density-reachable: eps 내에 다른 데이터 포인트가 속하고 min_samples 이상인 것
density-reachable: x1, xn에 대해 xi+1이 xi에 대해 directly density-reachable인 경우
density-connected: 두개의 데이터 포인트 x1, xn이 데이터 포인트 xi에 대해 density-reachable인 경우
cluster: x1이 클러스터 c에 속할 때, 데이터 포인트 x1에 대해 데이터 포인트 xn이 density-reachable하면 xn도 클러스터 c에 속함
그리고 x1, xn 모두 클러스터 c에 속하면 데이터 포인트 x1, xn,은 density-connected함
noise: 구성된 클러스터가 C1 … Ck일 때 어디에도 속하지 못한 데이터 포인트는 노이즈라고 함

가우시안 혼합 모형

Gaussian Mixture Model: 전체 집단 내부에 속한 하위 집단의 존재를 가정한 확률 모델

EM 알고리즘

1. 초기화 단계
2. E-step
   ric: i번째 데이터가 그룹 c에서 추출되었을 확률 (responsibility)
3. M-step
   파라미터 구하기