Spectral Grouping Using The Nystrom Method (2004 IEEE)

   背景：谱聚类算法的大致步骤是，求数据集之间的相似度矩阵，并构造出相似度图，然后求得某种形式上的 Laplacian Matrix（L, Lrw或者Lsym），然后求laplacian matrix的前K个特征向量，随后以k个特征向量组成的矩阵U的前K个行向量作为输入，运行k-means算法，得到最后的聚类结果。这要求对整个数据集进行处理，在很多应用中是不符合实际的。把Nystrom Method应用到聚类算法上，求解得到通过样本集的相似度矩阵得到的Laplacian Matrix的特征向量，通过局部数据的特征向量推导出整个数据集的特征向量的近似值，可应用于当数据规模巨大时运行谱聚类算法的场景。

   Nystrom Method用于求解如下形式的积分方程：

   在[a,b]中间取n个均分点，并运用矩形公式将积分写成数值计算的形式：

   特殊地，令[a,b]为[0,1]，于是上面的式子可以表示成矩阵形式：。于是得到Nystrom Extension公式：

（1）

利用这个公式，可以实现背景中所述的目的。

A为样本点集合的相似度矩阵，C为非样本点集合的相似度矩阵，B是所有样本点和非样本点之间的相似度构成的矩阵。下面将使用上式，用A,B表示出C的估计值。，从而得到整个相似度矩阵。

这是原始矩阵，包含了整个数据集中任何两个点之间的相似度。

Nystrom Extension的矩阵形式为（可推导），其中U是样本集的特征向量构成的矩阵（见Tutorials中U的定义），通过（1），得到W的特征向量的估计和W本身的估计：

Nystrom extension可用B^TA^-1B对C进行估计，于是，可以用||C-B^TA^-1B||作为以上近似运算准确性的衡量。

    论文的第三部分还分别讨论A是正定矩阵和非正定矩阵这两种情况下构造W的近似表示的方法。应用于基于NCut的聚类时，可以通过W的近似结果将D^-1/2WD^-1/2的近似结果表示出来，从而在求解Lsym的这一步骤，避免了处理整个数据集的问题，提升了整个算法的性能。最后，根据Fisher criterion的度量方法，结合大量实验，对算法做了性能和误差的分析。论文比较了在稀疏表示下，Nystrom Approximation方法和dense solution的估计结果。对于有许多0或者近似为0的元素时，前者的估计非常准确且很好地保留了特征状态。但是这种方法依然需要O(N²)的时间复杂度来计算亲和度（除了需要计算A，还需要计算B），原文中的Fig.3列出了在实验中对于同一个图像，对于不同的样本集规模应用近似算法求得特征向量近似结果的评估值（基于Fisher criterion）。

图中，a)是150个输入点，b)是150个Normalized Laplacian矩阵的特征向量，其中1-50是聚成堆状的50个点对应的特征向量。c)显示了采用高斯加权的欧氏距离计算相似度时，参数的不同取值对应两个cluster之间的距离。d）e）f）比较了两种算法的性能度量。

1，如果在聚类时使用k近邻图(k-nearest neiborhood graph)作为相似度图，用高斯加权的欧氏距离公式Sij=exp(-||xi-xj||²/(2d²))，那么是否有方法能够优化参数d和k，使得聚类结果最优？

    

   Tutorial of the Spectral Clustering 中的 8.1.3 讲到，求解最优的k，目前极少的文献可以指导我们完成这一工作。然而我们知道，参数k的选用应该至少使得图中的连通分量比目标聚类数少。

   虽然不能确定相似度图的connectivity parameters，但是现有的许多方法能够选择最佳的目标聚类数k。例如，求矩阵的前k个较小的特征值后，如果第k+1个特征值较大，则目标聚类数选为k。

2，是否能够在实验中或理论中找到一个方法，比较和度量Tutorial中提到的三种谱聚类算法的聚类结果？

   

   从图的分割的角度，聚类的优化目标有二，1，类间相似度和最小；2，类内相似度和最大。因此可以通过比较类间相似度和以及类内相似度和这两个量，定量地衡量聚类算法的性能。

   同时达到两个目的的，是NCut和MinmaxCut（其中根据分析，前者优于后者），而来源于RatioCut的unnormalized clustering算法只达到了第一条目的。这个角度上说，采用Lrw作为拉普拉斯矩阵的归一化谱聚类算法是最优的。

   以上结果有待在具体实验中展现。