基于图滤波的快速谱聚类

倪中源，刘惊雷

（烟台大学 计算机与控制工程学院，山东 烟台 264001）

0 引言

随着计算机的快速发展，人们对于数据的存储以及使用能力已经得到提升，在很多领域都积累了大量的数据，那么如何快速的处理这些数据成了许多人研究的方向［1］。谱聚类（Spectral Clustering，SC）作为数据挖掘中的一个基本工具，传统的SC算法，大致都遵循以下的步骤：假设给定一个数据点的集合，SC的目标是将该点的集合划分为多个簇［2］，首先，计算两点之间的相似度的权重，根据这个权重构成与这个集合相关的图以及邻接矩阵；其次，计算与图相关的拉普拉斯矩阵，通过特征分解计算出拉普拉斯矩阵的特征向量，取前几个特征向量；最后，运用聚类算法通过这几个特征向量将数据点划分成多个簇［3］。在SC的应用过程中，主要用于两种情况：首先，在对数据点的集合进行聚类过程中，一些特定结构（例如，同心圆）不能通过k-means算法聚类，这时就能用谱聚类算法进行聚类［4］。其次，输入数据是一个网络模型，例如社会网络、神经网络或交通网络，这时也需要SC算法进行聚类［5-6］。不过在对数据的聚类过程中，如果数据集过大，SC通常会遇到三个主要的计算瓶颈：邻接矩阵的建立、拉普拉斯矩阵的特征分解、k-means算法运行计算时间过大［7］。因此如何解决这三个瓶颈使得谱聚类更适合大规模的实际应用已成为现在机器学习的十分热门的话题。受到图形信号处理和图嵌入的启发，本文提出了一种基于图滤波的快速谱聚类算法。

目前主流的解决上述三个瓶颈的办法，通常是通过对小规模样本进行特征分解来解决数据量过大的问题［8］，小规模样本的特征分解是指从完整的矩阵中采样一组列，然后对子矩阵进行小规模特征分解，或者用伪特征向量来避免特征分解，其方法主要是使用多项式近似对特征向量进行估算［9］。在众多方法中，伪特征向量避免特征分解由于其模型简单、易于实施、效率高得到了广泛的关注。

考虑数据规模较大情况下的聚类问题，其中规模较大的数据主要造成两方面的影响。首先，谱聚类在计算图拉普拉斯矩阵的特征向量时出现非常耗时的情况，所需的时间复杂度是O（n3），导致当对大规模数据进行聚类的情况下会出现明显的速度缺陷。其次，传统的谱聚类最终k-means仍是对N个数据进行聚类运算，在处理大规模数据时是无法被接受的，导致传统的谱聚类只能适用于较小规模的数据集。本文设计了一种基于图滤波的快速谱聚类算 法（Fast Spectral Clustering via Graph Filter⁃ing，FSCGF），通过对随机信号的滤波技术近似表示出特征向量之间的欧式距离，并且在滤波的基础上利用特征值计数法避免了滤波过程中对矩阵的对角化，加快了聚类速度。同时利用抽样矩阵对原数据抽样减小数据规模，实现了在小规模上运行k-means，并通过重构优化的方式保证了对原始数据聚类结果的还原，提升聚类速度并保证了聚类的精度。

相比于传统的谱聚类，本文在假设已经给出拉普拉斯矩阵的情况下，主要特点和贡献如下：

（1）引入了一种基于图滤波的快速谱聚类的框架，通过特征值计数法估算特征值，利用估算的特征值生成低通滤波器对图上的随机信号进行滤波，克服了对拉普拉斯矩阵特征分解的难题，然后将这些滤波后的信号作为特征向量进行聚类。

（2）设计了一种基于图滤波的快速谱聚类算法，该算法利用抽样重构的方法以降低kmeans聚类的计算复杂度，使得计算时间比传统谱聚类更快。

（3）在多个数据集上进行了实验验证，实验结果表明，相对于传统的谱聚类算法，设计的FSCGF算法在效率和精度上有所提高。同时通过优化处理，极大地降低了近似误差对实验的影响，为数据的聚类课题提供了新的思路。

本文的结构设置如下：首先在第1节介绍了相关工作，接着在第2节中对设计的符号进行了总结，再对文中涉及的相关定义以及方法做了总结，然后在第3节中介绍了FSCGF算法，用框架图总结算法步骤，针对算法中的重要步骤进行详述，随后在第4节证明了所提算法的鲁棒性并计算了总的计算时间，在第5节用实验进行了测试，呈现了结果，并且在最后一节做出了总结以及展望了未来的工作。

