文件标题：基于可证自表示的离群点检测

3395并子空间中基于可证自表示的离群点检测作者：Daniel P. Robinson，Rene 'Vidal约翰霍普金斯大学，巴尔的摩，MD，21218，美国摘要许多计算机视觉任务涉及处理大量被离群值污染的数据，这些离群值需要被检测和拒绝。虽然基于鲁棒统计的离群点检测方法已经存在了几十年，但是仅最近才开发出基于稀疏和低秩表示的方法，以及当内点位于一个或多个低维子空间中时正确离群点检测的保证。本文提出了一种新的孤立点检测方法，结合稀疏表示和图上的随机游走。利用数据点可以表示为稀疏线性组合的性质，得到了数据点间的非对称亲和矩阵，并利用该矩阵构造了一个加权有向图.通过从这个图定义一个合适的马尔可夫链，我们建立了马尔可夫链的内点/离群点和本质/非本质状态之间的联系，这允许我们通过使用随机游走来检测离群点。我们提供了一个理论分析，证明我们的方法的正确性，几何和连通性假设。图像数据库上的实验结果表明，相对于最先进的稀疏和低秩离群点检测方法的优越性。1. 介绍在计算机视觉的许多应用中，包括运动估计和分割[18]和人脸识别[2]，高维数据集可以很好地近似于低维子空间的并集。这样的应用激发了大量关于从数据中学习一个或多个子空间的问题的研究子空间学习和子空间聚类。在实践中，数据集经常被不位于子空间中的点污染，即，异常值在这种情况下，在执行任何后续处理/分析之前，检测并拒绝这些离群值通常是必不可少的以前的工作。我们解决的问题，离群点检测的设置时，内点数据被假定为躺在一个未知的低维子空间（低相对于周围空间的维度）的工会。解决这个问题的传统方法是RANSAC [12]，基于随机选择点的子集，将子空间拟合到它们，并计算由该子空间良好拟合的点的数量;对于足够多的试验重复该过程并选择最佳拟合。RANSAC本质上是组合的，并且找到子空间的良好估计所需的试验次数随着子空间维度呈指数增长因此，选择的方法是通过惩罚点到最近子空间的非平方距离之和（代替PCA等经典方法中使用的平方距离）来鲁棒地学习子空间[9，21，54，53]。这样的惩罚对于异常值是然而，优化问题通常是非凸的，一个好的初始化对于找到最优解是非常重要的。赖特等人的开创性工作。[47] and Cand e'setal. [4]关于使用卷积x优化技术来解决对损坏条目具有鲁棒性的PCA问题，已经导致了许多最近的对离群值具有鲁棒性的PCA方法[48，28，23，52，20]。例如，OutlierPursuit[48] 使 用 核 范 数 · 通 过 求 解 问 题 minL<$X−L<$2 ，1+λ<$L<$（对于某些λ>0）来寻求低秩解。凸优化技术的一个突出优点是保证在一定条件下能正确识别异常值最近，几个非凸离群点检测方法也已开发出保证正确性[19，6]。尽管如此，这些方法通常对唯一的内层子空间进行建模，例如，在离群点追踪中通过低秩矩阵L，并且因此不能处理多个内量子空间，因为多个子空间的并集可能是高维的。另一类具有正确性理论保证的方法利用了离群值与其他数据点具有低相似性的事实在文献[5，1]中，引入了由极曲率定义的多路相似性，它具有利用子空间结构的优点。然而，多路相似性中的组合的数量可能非常大。一些最近的工作已经探索了使用数据点之间的内积进行离群值检测[16，35]。虽然计算上非常有效，但这些方法要求内点在子空间内良好分布并密集采样。3396(a) （b）表示矩阵R图1.存在离群值时的自我表征矩阵R的说明数据矩阵X的前32列对应于来自扩展耶鲁B数据库的一个个体在不同照明下的32张图像，接下来的32张图像是从所有其他个体中随机选择的;每个类别的三个示例显示在1（a）的顶部附近。 我们还在1（a）中示出了内点和离群点图像的典型表示向量，并且在1（b）中示出了完整的表示矩阵R，其中白色和黑色表示rij/= 0并且rij= 0。请注意，内点在其表示中仅使用其他内点，而离群点在其表示中使用内点和离群点。概述我们的方法和贡献。在这项工作中，我们解决的问题，离群检测使用数据的自我表示。所提出的方法建立在最初在[ 10 ]中引入的低维子空间的并集中的数据的自表达性属性上，其声明子空间中的点总是可以表示为子空间中其他点的线性组合。 特别地，如果X =[x1，···，xN]的列位于多个子空间中，则对于所有j = 1，. . . ，N，存在一个向量rj∈IRN使得xj=Xrj且rj的非零项对应于与xj相同的子空间中的点.如果子空间维数很小，则rj可以被认为是稀疏的，并且可以通过求解最小化问题来计算不返回到异常值的集合，因为一旦随机游走到达内点，它就不能返回到异常值。因此，我们设计了一个随机游走过程，并将离群值确定为概率趋于零的我们的工作对最先进的技术做出了以下贡献：1. 我们的方法可以检测离群值使用的概率分布的随机游走的图从数据的自我表示。2. 我们的数据自表示允许我们的方法处理多个内层层空间。不需要子空间的数目及其维数的知识，并且子空间可以具有非平凡的交集。3. 我们的方法可以通过我们来探索上下文信息-最小值γ公司简介-Xr2S.T.R= 0（1）进行随机游走，即，一个jj12jj2jj最大的点取决于它的邻居的4. 我们的分析表明，我们的方法正确地识别，对于某些γ>0。在[10]中，由R=[r1，···，rN]构造了一个无向图，其中每个顶点对应于一个数据点，如果rij或rji非零，则对应于xi和xj的顶点是连通的这样的图可以通过将谱聚类[41]应用于图的拉普拉斯算子来将数据分割到它们各自的子空间中。现在考虑X包含子空间的异常值的情况 图1示出了从（1）计算的示例表示矩阵R，用于从单个子空间（来自一个个体的面部图像）加上离群值（其他图像）提取的数据。 在这种情况下，表示R是这样的，即内点将其自身表示为几个其他内点的线性组合，而离群点将其自身表示为内点和离群点两者的线性组合。 受此观察的启发，我们使用有向图来建模数据关系：从xj到xi的有向边表示xj在其表示中使用xi（即， Rij 0）。 然后在表示图上初始化为离群值的随机游走将在对表示图的数据分布和连通性的适当假设下的离群值。5. 在真实图像库上的实验表明了该方法的有效性。2. 相关工作通过自我表征进行离群点检测。先前的工作已经探索了使用数据自表示作为子空间的联合中的离群值检测的工具。具体来说，由于观察到离群值没有稀疏表示，[37，8]如果xj在阈值以上，则将点xj声明为离群值。然而，这种阈值化策略对于彼此接近的离群值并不鲁棒，因为它们的表示向量可能具有小的1-范数。 LRR [25]求解低秩自表示矩阵R，而不是稀疏表示，并惩罚未平方自表示误差之和<$xj−X rj<$2，R3397我使其对异常值更鲁棒。然而，LRR要求子空间是独立的，并且子空间的并集的和是低维的[26]。通过最大一致性进行离群值检测。在各种各样的背景下，如最大一致性[55，7]和稳健线性回归[29，42]，人们研究了以下形式的问题构造数据自表示矩阵R =[r1，···，rN]。正如在引言中简要讨论的那样（也参见图1），观察到从（1）计算的自表示矩阵R对于内点和离群点具有不同的属性具体地，内点通常仅使用其他内点用于自我表示，即， 对于内点xj，该表示是这样的：仅当xj也是内点时，minBΣNi=1I（|xb−y i|≥ 100），（2）其中rij是R的第（i，j）个条目。如果内点位于低维子空间的并集中，则预期该属性成立，如从作品[11，37，51，45，43]中所证明的作为一个直观的解释，如果内围值位于低距离，其中I（·）是指示函数。请注意，如果我们设置yi= 1，则（2）可以被解释为检测数据X中的异常值，其中内点靠近仿射超平面。与（2）密切相关的问题是ΣN如果在这个子空间中，任何内点都具有使用该子空间中的其他点的稀疏表示。因此，这种表示可以通过使用稀疏诱导的正则化来发现，如（1）所示。相比之下，离群值通常随机分布在周围空间中，使得自-表示通常包含内点和外点。minBi=1I（|xb| ≥100）s.t.B我0，（3）由于从（1）计算的表示R是稀疏的，因此在表示中存在潜在的连接性问题其出现在许多应用中（例如，参见[34]）。 按面值-（3）可以用来从被异常值破坏的数据中学习线性超平面。为了检测一般低维子空间中的异常值，可以递归地应用（2）和（3）来找到子空间的正交补的基础[39]。然而，这种方法是有限的，因为只能有一个内层层空间和维数，图，即与其他内点没有良好连接的内点可以被检测为离群点，连接不好的节点可以被检测为内点。为了解决连通性问题，我们通过弹性网络问题计算数据自表示矩阵R[56，49]：minλr+1−λr2+γx−X r2s.t. R= 0，必须预先知道子空间大小。通过随机游走进行离群点检测。也许最jj12j22jj2jj（四）众所周知的基于随机游走的算法是PageRank [3]。PageRank最初是为了从网络图中确定网站页面的权威性而引入的，PageRank及其变体已在不同的上下文中用于对图中顶点的中心性进行排名。特别是，[30，31]提出了OutRank，它对点的“离群”进行排名，通过将PageRank应用于无向图的数据集，其中边的权重是两个连接的数据点之间的余弦相似性或然后，具有低中心性的点被视为离群点。OutRank返回的离群值是那些与其他数据点相似度较低的离群值。因此，如果子空间中的点不够密集，OutRank就不起作用。3. 自我表征离群点检测在本节中，我们提出了基于数据自表示的离群点检测方法。我们首先描述了数据的自我表示及其相关属性的内点和离群点。然后，我们设计了一个随机游走算法的表示图的限制行为，使我们能够识别的内点和离群值的集合。3.1. 数据自表示给定一个未标记的数据集X=[x1，···，xN]，其中包含内点和离群点，我们算法的第一步是其中，λ∈[0，1]控制稀疏-稀疏-性 （ 通 过 101 正 则 化 ） 和 连 通 性 （ 通 过 102 正 则化）。具体地说，如果λ被选择为接近1，我们仍然可以预期计算出的内点表示将只使用内点。已经引入了E12正则化以促进数据点之间的更多连接即如果λ∈[0，1），则期望在R.第4节详细讨论了从（4）计算的表示和连通性问题。3.2. 表示图与随机游动我们使用有向图G，我们称之为表示图，从表示矩阵R中捕获内点和离群点的行为。G的顶点对应于数据点X，并且边由（加权）邻接矩阵A给出：|R|n ∈IRN×N，其绝对值按元素取，即， 从xi到xi的边的权重是giv en，由aij=|rji|. 在表示图中，我们期望对应于内点的顶点将具有仅导致内点的边，而作为离群点的顶点将具有导致内点和离群点两者的边换句话说，我们不期望有任何从内点到离群点的边缘。以上一段为动机，我们设计了一个随机游走过程来识别离群值。表示图G上的随机游动是一个离散时间R3398Σ10马尔可夫链，其中从xi在给定时间到下一时间的xj由pij给出：=算法1通过表示图进行离群点检测输入：数据X= [x1，...，xN]，#迭代T，阈值T。aij/di，其中di：=是的。根据这个定义，如果开始1：使用X使用（4）求解R =[r1，···，rN]。一个随机游走的点是一个内点，那么它永远不会逃脱因为没有从任何内点到任何离群点的边缘。相比之下，从离群值开始的随机游走将可能最终处于内点状态，因为一旦它进入任何内点，它将永远不会返回到离群值状态。因此，通过使用不同的数据点来初始化随机游走，可以通过观察随机游走状态的最终概率分布来识别离群值（见图2）。如果P∈IRN×N是元素为pij的转移矩阵，则P与表示矩阵R相关，p ij=|rji|对于所有{i，j}∈{1，2，···N}，（5）定义π（t）=[π（t），. . . ，π（t）]为状态概率第二章： 使用（5）从R计算P。3：初始化t=0，π=[1/N，···，1/N]，π<$=0。4：对于t= 1，2，. . . 没做5：计算π+π。第六章： 端7：π/T。输出：异常值的指示器：如果π<$j≤π，则x j是异常值。1N分布，则状态转换由下式给出：π（t+1）=π（t）P。因此，t阶跃是π（t）=π（0）Pt其中π（0）是所选择的初始状态概率分布。3.3. 主要算法：基于R图的离群点检测我们建议通过在表示图G上使用随机游走来执行离群点检测。设初始概率分布为π（0 ）=[1/N，···，1/N]，然后计算t步跃迁π（t）=π（0）Pt.这可以被解释为从N个数据点中的每一个初始化随机游走，然后在t个步骤之后找到所有随机游走的概率分布的总和预计所有随机游走-从内点或外点开始-最终将具有内点状态的高概率和外点状态的低概率我们注意到，如上定义的π（t）不需要收敛，如二维示例P=[01]所示。相反，我们选择使用T步Ces表示，giv enby图2. 在一个表示图上的随机游动的说明。上图：绿色球表示内点，红色球表示外点，箭头表示节点之间的边。请注意，从内值到离群值之间没有边界。从任何点开始的随机游走将仅在内围点结束。底部：π<$（100）的条形图，第i个条形对应于π<$（100） 中 的 第i个 条 目。对该概率分布使用阈值将正确区分离群值和内值。（T）=1ΣTπ（0）Pt1ΣTπ（t），（6）包含从未知数量的未知子空间{S}n中提取的内点，以及在T T，=1t=1t=1S=1S，目标是识别离群值的集合。它是第一个T步概率分布的平均值（见图2）。序列{π<$（T）}的好处是它总是收敛的，并且当π（t）存在时，它的极限与π（t）的极限相同。在下一节中，我们将更详细地讨论这种选择，它的离群点检测属性及其收敛行为。我们的完整算法称为算法1。4. 正确性的理论保证让我们首先正式定义问题的离群检测和灰时，数据是从一个联盟的子空间。问题1（子空间并集中的离群点检测）给定数据X=[x1，···，xN]∈IRD×N，其列回想一下，我们的方法的动机是，理想情况下，在表示图中不会有从内点到离群点的边。这促使我们假设从任何内点开始的随机游走最终会返回到自身，即。内点是马尔可夫链的基本状态，而离群点是那些有机会永远不会回到自身的状态，即异常值是不重要的状态。形式上，我们使用状态空间为{1，· · ·，N}的（时间齐次）马尔可夫链，其中每个状态j对应于数据xj，并且转移概率P由（5）给出。给定{i，j}，我们说j是从i可达的，记为i→j，如果存在某个t>0使得Pt的第（i，j）项是正的。直观地说，i→j，如果随机游动可以从i到j移动200步。1234563399λX定义1（本质态和非本质态[22]）一个态i∈n是本质态，如果对所有j使得i→j，j → i也为真。一个国家如果不是必不可少的，那么它就是不必要的我们在本节中的目的是确定，如果内点与自身一致，即。它们是子空间保持的（第4.1节），并且表示R满足某些连通性条件（第4.2节），则内点是马尔可夫链的本质状态，而外点是非本质状态。随后，在第4.3节中，我们表明Cesa` ro意味着(6) 识别必要和不必要的状态，从而建立- ING算法1的正确性离群检测。4.1. 子空间保持表示我们首先建立内点只与其他内点表达自己时，他们躺在一个低维子空间的联合。这个属性在子空间聚类文献中得到了很好的研究。我们将借用以前工作中的术语和结果，并将其修改为我们当前的离群值检测任务。定义2（子空间保持表示[40]）如果xj∈ S是内点，则表示rj∈ IR N被称为子空间保持，如果rj的非零项对应于S中的点，即。 r ij0仅当xi∈ S<$。若表示矩阵R =[r1，···，rN] ∈IRN×N是子空间保持的，则rj对每个内点xj都是子空间保持的.一个表示矩阵R是子空间保持的，如果每个内点使用它自己的子空间中的点来表示。给定X，当某些几何条件成立时，可以通过求解（4）来获得子空间保持表示R下面的结果是由[49]修改而来的它假设X的列被归一化为具有单位的2-范数。定理1设xj∈ S ∈N是一个内点。定义x j的预言点为δj：=γ·（xj−X·r），其中X为包括来自其它子空间的异常值和内值该条件要求前者比后者大1−λ的裕度，如果λ接近于1.一、总的来说，条件（7）要求S <$i中的点在δ<$j周围是稠密的，δ <$j本身也在S <$i中，并且来自其他子空间的离群点和内点不靠近δ<$j。即使（7）对所有j成立，R是子空间保持的，我们不能自动建立内点/离群点和本质/非本质状态之间的等价性，因为与图的连通性相关这一点将在下面讨论。4.2. 连通性考虑在稀疏子空间聚类的上下文中，众所周知的连通性问题[32，46，27，49，44]是指同一子空间中的点在表示图中可能没有很好地连接的问题，这可能导致真实聚类的过度分割。因此，必须假设每个真正的聚类是连接的，以保证正确的聚类。对于离群点检测问题，可能发生的情况是，一个内点是不重要的，因此当内点不是良好连接时被分类为离群点;类似地，如果离群值没有连接到至少一个内点，则离群值可能是必要的，并且因此被分类为内点。事实上，这种情况甚至更加复杂，因为表示图是有向的，并且内点和离群点的行为不同。作为第一个例子，假设存在一个内点，它从未被用来表示任何其他内点。这相当于说没有任何边缘从任何其他内点进入该点请注意，如果此内点使用其他内点表达自身，则子空间保留属性仍然成立然而，由于离开该点的随机游走永远不会返回，因此不能将其识别为内围值。为了避免这种情况，我们需要做以下假设。−j j−j矩阵包含S中除xj以外的所有点，r：= arg minλ<$ r +1−λ<$r2+γ<$x−X<$2.假设1对于任何内层子空间S，{xj∈ S<$}是强连续的，连接，即在每个方向上都有一条路径，jr1222j−j2一对顶点。（4）的解rj是子空间保持的，如果假设1要求点之间具有良好的连通性max|阿克斯|− max|>1−λ，|>1−λ,（七）来自同一个内层子空间 我们还需要良好的沟通-王空军k/=j，k∈S王空军k：xk∈/S异常值和内值之间的关系考虑实例其中reδ<$j：=δj/δj<$2。我们在[50]中提供了一个证明大纲注意，顶点δj位于S中，它的定义只依赖于S中的点。条件（7）中的第一项捕获了S中靠近δ<$j的点的分布，并且如果δ<$j的邻域被S中的点很好地覆盖，则期望是大的。第二项描述了预言点δ<$j和所有其他数据点之间的相似性，当存在异常值的子集时，对于该子集，它们的所有外出边缘仅通向该相同子集内的点。在这种情况下，点的子集不能被检测为异常值，因为它们的表示模式与内点的表示模式相同。下一个假设排除了这种情况。假设2对于离群值的每个子集，在表示图中存在从该子集中的点到该子集之外的内点或离群点的边。λ3400m axi：ij|xxi|4.3. 主要定理：保证离群点检测我们现在可以通过我们的基于表示图的方法（如算法1所述）来建立有保证的离群值检测。定理2如果表示R是子空间保持的，并且满足假设1和2，则算法1在T=∞和∞= 0时正确地识别离群值。定理2是以下两个事实的直接结果（证明见[50]）。引理1如果表示R是子空间保持的并且假设1和2成立，则内点和离群点分别对应于本质和非本质状态。引理2对于任意概率转移矩阵P，（6）中的平均概率分布满足limT→∞π<$（T）=π，其中e π使得πj=0当且仅当状态j是非本质的.定理2表明，如果数据X满足中的几何条件，则问题1可由算法1求解。(7) 并且表示图满足所需的连通性假设。我们注意到，这里采用的Cesa` ro平均值的随机游走不同于例如PageRank采用的流行的重新开始的随机游走PageRank的好处然而，目前尚不清楚这种平稳分布是否识别离群值。事实上，PageRank随机游走中的所有状态都是必不可少的，因此离群值不会收敛到零概率。与此相反，在我们的方法中的随机游走不一定有一个唯一的平稳分布，但Cesa` ro平均确实收敛到一个平稳分布，我们已经证明，可以用来识别离群值。详细讨论见[50]。5. 实验我们使用几个图像数据库（见图3）来评估我们的离群值检测方法（算法1）。 为了计算（4）中的表示rj，我们使用[17]中的求解器，其中λ= 0。95和γ= α·λ，其中α是pa-J(a) 扩展耶鲁大学B(b) 加州理工学院-256(c) 线圈-100图3. 用于离群值检测的数据示例。对于每个数据库，顶部行显示了内点集的示例，底部行显示了离群点集的示例。48×42。Caltech-256 [15]是一个数据库，包含来自256个类别的图像，每个类别有80多个图像。 在这个数据库中还有一个额外的Coil-100数据集[33]包含100个不同对象的7，200张图像。每个物体有72个图像，以5度的姿势间隔拍摄，图像大小为32×32。对于扩展的Yale B和Coil-100数据集，我们使用原始像素强度作为特征表示。Caltech-256中的图像由从16层VGG网络的最后一个全连接层中提取的4，096维特征向量表示[36]。基线。我们比较了其他6个代表性的方法，旨在检测一个或多个异常值参数调整到每个数据集。 特别是，（4）非零当且仅当α>1。迭代次数T设为1000。5.1. 实验装置数据库。我们从三个公开的数据库中构建离群值检测任务。扩展的Yale B [14]数据集包含38个人在64种不同照明条件下的正面人脸图像。面部图像的大小为192×168，我们对其进行下采样，tiple子空间：[48]第 3 5 话 ： 我 的 世界[20]，DPCP [39]，LRR [25]，以及[37]的阈值。我们还比较了基于图的方法：OutRank [30，31]。我们实现了不精确的ALM [24]来解决OutlierPursuit中对于LRR，我们使用可在https://sites.google.com/site/guangcanliu/在线获得的代码。对于DPCP，我们使用作者提供的代码所有其他方法均根据其各自论文中的描述实现。评价指标。 每一种离群值检测方法都是3401表1. 扩展耶鲁B数据库上的结果。取一个或三个随机选择的受试者的图像作为内点，从其他受试者中随机选择离群点（每个受试者最多一个）。对于R-图，我们在γ的定义中设置α= 5。级别高于警察收割者OutlierPursuitLRRDPCP阈值化R图（我们的）Inliers：来自同一受试者的所有图像离群值：35%，取自其他受试者AUC0.5360.5560.9640.9720.8570.9520.8440.986F10.5520.5630.9110.9180.7970.8850.7630.951内点：来自三名受试者的所有图像离群值：15%，取自其他受试者AUC0.5190.5290.9320.9680.8070.8880.8480.985F10.2880.2920.7580.8560.5090.6530.5450.878为每个数据点指定一个数值，表示其“离群值”，并且需要一个阈值来确定内值和离群值。受试者操作特征（ROC）曲线绘制了所有阈值的真阳性率和假阳性率。我们使用曲线下面积（AUC）作为ROC方面的性能指标。AUC总是在0和1之间，完美模型的AUC为1，随机猜测的模型的AUC约为0。五、作为第二个指标，我们提供了F1分数，这是精确度和召回率的调和平均值。F1分数取决于阈值，我们报告所有阈值中最大的F1得分为1意味着存在一个阈值，该阈值使精确度和召回率都等于1，即内点和离群点的完美分离。本节中讨论的所有实验的报告数字是50次试验的平均值。5.2. 人脸图像假设我们得到一组一个或多个人的图像，但数据集也被各种其他人的面部图像所破坏。我们的任务是检测和删除那些外围的人脸图像。已知在不同光照条件下的人脸图像近似地位于低维子空间中。因此，这个任务可以建模为一个子空间或子空间的并集中的离群值检测问题。我们使用扩展的耶鲁B数据库。在第一个实验中，我们从38个受试者中随机选择一个个体，并使用该受试者的所有64张图像作为内点。然后，我们从剩下的37个子样本中选择图像作为离群值，每个主题最多有一个图像。整个数据集有25%的离群值。表1报告了50项试验的平均AUC和F1测量值。为了进行公平的比较，我们对所有方法的参数进行了微调。与最先进的技术相比我们看到我们的代表-基于站图的方法R-图优于其他方法方法.除本文方法外，REAPER、Outlier Pur- suit和DPCP算法都有较好的性能.这三种方法学习单个子空间，并将那些不适合子空间的子空间视为离群值，从而使它们非常适合此数据（一个个体的图像可以通过单个低维子空间很好地近似）。LRR和L1阈值方法使用数据自表示，这也是我们的方法的情况然而，LRR并没有给出好的离群点检测结果，这可能是因为其求解LRR模型的算法不能保证收敛到全局最优值。101-阈值也没有给出好的结果，表明表示向量的幅度不是用于分类离群值的鲁棒度量。通过考虑表示图中的连接模式，我们的方法取得了显着更好的结果。OutRank和CoP的性能明显差于其他方法。这种较差的性能可以通过使用基于相干性的距离来解释例如，可以认为，具有相同照明条件的两个面部之间的相干性可以高于相同面部在不同照明条件下的两个图像处理多个inlier组。为了测试这些方法处理多个内点组的能力，我们设计了第二个实验，其中取内点是3个随机选择的受试者的图像，并且如前所述，从其他受试者中随机抽取离群值。对于所有方法，我们使用与先前实验中相同的参数该实验的结果报告在表1中。我们可以看到，离群点追踪和我们的R图是两个最好的方法。虽然离群值追踪仅对单个低维子空间进行建模，但它仍然可以处理这些数据，因为与内点集中的三个受试者相对应的三个子空间的并集仍然是低维的，并且可以被视为单个低维子空间。然而，我们假设，随着我们增加内点组的数量，离群点追踪最终会失败，因为低维子空间的并集将不再是低秩的。我们的方法没有这个限制。与离群点追踪类似，原则上，REAPER和DPCP都可以通过将单个子空间拟合到它们的并集来处理多个内点组然而，REAPER和DPCP需要输入内围子空间的并集的维数，这在实践中可能难以估计事实上，在表1中，我们观察到，与离群值追踪相比，REAPER和DPCP的性能竞争力较低3402表2.加州理工256数据库的结果内点被取为一个、三个或五个随机选择的类别的图像，并且离群点从类别257-杂波中随机选择。对于R-图，我们在γ的定义中设置α= 20。级别高于警察收割者OutlierPursuitLRRDPCP阈值化R图（我们的）内点：一类图像离群值：50%AUC0.8970.9050.8160.8370.9070.7830.7720.948F10.8660.8800.8080.8230.8930.7850.7720.914内点：三类图像离群值：50%AUC0.5740.6760.7960.7880.4790.7980.8100.929F10.6820.7180.7840.7790.6710.7770.7820.880内点：五类图像离群值：50%AUC0.4070.4870.6570.6290.3370.6760.7740.913F10.6670.6720.7160.7110.6670.7150.7620.858表3. Coil-100数据库的结果。内点被取为一个、四个或七个随机选择的类别的图像，并且离群点从其他类别中随机选择（每个类别中最多一个）。对于R-图，我们在γ的定义中设置α= 10。级别高于警察收割者OutlierPursuitLRRDPCP阈值化R图（我们的）Inliers：来自一个类别的所有图像离群值：50%AUC0.8360.8430.9000.9080.8470.9000.9910.997F10.8620.8660.8920.9020.8720.8820.9780.990内点：来自四个类别的所有图像离群值：25%AUC0.6130.6280.8770.8370.6870.8590.9920.996F10.4910.5000.7030.6860.5410.6840.9410.970内点：来自七个类别的所有图像离群值：15%AUC0.5700.5800.8240.8220.6280.8040.9910.996F10.3420.3460.5410.5280.3660.5110.8970.955以及三个子空间情形的R图。5.3. 物体图像中的异常值我们测试的方法，以确定一个或几个对象类别，经常出现在一组图像中的离群值，包括对象，很少出现的能力。对于Caltech-256，在三个不同的实验中，使用n∈ {1，3，5}随机选择的类别中的图像作为内点从每个类别中，如果cat-egory有超过150个图像，我们使用前150个图像。然后，我们从“杂波”类别中随机挑选一定数量的图像对于Coil-100，我们随机选取n∈ {1，4，7}个类别作为内点，并从每个剩余类别中选取至多一个图像作为离群点。结果报告于表2和表3中。 我们看到我们的R图方法实现了最佳性能。两种基于几何距离的方法，OutRank和 CoP ， 在 有 一 个 内 点 类 别 时 取 得 了 很 好 的 效 果REAPER、Outlier Pursuit和DPCP的性能相似，但比我们的方法差这可能是因为它们都试图将线性子空间拟合到数据，而这两个数据库中的数据可以通过非线性流形更好地建模。阈值法和表示图法都是基于数据的自我表达，似乎对这些数据更有影响力6. 结论提出了一种结合数据自表示和表示图上随机游走的离群点检测方法与许多现有的方法鲁棒PCA，我们的方法是能够处理多个子空间，不需要知道子空间的数量或它们的尺寸。我们的分析表明，当满足一定的几何条件和两个连通性假设成立时，该方法保证识别离群点。在人脸图像和目标图像数据库上的实验中，我们的方法达到了最先进的性能。确认这项工作得到了NSF BIGDATA资助1447822的支持。作者还感谢Manolis Tsakiris、Conner Lane和Chun-Guang Li提供的有益意见。引用[1] E. Arias-Castro，G. Chen和G.勒曼基于局部线性近似的谱聚类电子学。J. 中央集权主义者，5：1537-1587，2011. 1[2] R. Basri和D.雅各布斯朗伯反射与线性子空间。IEEETransactionsonPatternAnalysisandMachineIntelligence，25（2）：218-233，2003。13403[3] S. Brin和L.页.大规模超文本网络搜索引擎的剖析。计算机网络和ISDN系统，30：107-117，1998。3[4] E. 我能吃吗，X。 L i，Y. Ma和J. 赖特稳健的主成分分析。ACM杂志，58，2011年。1[5] G. Chen和G. 勒曼 谱曲率聚类。International Journalof Computer Vision，81（3）：317-330，2009. 1[6] Y. Cherapanamjeri，P. Jain和P. Netrapalli。基于门限的有 效 离 群 鲁 棒 主 元 分 析 。 arXiv 预 印 本 arXiv ：1702.05571，2017。1[7] T.- J. Chin，Y.Heng Kee，A.Eriksson和F.诺伊曼用混合整数线性规划去除异常值.在IEEE计算机视觉和模式识别会议论文集，第5858-5866页3[8] Y. Cong，J. Yuan，and J.刘某用于异常事件检测的稀疏重建成本。在The 24 th IEEE Conference on ComputerVision and Pattern Recognition，CVPR 2011，ColoradoSprings，CO，USA，2011年6月20-25日，第34492[9] C. Ding，D. Zhou，X.他，和H。扎。R1-pca：鲁棒子空间分解的旋转不变l1范数主元分析。第23届国际机器学习会议论文集，第281ACM，2006年。1[10] E. Elhamifar和R.维达尔稀疏子空间聚类。在IEEE计算机视觉和图案识别会议，第2790-2797页，2009年。2[11] E. Elhamifar和R.维达尔稀疏子空间聚类：算法、理论和应 用 。 IEEE Transactions on Pattern Analysis andMachine Intelligence，35（11）：2765 3[12] M. A. Fischler和R. C.波尔斯RANSAC随机样本共识：模型 拟 合 的 范 例 ， 应 用 于 图 像 分 析 和 自 动 制 图 。Communications of the ACM，26：381-395，1981. 1[13] R. G.加拉格随机过程：理论应用。剑桥大学出版社，2013.[14] A. Georghiades，P. Belhumeur，D.克里格曼从少数到多数：可变光照和姿态下人脸识别的光照锥模型。IEEETransactionsonPatternAnalysisandMachineIntelligence，23（6）：643-660，2001。6[15] G. Griffin，A. Holub，和P.佩洛娜加州理工256目标分类数据集。2007. 6[16] R. Hec k el和H. 我是波奇。基于阈值的鲁棒子空间聚类IEEE Transactions on Information Theory，61（11）：6320-6342，2015。1[17] B. Jin，L. Lorenz和S.希弗勒弹性网络正则化：误差估计和有效集方法。逆问题，25（11），2009年。6[18] K. Kanatani基于子空间分离和模型选择的运动分割。IEEEInternational Conference on Computer Vision，第2卷，第586-591页，2001年。1[19] G. Lerman和T.毛努快速、鲁棒和非凸子空间恢复。arXiv预印本arXiv：1406.6145，2014年。1[20] G. Lerman，M.B. McCoy，J.A. Tropp和T.张某线性模型的凸松弛鲁棒计算发现-计算数学，15（2）：363 - 4 1 0 ， 2 0 1 5 。1、6[21] G. Lerman和T.张某利用几何最小化方法实现多子空间的鲁 棒 恢 复。Annals of Statistics，39（5）：2686-2715，2011. 1[22] D. A. Levin，Y.Peres和E.L. 威尔默马尔可夫链和混合时间。美国数学学会2009. 5[23] X. Li和J. Haupt.通过随机自适应压缩采样识别大矩阵中的离群值。IEEE Transactions on Signal Processing，63（7）：1792-1807，2015。1[24] Z.林，M。陈湖，澳-地Wu和Y. MA.增广的La- grange乘子法精确恢复损坏的低秩矩阵。arXiv：1009.5055v2，2011. 6[25] G. Liu，Z. Lin和Y. Yu.低秩表示的鲁棒子空间分割。国际机器学习会议，第663-670页，2010年。二、六[26] G. Liu，H.Xu和S.燕. 基于低秩表示的精确子空间分割在AISTATS，第703-711页，2012年。3[27] C. Lu，Z.Lin和S.燕. 相关自适应子空间跟踪套索分割。IEEEInternational Conference on Computer Vision ， 第1345-1352页，2013年。5[28] M. McCoy，J. A. Tropp等人基于半定规划的鲁棒主元分析的两个建议。电子统计杂志，5：1123-1160，2011年。1[29] K. Mitra，A. Veeraraghavan和R.切拉帕 基于稀疏正则化的鲁棒回归方法分析。IEEE Transactions on SignalProcessing，61（5）：12493[30] H. Moonesignhe和P. - N.