博文
2007 Tutorials of Spectral Clustering 学习笔记(03)
||
学习了谱聚类的算法，以及unnormalized spectral clustering和采用Lrw的谱聚类算法这两种聚类算法的来由后，继续学习了采用Lsym的谱聚类算法的原理。在 Setc.5.4 中有所阐述，原理和推导和前面类似。
Sect.6介绍了随机游走，Sect.7介绍的微扰理论是一种重要的近似方法，分别就两个不同角度解释了why spectral clustering works这个问题。Sect 8从实现的细节这个角度，继续阐述谱聚类算法的一些重要细节。本篇笔记将在今后继续完善下去。
用于求解积分方程的 Nystrom Method 可用于用小样本估测整个数据集的相似度矩阵的特征向量，在谱聚类算法尤其是基于NCut的谱聚类算法中有重要应用，故本周主要阅读了2004 IEEE的Spectral Grouping Using the Nystrom Method。
Sect 8.1 相似度图
首先看相似度函数。
1，被相似度函数“认为”相似度大的点，实际情况应该是确实更接近。反之亦然。
2，全局的、绝对的相似度并不重要，两点之间的相似度是0.1或者0.01并不重要，因为0.01和0.1都是很小的相似度，除非用全连通图（就算是全连通图，那些很小的相似度也不影响聚类结果，并不因为两点之间有一条权值很小的边，就将两点聚为一起），在图中，这两个点不会被一条边连接。
3，相似度函数的选用和数据定义域和数据的分布有关系。一般情况下选用高斯化欧氏距离函数是合适的。
相似度图：
1，e-图难以确定合适的e，因为一个数据集中可能存在不同的数据分布。
2，Mutual KNN相对于KNN的优点：可以避免将密度不同的两“堆”点连接起来。缺点，可能造成相似度图中边太少的问题。
3，全连通图也是一种选择，不过它将导致得到的拉普拉斯矩阵不是稀疏矩阵，在求特征向量时，将增大计算开销并影响准确度。
4，一般情况下，推荐使用KNN。
Sect 8.2 计算特征值
1，如果是KNN或者e-图，L将是稀疏的，此时有许多方法求解L的特征向量：the power method、Krylov Subspace method、Lanczos method等等。
2，典型算法的收敛速度为rk=|eigval(k)-eigval(k+1)|。
2，如果特征值有重根，比如当有k个不相连的类（相似度图有k个连通分支）则有k个为0的特征值。
Sect 8.3 最佳的k（类的个数）
eigengap heuristic 方法：如果前k个特征值较小，而第k+1个特征值较大，则聚类的类个数选为k。（如此说来，这种方法可配合计算特征值和特征向量使用。）
这种方法在各个cluster分开得很明显的情况下，否则如果受到过多噪声的影响，或者类之间的相互覆盖很严重，则这种方法有效性欠佳。
Sect 8.5 Laplacian 图的选择。
选择通过哪一个拉普拉斯矩阵的特征向量来聚类，是一个重要的问题。用L,Lrw和Lsym都可以达到聚类的目的。经过实验，三者的效果是有差别的。一般而言，归一化的谱聚类算法优于未归一化的谱聚类算法，而前者中，采用Lrw的算法优于采用Lsym的算法。
首先回顾聚类的目的。在Sect 5中一直将聚类看成一种最优化问题，具体而言需要优化的目的是要找到一个图的划分，使得：1，类间相似度最小，即cut(A，B)最小；2，类内相似度最大，即W(A,A)和W(A，B)最大。
假使k=2，A和B是V的两个割。W(A,A)=W(A，V)-W(A,B)=vol(A) - W(A,B)。所以为达到上面的优化目的，vol(A)必须最大化，cut(A，B)最小化。
而显然。NCut所解决的真是这个问题。故而，Lrw作为拉普阿斯矩阵是最合理的。NCut中含有vol(A)的优化问题，而，vol(A)=cut(A，B)+W(A,A) ，可是MinmaxCut只涉及到W(A，A)的优化，所以我们有理由相信，在谱聚类中，Lrw优于Lsym。
再看RatioCut，其优化目的是使得：1，cut(A，B)最小；2，|A|最大。但是类内相似度和集合中点的个数无关，而与集合中的点之间相似度有关。故而RatioCut对应的unnormalized spectral clustering算法不能很好地达到聚类目的。
https://blog.sciencenet.cn/blog-799581-626676.html
下一篇：Nystrom Method在聚类算法中的应用
扫一扫，分享此博文