基于黎曼流形的多视角谱聚类算法

李林珂，康昭，龙波

（1.电子科技大学 格拉斯哥学院，成都 611731；2.电子科技大学 计算机科学与工程学院，成都 611731；3.西南技术物理研究所，成都 610041）

0 概述

聚类分析是数据挖掘与机器学习领域中的研究热点，也是一种重要的数据分析技术［1-3］。传统的聚类分析旨在将单个视角的物理或抽象集合分成相似对象类，但由于数据来源的多样性，同一个数据可能有不同的观察视角［4］，例如文本可以由不同语言表示，图像可以有不同的特征描述符。多视角聚类旨在从多个视角的数据中学习一个新的统一表示，再将该表示输入到传统的聚类算法中。最简单的结合多视角数据信息的方法是将各视图特征直接拼接起来，得到单视图数据进行聚类［4-5］，但这种方法没有考虑到不同视角数据的差异性对最优解的影响。因此，多视角聚类的主要难点在于如何有效结合不同视角数据的互补信息。

近年来，多视角聚类算法主要分为基于矩阵分解、基于子空间聚类和基于谱聚类三类［6］。基于矩阵分解的多视角聚类算法旨在寻找一个共同的指示矩阵，现有许多研究将非负矩阵分解应用在多视角问题中［7-9］，受深度学习的影响，一些基于深度矩阵分解的方法也被提出［10］，此外还有一些基于核的方法［11］。基于子空间聚类的多视角聚类算法［12-14］将数据分散到不同的子空间中，并为数据寻找合适的低维子空间，代表算法包括稀疏子空间聚类［15］、基于格拉斯曼流形的子空间聚类［16］等。基于谱聚类的多视角聚类算法［17］旨在通过矩阵特征分解在局部流形结构上获得数据划分的一致性。

与其他算法相比，谱聚类算法的实现过程相对简单，且不易陷入局部最优解［18］。提升对各视角互补信息的提取利用率，是提高谱聚类算法效果的关键步骤。现已有多种方法用于提升谱聚类算法对不同视角数据的利用率［19-20］。根据现有的互补信息提取方法，将多视角谱聚类算法分为以下三大类［21］：第一类采用联合训练方式，使得各个视角的聚类结果彼此关联［4，19］；第二类假设预定义的邻接矩阵是最优邻接矩阵的扰动，然后通过低秩优化或稀疏优化，从所有视角中构造一个最优的邻接矩阵［20，22］；第三类线性或凸性结合了不同视角的拉普拉斯矩阵，并通过最小化组合矩阵的归一化分割来优化基拉普拉斯矩阵的组合系数［23］。

近年来，第三类方法在多视角谱聚类领域被广泛应用，且有多种相关创新方法用于结合不同视角的基拉普拉斯矩阵。在传统算法中：平均多视角谱聚类（Average Multi-View Spectral Clustering，A-MVSC）为每个视角的拉普拉斯矩阵分配相同的权重值，以得到一个新的拉普拉斯矩阵；单一视角最佳效果谱聚类（Single Best Spectral Clustering，SB-SC）在对每个视角分别进行谱聚类后，选取其中最佳的聚类效果。在典型的相关创新算法中：文献［24］提出的自动加权多图学习（Autoweighted Multiple Graph Learning，AMGL）在不引入附加参数的情况下，自动学习每个基拉普拉斯的最佳权重值；文献［25］采用最大正则角（Canonical Angle）来度量不同视角下谱聚类结果的差异；文献［21］提出的基于最优邻域的多视角谱聚类算法（Multi-view Spectral Clustering with Optimal Neighborhood Laplacian Matrix，ONMSC）使最优拉普拉斯矩阵落在所有基拉普拉斯矩阵的邻域内，并引入高阶拉普拉斯矩阵，提高了最优拉普拉斯矩阵对各视角信息的利用率；对于高阶拉普拉斯矩阵中引入的高阶连接信息，文献［26］在图嵌入的研究中指出，顶点之间的一阶连接信息代表了图的顶点间的局部相似关系，二阶连接信息表现了拥有相同近邻的顶点也具有相似性；文献［21］将高阶连接信息应用在多视角谱聚类算法中，在一定程度上提高了聚类的效果，同时研究了各阶连接信息对聚类效果的影响，发现随着所用拉普拉斯矩阵阶数的增大，近邻数的范围变大，相应算法的判别能力也随之下降。

