3月 01

谱聚类记录 – Spectral Clustering

​设G是一个无向图，The unnormalized graph Laplacian matrix of G is defined as：L = D – A，其中D是一个diagonal matrix，每一个entry D(i,i)是G中顶点Vi的度，A是邻接矩阵。

$f'Lf=\frac{1}{2} \sum\limits_{i,j=1}^n w_{ij}(f_i-f_j)^2$    （式1）

1.Graph cut point of view

​对于解决k=2的最小分割问题，貌似有可行算法，而k>2时，有两种优化目标：RatioCut (Hagen and Kahng 1992) and the normalized cut Ncut (Shi and Malik 2000).

Unfortunately, introducing balancing conditions makes the previously simple to solve mincut problem become NP hard。也就是说，优化上述目标的简单方法通常会使得聚类得到的结果中有很多类只有一个object。如果要使每个类中object的数量得到平衡，问题就变成NP hard啦。所以Spectral clustering is a way to solve relaxed versions of those problems.即谱聚类其实只是上述优化目标的一种近似解法而已。

2.Random walks point of view

A balanced partition with a low cut will also have the property that the random walk does not have many opportunities to jump between clusters.

​​we actually look for a cut through the graph such that a random walk seldom transitions from A to ~A and vice versa.