Clustering

Clustering

Reference: Pattern

경성 군집화 hard clustering = 한 셈플이 하나의 군집에 속하도록 강제하는 방식

연성 군집화 soft clustering = 샘플마다 군집에 속하는 정도를 다르게 할 수 있음

k-평균 알고리즘

입력: 훈련집합 \(X = \{x_1,x_2,\dots,x_n\}\) 군집의 개수 k

출력: 군집집합 \(C = \{c_1,c_2,\dots,c_k\}\)

k개의 군집 중심 \(Z = \{z_1,z_2,\dots,z_n\}\)를 초기화한다.

while (true)

    for (i=1 to n)

\(x_i\)를 가장 가까운 군집 중심에 배정한다.

    if (위에서 이루어진 배정이 이전 루프에서의 배정과 같으면) break
   
    for (j=1 to k)

\(z_j\)에 배정된 샘플의 평균으로 \(z_j\)를 대치한다.

for (j=1 to k)

\(z_j\)에 배정된 샘플을 \(c_j\)에 대입한다.

or

1. 데이터 포인트 중 적당한 점을 집단 개수만큼 선택해 중심으로 정함
2. 데이터 포인트와 각 중심 사이의 거리를 계산해 가장 가까운 중심을 해당 데이터 포인트가 속한 집단으로 정함
3. 집단마다 데이터 포인트의 평균을 계산하고 이를 새로운 중심으로 정함
4. 데이터 포인트 모두가 속한 집단이 변하지 않거나 더는 계산할 수 없을 때까지 과정 2,3을 반복함

최적화 문제로 해석

k평균은 직관에 기초한 휴리스틱한 알고리즘으로 보이는데, 이면에는 이론적인 토대를 갖추고 있다.

k평균의 목적함수

\(J(Z,A) = \sum^n_{i=1} \sum^k_{j=1} a_{ji} dist(x_i, z_j)\)

Z는 군집 중심으로 A는 샘플의 배정 정보를 나타내는 k*n 행렬이다. i번째 샘플이 j번째 군집에 배정되었다면 \(a_{ji}\)는 1이고, 그렇지 않으면 0이다.

k-평균은 최적화 문제를 푸는 알고리즘으로 볼 수 있다.

• 루프를 반복하면서 목적함수의 값이 작아지는 방향으로 해를 갱신한다.
• 어떤 초기 군집 중심을 가지고 출발하더라도 수렴한다는 것은 증명되었으나
• 초기 군집 중심이 달라지면 최종 결과가 달라지는 문제가 있다.

EM 기초

Z는 입출력단계에서 보이지 않는 은닉변수 latent variable

EM 알고리즘 Expectation Maximazation algorithm

E단계

• 은닉변수를 추정하는 단계

M단계

• 매개변수를 추정하는 단계

친밀도 전파 알고리즘

소셜네트워크 자료에서 사용?

커널 클러스터링

유클리드 거리로 표현되는 거리를 내적으로 표현해서 커널로 보내어 비선형으로 분리한 클러스터링 결과 얻기

초기값의 영향을 많이 받아 결과가 바뀌기도

스펙트럴 클러스터링

차원축소를 통래 초기값에 대한 의존성을 줄이려는 시도

파라미터의 자동 결정

직접 초기값 입력하면 거기에 의존하여 결과가 바뀌기도 하니 객관적으로 결정되게끔 파라미터 선택되게 하는 기법

제곱 손실 상호정보량mutual information 사용 상호정보량보다 이상값에 민감하게 반응하지 않는디.