传统的线性与凸性结合方法虽然具有高效性，却无法很好地获得每一视角中数据的结构信息。而对称正定（Symmetric Positive Definite，SPD）流形中的黎曼几何均值［27］将不同视角的拓扑信息结合，相比于传统算法，更加有效地提取出了各层数据的特征。现有大量基于随机块模型的多层图研究［28-30］存在。例如，文献［27］将SPD 几何均值与特征嵌入结合，提高了多层网络数据聚类的效果。

为更好地将各视角数据的互补信息引入到用于谱聚类的最优拉普拉斯矩阵中，本文提出一种基于黎曼几何均值与高阶连接信息的多视角谱聚类算法。按一定的权重线性结合单一视角的各阶拉普拉斯矩阵，将其作为该视角的基拉普拉斯矩阵。在此基础上，计算各视角的基拉普拉斯矩阵的几何均值即最优拉普拉斯矩阵并作为输入进行谱聚类。本文方法利用黎曼几何均值来聚合各视图信息，充分挖掘数据中的流形信息，同时引入高阶拉普拉斯矩阵，实现对数据中高阶连接信息的挖掘。

1 相关工作

1.1 谱聚类

谱聚类算法是由图论演变而来、基于谱图划分理论的聚类算法［31］，其将所有数据样本定义为无向图G=(X,E)的顶点，将样本数据的相似性看作点与点之间带权重的边，从而建立邻接矩阵（相似度矩阵），并求得正则拉普拉斯矩阵进行降维。对所有新数据点分组，使同一组对象之间具有较高的相似度而不同组的差异较大，从而达到聚类的目的。谱聚类算法的具体步骤如下：

定义图G=(X,E)。其 中：X=[x1,x2,…,xn]T∈Rn×d为图的顶点集，即数据样本集；n为样本数；d为样本的特征维度；E为连接顶点之间边的集合。基于k 近邻（k-Nearest Neighbor，kNN）算法，可以对给定的数据集X与核函数κ(·,·) 构造邻接矩阵A∈Rn×n，即xi、xj中只要有一个在对方的k个近邻中时，则被视为互相关联的，其距离可由核函数κ(·,·)表示。邻接矩阵A的i行j列被构造如下：

同时，可以得到相应的度矩阵D∈Rn×n：

相应的一阶正则拉普拉斯矩阵被定义为：

定义H∈Rn×c为聚类指示矩阵，其中c为类别数，则标准化谱聚类的目标函数如下：

1.2 高阶拉普拉斯矩阵

现有研究表明，高阶连接信息能够有效提高多视角谱聚类的效果，且在使用二阶连接信息时，聚类效果与运算效率相对较好。因此，本文只引入图的二阶连接信息，研究其对本文算法聚类效果的影响。

定义二阶邻近性［21］

二阶邻近性指的是网络中的一对顶点(u,v)的近邻网络结构的相似性。令aj为一阶邻接矩阵A的第j列，则二阶邻接矩阵A(2)可被定义如下：

其相应的度矩阵可被定义为：

由此可以得到二阶正则拉普拉斯矩阵：

1.3 多视角谱聚类

多视角谱聚类可被视为对多图的聚类问题，其无向图可被表示为：

其中：V≥1 表示视角的数目，也是图的个数。对每个视 角p∈{1,2,…,V} 构造其邻接矩 阵A1,A2,…,AV∈Rn×n与一阶正则拉普拉斯矩阵L1,L2,…,LV∈Rn×n。为了在聚类时应用每个视角的数据特征，文献［23］线性结合了各个视角的拉普拉斯矩阵，并得到了用于谱聚类的最优拉普拉斯矩阵，其目标函数如下：

