谱聚类新算法

聚类

LSC

2011年deng cai提出的基于标记点的大尺度谱聚类算法，2015年得到理论上的证明和误差证明，也说明了各个参数的选取影响以及未来的研究方向。标记点的选取可以选择KMeans或者随机选取。前者速度慢，准确性好，后者相反。两种方法的速度和准确率都是相对不错的。

算法原理

从二分图的矩阵$W_B$出发，将特征值问题的求解经过转换和替代，发现是和特征值分解相关。

算法流程

• 输入：n个数据点$x_1, x_2, \dots ,x_n \in \mathbf{R}^m$聚类的数量k
• 输出：k个聚类

具体步骤
1. 用kmeans或者随机选择的办法产生p个标记点U序列，kmeans计算复杂度是$O(tpn),t$是KMeans的迭代次数
2. 根据公式(4)建立所有数据点和标记点之间的稀疏关联矩阵$Z \in \mathbf{R}^{p \times n}$， 归一化每一数据点和r近邻标记点,计算复杂度为$O(pn)$
3. 计算pxp的$ZZ^T$前k个特征向量$A = [a_1, \dots, a_k]$，计算复杂度是$O(p^2 n)$
4. 根据公式7奇异值分解式子计算$B=[b_1, \dots , b_k]$，B的列向量是$W = {\hat Z}^T \hat Z$(nxn)的特征向量，计算复杂度是$O(p^3)$，直接计算是$O(n^3)$(注意：$n>>p$)
5. 对$B$的每一行数据做k-means获得聚类

程序下载地址：http://www.cad.zju.edu.cn/home/dengcai/Data/Clustering.html

影响因素

• 标记点p：大一点好，但不是越大越好，可以通过多次实验确定最优值。
• 最近的标记点r:从3-10，准确率略有下降。可通过多次实验确定最优值。(r< p)

参考文献

1. Chen X, Cai D. Large Scale Spectral Clustering with Landmark-Based Representation[C]//AAAI. 2011
2.