【机器学习】结合度量融合和地标表示的自编码谱聚类算法

第15卷第4期 智能系统学报 Vol.15 No.4 2020年7月 CAAI Transactions on Intelligent Systems Jul.2020 D0L:10.11992tis.201911039 结合度量融合和地标表示的自编码谱聚类算法 张敏，周治平2 (1.江南大学物联网工程学院，江苏无锡214122,2.江南大学物联网技术应用教育部工程研究中心，江苏无 锡214122) 摘要：针对大多数现有谱聚类算法处理大规模数据集时面临聚类精度低、大规模相似度矩阵存储开销大的问 题，提出一种结合度量融合和地标表示的自编码谱聚类算法。引入相对质量概念进行节点评估，选取最具代表 性的点作为地标点，通过稀疏表示近似获得图相似度矩阵，以降低存储开销。同时考虑到近邻样本的几何分布 和拓扑分布的信息，融合欧氏距离与Kendall Tau距离来度量地标点与其他样本之间的相似度，提高聚类精度： 以栈式自编码器取代拉普拉斯矩阵特征分解，将所获得的相似度矩阵作为自编码器的输入，通过联合学习嵌入 表示和聚类来进一步提高聚类精度。在5个大规模数据集上的实验验证了本文算法的有效性。 关键词：大规模数据集；度量融合：地标表示：相对质量：稀疏表示：栈式自编码器：联合学习：嵌入表示 中图分类号：TP18文献标志码：A文章编号：1673-4785(2020)04-0687-10 中文引用格式：张敏，周治平.结合度量融合和地标表示的自编码谱聚类算法，智能系统学报，2020,15(4)：687-696. 英文引用格式：ZHANG Min,ZHOU Zhiping.An autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation[J].CAAI transactions on intelligent systems,2020,15(4):687-696. An autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation ZHANG Min',ZHOU Zhiping2 (1.School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China;2.Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China) Abstract:Most existing spectral clustering algorithms are faced with low clustering accuracy and costly large-scale sim- ilarity matrix storage.Aiming at these problems,this paper proposes an autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation.First,instead of random sampling,the concept of relative mass is introduced to evaluate node quality.Based on this,the most representative nodes are selected as the landmark points and the graph similarity matrix is approximately obtained by sparse representation.Meanwhile,considering the geometric and topological distribution of the nearest neighbor samples,the Euclidean distance and Kendall Tau distance are integrated to measure the similarity between the landmarks and the other points,so as to increase the clustering pre- cision.A stacked autoencoder is then used to replace the Laplace matrix eigen-decomposition,and the obtained similar- ity matrix is taken as the autoencoder's input.The clustering accuracy is further improved by joint learning of embed- ded representation and clustering.Experiments on five large-scale datasets validate the effectiveness of our algorithm. Keywords:large-scale datasets;metric fusion;landmark representation;relative mass;sparse representation;stacked au- toencoder;joint learning;embedded representation 聚类旨在根据数据点之间的相似性将其划分 算法，缺乏处理复杂数据结构的能力，当样本空 到不同的簇，使簇内相似度最大，簇间相似度最 间非凸时，易陷入局部最优。近年来，谱聚类算 小u。传统聚类方法如K-means算法和模糊聚类 法因其可在任意形状空间内进行聚类，并收敛到 收稿日期：2019-12-02. 全局最优，在非凸数据集表现出良好聚类性能， 通信作者：张敏.E-mail:150618823731@163.com 在人脸识别、社区检测、图像分割等领域有着广

