博文
FASP 和 Nystrom low-rank approximation
||
FASP：Fast Approximate Spectral Clustering
2009年KDD上的这篇Fast Approximate Spectral Clustering，提出了一种谱聚类算法的框架，并设计了该框架下的两个实例：基于k-means算法的KASP，和基于随机游走的RASP。并通过实验说明了该框架的优势。这篇文章和之前阅读的Spectral Grouping Using Nystrom Method有很强的关联，它指出了后者的缺点，并强调消除这些缺点。目前被引用次数为72。
首先减小矩阵的规模，将处理后的小规模矩阵作为聚类算法的输入，最后将聚类得到的结果，通过样本点和原数据集的映射关系，恢复为原数据集的聚类结果。这是许多大数据谱聚类方法的根基。而前段时间阅读的一篇文章，Spectral Clustering Using Nystrom Method，采用的也正是这种思想：用某种方法从原数据的相似度矩阵的列集合中抽样，通过样本集以及样本集和非样本集之间的相似度，估测原数据的相似度矩阵和特征向量。文章列举了这篇文章所介绍的方法的三个缺点：
1，抽样时，并不关系相似度矩阵包含的信息（描述太抽象，不理解）。
2，空间复杂度很大（除了涉及到样本集的计算，未采样的数据点的集合也参与了计算）
3，如果原数据集是不平衡（unbalanced，这个概念在 2007 IEEE A Tutorial on the spectral clustering 中提到，和指示向量是否相互正交化有关）的，可以用于计算的样本集将会很小，这将很大程度影响最后计算结果的准确度。（2008 Improved Nystrom low-rank approximation and error analysis 中提到，用k_means方法采样使得Nystrom low-rank approximation的误差达到接近最小化的程度，但确实也回避了原数据集不平衡的问题）
KASP的算法如下：
预处理过程：
1，用K-Means算法对大小为n的原数据集{xi}n聚类，得到k个质心{yi}k。
2，建立质心集合到原数据集合的映射关系：离yi最近的xj，映射到yi。
聚类过程：
3，用谱聚类算法将k个质心聚为m类。
恢复过程
4，通过第2步得到的映射关系，将聚类结果映射为最终聚类结果。
算法的时间复杂度为：$ O({knt}+k^3) $，其中$ O(knt) $是第一步中kmeans算法的时间复杂度。算法的空间复杂度是$ O(2n+2k+k^2) $，由于未抽样的数据点不参与计算，空间复杂度大大小于2004年提出的Nystrom Approximation方法。
RASP算法和上面类似，仅仅是用随机游走树得到谱聚类的输入数据{yi}k。
下面说明该框架的理论支持：微扰理论。通过大量实验，说明FASP的优越性，然后通过理论上分析Laplacian Gragh的扰动来说明一点：FASP以牺牲了微小的聚类准确度为代价，实现了用较小的时间复杂度和空间复杂度对大数据实施谱聚类。
2002年NIPS上的Using the Nystrom method to speed up kernel machines 和 2005年发表在ICML的 Predictive low-rank decomposition for kernel methods ，是 Improved Nystrom low-rank approximation and error analysis 的两篇重要参考文献。后者的核心内容是在用于核矩阵估计的Nystrom low-rank approximation的基础上的误差分析与改进，这两篇文献是Improved一文改进的基础。
由于FASP算法罗列了Nystrom Approximation的三个缺点，而我前段时间读过的Improved一文相反地，对Nystrom low-rank approximation进行了改进，而改进的基础是核矩阵的Nystrom low-rank approximation，这增进了我对核矩阵的low-rank decomposition方法的兴趣。为更多地了解Nystrom low-rank approximation，下一周将从介绍该算法的基本文献开始进一步学习。
接下来的任务：
1，泛读关于k-means的最新文章；
2，泛读关于降维和谱聚类的联系的文章；
3，阅读上面提到的：2002 NIPS - Using the Nystrom method to speed up kernel machines 和 2005 ICML - Predictive low-rank decomposition for kernel methods，对Nystrom Approximation作一个小小的复习，并对Nystrom low-rank approximation作一个小结。
4，借以比较Nystrom Approximation和FASP的区别。
https://blog.sciencenet.cn/blog-799581-631128.html
上一篇：阶段性总结
下一篇：SDR, USDR and DRSC
扫一扫，分享此博文