第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·