DOI: 10.11992/tis.201911039 结合度量融合和地标表示的自编码谱聚类算法 张敏1 ，周治平1,2 （1. 江南大学 物联网工程学院，江苏 无锡 214122; 2. 江南大学 物联网技术应用教育部工程研究中心，江苏 无 锡 214122） 摘 要：针对大多数现有谱聚类算法处理大规模数据集时面临聚类精度低、大规模相似度矩阵存储开销大的问 题，提出一种结合度量融合和地标表示的自编码谱聚类算法。引入相对质量概念进行节点评估，选取最具代表 性的点作为地标点，通过稀疏表示近似获得图相似度矩阵，以降低存储开销。同时考虑到近邻样本的几何分布 和拓扑分布的信息，融合欧氏距离与 Kendall Tau 距离来度量地标点与其他样本之间的相似度，提高聚类精度； 以栈式自编码器取代拉普拉斯矩阵特征分解，将所获得的相似度矩阵作为自编码器的输入，通过联合学习嵌入 表示和聚类来进一步提高聚类精度。在 5 个大规模数据集上的实验验证了本文算法的有效性。 关键词：大规模数据集；度量融合；地标表示；相对质量；稀疏表示；栈式自编码器；联合学习；嵌入表示 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)04−0687−10 中文引用格式：张敏, 周治平. 结合度量融合和地标表示的自编码谱聚类算法 [J]. 智能系统学报, 2020, 15(4): 687–696. 英文引用格式：ZHANG Min, ZHOU Zhiping. An autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation[J]. CAAI transactions on intelligent systems, 2020, 15(4): 687–696. An autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation ZHANG Min1 ，ZHOU Zhiping1,2 (1. School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China; 2. Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: Most existing spectral clustering algorithms are faced with low clustering accuracy and costly large-scale sim￾ilarity matrix storage. Aiming at these problems, this paper proposes an autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation. First, instead of random sampling, the concept of relative mass is introduced to evaluate node quality. Based on this, the most representative nodes are selected as the landmark points and the graph similarity matrix is approximately obtained by sparse representation. Meanwhile, considering the geometric and topological distribution of the nearest neighbor samples,the Euclidean distance and Kendall Tau distance are integrated to measure the similarity between the landmarks and the other points, so as to increase the clustering pre￾cision. A stacked autoencoder is then used to replace the Laplace matrix eigen-decomposition, and the obtained similar￾ity matrix is taken as the autoencoder’s input. The clustering accuracy is further improved by joint learning of embed￾ded representation and clustering. Experiments on five large-scale datasets validate the effectiveness of our algorithm. Keywords: large-scale datasets; metric fusion; landmark representation; relative mass; sparse representation; stacked au￾toencoder; joint learning; embedded representation 聚类旨在根据数据点之间的相似性将其划分 到不同的簇，使簇内相似度最大，簇间相似度最 小 [1]。传统聚类方法如 K-means 算法和模糊聚类 算法，缺乏处理复杂数据结构的能力，当样本空 间非凸时，易陷入局部最优。近年来，谱聚类算 法因其可在任意形状空间内进行聚类，并收敛到 全局最优，在非凸数据集表现出良好聚类性能， 在人脸识别、社区检测、图像分割等领域有着广 收稿日期：2019−12−02. 通信作者：张敏. E-mail：15061882373_1@163.com. 第 15 卷第 4 期 智 能 系 统 学 报 Vol.15 No.4 2020 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2020

·688… 智能系统学报 第15卷 泛的应用。 均值优化Ncut的目标函数，避免拉普拉斯矩阵的 谱聚类将聚类问题转化为图分割问题)，通 直接特征分解。Tian等i6证明了自编码器和谱 过寻找最优子图对数据点进行划分。但现存的多 聚类之间的相似性，利用栈式自编码器代替特征 数谱聚类算法在处理大规模数据集时，涉及相似 分解，有效降低计算复杂度。Banijamali等 度矩阵构造和对应的拉普拉斯矩阵分解，往往需 提出将深层结构与地标表示相结合，实现快速且 要高昂的时空开销，高计算成本成为制约其在大 准确的聚类。但上述提及的谱聚类算法均使用传 规模场景应用中的瓶颈。为实现对大规模数据 统基于欧氏距离度量方案，并不能完全反映数据 的高效聚类分析，提升谱聚类算法的扩展性，大 复杂的空间分布特性。光俊叶等割提出融合欧 量研究方法被提出。Nystrom扩展作为一种近似 氏距离和Kendall Tau距离的谱聚类方法，充分利 低秩矩阵的有效方法，利用抽样技术，减少特征 用不同相似性度量从不同角度获取数据信息的优 分解复杂度。针对抽样策略的选择，Zhan等 势，全面反映底层结构信息。 设计了一种自适应的Nystrom采样方法，通过多 本文在地标点采样8的理论基础上，采用基 次遍历并更新抽样概率，选取更有意义的样本 于网页质量的PageRank算法计算节点的重要性， 点，以较小的抽样集获得理想的聚类效果。考虑 作为抽样策略依据代替随机抽样，选取代表点作 到高斯核参数调整问题，Yang等提出一种基于 为地标点，通过稀硫表示近似获得图相似度矩 层次二部图的谱聚类算法，通过金字塔结构式的 阵，以降低存储开销。同时为全面反映数据底层 多层锚点构造层次二部图降低计算复杂度，此外 结构信息，将欧氏距离与Kendall Tau距离两种度 采用无参数邻接分配策略构造相似度矩阵，避免 量方案融合，用局部标准差代替特定的缩放尺 参数调优过程。蔡登等⑧-提出基于地标表示的 度，构造融合多度量方式的自适应相似度矩阵， 研究，择取具有代表性的数据点作为地标点，通 以提高聚类精度。此外，用栈式自编码器代替特 过地标点的稀疏线性组合近似构造图相似度矩 征分解，在联合学习框架中进行嵌入表示学习和 阵，从而有效降低谱嵌入的计算复杂度，该算法 聚类，避免微调环节覆盖之前所得最优参数，从 一定程度上解决了矩阵存储开销问题，但其随机 而进一步提高聚类精度。 采样确定地标点的方式会造成聚类结果的不稳 定，故而地标点的选取为算法的关键。叶茂等 1相关算法理论 利用由近似奇异向量的长度计算的抽样概率来进 1.1基于QPR的地标选择 行抽样，以保证聚类结果的稳定性和精度。 PageRank算法采用平均分配思想，将节点权 Zhang等川提出一种基于增量视角的抽样框架， 重划分给人链节点，忽略节点质量存在差异性， 每一个要抽样的点是由先前选定的地标点决定， 改进后的加权PageRank算法通过传入链路权重 在地标点之间建立显式关系。但这些改进的方法 在择取地标点时都忽略了节点的拓扑属性，其可 wa及传出链路权重w,2个参数1，依据网络 结构有区分地进行权值分配，但该参数在迭代过 有效描述亲和图整体结构特性，对于捕捉高维数 据空间的拓扑信息有着重要意义。故邓思雨等叫 程中是固定存在的，存在局限性。基于网页质量 将PageRank分值作为样本信息量的度量指标， 的PageRank算法(page quality based PageRank al- Rafailid等l)提出一种基于地标选择的快速谱聚 gorithm,QPR)定义了相对质量Q(a,用于迭代过 程协助分配PR值，动态评估每个节点的质量，其 类算法，根据加权PageRank算法选择亲和图中最 计算公式为 重要的节点作为地标点。Liu等将数据点视为 PR(a) web页面，数据点之间的距离类似为链路间的权 Q(a)= 重，采用PageRank算法评估数据点的重要性，选 PR(b) MPR(a) (1) 择代表点。该方法能够区分球状和非球状的簇， 且减少噪声点的负面影响。以上这些改进的谱聚 MPR(a)=max PR(b heB(a) 类算法虽然降低了计算复杂度，仍然需要对矩阵 式中：B(a)表示节点a的入链节点集合：MPR(a) 进行特征分解。Jia等设计了一种无需特征分 表示a的入链节点集合中的最大PR值。相对质 解的大规模近似Ncut谱聚类算法，一方面通过对 量Q(a)将迭代过程中a的人链集合与其本身的 数据点的采样推断数据集的全局特征，减少归一 PR值信息结合，对于具有相同PR值的节点，拥 化切割的空间需求，另一方面利用近似加权核k 有较大入链PR值的节点将得到加权，从而在下

泛的应用[2]。 谱聚类将聚类问题转化为图分割问题[3] ，通 过寻找最优子图对数据点进行划分。但现存的多 数谱聚类算法在处理大规模数据集时，涉及相似 度矩阵构造和对应的拉普拉斯矩阵分解，往往需 要高昂的时空开销，高计算成本成为制约其在大 规模场景应用中的瓶颈[4]。为实现对大规模数据 的高效聚类分析，提升谱聚类算法的扩展性，大 量研究方法被提出。Nyström 扩展作为一种近似 低秩矩阵的有效方法，利用抽样技术，减少特征 分解复杂度[5]。针对抽样策略的选择，Zhan 等 [6] 设计了一种自适应的 Nyström 采样方法，通过多 次遍历并更新抽样概率，选取更有意义的样本 点，以较小的抽样集获得理想的聚类效果。考虑 到高斯核参数调整问题，Yang 等 [7] 提出一种基于 层次二部图的谱聚类算法，通过金字塔结构式的 多层锚点构造层次二部图降低计算复杂度，此外 采用无参数邻接分配策略构造相似度矩阵，避免 参数调优过程。蔡登等[8-9] 提出基于地标表示的 研究，择取具有代表性的数据点作为地标点，通 过地标点的稀疏线性组合近似构造图相似度矩 阵，从而有效降低谱嵌入的计算复杂度，该算法 一定程度上解决了矩阵存储开销问题，但其随机 采样确定地标点的方式会造成聚类结果的不稳 定，故而地标点的选取为算法的关键。叶茂等[10] 利用由近似奇异向量的长度计算的抽样概率来进 行抽样，以保证聚类结果的稳定性和精度。 Zhang 等 [11] 提出一种基于增量视角的抽样框架， 每一个要抽样的点是由先前选定的地标点决定， 在地标点之间建立显式关系。但这些改进的方法 在择取地标点时都忽略了节点的拓扑属性，其可 有效描述亲和图整体结构特性，对于捕捉高维数 据空间的拓扑信息有着重要意义。故邓思雨等[12] 将 PageRank 分值作为样本信息量的度量指标， Rafailid 等 [13] 提出一种基于地标选择的快速谱聚 类算法，根据加权 PageRank 算法选择亲和图中最 重要的节点作为地标点。Liu 等 [14] 将数据点视为 web 页面，数据点之间的距离类似为链路间的权 重，采用 PageRank 算法评估数据点的重要性，选 择代表点。该方法能够区分球状和非球状的簇， 且减少噪声点的负面影响。以上这些改进的谱聚 类算法虽然降低了计算复杂度，仍然需要对矩阵 进行特征分解。Jia 等 [15] 设计了一种无需特征分 解的大规模近似 Ncut 谱聚类算法，一方面通过对 数据点的采样推断数据集的全局特征，减少归一 化切割的空间需求，另一方面利用近似加权核 k- 均值优化 Ncut 的目标函数，避免拉普拉斯矩阵的 直接特征分解。Tian 等 [16] 证明了自编码器和谱 聚类之间的相似性，利用栈式自编码器代替特征 分解，有效降低计算复杂度。Banijamali 等 [ 1 7 ] 提出将深层结构与地标表示相结合，实现快速且 准确的聚类。但上述提及的谱聚类算法均使用传 统基于欧氏距离度量方案，并不能完全反映数据 复杂的空间分布特性。光俊叶等[18] 提出融合欧 氏距离和 Kendall Tau 距离的谱聚类方法，充分利 用不同相似性度量从不同角度获取数据信息的优 势，全面反映底层结构信息。 本文在地标点采样[8-9] 的理论基础上，采用基 于网页质量的 PageRank 算法计算节点的重要性， 作为抽样策略依据代替随机抽样，选取代表点作 为地标点，通过稀疏表示近似获得图相似度矩 阵，以降低存储开销。同时为全面反映数据底层 结构信息，将欧氏距离与 Kendall Tau 距离两种度 量方案融合，用局部标准差代替特定的缩放尺 度，构造融合多度量方式的自适应相似度矩阵， 以提高聚类精度。此外，用栈式自编码器代替特 征分解，在联合学习框架中进行嵌入表示学习和 聚类，避免微调环节覆盖之前所得最优参数，从 而进一步提高聚类精度。 1 相关算法理论 1.1 基于 QPR 的地标选择 w in (a,b) w out (a,b) Q(a) PageRank 算法采用平均分配思想，将节点权 重划分给入链节点，忽略节点质量存在差异性， 改进后的加权 PageRank 算法通过传入链路权重 及传出链路权重 2 个参数[13] ，依据网络 结构有区分地进行权值分配，但该参数在迭代过 程中是固定存在的，存在局限性。基于网页质量 的 PageRank 算法[19] (page quality based PageRank al￾gorithm, QPR) 定义了相对质量 ，用于迭代过 程协助分配 PR 值，动态评估每个节点的质量，其 计算公式为 Q(a) = PR(a) ( ∑ b∈B(a) PR(b) )/MPR(a) MPR(a) = max b∈B(a) PR(b) (1) B(a) a MPR(a) a Q(a) a 式中： 表示节点 的入链节点集合； 表示 的入链节点集合中的最大 PR 值。相对质 量 将迭代过程中 的入链集合与其本身的 PR 值信息结合，对于具有相同 PR 值的节点，拥 有较大入链 PR 值的节点将得到加权，从而在下 ·688· 智 能 系 统 学 报 第 15 卷

第4期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·689· 一轮迭代中具有更高PR值。随着多轮迭代，节 性。其聚类结果可能受到异常值影响，因为局部 点各自的PR值出现差距，高质量的节点能较快 尺度参数σ，可能扭曲了离群值。为避免该问题， 积累PR值，获得较高排名。该算法计算PageR- 文献[22]提出一种局部标准差谱聚类算法，定义 ank的公式为 PR(@=d∑PR(b)Pr(b-→a)+-d 局部标准差d= -》p,),其表示样本 1 l (2) x的前k个近邻的局部标准差，相似度矩阵的元 m--QoQc 素则如式(4)所示，尽可能地反映数据集的原始 分布： 式中：Pr(b→a)表示节点b分配给节点a的PR值 -p(xi,xi) 比重，F(b)表示节点b的出链节点集合，即F(b)= exp i≠i (4) {al(b,a)eE,d是一个阻尼因子，通常设置为0.85， n为节点个数。当所有节点满足式(3)时，迭代过 程停止： 2本文算法 PR(d)-PR(aas≤B (3) 2.1结合度量融合与地标表示的相似度矩阵 PR(@)aer 由1.2节可以看出谱聚类算法中所构造的相 该式表示上一次迭代与当前迭代之间的归一 似度矩阵维度为n×n,对于大规模数据集无法实 化差值，其中，B是预先设置的停止阈值。当满足 现高效的谱嵌入，空间计算复杂度较高。对此文 该式时，停止迭代，选择PR值最高的p节点作为 献[8-9]提出选取pn个地标点作为特征代表 地标点。 点，将所有样本近似表示为这些地标点的线性组 1.2自适应谱聚类算法 合，有效利用稀疏表示矩阵近似获得图相似度矩 相似度矩阵的构造是谱聚类算法的一个重要 阵。本文采用1.1节的基于QPR的地标选择方 步骤，而高斯核函数是构造相似度矩阵最常用的 式，选择P℉值最高的p个节点作为地标点。对 度量方法之一。给定数据集X=[x1,2,…,xJ∈R, 于任意给定样本，其近似样本可表示为 i=1,2,…,n,拟将其划分为K簇。谱聚类算法将 聚类问题视为无向图G=(V,E)的多路划分问题， 其中顶点集V={x,x2,…,xn}为所有样本集合，E= 尺1 {A}表示顶点间边的权重集合，A=(A)∈R, 式中：y,是地标点矩阵YeRp的列向量，Z为稀 i,j=1,2,…,n即为所需构造的相似度矩阵，其元素 疏表示矩阵Z∈Rm的第i行、第j列元素，表示 被定义为 所选取的p个地标点与所有样本点之间的成对相 似性。根据稀疏编码策略，与y越接近，Z越 -p(xi,x） exp i Ai= 2r2 大，而若y,不在样本x的k近邻内，则将Z置为 0,i=j 0,通过引入k近邻点来度量点对之间的局部亲和 式中：p(x,x)指样本x与x之间的一种距离度量 力。相应稀疏表示矩阵Z的元素为 方法，参数σ是手动给出的固定缩放参数，并不 A元 jE KNN() 具有自适应性，难以体现数据的真实分布20。自 Ami 适应谱聚类算法2！针对全局尺度参数不能有效 mEKNN(x) (5) 0,jKNN(x) 反映数据集真实分布信息，提出了局部尺度参数 的概念，根据样本x的第k个近邻定义样本x的 式中：A:表示样本：与地标点y,之间的相似度， 局部尺度参数σ：=px,x,该算法定义相似度矩 采用式(4)计算方式，尽可能反映数据集的原始 阵元素为 分布。在计算点对相似性时往往采用欧氏距离传 统度量方式，一些邻域有用信息容易被忽略。 -p(xi,xj) exp i≠j 200 Kendall Tau距离是衡量两个等级列表之间两两不 0,i=i 一致的数量，即求两个排列之间的逆序数，反映了 特定的缩放参数：可根据样本x:和x的邻 两个排列的相似程度。对于两排列L=(L,L2,…, 域点进行自调。该算法虽然在一定程度上克服了 Lni)及L2=(L2,L2,…,La),它们之间的Kendall 自适应谱聚类算法的缺点，但也有一定的局限 Tau距离定义为

一轮迭代中具有更高 PR 值。随着多轮迭代，节 点各自的 PR 值出现差距，高质量的节点能较快 积累 PR 值，获得较高排名。该算法计算 PageR￾ank 的公式为 PR(a) = d ∑ b∈B(a) PR(b)Pr(b → a)+ (1−d) n Pr(b → a) = Q(a)/ ∑ c∈F(b) Q(c) (2) Pr(b → a) b a F(b) b F(b) = {a|(b,a) ∈ E} d n 式中： 表示节点 分配给节点 的 PR 值 比重， 表示节点 的出链节点集合，即 ， 是一个阻尼因子，通常设置为 0.85， 为节点个数。当所有节点满足式 (3) 时，迭代过 程停止： PR(a)iter−1 −PR(a)iter PR(a)iter ⩽ β (3) β p 该式表示上一次迭代与当前迭代之间的归一 化差值，其中， 是预先设置的停止阈值。当满足 该式时，停止迭代，选择 PR 值最高的 节点作为 地标点。 1.2 自适应谱聚类算法 X = [x1, x2,··· , xn] ∈ R n×d , i = 1,2,··· ,n K G = (V,E) V = {x1, x2,··· , xn} E = {Ai j} A = (Ai j) ∈ R n×n i, j = 1,2,··· ,n 相似度矩阵的构造是谱聚类算法的一个重要 步骤，而高斯核函数是构造相似度矩阵最常用的 度量方法之一。给定数据集 ，拟将其划分为 簇。谱聚类算法将 聚类问题视为无向图 的多路划分问题， 其中顶点集 为所有样本集合， 表示顶点间边的权重集合， ， 即为所需构造的相似度矩阵，其元素 被定义为 Ai j =    exp( −ρ 2 (xi , xj) 2σ2 ) , i , j 0, i = j ρ(xi , xj) xi xj σ xi k xi σi = ρ(xi , xk) 式中： 指样本 与 之间的一种距离度量 方法，参数 是手动给出的固定缩放参数，并不 具有自适应性，难以体现数据的真实分布[20]。自 适应谱聚类算法[21] 针对全局尺度参数不能有效 反映数据集真实分布信息，提出了局部尺度参数 的概念，根据样本 的第 个近邻定义样本 的 局部尺度参数 ，该算法定义相似度矩 阵元素为 Ai j =    exp( −ρ 2 (xi , xj) 2σiσj ) , i , j 0, i = j 特定的缩放参数 σi 可根据样本 xi 和 xj 的邻 域点进行自调。该算法虽然在一定程度上克服了 自适应谱聚类算法的缺点，但也有一定的局限 σi σstd_i = vt 1 k−1 ∑k t=1 ρ 2 (xi , xt) xi k 性。其聚类结果可能受到异常值影响，因为局部 尺度参数 可能扭曲了离群值。为避免该问题， 文献 [22] 提出一种局部标准差谱聚类算法，定义 局部标准差 ，其表示样本 的前 个近邻的局部标准差，相似度矩阵的元 素则如式 (4) 所示，尽可能地反映数据集的原始 分布： Ai j =    exp( −ρ 2 (xi , xj) 2σstd_iσstd_ j ) , i , j 0, i = j (4) 2 本文算法 2.1 结合度量融合与地标表示的相似度矩阵 n×n p ≪ n p xi xˆi 由 1.2 节可以看出谱聚类算法中所构造的相 似度矩阵维度为 ，对于大规模数据集无法实 现高效的谱嵌入，空间计算复杂度较高。对此文 献 [8-9] 提出选取 个地标点作为特征代表 点，将所有样本近似表示为这些地标点的线性组 合，有效利用稀疏表示矩阵近似获得图相似度矩 阵。本文采用 1.1 节的基于 QPR 的地标选择方 式，选择 PR 值最高的 个节点作为地标点。对 于任意给定样本 ，其近似样本 可表示为 xˆi = ∑p j=1 Zjiyj yj Y ∈ R d×p Zi j Z ∈ R p×n p xi yj Zji yj xi k Zji k Z 式中： 是地标点矩阵 的列向量， 为稀 疏表示矩阵 的第 i 行、第 j 列元素，表示 所选取的 个地标点与所有样本点之间的成对相 似性。根据稀疏编码策略， 与 越接近， 越 大，而若 不在样本 的 近邻内，则将 置为 0，通过引入 近邻点来度量点对之间的局部亲和 力。相应稀疏表示矩阵 的元素为 Zji =    ∑ Aji m∈KNN(xi) Ami , j ∈ KNN(xi) 0, j < KNN(xi) (5) Aji xi yj L1 = (L11,L21,··· , Ln1) L2 = (L12,L22,··· ,Ln2) 式中： 表示样本 与地标点 之间的相似度， 采用式 (4) 计算方式，尽可能反映数据集的原始 分布。在计算点对相似性时往往采用欧氏距离传 统度量方式，一些邻域有用信息容易被忽略。 Kendall Tau 距离是衡量两个等级列表之间两两不 一致的数量，即求两个排列之间的逆序数，反映了 两个排列的相似程度。对于两排列 及 ，它们之间的 Kendall Tau 距离定义为 第 4 期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·689·

·690· 智能系统学报 第15卷 KT(L.L)=((i,j):iLn)A(L2>Lp)) (6) 式中：L:和L2表示L,和L2中第i个元素各自的 式中：F出表示基于欧氏距离度量的稀疏表示矩 序号，H为集合中元素的个数。若两排列相同，则 阵在h步迭代更新后的状态矩阵，F2表示基于 KT(L1,L2)为0；若两排列互为逆序，KT(L1,L2)为 Kendall Tau距离度量的矩阵在h步迭代更新后的 n(n-1)/2。通过除以n(n-1)/2进行规范化处理， 状态矩阵。此步骤每次更新状态矩阵时，生成两 使KT(L,L2)位于区间[0,1]内。 个并行交换扩散过程，在h步后，融合两种度量 若将欧氏距离及Kendall Tau距离两种度量 方式的稀疏表示矩阵Z: 方式融合，生成增强的相似度矩阵，能在反映点对 之间地理相似性的同时考虑点之间的拓扑逻辑相 Z=P+r (9) 2 似性。将点：和x之间的欧氏距离表示为P(x,x, 从概率角度分析该交叉扩散过程，对于状态 Kendall Tau距离表示为p2(,x)。在基于欧氏距 矩阵F,依据扩散映射4]可定义进行h步迭代 离对样本进行排序，然后利用Kendall Tau距离度 时的扩散距离M(位，)=F'i)-F':州，扩散 量两个样本之间的全局关系，全面反映数据的底 过程即是将数据空间映射到扩散空间R的过 层结构信息。对于样本x,基于欧氏距离计算与 程，本质上每个样本都可由自身与其他数据点间 p个地标点之间的相似度，可得一有序序列：List= 相似度表示。为实现核矩阵之间的融合，对于样本 [p(,xP1(,x),…,P(mx,…p(p,x小，同样的 x”eR,引入线性算子Z②，经过x,=Z2x+E 对于样本x可得有序序列Lst,那么结合式(6)， (ε为白噪声)线性运算后，由扩散映射性质可获 样本：和x之间的Kendall Tau距离则为 得x,的边缘分布2，同理可得x,。该交叉扩散 p2(xi,x)=KT(Listi,Listj) 过程的实质并非在原始数据空间中进行线性投 从度量融合的角度来看，大多数主流的思想 影，而是在扩散空间中进行迭代线性运算的，这 都是通过线性组合多个亲和图来获得互补的相似 样对样本的噪声和规模具有较强鲁棒性，且融合 信息2)，然而这个线性组合对分配给每个度量的 了整个样本集的相似流形的内在结构。 权重很敏感，且来自多个亲和图的互补信息并非 在由式(9)获得稀疏表示矩阵Z后，通过该 线性相关的。为探索两种距离度量方案相互融合 矩阵来近似获得数据X的规范化图亲和矩阵， 的思想，综合考虑相邻点的几何分布和拓扑分 布，受到联合训练算法的启发，采用基于消息传 即：G=2T2eRm,其中2=D-PZ,D为度矩阵， 递理论和交叉扩散过程的融合方法。以完全相似 其元素一般为D:=∑，乙，为进一步降低计算复杂 矩阵作为初始状态矩阵，即对式（⑤）不考虑k近邻 度，采用文献[2]计算度矩阵元素Da=diag(22), 点而构建相似矩阵，该初始状态矩阵F携带关于 其中2=2，为Px1的向量，其第k个元素为 每个地标点与其他所有样本点之间相似性的完整 扫1 信息，对应元素为 2的第k行元素之和，该计算D的时间复杂度为 O(p)。结合度量融合与稀疏表示的拉普拉斯矩 (7) 阵表示为 L-DGD--D-2T2D-! (10) =1 式(7)分别采用欧氏距离、Kendall Tau距离度量 然后将D2T作为栈式自编码器的输人，通 方法计算获得的完全相似矩阵表示为F、F2。 过编码和解码重构学习数据潜在特征表示。 稀疏表示矩阵实际上是完全相似矩阵的KNN 2.2深度嵌入谱聚类 图，在扩散过程中为提高计算效率，采用稀疏表 假定聚类任务为N个样本，X=,x2,…,x, 示矩阵作为核矩阵进行交叉扩散。将稀疏表示矩 x∈，i=1,2,…,n划分为K簇，每个都由聚类中 阵Z采用欧氏距离、Kendall Tau距离分别表示为 心4，j=1,2,…,K表示。为避免直接在样本空间 Z和Ze。首先将F,=Fu和F2。=F2视为送 X上进行聚类，首先使用非线性映射进行数据转 换，嵌入函数Pw:X→H,将原始数据映射到潜在 代过程第一步中的初始两个状态矩阵(=0)，而 特征空间H=[h1,h2,…,hnJ,heR4,与输入样本相 度量融合的关键步骤是迭代更新对应于每个度量 比具有较低维度(d,<d),再经过非线性映射进 的稀硫表示矩阵 行数据重构，解码器映射函数gw:H→，= F=Z0×F2×(Z)T (8) [,,…,],无表示样本，的数据重构。本文旨 FR,=Ze×F×(Z2)T 在寻找良好的嵌人特征表示h,,使其更适合于

KT(L1 ,L2) =   {(i, j) : i Lj1)∧(Li2 > Lj2))}    (6) Li1 Li2 L1 L2 i |·| KT(L1,L2) KT(L1,L2) n(n−1)/2 n(n−1)/2 KT(L1,L2) [0,1] 式中： 和 表示 和 中第 个元素各自的 序号， 为集合中元素的个数。若两排列相同，则 为 0；若两排列互为逆序， 为 。通过除以 进行规范化处理， 使 位于区间 内。 xi xj ρ1(xi , xj) ρ2(xi , xj) xi p Listi = [ρ1(x1, xi), ρ1(x2, xi),··· ,ρ1(xm, xi),··· , ρ1(xp, xi)] xj Listj xi xj 若将欧氏距离及 Kendall Tau 距离两种度量 方式融合，生成增强的相似度矩阵，能在反映点对 之间地理相似性的同时考虑点之间的拓扑逻辑相 似性。将点 和 之间的欧氏距离表示为 , Kendall Tau 距离表示为 。在基于欧氏距 离对样本进行排序，然后利用 Kendall Tau 距离度 量两个样本之间的全局关系，全面反映数据的底 层结构信息。对于样本 ，基于欧氏距离计算与 个地标点之间的相似度，可得一有序序列： ，同样的 对于样本 可得有序序列 ，那么结合式 (6)， 样本 和 之间的 Kendall Tau 距离则为 ρ2(xi , xj) = KT(Listi ,Listj) k F 从度量融合的角度来看，大多数主流的思想 都是通过线性组合多个亲和图来获得互补的相似 信息[23] ，然而这个线性组合对分配给每个度量的 权重很敏感，且来自多个亲和图的互补信息并非 线性相关的。为探索两种距离度量方案相互融合 的思想，综合考虑相邻点的几何分布和拓扑分 布，受到联合训练算法的启发，采用基于消息传 递理论和交叉扩散过程的融合方法。以完全相似 矩阵作为初始状态矩阵，即对式 (5) 不考虑 近邻 点而构建相似矩阵，该初始状态矩阵 携带关于 每个地标点与其他所有样本点之间相似性的完整 信息，对应元素为 Fji = Aji ∑p m=1 Ami (7) F (1) F (2) Z Z (1) Z (2) F (1) h=0 = F (1) F (2) h=0 = F (2) h = 0 式 (7) 分别采用欧氏距离、Kendall Tau 距离度量 方法计算获得的完全相似矩阵表示为 、 。 稀疏表示矩阵实际上是完全相似矩阵的 KNN 图，在扩散过程中为提高计算效率，采用稀疏表 示矩阵作为核矩阵进行交叉扩散。将稀疏表示矩 阵 采用欧氏距离、Kendall Tau 距离分别表示为 和 。首先将 和 视为迭 代过程第一步中的初始两个状态矩阵 ( )，而 度量融合的关键步骤是迭代更新对应于每个度量 的稀疏表示矩阵 F (1) h+1 = Z (1) × F (2) h ×(Z (1)) T F (2) h+1 = Z (2) × F (1) h ×(Z (2)) T (8) F (1) h h F (2) h h h Z 式中： 表示基于欧氏距离度量的稀疏表示矩 阵在 步迭代更新后的状态矩阵， 表示基于 Kendall Tau 距离度量的矩阵在 步迭代更新后的 状态矩阵。此步骤每次更新状态矩阵时，生成两 个并行交换扩散过程，在 步后，融合两种度量 方式的稀疏表示矩阵 ： Z = F (1) h + F (2) h 2 (9) F (1) h h M (1) h (i, j) = F (1) h (i,:)− F (1) h (j,:) ℜ (1) h x (1) h ∈ ℜ(1) h Z (2) x (2) h+1 = Z (2)x (1) h +ε ε x (2) h+1 x (1) h+1 从概率角度分析该交叉扩散过程，对于状态 矩阵 ，依据扩散映射[24] 可定义进行 步迭代 时的扩散距离 ，扩散 过程即是将数据空间映射到扩散空间 的过 程，本质上每个样本都可由自身与其他数据点间 相似度表示。为实现核矩阵之间的融合，对于样本 ，引入线性算子 ，经过 ( 为白噪声) 线性运算后，由扩散映射性质可获 得 的边缘分布[23] ，同理可得 。该交叉扩散 过程的实质并非在原始数据空间中进行线性投 影，而是在扩散空间中进行迭代线性运算的，这 样对样本的噪声和规模具有较强鲁棒性，且融合 了整个样本集的相似流形的内在结构。 Z X Gˆ = Zˆ T Zˆ ∈ R n×n Zˆ = D −1/2Z D Dii = ∑ j Zi j Dii = diag(Zˆ T i Zˆ s ) Zˆ s = ∑n j=1 Zˆ j p×1 k Zˆ k D O(np) 在由式 (9) 获得稀疏表示矩阵 后，通过该 矩阵来近似获得数据 的规范化图亲和矩阵， 即 ： ，其中 ， 为度矩阵， 其元素一般为 ，为进一步降低计算复杂 度，采用文献 [2] 计算度矩阵元素 ， 其中 ，为 的向量，其第 个元素为 的第 行元素之和，该计算 的时间复杂度为 。结合度量融合与稀疏表示的拉普拉斯矩 阵表示为 L = D − 1 2 GDˆ − 1 2 = D − 1 2 Zˆ T Z Dˆ − 1 2 (10) D − 1 然后将 2 Zˆ T 作为栈式自编码器的输入，通 过编码和解码重构学习数据潜在特征表示。 2.2 深度嵌入谱聚类 N X = [x1, x2,··· , xn], xi ∈ R dx ,i = 1,2,··· ,n K µj , j = 1,2,··· ,K X φW : X → H H = [h1,h2,··· ,hn],hi ∈ R dh dh ≪ dx gW′ : H → Xˆ Xˆ = [ ˆx1, xˆ2,··· , xˆn] xˆi xi {hi} n i=1 假定聚类任务为 个样本， 划分为 簇，每个都由聚类中 心 表示。为避免直接在样本空间 上进行聚类，首先使用非线性映射进行数据转 换，嵌入函数 ，将原始数据映射到潜在 特征空间 ，与输入样本相 比具有较低维度 ( )，再经过非线性映射进 行数据重构，解码器映射函数 , ， 表示样本 的数据重构。本文旨 在寻找良好的嵌入特征表示 使其更适合于 ·690· 智 能 系 统 学 报 第 15 卷

第4期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·691· 聚类，所构造的损失目标函数包含自编码器重构 损失及聚类损失，利用自编码器以无监督方式学 0-221+-'-9Xa- 习表示，所习得特征能最大限度地保留数据的固 反向传播给栈式自编码器，利用下层 将 有局部结构，聚类损失用于分散嵌入点。与需要 h 分层预训练以及非联合嵌入聚类的学习模型不 神经元梯度由上层神经元残差导出的规律，自上 同，同时避免微调步骤覆盖预训练获得的参数， 面下反向逐层计算出胎及0。给定小批量样 采用联合聚类和重构损失函数的目标函数，对所 本数目m及学习率入，编码器参数W、解码器参 有网络层进行端到端优化训练，迭代优化自编码 数W及聚类中心4更新公式为 器参数及聚类中心，损失目标函数J定义为 分(u+y J=J+yJo (11) W=W- maw+yam (16) 其中J,和分别表示为重构损失和聚类损失， aJ, y(0<y<1)用来调节潜在特征空间的失真程度。 W=W- m台aw (17) 基于2.1节，将构造的相似度矩阵作为栈式自编 码的输人，在进行聚类之前，对嵌入特征表示 4=4- 片au (18) h:,进行预训练，执行k-means算法，获得初始自 m台dw 编码器参数{WW)及聚类中心{41 2.3算法步骤 对于训练所获得的嵌人特征表示，在文献23] 算法结合度量融合和地标表示的自编码谱 引入了由-SNE衡量的软标签分布P,用来衡量 聚类算法 潜在空间样本：与聚类中心山；之间的相似度： 输入输入数据X,聚类数日K,地标点个数 P,停止阈值B,近邻点数目k,学习率入，迭代次 +h,-m P i=1.2,…,K (12) 数h,最大迭代次数maxiter,停止收敛阈值Th。 2a+脉-m 输出自编码器参数(WW)及聚类中心 {la及样本类标签Label,. 式中P表示潜在空间样本h:属于山所在簇的概 1)根据式(1)、(2)计算节点PR值，当所有节 率。结合最小化相关熵(KL散度)来降低软标签 点满足式(3)时，停止迭代，PR值降序排列，择取 分布P与辅助目标分布Q之间的差异，将聚类损 前p个高PR值节点作为地标点； 失目标函数J定义为 2)依据式(4)成对相似度计算，引入k近邻 =KuQn=∑∑als器 (13) 点，以欧氏距离、Kendall Tau距离2种度量方式， 通过式（⑤）分别计算相应的稀疏表示矩阵Z和 其中，辅助目标分布分量qk是由p:得到的，通过 Z②。同时，通过式(7)计算对应于2种度量方式 计算弘使其为零，求取相应封闭解获得9： op 的完全相似矩阵F)、F②； I∑Pre 3)将F、F2作为初始状态矩阵，Z、Z2作 9= (14) 为核矩阵，根据式(8)进行矩阵融合，迭代更新对 公m 应于每个度量的稀疏表示矩阵，在h步后结合式 (9)获得融合2种度量方式的稀疏表示矩阵Z; 最小化聚类损失目标函数J可视为自训练 4)通过式(10)构造拉普拉斯矩阵，将D2r 过程，此外，重构误差函数J,采用均值误差测量 作为栈式自编码器的输入，前向训练网络获得初 (mean squared error,MSE): 始化数据潜在特征表示{h,1； h=乃k-g知据 (15) 5)对嵌入特征表示h,进行预训练，执行k i=1 means算法，获得初始自编码器参数(WW)及聚 关于自编码器参数{WW}及聚类中心 类中心4 的更新，采用mini-batch随机梯度算法反向传播 6)若迭代次数大于maxiter,.转至10)，否则重 逐层训练网络。J.关于嵌人特征表示h:和聚类 复执行7)~9)： 中心4的梯度计算为 7)根据式(12)和式(14)计算Pk和q; 张-2a+k-nDg-- 8)根据式(11)、(13)和(15)计算损失目标函数； 9)采用mini-batch随机梯度算法反向传播逐

J 聚类，所构造的损失目标函数包含自编码器重构 损失及聚类损失，利用自编码器以无监督方式学 习表示，所习得特征能最大限度地保留数据的固 有局部结构，聚类损失用于分散嵌入点。与需要 分层预训练以及非联合嵌入聚类的学习模型不 同，同时避免微调步骤覆盖预训练获得的参数， 采用联合聚类和重构损失函数的目标函数，对所 有网络层进行端到端优化训练，迭代优化自编码 器参数及聚类中心，损失目标函数 定义为 J = Jr +γJc (11) Jr Jc γ(0 < γ < 1) {hi} n i=1 {W,W′ } { µj }K j=1 其中 和 分别表示为重构损失和聚类损失， 用来调节潜在特征空间的失真程度。 基于 2.1 节，将构造的相似度矩阵作为栈式自编 码的输入，在进行聚类之前，对嵌入特征表示 进行预训练，执行 k-means 算法，获得初始自 编码器参数 及聚类中心 。 pik hi µj 对于训练所获得的嵌入特征表示，在文献 [23] 引入了由 t-SNE 衡量的软标签分布 ，用来衡量 潜在空间样本 与聚类中心 之间的相似度： pik = (1+ hi −mj 2 ) −1 ∑K j=1 (1+ hi −mj 2 ) −1 , j = 1,2,··· ,K (12) pik hi µj P Q Jc 式中 表示潜在空间样本 属于 所在簇的概 率。结合最小化相关熵 (KL 散度) 来降低软标签 分布 与辅助目标分布 之间的差异，将聚类损 失目标函数 定义为 Jc = KL(Q ∥ P) = 1 N ∑ i ∑ k qik lg qik pik (13) qik pik ∂Jc ∂pik qik 其中，辅助目标分布分量 是由 得到的，通过 计算 使其为零，求取相应封闭解获得 ： qik = p 2 ik/ ∑ i ′ pi ′ k ∑ k ′ ( p 2 ik′ / ∑ i ′ pi ′ k ′ ) (14) Jc Jr 最小化聚类损失目标函数 可视为自训练 过程，此外，重构误差函数 采用均值误差测量 (mean squared error, MSE)： Jr = ∑n i=1 ∥xi −gW′ (hi)∥ 2 2 (15) {W,W′ } { µj }K j=1 Jc hi µj 关于自编码器参数 及聚类中心 的更新，采用 mini-batch 随机梯度算法反向传播 逐层训练网络。 关于嵌入特征表示 和聚类 中心 的梯度计算为 ∂Jc ∂hi = 2 ∑K j=1 (1+ hi −µj 2 ) −1 (qi j − pi j)(hi −µj) ∂Jc ∂µi = 2 ∑K j=1 (1+ hi −µj 2 ) −1 (pi j −qi j)(hi −µj) ∂Jc ∂hi ∂Jc ∂W ∂Jc ∂W′ m λ W W′ µj 将 反向传播给栈式自编码器，利用下层 神经元梯度由上层神经元残差导出的规律，自上 而下反向逐层计算出 及 。给定小批量样 本数目 及学习率 ，编码器参数 、解码器参 数 及聚类中心 更新公式为 W = W − λ m ∑m i=1 ( ∂Jr ∂W +γ ∂Jc ∂W ) (16) W′ = W′ − λ m ∑m i=1 ∂Jr ∂W′ (17) µj = µj − λ m ∑k j=1 ∂Jr ∂µj (18) 2.3 算法步骤 算法 结合度量融合和地标表示的自编码谱 聚类算法 K p β k λ h maxiter Th 输入 输入数据 X，聚类数目 ，地标点个数 ，停止阈值 ，近邻点数目 ，学习率 ，迭代次 数 ，最大迭代次数 ，停止收敛阈值 。 {W,W′ } { µj }K j=1 输 出 自编码器参数 及聚类中心 及样本类标签 Label。 p 1) 根据式 (1)、(2) 计算节点 PR 值，当所有节 点满足式 (3) 时，停止迭代，PR 值降序排列，择取 前 个高 PR 值节点作为地标点； k Z (1) Z (2) F (1) F (2) 2) 依据式 (4) 成对相似度计算，引入 近邻 点，以欧氏距离、Kendall Tau 距离 2 种度量方式， 通过式 (5) 分别计算相应的稀疏表示矩阵 和 。同时，通过式 (7) 计算对应于 2 种度量方式 的完全相似矩阵 、 ； F (1) F (2) Z (1) Z (2) h Z 3) 将 、 作为初始状态矩阵， 、 作 为核矩阵，根据式 (8) 进行矩阵融合，迭代更新对 应于每个度量的稀疏表示矩阵，在 步后结合式 (9) 获得融合 2 种度量方式的稀疏表示矩阵 ； D − 1 2 Zˆ T {hi} n i=1 4) 通过式 (10) 构造拉普拉斯矩阵，将 作为栈式自编码器的输入，前向训练网络获得初 始化数据潜在特征表示 ； {hi} n i=1 {W,W′ } { µj }K j=1 5) 对嵌入特征表示 进行预训练，执行 k￾means 算法，获得初始自编码器参数 及聚 类中心 ； 6) 若迭代次数大于 maxiter ，转至 10)，否则重 复执行 7) ~ 9)； 7) 根据式 (12) 和式 (14) 计算 pik 和 qik； 8) 根据式 (11)、(13) 和 (15) 计算损失目标函数； 9) 采用 mini-batch 随机梯度算法反向传播逐 第 4 期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·691·