其中：μp表示第p个视角的线性组合权重值，共有V个视角；向量μ为各个视角拉普拉斯矩阵的权重值集；r是平衡各个视角贡献度的超参数。但是文献［23］算法过度缩减了最优拉普拉斯矩阵的可行集［11］，导致解决方案代表性较弱，其性能可能略逊于使用单个视角进行聚类的效果。

文献［21］考虑了低阶与高阶拉普拉斯矩阵的特性，使最优拉普拉斯矩阵落在各阶拉普拉斯矩阵线性结合后的邻域中，并用该最优拉普拉斯矩阵进行谱聚类，其目标函数如下：

其中：L*表示最优拉普拉斯矩阵；表示第u阶基拉普拉斯矩阵的线性组合；O为最高阶数，[O]等同于{1,2,…,O}；γ为重要程度平衡系数。在式（12）中，相关性测量矩阵M记录了邻接矩阵之间的内核校准值［32］，其定义如下：

文献［21］算法虽然增强了用以谱聚类的拉普拉斯矩阵的不同视角的数据信息表示能力，且提高了谱聚类的聚类效果，但是仍然没有很好地结合各视角的拉普拉斯矩阵的信息。

1.4 黎曼几何均值

基于图论的随机块模型（Stochastic Block Model，SBM）是近年来普遍用于非标准数据聚类与社区检测的聚类方法，其原理与谱聚类算法类似，但数据节点间的邻接关系在谱聚类算法中被表示为给定值，在随机块模型中却被表示为伯努利随机变量，可根据概率对等性对该模型中具有相似特征的节点进行分类［33-34］。在随机块模型的多层数据聚类问题中，相比于矩阵的算数平均值，矩阵幂均值在幂趋于-∞时更好地恢复了互补层数据的聚类信息。

黎曼几何均值是一种基于SPD 流形中黎曼距离的矩阵幂均值。寻找不同图SPD 矩阵的黎曼几何均值的过程，等同于寻找一个到各个图SPD 矩阵{Lp}1≤p≤V黎曼距离最小 的SPD矩阵L的过程，可表示为［35］：

其中：Φ(·,·)算子表示对SPD 矩阵的一系列操作；η(N)表示N×N的SPD 矩阵的流形；D：η(N)×η(N)→R为相应距离。

式（14）中黎曼距离D的具体表达式如下［35］：

其中：Log 表示SPD 矩阵的对数运算。在这种情况下，不同图的信息都能被最优SPD 矩阵L较好地表现出来。

2 多视角谱聚类算法

2.1 几何均值与一阶拉普拉斯矩阵的结合

在传统的多视角谱聚类算法中，用于谱聚类的最优拉普拉斯矩阵由各视角的拉普拉斯矩阵线性结合所得。这种信息结合方式类似于算数均值的运算，没有很好地考虑到不同视角的特有拓扑信息，从而降低了最优拉普拉斯矩阵的代表性。

为提高数据的利用率，本文首先计算不同视角下相应的一阶基拉普拉斯矩阵的黎曼几何均值，即最优拉普拉斯矩阵L*，并将其作为谱聚类算法的输入矩阵得到最终的聚类结果。该过程可用以下目标函数表示：

2.2 几何均值与高阶拉普拉斯矩阵的结合

为更好地在最优拉普拉斯矩阵L*中表示出各视角的信息，本文将黎曼几何均值与高阶拉普拉斯矩阵的思想相结合。首先按一定的权重值αu(u∈[O])线性结合单一视角的各阶拉普拉斯矩阵，作为该视角的基拉普拉斯矩阵；然后计算各视角相应的基拉普拉斯矩阵的几何均值，并将该几何均值作为谱聚类算法的输入，进行数据聚类。具体步骤如下：

1）计算得到最优拉普拉斯矩阵L*。

获得最优拉普拉斯矩阵的目标函数如下：

其中：αu为第u阶拉普拉斯矩阵的权重值。当V＞2时，该问题没有闭式解，因此，本文通过Fréchet-Karcher 梯度流计算其几何均值。具体的迭代过程如下［36］：

