鲁棒子空间聚类框架：基于图聚类和几何感知的方法

9875子空间结构感知谱聚类的鲁棒子空间聚类日本NTT公司通信科学实验室，山口正孝、入江高仁、川西隆仁、Kashino Kunio{yamaguchi.masataka.up，go.irie. juo，takahito.kawanishi.fx，kunio.kashino.me}@hco.ntt.co.jp摘要子空间聚类是从多个子空间的并集中提取数据的分区问题。近年来最流行的子空间聚类框架是基于图聚类的方法，该方法分两步进行子空间聚类：图的构造和图的聚类。虽然这两个步骤对于精确聚类同样重要，但绝大多数工作都集中在改进图构造步骤而不是图聚类步骤上。在本文中，我们提出了一个新的图聚类框架的鲁棒子空间聚类。通过将几何感知项与谱聚类目标相结合，我们鼓励我们的框架对给定亲和矩阵中的噪声和离群值具有鲁棒性我们还开发了一个有效的期望最大化为基础的优化算法。通过在四个真实数据集上的大量实验，我们证明了所提出的方法优于现有方法。1. 介绍在许多实际场景中，-10的高维数据存在于低维线性子空间的并集中。将这样的数据分区，使得每个聚类由属于一个子空间的所有数据组成的问题称为子空间聚类。子空间聚类在计算机视觉[44，28]、数据挖掘[2，35]、网络分析[12，8]、系统识别等领域有着重要而广泛的应用，因此备受关注[46，3]和生物学[21，29]。在过去的几十年里，已经提出了许多子空间聚类方法，包括代数方法[5，9，14，20，45，30，19]，迭代方法[6，41，1，52]，统计方法[38，37，50，36]，和图形聚类-方法[49，7，10，11，25，47，27，26，43，15，22]。自从著名的基于自我表征的方法[10，11]被提出以来，最近的许多努力都集中在基于图聚类的方法上，因为它们在实际环境中的表现优于其他方法大多数基于图聚类的方法分两步执行第一步，图构造，是计算一个亲和矩阵，其中属于同一子空间的一对数据点具有比不同子空间中的数据点更高的亲和度。第二步，图聚类，是通过应用图聚类方法（例如，谱聚类）到亲和矩阵。虽然图构造和图聚类对于实现精确聚类都很重要，但大多数先前的工作都集中在改进图构造上。事实上，如果可以获得满足某些条件（例如，如果第i个和第j 个数 据点 属 于 相同 的 子 空间 ， 则 Mij>0 ， 否则Mij=0），因此寻求用于计算亲和矩阵的更好方法对于正确地聚类数据是重要的。然而，在实际设置中，数据包含噪声和异常值，因此没有方法不总是提供满足这些条件的亲和度。为了准确地聚类数据，改进图聚类步骤同样重要。在过去的十年中，谱聚类[32]已经成为图聚类步骤的事实上的标准方法。尽管它在基于图聚类的子空间聚类方法中的有效性已被经验验证，但其性能随着亲和矩阵中噪声强度的增加而迅速恶化缓解这个问题的一种方法是不仅使用亲和矩阵，而且使用数据在然而，据我们所知，没有一种图聚类方法在子空间聚类时考虑了数据为了准确地进行子空间聚类，我们提出了一种几何感知的图聚类方法，基于图聚类的子空间聚类。更具体地说，我们提出了一种新的图聚类目标，包括谱聚类目标和一个新的几何感知术语，鼓励每个集群中的数据位于相同的低维子空间。我们注意到，所提出的目标的最大化可以被解释为最大后验（MAP）估计问题的一个变体，9876∈U U ∪ U ∪ ∪ UFC{|}G|| ||Ci=1GLIJLIJ̸高斯混合模型（GMM），因此，我们采用期望最大化（EM）算法求解的目标。通过在四个真实数据集上的大量实验，我们证明了所提出的方法优于现有的方法.此外，我们还证明了我们的方法对于统一图构造和聚类步骤的框架也是有效的[24]。本文的贡献如下：图形构造：各种方法[49，7，10，11，25、47、27、26、43、15、22、17]已提出计算亲和矩阵。例如，其中最具代表性的基于自我表征的方法首先构建自我表征矩阵Z，其通过用其他数据点的线性组合表示每个数据点来计算，然后使用Z计算亲和矩阵M（例如，M ij=|Z*|+的|ZT|）. 为了-本文提出了一种基于图聚类的子空间聚类方法，该方法不仅基于给定的亲和矩阵，而且基于数据在环境空间中的几何结构对数据进行聚类我们提供了四个真实世界的数据集上的实验结果，这表明我们的方法的有效性。2. 初步2.1. 问题公式化子空间聚类是对N个D维数据点X=[x1，...，xN]TRN×D，它们存在于K个低维线性子空间的并中（或附近） =12...K，使得每个聚类由属于一个子空间的所有数据组成。具体地，问题是找到分配矩阵G =[g1，...，gK]∈ {0，1}N×K，满足G1K=1N，且如果Gij = 1，则xi ∈Uj.2.2. K子空间K-子空间[41，1]通过更新分配矩阵G和正交子的集合来最小化以下目标：把自表示矩阵Z代入，大多数方法先解决以下问题：min h（E）+ηr（Z），s.t. X=XZ + E，（2）Z∈C其中h（E）是重构误差E的损失函数（例如，h（E）=||E||2），r（Z）是自表示矩阵Z的正则化子（例如，r（Z）=E1），并且是Z的约束集（例如， =Z ZRN×N，Z ii=0）。已经证明，通过某些方法计算的亲和矩阵，稀疏子空间聚类（SSC）[10，11]，满足自表达特性（即， 如果第i个和第j个数据点属于相同的子空间，则Mij>0，否则在某些条件下M ij= 0）。 在这种情况下，我们可以通过简单地应用谱聚类，或更简单的方法，如深度优先搜索，得到正确的聚类结果。然而，在实际环境中，这些条件通常不成立，由于噪声和离群值，和聚类性能高度依赖于后续图聚类方法的鲁棒性。图聚类：在图构造步骤之后，通过将图聚类方法应用于计算的亲和矩阵来对数据进行聚类。典型图聚类方法通过找到最大化某些目标的分配矩阵来聚类数据，如下所示：mal基{Ui}K或者：（3）在G∈ G的条件下，max∈（G，Mmin∑K∑NG ij||x i− U TU ky i||第二章（一）N×K{y}N、{U}K其中G ={G|G ∈ {0，1}，G1K= 1N}。我我此外，通过替换等式中的平方距离项，(1)利用概率主成分分析（PPCA）在子空间聚类中，谱聚类用于图聚类。谱聚类使用以下目标：可 以 自 然 地 扩 展 到 它 的 概 率 版 本 ， 称 为 PPCA（MPPCA）的混合物[39]。虽然K-子空间和MPPCA都是实用的，但它们都有一些缺点。（G，M）=∑Kl=1TMg1、（4）gTDgl例如，它们倾向于收敛到局部最小值[42]。2.3. 基于图聚类的方法基于图聚类的子空间聚类方法首先计算亲和矩阵，其中属于相同子空间的一对数据点具有比不同子空间中的数据点更高的亲和度，然后将图聚类方法应用于该亲和矩阵。其中D是一个阶矩阵，如果i = j，则满足（D）ij=0;否则;（D）ii=jM ij. 由于计算最优分配矩阵G是NP难的，因此它是近似的。通过连续松弛来解决问题。更多详情请参见[51]。使用典型的图聚类方法进行子空间聚类的一个缺点是，它们的性能随着亲和矩阵中噪声强度的增加而迅速下降，因为它们仅基于··9877−GKS{|∈ R<$ }我KT2K∈ R ∈ R给定亲和矩阵。 缓解这个问题的一个方法是不仅使用给定的亲和矩阵，而且使用数据的几何结构进行图聚类。虽然Nieet al. [34]提出了一种图聚类方法，认为数据以及亲和矩阵，他们的方法是不特殊的，或者，受K-子空间的概率版本的启发MPPCA [39]，我们考虑替换方程的平方范数。(7)其中零均值高斯分布的似然性如下：用于子空间聚类。一些先前的工作[24，48]提出了子空间聚类框架，将图构造和图聚类统一到单个优化问题中。然而，他们的方法在内部使用∑Nr（G，X）= max2001年，K∈我∑K日志KGikN（xi; 0，nk+σI），（八）谱聚类;因此他们的方法对于给定亲和矩阵中的噪声仍然是脆弱的。3. 子空间结构感知的谱聚类为了提高谱聚类在子空间聚类问题中的鲁棒性，我们考虑利用数据在周围空间中的几何结构进行图聚类。更具体地说，我们建议使用以下目标，它由谱聚类目标r（G，M）和一个新的几何感知项r（G，X）组成，该项鼓励每个聚类中的数据位于相同的低-其中σI是避免协方差矩阵退化的项（本文中我们设置σ = 1e6）。使用Eq.(8)对于r（G，X），不再需要设置di的个数不像Eq.（七）、另外，更有趣的是，可以看出，Eq. (8)作为秩函数的平滑替代。3.1. 高斯对数似然作为秩的替代在下面，我们证明了Eq。（8）作为秩函数的光滑近似。首先，Eq. (8)可以表示如下：维度子空间：max（1−η）<$（G，M）+ηr（G，X）服从G∈ G，（五）∑Nr（G，X）= max2001年，K∈S我∑K日志KGikN（xi; 0，k），（9）其中η是超参数。最重要的关键是如何定义方程中的几何感知项r（G，X）（五）、一个简单的想法是使用每个聚类的数据矩阵的秩的和，如下所示∑K哪里=ΣΣD×D和σI。 让我们来看看 1，... K是等式的最大化者。(9)，可以解析求解如下：k=UkDiag（max（dk，σ1D））U T，（10）r（G，X）=−Krank（Diag（gk）X）（六）哪里∑1伊·吉克∑iGikxixT=UkDiag（dk）UT(see超级∑K∑D=−K D|0 |0补充材料的推导）。 此外，由用等式代替。(10)进入Eq. (9)，r（G，X）可以表示如下：其中λkd是Diag（gk）X的第k个奇异值。使用Eq.（6）对于几何感知项，r（G，X）∑K∑Dρ2λ ρ2λ2它可以直接鼓励减少intrin-=−的数量klog max（1，kd）+kmin（1，kd）+const.ρ数据 然而，由于其不连续性，求解Eq。 (5)是σK D∑K∑Dρk2σ2使用Eq. (6)对于r（G，X）. 此外，Eq.(6) 对每个聚类数据中的噪声非常敏感另一个想法是使用K-子空间的目标，r（G，X）如下：=−fρk，σ（λ kd）+常数K D（十一）其中ρk=mkσ，mk是属于r（G，X）=min∑N ∑K G ||x -U U y||、第k个簇和f（λ）=2ρlog max（1，λ）+2ρmin（1，λ）-ijiKKI2ρ，σσρ2σ ρ2{yi}N，{Ui}KI II K（七）（见补充材料的推导）。 从当量(11)，我们可以看到r（G，X）可以表示为每个奇异值的函数的其中y idi和U idi×D。然而，当使用当量(7)必须设置维数d，这通常是事先未知的。2压缩，fp，σ（λ）也类似于聚集有损压缩（ALC）的对象值得注意的是，ALC的目标是从数据压缩的角度导出的，而Eq.（十一）29878K2−−| |G2|222σH{|∈ R≤≤1086图2.两种混合模型的比较（一）定向4对应于零均值高斯混合的图形模型真模型（b）对应于该模型的有向∑图模型K2概率模型p（xi）=G ikN（xi; 0，k）.00 2 4 6 8 10 12λ图1.比较的|0，|0,|1、|1,且fρ，σ（λ）=ρlog max（1，λ）+ρmin（1，λ）（在此图中，我们设置其中= G GN×K，0G ij1，G1K=1N3。由于标准的谱聚类算法不能可以用来解决Eq。(12)由于引入了几何敏感项r（G，X），我们提出了一种新的算法.首先，我们重写Eq。(12)如下所示σ√ρ ρρ=σ=3）。 从这个图中，我们可以看到，Eq。（十一）类似于|λ|0，但也是平滑的，并且抑制小的输入值。max（1 η）<$（G，M）+ηr（G，X）G∈H= max（1 η）（G，M）+G∈H图 3、比较了（1）L0范数|0，其对应于秩函数rank（λ），（2）|0, whichcorresponds to the rank function rank(λ),(2)∑N最大η2001年，K∈S我∑K日志KGikN（xi; 0，k）核范数λ1，它可以被认为是凸环，秩函数的导数;（3）导函数=max∑N（1−η）<$（G，M）+η∑K日志GikN（xi; 0，k），f（λ）=ρ2log max（1，λ）+ρ2min（1，λ2）。从图3、G∈Hρ，σσρ2σ ρ22001年，K∈Si k我们可以观察到，秩函数非常敏感，噪声在λ=0，而核范数高估了一个大的输入值相比，秩函数。另一方面，我们可以观察到函数fρ，σ（λ）类似于秩函数，但它可以抑制小输入值，也可以避免对大输入值的高估。此外，由于函数fρ，σ（λ）是光滑的，因此它比秩函数更容易优化。由于上述原因，我们使用Eq。(9)对于几何感知项r（G，X）。4. 优化与原始谱聚类问题一样，很难直接求解方程。（五）、因此，遵循标准谱聚类算法，我们将分配矩阵Z从离散域放宽更具体地说，我们放松了Eq。(5)如下所示max（1−η）<$（G，M）+ηr（G，X）服从G∈H，（十二）（十三）请注意，等式中的第二项为：(13)可以被解释为GMM的变体的对数似然，其中混合系数向量是针对每个样本独立定义的（即， 第i个样本的系数向量gi=[Gi1，...， GiK]T）。 为了澄清GMM和混合模型之间的差异，我们在图中显示了这些有向图模型的比较。二、此外，第一项可以被解释为混合系数矩阵的正则化子，即，G. 从这个观察，解决Eq。公式（13）可以被解释为解决G（和G1，...，在这个混合模型上。 为了解决这个MAP估计问题，我们提出了一种新的EM为基础的算法。4.1. EM算法在介绍该算法之前，我们首先回顾了EM算法。 给出了一个混合模型p（x|θ）=zp（x，z θ），其中x是一个数据点，z是一个硬赋值-我们有：是从K-子空间和它的概率解释，这是更直观的子空间聚类比数据压缩。此外，他们的算法是基于贪婪算法，而我们的算法是基于连续优化问题，这往往会导致更好的解决方案比贪婪算法。3注意，我们限制每个样本的分配向量[G·1，. . . ，G·K]在（K −1）-单形中的一个推广。这对应于计算样本的软分配向量的问题，这在某些情况下也是有用的半监督学习），虽然我们的主要重点是获得离散的解决方案。（一）（b）第（1）款格兹伊Ng^izi塞吉 N∑iK∑iK2|0 |0|1 |1ρ2λρ2λ2σlogmax（1，ρ）+2σmin（1，ρ2）9879我K∈ H∞⊘q（z）−KKKKK我KGlogp（x|θ）=log∑p（x，z|θ）z遵循用于更新高斯混合模型的参数的标准EM算法，我们更新协方差矩阵然后更新混合系数G，并进行到E步骤。当G固定时，= log∑q（z）p（x，z|θ）q（ z）（十四）2001年，ΣK可按以下方式获得（见补充资料，z的推导）：≥∑q（z）logp（x，z|θ）=L（q，θ），Σ1=UDiag（max（d，σ1））UT，（17）z1∑NT其中L（q，θ）和q（Z）被称为证据下限哪里∑Nq（Z =1）iq（Zik= 1）xi xi=边界（ELBO）和变分分布。EM算法解决了p（x）的最大似然（或MAP）估计问题|θ）通过最大化ELBOUkDia g（dk）U T.当2011年，...，当K=k时，我们通过求解以下方程来获得最优参数G：问题：(plus参数θ在其先验p（θ）上的对数似然，也就是说，logp（θ）），通过交替迭代（E）期望步骤和（M）最大化步骤，分别更新q（z）和θ。MaxG∈H1−ηη∑N（G，M）+我∑Kq（ Zik= 1）log GikK活泼地在E步中，给定参数θ∈，最优变分分布q（z）为p（z|X，θ）。在M步中= maxG∈RN×D1−η（G，M）+ηgiv变分分布q∈（z），最优参数-∑N ∑K∑etersθ通过求解max∑θzq∈（z）logp（x，z|（θθ）q（Zik= 1）logGik-H（G）（或maxθ<$ zq<$（z）logp（x，z|如果参数ikp（θ）的先验值）。更多详情，请参见[4]。4.2. 该算法接下来，我们介绍我们的算法求解方程。（13）。整体算法在算法1中示出。由于我们遵循标准EM算法，交替迭代-（十八）其中iH（G）是定义为iH（G）= 0的指示函数，如果G;否则，iH（G）=. 为了解决这个问题，我们采用了近似梯度下降（PGD）方法，它迭代地更新G如下：在E步骤和M步骤中，我们将在下面解释这两个步骤。[E-步骤]更新q（Z）：G iv en参数ΣKGnew= proxγ，ιH（G+γ（1−η））（G，M）+Qη GZG）），（十九）和G，则最优变分分布q（Z）可如下获得：其中QZ是矩阵，使得（QZ）ij=q（Zij=1），逐元素除法运算符，q（ Z=1）=GijN（xi;0，j）prox（Gt）=argmin1||G−G||2+i（G）. （二十）ij∑KG（十五）N（x; 0，n）γ，ιHα2γFH[M-step]正在更新[1，...，在变量分布q（Z）中，我们想要解决以下问题：∑当量（20）对应于投影每个样本的分配向量[ G ·1，. . .，G·K]到其在（K1）-单形中的最近点。当量(20)可以通过一些现有的算法有效地计算，例如，[33]第33段。MaxG∈H2001年，K∈Slogp（G）+q（Z）logp（X，Z）|G，101，...，（克 罗 地 亚）Z初始化：与标准EM算法类似，我们的算法往往会导致一个糟糕的局部极小值，= maxG∈H2001年，K∈S1−η（G，M）+η初始化。幸运的是，我们根据经验发现，我们的算法倾向于通过初始化q（Z）来找到更好的局部最小值，其中初始化q（Z）具有由stan获得的分配矩阵∑∑Nq（ Z）Z i∑K日志KZik GikN（xi;0，k）Dikikˆ9880标准谱聚类算法（即， q（Zij= 1）= G ij）。从这个观察，我们通过谱clus初始化q（Z）tering。= maxG∈H2001年，K∈S1−η（G，M）+η4.3. 离散化∑N ∑KI kq（Zik= 1）（logGik+ logN（xi;0，k））（十六）然后，我们离散化的结果得到通过放松问题方程（十二）、在解释我们的离散化方法之前，我们引入以下命题（见补充材料的证明）：98814：←UDiag（max（d，σ））Ukk D1−ηηik∈ H∈ HηIJ×算法1子空间结构感知谱聚类输入：数据矩阵X=[x1，...，x N]T和初始变分分布q（Z）。1：重复2：【M步】3：更新参数1，...，如下所示：1TK5：通过求解以下方程来更新参数G0.750.700.650.60 0.1 1.0 10.0 1001 −λ λ0.700.650.60CASS与我们的SSC与我们的S与MSC与MSCCASSSCR with MSCwith MSCLRLSRR与我们的与我们的LRLSR0.1 1.0 10.0 1001 −λ λPGD的问题6：maxG∈RN×D<$（G，M）+∑N∑K q（ Zik=图3. EYaleB数据集上的实验结果。自NMIηi k1) logGik−ιH（G）用我们的方法计算，设置1-η=1000。0是多7： [E步]8：更新变分分布q（Z）如下：GikN（xi;0，k）小于其它的，所以在该图中未示出Best viewed彩色的。9：q（Zik= 1）=∑KGN（x;0，n）jij j10：直到收敛十一： 如下所示离散化G12：G=k=argmaxGik′>k′ ∈ {1，.，K}产出：G*反对意见1. 假设η=1，且η1，...， K是固定的。如果G是方程的最优解之一。（13），Gt，定义如下，也是它的最优解（之一）：近似地解决了Eq.的最大化问题。（四）、SEC与我们的方法一样，考虑了周围空间中的几何信息以及Eq. (4)但它的目标不是专门针对子空间聚类的。对于图像数据集，我们发现图聚类方法使用一些亲和度计算方法会导致机会水平的结果。为了避免这种现象，遵循Huet al.[15]，我们将PCA应用于数据，并使用前20个组件进行实验。选择SSC、LRR、LSR和CASS的超参数，以便使用MSC时达到最佳精度。MSC没有超参数，而†=，（二十一）SEC有两个超参数，在他们的论文中表示为γ和µ。在我们的实验中，遵循Nie等人的实验， 我们设γ =1。至于μ，如果参数为真，则·>为1，否则为0。这一命题表明，质量的解决方案是不显着恶化，通过将其转换为一个新的离散的解决方案，方程。(21)当η足够接近1时。基于这一观察，我们将连续的解决方案，以最终的分配方程。（21）。5. 实验为了验证我们的方法的有效性，我们在四个真实世界的应用程序上进行了实验：人脸聚类、目标图像聚类、手写数字聚类和运动聚类。 为了显示我们的方法的多功能性，我们采用了四种方法来计算自表示矩阵：稀疏子空间聚类（SSC）、低秩表示（LRR）、最 小二 乘 回归 （ LSR ） 和相 关 自适 应子 空 间分 割（CASS）。我们还采用了El- hamifar和Vidal [11]和Ji等人使用的化学方法。[18]用于将自我表示矩阵转换为亲和矩阵。为了评估每种方法的性能，我们使用两个指标：聚类精度和归一化互信息（NMI）。我们比较了我们的方法与多类谱聚类（MSC）和谱嵌入聚类（SEC）。MSc我们研究了设置μ=0，0的情况。010 1，1，和显示其中最好的分数为每一个组合数据集、方法和指标4. 注意，该实验方案导致SEC对每个设置进行过拟合 对于我们的方法，我们设置1-η=100。0，除非另有说明。5.1. 人脸图像聚类设 置 ： 我 们 首 先 在 扩 展 的 耶 鲁 人 脸 数 据 库 B（EYaleB）上进行了一项实验[23]。EYaleB是一个人脸图像数据集，由38个被试在各种光照条件下的2,432张人脸图像组成。每个主题有64个图像。我们使用的图像大小为48 42，由Elhamifar和Vidal提供[11]。我们通过随机选择10名受试者生成10个子集，并使用它们来评估每种方法结果：表1显示了EYaleB上的聚类结果。可以看出，在所有情况下，我们的方法优于其他两种方法。这表明了我们方法的有效性。参数灵敏度：我们还通过改变参数η来测试我们的方法的性能。结果4由于设置µ= 0的情况对应于MSC，因此其得分永远不会小于MSC。LRR与我们的LSR与我们的CASS与我们的SSC与我们的R with MSCwith MSCS与MSC与MSCLRLSRCASSSC精度NMIG9882η×η−η×SSCLRRLSRCass方法准确度NMI精度NMI准确度NMI准确度NMIMSc0.625 0.5720.6320.575 0.6460.5930.735 0.658Seb0.631 0.5830.6450.598 0.6460.5950.735 0.658我们0.643 0.6000.6620.621 0.6690.6160.743 0.667表1.EYaleB数据集上的实验结果SSCLRRLSRCass方法准确度NMI精度NMI准确度NMI准确度NMIMSc0.781 0.8730.7630.838 0.7920.8820.904 0.958Seb0.781 0.8730.7630.862 0.7920.8820.904 0.958我们0.788 0.8850.7810.861 0.7970.8910.904 0.958表2.COIL100数据库上的实验结果如图3所示 在所有情况下，指标5.3 的峰值。 手书写数字聚类当1-n=100。0，结果变得更糟，η大于或小于。 这表明，图聚类项r（G，M）和几何感知项r（G，X）两者，而不是一个或另一个，应该被考虑以实现更好的聚类结果。此外，在所有情况下，我们可以观察到，聚类结果是多我们接下来在美国邮政手上做了一个实验[16]由10个数字类别组成的书面数字数据集。每个图像有16个16像素。我们从每个类别中随机选择100幅图像生成10个子集，并用它们来评估每种方法当1−η太大了。 这是-结果：表3显示了对COIL 100的聚类结果。因为，当η接近于零时，方程的连续解。（12）可能以G=1NvT 5的形式近似因式分解，其中v是（K1）-单纯形中的向量，因此所有数据点倾向于被分配到单个聚类。此外，即使1-η比其峰值小得多，我们的方法也倾向于优于MSC基线基于这一观察，我们建议在无法调谐时选择小η（例如，当验证数据集不可用时）。5.2. 目标图像聚类设置：我们接下来在COIL100数据库[31]上进行了一项实验，该数据库由100个对象类别的7200张图像组成，例如鸭子和汽车。每个类有72个图像，每个图像有32个32像素。与EYaleB上的实验一样，我们通过随机选择十个类别来生成十个子集，并使用它们来评估每个方法结果：表2显示了对COIL 100的聚类结果。可以看出，在大多数情况下，我们的方法优于其他两种方法。这也证明了我们方法的有效性。5特别地，我们可以证明，当η= 0时，分配矩阵G总是方程的最优解之一（12）如果它可以分解为G=1NvT的形式，其中v是（K−1）-单形中的向量，并且对所有i都满足vi>0。证据见补充材料。可以看出，在大多数情况下，我们的方法优于其他两种方法。这也证明了我们方法的有效性。5.4. 轨迹聚类接 下 来 ， 我 们 在 Hopkins 155 运 动 分 割 数 据 库（Hopkins 155）上进行实验。Hop-kins 155是一个视频数据集，它由155个具有多个2D轨迹的视频序列组成。每个序列包含两个或三个运动。我们使用所有155个视频序列来评估每种方法结果：表4示出了对Hopkins155的聚类结果.可以看出，在大多数情况下，我们的方法优于其他两种方法。这也证明了我们方法的有效性。5.5. 将我们的方法引入结构化稀疏子空间聚类最近，已经提出了子空间聚类框架，将图构建和图聚类统一到单个优化问题中[13，24，48]。为了研究我们的方法是否对此类框架也有效，我们在EYaleB数据集上结合我们的方法和结构化稀疏子空间聚类（S3C）[24]（代表性统一框架之一）进行了实验。98832| |||i、j22不12345678910SSCLRRLSRCass方法准确度NMI精度NMI准确度NMI准确度NMIMSc0.749 0.6170.7650.773 0.7660.7680.784 0.789Seb0.749 0.6770.7710.784 0.7660.7680.784 0.799我们0.756 0.7870.7770.797 0.7860.7970.787 0.798表3.USPS数据集上的实验结果SSCLRRLSRCass方法准确度NMI精度NMI准确度NMI准确度NMIMSc0.939 0.8400.9370.830 0.9800.9360.881 0.733Seb0.939 0.8400.9370.830 0.9800.9360.881 0.733我们0.947 0.8600.9470.861 0.9790.9360.894 0.767表4.Hopkins数据集上的实验结果S3C：S3C通过最小化以下目标来同时优化自表示矩阵Z和分配矩阵G0.700.70minZ ∈{Z|Z∈RN×N，Zii=0}，G||1，G + τ||X-XZ||F，||F,（二十二）0.650.65哪里||Z||∑=|Z |gi − gj||2），α是a||2), andα is a0.60超参数S3C通过交替地更新Z和G，同时修复另一个。 更具体-迭代次数迭代次数换句话说，使用交替方向乘法器（ADMM）来更新Z，而已经提出了以下两种方法来更新G：G用一个二元分配矩阵来更新，该分配矩阵是通过对亲和矩阵M=Z+Z T应用谱聚类而计算出的。这种方法被称为Hard-S3 C。G用实值分配矩阵更新，该实值分配矩阵通过连接每个数据点的标准化K维嵌入来计算图4. EYaleB数据集上的实验结果。对于每种方法，每次迭代后的精度和NMI显示在此图中。最好用彩色观看。每次迭代的结束。其他实验设置与第5.1节中的EYaleB实验相同。实验结果：实验结果如图所示。4.从这些结果中，我们可以观察到，通过将我们的方法引入硬S3C和软S3C，聚类结果得到改善。这些结果表明使用我们的方法的有效性，即使是统一的图构造和图聚类的框架。|+的|Z|（即，|(i.e.,在k均值步骤之前）。 最终（二进制）分配矩阵G的计算简单地通过将谱聚类应用于最终亲和矩阵M.这种方法被称为Soft-S3 C。实验设置：在这个实验中，我们研究了用我们的方法替换Hard-S3 C和Soft-S3 C中的谱聚类是否能一致地改善聚类结果。具体地说，我们比较了四种方法：硬S3C，硬S3C与我们的方法，软S3C和软S3C与我们的方法。继Liet al.[24]，我们设置α=0。1，α=1。0分别用于硬S3C和软S3C。我们还设置τ=1。0的情况。我们迭代更新Z和G十次，计算性能为6. 结论我们提出了一种新的图聚类框架的鲁棒子空间聚类。通过将一个新的几何感知项与谱聚类目标相结合，我们鼓励我们的框架对给定亲和矩阵中的噪声和离群点具有鲁棒性。我们还开发了一种新的EM优化算法。通过在四个真实数据集上的大量实验，我们证明了所提出的方法优于现有的方法。此外，我们还证明了我们的方法对于统一图构造和聚类步骤的框架也是在未来，我们将致力于提供进一步的理论分析所提出的方法。软S3C硬S3C软-S3 C+我们硬-S3 C+我们软S3C硬S3C软-S3 C+我们硬-S3 C+我们精度NMI··地下1IJ0.60123456789109884引用[1] Pankaj K Agarwal和Nabil H Mustafa。K-means投影聚类。第23届ACM SIGMOD-SIGACT-SIGART数据库系统原理研讨会论文集，2004年。[2] RakeshAgrawal ， JohannesGehrke ， DimitriosGunopulos，and Prabhakar Raghavan. 数据挖掘应用中高维数据的自动子空间聚类，第27卷。ACM，1998年。[3] 劳伦特·巴科基于稀疏优化的线性切换系统辨识。Automatica，47（4）：668[4] 克 里 斯 托 弗 ·M· 毕 晓 普 。 模 式 识 别 和 机 器 学 习 。Springer，2006.[5] Terrance E Boult和L Gottesfeld Brown。基于因式分解的运动分割IEEE视觉运动研讨会，1991年。[6] Paul S Bradley和Olvi L Mangasarian。K平面聚类Journal of Global Optimization，16（1）：23[7] 陈广良和吉拉德·勒曼。谱曲率聚类。IJCV，81（3）：317[8] Yudong Chen，Ali Jalali，Sujay Sanghavi，and Huan Xu.通过凸优化对部分可观察图进行聚类。JMLR，15（1）：2213[9] João Paulo Costeira和Takeo Kanade。独立运动物体的多体分解方法。IJCV，29（3）：159[10] Ehsan Elhamifar 和 René Vidal 。 稀 疏 子 空 间 聚 类 。CVPR，2009。[11] Ehsan Elhamifar和Rene Vidal。稀疏子空间聚类：算法、理论和应用。TPAMI，35（11）：2765[12] 布莱恩·埃里克森，劳拉·巴尔扎诺，罗伯特·诺瓦克。高阶矩阵补全。在人工智能和统计学，2012年。[13] 冯佳世，林周晨，徐欢，严水城。基于块对角先验的鲁棒子空间分割。CVPR，2014。[14] 威廉·吉尔。 运动图像的多体分组。IJCV，29（2）：133[15] Han Hu，Zhouchen Lin，Jianjiang Feng，and Jie Zhou.平滑表示聚类。CVPR，2014。[16] 乔纳森·J赫尔一个用于手写文本识别研究的数据库TPAMI，16（5）：550[17] Amin Jalali和Rebecca Willett通过切锥的子空间聚类。在NIPS，2017年。[18] 潘骥，马蒂厄·萨尔茨曼，李洪东。高效的稠密子空间聚类。InWACV，2014.[19] 潘骥，马蒂厄·萨尔茨曼，李洪东。形状交互矩阵的重新访问和鲁棒性：有效的子空间聚类与损坏和不完整的数据。在ICCV，2015年。[20] 金谷健一通过子空间分离和模型选择的运动分割。载于CVPR，2001年。[21] 汉斯-彼得·克里格尔皮尔·克鲁格和亚瑟·齐梅克聚类高维数据：子空间聚类、基于模式的聚类和相关聚类综述。TKDD，3（1）：1，2009.[22] 赖汉江、潘燕、卢灿义、唐勇、严水城。高效的k-支撑矩阵追踪。2014年，在ECCV[23] Kuang-Chih Lee，Jeffrey Ho，and David J Kriegman.可变光照下人脸识别中线性子空间的获取。TPAMI，27（5）：684[24] Chun-Guang Li，Chong You，and René Vidal.结构化稀疏子空间聚类：一个联合亲和学习和子空间聚类框架.IEEE Trans. 图像处理，26（6）：2988 -3001，2017年。[25] 刘光灿，林周晨，余勇。通过低秩表示的鲁棒子空间分割。ICML，2010年。[26] Canyi Lu，Jiashi Feng，Zhouchen Lin，and ShuichengYan.基于轨迹套索的相关自适应子空间分割。InICCV，2013.[27] Can-Yi Lu，Hai Min，Zhong-Qiu Zhao，Lin Zhu，De-Shuang Huang，and Shuicheng Yan.通过最小二乘回归的鲁棒和高效的子空间分割。ECCV，2012年。[28] Yi Ma，Harm Derksen，Wei Hong，and John Wright.通过有损数据编码和压缩分割多元混合数据。TPAMI，29（9），2007年。[29] 布莱恩·麦克威廉姆斯和乔瓦尼·蒙塔纳。高维数据的子空间聚类：一种预测方法。数据挖掘和知识发现，28（3）：736[30] 全一莫和布鲁斯A德雷珀。用于缺失数据运动分割的半非负矩阵分解。ECCV，2012年。[31] Sameer A Nene，Shree K Nayar，Hiroshi Murase，等.Columbia对象图像库（线圈-100）。一九九六年。[32] Andrew Y Ng、Michael I Jordan和Yair Weiss。 关于谱聚类：分析和算法。NIPS，2002年。[33] Feiping Nie ， Xiaoqian Wang ， Michael I Jordan ， andHeng Huang.基于图聚类的约束Laplacian秩算法。在AAAI，2016。[34] 聂飞 平， 徐东 ，曾 伟雄 ，张昌 水。 谱嵌 入聚 类。InIJCAI，2009.[35] 兰斯·帕森斯，艾特沙姆·哈克，刘欢。高维数据的子空间聚类：审查. Acm Sigkdd Explorations Newsletter，6（1）：90[36] Shankar Rao，Roberto Tron，Rene Vidal，and Yi Ma.运动分 割中 存在的 边远 ，不 完整， 或损 坏的轨 迹。TPAMI，32（10）：1832[37] 菅谷泰之和金谷健一。多体运动分割的退化几何结构。视频处理中的统计方法国际研讨会，2004年。[38] Michael E Tipping和Christopher M Bishop。混合概率主成分分析器。神经计算，11（2）：443[39] Michael E Tipping和Christopher M Bishop。概率主成分分 析 皇 家 统 计 学 会 杂 志 ： Series B （ StatisticalMethodology），61（3）：611 - 622，1999.[40] 罗伯托·特隆和勒内·维达尔。三维