·692· 智能系统学报 第15卷 层训练网络，根据式(16)(18)更新整个网络参数 本文算法与文献[8-9]基于地标表示的快速 wW)及聚类中心4 谱聚类算法LSC-R和LSC-K,未考虑地标点的基于 10)根据软标签分布P来分配样本类标签： 自编码的谱聚类算法DEC及GraEnt、文献[I7刀 Label(i)=arg max po 中自编码器与地标点结合的快速谱聚类算法 kE1.2,-K 2.4算法复杂度分析 SCAL-R及SCAL-K进行对比。LSC-R及SCAL- 首先，从n个数据样本中选择p个地标点，该 R是通过随机采样获取p个地标点，LSC-K及 步骤时间复杂度为Otpm),t为迭代次数。相似度 SCAL-K是采用k-means算法获得p个地标点的。 为保证算法之间的公平对比，具体参数如下 矩阵构造部分涉及了2种度量方案的融合以及构 造稀疏表示矩阵1m,时间复杂度为O(pnlog2.n)。本 设置：文献[8-9]、[17]及本文算法涉及的地标点 个数p统一设置为1000，稀疏表示矩阵构造涉及 文算法用栈式自编码器代替拉普拉斯矩阵特征分 的近邻点数目k设置为5，所有算法涉及k-means 解部分，时间复杂度为O(nD+nvK),K为聚类数 部分迭代次数为500。文献[16]、[17]、[25]及 目，D为设置的隐藏层最大单元数，v为数据潜在 本文算法涉及的自编码器部分，编码器维度为 特征表示维度，一般K≤v≤D,所提算法整体时 p-500-500-2000-10,解码器则为10-2000-500- 间复杂度为O(tpm+pnlog2n+nD)。基于地标表示 500-P,非线性激活函数统一采用线性校正单元 的快速谱聚类算法[时间复杂度为Otpm+pm+ (rectified linear units,ReLU)。本文算法中涉及的 p3+p2n),由于p 54 GraEn[16] 0.81820.28720.7350 0.2218 0.5134 CIFARI0 60000 10 1024 本文算法0.90120.46900.8903 0.33250.6129