2）计算得到最优的聚类指标矩阵H。

得到最优拉普拉斯矩阵L*后，将其作为输入代入以下目标函数：

根据谱聚类的基本性质易得，H的最优解为矩阵L*的与c个最小特征值相对应的特征向量所构成的矩阵。

综上所述，完整的基于高阶拉普拉斯矩阵与黎曼几何均值的多视角谱聚类算法（Riemann Manifold based Multi-view Spectral Clustering，RMMSC）描述如下：

算法RMMSC 算法

输入样本数n，数据类别数c，V个特征视角的数据集[x1,x2,…,xV]T，各阶拉普拉斯矩阵平衡参数αu，迭代步长β，近邻数N

输出最优拉普拉斯矩阵L*，最优聚类指标矩阵H

步骤1建立数据各视角的各阶邻接矩阵与正则拉普拉斯矩阵。

步骤2 初始化：

步骤3重复式（18），直到满足迭代停止条件：

步骤4通过式（19）计算H。

对于最终得到的H，RMMSC 算法用K-means 算法为样本的最终聚类结果分配对应的标签。为减小K-means 算法的随机性，本文在每一次实验中，对其聚类过程重复50 次，并取具有最小K-means 损失值的聚类结果。

2.3 算法复杂度

本文算法采用的迭代方法涉及矩阵对数与指数的运算，其对应时间复杂度为O(n3)。最终对H的计算涉及对大小为n2的矩阵的奇异值分解（Singular Value Decomposition，SVD）问题，其对应的时间复杂度也为O(n3)［21］。总体而言，算法复杂度为O(In3)，其中I为迭代次数，这与现有多数算法的复杂度处于同一数量级，例如AMGL［24］、ONMSC［21］。

3 实验

为验证本文方法的聚类效果，选择5 个当下流行的数据集，分别从聚类精度（ACC）、归一化互信息（NMI）、纯度（Purity）这三个角度与已有的7 个聚类算法做对比实验。实验的计算机环境为：处理器为Intel®CoreTMi5-8400 CPU@2.80 GHz，内存16 GB，操作系统为Windows10，编程语言为MATLAB R2017a（64 位）。RMMSC 算法源代码链接为：https：//github.com/sckangz/RMMSC。

3.1 数据集

本文采用包括自然语言处理、图像识别、图像处理等分支，机器学习中常用的5 个数据集作为测试数据集，如表1 所示。

表1 实验数据集属性Table 1 The attributes of datasets in experiment

各个数据集主要属性的具体描述如下：

Flower17：本数据集包含17 个英国常见的花朵类别，每个类别包含80 幅图，共1 360 个样本，有hsv、hog、color、shape 等7 个特征维度。

BBCSport：本数据集由英国广播公司体育网站的文件组成。选取其中554 个样本，包含5 个领域的体育新闻文章（田径、板球、足球、橄榄球、网球）。数据集包含从两个特征维度构造的矩阵。

UCI-Digit：本数据集包含手写数字0～9的2 000个样本，共10 个类别。本实验使用了样本的3 个特征集，分别为76 个字符形状的傅里叶系数、216 个轮廓相关的特征以及64 个Karhunen-love 系数。

Mfeat：本数据集包含摘自荷兰实用地图集的手写数字0～9 的2 000 个样本，共有10 个类别，每个类别200 个图案。本实验使用样本的12 个特征集。

Caltech101mit：本数据集是由102 个类别的对象图片组成的数据集，这些图像分别隶属于102 个种类，包含大象、自行车、足球、人类的大脑等，主要用于目标识别和图像分类，共1 530 个样本、25 个特征视角。

3.2 实验设定