1 相关工作

谱聚类是传统聚类算法中受到广泛应用的一种聚类算法，比起k-means算法，谱聚类对不同数据的适应能力更强，实际应用的范围也很广，聚类效果也更加好，同时其计算复杂度也不高，能在很快的时间内完成聚类操作，并且算法易于实现。因此，在对实际问题的聚类过程中，谱聚类通常会得到优先考虑。

最初在图论中演变出了谱聚类算法，但由于其聚类的高效性，所以在聚类中得到了广泛的应用。其主要思想是将数据看作点，点与点之间能通过边进行连接，构成一张图ɡ，比较近的点与点之间的边的权重比较大，而比较远的点与点之间的边的权重就比较小，谱聚类的目标就是对这张图进行切图操作，让子图之间的边的权重尽量的小，而子图内的边的权重尽量大，最终得到聚类结果。

谱聚类的构图方法中主流的方法有三种，分别是ε-邻近法、k-近邻法和全连接法，本文参照的谱聚类使用的是全连接法，因为点与点之间的权重值都大于0，在全连接法中可以使用不同的函数来定义边的权重，在实际应用中高斯函数是最普遍的，公式如下：

Ncut切图和RatioCut切图类似，只是把上式的分母|Ai|换成 vol（Ai），由于子图中点的个数多并不代表子图的权重就一定大，所以切图过程中基于权重的切图也就更合理些。

上述方法只是解决了谱聚类过程中的一般步骤，在实际应用中谱聚类还是会遇到一些问题，其三个主要的计算缺陷包括：邻接矩阵A的建立、拉普拉斯矩阵L的特征分解和k-means运算。如何创建相似度矩阵A，使其能更准确地反应点与点之间的关系，并且使较相似的点与点之间的相似度更高，不相似的点与点之间的相似度更低，是谱聚类需要解决的问题。虽然高斯相似矩阵对计算两点间的相似度取得了一些成功，但是参数σ的选取却有局限性。因为需要预先选取几个σ的值，分别对不同的σ值执行谱聚类，将最好的结果作为最终σ的选择，这种做法降低了人工的选择，但是却增加了时间复杂度。由相似度矩阵得到拉普拉斯矩阵之后，对特征向量的选择也是一个问题，也就是拉普拉斯矩阵的特征分解问题。通常情况下是直接选择拉普拉斯矩阵的前k个特征向量，但是其复杂的计算过程和计算时间在很大程度上减低了谱聚类算法的实用性。最终在执行kmeans过程中也需要解决数据量大的情况，如果数据量N或者聚类的数目k很大的话，也会降低谱聚类的计算时间。这些瓶颈引起了学者们的注意，他们提出了很多解决这些瓶颈的思路，例如核方法［10-11］、采样方法［12-13］、近似表示法［14］、自适应采样法［15］。其中一些学者提出的理念是解决特征分解的瓶颈，这些方法都以快速计算特征向量作为目标［16-17］。但k-means仍然应用于N个特征向量。其他的一些学者提出的方法则是旨在降低k-means的复杂度［18-19］，没有回避特征分解和N的数目太大的问题。

本文受新兴领域图信号处理的启发［20］，为了解决SC的瓶颈中的后两步，详细地介绍了一种基于图滤波的快速谱聚类算法（FSCGF）。假设给出了原始数据集｛x1，x2，…，xN｝，该方法有两个主要部分，首先在图上滤波O（log k）个随机信号，将其作为伪特征向量进行聚类，从而避免了对拉普拉斯的特征向量的复杂计算，主要介绍了如何将滤波器与聚类算法进行结合。其次使用信号抽样理论来减少k-means的计算规模，降低算法的时间复杂度。运用此方法后，聚类的复杂度降低到O［k2log2（k）］，而SC的时间复杂度是O（Nk2）。所以这种方法很容易扩展到大型数据集，这在后面的真实数据集上进行了证明。FSCGF提出的方法总结：通过特征值计数方法，估算算法中所需的λk，利用λk生成低通滤波器。利用低通滤波器对信号滤波产生一个伪特征向量集，从整个集中抽取O（k log k）个样本，对抽取的子集执行k-means聚类算法，加快聚类速度，得到聚类结果。最后将得到的聚类结果进行重构，得到原数据的聚类结果。

