Spectral Clustering

Posted by Kaiyuan Chen on May 21, 2018

Spectral Clustering a Brief Tutorial

Intro

Graph based clustering problems are treating clustering as graph partitioning. In this case, it treats cluster points using eigenvectors.

Advantages

  • good for sparse data
  • don’t make assumption on statistics

Matrices

D(degree matrix) = d(v_i) for i = j, 0 otherwise

​ which has degree of each vertex

Affinity matrix is i,j pair of affinity

Laplacian L = D - A

Spectrum Matrix is k eigen vectors of L with dimension N*k, N is dimension of eigen vector.

After getting spectral matrix, we calculate k means in a much lower dimension

Application

image segmentation, motion segmentation, image clustering etc.

Reference

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7009685