【机器学习】加权PageRank改进地标表示的自编码谱聚类算法

资源类别：文库，文档格式：PDF，文档页数：8，文件大小：3.3MB，团购合买

第15卷第2期智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992tis.201904021 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190828.1756.008.html 加权PageRank改进地标表示的自编码谱聚类算法储德润，周治平 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对传统谱聚类算法在处理大规模数据集时，聚类精度低并且存在相似度矩阵存储开销大和拉普拉斯矩阵特征分解计算复杂度高的问题。提出了一种加权PageRank改进地标表示的自编码谱聚类算法，首先选取数据亲和图中权重最高的节点作为地标点，以选定的地标点与其他数据点之间的相似关系来逼近相似度矩阵作为叠加自动编码器的输入。然后利用聚类损失同时更新自动编码器和聚类中心的参数，从而实现可扩展和精确的聚类。实验表明，在几种典型的数据集上，所提算法与地标点谱聚类算法和深度谱聚类算法相比具有更好的聚类性能。关键词：机器学习；数据挖掘；聚类分析；地标点聚类；谱聚类；加权PageRank;自动编码器；聚类损失中图分类号：TP18文献标志码：A文章编号：1673-4785(2020)02-0302-08 中文引用格式：储德润，周治平.加权PageRank改进地标表示的自编码谱聚类算法J.智能系统学报，2020,15(2)： 302-309. 英文引用格式：CHU Derun,ZHOU Zhiping..An autoencoder spectral clustering algorithm for improving landmark representation by weighted PageRank[Jl.CAAI transactions on intelligent systems,2020,15(2):302-309. An autoencoder spectral clustering algorithm for improving landmark representation by weighted PageRank CHU Derun,ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China) Abstract:Several problems,such as low clustering precision,large memory overhead of the similarity matrix,and high computational complexity of the Laplace matrix eigenvalue decomposition,are encountered when using the traditional spectral clustering algorithm to deal with large-scale datasets.To solve these problems,an autoencoder spectral cluster- ing algorithm for improving landmark representation by weighted PageRank is proposed in this study.First,the nodes with the highest weight in the data affinity graph were selected as the landmark points.The similarity matrix was ap- proximated by the similarity relation between the selected ground punctuation points and other data points.The result was further used as the input of the superimposed automatic encoder.At the same time,the parameters of the automatic encoder and cluster center were updated simultaneously using clustering loss.Thus,extensible and accurate clustering can be achieved.The experimental results show that the proposed autoencoder spectral clustering algorithm has better clustering performance than the landmark and depth spectral clustering algorithms on several typical datasets. Keywords:machine learning;data mining;cluster analysis;landmark spectral clustering;spectral clustering;weighted pagerank;autoencoder;clustering loss 聚类是数据挖掘、模式识别等许多研究领域数据集划分为紧凑的聚类，使聚类内的数据对象中的基本问题之一，聚类分析的目的是将给定的比不同的聚类中的数据对象更加相似。其中谱聚收稿日期：2019-04-09.网络出版日期：2019-08-29. 类可以适应更广泛的几何形状，并检测非凸模式通信作者：储德润.E-mail:CDR0727@163.com 和线性不可分离的簇，而不存在局部最优问题

DOI: 10.11992/tis.201904021 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190828.1756.008.html 加权 PageRank 改进地标表示的自编码谱聚类算法储德润，周治平（江南大学物联网技术应用教育部工程研究中心，江苏无锡 214122）摘要：针对传统谱聚类算法在处理大规模数据集时，聚类精度低并且存在相似度矩阵存储开销大和拉普拉斯矩阵特征分解计算复杂度高的问题。提出了一种加权 PageRank 改进地标表示的自编码谱聚类算法，首先选取数据亲和图中权重最高的节点作为地标点，以选定的地标点与其他数据点之间的相似关系来逼近相似度矩阵作为叠加自动编码器的输入。然后利用聚类损失同时更新自动编码器和聚类中心的参数，从而实现可扩展和精确的聚类。实验表明，在几种典型的数据集上，所提算法与地标点谱聚类算法和深度谱聚类算法相比具有更好的聚类性能。关键词：机器学习；数据挖掘；聚类分析；地标点聚类；谱聚类；加权 PageRank；自动编码器；聚类损失中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)02−0302−08 中文引用格式：储德润, 周治平. 加权 PageRank 改进地标表示的自编码谱聚类算法 [J]. 智能系统学报, 2020, 15(2): 302–309. 英文引用格式：CHU Derun, ZHOU Zhiping. An autoencoder spectral clustering algorithm for improving landmark representation by weighted PageRank[J]. CAAI transactions on intelligent systems, 2020, 15(2): 302–309. An autoencoder spectral clustering algorithm for improving landmark representation by weighted PageRank CHU Derun，ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: Several problems, such as low clustering precision, large memory overhead of the similarity matrix, and high computational complexity of the Laplace matrix eigenvalue decomposition, are encountered when using the traditional spectral clustering algorithm to deal with large-scale datasets. To solve these problems, an autoencoder spectral clustering algorithm for improving landmark representation by weighted PageRank is proposed in this study. First, the nodes with the highest weight in the data affinity graph were selected as the landmark points. The similarity matrix was approximated by the similarity relation between the selected ground punctuation points and other data points. The result was further used as the input of the superimposed automatic encoder. At the same time, the parameters of the automatic encoder and cluster center were updated simultaneously using clustering loss. Thus, extensible and accurate clustering can be achieved. The experimental results show that the proposed autoencoder spectral clustering algorithm has better clustering performance than the landmark and depth spectral clustering algorithms on several typical datasets. Keywords: machine learning; data mining; cluster analysis; landmark spectral clustering; spectral clustering; weighted pagerank; autoencoder; clustering loss 聚类是数据挖掘、模式识别等许多研究领域中的基本问题之一，聚类分析的目的是将给定的数据集划分为紧凑的聚类，使聚类内的数据对象比不同的聚类中的数据对象更加相似。其中谱聚类可以适应更广泛的几何形状，并检测非凸模式和线性不可分离的簇，而不存在局部最优问题，收稿日期：2019−04−09. 网络出版日期：2019−08−29. 通信作者：储德润. E-mail：CDR0727@163.com. 第 15 卷第 2 期智能系统学报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020

