二分k-means锚点提取的快速谱聚类.pdf

Computer Engineering and Applications计算机工程与应用2023，59（16）聚类是通过对相似数据进行分类而获得有价值的信息1。大部分聚类算法通过欧氏几何度量数据相似性2-3，如常见的k-means通常用于进行快速聚类，但它局限于凸分布的数据集，对于一些非凸数据集常常很难有效地描述。相比之下，谱聚类（spectral clustering，SC）是一种基于图的聚类技术，能够有效利用数据的图和流形信息处理非凸形状的簇，与k-means相比，它能够处理更复杂的数据结构，但由于求解特征向量时计算复杂度高而无法直接处理大规模数据。因此，构建解决大规模数据的谱聚类算法成为研究的难点。二分k-means锚点提取的快速谱聚类罗兴隆1，贺兴时1，杨新社21.西安工程大学 理学院，西安 7106002.密德萨斯大学 科学与技术学院，伦敦 NW4 4BT摘要：光谱聚类（spectral clustering，SC）由于在无监督学习中的有效性而受到越来越多的关注。然而其计算复杂度高，不适用于处理大规模数据。近年来提出了许多基于锚点图方法来加速大规模光谱聚类，然而这些方法选取的锚点通常不能很好地体现原始数据的信息，从而导致聚类性能下降。为克服这些缺陷，提出了一种二分k-means锚点提取的快速谱聚类算法（fast spectral clustering algorithm based on anchor point extraction with bisectingk-means，FCAPBK）。该方法利用二分k-means从原始数据中选取一些具有代表性的锚点，构建基于锚点的多层无核相似图；然后通过锚点与样本间的相似关系构造层次二部图。最后在5个基准数据集上分别进行实验验证，结果表明FCAPBK方法能够在较短的时间内获得良好的聚类性能。关键词：二分k-means；二部图；锚点图；谱聚类文献标志码：A中图分类号：TP181doi：10.3778/j.issn.1002-8331.2205-0036Fast Spectral Clustering Based on Anchor Point Extraction with Bisectingk-meansLUO Xinglong1,HE Xingshi1,YANG Xinshe21.College of Science,Xi an Polytechnic University,Xi an 710600,China2.College of Science and Technology,Middlesex University,London NW4 4BT,UKAbstract：Spectral clustering（SC）has received increasing attention due to its effectiveness in unsupervised learning.However,due to its high computational complexity,it is not suitable for processing large-scale data.In recent years,manyanchor points graph-based methods have been proposed to accelerate large-scale spectral clustering.However,the anchorpoints selected by these methods usually cannot well reflect the information of the original data,which leads to the degra-dation of clustering performance.To overcome these shortcomings,a fast spectral clustering algorithm based on anchorpoint extraction with bisectingk-means（FCAPBK）is proposed.The method uses bisectingk-means to select some repre-sentative anchor points from the original data,then constructs a multi-layer kernel-free similarity graph based on anchorpoints,and constructs a hierarchical bipartite graphs through the similar relationship between the anchor points and thesample.Finally,experiments are carried out on five benchmark datasets,and the results show that the FCAPBK method canobtain good clustering performance in a short time.Key words：bisectingk-means;bipartite graphs;anchor points;spectral clustering理论与研发基金项目：国家自然科学基金（12101477）；陕西省自然科学基础研究计划（2020JQ-831）。作者简介：罗兴隆（1997），男，硕士研究生，主要研究方向为聚类分析、智能计算，E-mail：；贺兴时（1960），男，硕士，教授，研究方向为优化算法及应用、数理统计等；杨新社（1965），男，博士，英国国家物理实验室高级科学家，主要研究领域为数学建模、工程优化以及科学、数值计算方法等。收稿日期：2022-05-05修回日期：2022-06-13文章编号：1002-8331（2023）16-0074-08742023，59（16）近年来，提出了许多基于锚点图的方法，用于处理谱聚类的大规模数据集，如可扩展的半监督学习4-5、多视图大尺度光谱聚类6、大规模光谱聚类降维7-9以及基于二部图的谱聚类10。与传统的图方法不同，基于锚点图的方法根据锚点建立与原始数据点之间的邻接关系。Zhang等人11首先建议使用一组锚点来对数据流形进行有效的低秩近似，并给出一个信息损失最小的模型。Liu等人12提出了锚点图模型，并将它引入到基于图的学习任务中。Wang等人13随后提出了一种改进算法，显示了更好的性能和计算效率。与传统的图相比，这些基于锚点图的方法可以大大降低图构造的复杂性。Fowlkes等人14采用经典的Nystrm方法加速了特征分解，并应用于谱聚类，得到了处理大数据的ASC算法。该方法使用随机抽样，虽然简单快速，但其不确定性在很大程度上影响了聚类结果，且性能取决于样本集的质量。Li等人15利用随机低秩矩阵近似算法提出了一种可扩展的 Nystrm 方法，对从输入图中采样的列集的内子矩阵进行近似奇异值分解（singular valuedecomposition，SVD），进一步加快了该算法的分解速度。但这类方法占用内存大，易丢失小簇且数值稳定性不高。Shinnou等人16将原始数据集替换为相对较少的数据集，并对较小数据集对应的邻接矩阵进行后续操作。Yan等人17提出了基于均值的近似光谱聚类（k-means-based approximate spectral clustering algorithm，KASP）方法。该方法首先对集群的数据集执行k-means；然后，将传统的光谱聚类应用于各聚类中心，数据点被分配给集群作为其最近的中心。Chen等人18和Liu等人19基于一些数据点快速收敛到真实嵌入，引入了一种顺序缩减算法，从而使早期停止策略加速分解。然而，这类方法由于k-means的局部收敛，若某一质心点聚类错误，则该质心点附近的点均同样聚类错误。本文针对以上选取锚点算法的不足，提出一种二分k-means锚点提取的快速谱聚类算法（fast spectral clus-tering algorithm based on anchor point extraction withbisectingk-means，FCAPBK）。利用二分k-means从原始数据中选取一部分具有代表性的锚点。通过锚点和数据点构造多层锚点图，然后利用原始数据点和最后一层锚点构造二部图，使多层锚点图构成一个层次二部图，该方法既可以使选取到的锚点具有代表性，也可以使谱聚类的复杂度大大降低。最后，对相似图进行谱聚类分析，并在不同实验数据集上验证最终聚类效果。1相关工作1.1谱聚类算法设X=x1,x2,xnTRnd表示n个样本的d维数据集矩阵，其中xiRd表示数据集X中的第i个数据点，将每个数据点xi看作是亲和图上的一个顶点，每个点和点之间的边表示邻接关系。对于n个任意的点i和点j,wij表示xi和xj之间边的权重，W=wijRnn表示亲和图的邻接矩阵。wij以高斯核函数表示如下：wij=e-xi-xj2222,xiKNN(xj)or xjKNN(xi)0,otherwise（1）其中，xi-xj22是xi和xj欧氏距离的平方，是核参数，KNN(xi)表示样本xi的k近邻集合。设L表示图拉普拉斯矩阵，其定义为L=D-W。归一化后的图拉普拉斯矩阵为：L=D-12LD-12=I-D-12WD-12（2）式中，D是一个对角矩阵，第i个对角线上元素为di=jwij。因此，归一化谱聚类20的目标函数被定义为：minFTF=Itr(FTLF)（3）其中，tr()为矩阵的迹，FRnc表示数据集的类指示矩阵。由于F的元素是离散值，求解方程（3）是NP难题。为了使该问题得到解决，通常将矩阵F从离散值松弛为连续值。通过对L的特征值分解，使其转化为L的c个最小特征值对应的特征向量，得到由特征向量组成的松弛连续解。然后，利用k-means等聚类方法来计算离散解。谱聚类步骤如下：步骤 1 数据矩阵X=x1,x2,xnTRnd，生成图的邻接矩阵W和对角矩阵D；步骤2 归一化普拉斯矩阵L=I-D-12WD-12；步骤3 生成L的最小c个特征值及其对应的特征向量；步骤4 将c个特征值对应的特征向量通过k-means聚类。1.2基于二分k-means选取锚点近年来，在大规模数据集中基于锚点的方法21有了广泛的应用，不仅在基于图的方法中降低了计算成本，而且获得了良好的效果。基于锚点的方法是从原始数据点中选取m(mn)个代表原始数据结构的代表点，称为锚点。锚点的选取方式通常有两种：一种是从原始数据中随机选取锚点，随机选取虽然快速、简单，但得到的锚点是随机的，不能很好地体现原始数据的结构；另一种是采用k-means选取锚点，使用k-means得到原始数据的中心，使用得到的中心点作为锚点。该方法虽然得到锚点比随机选取有代表性，但由于k-means对数据输入顺序敏感而且仅考虑数据的空间局部信息，易选取过多的噪声成为锚点。针对这些问题，本文引入二分k-means算法来选取锚点，不但对噪声鲁棒，对数据输入顺序不敏感，而且通罗兴隆，等：二分k-means锚点提取的快速谱聚类75Computer Engineering and Applications计算机工程与应用2023，59（16）过每次选择误差和SSE最小的簇进行划分，在一定程度上能避免选取到噪声点。1.2.1二分k-means算法k-means是一种基于划分方法的聚类，然而传统k-means算法对噪声点和离群点很敏感。针对这一局限性，很多国内外学者都做了相关的研究。左进等人22通过计算数据点的紧密性值，选取不是异常值的初始聚类中心，使聚类效果在全局范围内是最佳的。Xia等人23通过搜索邻居簇和将查询到的簇划分为稳定的和活跃的区域来加速标准k-means算法。Duan等人24提出了一种基于大距离和高密度的中心点初始化方法，用距离加权平均的倒数表示样本密度，选择距离较大、密度较高的数据样本作为初始聚类中心。Ding等人25提出了一种Yinyangk-means算法，通过在初始阶段对中心进行聚类，有效地保持数据点和中心点之间的上下界，避免了不必要的距离计算。有学者提出了二分k-means聚类算法，该算法减少了聚类相似度的计算量，从而能加快k-means执行速度。在选取聚类中心时进行了优化，因此能较好地克服对初始中心敏感的问题，有着相对稳定的聚类性能。二分k-means算法26具体步骤如下：首先，将数据集的所有样本初始化为同一个簇，计算该簇数据集的质心;其次，使用k-means算法将该簇一分为二，以最小化聚类代价函数（误差平方和）为选择依据，在所得到的簇中选择一个簇进行一分为二划分;不断重复以上步骤，直到选出给定的k个簇作为终止条件。算法1 基于二分k-means算法输入：数据集矩阵X=x1,x2,xnT，聚类簇数k。输出：簇划分C=C1,C2,Ck。1.将所有数据看作一个簇，计算簇中心（数据点的质心）2.while簇中心个数hk（6）其中，k为近邻数据点的数量。由以上计算表达式可以得到无核邻近分配27方法的以下优势：（1）式中求解到的邻接矩阵是自然稀疏矩阵，而稀疏矩阵对于基于图学习任务的计算效率很高。（2）通过表达式计算亲和度只涉及一个近邻参数k，此参数是一个整数，易于调整，且表达式只涉及基本的简单运算。而采用LLE和稀疏编码等方法计算亲和度，涉及到计算高斯函数和其他参数。步骤1 二分k-means步骤2 锚图构造锚点样本点图1选取锚点和构造二部图的过程Fig.1Process of selecting anchor points andconstructing bipartite graphs762023，59（16）（3）数据点的亲和度具有伸缩不变性，不会因为数据样本的扩大、缩小影响其度量尺度。数据点间的距离特征与它们之间的亲和度也具有一致性。图2为锚点和数据点的锚点图构造过程。图中h61、h62和h63是第6个数据点与第1、2、3个锚点的邻接关系（x1,x2,x7是数据点，u1、u2、u3是锚点），且h61+h62+h63=1。2层次二部图的谱聚类分析2.1层次二部图的构造在半监督学习6中，设G=X,U,E表示基于锚点的层次图，其中XRnd为数据集矩阵，U为锚点集，E为相邻层间边邻接矩阵的集合。假设原始数据点X用底层L0表示，其余的锚点层是由多个锚点集U组成的La(a=1,2,h)表示，其中Ua(UaRmad,a=1,2,h)的大小逐渐减小，即m1m2mh，ma是La中的锚点个数。E=H0,1,H1,2,Hh-1,hRnm1,m1m2,mh-1mh,其中Ha-1,a是La-1和La数据点之间的邻接矩阵。在此引入无监督学习中的层次二部图28，由文献28可知，层次二部图由原始数据层L0和最后一层Lh构造。因此，二部图的邻接矩阵12可以写为：W=0HHHTH0（7）其中，WR(n+mh)(n+mh)是邻接矩阵，0表示全 0矩阵，HHRnmh表示原始数据点层L0到最后一层锚点Lh之间累积的邻接矩阵。接下来，使用第1.3节的方法计算从Lh到Lh-1层间的邻接矩阵Hh,h-1，从而得到邻接矩阵：HH=H0,1H1,2Hh-1,h（8）设FG表示Lh中锚点数据集的类指标矩阵，Fx为L0中数据点的类指标矩阵。利用上述累积6邻接矩阵，可以得到从密集L0到稀疏Lh的类指标矩阵28：Fx=H0,1H1,2Hh-1,hFG=HHFG（9）接下来，通过邻接矩阵W求得数据集的对角矩阵D为：D=Da00Db（10）其中，DaRnn和DbRmhmh是一个对角矩阵，Da的对角元素是H的行和，Db的对角元素是H的列和。对于HH中的向量，由行的归一化hTi1=1（1是全为1的列向量）可知，Da=In（In是nn阶单位矩阵），故D可以写为：D=In00Db（11）因此，拉普拉斯矩阵L=D-W（D为对角矩阵）为：L=In00Db-0HHHTH0=In-HH-HTHDb（12）由归一化后的L=I-D-12WD-12可知：L=In00D-12bIn-HH-HTHDbIn00D-12b=In-HHD-12b-D-12bHTHIm=I-0HHD-12bD-12bHTH0（13）其中，Im是mm阶单位矩阵。2.2谱聚类分析由经典谱聚类可知，基于层次二部图28的谱聚类的目标函数29定义为：minFTF=Itr(FTLF)（14）其中，tr()表示矩阵的迹，I是单位矩阵，F=FxFG是所有数据点的类指标矩阵。由谱聚类的相关求解知识可知，对L的特征值分解即为（14）的最优解，由归一化的L可得目标函数为：minFTF=ItrFTI-0HHD-12bD-12bHTH0F（15）接下来，令M=HHD-12b，因此，目标函数（15）可以写成如下：minFTF=Itr FTI-0MMT0F=maxFTF=ItrFT0MMT0F=maxFTxFx+FTGFG=ItrFxFGT0MMT0FxFG=maxFTxFx+FTGFG=Itr(FTxMFG)（16）接下来，通过使用奇异值分解方法对M进行分解，得到F的松弛连续解，令URnn为左奇异向量矩阵、Rnmh为奇异值矩阵、VRmhmh为右奇异向量矩阵。因此，矩阵M的奇异值分解（SVD）可以写成如下：M=UVT（17）最后，通过k-means聚类方法进行离散化处理，计算出离散类指标Y。h63h61h62x2x1x4x3x6x5x7u2u1u3图2锚点图的构造Fig.2Construction of anchor points graph罗兴隆，等：二分k-means锚点提取的快速谱聚类77Computer Engineering and Applications计算机工程与应用2023，59（16）算法2 FCAPBK算法输入：样本数据集XRnd，类簇数c，每一层锚数m1,m2,mh，近邻数k。输出：c个类簇的标签。1.由算法1产生m个锚点2.根据式（6）得到相邻层邻接矩阵H0,1,H1,2,Hh-1,h3.根据式（8）得到矩阵HHHH=H0,1H1,2Hh-1,h4.通过式（7）计算多层二部图的邻接矩阵W=0HHHTH05.通过对矩阵M=HHD-12b进行奇异值分解，得到Fx和FG的松弛连续解6.利用k-means聚类方法获得最终c类指标Y2.3时间复杂度分析给定n个样本数据集XRnd,类簇数c,L1到Lh层中的锚点数m1,m2,mh，FCAPBK的计算复杂度由以下五部分组成：（1）通过从L1层到Lh层的二分k-means选择得到m个锚点的计算复杂度为O(nm1dt+m1m2dt+mh-1mhdt)，由于nm1mh，可近似为O(nm1dt)。（2）从H0,1到Hh,h-1的矩阵需要的计算复杂度为O(d(nm1+m1m2+mh-1mh),由于nm1mh,计算复杂度可以近似为O(m1nd)。（3）由于nm1mh，故HH的计算复杂度可以近似为O(nm1mh)。（4）通过对矩阵M进行SVD，得到F的松弛连续解的计算复杂度O(nmhc)。（5）对松弛离散解执行k-means所需要的计算复杂度为O(nmhct)，其中t是迭代次数。因此，FCAPBK的计算复杂度可以近似为O(nm1(dt+d+mh+c(t+1)。此外，总结了 LLGC30、AGR12和 Nystrm31三种典型方法的时间复杂度。从表1中观察到，LLGC在图的正则化中具有三次方的时间复杂度，当数据集规模很大时，计算会相当耗时；Nystrm也面临二次方的计算复杂度；AGR在图构造中的复杂性与数据大小呈线性关系，但当要达到合理精度所需锚点足够密集时，面临的计算成本显著增加。然而，本文由于采用层次锚点的方法，使得最密集锚点的规模比较小。因此，本文方法的计算成本降低了很多，并且能够处理大规模数据集。3实例分析3.1实验数据集3.1.1合成数据集以下给出一个合成数据集的实例来分析和验证本文方法的效果。由图3可以看出：图3（a）为由4个类的人工合成数据集组成的初始数据，有243个数据点和4类样本。图3（b）为采用二分k-means方法选择得到的16个锚点数据图，其中红色五角星代表从数据中选择的锚点，显然，采用二分k-means方法得到的锚点能大致代表原始数据图的结构，类内的选择和类间的选择也大体一致。图3（c）显示了该数据集中对c个类簇的选择结果和最终的算法LLGCAGRNystrmFCAPBK复杂度O(dnlbn+n3)O(dnlbm1+knm1+m31+nm1c)O(nmk+n2md+m3)O(nm1(dt+d+mh+c(t+1)表1四种方法的时间复杂度比较Table 1Comparison of time complexity of four methods注：n为样本点数，d为样本的维度，m为标记的样本点数，c为类簇数，t为迭代次数，h为锚层数。-6-4-202468xy-8-6-4-202468（a）人工合成数据集的原始图-6-4-202468xy-8-6-4-202468（b）人工合成数据集的锚点图-6-4-202468xy-8-6-4-202468（c）聚类结果图图3在人工合成数据集上的实验Fig.3Experiments on synthetic datasets782023，59（16）聚类结果（四种不同的颜色代表得到的四类簇）。因此，二分k-means应用于谱聚类能很好地实现聚类结果，以上合成数据集的聚类准确率达到99%以上。3.1.2基准数据集将FCAPBK在以下5个基准数据集上分别进行实验，以展示所提出方法的性能。USPS20数据集包含了1 854个手写数字样本和256个维度，有10个类；Mnist10数据集包含了6 996个从“0”到“9”的手写数字样本，样本维度为784维，包含10类；USPS数据集包含9 298个手写数字和10类的样本，256个维度；Letter数据集包含20 000个英文字母从A到Z的大写字母样本，每个样本转换为16个原始数字属性；Protein是蛋白质数据集，包含3类，每类样本数分别为11 310、5 251、7 826，共24 387个样本，特征维度为357维。表2列出了一些具体的统计数据。3.2指标评价通过比较每个数据集聚类结果标签与数据集原始标签来对聚类性能进行评价。采用聚类精确率（Acc）、归一化互信息（NMI）作为评价指标。Acc能发现每个簇和类之间的对应关系，并测量每个聚类包含的相应类别中的数据点数。NMI 也是评价聚类质量的一种方法。给定一组聚类类标签和一组真实标签，则计算表达式为：Acc=1ni=1n(map(ri),li)其中，n为样本总数；ri为xi聚类方法预测得到的标签；li为样本的真实标签；(x,y)是delt函数，如果x=y,(x,y)=1,否则，(x,y)=0；map(ri)是将聚类预测标签映射到数据集对应的真实标签的置换映射函数。NMI=i=1nj=1nNijlgNijnimj i=1nnilgninj=1nmjlgmjn其中，ni为各个数据集聚类结果类标签中包含的数据点个数；mj为每个真实类标签的数据点数量；Nij为聚类结果类标签和真实类标签之间数据点个数的交集。3.3对比算法为了验证所提出算法的有效性，本文选取了k-means、谱聚类（SC）、FSC32和 SCHBG28、Nystrm31作为对比。由于上述每组数据集的样本规模相差比较大，且选择不同的锚点数会有不同的聚类结果。因此，将数据集根据样本数量分为小、大规模两组。在这些实验中，将Mnist10和 USPS20、USPS 视为小规模数据集；Protein 和 Letter视为大规模数据集。在小规模数据集上由于数据USPS20比较少，文中方法和SCHBG采用锚点数m1和m2分别为 500、128，其余两组数据分别采用锚点数为 1 000、128；而在大规模数据集Protein和Letter上m1和m2分别取为2 000、256。对于FSC方法，在小规模数据集上，采用锚点数为128，在大规模数据集上，锚点数设置为256。设置近邻数k为5。对于Nystrm算法，在小规模数据集上采样点数设为128，大规模数据集上为256。3.4实验结果分析所有算法在每个数据集上均进行了15次实验，得到5个数据集的平均准确率（Acc）、平均运行时间（Time）、平均归一化互信息（NMI）。从表3和表4中可以如下观察结果，FCAPBK方法准确率在数据集USPS、USPS20、Mnist10上与其他算法相比表现得最好，为71.60%、65.22%、73.85%，并在数据集USPS、Mnist10上其归一化互信息也是最优的，达到了72.48%、66.96%，在USPS20上归一化互信息也是次优的。在Protein数据集上，FCAPBK算法准确率为次优的，略低于SCHBG的准确率，而归一化互信息在各聚类算法中均非常低，只有 1%左右。在 Letter 数据集上，FCAPBK准确率和互信息虽然不及其他基于锚点图的算法，但基本上也保持相对平衡。从表5中可以看出，在小规模数据集USPS20上，所有算法的时间消耗相差不大，传统的谱聚类（SC）算法的时间消耗要高于构造锚点图的算法；对于小规模数据集 Mnist10 和 USPS，k-means 算法占据很大的优势，统计信息样本维度类USPS201 85425610Mnist106 99678410USPS9 89225610Protein24 3873573Letter20 0001626表25个基准数据集信息统计表Table 2Statistics of five benchmark datasets算法k-meansSCFSCSCHBGNystrmFCAPBKUSPS2063.3969.5966.4470.6767.5871.60Mnist1053.8564.4860.6064.8950.8365.22USPS65.9567.4964.0270.4767.3173.85Protein42.5843.9143.4644.2941.9843.97Letter25.9527.2429.2331.6330.4329.27表3各个算法在5个数据集上的AccTable 3Acc of each algorithm on 5 datasets单位：%算法k-meansSCFSCSCHBGNystrmFCAPBKUSPS2062.1472.9565.5870.8062.8972.25Mnist1048.9866.7460.0466.0844.6066.96USPS61.1369.5460.7171.2563.1872.48Protein0.760.650.530.670.450.59Letter34.2837.2540.5741.2738.8940.47表4各个算法在5个数据集上的NMITable 4NMI of each algorithm on 5 datasets单位：%罗兴隆，等：二分k-means锚点提取的快速谱聚类79Computer Engineering and Applications计算机工程与应用2023，59（16）FCAPBK的时间消耗虽然不是最优的，但依旧和其他锚图算法相差不大；在大规模数据集Letter上，FCAPBK较其他图聚类算法的时间消耗相对比较低，在大规模数据集Protein中，FCAPBK时间消耗较长，这是因为在用二分k-means分层选取锚点时，该数据集的维度较高，导致算法迭代次数加长。需要指出的是，Nystrm的理论时间复杂度要高于 FCAPBK算法，但在有些数据集中却出现了相反的情况，这是因为在小数据集中，Nystrm选取了少量的采样点，而FCAPBK分层选取了和Nystrm相同数量的锚点，故得到的实际时间较长，但反观在大规模数据集上，FCAPBK比Nystrm效率更高。综上所述，本文提出的算法在小规模数据集USPS20、Mnist10、USPS上的性能较优，计算成本也相对较低；在大规模数据集Protein和Letter上也能有相对合适的时间及良好的性能。4结束语本文提出了一种新的二分k-means锚点提取的快速谱聚类算法（FCAPBK）。首先，通过二分k-means方法选取锚点，有效地降低了随机抽样和k-means聚类的质心点不稳定及无法体现原数据整体分布的影响，使得到的锚点更具有代表性；接着，构造多层无核锚点图，通过选择多层无核锚点来构建层次二部图；然后，与传统的基于图的光谱聚类方法不同，本文方法选取了一部分锚点来代表原始数据点，有更低的复杂度。在真实数据集上的实验结果表明，FCAPBK算法的聚类精度和归一化互信息结果都比较优，在速度方面相比于一些传统方法有明显的优势。总体来说，本文算法在精度和速度的综合条件下，性能比较稳定且有了很大提升。由于本文算法在选取锚点阶段，需要每次选择最大限度降低代价函数的簇，当数据维度很高时，时间会略微增加。今后的研究重点将是如何简化运算，高效地处理高维大数据，同时改进谱聚类的离散化处理部分。参考文献：1 FAYYAD U，PIATETSKY-SHAPIRO G，SMYTH P.Fromdata mining to knowledge discovery in databasesJ.AIMagazine，1996，17（3）：37.2 JAIN A K，MURTY M N，FLYNN P J.Data clustering：areviewJ.ACM Computing Surveys，1999，31（3）：264-323.3 HASTIE T，TIBSHIRANI R，FRIEDMAN J.The elementsof statistical learningM.New York：Springer Series in Sta-tistics，2001.4 CHANG X，YANG Y.Semisupervised feature analysis bymining correlations among multiple tasksJ.IEEE Trans-actions on Neural Networks and Learning Systems，2016，28（10）：2294-2305.5 CHANG X，YU Y L，YANG Y，et al.Semantic pooling forcomplex event analysis in untrimmed videosJ.IEEE Trans-actions on Pattern Analysis and Machine Intelligence，2016，39（8）：1617-1632.6 WANG M，FU W，HAO S，et al.Learning on big graph：label inference and regularization with anchor hierarchyJ.IEEE Transactions on Knowledge and Data Engineering，2017，29（5）：1101-1114.7 GAO Q，MA L，LIU Y，et al.Angle 2DPCA：a new for-mulation for 2DPCAJ.IEEE Transactions on Cybernetics，2017，48（5）：1672-1678.8 GAO Q，XU S，CHEN F，et al.R1-2-DPCA and face rec-ognitionJ.IEEE Transactions on Cybernetics，2018，49（4）：1212-1223.9 NIE F，ZHU W，LI X.Unsupervised large graph embed-dingC/Proceedings of the 31st AAAI Conference on Arti-ficial Intelligence，2017：2422-2428.10 LI Y，NIE F，HUANG H，et al.Large-scale multi-viewspectral clustering via bipartite graphC/Proceedings of the29th AAAI Conference on Artificial Intelligence，2015：2750-2756.11 ZHANG K，KWOK J T，PARVIN B.Prototype vector machinefor large scale semi-supervised learningC/Proceedingsof the 26th Annual International Conference on MachineLearning，2009：1233-1240.12 LIU W，HE J，CHANG S F.Large graph construction forscalable semi-supervised learningC/Proceedings of the27th International Conference on Machine Learning，2010：679-686.13 WANG M，FU W，HAO S，et al.Scalable semi-supervisedlearning by efficient anchor graph regularizationJ.IEEETransactions on Knowledge and Data Engineering，2016，28（7）：1864-1877.14 FOWLKES C，BELONGIE S，CHUNG F，et al.Spectralgrouping using the Nystrom methodJ.IEEE Transactionson Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.15 LI M，KWOK J T Y，LU B.Making large-scale Nys-trm approximation possibleC/Proceedings of the 27thInternational Conference on Machine Learning，2010：631-638.16 SHINNOU H，SASAKI M.Spectral clustering for a largedata set by reducing the similarity matrix sizeC/Pro-算法k-meansSCFSCSCHBGNystrmFCAPBKUSPS200.292.560.520.530.330.86Mnist100.5920.244.4510.125.9411.94USPS2.1770.873.286.335.477.73Protein5.21240.5618.2738.6747.3840.53Letter1.36218.3713.7615.7220.4915.33表5各个算法在5个数据集上的运行时间Table 5Running time of each algorithm on 5 datasets单位：s802023，59（16）ceedings of the 2008 International Conference on Lan-guage Resources and Evaluation，2008：201-204.17 YAN D，HUANG L，JORDAN M I.Fast approximate spec-tral clusteringC/Proceedings of the 15th ACM SIGKDDInterna