{W,W′ } { µj }K j=1 层训练网络，根据式 (16)~(18) 更新整个网络参数 及聚类中心 ； P Label(i) = argmax k∈1,2,···,K pik 10) 根据软标签分布 来分配样本类标签： 。 2.4 算法复杂度分析 n p O(tpn) t O(pnlog2n) O(nD2 +nvK) K D v K ⩽ v ⩽ D O(tpn+ pnlog2n+nD2 ) O(tpn+ pn+ p 3 + p 2n) p ≪ n O(tpn+ pn+ p 2n) p D n O(n 2 +nD2 ) O(n 2 +nKD) 首先，从 个数据样本中选择 个地标点，该 步骤时间复杂度为 ， 为迭代次数。相似度 矩阵构造部分涉及了 2 种度量方案的融合以及构 造稀疏表示矩阵[17] ，时间复杂度为 。本 文算法用栈式自编码器代替拉普拉斯矩阵特征分 解部分，时间复杂度为 ， 为聚类数 目， 为设置的隐藏层最大单元数， 为数据潜在 特征表示维度，一般 ，所提算法整体时 间复杂度为 。基于地标表示 的快速谱聚类算法[ 9 ] 时间复杂度为 ，由于 ，时间复杂度可写为 。 和 取值相当且远小于 ，因而本文算法 复杂度略高于基于地标表示的快速谱聚类算法时 间复杂度，但远远低于基于自编码器的谱聚类算 法 DEC[25] 的时间复杂度 、GraEn [16] 的 时间复杂度 。 3 实验及分析结果 3.1 实验环境 为证明本文算法适用于大规模数据集，选取 如下 5 个数据集：MNIST、USPS、COIL100、Cover￾Type 和 CIFAR10。这 5 个数据集包含不同类型 的图像，如手写数字、英文字母表、物体图像和森 林植被类等，样本数较大，可以有效验证本文算 法在大规模数据集上的聚类性能。表 1 为相关数 据集的具体信息。仿真实验硬件环境为 Intel(R) Core(TM) i7-6 700 CPU @3.40 GHz；16 GB RAM； 操作系统：Windows7；编程语言：Python 3.5。 表 1 实验数据集描述 Table 1 The description of experimental datasets 数据集 样本数 类 维数 MNIST 70 000 10 784 LetterRec 20 000 26 16 COIL100 7 200 100 1 024 CoverType 581 012 7 54 CIFAR10 60 000 10 1 024 p p 本文算法与文献 [8-9] 基于地标表示的快速 谱聚类算法 LSC-R 和 LSC-K，未考虑地标点的基于 自编码的谱聚类算法 DEC[25] 及 GraEn[16] 、文献 [17] 中自编码器与地标点结合的快速谱聚类算法 SCAL-R 及 SCAL-K 进行对比。LSC-R 及 SCAL￾R 是通过随机采样获取 个地标点，LSC-K 及 SCAL-K 是采用 k-means 算法获得 个地标点的。 p k p−500−500−2 000−10 10−2 000−500− 500−p β = 10−3 h = 10 m λ = 0.1 Th = 0.001 maxiter γ = 0.1 为保证算法之间的公平对比，具体参数如下 设置：文献 [8-9]、[17] 及本文算法涉及的地标点 个数 统一设置为 1 000，稀疏表示矩阵构造涉及 的近邻点数目 设置为 5，所有算法涉及 k-means 部分迭代次数为 500。文献 [16]、[17]、[25] 及 本文算法涉及的自编码器部分，编码器维度为 ，解码器则为 ，非线性激活函数统一采用线性校正单元 (rectified linear units，ReLU)。本文算法中涉及的 停止阈值 ，距离度量融合步骤迭代次数设 置为 ，参数优化更新部分采用 mini-batch 随 机梯度算法，小批量样本数目 为 256，学习率 ；在预训练阶段，执行 k-means 算法 20 次选 取最佳结果，初始化自编码器参数和聚类中心； 收敛阈值设置为 ，最大迭代次数 为 20 000，调节潜在特征空间的失真程度 。 3.2 实验分析 为了比较这些算法性能，通过聚类结果和样 本真实标签进行对比。采用聚类准确率 (ACC) 和 标准化互信息 (NMI) 来作为度量指标进行评估比 较。ACC 和 NMI 这 2 种度量标准在 [0,1] 之间取 值，值越大聚类性能越好。各种算法在 5 个大规 模数据集的实验结果如表 2、3 所示。 表 2 不同数据集的准确率 (ACC) 的比较 Table 2 Comparison of clustering accuracy (ACC) for dif￾ferent data sets 算法 MNIST LetterRec COIL100 CoverType CIFAR10 LSC-R[9] 0.589 0 0.292 2 0.489 6 0.247 5 0.471 6 LSC-K[9] 0.727 0 0.303 3 0.545 6 0.255 0 0.504 0 SCAL-R[17] 0.836 1 0.439 4 0.790 5 0.260 2 0.561 9 SCAL-K[17] 0.889 8 0.447 0 0.812 2 0.293 3 0.580 2 DEC[25] 0.865 1 0.297 5 0.721 9 0.249 7 0.482 1 GraEn[16] 0.818 2 0.287 2 0.735 0 0.221 8 0.513 4 本文算法 0.901 2 0.469 0 0.890 3 0.332 5 0.612 9 ·692· 智 能 系 统 学 报 第 15 卷