2 FSCGF的相关定义和方法

2.1 基本符号

本文使用的符号及含义见表1。

表1 基本符号Table 1 Basic symbols

2.2 FSCGF的相关定义

定义1（图信号）设Ѵ是图ɡ的顶点集，图信号f是Ѵ上的一个函数，向量形式下f=(f(v1)，f(v2)，…，f(vn))T，任何图信号 f都可以用基信号的线性组合表示。

其中 ϑi是 ϖi的系数，系数|ϑi|的大小代表 ϖi在信号f中的频数［21］。由公式1可知，基信号ϖi的平滑度由特征值λi来衡量，频率较低的（特征值较小）基信号在图上更平滑。

因此，一个平滑的图信号f主要由低频基信号组成［22］，而图滤波的主要思想是，根据相应的数据关系图，设计合适的图滤波器，用此滤波器对图信号进行滤波，产生新的平滑的信号。一个线性的图滤波器可以表示为矩阵形式H∈RN×N，那么对图信号f的滤波操作就可以写作Hf。

定义2（图的傅里叶矩阵）标准化后的拉普拉斯矩阵通常表示为L=I-D-1/2AD-1/2，其中I是N维的单位矩阵，D是对角矩阵，且D满足 Dii= ∑j≠iAij［23］。从上述的描述中就可知，L是实对称半正定矩阵，设U=(u1|u2|…∣uN)∈RN×N是特征向量的标准正交基，那么L可以表示为L=UΛUT，其中Λ∈RN×N是特征值构成的对角矩阵，满足：0=λ1≤λ2…≤λN≤2。类比以上对拉普拉斯矩阵的描述可以看出，L=UΛUT是经典的傅里叶模式，特征值是频率的平方，U的列可以看作图的傅里叶模态［24］。其他类型的傅里叶矩阵也是存在的，但是FSCGF为了体现图信号处理与谱聚类之间的关系，使用基于拉普拉斯的傅里叶矩阵显得更合适。

定义3（图滤波）对图信号x进行图傅里叶变换，可写作x̂=UTx。给定一个定义在［0，2］上的滤波函数h，由这个函数生成的图滤波器H∈RN×N可以被表示为 H=h（L）=Uh（Λ）UT，其中 h（Λ）=diag（h（λ1），h（λ2），…，h（λN））是特征值构成的对角矩阵，结合傅里叶变换，被滤波后的信号x就可以写作Hx［25］。在FSCGF中，用 hλc表示理想的低通滤波器，且 hλc满足以下条件，对于任意的 λ∈[0，2]，

这样就可以通过上式用hλc生成图滤波器 Hλc［26］。

2.3 FSCGF的相关方法

谱聚类算法输入数据是数据点（x1，x2，…，xN）的集合，参数 k是聚类的簇数［28］。算法步骤如算法1。

在算法1中需要先利用公式4提取U的每一行，得到特征向量 fi，其中 fi∈Rk，如果把 fi定义为每个节点的特征向量，那么每个节点就看作是一个 k维的向量［29］。

通过计算特征向量fi与fj之间的欧氏距离Pij，再运行k-means算法就可以得到需要的簇。但是对于拉普拉斯矩阵L，如果数据量N过大，对L进行特征值分解的计算过程是非常复杂且耗时的，所以本文提出了一种基于图滤波的快速谱聚类算法，该算法对如何避免特征值分解进行了详细的描述，克服了谱聚类过程中的第二个瓶颈，加快了聚类的速度。

3 基于图滤波的快速谱聚类算法

首先通过图1对算法的整体框架进行了介绍，然后通过描述以下的三个方面对算法的主要步骤进行了讲解。

（1）特征值计数估算λk，是构造滤波器的必要步骤。

（2）抽样与重构，减少聚类的时间复杂度并还原原聚类结果。

（3）抽样数量的选择，确定所需的抽样数目并能正确的还原聚类结果。

