4155随机稀疏子空间聚类陈颖1，李春光1，崇友21北京邮电大学信息工程学院加州大学伯克利分校摘要最先进的子空间聚类方法是基于自表达模型，它将每个数据点表示为其他数据点的线性组合。通过强制这种表示是稀疏的，稀疏子空间聚类保证产生子空间保持数据亲和性，其中两个点仅在它们来自相同子空间时才连接然而，另一方面，来自相同子空间的数据点可能没有良好连接，导致过度分割的问题。我们引入dropout来解决过度分割的问题，这是基于随机丢弃自表达模型中的数据点特别地，我们证明了dropout等价于在表示系数上增加一个平方π2然后，我们将优化问题重新表述为一组小规模子问题上的共识这导致了一个可扩展的和灵活的稀疏子空间聚类方法，称为随机稀疏子空间聚类，它可以有效地处理大规模数据集。在合成数据和真实世界数据集上的大量实验验证了我们的建议的效率和有效性。1. 介绍这在许多应用中是不可用的。此外，相关的优化问题是非凸的，因此良好的初始化对于找到最优解很重要[23，16]。由于k-子空间方法的局限性，现代子空间聚类采用谱聚类，其从适当的数据亲和图恢复数据的分割，该数据亲和图捕获两个点是否来自相同的子空间。大量早期的构建亲和图的方法都是基于拟合和比较局部子空间[54，63]。这样的方法需要子空间上的密集样本，并且不能处理子空间相交的情况。在过去的几年中，自表达模型[11，12]已经成为子空间聚类中计算亲和图的强大工具，并已推动了实质性的发展和应用。给定数据矩阵X=[x1，· · ·，xN]∈IRD×N，其列由子空间的联合，自表达模型指出每个数据点xj∈ IRD可以被表达为其他数据点的线性组合，即，xj=Xcj+ej，cjj=0，（1）其中cj∈IRN是系数向量，ej是误差项。虽然（1）中的线性方程可能有许多可行解，但至少存在一个子空间保持的cj，即cij0仅当点xi和xj在许多现实世界的应用中，高维数据可以很好地近似为低维子空间的并集，其中每个子空间对应于一个类或类别。根据它们所属的子空间分割一组数据点的问题，称为子空间聚类[46，48]，已经发现了许多重要的应用，例如运动分割[9，8]，图像聚类[28]，混合系统识别[45，3]，基因表达谱聚类[29]等。以前的工作。 子空间聚类的传统方法是k-子空间，其基于将一组基参数化到子空间并找到最小化数据点到其对应子空间的距离的分割[5，2]。k-子空间方法需要对底层子空间的维数进行精确估计都在同一个子空间[39，61，48]。给定子空间保持表示[c1，···，cN]，亲和图由亲和（权重）矩阵导出，其第i，j个条目是|cij|+的|cji|.稀疏子空间聚类。 许多方法已经提出了计算子空间保持表示-通过对系数cj[12，28，10，24，40，60，55，58]施加先验或正则化来进行计算。其中，稀疏子空间聚类（SSC）[12，60]是基于找到稀疏解决方案（1）已成为极端流行，由于他们的理论保证和实施的成功。在温和的条件下，SSC保证恢复子空间保持的解决方案，即使数据点被破坏与离群值，噪声或缺失值，当子空间相交或仿射4156[39、61、52、44、21、59]。虽然子空间保持恢复保证了来自不同子空间的两个点在亲和图中没有连接，但不能保证来自相同子空间的点形成单个连接分量。因此，出现了一个连接性问题，即谱聚类对具有不良好连接的数据点的子空间产生过分割特别是，早期的工作[31]表明，当子空间的维数大于3时，SSC中确实存在连通性问题。几个作品试图解决的连通性关于SSC。受系数矩阵上的低秩正则化导致稠密解的事实的启发，[53]中提出了一种混合的N1不幸的是，解决[53]中的优化问题需要在算法的每次迭代中进行奇异值分解，这对于大规模数据在计算上是不允许的。More recently, in [51] a post-processing step that mergespoten- tial over-segmented fragments of a subspace intothe same cluster is proposed. 虽然这种方法在概念上很简单，并且有理论上的保证，但它只能在理想化的设置下工作，其中亲和图是完美的子空间保持的。纸质捐款。我们利用dropout来解决与SSC相关的连接问题。Dropout是为深度学习开发的一种技术，作为一种隐式正则化，可以有效缓解过拟合[41，50，49，4，13，7]。本文中的dropout是指在计算（1）中的自表达表示时，随机均匀地删除X的列的操作这样的操作等价于在表示系数向量cj上添加一个λ2正则化项，这有效地诱导了稠密解。 通过删除字典中的列，我们解决了只涉及原始数据集的一部分（通常非常小）的优化问题。当处理无法加载到内存中的超大规模数据集时，这是一个特别有吸引力的属性该文件的贡献突出如下。1. 本文在自表达子空间聚类模型中引入了一种dropout技术，并证明了它与一个平方范数正则化子是不对称等价的。2. 我们提出了一个随机稀疏子空间聚类模型，是基于丢弃列的数据矩阵。该模型具有灵活的可扩展性和隐式的提高亲和图连通性的能力。3. 我们将随机稀疏子空间聚类模型转化为一个共识优化问题，并提出了一个有效的共识算法来解决这个问题。4. 我们在合成数据和真实世界的基准数据上进行了广泛的实验，并展示了我们的建议的最先进的性能。2. 相关工作子空间聚类中的自表达模型。存在-基于自表达模型的子空间聚类方法可以分为三类。a）为了导出子空间保持解，现有方法在cj上使用不同的正则化。这包括[11]中的N1范数，[25]中的核范数，[28]中的N2范数，[29]中的TraceLasso范数，[29]中的N1加核范数，[29]中的N1加N2范数，[29]中的N0范数。[55]和[19，20]中的加权范数b）处理在实际应用中出现的不同形式的噪声，现有的方法对Ej使用不同的正则化，例如，在[11]中使用的101和102范数，在[25]中使用的102 ，1范数，在[18]中的高斯混合，以及在[22]中提出的加权误差熵。c）为了在适当的特征空间中执行子空间聚类，自表达模型与基于学习线性投影[26，33，35]或卷积神经网络[14，64，62]的特征学习方法相结合。可扩展子空间聚类。近年来，针对子空间聚类的可扩展性提出了一些尝试.例如，在[36]中，首先对一小部分数据进行聚类，然后根据学习的聚类对其余数据进行分类;在[60，10]中，采用贪婪算法[34]来求解稀疏自表达模型;在[43]中，使用草图技术来加速SSC;在[56]中，提出了一种分治框架，用于将SSC扩展到大规模数据;在[37]中，提出了一种基于在线字典学习的方法来扩展低秩子空间聚类[47，25];在[1]中，SSC在分层聚类的多个数据子集上进行，然后通过多层图融合方法进行合并;在[57]中，贪婪样本提出了一种选择方法来扩展SSC以处理类不平衡数据。虽然这些方法在较大尺寸的数据集上执行子空间聚类，但是对于[1，36，37]中用于子空间聚类目的的字典的质量没有任何理论保证，也没有任何努力来解决[10，60，56，43，1]中SSC的连通性问题结果，由于使用子采样数据或错误的过分割，这些方法中的聚类精度被严重牺牲最后，几乎所有的子空间聚类方法都需要将整个数据加载到内存中。如果数据的大小太大，这些方法都不起作用。3. 自我表达模型我们正式引入dropout操作的自我表达模型，并表明它是等价的表示向量上添加一个dropout2正则化在下一节中，我们使用这种丢弃特性来开发一个可扩展的灵活的子空间聚类模型，用于解决与SSC相关的图连通性问题。4157i=1我2C2i=1222ij2考虑最小化自表达残差的问题，如下所示：minxj−Xcj2，s.t. cjj=0。（二）在本文中，我们的目标是开发一个可扩展的和灵活的子空间聚类方法的基础上制定的（6），通过其等价于（8），有一个隐式的正则化，诱导稠密的解决方案。出于实际中捷2受用于训练神经网络的dropout技术的启发[41，50，49，4，13，7]，我们在（2）中的自我表达模型中提出了一个dropout操作类似于dropping2为了达到这个目的，我们用样本均值来代替期望E[·]，并通过求解下面的优化问题来解决（6“hiddenmin 1∑Txj− ∑ （t）cijxiS.T. cjj=0， （9）随机均匀丢弃X列具体来说，我们引入0≤δ≤1作为脱落率CJ不I2t=1i且令{N}是Ni.i.d. Bernoulli random variables with其中ξ（吨）是伯努利随机变量概率分布由下式给出：{我可以独立于（3）中的分布绘制。ξi=11−δ概率为1-δ（三）4. 随机稀疏子空间聚类：0，概率为δ。然后，在（2）中以概率δ均匀随机地丢弃X的列是通过将Ni.i.d. Bernoulli随机变量{i}N到X中的相应列，即，∑仿真和一致性算法正如在引言中简要讨论的那样，稀疏子空间聚类的目的是找到一个具有最稀疏系数向量的自表达表示也就是说，它旨在解决以下优化问题minxj−CJicijxi我S.T. c jj= 0。（四）min<$xj−Xcj<$2，S.T. cjJ下面的定理给出了自我表达模型中dropout的渐近效果定理1设{N i}N为N i.i.d. Bernoulli随机变量，其分布如（3）中所定义。 我们有：∑Exj−icijxi2我其中，是对向量中的非零条目的数量进行计数的伪范数，并且s是调优参数。控制解的稀疏性的参数。在[60]中已经表明，在温和的条件下，用于求解（10）的称为正交匹配追踪（OMP）[34]的贪婪算法可证明产生子空间保持解。另一方面，它也是在[60]中建立的。=xj−∑cijxi2+我δ1 −δ∑2.我（五）由OMP产生的子空间保持解中的非零项的数量不能超过xj所在的子空间的维数这个上限限制了通过定理1，我们可以看到，∑OMP在产生密集亲和图方面的能力，导致过度分割的高风险。minExj−CJicijxi我S.T. cjj=0，（6）我们在前一节中引入了dropout技术，以通过以下方式解决（10）中的连通性问题：等价于最优化问题OMP 具体来说，在4.1节中，我们提出了一种灵活的子空间聚类方法，该方法将SSC与（9）相结合，∑ ∑最小值xc x2+δ2 2随后将其重写为共识优化prob-j−ijI2J我1 −δ 我2012年12月22日，cjj= 0。（七）莱姆然后，在第4.2节中，我们提出了一个有效的交替最小化算法来解决一致性问题。4.1. 随机稀疏子空间聚类特别地，如果X的列具有单位范数（例如，通过数据预处理步骤），则（7）简化为∑min<$xj−cijxi<$2+λ<$cj<$2s.t.cjj=0，（8）通 过 结 合 （ 9 ） 中 的 自 表 达 模 型 的 样 本 均 值 和（10）中的稀疏约束，我们提出了一个随机稀疏子空间聚类模型，如下所示：2 2J我1∑T∑CC4158其中λ=δ。 这正是《minxj−（t）cijxi1−δ基于最小二乘回归的子空间聚类方法CJ不t=1中文（简体）[28]，并已知一般产生稠密解。S.T.cj我4159（k）t=1（k+1）（k+1）（k+1）JJJJJB22jjjjj=1算法1：阻尼OMP输入：字典I，I，xj∈ IR D，cj，s，λ和λ。1：初始化k = 0，残差q（0）= xj，S（0）= x j。算法2用于解决问题的共识OMP（13）输入：X =[x1，. - 是的- 是的 ，xN] ∈ IR D×N，xj∈IR D，parame-s、δ、λ、λ、T.J第二章： 而k< s和qj2>3：通过（16）找到i_n，并更新S（k+1）←S（k）{i};{}T1：样本T子字典 int（t）;第二章： 而不收敛（吨）4：通过求解（17）来更新bj;3： 给定cj，求解{bj}的T个子问题双线性算法1;不t=1 按面值-5： 更新q<$xj−kb和k<$k+1;（t）T1∑T（吨）J J6：end while输出：b4： 给定{bj}t=1，通过cj←T更新cj5：end while输出：c。t=1bj;其中s控制解的稀疏性。1由于T子问题中使用的字典的随机性质和稀疏约束，我们参考（11）随机用I（t）表示子问题的保留列和删除列的索引集，索引为t：={i：k（t）>0}和J（t）：={i：k（t）=0}，分别为：稀疏子空间聚类。我，并让（吨）我与数据矩阵X相同，除了为了理解问题（11）的本质，我们引入T个辅助变量{b（t）}T并导出一个e-由J索引的列被设置为零向量。为（吨）jt=1等效制剂如下：清晰度，我们通过字典重写问题（14），但忽略上标t如下：1∑T∑22minxj−（t）b（t）ximinxj−bj<$2+λbj−cj<$2，c，{ b（t）}T T2bj（十五）JJt=1（一）t=1我（T）（吨）（十二）S.T. 当bj=0时，S.T. BJ = ···=bj=cj，bj0≤s，b（t）= 0，t = 1，···，T.这显然是一个关于T块的共识问题。一旦找到最优解c，我们就引入亲和力vi-为了有效地解决问题（15），我们开发了一个贪婪算法来从索引内的支持度更新bj第一组保存的柱子。2具体来说，我们将支撑集S（0）初始化为空集，J1q（0）=x，并找到支持集S（k+1）2016- 02 - 22 01：01：02（|cij|+的|cji|）并通过j j应用谱聚类的解决方案，标准化切割[38]在这个亲和矩阵上。备注。在问题（12）中，T个子问题可以被求解通过贪婪搜索过程，即，递增S（k），通过在每次迭代时添加一个索引i，每个子问题使用一个小字典，（1−δ）N 平均列数为100。 这很吸引人imax= arg maxi∈I\S（k）n（q（k），cj），（16）特别是当数据太大而不能装入存储器时。其中，n（q（k），c）=（x<$q（k））2+ 2λx<$q（k）c−λc2，ijjiJIjijijij4.2. 一致性正交匹配追踪为了有效地解决问题（12），而不是精确地解决问题（12），我们引入一组惩罚项并如下解决松弛问题：更新S（k+1）=S（k）<${i<$}来解决问题min<$xj−<$bj<$2+λ<$bj−cj<$2j（17）S.T. supp（bj）<$S（k+1）min1∑T∑xj−<$（t）b（t）xi<$2+λ<$b（t）−cj<$2一个封闭的解决方案，然后计算残差-c，{ b（t）}T2j2（十三）ualq（k+1）=x-k（k+1）。t=1ijjjS.T. b（t）其中λ> 0是惩罚参数。 我们通过交替地更新{b（t）}T和cj来解决问题（13）。}4160本文总结了求解Al-Taxm1中问题（15）的步骤，称之为阻尼正交匹配算法（DampedOMP）.2. 当{b（t）}T固定时：我们从问题中求解c（t）Tjj=1j1. 当cj固定时：我们求解{bj }j=1并行从每个T子问题如下min λ∑Tb（t）−cj∑（t）（t）2（t）2CJ TJ2minxj−b（t）Jξibijxi<$2+λ<$bj−cj<$2，我（十四）t=1它有一个封闭形式的解c=1∑Tb（t）。S.T.当b（t）= 0时，tt=1jj0jj2只从I中的更新bj的原因是为了放大1由于隐式的平方正则化，稀疏度可以大于子空间的维数在保持效率的同时支持共识解cj。 这相当于在（11）或（12）中采用扩大的稀疏性参数s′> s。41612不J22i=11009080706050401021031041050.350.30.250.20.150.10.050102103104105102101100十比一10-2102103104105数量的数据点数量的数据点数量的数据点图1.S3COMP-C、S3COMP、EnSC和SSCCOMP在合成数据上的性能比较算法3：S3COMP-C输入：X =[x1，. - 是的- 是的 ，xN] ∈ IR D×N，xj∈IR D，参数s，δ，λ，λ，τ和T.一曰： 运行算法2;1、A = 0，A = 1，B=1，A=1，|cij|+的|cji|）的情况下;3：通过归一化切割运行谱聚类[38];输出：细分矩阵。我们总结了用于解决算法2中的一致性问题（13）的交替最小化算法，称为一致性OMP。为了清楚起见，我们在算法3中对我们提出的子空间聚类方法的整个过程进行了分类，称为通过具有一致性的正交匹配追踪的随机稀疏子空间聚类（S3COMP-C），并且我们使用S3COMP来引用通过算法2仅一次外部迭代来解决一致性问题（13）请注意，每个支架的尺寸溶液b（t）最大为s，因此溶液的支撑尺寸为S3COMP可以包含更多的非零条目（最多sTN），亲和矩阵仍然是稀疏的，因此谱聚类中特征值分解的时间复杂度为O（nsN），略高于SS的O（nsN）COMP. 对于一个大规模的数据集，我们设置（1-δ）δ1，并行求解T个降维子问题。这意味着-使S3COMP-C和S3COMP具有更灵活的可扩展性。5. 实验为了评估我们所提出的方法的性能，我们进行了大量的实验合成数据和现实世界的基准数据集。方 法 和 步 骤 We select eight state-of-the-art sub- spaceclustering methods as baselines: SCC [8], LSR [28],LRSC [47], and several scalable subspace clustering meth-ods, including SSCOMP [60], EnSC [58], OLRSC [37],SR-SSC [1], and ESC [57]. 在实验中，我们使用作者提供的代码来计算自我表达J通过1的tioncj∑Tt=1 b（t）将达到sT，导致矩阵C，其中调整参数以给出最佳涉及改进的诱导亲和图的连通性收敛和停止准则与OMP [34]中的收敛分析类似，算法1最多收敛s步。对于算法2，我们通过检查cj在两个连续迭代中的相对变化是否小于阈值ε或达到最大迭代次数来停止算法2。虽然我们不能证明算法2的收敛性，但对合成数据和真实世界数据的实验表明了良好的收敛性。在实验中，我们观察到外部迭代的次数是小，即，在真实世界的数据集上，T0=35复杂性分析。在算法2中，它通过阻尼OMP并行求解T个尺寸缩减的子问题，每个子问题需要N（1-δ）个内积。因此，在本发明中，聚类精度 对于谱聚类，我们应用亲和矩阵A上的归一化切割[38]，其通过A=|C|+的|C|除了SCC，它有自己的谱聚类步骤。本节所有实验中报告的结果均为10次试验的平均值福尔-在[60]中，我们用聚类精度3（acc：a%）、子空间保持表示误差（sre：e%）、连通性4（conn：c）和运行时间5（t）来评估每个算法5.1. 合成数据实验Setup. 我们遵循[60]中使用的设置，在环境空间IR9中随机生成n = 5个维度d = 6的子空间。 每个子空间包含在IR9的单位球面上随机采样的Ni个数据点，其中Ni在30到3396之间变化。因此，数据点的总数N变化该阶段中每个子概率在一次外部迭代中，lem是O（DN2（1−δ）s）。S3COMP和S3COMP-C的亲和基质最多含有sTN非零条目;而SSCOM的亲和矩阵3它是通过在所有可能的排列下找到聚类索引和地面真实标签之间的最佳对齐来计算的。4设λ（i）是对应于第i个聚类的归一化图拉普拉斯算子的第二小特征值[30]。连接是COM-P最多包含sN个非零项。 特征值使用ARPACK分解稀疏矩阵需要由c：= mini{λ（i）}n计算 合成数据。 为了表现出进步-∑（i）n对于真实世界的数据，我们计算c：=1i=1λ2。O（nTN）操作，其中n是子空间的数量(i.e.、簇）。而S3COMP-C和5表1至表5中的S3COMP的运行时间是基于T个子任务之间的最大运行时间加上谱聚类的时间。SSCOMPEnSCS3COMPS3SSCOMPEnSCS3COMPS3COMP-CSSCOMPEnSCS3COMPS3COMP-C聚类准确度（a%）连通性（c）运行时间（t，秒）n41620.90.70.50.3950.9940.7930.5920.3910.40.350.30.250.20.150.1750.9700.7650.560550.3500.19010 20 30 40 50 60 70 80 90 100不0.110 20 30 40 50 60 70 80 90 100不0.050.14510 20 30 40 50 60 70 80 90 100不(a) 聚类准确度（a%）(b) 连通性（c）(c) 子空间保留率（1 −e%）图2.在Ni= 320的合成数据上作为T和δ的函数的S3COMP-C的性能。强度对应于值。从150到16980。为了公平比较，我们使用与[60]中相同的参数s=5。我们设置T=15，并选择{ 0}中的退出率δ。1，0。2、···、0。9}。我们进行实验的合成数据与不同的数据点，每个子空间和报告的准确性，连接性，和子空间保持错误。我们将每个度量作为N i的函数，并在图中以曲线的形式呈现。1.一、我们观察到S3 COMP-C和S3COMP在聚类精度和连通性方面都优于SSCOMP，特别是当数据点密度较低时。很明显，EnSC、S3COMP和S3COMP-C在所有情况下都改善了连通性。S3 COMP的计算时间与SS-COMP相当（甚至更低）. EnSC的聚类精度与S3 COMP相比具有很强的竞争力，但时间开销高于S3COMP-C。为了更好地理解参数δ和T的影响，我们用S3 COMP-C对Ni=320的合成数据在不同的δ∈ {0. 1，· · ·，0. 9）和T∈ {5，10，· · ·，100}。 每个指标是以δ和T的函数记录的，并显示为-图中灰度图像的强度。二、我们观察到，即使使用高丢失率（例如，δ=0。（85）当T大于10时。粗略地说，较高的丢弃率导致较高的连通性和更有效的算法。Thought we also observe that using a higher dropoutrate leads to slightly higher subspace-preserving errors6, itdoes not necessarily degenerate the clustering accuracy.这是因为改进的连通性不仅有助于避免相同子空间中的数据点的过分割，而且还使相同子空间中的连通数据点在谱嵌入中具有更紧凑的簇。5.2. 真实世界数据集上的实验在本小节中，我们在四个基准数据集上演示了所提出的方法的性能，包括扩展耶鲁B（EYaleB）[15]，哥伦比亚对象图像库（COIL100）[32]，MNIST [17]和德国交通标志识别基准（GTSRB）[42]。数据集描述。Extended Yale B包含了38个人在64种不同光照条件下的2432张正面面部图像，每张图像大小为192×168。在我们的实验中，我们使用所有38个个体的图像，并将每个图像调整为48×42像素，并将每个图像中的原始像素连接为2016维向量。COIL100包含100个不同对象的7，200个灰度图像。每个物体有72个图像，以5度的姿势间隔拍摄。 我们将每个图像的大小调整为32×32，并将每个图像中的灰色像素连接为1024维向量。MNIST包含70，000个手写体的灰度图像-十位数字0- 9。除了整个数据集（表示为M-NIST 70000），我们还准备了两个子集-MNIST 4000和MNIST 10000，它们是通过每个类别随机采样Ni=400和Ni=1000对于每个图像，我们使用散射卷积网络[6]然后使用PCA将维度减少到500GTSRB包含43类街道标志图像，总计超过50，000个样本。 我们像ESC [57]中一样对数据集进行预处理，这导致了14个类别中12，390个图像的不平衡数据集。每个图像由数据库提供的1568维HOG特征表示。特征向量被减去均值并通过PCA投影到维度500。Setup. 请注意，在执行子空间聚类之前，所有特征向量都被归一化为具有单位N2范数。 为了进行公平的比较，我们分别为MNIST设置s=10，为扩展耶鲁B设置s=5，如SSCOMP [60]所示，并为GTSRB和COIL 100设置s=37对于真实世界数据集上的实验，我们设置T=15，并选择{0. 100 20，···，0。90}。结果扩展耶鲁B的结果列于表1。我们可以看到，S3COMP-C和S3COMP分别比SS- COMP提高了大约10%和4%的聚类准确度，S3COMP-C产生了第二好的结果聚类精度连接性得到改善，[6]这并不有助于提高代数连通性[30]。因此，代数连通度关于δ的精确关系不是简单单调的。7在实践中，参数s被设置为等于（或略小于）数据的固有维数，这是可以估计的。4163方法acc（a%）MNIST 4000sre（e%）conn（c<$）t（秒）acc（a%）MNIST 10000sre（e%）conn（c<$）t（秒）LSR80.0278.530.607514.7981.7580.220.6389147.98LRSC85.6179.870.64194.7789.6081.360.664612.87SCC71.30--70.7572.20--218.16OLRSC65.3285.700.866047.467.6286.110.8738217.43ESC87.22--27.9890.76--59.41EnSC85.8520.400.111735.8985.9416.630.093889.21SSCCOMP91.1434.260.13713.6393.8032.080.121211.99SR-SSC91.70--39.2490.05--79.87S3 COMP94.3033.150.15294.7095.7330.110.17209.14S3 COMP-C94.2733.260.152712.8895.7433.150.171926.50表3.MNIST上的性能比较，其中子空间保持误差，并保持更好的连通性，由于采取了很好的折衷之间的101和102规范。请注意，最好的三种方法S3 COMP-C，S3 COMP和EnSC都产生非常低的子空间保留误差，并且它们共享（隐式或显式）N2范数。表1.EYaleB上的性能比较，其中ESC神经网络使用不同的方式来定义亲和力的自我表达系数。方法acc（a%）线圈100sre（e%）conn（c<$）t（秒）SCC55.24--479.13LRSC50.1096.430.707225.11LSR48.2294.950.524662.91SSCCOMP49.8814.030.006013.33ESC56.90--56.31SR-SSC58.85--204.38EnSC63.944.360.016319.03S3 COMP71.473.350.00817.68S3 COMP-C78.893.150.007720.10表2. COIL 100上的性能比较，其中保持相当或甚至更低的子空间保持误差和计算成本。虽然ESC产生最好的聚类精度，但时间成本要重得多。 L-SR、LRSC和OLRSC具有较好的连通性，但子空间保持误差较大，准确率在60%左右。虽然EnSC也具有良好的连通性和较低的子空间保持误差，但其精度和计算时间均低于S3COMP-C和S3COMP。在表2中，我们报告了COIL 100的结果。我们可以看出，S3COMP-C和S3COMP产生了领先的聚类精度，并保持了较低的子空间保持误差。 EnSC产生第三最好的聚类精度，表4.MNIST上的性能比较，其中†：与最小的11个特征值相关的结束11个特征向量用于谱聚类，详细信息在支持材料中提供。关于MNIST的实验提供于表3中，4. 同样，我们可以观察到，S3 COMP-C在MNIST 4000和MNIST 10000上仍然提高了聚类准确率约2.33%对MNIST 70000、SSCOMP由于连接性问题，产生比S3COMP-C、 S3虽然EnSC具有最低的子空间保持误差，但连接性和时间成本没有很好的权衡。请注意，LSR、LRSC、SCC和OLRSC由于64 G的内存限制而无法 获 得 结 果 ; 而 S3 COMP-C 和 S3 COMP 继 承 了SSCCOMP的计算效率。在表5中，我们显示了GTSRB的结果。虽然GT-SRB是一个不平衡的数据集，但令人惊讶的是，我们可以再次观察到所提出的S3 COMP和S3 COMP-C优于所列出的基线算法，并在所有四个度量中获得令人对于EnSC，虽然它产生最低的子空间保持误差，但低连通性导致较差的聚类结果。由于不平衡，方法acc（a%）扩展耶鲁大学Bsre（e%）conn（c<$）t（秒）SCC12.80--615.69OLRSC26.8495.980.628498.25LSR63.9987.570.50673.21LRSC63.1788.750.45267.20EnSC61.2023.140.055052.98SR-SSC62.11--79.46SSCCOMP77.5920.130.03812.54ESC开关87.58--28.01S3 COMP81.6120.180.07231.92方法acc（a%）MNIST 70000sre（e%）conn（c<$）t（秒）OLRSCM---SR-SSC87.22--585.31SSCCOMP†81.5928.570.0830280.58ESC90.87--596.56EnSC93.6715.300.0911932.89S3 COMP†96.3130.120.1569218.724164连通性（c）0.140.120.10.080.060.040.020123456789标签10111213 14表5. GTSRB上的性能比较，其中图4. Histograms of second minor eigenvalues of the normal- izedgraph Laplacian for each category of GTSRB.数据分布，很难找到一个很好的折衷之间的1001和1002规范。339618801041577320九十五点六900.585800.475700.35.3. 更多的评价收敛行为。为了评估所提出的S3 COMP-C的收敛性，我们在图中显示了在合成数据和真实世界数据集上的两次连续迭代中自表达矩阵C3 .第三章。我们观察17798553065605550450.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9（一）0.20.100.10.2 0.3 0.4 0.5 0.6 0.7 0.8（b）第（1）款自我表达矩阵在几次迭代后变得稳定。这证实了算法2的收敛性。图5.评价S3COMP-C中丢失率δ对每个子空间不同数据点数量的合成数据的影响。（一）作为δ和Ni的函数的聚类准确度（a%）。(b)作为函数δ的连通性c。0.50.40.30.20.10Ni=30Ni=55Ni=98Ni=177Ni=320Ni=577Ni=1041Ni=1880Ni=33962 4 6 810迭代(a) 合成数据0.250.20.150.10.0502 4 6 810迭代(b) 真实世界数据灵活的可扩展性，同时在计算效率和聚类精度之间建立理想的折衷。6. 结论我们在自我表达图3. C在连续的外部迭代中的相对变化连通性的改善。为了更好地观察所提出的方法的连通性改进，我们在图中显示对应于GTSRB的每个类别的归一化图拉普拉斯算子的第二小特征值的直方图4.第一章请注意，归一化图拉普拉斯算子关于每个类别的第二次小特征值测量代数连通性[30]。第二次特征值的显著改善直观地表明连通性的显著改善。脱落率δ的评价。为了评估不同丢失率δ的影响，我们在合成数据上记录了使用不同丢失率的S3COMP-C每个子空间具有不同数量的数据点的集合。实验结果如图所示。五、我们观察到，当数据点的密度增加时，当增加丢弃率时，聚类精度保持相对稳定。因此，当数据点的密度较高时，我们可以使用较大的丢弃率来丢弃更多的数据点。这证实了dropout策略实际上会导致子空间聚类模型。 通过使用伯努利运行-dom变量，我们证明了自表达模型中的dropout等价于增加一个平方的范数正则化。此外，我们提出了一个可扩展的和灵活的子空间聚类方法，这是制定了一个共识优化问题。我们解决了共识问题的交替最小化算法，其中包括一组阻尼正交匹配的追求和平均操作。这导致了一个原则性和灵活的方式来提高诱导亲和图的连通性，并实现了理想的计算效率和聚类精度之间的折衷。在人工数据和真实数据上的实验验证了该方法的有效性。确认本课题得到了国家自然科学基金项目61876022和北京大学机器感知MoE重点实验室开放项目基金的资助。SSCOMPEnSCS3COMPS3COMP-C线圈100EYaleBGTSRBMNIST4000MNIST10000 MNIST70000Ni=30Ni=55Ni=98Ni=177Ni=320Ni=577Ni=1041Ni=1880Ni=3396C的相对变化C的相对变化N我次小特征值方法acc（a%）GTSRBsre（e%）conn（c<$）t（秒）LSR73.9382.800.6185290.97LRSC87.2878.970.636715.85SCC70.82--237.01OLRSC82.4277.150.7606291.38SR-SSC78.42--223.34SSCCOMP82.525.420.021315.43EnSC86.050.810.009533.46ESC90.16--32.13S3 COMP95.252.400.05763.134165引用[1] Maryam Abdolali ， Nicolas Gillis ， and MohammadRahmati.使用随机聚类和多层图的可扩展和鲁棒的稀疏子空间聚类。信号处理，163：166-180，2019。二、五[2] P. Agarwal和N.穆斯塔法k-means投影聚类在ACM数据库系统原理研讨会，2004年。1[3] 洛朗·巴科和雷内·维达尔。MIMO SARX模型的代数辨识。 在混合动力系统国际研讨会上：计算和控制，第43-57页。斯宾格-Verlag，2008年。1[4] P. Baldi和P.萨多夫斯基了解dropout在神经信息处理系统，2013年。二、三[5] P. S. Bradley和O. L.曼格萨里安 k平面聚类Journal of Global Optimization，16（1）：23-32，2000.1[6] 琼·布鲁纳和圣·埃菲·马拉特。变分散射卷积网络。IEEETransactionsonPatternAnalysisandMachineIntelligence，35（8）：1872-1886，2013。6[7] Jacopo Cavazza，Benjamin D Haeffele，Connor Lane，PietroMorerio，VittorioMuriino，andReneVidal.Dropout作为矩阵分解的低秩正则化子在人工智能和统计国际会议上，第84卷，第435-444页二、三[8] G. Chen和G.勒曼谱曲率聚类（SC- C）. InternationalJournal of Computer Vision，81（3）：317- 330，2009.一、五[9] Joao Paulo Costeira和Takeo Kanade。独立运动物体的多体分解方法。国际计算机视觉杂志，29（3）：159-179，1998. 1[10] 伊娃湖Dyer，Aswin C. Sankaranarayanan和Richard G.巴拉纽克子空间聚类的贪婪特征选择。Journal of MachineLearning Research，14（1）：2487-251
我的内容管理
展开