第2期储德润，等：加权PageRank改进地标表示的自编码谱聚类算法 ·303· 被广泛用于数据挖掘和图像分割。基于深度自编码的聚类算法可以提高大规模应谱聚类算法虽然性能良好，但由于其计算复用的效率，但它们都需要使用整个数据集的相似杂度高，很难适用于大规模的数据集。近些年度矩阵作为自动编码器的输入，保存了所有数据来，研究人员为了加快谱聚类算法的计算速度和点的相似性，由于内存消耗大，不适用于大规模降低谱聚类算法对于大规模数据集的计算复杂数据集。度问题，探索研究了一系列的方法来提高谱聚类本文采用加权PageRank算法，选取数据亲和算法对于大规模数据集的可拓展性。Lⅰ等四提出图中最具代表的点作为地标点。以选定的地标点了一种精确的、可扩展的Nystrom算法，使用最近与其他数据点之间的相似关系来逼近相似度矩阵的随机低秩矩阵逼近算法对内部子矩阵进行近作为叠加自动编码器的输入，通过采样几个数据似的SVD,降低随机采样引起的不稳定性和采样点来代替所有数据点。用叠加式自动编码器代替误差。赵晓晓等)结合稀疏表示和约束传递，提拉普拉斯矩阵的特征分解，然后进行k-means聚出一种结合稀疏表示和约束传递的半监督谱聚类。同时进一步改进聚类和嵌入表示，通过迭代类算法，进一步提高了聚类准确率。Ding等1提优化基于Kullback Leibler(KL)散度的聚类损失，出一种基于hmrf模型的半监督近似谱聚类算法，将聚类和表示联合更新，从而能够获得更强大的利用hmrf半监督聚类与近似加权核k均值之间表示和更精确的聚类结果。的数学联系，利用近似加权核k-均值计算hmrf谱聚类的最优聚类结果。He等提出了一种有效 1相关算法理论的大规模数据谱聚类方法，谱聚类的复杂度比现 1.1基于加权PageRank算法的地标选择有的Nystrom近似在大规模数据上的复杂度要 PageRank算法l是使用最广泛的页面排序低。显著加快谱聚类中的特征向量逼近和效益算法之一。但是原始PageRank算法也存在一些预测速度。林大华等针对现有子空间聚类算法问题，假设两个节点“和c彼此指向但没有指向没有利用样本自表达和稀疏相似度矩阵，提出了其他节点，并且存在第3个节点w指向其中一个节一种新的稀疏样本自表达子空间聚类方法，所获点。这个循环将累积秩，但不会将任何秩分配到得的相似度矩阵具有良好的子空间结构和噜棒性。Yang 前两个节点，因为没有输出链路。为了处理这个等提出了一种新的基于层次二部图的谱聚类方问题，通过一个迭代过程来近似节点u的PageRank 法，采用无参数而有效的邻域分配策略构造相似值PR(。则有式(1)：矩阵，避免了调整相似性矩阵的需要，大大降低 PR(四=(I-d0+d∑PR四 (1) 了算法的计算复杂度。虽然众多改进的谱聚类 ) N 算法在一定程度上减小了谱聚类的时间复杂度，其中，d是一个阻尼因子，通常设置为0.852。但仍然要对拉普拉斯矩阵进行特征分解，对于大加权PageRank算法在文献[13]中提出，加权规模的数据集来说内存消耗过大，具有巨大的空 PageRank算法根据节点的重要性为节点分配排间复杂度。最近，深度学习可在计算机视觉、语序值。这种重要性是根据传入链路和传出链路的音识别和自然语言处理中得到了广泛的研究。权重来分配的，其中，链路表示各自的基于内容一些深度学习的方法已经被提出来用于数据聚的关系，分别以w8和w,表示。w8b是(a,b)的类。Tian等)利用叠加稀疏自编码器得到原始传入链路权重，它是根据到节点b的传入链路数图的非线性嵌入，然后对嵌入表示进行k-均值聚和到节点a的所有参考节点的传人链路数来计算类，得到聚类结果，用叠加的自动编码器代替特的，其公式为征分解，有效地降低了计算复杂度。Shao等o提 )= (2) 出了一种新的快速图谱聚类深度线性编码方案， cER。该方法同时学习了线性变换和编码，并利用深层其中，6是节点b的传入链路数；i是节点c的传结构进一步细化了识别特征。Song等u提出了入链路数；R。是节点a的参考节点集（基于内容一种新的基于自编码网络的聚类方法，通过设计的最近邻域)。w,是(a,b)的传出链路权重，它是数据与聚类中心之间距离的约束，得到了一种更根据节点α的所有参考节点的传出链路数计算适合于聚类的稳定而紧凑的表示形式。这种深的，其公式为层次的结构可以学习到强大的非线性映射，数据 w,= (3) 可以很好地在变换后的空间中进行分割。上述

被广泛用于数据挖掘和图像分割。谱聚类算法虽然性能良好，但由于其计算复杂度高，很难适用于大规模的数据集。近些年来，研究人员为了加快谱聚类算法的计算速度和降低谱聚类算法对于大规模数据集的计算复杂度问题，探索研究了一系列的方法来提高谱聚类算法对于大规模数据集的可拓展性。Li 等 [1] 提出了一种精确的、可扩展的 Nystrom 算法，使用最近的随机低秩矩阵逼近算法对内部子矩阵进行近似的 SVD，降低随机采样引起的不稳定性和采样误差。赵晓晓等[2] 结合稀疏表示和约束传递，提出一种结合稀疏表示和约束传递的半监督谱聚类算法，进一步提高了聚类准确率。Ding 等 [3] 提出一种基于 hmrf 模型的半监督近似谱聚类算法，利用 hmrf 半监督聚类与近似加权核 k 均值之间的数学联系，利用近似加权核 k-均值计算 hmrf 谱聚类的最优聚类结果。He 等 [4] 提出了一种有效的大规模数据谱聚类方法，谱聚类的复杂度比现有的 Nystrom 近似在大规模数据上的复杂度要低。显著加快谱聚类中的特征向量逼近和效益预测速度。林大华等[5] 针对现有子空间聚类算法没有利用样本自表达和稀疏相似度矩阵，提出了一种新的稀疏样本自表达子空间聚类方法，所获得的相似度矩阵具有良好的子空间结构和鲁棒性。Yang 等 [6] 提出了一种新的基于层次二部图的谱聚类方法，采用无参数而有效的邻域分配策略构造相似矩阵，避免了调整相似性矩阵的需要，大大降低了算法的计算复杂度。虽然众多改进的谱聚类算法在一定程度上减小了谱聚类的时间复杂度，但仍然要对拉普拉斯矩阵进行特征分解，对于大规模的数据集来说内存消耗过大，具有巨大的空间复杂度。最近，深度学习[7] 在计算机视觉、语音识别和自然语言处理中得到了广泛的研究。一些深度学习的方法已经被提出来用于数据聚类 [8]。Tian 等 [9] 利用叠加稀疏自编码器得到原始图的非线性嵌入，然后对嵌入表示进行 k-均值聚类，得到聚类结果，用叠加的自动编码器代替特征分解，有效地降低了计算复杂度。Shao 等 [10] 提出了一种新的快速图谱聚类深度线性编码方案，该方法同时学习了线性变换和编码，并利用深层结构进一步细化了识别特征。Song 等 [11] 提出了一种新的基于自编码网络的聚类方法，通过设计数据与聚类中心之间距离的约束，得到了一种更适合于聚类的稳定而紧凑的表示形式。这种深层次的结构可以学习到强大的非线性映射，数据可以很好地在变换后的空间中进行分割。上述基于深度自编码的聚类算法可以提高大规模应用的效率，但它们都需要使用整个数据集的相似度矩阵作为自动编码器的输入，保存了所有数据点的相似性，由于内存消耗大，不适用于大规模数据集。本文采用加权 PageRank 算法，选取数据亲和图中最具代表的点作为地标点。以选定的地标点与其他数据点之间的相似关系来逼近相似度矩阵作为叠加自动编码器的输入，通过采样几个数据点来代替所有数据点。用叠加式自动编码器代替拉普拉斯矩阵的特征分解，然后进行 k-means 聚类。同时进一步改进聚类和嵌入表示，通过迭代优化基于 Kullback Leibler(KL) 散度的聚类损失，将聚类和表示联合更新，从而能够获得更强大的表示和更精确的聚类结果。 1 相关算法理论 1.1 基于加权 PageRank 算法的地标选择 u w u (u) PageRank 算法[12] 是使用最广泛的页面排序算法之一。但是原始 PageRank 算法也存在一些问题，假设两个节点和 c 彼此指向但没有指向其他节点，并且存在第 3 个节点指向其中一个节点。这个循环将累积秩，但不会将任何秩分配到前两个节点，因为没有输出链路。为了处理这个问题，通过一个迭代过程来近似节点的 PageRank 值 PR 。则有式（1）： PR(u) = (1−d)+d ∑ v∈B(u) PR(v) Nv (1) 其中， d 是一个阻尼因子，通常设置为 0.85[12]。 w in (a,b) w out (a,b) w in (a,b) (a,b) b a 加权 PageRank 算法在文献 [13] 中提出，加权 PageRank 算法根据节点的重要性为节点分配排序值。这种重要性是根据传入链路和传出链路的权重来分配的，其中，链路表示各自的基于内容的关系，分别以和表示。是的传入链路权重，它是根据到节点的传入链路数和到节点的所有参考节点的传入链路数来计算的，其公式为 w in (a,b) = ∑ ib c∈Ra ic (2) ib b ic c Ra a w out (a,b) (a,b) a 其中，是节点的传入链路数；是节点的传入链路数；是节点的参考节点集 (基于内容的最近邻域)。是的传出链路权重，它是根据节点的所有参考节点的传出链路数计算的，其公式为 w out (a,b) = ∑ob c ∈Ra oc (3) 第 2 期储德润，等：加权 PageRank 改进地标表示的自编码谱聚类算法 ·303·