FSCGF克服了谱聚类中的两个难点，分别是拉普拉斯矩阵的特征值分解和k-means在面对大规模数据时聚类太耗时的情况。首先，如果在利用公式3中的低通滤波器对随机信号进行滤波，那么需要先通过对拉普拉斯矩阵进行对角化，计算L的前k个特征向量，得到滤波所需的 hλk（λk=λc），但这样会使算法的时间复杂度变慢，所以在公式3中需要克服这个问题，FSCGF采用特征值计数法，先确定区间［a，b］，然后使用特征值计数的方式估计［a，b］中的特征值数量，通过多次迭代最终确定所需的λk，再利用所得的λk生成滤波器，过滤随机信号得到每个点对应的伪特征向量τ。总之，先通过用低通滤波器H的多项式近似H͂，快速的过滤一些随机信号来形成伪特征向量，用这些伪特征向量代替特征向量，从而避免了L的特征值分解。在克服第二个难点时，需要对N个通过滤波生成的伪特征向量的n个伪特征向量进行采样，然后执行k-means运算，将其对应的n个节点聚类为k个簇，并将这些结果插回到完整的图中进行重建，得到预期的聚类效果。在下面的小节中解释了为什么这些结果是适用于聚类的，并且只要对O（k log k）个特征进行抽样就够了。但是需要注意的是，要将数据聚类成k个簇，至少需要k个样本。图1展示了FSC⁃GF的框架。

图1 本文方法的主要框架Fig.1 Main framework of the proposed method

基于图滤波的快速谱聚类算法步骤见算法2，上述过程中，FSCGF还需要特征值计数以及抽样和重构步骤的详细介绍。

3.1 特征值计数估算λk

特征值计数的主要任务是计算分布在区间［a，b］中的特征值的个数，这样才能有效地估算算法中所需要的λk。而估算［a，b］中特征值的个数的最简单的方式就是求解FDFT的两个因式分解，设为Z-aI和Z-bI，其中F是一个单位下三角矩阵，D是对角矩阵，Z是埃尔米特矩阵，不过当Z很大时，需要耗费的时间也会变得很多。为了采用更加快捷的方式，可以采用特征值投影轨迹近似的方法，如公式5所示：

从公式5中可以看出，投影P的特征值要么是1，要么是0，所以P的迹tr（P）就等于区间［a，b］上的特征值的个数，为了更加简化计算过程，可以用随机迹估计E（sTPs）近似表示P的迹，那么P的迹就可以用随机向量的乘积来表示，并计算其平均值来估算tr（P），如公式6所示：

通过对sk进行归一化操作，最终［a，b］中的特征值个数就可以通过公式7计算得出：

3.2 抽样和重构

为了从n个聚类结果中成功的恢复aj通常通过二次规划公式9实现：

公式9能通过公式10求解，其中G是抽样矩阵，γ代表一个正则化参数，g（L）是一个正的非减多项式。

其中 q2（ηi-ηj）是 ηi与 ηj之间的欧式距离的平方，σi表示一个范围内的大小，写作 σi=q2（ηi，ηb），ηb与 ηi相隔 b 个伪特征向量，并且 b 的值是手动输入的一个参数，那么重构后的拉普拉斯矩 阵 就 可 以 表 示 为 ：L͂=I-D͂-1/2A͂D͂-1/2（D͂仍然是A͂行的和构成的对角矩阵）。那么FSCGF的重构目标函数就可以写作公式12：

这样就省去了计算g（L）的步骤，同样起到了优化算法时间复杂度的目的。

3.3 抽样数量

其中x表示Uk空间中的向量，那么需要采样的数目n满足公式14：

4 算法性质分析

4.1 算法的鲁棒性分析

4.2 算法的复杂度分析

定理2（算法的复杂度）FSCGF的总时间复杂度为O(k2log2k+mN(logN+k))，其中N是总样本的个数，k是需要聚成的簇数，m是高阶近似的阶数。

证明 算法2的主要计算过程在1，4，6，7的过程中。首先，过滤图信号的时间复杂度是O（ml）（l是边的个数），因此算法2的步骤1在算法3中给出伪代码，每次迭代时间复杂度为O（ml log N），而当d=log n时，步骤4的时间复杂度为O（ml log n），步骤 7需要用到gλk（λ）=1-hλk（λ）的多项式逼近，如果用共轭梯度法或梯度下降法来求解时，步骤7在迭代中进行一次滤波操作，所以步骤7的时间复杂度为O（mlk）。另外，k-means在每次迭代过程中将r维的p个特征向量聚类成k个类的时间复杂度是O（kpr）。因此，如果mp=n并且r=d=O（log n），那么步骤6的时间复杂度就是O（kn log n）。FSCGF 的时间复杂度为 O［ml（log N+log n+k）+kn log n］。实际应用中，对于稀疏图，l是等于O（N）的。对于抽样的个数满足n=O（k log k）的情况，FSCGF的时间复杂度就应该是O（k2log k+mN（log N+k））。

