Clustering

hierarchical

• 각 데이터 point를 cluster로 간주하고, 가장 가까운 cluster들을 반복적으로 병합(상향 방식)하여 클러스터를 형성한다.

• 결과적으로 dendrogram 형태의 계층 구조를 생성하여 클러스터 간의 관계를 시각적으로 표현할 수 있다.

k-means

1. 초기 k개의 centroid를 랜덤으로 부여한다.

2. 각 포인트를 가장 가까운 centroid와 연결하여 클러스터를 형성한다.

3. 클러스터가 형성된 후, 각 클러스터의 새로운 centroid를 계산한다.

4. centroid가 바뀌지 않을 때까지(즉, 수렴할 때까지) 2단계와 3단계를 반복한다.

• 적절한 k는 클러스터의 포인트들과 centroid 간 거리의 평균이 급격하게 감소한 후 조금씩 감소할 때로 결정한다.

• centroid와 포인트 간의 거리가 좁을수록 잘 클러스터링된 것이다.

• 초기 centroid의 위치가 클러스터링의 결과에 큰 영향을 미친다.

score

• $SSE = \sum_{i} \sum_{x \in C_i}(x-m_i)^2$, 낮을수록 cluster안의 point들이 잘 뭉쳐있다는 의미

• $SSB = \sum_{i} |C_i|(m-m_i)^2$, 클수록 cluster이 잘 구분된다는 의미

• $C_i$: i-th cluster

• $m_i$: centroid of $C_i$

• $|C_i|$: size of cluster i

• $m$: mean of all points

spectral(graph)

1. $L$ matrix를 생성한다.

2. $L$의 eigen value($\lambda$)와 eigen vecotr($x$)를 찾는다.

3. $\lambda_2$의 벡터로 매핑한다.

4. 매핑된 1차원 벡터 값을 정렬하고 분리한다.

graph cut

• $m$: number of edges of the graph

• $cut(A)=\sum_{i \in A, j \notin A}W_{ij}$

• $vol(A)=2*{number \ of \ edges \ insde A + cut(A)}$

• $\varnothing(A)=\frac{cut(A)}{min(vol(A), 2m-vol(A))}$

matrix

• $A$(adjacency matrix): 인접한 노드를 1로 표현

• $D$(degree matrix): 노드의 차수를 값으로 하는 대각행렬

• $L$(laplacian matrix): $D - A$

  • L의 모든 eigen value는 0 이상이고, $x^TLx=\sum{ij}L_{ij}x_ix_j \geq 0$과 $L=N^TN$을 만족한다.

  • L에서 찾은 eigen value와 vector에 대해 $\lambda_2=min_x\frac{x^TMx}{x^Tx}$를 만족한다. 이때 $\lambda_2$는 graph cut을 수행할 때 유용한 경계 값을 제공한다.

eigen value & vector

• $\lambda: det(A-I\lambda)=0$

• $X: (A-I\lambda)v=0$