第4期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·693· 表3不同数据集的标准化互信息(NM四的比较 17.15%、5.84%。说明本文构造的结合度量融合和 Table 3 Comparison of normalized mutual information 地标表示的相似度矩阵更全面地反映了数据之间 (NMI)for different data sets 的结构信息，且运行效率大大得到提升。 算法 MNIST LetterRec COIL100 CoverType CIFAR10 3)此外，间接可以看出，以LSC-R、LSC-K为 LSC-RI9 代表的引入地标点算法与DEC、GraEn为代表 0.59110.3734 0.7315 0.0831 0.0348 的基于深度自编码算法相比，在MNIST、COL1O0 LSC-KI9 0.72220.3963 0.7632 0.0902 0.0542 及CIFAR10这些维度相对较高的大规模数据集 SCAL-Rm0.82970.3915 0.8274 0.0912 0.0765 中，聚类性能处于劣势，但在LetterRec及Cover-- sCAL-K70.87540.4055 Type维度较低的数据集上则处于优势，可见基于 0.8416 0.1025 0.0844 自编码器的算法对于高维数据集较为友好，地标 DECRS] 0.83690.3851 0.8045 0.0856 0.0651 点的择取有利于大规模数据集的聚类性能。 GraEn[16 0.74730.37120.7911 0.0719 0.0579 本文算法采用欧氏距离与Kendall Tau距离 本文算法0.88210.44350.87020.13420.1521 度量融合的方式，挖掘数据的真实分布，从上述 结论1)可以看出算法性能会受到距离度量方式 通过表2、3两种指标下的各种算法性能度量 的影响。为深人分析，将本文算法稀疏表示矩阵 对比，可以看出本文提出的结合度量融合和地标 构造部分，分别采用基于欧氏距离(SCE)与基于 表示的自编码谱聚类算法在MNIST、LetterRec、 Kendall Tau距离(SCK)计算点对相似度，采用 COLl00、CoverType及CIFAR10这5个大规模数 ACC和NMI两个指标与本文算法融合度量方案 据集上，相对于基于地标表示的快速谱聚类算法 进行性能对比。表4显示3种算法在3个数据集 LSC-R和LSC-K,未考虑地标点的基于自编码的 上的算法性能。从表4可以看出，2种距离度量 谱聚类算法DEC及GraEn,.自编码器与地标点结 方式的融合一定程度上能更全面地反映数据之间 合的快速谱聚类算法SCAL-R及SCAL-K,在ACC 的结构信息，从而获得更为理想的聚类性能。欧 和NMI两种指标下均表现出了更为理想的聚类 氏距离与Kendall Tau距离这两种度量方式的优 性能。同时，还可以得出如下结论： 劣，并不能准确地从数据中评判出来，但结合表2、3 1)本文算法在稀疏表示矩阵构造部分由于引 可以看出，基于本文算法的SCE和SCK算法在 入网页质量进行地标点择取，并进行度量融合计 3个数据集上与其他几种算法相比，相对处于优 算点对相似度，在算法复杂度方面，相对于旨在 势。特别是与SCAL R及SCAL K算法对应ACC 提升谱聚类算法效率的LSC-R和LSC-K处于劣 和NMI对比可以得出，本文通过基于网页质量的 势。从运行时间上看，在MNIST数据集上，LSC PageRank算法择取地标点总体上要优于随机选 R及LSC-K算法仅需10s左右，本文算法则需 择与k-means算法的方法，但也有低于这两种方 200~300s的运行时间，但相对于DEC及GraEn, 法的情况出现，为深入分析，更改地标点个数p 本文算法运行时间降低了1000~2000s,有了很 从100~1000，在3个数据集上，进行本文算法与 大的提升。且从表2中可以看出，就ACC,本文 SCAL-R、SCAL-K的ACC值的对比实验。图1、2 算法与LSC-K算法相比，在MNIST、LetterRec、 分别显示了SCAL-R、SCAL-K及本文算法在选取 COIL1000、CoverType及CIFAR10F分别提升了 的3个数据集上，地标点个数从100~1000之间变 17.42%、16.57%、34.47%、7.75%、10.89%,与随机 化，所对应的ACC及NM值。图中可直观看出， 抽样择取地标点的LSC-R算法相比，优势更大。 本文算法在3个数据集上的ACC、NMI普遍比 同样地，从表3看出，本文算法NMI值也有了明 LSC-K、SCAL-K要高，除去在MNIST数据集上， 显的提升。而与SCAL-R及SCAL-K算法相比， 地标点个数较少时，本文算法与SCAL-R算法相 本文融合两种距离度量多角度描述数据集的结 比略处于劣势，这是由于本文构造相似度矩阵采 构信息，使其在ACC、NMI两种指标上均处于 用的度量融合方案，在地标点个数相对多时，能 优势。 有效地挖掘数据的结构信息，地标点个数从 2)相比未考虑地标点的基于自编码的谱聚 300开始，本文算法便展现出优势。同时从折线 类算法DEC及GraEn,本文算法ACC和NMI也 走势可以看出，地标点个数的增加，3种算法的 有了一定的提升，如与DEC算法对比，本文算法 ACC、NMI值也随之提高，且本文算法呈现稳步 在LetterRec数据集上ACC、NMI分别提升了 上升趋势，这表明两个聚类性能指标受地标点个

