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

第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):i<j.((La <L)A(Ln<L))or((La >Ln)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 < j,((Li1 < Lj1)∧(Li2 < Lj2))or((Li1 > 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·