Spectral Clustering

方法

首先采用高斯核计算样本之间的距离,其中$||s_i - s_j||^2$求的是l2 norm 的平方。

非正则化的拉普拉斯矩阵（unnormalized graph Laplacian matrix）定义为： $$ L = D - W $$ 其中W为邻接矩阵（adjacency matrix）D为度矩阵(degree matrix)定义为 $$ D_{i, i} = \sum_{j=1}^n w_{i, j}. $$

正则化的拉普拉斯矩阵（normalized graph Laplacians）定义为;

$$ L_{sym} = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} = I - D^{-\frac{1}{2}}WD^{-\frac{1}{2}} $$

• 需要注意在第二张图中的"first k eigenvectors"指的是k个最小的特征值对应的特征向量。

并行化

困难

1. 如何分布式的计算相似矩阵？
2. 如何分布式的进行相似矩阵的三角化？
3. 如何分布式的求解三角矩阵的特征向量与特征值？

参考

1. On Spectral Clustering: Analysis and an algorithm
2. A Tutorial on Spectral Clustering