表 3 不同数据集的标准化互信息 (NMI) 的比较 Table 3 Comparison of normalized mutual information (NMI) for different data sets 算法 MNIST LetterRec COIL100 CoverType CIFAR10 LSC-R[9] 0.591 1 0.373 4 0.731 5 0.083 1 0.034 8 LSC-K[9] 0.722 2 0.396 3 0.763 2 0.090 2 0.054 2 SCAL-R[17] 0.829 7 0.391 5 0.827 4 0.091 2 0.076 5 SCAL-K[17] 0.875 4 0.405 5 0.841 6 0.102 5 0.084 4 DEC[25] 0.836 9 0.385 1 0.804 5 0.085 6 0.065 1 GraEn[16] 0.747 3 0.371 2 0.791 1 0.071 9 0.057 9 本文算法 0.882 1 0.443 5 0.870 2 0.134 2 0.152 1 通过表 2、3 两种指标下的各种算法性能度量 对比，可以看出本文提出的结合度量融合和地标 表示的自编码谱聚类算法在 MNIST、LetterRec、 COIL100、CoverType 及 CIFAR10 这 5 个大规模数 据集上，相对于基于地标表示的快速谱聚类算法 LSC-R 和 LSC-K，未考虑地标点的基于自编码的 谱聚类算法 DEC 及 GraEn，自编码器与地标点结 合的快速谱聚类算法 SCAL-R 及 SCAL-K，在 ACC 和 NMI 两种指标下均表现出了更为理想的聚类 性能。同时，还可以得出如下结论： 1) 本文算法在稀疏表示矩阵构造部分由于引 入网页质量进行地标点择取，并进行度量融合计 算点对相似度，在算法复杂度方面，相对于旨在 提升谱聚类算法效率的 LSC-R 和 LSC-K 处于劣 势。从运行时间上看，在 MNIST 数据集上，LSC￾R 及 LSC-K 算法仅需 10 s 左右，本文算法则需 200~300 s 的运行时间，但相对于 DEC 及 GraEn， 本文算法运行时间降低了 1 000~2 000 s，有了很 大的提升。且从表 2 中可以看出，就 ACC，本文 算法与 LSC-K 算法相比，在 MNIST、LetterRec、 COIL100、CoverType 及 CIFAR10F 分别提升了 17.42%、16.57%、34.47%、7.75%、10.89%，与随机 抽样择取地标点的 LSC-R 算法相比，优势更大。 同样地，从表 3 看出，本文算法 NMI 值也有了明 显的提升。而与 SCAL-R 及 SCAL-K 算法相比， 本文融合两种距离度量多角度描述数据集的结 构信息，使其在 ACC、NMI 两种指标上均处于 优势。 2) 相比未考虑地标点的基于自编码的谱聚 类算法 DEC 及 GraEn，本文算法 ACC 和 NMI 也 有了一定的提升，如与 DEC 算法对比，本文算法 在 LetterRec 数据集上 ACC、NMI 分别提升了 17.15%、5.84%。说明本文构造的结合度量融合和 地标表示的相似度矩阵更全面地反映了数据之间 的结构信息，且运行效率大大得到提升。 3) 此外，间接可以看出，以 LSC-R、LSC-K 为 代表的引入地标点算法与 DEC、GraEn 为代表 的基于深度自编码算法相比，在 MNIST、COIL100 及 CIFAR10 这些维度相对较高的大规模数据集 中，聚类性能处于劣势，但在 LetterRec 及 Cover￾Type 维度较低的数据集上则处于优势，可见基于 自编码器的算法对于高维数据集较为友好，地标 点的择取有利于大规模数据集的聚类性能。 p 本文算法采用欧氏距离与 Kendall Tau 距离 度量融合的方式，挖掘数据的真实分布，从上述 结论 1) 可以看出算法性能会受到距离度量方式 的影响。为深入分析，将本文算法稀疏表示矩阵 构造部分，分别采用基于欧氏距离 (SCE) 与基于 Kendall Tau 距离 (SCK) 计算点对相似度，采用 ACC 和 NMI 两个指标与本文算法融合度量方案 进行性能对比。表 4 显示 3 种算法在 3 个数据集 上的算法性能。从表 4 可以看出，2 种距离度量 方式的融合一定程度上能更全面地反映数据之间 的结构信息，从而获得更为理想的聚类性能。欧 氏距离与 Kendall Tau 距离这两种度量方式的优 劣，并不能准确地从数据中评判出来，但结合表 2、3 可以看出，基于本文算法的 SCE 和 SCK 算法在 3 个数据集上与其他几种算法相比，相对处于优 势。特别是与 SCAL_R 及 SCAL_K 算法对应 ACC 和 NMI 对比可以得出，本文通过基于网页质量的 PageRank 算法择取地标点总体上要优于随机选 择与 k-means 算法的方法，但也有低于这两种方 法的情况出现，为深入分析，更改地标点个数 从 100~1 000，在 3 个数据集上，进行本文算法与 SCAL-R、SCAL-K 的 ACC 值的对比实验。图 1、2 分别显示了 SCAL-R、SCAL-K 及本文算法在选取 的 3 个数据集上，地标点个数从 100~1 000 之间变 化，所对应的 ACC 及 NMI 值。图中可直观看出， 本文算法在 3 个数据集上的 ACC、NMI 普遍比 LSC-K、SCAL-K 要高，除去在 MNIST 数据集上， 地标点个数较少时，本文算法与 SCAL-R 算法相 比略处于劣势，这是由于本文构造相似度矩阵采 用的度量融合方案，在地标点个数相对多时，能 有效地挖掘数据的结构信息，地标点个数 从 300 开始，本文算法便展现出优势。同时从折线 走势可以看出，地标点个数的增加，3 种算法的 ACC、NMI 值也随之提高，且本文算法呈现稳步 上升趋势，这表明两个聚类性能指标受地标点个 第 4 期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·693·