相比之下，SC的k-means在每次迭代过程中的时间复杂度是O（N k2），在大多数情况下，SC的时间复杂度和FSCGF比起来会大很多，除此之外，SC还包括计算L的前k个特征向量的时间复杂度，所以，对于较大的N或k，FSC⁃GF比SC更快。接着，在后面的实验中证实了FSCGF在时间复杂度方面确实比SC更优。

文章提出的FSCGF具有以下的几个特点：

（1）用信号滤波技术生成伪特征向量代替了拉普拉斯矩阵L的特征分解，使算法在大型数据集上降低了运算时间。

（2）通过抽样技术，减少了k-means的运算数据量，进一步的降低了算法的计算时间，更加适用于大型数据的处理。

（3）公式12使用局部尺度的自适应系数γ降低了误差，并且该优化方法使得聚类恢复的精度更高。

5 实验

5.1 实验环境

FSCGF在四个不同类型的真实数据集中进行测试，真实数据集分别是事物数据集（COIL20）、声音数据集（TED-LIUM）、字符数据集（USPS）和生物医学数据集（Cardiac MRI），图2为4种数据集的示例图。

图2 实验中使用的COIL20（a）、TED-LIUM（b）、USPS（c）和Cardiac MRI（d）数据集的实例图片Fig.2 Example images of COIL20(a),TED-LIUM(b),USPS(c)and Cardiac MRI(d)datasets used in the experiment

5.1.1 事物数据集

COIL20数据集是彩色图片集合，总共有1 440张图像，每幅图像后间隔5°再拍摄下一张图像，总共对20个不同的物体从不同角度进行拍摄，每个物体拍摄了72张图像。每张图像都处理成128×128大小。

5.1.2 声音数据集

TED-LIUM是一个人类语音数据集，包括TED演讲音频和对应讲稿。其中一共录制了包括8 671段演讲录音和对应的演讲稿。

5.1.3 字符数据集

USPS是美国邮政数据集，图片中展示的0，1，…，9数字用于手写数字识别，都是8位灰度图像，数据集中总共包含了9 298个实例。

5.1.4 生物医学数据集

Cardiac MRI是心脏左心室外膜和心内膜的图像，记录了心脏病患者的医疗影像，数据集中总共包含了患者的9 298张图像。

为了证明FSCGF比现有的聚类算法具有更好的准确性，FSCGF对现有的几种聚类算法进行了比较，并且针对不同的数据集进行了多次实验。表2是几种真实数据集的介绍。

表2 数据集Table 2 Datasets

5.2 评估标准

为了有效地评估实验的结果，使用的度量指标分别是准确度（Accuracy，ACC）、调整兰德系数（Adjusted Rand Index，ARI）和标准化互信息（Normalized Mutual Information，NMI）。

5.2.1 ACC

上述公式中，π是N个样本的排列，Xt和X是聚类正确的样本和所有需要测试的样本，如果第i个簇中包含了样本点j，那么它们的第i个条目的值就是1，反之为0。ACC指标是在计算所有样本中聚类结果正确的样本的比例。

5.2.2 ARI

ARI是用来评判两个数据分布之间的一致性的，ARI的定义表示为如下公式：

上述公式中，a00表示把不同的类型的样本点分配给不同的集合，a01表示把不同类型的样本点分配给相同的集合，a10表示把相同的类型的样本点分配给不同的集合，a11表示把相同的类型的样本点分配给相同的集合。

5.2.3 NMI

标准化互信息（NMI）指标通常是用来测量不同的聚类结果的相似度，并且计算它们聚类正确的权重。如果A是真实的聚类集，而A*是根据聚类算法聚类得到的聚类集。那么互信息MI的定义表示为如下公式：

上述公式中，p（ai）和 p（aj）分别是 ai和 aj中的随机选择的数据点，p（ai，aj）表示数据点同时属于簇ai和aj的联合概率，NMI的定义可以表示为如下公式：

在上述公式中，H（A）和H(A*)分别表示A和A*的熵。在指标的性能判定中，NMI的值越大，表示聚类的性能越好。

5.3 比较方法

为了评价所提方法的聚类性能，将FSCGF算法和以下的算法进行了比较：