根据谱聚类相关文献，为达到较好的实验效果，本文对实验中涉及的3 个主要超参数进行设定。近邻数在[0.05s,0.15s,…,0.95s]中取值，其中s=n/c为平均样本数。经验证发现，近邻数取值在10 附近时算法聚类效果相对较好。由于本实验只涉及一二阶拉普拉斯矩阵的应用，2.2节中算法的各阶拉普拉斯矩阵的平衡参数αu被简化为参数α，即在线性结合时，设置一阶拉普拉斯矩阵的权重为1，二阶拉普拉斯矩阵的权重为α。同时，经所用数据集验证，算法在迭代步长为0 ＜β＜时收敛，且在取值为时算法体现出较好的收敛效果与较快的收敛速度［37］。

除此之外，由于拉普拉斯矩阵是对称半正定矩阵，其特征向量的所有元素为0 或正数。但MATLAB 中的矩阵对数函数（logm）无法对特征值中含有非正数的矩阵进行运算，即logm 函数的输入矩阵需要为对称正定矩阵，而对称半正定拉普拉斯矩阵特征向量中的0 元素则影响了logm 函数的正常使用。为解决此问题，本文对各视角的基拉普拉斯矩阵归一化处理至（0，1），从而避免logm 函数无法运算得到正确结果的情况.

3.3 评估指标

本文实验采用以下3 个常用的评价指标来评价算法的聚类效果：

1）精确度（ACC），用于比较聚类结果的标签与数据集所提供的标签的匹配度，计算公式如下：

其中：li与分别表示xi的聚类结果与相应的聚类标签；n为样本总数。当且仅当x=y时，函数δ(x,y)=1，其他情况下为0。基于Kuhn-Munkres 算法［38］，置换映射函数map(.)将每个聚类的索引映射到具体的标签上。

2）归一化互信息（Normalized Mutual Information，NMI），用于衡量两个聚类结果的相似程度即聚类效果，计算公式如下：

3）纯度（Purity），即正确聚类样本数占总样本数的比例，计算公式如下［39］：

其中：ni表示 类别Ci中数据点 的个数表示第i组输入数据被分配到第j类的样本个数。算法的ACC、NMI、Purity 指标值越大，聚类效果越好。

3.4 对比算法

为证明本文算法的有效性，将其与7 个现有的多视角谱聚类算法以及多核聚类算法进行对比。

1）平均多视角谱聚类（Average Multi-View Spectral Clustering，A-MVSC）算法，其为每个视角的拉普拉斯矩阵分配相同的权重值，以得到一个新的拉普拉斯矩阵进行聚类。

2）单一视角最佳效果谱聚（Single Best Spectral Clustering，SB-SC）算法，其对每个视角分别进行谱聚类，并选取最佳的聚类效果。

3）自动加权多图学习（Auto-weighted Multiple Graph Learning，AMGL）算法［24］，该算法可以自动学习每个图的最优权值，且不需要引入附加参数。

4）自适应近邻的多视角学习（Multiview Learning with Adaptive Neighbors，MLAN）算 法［40］，该算法可以同时进行聚类和局部结构学习。

5）最优邻域的多核聚类（Optimal Neighbors Kernel Clustering，ONKC）算法［11］，该算法构造了有自适应能力的局部核，充分考虑了单个数据样本的局部密度。

6）基于矩阵诱导正则化的多核K 均值聚类（Multiple Kernel k-means Clustering with Matrix Induced Regularization，MKKM-MR）算法［10］，该算法减少了冗余核对聚类结果的影响，增强了所选核的多样性。

7）基于最优邻域拉普拉斯矩阵的多视角谱聚类（Multi-View Spectral Clustering with Optimal Neighborhood Laplacian Matrix，ONMSC）算法［21］，该算法引入了低阶与高阶拉普拉斯矩阵的最优邻域，增强了最优拉普拉斯函数的容量，且利用隐藏的高阶连接信息获得了较好的收敛性。

3.5 实验结果

基于一阶拉普拉斯矩阵和二阶拉普拉斯矩阵的几何均值的多视角谱聚类性能如表1 和表2 所示，其中最优数据加粗表示。可以看出，本文算法在Flower17、BBCSport，UCI-Digit、Mfeat 数据集中的聚类效果普遍优于其他对比算法。以Flower17 数据集为例，其ACC 较基准模型ONMSC 提高了1.47 个百分点，Purity 提高了1.04 个百分点。但Caltech101mit数据集聚类的ACC 与Purity 稍低于ONMSC。