·694· 智能系统学报 第15卷 数的选取影响很大。总体来说，在不同地标点的 0.90 o-LSC-K 个数选取下，本文算法展现出优于其他算法的聚 0.85 ★SCAL- 一本文算法 类性能。 0.80 ★ 表4不同距离度量方案的算法性能对比 0.75 Table 4 Performance comparision of algorithms with dif- ferent distance measurement schemes 0.65 数据集 算法 SCE SCK 本文算法 0.60 0 200 400 600 8001000 ACC 0.8733 0.8624 0.9012 地标点的个数 MNIST NMI 0.8489 0.8545 0.8821 (a)MNIST数据集 ACC 0.8391 0.8214 0.8903 0.90 -o-LSC-K COIL100 0.85 ★SCAL-K NMI 0.8547 0.8427 0.8702 一本文算法 90.80 ACC 0.5975 0.5899 0.6129 CIFAR10 0.75 NMI 0.1124 0.1324 0.1521 0.65 0.95 -o-LSC-K 0.60 0.90 200 400600 800 1000 ★SCAL-K 一 本文算法 地标点的个数 0.85 (b)COL100数据集 0.80 0.16 0.75 o-LSC-K 0.14 ★SCAL-K 0.70 厨0.12 一本文算法 0.65 0.60 0 200 400600 8001000 0.08 地标点的个数 0e (a)MNIST数据集 0.04 ★★ 0.9r -o-LSC-K ★SCAL-K 0.02 0 200 400 600 8001000 0.8 一本文算法 地标点的个数 (C)CIFARI0数据集 0.7 图2不同数据集上3种算法的NMⅡ比较 0.6 Fig.2 Comparison of the NMIs of three algorithms on dif- 0.5 ferent dataset 0.4 0 200 4006008001000 4结束语 地标点的个数 (b)COL100数据集 随着数据规模的增大，结构信息的复杂度提 0.65 高，在聚类过程中往往会耗费大量时间，存在相 -o-LSC-K ◆SA✉K 0.60 似度矩阵存储开销大及矩阵分解复杂度高的问 本文算法 题，且聚类精度也会受到影响。为此，本文提出 0.55 一种结合度量融合和地标表示的自编码谱聚类算 法，通过引入节点相对质量概念作为地标点选择 0.45 的依据，以地标点与其他样本点之间相似度构造 图相似度矩阵，以降低存储开销。同时，融合欧 0.40 0 200 400 600 800 1000 氏距离与Kendall Tau距离作为相似度度量方式， 地标点的个数 (c)CIFAR10数据集 充分挖掘数据底层结构信息，且以栈式自编码器 代替拉普拉斯矩阵分解步骤，通过联合学习框架 图1不同数据集上3种算法的ACC比较 Fig.1 Comparison of the ACCs of three algorithms on dif. 进一步提高聚类精度。实验表明在几种大规模数 ferent datasets 据集上本文算法具有较好的聚类性能，但由于本

数的选取影响很大。总体来说，在不同地标点的 个数选取下，本文算法展现出优于其他算法的聚 类性能。 表 4 不同距离度量方案的算法性能对比 Table 4 Performance comparision of algorithms with dif￾ferent distance measurement schemes 数据集 算法 SCE SCK 本文算法 MNIST ACC 0.873 3 0.862 4 0.901 2 NMI 0.848 9 0.854 5 0.882 1 COIL100 ACC 0.839 1 0.821 4 0.890 3 NMI 0.854 7 0.842 7 0.870 2 CIFAR10 ACC 0.597 5 0.589 9 0.612 9 NMI 0.112 4 0.132 4 0.152 1 0.95 0.90 0.85 0.80 聚类准确率 聚类准确率 聚类准确率 0.75 0.70 0.65 0.60 0.40 0.45 0.50 0.55 0.60 0.65 0.4 0.5 0.6 0.7 0.8 0.9 0 400 600 200 地标点的个数 800 1 000 0 400 600 200 地标点的个数 800 1 000 0 400 600 200 地标点的个数 800 1 000 LSC-K SCAL-K 本文算法 LSC-K SCAL-K 本文算法 LSC-K SCAL-K 本文算法 (a) MNIST 数据集 (b) COIL100 数据集 (c) CIFAR10 数据集 图 1 不同数据集上 3 种算法的 ACC 比较 Fig. 1 Comparison of the ACCs of three algorithms on dif￾ferent datasets 0.90 0.85 0.80 标准化互信息 标准化互信息 标准化互信息 0.75 0.70 0.65 0.60 0.02 0.04 0.06 0.08 0.10 0.14 0.12 0.16 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0 400 600 200 地标点的个数 800 1 000 0 400 600 200 地标点的个数 800 1 000 0 400 600 200 地标点的个数 800 1 000 LSC-K SCAL-K 本文算法 LSC-K SCAL-K 本文算法 LSC-K SCAL-K 本文算法 (a) MNIST 数据集 (b) COIL100 数据集 (c) CIFAR10 数据集 图 2 不同数据集上 3 种算法的 NMI 比较 Fig. 2 Comparison of the NMIs of three algorithms on dif￾ferent dataset 4 结束语 随着数据规模的增大，结构信息的复杂度提 高，在聚类过程中往往会耗费大量时间，存在相 似度矩阵存储开销大及矩阵分解复杂度高的问 题，且聚类精度也会受到影响。为此，本文提出 一种结合度量融合和地标表示的自编码谱聚类算 法，通过引入节点相对质量概念作为地标点选择 的依据，以地标点与其他样本点之间相似度构造 图相似度矩阵，以降低存储开销。同时，融合欧 氏距离与 Kendall Tau 距离作为相似度度量方式， 充分挖掘数据底层结构信息，且以栈式自编码器 代替拉普拉斯矩阵分解步骤，通过联合学习框架 进一步提高聚类精度。实验表明在几种大规模数 据集上本文算法具有较好的聚类性能，但由于本 ·694· 智 能 系 统 学 报 第 15 卷