·304· 智能系统学报第15卷其中，o%是节点b的传出链路数；o是节点c的传其中，()是一个具有尺度参数σ的高斯核函出链路数。数，(x,4)=exp(-x-4l/2o2)是最常用的高斯 wpr(b)的计算需要迭代过程来调整近似到理核函数之一，其中，σ控制着每个数据点的局部论真值，wpr表示节点的加权PageRank权重，所邻域。根据核尺度参数σ的自调整策略，在本文有节点的wpr初始值初始化为l/n,n为节点数。所提算法中，设置σ2=0，YΦ(x,u),其中σ：是在每个迭代中，每个节点b的wpr(b)计算如下： i的邻居点的平均距离，也是Z ERPXn的稀疏表 wpr(b)=I-d④wpr(a)+d∑wpr(awaw(④) 示中的非零元素。对于W亲和矩阵，认为W= 在每次迭代中，所有节点的wpr值都是基于式 2T2,其中2=DrZ是D=∑，乙：度矩阵的归一 (4)减小的。对于所有节点当满足以下的停止化Z。准则时，迭代过程停止：如果计算所有数据点的相似性矩阵并将其作 Nprb)a-1-wpr(b)延≤B 为堆叠式自动编码器的输入，对于大型数据集来 (5) wpr(b)er 说空间消耗非常高。代替计算给定数据与所有其其中，分数是前一次迭代与当前迭代之间的归一他数据点的相似性，本文算法只考虑选择的地标化差值，B是一个预定义的停止阈值，这里设置点与其他数据点之间的相似性。在这里重写了如 B=10-3。最后当式(5)成立时，选择wpr最高的p 下拉普拉斯矩阵的形式：节点作为地标点。 Lnew =SST (8) 2改进地标表示的自编码谱聚类算法在这里使用S作为叠加自编码器的输人，从前文可以知道归一化相似矩阵可以用稀疏表示矩 2.1构造新的拉普拉斯矩阵阵Z,为了进一步降低计算复杂度，在这里使用一在文献[14-15]中，提出了基于地标点的谱聚种简单的方法计算度矩阵D2,矩阵的主要对角线类算法来加速谱聚类，在给定n个数据点的数据元素一般计算如下：集的情况下，选择p<n个具有代表性的数据点 d=∑w=∑22 (9) 作为地标的特征点，将原始数据点表示为这些地对式(11)进行运算演化可以得到：标的线性稀疏组合，然后利用基于地标的表示来高效地计算数据的谱嵌入，并通过理论分析证明 d山--=g28=2 (10) 1 其性能优于Nystruom和快速谱聚类方法，有效地 = 利用稀疏表示矩阵逼近了整个图的相似度矩阵。其中，2是一个p×1的向量，第k个元素是2中它表示选定的p个地标点与n个数据点之间的成第k行元素的和。对相似性。 D2=diag() (11) 给定数据矩阵X={x1,2…xn}∈R4,它可以在这里新的拉普拉斯矩阵的构造如下：近似为X≈UZ。U每一列都可以看作捕捉数据 Le=DPWDR=D:E2TZDR (12) 中较高层次特征的基向量。选定的地标点可以看 S=D-IPaT (13) 作是基向量。假设对于任何数据，已经有了地标最后，将相似度矩阵S输入到自动编码器中，最矩阵U。对于任意点x,它的近似￡：计算为后运行k-means聚类，从而得到聚类结果。 (6) 2.2自编码器与聚类优化自动编码器是一种用于有效编码和降维的无根据稀疏编码策略，假设当x,更接近4时，监督学习的人工神经网络。自动编码器的目的是矩阵Z的第j个元素应该更大。为了强调这一假使原始输人：和新的嵌入表示y的重构输出m 设，创建Z亲和稀疏矩阵的稀疏表示，通过选择之间的重构损失最小化69。重构损失定义如下 r<p个最近的地标点，代替p个地标点(U∈R), N 例如，如果不是r的最近的地标之一，则z的 L=∑1,8f;0):》 (14) 值为0，生成稀疏表示矩阵Z。设Uo∈R表示 U的子矩阵，由x:最近的r个地标点组成，然后其中，{0,2}=h1,b,2,b2}是自动编码器的参数。计算出每个z#元素如下：虽然用自编码器配合得到聚类结果，有效地 Φ(x,u) 降低了计算复杂度，减小了空间复杂度。但是， Zi= Φ(x,u） iE1,2,....n,and,jeU (7) 由于需要计算和保存所有数据点的相似关系，因 fEUu 此内存消耗进一步增加。学习表示与聚类分离