（1）SC：谱聚类算法主要思想是把样本看作空间中的点，距离远的点之间的权重较低，近的较高，通过对所有样本组成的图切图，使得一个簇内的边权重尽可能得高［30］。

（2）基于标记表示的大规模谱聚类（Land⁃mark based Spectral Clustering using k-means，LSC-K）：是由LSC衍生而出用于解决大规模数据的一种聚类算法［31］。

（3）k-means的大规模聚类（Compressed kmeans，CKM）：用于快速大规模聚类，通过将数据压缩成二进制码减少存储，加快聚类速度［32］。

（4）最小二乘回归用于子空间聚类（Least Squares Regression for Subspace Clustering，LSR）：子空间聚类算法，采用最小二乘回归进行鲁棒高效的子空间分割［33］。

5.4 实验设计

为了证明FSCGF能够准确有效地对不同量级的样本点进行准确的聚类，在不同的真实数据集上对FSCGF进行了测试，从实验角度证明FSCGF的鲁棒性，即使存在噪声FSCGF也能很好地对原始数据进行聚类，接下来与现有的几种聚类算法进行了比较，分别使用了ACC、NMI和ARI，证实了FSCGF的可行性以及优越性。与传统的谱聚类算法类似，结合框架中的内容，FSCGF还是用高斯相似度方法对数据进行了初始化，同时对其生成的拉普拉斯矩阵进行归一化处理，然后再根据框架中的滤波以及抽样重构步骤，完成了对数据的聚类操作。对于数据集的设置，从表2中可以看出，FSCGF根据其聚类的数量设置所有数据集中的类别数，并在合理范围内对实验参数进行手动调整以达到较好的实验结果。

5.5 参数分析

如何对不同的数据集选用最优参数是个一直未得到解决的问题。FSCGF需要用到n、d、m和γ。其中n=t k log k和d=o log n用于抽样数量和需要滤波的信号的个数，m和γ用于高阶近似的阶数和优化算法的正则化参数。为了充分说明参数敏感性，对于每个数据集都采用固定参数m和γ，并重点观察参数n在可变范围内的性能变化，因为n是FSCGF算法中最关键的一项，且d由n决定。经过一系列的选择，最终确定当m=50，γ=10-3时能获得最优解。在t的可选范围内随机选择一组测试集，然后选择测试集中不同的值进行测试，最终结果如图所示。将 t的可选范围设为｛0.5，1，1.5，2，2.5｝是为了满足公式14中对n的限定，图3展示了在不同数据集上不同参数值的聚类精度。图中可以看出，在不同的数据集上，最优参数是不同的，对于簇数较小的数据集，t的选择会较大，簇数较大的数据集，t的选择会较小。

图3 四个不同的数据集上，FSCGF相对于参数n中系数t的性能检测Fig.3 Performance test of FSCGF relative to the coeffi⁃cient t in parameter n on four different datasets

6 分析与讨论

图4展示了FSCGF在真实数据集上的实验结果，相关讨论如下。

图4 各个数据集运行不同算法得到的计算时间结果Fig.4 The computation time required by different algorithms on different data sets

表3 不同方法在不同数据集上的准确度（%）Table 3 ACC(%)of different methods in different datasets

表4 不同方法在不同数据集上的标准化互信息（%）Table 4 NMI(%)of different methods in different datasets

表5 不同方法在不同数据集上的调整兰德系数（%）Table 5 ARI(%)of different methods in different datasets

7 结论

本文提出了一种基于图滤波的快速谱聚类算法FSCGF。FSCGF的特点在于克服了传统谱聚类中对拉普拉斯矩阵的特征值分解和对于较大的N或k执行k-means计算时间长的问题，可以有效地对大规模的数据集进行快速的聚类，同时对聚类的性能指标也有一定改善。FSCGF与传统的谱聚类不同，利用特征值计数方法估算特征值并产生对应的滤波器，对随机信号滤波形成新的伪特征向量来代替原始的特征向量，从而解决了特征分解的问题，再利用抽样重构的原理降低了大规模数据集的样本点数量，有效地提高了聚类的速度，保证了聚类的准确度。最后针对不同的真实数据集（Face、Voice、Word和Biomedical类型的数据集）测试了FSCGF。从实验结果可以得知，FSCGF比传统的谱聚类和一些其他的聚类算法更加准确。为了得到更好的聚类效果，未来可以采用模型选择的方法对文中的参数进行调整；将图的傅里叶转换与FSCGF相结合，加快聚类的速度。