第4期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·695· 文算法聚类精度受地标点个数影响较大，且选取 ing:incremental perspective and novel analysis[J].ACM 方式略微增加了算法复杂度，未来将致力于寻求 transactions on knowledge discovery from data,2016, 更为有效的地标点选择方式，在保证聚类精度的 11(11-25. 同时进一步降低算法复杂度。 [12]邓思宇，刘福伦，黄雨婷，等.基于PageRank的主动学 习算法).智能系统学报，2019,14(3)551-559. 参考文献： DENG Siyu,LIU Fulun,HUANG Yuting,et al.Active [1]WANG Lijuan,DING Shifei,JIA Hongjie.An improve- learning through PageRank[J.CAAl transactions on in- ment of spectral clustering via message passing and telligent systems,2019,14(3):551-559. density sensitive similarity[J].IEEE access,2019,7: [13]RAFAILID D.CONSTANTINOU E,MANOLO- 101054-101062 POULOS Y.Landmark selection for spectral clustering [2]LI Xinning,ZHAO Xiaoxiao,CHU Derun,et al.An au- based on weighted PageRank[J].Future generation com- toencoder-based spectral clustering algorithm[J].Soft com- puter systems,2017,68:465-472. puting,2020,24(3:1661-1671. [14]LIU Li,SUN Letian,CHEN Shiping,et al.K-PRSCAN: [3]王一宾，李田力，程玉胜.结合谱聚类的标记分布学 A clustering method based on PageRank[J].Neurocom- puting,2016,175:65-80. 习[.智能系统学报，2019,145)：966-973. WANG Yibin,LI Tianli,CHENG Yusheng.Label distri- [15]JIA Hongjie,DING Shifei,DU Mingjing,et al.Approx- imate normalized cuts without eigen-decomposition[J]. bution learning based on spectral clustering[J].CAAI Information sciences,2016,374:135-150. transactions on intelligent systems,2019,14(5):966-973. [4]赵晓晓，周治平.结合稀疏表示与约束传递的半监督谱 [16]TIAN Fei,GAO Bin,CUI Qing,et al.Learning deep rep- resentations for graph clustering[C]//Proceedings of the 聚类算法)智能系统学报，2018,13(5)855-863. 28th AAAI Conference on Artificial Intelligence.Quebec. ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spec- Canada,2014:1293-1299. tral clustering algorithm combined with sparse representa- [17]BANIJAMALI E,GHODSI A.Fast spectral clustering us- tion and constraint propagation[J].CAAI transactions on ing autoencoders and landmarks[C]//Proceedings of Inter- intelligent systems,2018,13(5):855-863. national Conference Image Analysis and Recognition. [5]LANGONE R,SUYKENS J A K.Fast kernel spectral Montreal,Canada,2017:380-388. clustering[J].Neurocomputing,2017,268:27-33. [18]光俊叶，邵伟，孙亮，等.基于融合欧氏距离与Kendall [6]ZHAN Qiang,MAO Yu.Improved spectral clustering Tau距离度量的谱聚类算法U.控制理论与应用，2017 based on Nystrom method[J].Multimedia tools and applic- 346):783-789 ations,.2017,76(19):20149-20165. GUANG Junye,SHAO Wei,SUN Liang,et al.Spectral [7]YANG Xiaojun,YU Weizhong,WANG Rong,et al.Fast clustering with mixed Euclidean and Kendall Tau spectral clustering learning with hierarchical bipartite metrics[J].Control theory applications,2017,34(6): graph for large-scale data[J].Pattern recognition letters, 783-789 2020,130(2:345-352. [19]WEI Kai,TIAN Pingfang,GU Jingguang,et al.RDF data [8]CHEN Xinlei,CAI Deng.Large scale spectral clustering assessment based on metrics and improved PageRank al- with landmark-based representation[C]//Proceedings of the gorithm[C]//Proceedings of International Conference on 24hAAAI Conference on Artificial Intelligence.San Fran- Database Systems for Advanced Applications.Suzhou, cisco,.USA,2011:313-318. China.2017:204-212. [9]CAI Deng,CHEN Xinlei.Large scale spectral clustering [20]谢娟英，丁丽娟.完全自适应的谱聚类算法).电子学 via landmark-based sparse representation[J].IEEE trans 报，2019,47(5)：1000-1008. cybern,2015,45(8):1669-1680. XIE Juanying,DING Lijuan.The true self-adaptive spec- [10们叶茂，刘文芬.基于快速地标采样的大规模谱聚类算 tral clustering algorithms[J].Acta electronica sinica, 法[.电子与信息学报，2017,39(2)：278-284 2019,47(5:1000-1008. YE Mao,LIU Wenfen.Large scale spectral clustering [21]NG A Y,JORDAN M I,WEISS Y.On spectral cluster- based on fast landmark sampling[J].Journal of electron- ing:analysis and an algorithm[C]//Proceedings of Neural ics and information technology,2017,39(2):278-284. Information Processing Systems 14,NIPS 2001.Van- [11]ZHANG Xianchao,ZONG Linlin,YOU Quanzeng,et al. couver,British Columbia,Canada,2002:849-856. Sampling for Nystrom extension-based spectral cluster- [22]XIE Juanying,ZHOU Ying,DING Lijuan.Local stand-

文算法聚类精度受地标点个数影响较大，且选取 方式略微增加了算法复杂度，未来将致力于寻求 更为有效的地标点选择方式，在保证聚类精度的 同时进一步降低算法复杂度。 参考文献： WANG Lijuan, DING Shifei, JIA Hongjie. An improve￾ment of spectral clustering via message passing and density sensitive similarity[J]. IEEE access, 2019, 7: 101054–101062. [1] LI Xinning, ZHAO Xiaoxiao, CHU Derun, et al. An au￾toencoder-based spectral clustering algorithm[J]. Soft com￾puting, 2020, 24(3): 1661–1671. [2] 王一宾, 李田力, 程玉胜. 结合谱聚类的标记分布学 习 [J]. 智能系统学报, 2019, 14(5): 966–973. WANG Yibin, LI Tianli, CHENG Yusheng. Label distri￾bution learning based on spectral clustering[J]. CAAI transactions on intelligent systems, 2019, 14(5): 966–973. [3] 赵晓晓, 周治平. 结合稀疏表示与约束传递的半监督谱 聚类算法 [J]. 智能系统学报, 2018, 13(5): 855–863. ZHAO Xiaoxiao, ZHOU Zhiping. A semi-supervised spec￾tral clustering algorithm combined with sparse representa￾tion and constraint propagation[J]. CAAI transactions on intelligent systems, 2018, 13(5): 855–863. [4] LANGONE R, SUYKENS J A K. Fast kernel spectral clustering[J]. Neurocomputing, 2017, 268: 27–33. [5] ZHAN Qiang, MAO Yu. Improved spectral clustering based on Nyström method[J]. Multimedia tools and applic￾ations, 2017, 76(19): 20149–20165. [6] YANG Xiaojun, YU Weizhong, WANG Rong, et al. Fast spectral clustering learning with hierarchical bipartite graph for large-scale data[J]. Pattern recognition letters, 2020, 130(2): 345–352. [7] CHEN Xinlei, CAI Deng. Large scale spectral clustering with landmark-based representation[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence. San Fran￾cisco, USA, 2011: 313−318. [8] CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE trans cybern, 2015, 45(8): 1669–1680. [9] 叶茂, 刘文芬. 基于快速地标采样的大规模谱聚类算 法 [J]. 电子与信息学报, 2017, 39(2): 278–284. YE Mao, LIU Wenfen. Large scale spectral clustering based on fast landmark sampling[J]. Journal of electron￾ics and information technology, 2017, 39(2): 278–284. [10] ZHANG Xianchao, ZONG Linlin, YOU Quanzeng, et al. Sampling for Nyström extension-based spectral cluster- [11] ing: incremental perspective and novel analysis[J]. ACM transactions on knowledge discovery from data, 2016, 11(1): 1–25. 邓思宇, 刘福伦, 黄雨婷, 等. 基于 PageRank 的主动学 习算法 [J]. 智能系统学报, 2019, 14(3): 551–559. DENG Siyu, LIU Fulun, HUANG Yuting, et al. Active learning through PageRank[J]. CAAI transactions on in￾telligent systems, 2019, 14(3): 551–559. [12] RAFAILID D, CONSTANTINOU E, MANOLO￾POULOS Y. Landmark selection for spectral clustering based on weighted PageRank[J]. Future generation com￾puter systems, 2017, 68: 465–472. [13] LIU Li, SUN Letian, CHEN Shiping, et al. K-PRSCAN: A clustering method based on PageRank[J]. Neurocom￾puting, 2016, 175: 65–80. [14] JIA Hongjie, DING Shifei, DU Mingjing, et al. Approx￾imate normalized cuts without eigen-decomposition[J]. Information sciences, 2016, 374: 135–150. [15] TIAN Fei, GAO Bin, CUI Qing, et al. Learning deep rep￾resentations for graph clustering[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence. Québec, Canada, 2014: 1293−1299. [16] BANIJAMALI E, GHODSI A. Fast spectral clustering us￾ing autoencoders and landmarks[C]//Proceedings of Inter￾national Conference Image Analysis and Recognition. Montreal, Canada, 2017: 380−388. [17] 光俊叶, 邵伟, 孙亮, 等. 基于融合欧氏距离与 Kendall Tau 距离度量的谱聚类算法 [J]. 控制理论与应用, 2017, 34(6): 783–789. GUANG Junye, SHAO Wei, SUN Liang, et al. Spectral clustering with mixed Euclidean and Kendall Tau metrics[J]. Control theory & applications, 2017, 34(6): 783–789. [18] WEI Kai, TIAN Pingfang, GU Jingguang, et al. RDF data assessment based on metrics and improved PageRank al￾gorithm[C]//Proceedings of International Conference on Database Systems for Advanced Applications. Suzhou, China, 2017: 204−212. [19] 谢娟英, 丁丽娟. 完全自适应的谱聚类算法 [J]. 电子学 报, 2019, 47(5): 1000–1008. XIE Juanying, DING Lijuan. The true self-adaptive spec￾tral clustering algorithms[J]. Acta electronica sinica, 2019, 47(5): 1000–1008. [20] NG A Y, JORDAN M I, WEISS Y. On spectral cluster￾ing: analysis and an algorithm[C]//Proceedings of Neural Information Processing Systems 14, NIPS 2001. Van￾couver, British Columbia, Canada, 2002: 849−856. [21] [22] XIE Juanying, ZHOU Ying, DING Lijuan. Local stand- 第 4 期 张敏，等：结合度量融合和地标表示的自编码谱聚类算法 ·695·

·696· 智能系统学报 第15卷 ard deviation spectral clustering[C]//Proceedings of the 作者简介： 2018 IEEE International Conference on Big Data and Smart Computing (BigComp).Shanghai,China,2018: 张敏，硕士研究生，主要研究方向 242-250. 为数据挖掘。 [23]WANG Bo,JIANG Jiayan,WANG Wei,et al.Unsuper- vised metric fusion by cross diffusion[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pat- tern Recognition.Providence,Rhode Island,2012: 2997-3004 [24]COIFMAN RR,LAFON S.Diffusion maps[J].Applied 周治平，教授，博士，主要研究方 and computational harmonic analysis,2006,21(1):5-30. 向为智能检测、网络安全。发表学术 论文80余篇。 [25]XIE Junyuan,GIRSHICK R B,FARHADI A.Unsuper- vised deep embedding for clustering analysis[C]//Pro- ceedings of the 33nd International Conference on Ma- chine Learning.New York,USA,2016:478-487. 第五届认知系统和信息处理国际会议 认知系统和信息处理国际会议(ICCSIP)每两年举办一次，已成为认知科学、智能系统、机器人等领域学 者与企业的交流桥梁，为促进海内外学者的交流提供了全球化的平台，目前已举办4届，录用的论文在 Springer出版。当前正是认知科学与人工智能的飞速发展期，二者的结合与交融有利于触发瞬间灵感，推动 创新步伐。因此，第五届认知系统和信息处理国际会议(ICC$P2020)主题为”面向人工智能的认知计算”，并 于2020年12月18-20日在中国珠海横琴岛召开，希望推动认知、心理、智能、机器人等领域的融通交汇。此 外，还将特别设立科技抗疫专题，欢迎各界人士依托此平台为全球科技抗疫贡献力量。同时国际会议现场 还举办中国人工智能学会认知系统与信息处理专委会的年会。 1.专辑录用的优秀论文将会推荐至下列期刊专辑发表： 1)Cognitive Computation and Systems;2)InternationalJournal of Control,Automation,and Systems;3)Robotics and Autonomous Systems;4)Science China:Information Sciences;5)Tsinghua Science and Technology(English Ver- sion):6)IEEE Transactions on Cognitive and Development Systems;7)IEEE Transactions on Fuzzy Systems. 2.主题（包含但不限于）： 认知系统：认知科学与技术，视觉认知处理，听觉认知处理，新颖认知计算模型，认知指标，认知心理学，认 知机器人学，认知无线电，认知雷达。 信息处理：信息表示与度量，多模态信息交互与融合，大数据和智能信息处理，神经认知计算与学习，视觉 信息处理，脑机接口，生物信息学及应用，灵巧操作的多模态认知机制，极限学习及应用。 3.重要日期： 投稿截止：2020.10.10 录用通知：2020.10.30 会议注册：2020.11.20 4.联系我们： E-mail:csip2020-2020@163.com,手机号：15952525480 更多信息请详见：http:/iccsip2020.caai.cnl

ard deviation spectral clustering[C]// Proceedings of the 2018 IEEE International Conference on Big Data and Smart Computing (BigComp). Shanghai, China, 2018: 242−250. WANG Bo, JIANG Jiayan, WANG Wei, et al. Unsuper￾vised metric fusion by cross diffusion[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pat￾tern Recognition. Providence, Rhode Island, 2012: 2997−3004. [23] COIFMAN R R, LAFON S. Diffusion maps[J]. Applied and computational harmonic analysis, 2006, 21(1): 5–30. [24] XIE Junyuan, GIRSHICK R B, FARHADI A. Unsuper￾vised deep embedding for clustering analysis[C]//Pro￾ceedings of the 33nd International Conference on Ma￾chine Learning. New York, USA, 2016: 478−487. [25] 作者简介： 张敏，硕士研究生，主要研究方向 为数据挖掘。 周治平，教授，博士，主要研究方 向为智能检测、网络安全。发表学术 论文 80 余篇。 第五届认知系统和信息处理国际会议 认知系统和信息处理国际会议（ICCSIP）每两年举办一次，已成为认知科学、智能系统、机器人等领域学 者与企业的交流桥梁，为促进海内外学者的交流提供了全球化的平台，目前已举办 4 届，录用的论文在 Springer 出版。当前正是认知科学与人工智能的飞速发展期，二者的结合与交融有利于触发瞬间灵感，推动 创新步伐。因此，第五届认知系统和信息处理国际会议 (ICCSIP2020) 主题为”面向人工智能的认知计算”，并 于 2020 年 12 月 18-20 日在中国珠海横琴岛召开，希望推动认知、心理、智能、机器人等领域的融通交汇。此 外，还将特别设立科技抗疫专题，欢迎各界人士依托此平台为全球科技抗疫贡献力量。同时国际会议现场 还举办中国人工智能学会认知系统与信息处理专委会的年会。 1.专辑录用的优秀论文将会推荐至下列期刊专辑发表： 1）Cognitive Computation and Systems；2）InternationalJournal of Control, Automation, and Systems；3）Robotics and Autonomous Systems；4）Science China: Information Sciences；5）Tsinghua Science and Technology (English Ver￾sion)；6）IEEE Transactions on Cognitive and Development Systems；7）IEEE Transactions on Fuzzy Systems。 2.主题（包含但不限于）： 认知系统：认知科学与技术,视觉认知处理,听觉认知处理,新颖认知计算模型,认知指标,认知心理学,认 知机器人学,认知无线电,认知雷达。 信息处理：信息表示与度量,多模态信息交互与融合,大数据和智能信息处理,神经认知计算与学习,视觉 信息处理,脑机接口,生物信息学及应用,灵巧操作的多模态认知机制,极限学习及应用。 3.重要日期： 投稿截止：2020.10.10 录用通知：2020.10.30 会议注册：2020.11.20 4.联系我们： E-mail:csip2020-2020@163.com，手机号：15952525480 更多信息请详见：http://iccsip2020.caai.cn/ ·696· 智 能 系 统 学 报 第 15 卷