第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 卷
第2期 储德润,等:加权PageRank改进地标表示的自编码谱聚类算法 ·309· [13]XING W,GHORBANI A.Weighted PageRank al- York,USA,2014:661-670 gorithm[C]//Proceedings of Second Annual Conference [19]LI Mu,KWOK J T,LU Baoliang.Making large-scale on Communication Networks and Services Research.Fre- Nystrom approximation possible[C]//Proceedings of the dericton,Canada,2004:305-314. 27th International Conference on Machine Learning. [14]CHEN Xinlei,CAI Deng.Large scale spectral clustering Haifa,Israel,2010:631-638. with landmark-based representation[C]//Proceedings of [20]CHEN W Y,SONG Yangqiu,Bai Hongjie,et al.Parallel the Twenty-Fifth AAAI Conference on Artificial Intelli- spectral clustering in distributed systems[J].IEEE transac- gence.San Francisco,USA,2011:313-318. tions on pattern analysis and machine intelligence,2011. [15]CAI Deng,CHEN Xinlei.Large scale spectral clustering 33(3:568-586 via landmark-based sparse representation[J].IEEE trans- 作者简介: actions on cybernetics,2015,45(8):1669-1680. 储德润,硕土研究生,主要研究方 [16]BENGIO Y,COURVILLE A,VINCENT P.Representa- 向为数据挖掘。 tion learning:a review and new perspectives[J].IEEE transactions on pattern analysis and machine intelligence, 2013,35(8)1798-1828. [17]XIE Junyuan,GIRSHICK R B,FARHADI A.Unsuper- vised deep embedding for clustering analysis[C]//Pro- ceedings of the 33rd International Conference on Ma- 周治平,教授,博士,主要研究方 向为智能检测、网络安全,发表学术论 chine Learning.New York,USA,2016:478-487. 文20余篇。 [18]LI Mu,ZHANG Tong,CHEN Yuqiang,et al.Efficient mini-batch training for stochastic optimization[C]//Pro- ceedings of the 20th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining.New
XING W, GHORBANI A. Weighted PageRank algorithm[C]//Proceedings of Second Annual Conference on Communication Networks and Services Research. Fredericton, Canada, 2004: 305−314. [13] CHEN Xinlei, CAI Deng. Large scale spectral clustering with landmark-based representation[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, USA, 2011: 313−318. [14] CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE transactions on cybernetics, 2015, 45(8): 1669–1680. [15] BENGIO Y, COURVILLE A, VINCENT P. Representation learning: a review and new perspectives[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(8): 1798–1828. [16] XIE Junyuan, GIRSHICK R B, FARHADI A. Unsupervised deep embedding for clustering analysis[C]//Proceedings of the 33rd International Conference on Machine Learning. New York, USA, 2016: 478−487. [17] LI Mu, ZHANG Tong, CHEN Yuqiang, et al. Efficient mini-batch training for stochastic optimization[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New [18] York, USA, 2014: 661−670. LI Mu, KWOK J T, LU Baoliang. Making large-scale Nyström approximation possible[C]//Proceedings of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 631−638. [19] CHEN W Y, SONG Yangqiu, Bai Hongjie, et al. Parallel spectral clustering in distributed systems[J]. IEEE transactions on pattern analysis and machine intelligence, 2011, 33(3): 568–586. [20] 作者简介: 储德润,硕士研究生,主要研究方 向为数据挖掘。 周治平,教授,博士,主要研究方 向为智能检测、网络安全,发表学术论 文 20 余篇。 第 2 期 储德润,等:加权 PageRank 改进地标表示的自编码谱聚类算法 ·309·