其中，ob 是节点 b 的传出链路数；oc 是节点 c 的传出链路数。 wpr(b) wprwpr 1/n n b wpr(b) 的计算需要迭代过程来调整近似到理论真值，表示节点的加权 PageRank 权重，所有节点的初始值初始化为，为节点数。在每个迭代中，每个节点的计算如下： wpr(b) = (1−d)wpr(a)+d ∑ a∈R(b) wpr(a)w in (a,b)w out (a,b) (4) 在每次迭代中，所有节点的 wpr 值都是基于式 (4) 减小的[13]。对于所有节点当满足以下的停止准则时，迭代过程停止： wpr(b)iter−1 −wpr(b)iter wpr(b)iter ⩽ β (5) β β = 10−3 wpr p 其中，分数是前一次迭代与当前迭代之间的归一化差值，是一个预定义的停止阈值，这里设置。最后当式 (5) 成立时，选择最高的节点作为地标点。 2 改进地标表示的自编码谱聚类算法 2.1 构造新的拉普拉斯矩阵 n p ≪ n p n 在文献 [14-15] 中，提出了基于地标点的谱聚类算法来加速谱聚类，在给定个数据点的数据集的情况下，选择个具有代表性的数据点作为地标的特征点，将原始数据点表示为这些地标的线性稀疏组合，然后利用基于地标的表示来高效地计算数据的谱嵌入，并通过理论分析证明其性能优于 Nystrüom 和快速谱聚类方法，有效地利用稀疏表示矩阵逼近了整个图的相似度矩阵。它表示选定的个地标点与个数据点之间的成对相似性。 X = {x1, x2 · · · xn} ∈ R n×d X ≈ UZ U U xi xˆi 给定数据矩阵，它可以近似为。每一列都可以看作捕捉数据中较高层次特征的基向量。选定的地标点可以看作是基向量。假设对于任何数据，已经有了地标矩阵。对于任意点，它的近似计算为 xˆi = ∑p j=1 zjiuj (6) xi uj Z j Z r < p p U ∈ R d×p uj r zji Z U⟨i⟩ ∈ R d×r U xi r zji 根据稀疏编码策略，假设当更接近时，矩阵的第个元素应该更大。为了强调这一假设,创建亲和稀疏矩阵的稀疏表示,通过选择个最近的地标点,代替个地标点 ( )，例如，如果不是的最近的地标之一，则的值为 0，生成稀疏表示矩阵。设表示的子矩阵，由最近的个地标点组成，然后计算出每个元素如下： zji = Φ ( xi ,uj ) ∑ j ′∈U⟨i⟩ Φ ( xi ,uj ) , i ∈ 1,2,· · · ,n, and, j ∈ U⟨i⟩ (7) Φ(·) σ Φ ( xi ,uj ) = exp( − xi−uj /2σ 2 ) σ σ σ 2 = σiσj ,∀Φ ( xi ,uj ) σi i Z ∈ R p×n W W = Zˆ T Zˆ Zˆ = D −1/2Z D = ∑ j Zji Z 其中，是一个具有尺度参数的高斯核函数，是最常用的高斯核函数之一，其中，控制着每个数据点的局部邻域。根据核尺度参数的自调整策略，在本文所提算法中，设置，其中是的邻居点的平均距离，也是的稀疏表示中的非零元素。对于亲和矩阵，认为，其中是度矩阵的归一化。如果计算所有数据点的相似性矩阵并将其作为堆叠式自动编码器的输入，对于大型数据集来说空间消耗非常高。代替计算给定数据与所有其他数据点的相似性，本文算法只考虑选择的地标点与其他数据点之间的相似性。在这里重写了如下拉普拉斯矩阵的形式： Lnew = SST (8) S Z D2 在这里使用作为叠加自编码器的输入，从前文可以知道归一化相似矩阵可以用稀疏表示矩阵，为了进一步降低计算复杂度，在这里使用一种简单的方法计算度矩阵，矩阵的主要对角线元素一般计算如下: d2ii = ∑ i wi j = ∑ i zˆ T i zˆj (9) 对式 (11) 进行运算演化可以得到： d2ii = ∑n j=1 wi j = ∑n j=1 zˆ T i zˆj = zˆ T i ∑n j=1 zˆj= zˆ T i Zˆ s (10) Zˆ s p×1 k Zˆ k 其中，是一个的向量，第个元素是中第行元素的和。 D2= diag( Zˆ T Zˆ s ) (11) 在这里新的拉普拉斯矩阵的构造如下: Lnew = D −1/2 2 W D−1/2 2 = D −1/2 2 Zˆ T ZˆD −1/2 2 (12) S = D −1/2 2 Zˆ T (13) 最后，将相似度矩阵 S 输入到自动编码器中，最后运行 k-means 聚类，从而得到聚类结果。 2.2 自编码器与聚类优化 xi yi mi 自动编码器是一种用于有效编码和降维的无监督学习的人工神经网络。自动编码器的目的是使原始输入和新的嵌入表示的重构输出之间的重构损失最小化[16-19]。重构损失定义如下: Lr = ∑N i=1 l(xi ,g(f (xi ; θ1); θ2)) (14) 其中， {θ1, θ2} = {h1,b1,h2,b2} 是自动编码器的参数。虽然用自编码器配合得到聚类结果，有效地降低了计算复杂度，减小了空间复杂度。但是，由于需要计算和保存所有数据点的相似关系，因此内存消耗进一步增加。学习表示与聚类分离， ·304· 智能系统学报第 15 卷

