Grassmann流形优化用于稀疏谱聚类

52580Grassmann流形优化辅助稀疏谱聚类0王琼 a 高俊斌 b 李宏 a0中国华中科技大学数学与统计学院，武汉4300740{ wangqiong701,hongli } @hust.edu.cn b商学分析学学科，悉尼大学商学院，悉尼大学，澳大利亚新南威尔士州20060junbin.gao@sydney.edu.au0摘要0谱聚类是先驱聚类方法之一。它依赖于谱分解准则来学习数据的低维嵌入，用于基本聚类算法。稀疏谱聚类（SSC）通过施加稀疏诱导惩罚来在低维空间中引入相似性的稀疏性，从而产生一个非凸优化问题。该问题通过标准ADMM（交替方向乘子法）求解松弛凸问题，而不是通过推断特征结构来推断潜在表示。本文提供了一个直接解决方案，即解决一个新的Grassmann优化问题。通过这种方式，计算潜在嵌入成为流形上的优化的一部分，最近发展起来的流形优化方法可以应用于此。结果表明，学习到的新特征不仅对聚类非常有信息量，而且在降维后的可视化中更直观有效。我们对模拟数据集和几个真实世界基准数据集进行了实证研究，以验证所提出的方法。实验结果展示了这种基于流形的聚类和降维方法的有效性。01. 引言0聚类是探索性数据分析中的主要无监督学习任务之一，应用范围从统计学、计算机科学、生物学到社会科学或心理学[13]。数据聚类的重点已经从经典的以质心为导向的聚类[4]转移到了子空间聚类[13,24]，其中数据根据它们对子空间结构的亲和力进行聚类。在不同的动机下，研究人员开发了许多类型的聚类算法。谱聚类（SC）[10]是机器学习中的先驱聚类方法之一。0社区。我们已经看到它在运动分割[13]、图像分割[22]、语音分离[3]、科学期刊聚类和功率负载聚类[17]等方面的应用。一般来说，谱聚类算法的两个主要步骤是，参考第2节或[10,21]等，（1）为给定的数据样本集形成/学习相似性/亲和性矩阵；（2）执行常规聚类方法对数据样本进行分类，如归一化割（NCut）[22]。这两个主要步骤决定了谱聚类方法的性能。已经进行了大量的工作来改进SC方法的性能，通过学习更好的亲和矩阵和推断数据的新表示。本文与第二范式相关，旨在学习原始数据的潜在表示。由于这两个范式高度相关，因此值得回顾第一范式的最近研究。谱聚类方法中学习相似性/亲和性矩阵的两个经典代表是稀疏子空间聚类（SSubC）[13]和低秩表示（LRR）[18]。SSubC和LRR都依赖于线性空间中的自表达属性[13]：联合子空间中的每个数据点都可以通过数据集中其他点的线性组合来高效重构。SSubC通过独立方式利用l1子空间检测属性进一步引入稀疏性，而LRR模型通过低秩要求以整体方式考虑数据对象之间的内在关系。已经证明，当数据集实际上由多个子空间的并集组成时，LRR方法可以通过子空间聚类揭示这种结构[19,8]。自表达属性建立在数据之间的线性关系上。为了利用数据的流形结构，特别是流形值数据中隐藏的非线性信息，一些作者已经探索了流形几何的自表达，并扩展了Stiefel的LRR。L = I − D− 12 WD− 12minU∈RN×d⟨UUT , L⟩s.t.UT U = I.(1)52590流形[28]，正定流形[14]和Grassmann流形[25,26]。在第二个范式中，许多研究者将其视为学习信息潜在表示的对象。在最近的稀疏谱聚类（SSC）中，Lu等人[20]指定了一种稀疏引起的惩罚来学习更多受欢迎的聚类潜在表示。由于非Frobenius范数约束，解决方案不再由特征向量决定，潜在表示通过后期计算得出。事实上，SC的目标是描述相似性/亲和力矩阵的特征结构与潜在表示所暗示的分区之间的接近程度[3]。换句话说，与显式推断特征结构的潜在表示不同，学习子空间结构应该是期望的。这提示在子空间上实施SC优化是必要且更合理的，即在Grassmann流形上的点。近年来，Grassmann流形[5,9]在计算机视觉研究社区中引起了极大的兴趣，用于众多应用任务。从数学上讲，Grassmann流形G(d,N)定义为R^N中所有d维子空间的集合，其中0 ≤ d ≤N。其黎曼几何最近在文献中得到了很好的研究，例如[2, 1,12]。这为在Grassman流形上定义的任何优化问题的解决铺平了道路。事实上，近年来，机器学习社区一直关注用于机器学习任务的流形优化。Theis等人[23]将独立成分分析与降维作为Stiefel流形上的优化问题。Journee等人[16]也将稀疏主成分分析框架应用于该流形。Cunningham和Ghahramani[11]提出了一个统一的降维框架。第2节将清楚地说明如何将Grassmann流形优化嵌入SC框架中。与前述的LRR子空间聚类方法相比，SSubC具有自己的优势，例如其鲁棒性和较低的计算复杂性。本文与通过Grassmann流形优化学习更好和更高效的潜在特征表示有关。结果表明，学习到的新特征不仅对聚类非常有信息性，而且在降维后的可视化中更直观和有效。本文的主要贡献是：01.我们采用Grassmann流形优化策略，以优化[20]中引入的稀疏谱聚类目标。02.我们将标准的ADMM（交替方向乘子法）[6]与Grassmann流形优化相结合，受到最近的研究[7]的启发。03. 我们探索了基于给定解的新SC算法在降维上的应用。0通过Grassmann流形优化算法。0本文的结构如下。第2节总结了相关工作和SC和SSC的预备知识。第3节重点介绍Grassmann流形优化的框架，并开发必要的优化相关要素。最后，提出了在Grassmann流形上解决所提出模型的聚类算法。第4节通过对数据和真实世界数据集上的聚类和降维问题进行评估，评估了所提出方法的性能。最后，在第5节中提供了结论和未来工作的建议。02. 问题再探0在继续之前，我们先简要介绍谱聚类。假设0X = [x1, ∙ ∙ ∙ , xN] ∈ RD×N0是要进行聚类的N个数据点的集合，其中D是数据的维度。我们用K表示聚类的数量，它是一个预先指定的整数，尽管K可以从给定的数据集中学习。聚类的目的是根据某种相似性标准将数据集X划分为K个簇。谱聚类（SC）一直是一种广泛使用的聚类技术[21]。为了服务于本文，我们重复通用的SC算法如下[20]：01. 构建一个 N × N 的矩阵 W ，其中包含这些 N个点之间的成对相似性（权重）。02. 形成归一化的图拉普拉斯矩阵0其中 D 是对角矩阵，d ii = � N j =1 w ij 。03. 解决以下约束优化问题，计算 U ∈ R N × d ，04. 对 U ∈ R N × d的每一行进行归一化，得到一个新的矩阵 � U 。05. 对 U 的行进行 k-means 聚类，将它们分成 K 组。0U 的行实际上被视为原始 D 维数据 X 的低维表示。UU T的元素表示原始数据的潜在表示（行）之间的相似性或亲和性，因此问题（1）中的目标函数是强制数据相似性与graph Laplacian L from data. The columns of U indeedcome from the first d eigenvectors of L corresponding to thesmallest d eigenvalues, or equivalently the eigenvectors ofminU∈RN×d⟨UUT , L⟩ + β∥UUT ∥0, s.t. UT U = I,(2)minU∈RN×d⟨UUT , L⟩ + β∥UUT ∥1, s.t. UT U = I.(3)min⟨P, L⟩ + β∥P∥1,f(U) = ⟨UUT , L⟩ + β∥UUT ∥1(5)S(d, N) = {U ∈ RN×d | UT U = I}.f(UQ) = f(U),min[U]∈G(d,N) f(U) = ⟨UUT , L⟩ + β∥UUT ∥1,(6)526002 对应于 d个最大特征值。Ng等人观察到，当一些关键特征值相等时，最佳的新表示 U是由子空间而不是特定特征向量决定的。Ng等人还分析了低维嵌入在聚类中更有效的原因。正如Ng等人[21]所指出的那样，在理想情况下，UU T可以被排列为块对角结构。块对角结构是受欢迎的，因为它提高了聚类性能。在最近的一项工作中，已经利用了在谱聚类中引入或强制稀疏性的思想[20]，提出了稀疏谱聚类（SSC）。SSC通过解决以下稀疏诱导问题来寻找更好的表示U：0其中 β > 0 权衡了SC的目标和 UU T的稀疏性。然而，最小化 ∥ ∙ ∥ 0导致一个NP难的组合优化问题。众所周知，ℓ 1 -范数是ℓ 0-范数在ℓ 1 -球内的凸包。在机器学习中，通常用ℓ 1-范数替代ℓ 0-范数，因此问题（2）可以放松为以下问题，以获得更好的数值目标：0理想情况下，与弱簇间连接对应的 UU T中的元素趋向于零，而与强簇内连接对应的元素将被保留。然而，放松问题（3）仍然是关于潜变量 U的约束非凸优化问题。[20]的作者进一步优化了新变量 P =UU T ，基于以下事实：集合 S 2 = � P ∈ S N × N | 0 � P �I，tr � P � = d � 是集合 S 1 = � UU T | U ∈ R N × d，U T U= I �的凸包。最后，SSC旨在解决以下放松的凸问题，定义如下：0s.t. 0 � P � I，tr � P � = d. (4)0现在问题（4）可以通过标准的ADMM过程解决，借助一种称为cappedsimplex投影问题的高效算法的帮助。有关更多详细信息，请参阅[20, 27]。在为 P 解决（4）后，通过使用与 d相对应的前 d 个特征向量来近似计算（3）的潜在表示 U的最终解。0通过其特征分解将 P 的最大 d个特征值进行重组。正如我们之前提到的，这个 U可能不是以下聚类过程的最佳解决方案。在下一节中，我们提出直接解决放松问题（3）。03. Grassmann流形优化03.1. 问题的改革0考虑问题（3）。将目标函数表示为0其中 L是给定的数据图的Laplacian。问题（3）中的约束条件定义了所谓的Stiefel流形，由所有正交列矩阵组成。0因此，问题（3）是Stiefel流形 S ( d, N ) 上的一个无约束流形优化问题。考虑到 d 阶群O ( d ) =  { Q  ∈  R d × d | Q T Q  =  I } ，其中 Q  ∈ O ( d ) ，我们可以在Stiefel流形S ( d, N ) 上定义一个等价关系 � ，即 U 1  �  U 2  意味着存在一个 Q  ∈ O ( d ) ，使得 U1  =  U 2 Q 。在这个等价关系下，Stiefel流形 S ( N, d )的商空间实际上是抽象Grassmann流形 G ( N, d ) 的具体表示，参见[2,12]。Grassmann流形上的一个点实际上是由等价类[ U ] =  { UQ  |  对于所有 Q  ∈ O ( d) }  ，其中 U  ∈  R N × d 实现的。0是一个正交列矩阵，称为Grassmann点[ U]的代表。很容易检查对于任何 Q ∈ O ( d ) ，我们有0这表明问题（3）的目标函数在等价类[ U]上具有相等的值。换句话说，如果 U是（3）的解，那么对于任何 Q ∈ O ( d ) ，UQ也是（3）的解。简单地在Stiefel流形 S ( d, N )上优化（3）可能会导致等价类上的函数值相等的问题。更好的策略是将问题重新定义为Grassmann流形上的问题，如下所示。0其中方程6是一个无约束的Grassmann流形优化问题。在过去的二十年中，已经开发出了许多解决流形优化问题的方法。代表性的工作[2]已经开发了一个在不同类型的矩阵流形上定义优化函数的框架。典型的算法有Riemannian梯度下降算法和Riemannian信任区域算法。52610这些方法在Matlab工具箱ManOpt 1中得到了实现。流形优化的成功算法取决于对所关注流形的丰富Riemann几何的了解。Edelman等人[12]探索了Stiefel流形和Grassmann流形的Riemann几何，并在这些流形上开发了优化算法。这些流形优化算法最重要的组成部分是由相关流形的Riemann度量引起的Riemann梯度。Riemann流形的丰富几何使得可以定义目标函数 f的Riemann梯度和Hessian，以及在流形上从点 U开始沿着指定切向方向移动的系统化过程（称为投影）。对于大多数嵌入在欧几里得空间中的流形，如Grassmann流形，Riemann梯度是欧几里得梯度在流形的相关切空间上的投影。在下一小节中，我们将重点讨论计算稀疏谱聚类目标函数（5）的欧几里得梯度。03.2. 计算梯度0新优化问题（6）的目标函数（5）在 UU T的元素为零的位置不可微。然而，在这种情况下，我们将采用使用次微分。为了推导其欧几里得导数的公式，我们引入几个符号。对于大小为 m  ×  n 的矩阵 A ，vec ( A )是一个 mn 维向量，通过逐一堆叠 A 的列得到，ivec ( vec( A )) =  A 是vec的逆操作。A �  B 是矩阵 A 和 B的Kronecker积。变换 T m,n 是一个大小为 mn  ×  mn的矩阵，使得vec ( A ) =  T m,n vec ( A T )。对于目标函数（5）中的第一项，我们注意到：0�UU T, L� = tr(UU T L) = tr(UTLU)。0因此0��UU T, L� = LU + LTU = 2LU0因为L通常是对称的。考虑目标函数的第二项。首先，根据链式法则，我们有：0vec � ∥UU T∥10∂U0�T = vec(sgn(UUT))T ∂UU T0∂U，0其中0∂UU T0∂U = (IN2 + TN×N,N×N)(U � IN)。01 http://www.manopt.org0将列向量D定义为0D = ∂UU T0∂U vec(sgn(UUT))0因此，目标函数f(U)的欧几里得导数为：�f(U) = 2LU +βivec(D)。（7）03.3. 稀疏谱聚类算法0在Grassmann点[ U]的代表U处，Riemann梯度可以简单地计算为0grad [U] f = (I - UUT)�f(U)。0通过这个计算，我们可以使用ManOpt工具箱解决Grassmann流形优化问题（6），得到解U。对于初始的N×k潜在表示矩阵U(0)，可以通过使用W的前k个特征向量对应于最大的k个特征值来近似，其中N×N矩阵W是N个数据点之间的成对相似性（权重）。我们在算法1中总结了算法。0算法1 Grassmann流形优化辅助谱聚类（GSC）算法输入：数据矩阵X = [x1, x2, ...,xN]，潜在维数d和权衡参数β。 输出：稀疏潜在表示U。1：构建相似性矩阵W，并计算初始潜在表示U(0)；2：计算归一化拉普拉斯矩阵L；03：使用初始U(0)，调用ManOpt工具箱中的Riemanniantrust-region（RTR）算法来优化目标，直到满足预定义的终止准则。0使用Riemanniantrust-region（RTR）算法给出的解U有两种方式。由于U的行被视为原始数据的潜在表示，当d相对较小时，我们可以将它们视为降维的结果。因此，问题（6）的优化可以被视为一种降维，而准则等价于在数据空间和潜在空间中匹配对象的相似性信息[21]。这与Twin Kernel Embedding[15]的思想有一定的联系，其中通过核函数指定了数据空间和潜在空间之间的核关系。我们在合成数据和真实世界数据上的实验表明，在降维和可视化方面表现出色。我们将其称为Grassmann流形优化辅助降维（GDR）。第二种方式是将U用于最终的数据聚类。例如，我们可以将U作为k-means的输入。在这种情况下，我们将其称为Grassmann流形优化辅助谱聚类（GSC）算法。-101-1-0.500.51(a)-101-0.500.511.5(b)-202-202(c)-0.500.500.20.40.6(d)-1-0.500.51-1-0.500.51(a)-101-0.500.51(b)-202-202(c)-0.500.500.20.40.6(a)-0.500.500.10.20.30.40.50.60.7(b)-0.500.500.20.40.6(c)52620本文中，我们构建了一个新的相似性矩阵W� =UUT，并将其作为输入用于NormalizedCut（NCut）方法将数据分成簇。我们将该算法称为Grassmann流形优化辅助谱聚类（GSC）算法。04. 实验结果0在本节中，我们首先评估了我们的GSC模型在合成数据集上进行聚类的性能。其次，我们将其与GDR模型结合起来进行降维和聚类。我们还对比了我们的算法与传统的Ncut算法以及[20]中提出的凸稀疏谱聚类（SSC）。由于SSC与NormalizedCut（NCut）的性能优于与K-means的性能。为了公平比较，我们改变了[20]中最终的SSC处理步骤。在我们的程序中，我们直接将矩阵P作为输入，而不是使用P的前k个特征向量对应于k个最大特征值来近似U，然后使用Ncut方法将数据分成簇。该算法使用Matlab R2015a编码，并在一台CPU3.20GHz和8G RAM的PC上进行。04.1. 合成数据上的实验0本实验中使用的合成数据包括（1）两个半月形数据；（2）三个高斯数据；（3）三个环形数据；（4）两个不相交的二次曲线。本实验中使用的数据在图1中显示，其聚类已着色。两个半月形数据：存在两个以半月形状分布的数据簇，稍微交叉重叠。该数据集经常用于测试新的聚类算法的性能。数据是从两个正弦曲线中随机生成的，噪声百分比设置为0.09。在这种情况下，每个簇包含100个样本。三个高斯数据：第二个玩具数据集是从三个高斯分量的混合中采样得到的。每个簇服从方差为0.05的高斯分布。每个簇有100个样本。三个环形数据：第三个合成数据集是在二维平面上随机生成的三个环形数据，其中数据分布在圆上，噪声百分比设置为0.15。每个簇分别有100、100和150个样本。两个不相交的二次曲线数据：最后一个数据集由分布在两个不相交的抛物线形状曲线上的两个簇的数据组成，没有重叠，受到均值为0、方差为0.05的高斯噪声的干扰。每个簇包含200个样本。在我们的算法中，我们使用经典的k最近邻（k-nn简称）图来构建基于数据点之间邻居关系的相似性。然后，我们计算高斯核作为相似性，它也可以用作算法1中的步骤1的输入。核的标准差取为数据点之间的成对欧氏距离的中位数。我们0图1.合成玩具数据集：两个半月形数据（a）；三个高斯数据（b）；三个环形数据（c）；两个不相交的二次曲线（d）。0图2.Ncut数据聚类结果的可视化，分别为两个半月形（a），三个高斯（b）和三个环形数据（c）。GSC和SSC对这三种情况都达到了100％的准确率。0图3. 两个不相交的二次曲线的聚类结果，使用Ncut（a），SSC（b）和GSC（c）0计算高斯核作为相似性，它也可以用作算法1的步骤1的输入。核的标准差取为数据点之间的成对欧氏距离的中位数。我们K-NN Graph50100150200250300350400(a)SSC50100150200250300350400(b)GSC50100150200250300350400(c)β=0.00001100100100100β=0.0000510010081.71100β=0.000110091.3176.86100β=0.00055395.749.4387.14β=0.00151.3495.341.7183.71β=0.005459338.0083.71β=0.0144.339334.5783.7152630图4.两个不相交的二次曲线数据集的相似性矩阵图：（a）k-nn，其中k= 8；（b）SSC中的P；（c）GSC中的UU T0在两个半月形、三个高斯数据集和两个不相交的二次曲线中，设置k = 6，而对于三个环形数据集，设置k =8。在这项工作中，我们假设聚类数K是已知的。经典Ncut算法在两个半月形、三个高斯和三个环形数据集上的聚类准确率分别为56.50％，60.10％和86.00％。图2显示了基于Ncut的前三个数据集的聚类结果的可视化比较。结果并不令人满意。0β 三个高斯 三个环形0表1.SSC和GSC对三个高斯和三个环形数据集在不同β下的聚类准确率（%）。0我们不直接将Ncuts应用于数据的相似性矩阵，而是将相似性矩阵作为算法1的第1步的结果输入。在通过算法1获得解U后，我们将U作为NCut算法的输入，即W�=UUT。在两个半月形、三个高斯和三个环形数据集上，当β =0.00001时，GSC和SSC都取得了最佳结果，准确率均为100％。我们比较了β对GSC和SSC性能的影响。随着β的增加，GSC的性能优于SSC，尤其是对于三个环形和三个高斯数据集。表1显示了两个数据集上参数β的聚类性能。两种情况都表明，与β相比，GSC的性能更加稳健。对于两个不相交的二次曲线数据集，Ncut方法的聚类准确率很差，为54.50％。当β =0.000001时，GSC方法的最佳结果为100％，而最佳0SSC的性能仅为83.50％的准确率。聚类准确性的可视化比较结果如图3所示。为了探索数据中的底层低维结构，我们还提供了两个不相交的曲线数据集的亲和矩阵的可视化比较。图4（a）绘制了通过k-nn（k =8）得到的亲和矩阵W；图4（b）显示了SSC中的P（方程（4））；图4（c）展示了GSC中的UUT（方程（6））。通过GSC获得的亲和矩阵有效地揭示了数据的聚类结构，从而有利于后续的聚类任务。从列出的结果可以得出三个观察结果：01.对于普通数据集，如两个月亮、三高斯和三环数据集，GSC和SSC都可以达到相同的最佳准确率。GSC和SSC的聚类结果优于Ncut算法。02.GSC对于GSC的聚类结果比SSC更加稳健，尤其是对于复杂的三高斯、三环数据和两个不相交的曲线数据集。03.对于两个不相交的曲线等数据，GSC优于SSC。原因可能是GSC更加重视数据的非线性流形结构。这激励我们在许多高维数据上进行GSC算法，并使用我们的GDR方法追求它们的潜在低维表示。04.2. 实验在真实世界基准数据集上0在本小节中，我们在一些公共数据库上进行了几个实验，以评估提出的GSC模型。我们使用扩展的YaleB数据集、ORL数据集和MNIST手写数字数据库来评估提出的聚类方法。我们使用准确率进行性能评估。04.2.1 聚类实验0对于聚类问题，所有实验都在以下三个公共可用数据集上进行：01.YaleB人脸数据库（http://vision.ucsd.edu/content/yale-face-database）。02. ORL人脸数据库（http://www.cam-orl.co.uk）。03.MNIST数据库中的一部分手写数字图像（http://yann.lecun.com/exdb/mnist）。K = 561.56(9.34)95.64(5.90)96.58(3.94)K = 856.77(8.84)88.95(4.76)91.65(4.64)K = 1048.39(7.61)82.86(4.86)85.24(4.34)K = 1246.94(4.82)80.17(4.40)82.64(4.20)K = 1545.51(4.06)76.91(1.57)77.82(1.63)K = 1845.33(3.80)75.06(1.59)76.84(1.49)βK = 5K = 10K = 15SSCGSCSSCGSCSSCGSCβ=0.0000195.5396.1482.2483.3076.8277.14β=0.0000595.3596.2581.9383.3976.6777.04β=0.000195.2596.3476.2581.9676.3776.59β=0.000580.3895.8969.2781.6167.4476.59β=0.00157.9885.9454.3769.8568.7573.70β=0.00536.9872.8532.7561.3552.4870.13β=0.0130.5962.5122.3755.0038.1469.8752640(a)0(b)0图5. 人脸数据集的示例：（a）扩展的Yale B和（b）ORL人脸。0图6. MNIST手写数字的示例0扩展的YaleB数据集由38个人类主体的人脸图像组成。图5（a）显示了一些样本人脸图像。对于每个主体，有N i =64个正面人脸图像，这些图像是在不同的光照条件下获取的。图像是在不同的照明和表情条件下拍摄的。为了减少所有算法的计算成本和内存需求，我们将图像降采样为32×32像素，并将每个1032D矢量化图像视为数据点。ORL人脸数据库由400张大小为112×92的图像组成，其中一些样本显示在图5（b）中。有40个个体，每个人有10张图像。这些图像是在不同的时间、光照和面部表情下拍摄的。人脸以正面视图的直立姿势呈现，稍微左右旋转。所有数据都以10304（像素）×400（人脸）的矩阵形式收集。为了避免大值，数据矩阵除以100。我们按照[13]中的设置，通过l1-graph构建亲和矩阵，并对这两个人脸数据集应用Ncut、SSC和GSC。构建了六个子集，其中包含所有随机选择的主体的图像，聚类数目K从5到18。我们将{0.00001，0.00005，0.0001，0.0005，0.001，0.05，0.01}设置为GSC（6）和SSC（3）的参数β的候选集，并进行网格搜索来调整参数β。对于每个数据集和每个算法，进行了详尽的测试以找到准最优的参数设置。最终的性能得分是通过对20次试验的得分进行平均计算得到的。0方法 Ncut SSC GSC0表2. YaleB数据集上的聚类结果的准确率（%）和标准差。0我们还评估了GSC模型相对于SSC在稀疏正则化参数β方面的稳定性。这次，我们在这两种方法中设置相同的β，并分别设置聚类数K为5、10和15。0表3. SSC和GSC在YaleB人脸数据集上对不同β的聚类准确率（%）。0实验重复20次，并总结了两个数据集上使用准最优参数设置的聚类准确率的均值和标准差，分别在表2和表4中。表3和表5展示了在两个人脸数据集上针对不同β的聚类性能，通过对上述重复20次实验的聚类准确率进行平均。这些结果表明，GSC方法在准确性和稳定性方面均优于SSC方法。图6中的手写数字图像子集选自MNIST数据库，该数据库包含60000个数字图像，每个数字有600个图像。所有图像都是灰度图像，大小均为28×28像素。我们使用了一个包含400个样本和5个聚类（每个聚类有80个样本）的子集。在这个测试中，我们比较了原始l1-graph、SSC和GSC算法得到的相似度矩阵。显然，我们的GSC算法捕捉到了聚类的结构信息。现在我们讨论算法的收敛性。收敛性和最优性：（6）中的新优化GSC是非线性的，我们使用Riemanniantrust-region（RTR）算法来求解。可能存在许多局部最小值。一般的收敛性分析已经在[1]中完成。对于我们的情况，收敛的条件得到满足，从数据相似度W的特殊初始化可能将迭代过程驱向一个好的解。K = 559.85(6.98)97.25(6.62)97.80(5.41)K = 855.75(6.31)91.25(5.89)93.50(5.41)K = 1055.25(5.91)80.95(10.67)82.77(6.32)K = 1251.35(6.98)79.55(11.32)82.50(10.82)K = 1550.47(5.07)78.85(7.06)79.67(4.79)K = 1850.10(4.76)77.95(7.41)78.96(5.21)βK = 5K = 10K = 15SSCGSCSSCGSCSSCGSCβ=0.0000194.6096.2079.9081.3077.2677.73β=0.0000594.6096.2079.7080.8077.0777.47β=0.000194.2596.0079.1080.9676.7777.69β=0.000595.6096.0080.6081.2177.1377.73β=0.00195.8096.6780.7080.8077.4578.00β=0.00590.0096.0075.5081.3070.2077.13β=0.0178.2587.3359.8077.1054.5373.87400020000-2000-4000-4000-200002000200010000-1000-20004000(a)10.50-0.5-1-1-0.500.50.40.20-0.2-0.4-0.61(b)0.20.10-0.1-0.2-0.2-0.100.10.150.10.050-0.05-0.1-0.150.2(c)400020000-2000-4000-6000-6000-4000-2000020002000-1500-1000-5000500100015004000(d)0.80.60.40.20-0.2SSC U-0.4-0.6-0.4-0.20-0.3-0.2-0.100.10.20.30.40.50.2(e)0.150.10.050-0.05-0.1-0.15-0.1-0.0500.050.10.150.30.20.10-0.1(f)52650L1 Graph0SSC0OGM0图7. 5类MNIST数字的相似度矩阵：(a) l1-graph；(b)SSC中的P；(c) GSC中的UU T。0方法 Ncut SSC GSC0表4. ORL数据集上的聚类结果的准确率（%）和标准差。0所有实验情况都显示出良好的收敛速度。0表5. SSC和GSC在ORL人脸数据集上不同β值下的聚类准确率(%)。04.2.2 降维实验0降维(DR)是一种通过低维嵌入来表示高维数据的方法，使得低维数据可以在预处理系统中有效使用，或者通过避免维数灾难来更好地理解数据。已经证明DR是一个重要的工具，并且在数据挖掘、数据可视化和机器学习的许多领域中被广泛应用。除了在聚类准确性方面的优势之外，我们的Grassmann流形优化的另一个优点是可以得到由矩阵U给出的嵌入空间，其中U的行被视为原始数据的潜在表示。在由U的行定义的低维空间中，我们希望能够揭示数据聚类。0图8. 原始数据集PCA降维的数据可视化(a)和(d);SSC的矩阵U(b)和(e)，以及GDR的矩阵U(c)和(f)：YaleB人脸数据集5类情况在第一行，8类情况在第二行。0为了测试我们算法的降维能力，我们在YaleB人脸数据集上测试了GDR。图8(a)和(d)分别展示了在第4.2节中使用主成分分析(PCA)线性降维方法后，5类和8类YaleB人脸数据集的三维散点图。同样，图8(b)和(e)展示了使用前3个特征值对应的前3个特征向量的SSC的解U的三维散点图，图8(c)和(f)展示了我们的GDR给出的解U的三维散点图。可以清楚地看到，GDR是对数据集进行有意义可视化的优选方法。05. 结论0本文提出了采用Grassmann流形优化策略直接优化[20]中引入的稀疏谱聚类目标的GSC模型。我们还提出了GDR模型，将原始数据的潜在表示可视化为降维结果。在几个真实数据集上进行了大量实验，证明了我们方法的有效性。0致谢0本研究项目得到澳大利亚研究委员会（ARC）通过DP140102270号资助，部分资助来自中国国家自然科学基金（61472155号）和华中科技大学创新基金（2015QN130号）。[1] P. A. Absil, R. Mahony, and R. Sepulchre. Riemannian ge-ometry of Grassmann manifolds with a view on algorithmiccomputation.Acta Applicadae Mathematicae, 80(2):199–220, 2004.[2] P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization al-gorithms on matrix manifolds. Princeton University Press,2008.[3] F. R. Bach and M. I. Jordan. Learning spectral clustering,with application to speech separation. Journal of MachineLearning Research, 7:1963–2001, 2006.[4] C. Bishop. Pattern Recognition and Machine Learning. In-formation Science and Statistics. Springer, 2006.[5] N. Bounmal and P.-A. Absil. Low-rank matrix completionvia preconditioned optimization on the Grassmann manifold.Optimization-online, pages 1–31, 2014.[6] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Dis-tributed optimization and statistical learning via the alternat-ing direction method of multipliers. Foundations and Trendsin Machine Learning, 3(1):1–122, 2010.[7] H. Chen, Y. Sun, J. Gao, and Y. Hu. Fast optimization al-gorithm on riemannian manifolds and its application in low-rank representation. CoRR, abs/1512.01927, 2015.[8] J. Chen and J. Yang.Robust subspace segmentation vialow-rank representation. IEEE Transactions on Cybernetics,44(8):1432–1445, 2014.[9] T. Connie, M. K. O. Goh, and A. B. J. Teoh. A grassmannianapproach to address view change problem in gait recognition.IEEE Transactions on Cybernetics, 2016.[10] N. Cristianini, J. Shawe-Taylor, and J. S. Kandola. Spectralkernel methods for clustering. In Proceedings of Advances inNeural Information Processing Systems, page 649655, 2001.[11] J. P. Cunningham and Z. Ghahramani. Unifying linear di-mensionality reduction. arXiv:1406.0873, 1, 2014.[12] A. Edelman, T. A. Arias, and S. T. Smith. The geometry ofalgorithms with orthogonality constraints.