博文
reading list - spectral clustering
|||
精读：
[1] 2007 Springer. Ulrike von Luxburg, A Tutorial on Spectral Clustering. 介绍了laplacian graph，similarity graph等谱聚类基础知识，以及利用三种laplacian graph进行聚类的谱聚类算法极其来由。最后介绍了诸如拉普拉斯矩阵的选择，聚类参数的选择，特征向量的求解等子问题的求解方法和进展。
[2] 2004 IEEE. Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik, Spectral Grouping Using the Nystrom Method.
介绍了将用于求解积分方程的Nystrom method通过变换，用于聚类算法的方法，这么做的好处，是通过对数据集中的抽样数据集进行Nystrom approximation，通过样本集的相似度矩阵估算出整个数据集的相似度矩阵，通过样本集的拉普拉斯矩阵的特征向量估算出整个数据集的拉普拉斯矩阵的特征向量，从而大大降低了处理大数据谱聚类问题的计算开销。
[3] 2008 ICML. Kai Zhang, Ivor W.Tsang, James T.Kwok, Improved Nystrom Low-Rank Approximation and Error Analysis.
小秩矩阵估计有许多方法，贪心算法，Nystrom Method和随机化算法。而其中Nystrom的性能和效率较高。该文首先对Nystrom approximation进行误差分析，并据此提出用KM算法求解landmark points从而得到样本集，并验证了这种方法由从算法的时间复杂度和为Nystrom low-rank approximation抽样时所带来的误差大小上，效果都优于前面三种抽样方法。
[4] 2009 KDD - Fast Approximating Spectral Clustering
说明了Nystrom low-rannk approximation的缺陷：
1，抽样时，并不关系相似度矩阵包含的信息（描述太抽象，不理解）。
2，空间复杂度大（不仅使用了样本集，未被采样的数据点集合也参与了计算，参考精读[2]，C是由A和B同时参与计算得到的）
3，如果原数据集是不平衡（unbalanced，这个概念在 2007 IEEE A Tutorial on the spectral clustering 中提到，和指示向量是否相互正交化有关）的，可以用于计算的样本集将会很小，这将很大程度影响最后计算结果的准确度。（精读[3]中提到，用k_means方法采样使得Nystrom low-rank approximation的误差达到接近最小化的程度，但确实也回避了原数据集不平衡的问题）
随后提出了自己的框架FASP，并在此框架下设计了采用K-Means的KASP和采用随机游走的RASP，通过实验说明了框架的优势：在聚类效果上牺牲了极小的代价，换来了计算的时间复杂度和空间复杂度很大的节约。随后通过微扰理论为框架提供了一定的理论支持。（个人认为该文章是先作出FASP优于其他算法的猜想，再用实验验证，最后理论上分析算法的误差和性能。）
[5] 2011 AISTATS Dimension Reduction for Spectral Clustering
其一，髙维度的数据点构建NN（近邻）图时会失效，原因是维度太高时，两点之间的距离将趋于常数；其二，谱聚类具有很大的灵活性，可用于许多数据类型的处理，但其致命弱点是对不重要的数据和噪点非常敏感。DRSC的目的是将原本高维数据降到线性空间，以便于作为谱聚类算法的输入；并因为降维时为了求降维子空间，用到的优化目标函数和Lsym谱聚类算法的优化目标函数相同，作者尽可能地将它与谱聚类算法结合起来。
DRSC是一个迭代算法次。对于一个数据集X，通过迭代最终求得它在central subspace上的正交投影。
引用次数仅1次的这篇论文，引用了许多论文，用到很多其他的理论，要弄懂这篇文章，需要阅读甚至精读很多参考文献，任务繁重。在阅读完它的重要参考文献（包括SDR等）之前，还没明白算法的由来。
[6] 2008 [NIPS] Spectral clustering with perturbed data
这篇目前引用量是43的文章，可以说是FASP框架灵感的来源。这篇文章沿着谱聚类（确切说，是bipartition）的算法流程，从数据集X上的扰动开始到相似度矩阵K的扰动、拉普拉斯矩阵Lrw的扰动，最终分析得到此扰动对谱聚类结果的影响（mis-clustering rate）的上界。
作者在分析中发现，聚类效果很大程度受到数据的均方差的影响，因而认为减小均方差可以提高聚类的准确性。实际上FASP确实是在实施聚类之前对数据进行预处理，达到上述目的。【鸣谢FIATLUX】
[7] 2006 [ICDM] Fast and extract out-of-core K-means clustering
K-Means虽然被称为是一种简单快速的方法，但是每次更新质心时，所有的数据点都需要参与计算，实际运行效果有待改善，而改善的空间在于，导致质心的位移的数据点只有簇的边界点。前人很多工作为了加快KM，都付出了准确度上的代价，FEKM的优势在于，提高了算法效率的同时还能精确地计算出一组质心，它和直接对大数据实施KM得到的一组质心是相同的。FEKM还有对抽样规模不敏感等优点。但是仍未解决KM原生的诸如对离群点和噪点敏感等许多问题。
作者用归纳方法对算法的正确性给出了证明。
[8] 1999 [ICDT] When is nearest neighbor meaningful[cited 1301]
引用次数上千，是研究NN和降维的重要文献。其中讨论了髙维度空间上NN失效的问题，用Slutsky定理给出了证明了满足一定条件时，维度的增大将导致数据集中各点的距离趋于相等。并通过实验找到了一个维度上限的经验值15，并且对满足不同概率分布的数据集进行了大致分析，分析此数据是否存在高维NN失效的问题。
[9] 2003 [Citeseer] A Comparison of Spectral Clustering Algorithms
这篇对比分析性的文章比较了当时最提出的四种主要的谱聚类算法（该文章作者也是提出了其中两种算法的大牛）。分为两类：迭代的和非迭代的。理论上证明了将Lsym和Lrw两个矩阵作为L的两种算法（NJW和Meila-Shi算法）是等价的。并用实验结果分析比较了四种算法，不过，作者并没有达到文章开始提到的“ find out which of the sub-components are important and which not,and to see if some combinations of these works the best.”的目的，目前的谱聚类算法的主体，仍然没超越大牛当年的思想。
[10]2013 A Comparative of Initialization Methods of K-Means
从1965年的文献开始，罗列了许多IMs of KM。依次介绍了各个方法及其优缺点，并从复杂度角度比较了两种复杂度的算法及其应用。作为一篇导论性或综述性的文章具有一定可读性。
泛读：
[1] 1997 Graph Theory, Combinatorics and Application. Bojan Mohar, THE LAPLACIAN SPECTRUM OF GRAPHS.（被精读[1]所引用）
系统地介绍了拉普拉斯图极其性质。
[2] 2002 [Springer Annals of the Institute of Statistical] SDR and Graphics in Regression
主要阅读了SDR部分，介绍Sufficient Dimension Reduction，一种监督降维方法。引用次数为32，许多论文在此基础上提出了其他的降维方法和应用。
https://m.sciencenet.cn/blog-799581-628674.html
上一篇：Nystrom Method在聚类算法中的应用
下一篇：Nystrom估计的误差分析及改进
扫一扫，分享此博文