第2期储德润，等：加权PageRank改进地标表示的自编码谱聚类算法 ·305· 嵌入表示是不可靠的，对聚类有负面影响。为了 2.3所提算法流程将聚类和学习表示联合更新，并且能够获得更强加权PageRank改进地标表示的自编码谱聚大的表示和更精确的聚类结果，将这两个过程集类算法步骤：成到一个具有基于KL散度的聚类损失函数的单输入数据集X,目标聚类数k,地标数目p 一框架中，并迭代地优化了自动编码器和聚类中最近邻地标数目r,停止阈值B,迭代数目t,停止心的参数。聚类损失被定义为分布在P和Q之阈值h。间的KL散度，其中Q是由-SNE测量的软标签输出实际聚类数目y,聚类损失L,重构损的分布，P是由Q导出的目标分布。聚类损失可失Lo 以用来同时更新堆叠式自动编码器和聚类中心的 1)根据式(2)(4)计算wpr(b)的值，迭代计算参数，如式(15)所示： wpr直到满足式(S),根据最高的wpr值选择p个 L=KL(PIO)=∑∑P,log (15) 地标点。 9 2)通过式(7)计算稀疏表示矩阵Z,所选地标其中，9附是由t-SNE测量的嵌入表示y和聚类中点p和具有r个最近邻地标点的矩阵U。心c,的相似性。（+b-c) 3)通过式(12)计算新的拉普拉斯矩阵Lw。 (16) 4)使用D22r作为自动编码器的输人。接 ∑1+-c) 着对叠加式自动编码器进行训练，得到嵌入表 P是由q确定的目标分布：示h。呢∑9 5)在最后一个隐藏层的嵌入表示：上进行k means聚类，以初始化聚类中心cj。根据式(22)、 p时= (17) ∑∑w (23)更新自动编码器的参数和聚类中心c0 2.4算法复杂度分析因为，P是由9确定的目标分布，所以L的假设从n个数据点中选择p个地标，则所提最小化可以看作是自我训练的一种形式。重构损算法采用加权PageRank选择地标点，该步骤的时失保证了嵌入空间能够保持数据的局部结构，因间复杂度为O(pm),其中t为迭代次数。为了构此将重构损失和聚类损失作为优化参数的目标造新的相似矩阵，只需根据方程计算稀疏表示矩函数。阵Z,这一步的时间复杂度为O(pm)。堆叠式自动 L=L+AL (18) 其中，1(（≥0）是一个控制嵌入空间失真程度的因子。编码器和优化算法的时间复杂度为O(nD2+ndk), 利用最小批量随机梯度下降可以得到自动编 k是簇数，D是隐藏层的最大单元数，d是嵌入层码器的聚类中心和参数的优化，计算出L关于嵌的维数。通常k≤d≤D,所以时间复杂度可写为入表示和聚类中心c的梯度。 O(tpn+pm+nD)。基于地标点的谱聚类算法阿的时张-221+b-c'p-46-6 间复杂度为O(tpm+pm+p2n+p),又p≤n,则p3≤ (19) dy p2n,故p2n+p3≈p2n,所以基于地标点谱聚类算法 1 a业-221+-c0'(a-p6-c）的时间复杂度可写为O(tpn+pm+p2n),其中p与 (20) oc: 1 D的取值相近且远小于n,因此，可推断本文方法 L/y:可以传递到叠加的自动编码器，并用与基于地标点谱聚类算法时间复杂度相当，但由于反向传播以计算参数aLe/aM1、Le/aM2的梯于算法改进中通过采样少数几个数据，点来推断数度。编码器权重的更新公式如下：据集的全局特征，空间复杂度有所降低。 M=M-2(0+%) (21) 3实验与结果分析译码器的权重公式更新如下： M=M-2胎） 3.1实验环境及性能指标 (22) 在本文算法实验中，选取了几个数据量较大聚类中心c的更新公式如下：的数据集进行实验，它们分别为手写数字数据集 99”此 (23) USPS、Pendigits、MNIST、英文字母表数据集Let- m台ac terRec和UCI数据库中的数据集CoverType,表I 式中：m是小批量的样本数；刀是学习速率。给出了数据集的详细特征。本文算法实验是在Pyt

P Q Q P Q 嵌入表示是不可靠的，对聚类有负面影响。为了将聚类和学习表示联合更新，并且能够获得更强大的表示和更精确的聚类结果，将这两个过程集成到一个具有基于 KL 散度的聚类损失函数的单一框架中，并迭代地优化了自动编码器和聚类中心的参数。聚类损失被定义为分布在和之间的 KL 散度，其中是由 t-SNE 测量的软标签的分布，是由导出的目标分布。聚类损失可以用来同时更新堆叠式自动编码器和聚类中心的参数，如式（15）所示： Lc = KL(P∥Q) = ∑ i ∑ j pi j log pi j qi j (15) qi j yi cj 其中，是由 t-SNE 测量的嵌入表示和聚类中心的相似性。 qi j = ( 1+ yi −cj 2 )−1 ∑ j ( 1+ yi −cj 2 )−1 (16) pi j 是由 qi j 确定的目标分布： pi j = q 2 i j/ ∑ i qi j ∑ j   q 2 i j/ ∑ i qi j   (17) 因为， pi j 是由 qi j 确定的目标分布，所以 Lc 的最小化可以看作是自我训练的一种形式。重构损失保证了嵌入空间能够保持数据的局部结构，因此将重构损失和聚类损失作为优化参数的目标函数。 L = Lc +λLr (18) 其中， λ (λ ⩾ 0) 是一个控制嵌入空间失真程度的因子。 Lc yi cj 利用最小批量随机梯度下降可以得到自动编码器的聚类中心和参数的优化，计算出关于嵌入表示和聚类中心的梯度。 ∂Lc ∂yi = 2 ∑k j=1 ( 1+ yi −cj 2 )−1 ( pi j −qi j) (yi −cj ) (19) ∂Lc ∂cj = 2 ∑k i=1 ( 1+ yi −cj 2 )−1 ( qi j − pi j) (yi −cj ) (20) ∂Lc/∂yi ∂Lc/∂M1 ∂Lc/∂M2 可以传递到叠加的自动编码器，并用于反向传播以计算参数、的梯度。编码器权重的更新公式如下： M1 = M1 − η m ∑m i=1 ( ∂Lc ∂M1 +λ ∂Lr ∂M1 ) (21) 译码器的权重公式更新如下： M2 = M2 − η m ∑m i=1 ( ∂Lr ∂M2 ) (22) 聚类中心 cj 的更新公式如下： cj = cj − η m ∑m i=1 ∂Lc ∂cj (23) 式中：m 是小批量的样本数； η 是学习速率。 2.3 所提算法流程加权 PageRank 改进地标表示的自编码谱聚类算法步骤： X k p r β t h 输入数据集，目标聚类数，地标数目，最近邻地标数目，停止阈值，迭代数目，停止阈值。 y Lc Lr 输出实际聚类数目，聚类损失，重构损失。 wpr(b) wpr wpr p 1) 根据式 (2)~(4) 计算的值，迭代计算直到满足式 (5)，根据最高的值选择个地标点。 Z p r U 2) 通过式 (7) 计算稀疏表示矩阵，所选地标点和具有个最近邻地标点的矩阵。 3) 通过式 (12) 计算新的拉普拉斯矩阵 Lnew。 D −1/2 2 Zˆ T hi 4) 使用作为自动编码器的输入。接着对叠加式自动编码器进行训练，得到嵌入表示。 hi cj cj 5) 在最后一个隐藏层的嵌入表示上进行 kmeans 聚类，以初始化聚类中心。根据式 (22)、 (23) 更新自动编码器的参数和聚类中心。 2.4 算法复杂度分析 n p O(tpn) t Z O(pn) O ( nD2 +ndk) k D d k ⩽ d ⩽ D O ( tpn+ pn+nD2 ) O ( tpn+ pn+ p 2n+ p 3 ) p ≪ n p 3 ≪ p 2n p 2n+ p 3 ≈ p 2n O ( tpn+ pn+ p 2n ) p D n 假设从个数据点中选择个地标，则所提算法采用加权 PageRank 选择地标点，该步骤的时间复杂度为，其中为迭代次数。为了构造新的相似矩阵，只需根据方程计算稀疏表示矩阵 ,这一步的时间复杂度为。堆叠式自动编码器和优化算法的时间复杂度为，是簇数，是隐藏层的最大单元数，是嵌入层的维数。通常，所以时间复杂度可写为。基于地标点的谱聚类算法[15] 的时间复杂度为，又，则，故，所以基于地标点谱聚类算法的时间复杂度可写为，其中与的取值相近且远小于，因此，可推断本文方法与基于地标点谱聚类算法时间复杂度相当，但由于算法改进中通过采样少数几个数据点来推断数据集的全局特征，空间复杂度有所降低。 3 实验与结果分析 3.1 实验环境及性能指标在本文算法实验中，选取了几个数据量较大的数据集进行实验，它们分别为手写数字数据集 USPS、Pendigits、MNIST、英文字母表数据集 LetterRec 和 UCI 数据库中的数据集 CoverType，表 1 给出了数据集的详细特征。本文算法实验是在 Pyt- 第 2 期储德润，等：加权 PageRank 改进地标表示的自编码谱聚类算法 ·305·

·306· 智能系统学报第15卷 hon3.6,计算机的硬件配置为Intel Core i7-7700 同时将控制嵌入表示空间失真程度的A值设为0.1。 CPU3.60GHz、16GB内存的平台下进行。 3.2实验结果分析表1实验数据集的特征为了验证本文算法的性能，采用文献[20]中 Table 1 Characteristics of experimental datasets 聚类准确率ACC和归一化互信息NMⅫ两种聚类数据集数据个数类数维数度量指标来对聚类结果进行评估和分析比较。AC℃ 和NM的取值范围都在0~1之间，较高的值表 USPS 9280 10 256 示较好的聚类结果。 Pendigits 10992 10 16 根据表2可以看出，基于聚类准确率(ACC) MNIST 70000 10 784 的实验结果表明，提出的加权PageRank改进地标 LetterRec 20000 26 16 表示的自编码谱聚类算法在USPS、Pendigits、 Covtype 581012 7 54 MNIST、LetterRec、Covtype数据集上相较于基于 nystrom的方法、基于地标点采样的快速谱聚类方总体而言，提出的方法在ACC和NMI上均法、基于深度学习自编码的快速图聚类方法都取优于其他所列的对比方法。得了最好的结果，所提方法在聚类准确率方面都本文算法与文献[I]中基于nystrom的方法，优于以上所提其他方法。特别是在MNIST数据文献[9]中基于叠加稀疏自动编码器聚类方法G- 集上，GraEn、DLC、DEC和提出的方法这些基于 raEn,文献[10]中基于深度学习编码的快速图聚深度学习自编码的谱聚类方法的聚类结果均明显类方法DLC,文献[14-15]基于地标点采样的快速高于传统nystrom的方法、RSNy方法和基于地标谱聚类方法LSC-R和LSC-K,文献[17)]中深层嵌点的方法(LSC-R,LSC-K),其中相较于传统ys- 入聚类方法DEC和文献[I9]基于改进可拓展的y- trom的方法，本文所提的方法在MNIST数据集上 strom方法RSNy这些算法进行实验对比。聚类准确率方面提高了35.91%。相较于基于地本文实验的具体的实验参数设置如下：基于标点的快速谱聚类方法LSC-R,提高了30.71%。地标点采样的快速谱聚类方法L$C有两个参数可以看出，所提方法相较于这些方法聚类精度的需要设置，分别为地标点p的数目，最近邻地标提高是巨大的。相较于其他几种快速谱聚类方点r的数目，在这里，我们统一设置p=1000和法，所提方法在MNIST数据集上分别提高了 r=5。在加权PageRank算法中，我们设置收敛阈 18.73%和16.91%，总体而言也是相当可观。同值B=10-3。编码器被设置为维数为p-500-500- 时，从表中可以看出基于地标点的方法在USPS 2000-10的多完全连接层，适用于所有的数据 Pendigits、LetterRec和Covtype数据集上的聚类准集。解码器是维数为10-2000-500-500-p的编确率比基于自编码的方法在一定程度上还要好。码器的镜像。并且，将最小批量设置为256个，初但是所提的方法相较于这些方法而言，实验得到始学习速率n设为0.1。停止阈值设为h=10-3, 的聚类准确率方面均是最优的。表2不同数据集的聚类准确率(ACC)的比较 Table 2 Comparison of clustering accuracy of different data sets 算法 USPS Pendigits MNIST LetterRec Covtype Nystrom 0.6814 0.7394 0.5370 0.3011 0.2231 RSNy 0.7061 0.7547 0.7088 0.2949 0.2242 LSC-R 0.7524 0.7904 0.5890 0.2922 0.2475 LSC-K 0.7753 0.8199 0.7270 0.3033 0.2550 GraEn 0.6931 0.7364 0.8182 0.2872 0.2218 DLC 0.7263 0.7692 0.8367 0.2957 0.2431 DEC 0.7499 0.7904 0.8651 0.2975 0.2497 本文算法 0.7897 0.8461 0.8961 0.3093 0.2682

