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