表2 不同聚类算法在5 个基准数据集上的性能对比Table 2 Performance comparison of different clustering algorithms on five benchmark datasets

相比于一阶拉普拉斯矩阵和二阶拉普拉斯矩阵的单独应用，按一定权重值结合一阶与二阶拉普拉斯矩阵在一定程度上提升了Flower17、BBCSport、Caltech101mit数据集的聚类效果。对于Flower17 数据集，ACC 提高了0.67 个百分点，NMI 提高了0.93 个百分点，Purity提高了0.66个百分点。而UCI-Digit与Mfeat数据集在应用二阶拉普拉斯矩阵后，也表现出高于AMGL、MLAN、ONMSC 等算法的聚类效果。

由于本文算法包含多次对矩阵的开方（sqrtm）与对数（logm）运算，在所选数据集最优结果对应的参数取值下，其平均运行时间约为365 s（对于小样本数据集，如BBCSport 运算时间极短，为4 s；但对大样本数据集如Caltech101 运行时间较长，为483 s），长于基准模型ONMSC 算法的平均运行时间27 s。但本文算法达到收敛所需的迭代次数普遍少于ONMSC 算法。

3.6 参数分析

3.6.1 参数灵敏度

本文算法共涉及3 个参数：α，β，s。其中：α为二阶拉普拉斯矩阵的权重；β为迭代步长；s为平均样本数，用以计算近邻数。为检验RMMSC 的参数灵敏度，本文应用了网格搜索的方法，固定2 个参数，在一定范围内改变其他参数的值。对参数进行灵敏性分析后发现，β对各数据集聚类效果影响极小，可忽略不计；α对聚类结果有一定的影响，但在较大的参数范围内相对稳定；s对BBCSport 数据集聚类结果影响较大，而对其他数据集影响相对较小。同时，该算法在多个参数取值下的结果皆优于基准算法ONMSC，说明其可行性强。图1～图3 展示了算法对选取的2 个数据集（Flower17 与Caltech101mit）的参数灵敏度，可以看出，对于Caltech101mit，算法在s=0.05 时不收敛，无法得到有效聚类结果。

图1 参数α 对聚类效果的影响Fig.1 Parameter α’s influence on clustering effect

图2 s 与α 对聚类效果的共同影响Fig.2 Joint influence of s and α on clustering effect

图3 参数s 对聚类效果的影响Fig.3 Parameter s’s influence on clustering effect

3.6.2 算法收敛

对所用数据集，本文在特定参数下测试所提算法的迭代收敛性。图4 显示了收敛性测试结果，其中横坐标表示迭代的次数，纵坐标表示两次连续迭代所得的拉普拉斯矩阵的差值矩阵的二范数。可以看出，在合适的参数取值下，所用数据集均在15 次迭代内达到了较好的收敛效果。

图4 本文算法收敛性分析Fig.4 Convergence analysis of the proposed algorithm

4 结束语

本文提出一种基于高阶拉普拉斯矩阵与黎曼几何均值的多视角谱聚类算法。由于顶点之间的二阶邻近性反映出拥有相同近邻的顶点也在对方的邻域中，因此与传统的谱聚类算法相比，该算法一阶与二阶拉普拉斯矩阵的共同应用提高了不同视角基拉普拉斯矩阵对视角信息的表达能力。此外，相比于算术均值的使用，SPD 流形下的黎曼几何均值将各视角的拓扑信息概括到单个最优拉普拉斯矩阵，使最终用于谱聚类的拉普拉斯矩阵更好地表达了各视角数据的互补信息。在多个数据集上的测试结果表明，该算法具有较好的聚类性能与收敛性。本文同时给出了具有较快收敛速率与聚类效果的推荐参数取值。后续将会进一步优化本文算法，缩短其在较大数据集下的运算时间，同时也将结合子空间聚类思想，进一步提高聚类性能。