hon 3.6，计算机的硬件配置为 Intel Core i7-7700 CPU 3.60 GHz、16 GB 内存的平台下进行。总体而言，提出的方法在 ACC 和 NMI 上均优于其他所列的对比方法。本文算法与文献 [1] 中基于 nystrom 的方法，文献 [9] 中基于叠加稀疏自动编码器聚类方法 GraEn，文献 [10] 中基于深度学习编码的快速图聚类方法 DLC，文献 [14-15] 基于地标点采样的快速谱聚类方法 LSC-R 和 LSC-K，文献 [17] 中深层嵌入聚类方法 DEC 和文献 [19] 基于改进可拓展的 nystrom 方法 RSNy 这些算法进行实验对比。 p r p = 1 000 r = 5 β = 10−3 p−500−500− 2 000−10 10−2 000−500−500− p η h = 10−3 本文实验的具体的实验参数设置如下：基于地标点采样的快速谱聚类方法 LSC 有两个参数需要设置，分别为地标点的数目，最近邻地标点的数目，在这里，我们统一设置和。在加权 PageRank 算法中，我们设置收敛阈值。编码器被设置为维数为的多完全连接层，适用于所有的数据集。解码器是维数为的编码器的镜像。并且，将最小批量设置为 256 个，初始学习速率设为 0.1。停止阈值设为，同时将控制嵌入表示空间失真程度的 λ 值设为 0.1。 3.2 实验结果分析 0 ∼ 1 为了验证本文算法的性能，采用文献 [20] 中聚类准确率 ACC 和归一化互信息 NMI 两种聚类度量指标来对聚类结果进行评估和分析比较。ACC 和 NMI 的取值范围都在之间，较高的值表示较好的聚类结果。根据表 2 可以看出，基于聚类准确率 (ACC) 的实验结果表明，提出的加权 PageRank 改进地标表示的自编码谱聚类算法在 USPS、Pendigits、 MNIST、LetterRec、Covtype 数据集上相较于基于 nystrom 的方法、基于地标点采样的快速谱聚类方法、基于深度学习自编码的快速图聚类方法都取得了最好的结果，所提方法在聚类准确率方面都优于以上所提其他方法。特别是在 MNIST 数据集上，GraEn、DLC、DEC 和提出的方法这些基于深度学习自编码的谱聚类方法的聚类结果均明显高于传统 nystrom 的方法、RSNy 方法和基于地标点的方法 (LSC-R，LSC-K)，其中相较于传统 nystrom 的方法，本文所提的方法在 MNIST 数据集上聚类准确率方面提高了 35.91%。相较于基于地标点的快速谱聚类方法 LSC-R，提高了 30.71%。可以看出，所提方法相较于这些方法聚类精度的提高是巨大的。相较于其他几种快速谱聚类方法，所提方法在 MNIST 数据集上分别提高了 18.73% 和 16.91%，总体而言也是相当可观。同时，从表中可以看出基于地标点的方法在 USPS、 Pendigits、LetterRec 和 Covtype 数据集上的聚类准确率比基于自编码的方法在一定程度上还要好。但是所提的方法相较于这些方法而言，实验得到的聚类准确率方面均是最优的。表 1 实验数据集的特征 Table 1 Characteristics of experimental datasets 数据集数据个数类数维数 USPS 9 280 10 256 Pendigits 10 992 10 16 MNIST 70 000 10 784 LetterRec 20 000 26 16 Covtype 581 012 7 54 表 2 不同数据集的聚类准确率 (ACC) 的比较 Table 2 Comparison of clustering accuracy of different data sets 算法 USPS Pendigits MNIST LetterRec Covtype Nystrom 0.681 4 0.739 4 0.537 0 0.301 1 0.223 1 RSNy 0.706 1 0.754 7 0.708 8 0.294 9 0.224 2 LSC-R 0.752 4 0.790 4 0.589 0 0.292 2 0.247 5 LSC-K 0.775 3 0.819 9 0.727 0 0.303 3 0.255 0 GraEn 0.693 1 0.736 4 0.818 2 0.287 2 0.221 8 DLC 0.726 3 0.769 2 0.836 7 0.295 7 0.243 1 DEC 0.749 9 0.790 4 0.865 1 0.297 5 0.249 7 本文算法 0.789 7 0.846 1 0.896 1 0.309 3 0.268 2 ·306· 智能系统学报第 15 卷

