博文
阶段性总结
||
我对大数据谱聚类的学习，从2007年IEEE上的 A tutorial on spectral clustering 开始。这篇文章从相似度及拉普拉斯图这两个基本概念开始，介绍了基本的谱聚类算法，并针对运用三个不同的拉普拉斯矩阵（L，Lsym，Lrw）做谱聚类的三种方法分别解释了算法的由来，随后罗列了诸如相似度图的选取（相似度图的比较、对聚类的影响、相似度参数的优化问题）、特征向量的求解、聚类个数k的确定、拉普拉斯矩阵的比较和选取等方面，讨论了重要的细节问题。从这些问题出发，甚至衍化出对谱聚类不同方面的研究。
和 Tutorial 相关的重要论文，是90年代Mohar的两篇文章 The Laplacian spectrum of graphs 和 Some applications of Laplace eigenvalues of graphs。这两篇文章介绍了关于拉普拉斯图的基础知识（尤其是重要性质）。
通过精读第一篇文章，对谱聚类算法的实施，由来以及影响因素有了一定了解。但是关于相似度参数的优化问题和特征向量求解等子问题相关的文章，还未涉足。
传统的谱聚类算法（Tutorial中所介绍的三种算法）由于其$ O(N^3) $的复杂度，对大数据问题是不适用的，Fast Approximate Spectral Clustering一文中提到，N达到1000数量级时，传统的谱聚类算法需要的开销就无法忍受了，而数据到上百万的规模时，传统谱聚类算法是完全不可行的。
2009年KDD上的 Fast Approximate Spectral Clustering 对解决大数据谱聚类问题的方法做了简单的总结：
1，二次抽样
2，不丢失原数据的结构和特征的情况下，用小规模的数据代替大规模数据
3，low-rank matrix approximation（Nystrom low-rank approximation）
三种方法的共同点，都是在运行某种聚类算法之前，缩小输入数据的规模。
其中第三种方法是将原本用于求解积分方程的 Nystrom Method 运用到谱聚类上，其贡献是通过样本集的其特征向量，估计原数据的特征向量，并用于谱聚类。这种方法常常出现在文献中，受到许多研究者众星捧月般的推荐。
关于Nystrom Approximation的文章，我阅读了两篇，2001年的 Spectral Grouping Using Nystrom Method 介绍了基本的Nystrom Approximation的方法。这篇文章的精髓主要在从Nystrom Method到谱聚类算法的数学推导上。
而在2008年的 Improved Nystrom lowrank approximation and Error Analysis 对用于核矩阵的low-rank approximation的Nystrom Method做了误差分析，他们得出的结果是误差主要来源于用样本点（landmark points）来标记原数据点（离某个样本点较近的原数据点将被这个样本点标记）的过程，因此联想到采用k-means的方法获取landmark points，将得到最优的结果。
在这个过程中，发现了以下问题。
1，k-means的算法优化问题。近年来这方面的论文不少，最新的两个是：
2013 Equally contributory privacy-preserving k-means clustering
2013 A comparative study of efficient initialization methods for the k-means
2，参数的优化问题：
·可优化的参数：相似度参数，相似度图参数（如KNN图的参数k），聚类个数k，采样参数（如采样规模m等）。
3，评估聚类算法准确度的方法。
·聚类本身可视为优化问题，可用优化目标作为检验标准。
·设计实验，在几周前实现了基本的三种谱聚类算法和已有的数据集的基础上，对三个算法进行评估。
·还有其他标准吗？
4，离群点等对聚类结果的影响和消除。
5，降维方法在谱聚类上的应用
·PCA、KPCA和谱聚类的结合有一部分现成的研究，二者的结合是从2004年开始出现的，目前涉及的文章较少，尚未深入阅读。
2003 iro.umontreal.ca - Learning Eigenfunctions of Similarity- Linking Spectral Clustering and Kernel PCA
2004 Springer - The PCA of a Graph and Its Relationship to Spectral Clustering
2004 ICML - K-means clustering via principal component analysis
2010 IEEE - Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted KPCA
2011 AISTATS - Dimensionality Reduction for Spectral Clustering
为了进一步学习谱聚类算法领域，计划大体从四个方面同时地继续建树自己的知识体系：k-means算法、抽样和估计，误差估计，降维和谱聚类。
To Be Continue...
https://blog.sciencenet.cn/blog-799581-630820.html
上一篇：Nystrom估计的误差分析及改进
下一篇：FASP 和 Nystrom low-rank approximation
扫一扫，分享此博文