第2期储德润，等：加权PageRank改进地标表示的自编码谱聚类算法 ·307· 同时，根据表3可以看出所提的方法与其他 ACC和NMI相较于传统nystrom方法和基于地标几种方法相比在NM上均得到了提高，并且相较点的谱聚类方法而言均有所提高。与DEC方法于其他几种方法是最优的。同样在MNIST数据相比，DEC方法的ACC和NMI分别提高了4.69% 集上，所提的方法相较于传统nystrom方法和基和8.96%，结果表明，联合更新聚类中心和学习嵌于地标的快速谱聚类方法都取得了大幅的提高。入表示可以提高聚类结果，这也适用于其他4个相对于传统nystrom方法和基于地标点的谱聚类数据集。尽管在USPS数据集上，基于自编码的方法LSC-R,所提的方法在NMI上分别提高了方法的聚类精度没有基于地标点方法的聚类精度 40.31%和29.22%，在其他数据集上，所提的方法好，但是在其他几个高维大规模数据集上基于自相较于其他方法而言也均有不同幅度的提高。从编码的方法在聚类精度方面要更好，说明基于自表2和表3中均可以看出，对于最原始的基于自编码的方法和所提的方法更加适用于高维的大规编码的方法GraEn。在MNIST数据集上，它的模数据。表3不同数据集的归一化互信息(NMD的比较 Table 3 Comparison of normalized mutual information (NMI)for different data sets 算法 USPS Pendigits MNIST LetterRec Covertype Nystrom 0.6340 0.6681 0.4802 0.3912 0.0742 RSNy 0.6549 0.6813 0.6255 0.3718 0.0744 LSC-R 0.7541 0.7767 0.5911 0.3734 0.0831 LSC-K 0.7915 0.7808 0.7222 0.3963 0.0902 GraEn 0.6620 0.6555 0.7473 0.3712 0.0719 DLC 0.7351 0.7035 0.7804 0.3835 0.0786 DEC 0.7413 0.7351 0.8369 0.3851 0.0856 本文算法 0.7993 0.7983 0.8833 0.4016 0.0934 总体而言，提出的方法在ACC和NMI上均的聚类指标ACC和NMI的对比实验。从图1中优于其他所列的对比方法。可以看出，随着地标点个数的增加，3种方法的图1和图2显示了选取的3个不同的数据集 ACC也随之增加，总体均呈现增幅形式，最后均中，随着地标点数量p从100-1000变化，基于地趋于稳定，并且所提算法在3个数据集上的标点的谱聚类算法LSC-R和LSC-K与所提方法 ACC均高于其他两种对比算法的ACC。 0.84 0.31 。。用 0.26 0.82 0.24 0.80 030 0.22 霉0.29 毫0.20 救0.76 款0.18 ￥0.74 ·。随机地标点谱聚类 028 ·随机地标点谱聚类。k-means.地标点谱聚类 0.27 。k-means地标点谱聚类￥0.16 ·随机地标点谱聚类 0.72 0.14 +k-means地标点谱聚类 ·本文算法 ·本文算法 0.70 0.26 0.12本文算法物 2004006008001000 2004006008001000 2004006008001000 地标点的个数地标点的个数地标点的个数 (a)Pendigits (b)LetterRec (c)Covertype 图1不同数据集上不同地标点的聚类准确率的比较 Fig.1 Comparison of clustering accuracy of different punctuation points on different datasets 由图2可知，所提的方法在LetterRec和Cov- 的，所以覆盖类型在实际地理上是非常接近的， type数据集上在初始阶段，随着地标点的增加相对于其他手写数字数据集而言，这两个数据集 NMI存在低于其他方法的情况，这是因为所选数据特性更加复杂。并且在选取较少地标点时， LetterRec数据集的字符图像基于26种不同的字采用加权PageRank算法选择地标点与随机选择体，26种字体中的每一个字母都被随机扭曲。地标点和基于k-menas算法选择地标点相比并不 Covertype数据集是一个从地图变量预测森林覆能展现出较大的优势，所以在选取较少地标点时盖类型的数据集，它们都主要是在荒野地区发现聚类性能存在低于其他方法的情况，但在总体情

同时，根据表 3 可以看出所提的方法与其他几种方法相比在 NMI 上均得到了提高，并且相较于其他几种方法是最优的。同样在 MNIST 数据集上，所提的方法相较于传统 nystrom 方法和基于地标的快速谱聚类方法都取得了大幅的提高。相对于传统 nystrom 方法和基于地标点的谱聚类方法 LSC-R，所提的方法在 NMI 上分别提高了 40.31% 和 29.22%，在其他数据集上，所提的方法相较于其他方法而言也均有不同幅度的提高。从表 2 和表 3 中均可以看出，对于最原始的基于自编码的方法 GraEn。在 MNIST 数据集上，它的 ACC 和 NMI 相较于传统 nystrom 方法和基于地标点的谱聚类方法而言均有所提高。与 DEC 方法相比，DEC 方法的 ACC 和 NMI 分别提高了 4.69% 和 8.96%，结果表明，联合更新聚类中心和学习嵌入表示可以提高聚类结果，这也适用于其他 4 个数据集。尽管在 USPS 数据集上，基于自编码的方法的聚类精度没有基于地标点方法的聚类精度好，但是在其他几个高维大规模数据集上基于自编码的方法在聚类精度方面要更好，说明基于自编码的方法和所提的方法更加适用于高维的大规模数据。总体而言，提出的方法在 ACC 和 NMI 上均优于其他所列的对比方法。 p 图 1 和图 2 显示了选取的 3 个不同的数据集中，随着地标点数量从 100~1 000 变化，基于地标点的谱聚类算法 LSC-R 和 LSC-K 与所提方法的聚类指标 ACC 和 NMI 的对比实验。从图 1 中可以看出，随着地标点个数的增加，3 种方法的 ACC 也随之增加，总体均呈现增幅形式，最后均趋于稳定，并且所提算法在 3 个数据集上的 ACC 均高于其他两种对比算法的 ACC。由图 2 可知，所提的方法在 LetterRec 和 Covtype 数据集上在初始阶段，随着地标点的增加 NMI 存在低于其他方法的情况，这是因为所选 LetterRec 数据集的字符图像基于 26 种不同的字体，26 种字体中的每一个字母都被随机扭曲。 Covertype 数据集是一个从地图变量预测森林覆盖类型的数据集，它们都主要是在荒野地区发现的，所以覆盖类型在实际地理上是非常接近的，相对于其他手写数字数据集而言，这两个数据集数据特性更加复杂。并且在选取较少地标点时，采用加权 PageRank 算法选择地标点与随机选择地标点和基于 k-menas 算法选择地标点相比并不能展现出较大的优势，所以在选取较少地标点时聚类性能存在低于其他方法的情况，但在总体情表 3 不同数据集的归一化互信息 (NMI) 的比较 Table 3 Comparison of normalized mutual information (NMI) for different data sets 算法 USPS Pendigits MNIST LetterRec Covertype Nystrom 0.634 0 0.668 1 0.480 2 0.391 2 0.074 2 RSNy 0.654 9 0.681 3 0.625 5 0.371 8 0.074 4 LSC-R 0.754 1 0.776 7 0.591 1 0.373 4 0.083 1 LSC-K 0.791 5 0.780 8 0.722 2 0.396 3 0.090 2 GraEn 0.662 0 0.655 5 0.747 3 0.371 2 0.071 9 DLC 0.735 1 0.703 5 0.780 4 0.383 5 0.078 6 DEC 0.741 3 0.735 1 0.836 9 0.385 1 0.085 6 本文算法 0.799 3 0.798 3 0.883 3 0.401 6 0.093 4 (a) Pendigits 0.84 0.82 0.80 0.78 0.76 0.74 0.72 0.70 200 400 600 地标点的个数聚类准确率 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类 (b) LetterRec 0.31 0.30 0.29 0.28 0.27 0.26 200 400 600 地标点的个数聚类准确率 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类 (c) Covertype 0.26 0.24 0.22 0.20 0.18 0.16 0.14 0.12 200 400 600 地标点的个数聚类准确率 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类图 1 不同数据集上不同地标点的聚类准确率的比较 Fig. 1 Comparison of clustering accuracy of different punctuation points on different datasets 第 2 期储德润，等：加权 PageRank 改进地标表示的自编码谱聚类算法 ·307·

·308· 智能系统学报第15卷况下，随着选取地标点的增多，所提算法展现出到1000左右时趋于稳定，展现出均优于对比算较快的增长优势和较好的聚类性能，在地标点达法的聚类性能。 0.85r 0.42 0.10 则040 是8网；日 0.80 0.38 1g0.36 0.07 0.70 。随机地标点谱聚类 20.34 ￥0.06 .0.32 一随机地标点谐聚类 .0.05 ··随机地标点谱聚类 g0.65 ·k-means地标点谱聚类 ·本文算法 g0.30 +k-means地标点谱聚类 +k-means地标点谱聚类 ·本文算法 g0.04 ·本文算法 0.60 0.28 0.03 2004006008001000 2004006008001000 2004006008001000 地标点的个数地标点的个数地标点的个数 (a)Pendigits (b)LetterRec (c)Covertype 图2不同数据集上不同地标点的归一化互信息的比较 Fig.2 Comparison of normalized mutual information of different punctuation points on different dataset 4结束语 [4]HE Li,RAY N,GUAN Yisheng,et al.Fast large-scale spectral clustering via explicit feature mapping[J].IEEE 本文提出了一种加权PageRank改进地标表 transactions on cybernetics,2019,49(3):1058-1071 示的自编码谱聚类算法，该算法利用加权PageR [5]林大华，杨利锋，邓振云，等.稀疏样本自表达子空间聚 ank算法选取数据亲和图中最具代表性的点作为类算法U.智能系统学报，2016,11（⑤）696-702 地标点，然后以选定的地标点与其他数据点之间 LIN Dahua,YANG Lifeng.DENG Zhenyun,et al.Sparse 的相似度矩阵作为叠加自动编码器的输入，以减 sample self-representation for subspace clustering[J]. 少内存消耗，用叠加式自动编码器代替拉普拉斯 CAAI transactions on intelligent systems,2016,11(5): 矩阵的特征分解，降低了时间复杂度。通过迭代 696-702 优化基于KL散度的聚类损失对聚类进行了进一 [6]YANG Xiaojun,YU Weizhong,WANG Rong,et al.Fast 步细化，结合重构损失和聚类损失考虑了数据的 spectral clustering learning with hierarchical bipartite 局部结构，同时更新了自动编码器和聚类中心的 graph for large-scale data[J/OL].Pattern recognition let- 参数。证明了该方法对不同类型数据集的有效 ters:(2018-06-22).https://www.sciencedirect.com/ 性，实验结果表明，与传统谱聚类算法、基于地标 science/article/abs/pii/S016786551830271X.DOI: 10.1016/J.PATREC.2018.06.024. 点的谱聚类算法和其他基于深度学习自编码的方 [7]LECUN Y.BENGIO Y,HINTON G.Deep learning[J] 法相比，在几个大规模的数据集上，提出的方法 Nature,.2015,521(7553):436-444. 具有更好的聚类性能。在未来，致力于研究更加 [8]SHAHAM U,STANTON K,LI H,et al.SpectralNet: 有效的地标点采样方法，结合优化的自动编码器 spectral clustering using deep neural networks[J]. 从而更好的提高谱聚类的聚类性能。 arXiv:1801.01587.2018. 参考文献： [9]TIAN Fei,GAO Bin,CUI Qing,et al.Learning deep rep- resentations for graph clustering[C]//Proceedings of the [1]LI Mu,BI Wei,KWOK JT,et al.Large-scale nystrom ker- Twenty-Eighth AAAI Conference on Artificial Intelli- nel matrix approximation using randomized SVD[J].IEEE gence.Quebec City,Canada,2014:1293-1299. transactions on neural networks and learning systems, [10]SHAO Ming,LI Sheng,DING Zhengming,et al.Deep 2015.26(1):152-164. linear coding for fast graph clustering[C]//Proceedings of [2]赵晓晓，周治平.结合稀疏表示与约束传递的半监督谱 the 24th International Conference on Artificial Intelli- 聚类算法】.智能系统学报，2018,13(5)：855-863 gence.Buenos Aires,Argentina,2015:3798-3804. ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spec- [11]SONG Chunfeng,LIU Feng,HUANG Yongzhen,et al. tral clustering algorithm combined with sparse representa- Auto-encoder based data clustering[C]//Proceedings of tion and constraint propagation[J].CAAI transactions on the 18th Iberoamerican Congress on Pattern Recognition intelligent systems,2018,13(5):855-863. Havana,Cuba,2013:117-124 [3]DING Shifei,JIA Hongjie,DU Mingjing,et al.A semi-su- [12]PAGE L,BRIN S,MOTWANI R,et al.The PageRank pervised approximate spectral clustering algorithm based citation ranking:bringing order to the web.SIDL- on HMRF model[J].Information sciences,2018,429: WP-1999-0120[R].Technical Report,California:Stan- 215-228 ford Digital Libraries,1999

况下，随着选取地标点的增多，所提算法展现出较快的增长优势和较好的聚类性能，在地标点达到 1 000 左右时趋于稳定，展现出均优于对比算法的聚类性能。 4 结束语本文提出了一种加权 PageRank 改进地标表示的自编码谱聚类算法，该算法利用加权 PageRank 算法选取数据亲和图中最具代表性的点作为地标点，然后以选定的地标点与其他数据点之间的相似度矩阵作为叠加自动编码器的输入，以减少内存消耗，用叠加式自动编码器代替拉普拉斯矩阵的特征分解，降低了时间复杂度。通过迭代优化基于 KL 散度的聚类损失对聚类进行了进一步细化，结合重构损失和聚类损失考虑了数据的局部结构，同时更新了自动编码器和聚类中心的参数。证明了该方法对不同类型数据集的有效性，实验结果表明，与传统谱聚类算法、基于地标点的谱聚类算法和其他基于深度学习自编码的方法相比，在几个大规模的数据集上，提出的方法具有更好的聚类性能。在未来，致力于研究更加有效的地标点采样方法，结合优化的自动编码器从而更好的提高谱聚类的聚类性能。参考文献： LI Mu, BI Wei, KWOK J T, et al. Large-scale nyström kernel matrix approximation using randomized SVD[J]. IEEE transactions on neural networks and learning systems, 2015, 26(1): 152–164. [1] 赵晓晓, 周治平. 结合稀疏表示与约束传递的半监督谱聚类算法 [J]. 智能系统学报, 2018, 13(5): 855–863. ZHAO Xiaoxiao, ZHOU Zhiping. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J]. CAAI transactions on intelligent systems, 2018, 13(5): 855–863. [2] DING Shifei, JIA Hongjie, DU Mingjing, et al. A semi-supervised approximate spectral clustering algorithm based on HMRF model[J]. Information sciences, 2018, 429: 215–228. [3] HE Li, RAY N, GUAN Yisheng, et al. Fast large-scale spectral clustering via explicit feature mapping[J]. IEEE transactions on cybernetics, 2019, 49(3): 1058–1071. [4] 林大华, 杨利锋, 邓振云, 等. 稀疏样本自表达子空间聚类算法 [J]. 智能系统学报, 2016, 11(5): 696–702. LIN Dahua, YANG Lifeng, DENG Zhenyun, et al. Sparse sample self-representation for subspace clustering[J]. CAAI transactions on intelligent systems, 2016, 11(5): 696–702. [5] YANG Xiaojun, YU Weizhong, WANG Rong, et al. Fast spectral clustering learning with hierarchical bipartite graph for large-scale data[J/OL]. Pattern recognition letters: (2018-06-22). https://www.sciencedirect.com/ science/article/abs/pii/S016786551830271X. DOI: 10.1016/J.PATREC.2018.06.024. [6] LECUN Y, BENGIO Y, HINTON G. Deep learning[J]. Nature, 2015, 521(7553): 436–444. [7] SHAHAM U, STANTON K, LI H, et al. SpectralNet: spectral clustering using deep neural networks[J]. arXiv:1801.01587, 2018. [8] TIAN Fei, GAO Bin, CUI Qing, et al. Learning deep representations for graph clustering[C]//Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Québec City, Canada, 2014: 1293−1299. [9] SHAO Ming, LI Sheng, DING Zhengming, et al. Deep linear coding for fast graph clustering[C]//Proceedings of the 24th International Conference on Artificial Intelligence. Buenos Aires, Argentina, 2015: 3798−3804. [10] SONG Chunfeng, LIU Feng, HUANG Yongzhen, et al. Auto-encoder based data clustering[C]//Proceedings of the 18th Iberoamerican Congress on Pattern Recognition. Havana, Cuba, 2013: 117−124. [11] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web. SIDL− WP−1999−0120[R]. Technical Report, California: Stanford Digital Libraries, 1999. [12] (a) Pendigits 0.85 0.80 0.75 0.70 0.65 0.60 200 400 600 地标点的个数归一化互信息 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类 (b) LetterRec 0.42 0.40 0.38 0.36 0.34 0.32 0.30 0.28 200 400 600 地标点的个数归一化互信息 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类 (c) Covertype 0.10 0.09 0.08 0.07 0.06 0.05 0.04 0.03 200 400 600 地标点的个数归一化互信息 800 1 000 随机地标点谱聚类本文算法 k-means地标点谱聚类图 2 不同数据集上不同地标点的归一化互信息的比较 Fig. 2 Comparison of normalized mutual information of different punctuation points on different dataset ·308· 智能系统学报第 15 卷

点击进入文档下载页（PDF格式）

已到末页，全文结束