基于样本的类不平衡数据的扩展性

一种可扩展的基于样本的类不平衡数据陈有，陈立，陈立平。Robinson，Ren´eVidal美国约翰霍普金斯大学医学博士抽象。子空间聚类方法基于将每个数据点表示为几个其他数据点的线性组合（例如，稀疏子空间聚类）由于其经验上的成功和理论上的保证而成为无监督学习的流行工具。然而，它们的性能会受到不平衡的数据分布和大规模数据集的影响。本文提出了一种基于样本的子空间聚类方法，以解决不平衡和大规模数据集的问题。所提出的方法搜索最好地表示所有数据点的表示系数的1范数所测量的数据的子集。为了有效地解决我们的模型，我们引入了一个最远的第一搜索算法，迭代地选择最少的代表点作为样本。当数据来自一个联盟的子空间，我们证明了计算的子集包含足够的样本从每个子空间表达所有的数据点，即使数据是不平衡的。我们的实验表明，该方法优于国家的最先进的子空间聚类方法在两个大规模的图像数据集是不平衡的。我们还证明了我们的方法在人脸图像分类任务的无监督数据子集选择关键词：子空间聚类，不平衡数据，大规模数据1介绍计算机视觉中的大型注释数据集（诸如ImageNet）的可用性已经导致使用监督学习技术（诸如深度学习）的对象检测和分类的许多最近的突破。然而，随着数据大小的持续增长，注释数据以训练完全监督算法变得越来越困难。因此，开发可以从未标记数据集学习的无监督学习技术变得非常重要。现有的标记数据库，如ImageNet，是手动组织的，以实现类平衡。另一方面，未标记数据集中的数据样本的数量对于不同的类变化很大。因此，处理不平衡数据是无监督学习任务中的一个主要挑战传统的无监督学习方法利用了这样一个事实，即在许多计算机视觉应用中，数据的底层维度远小于环境维度。例如，众所周知，图像在变化的照明条件下的面部的亮度可以很好地近似为2C.你C Li，D.罗宾逊河维达尔λ11040.90.81020.71000.6（不平衡）10 25 40（平衡）第一子空间(a) 不平衡数据的聚类10-2103104105106数量的数据点(b) 大规模数据的聚类图1.一、不平衡数据和大规模数据的子空间聚类（a）x和100−x点（x在x轴上变化）从在5维环境空间中均匀随机绘制的2个3维注意，SSC的聚类准确性随着数据集变得不平衡而显著降低。（b）在20维的环境空间中随机均匀地画出10个5维的子空间从每个子空间均匀随机抽取相等数量的点请注意，SSC的运行时间随着数据大小的增加而显著增加。一个9维的子空间在实践中，计算机视觉数据集通常包含多个类，因此它们可以通过低维子空间的并集来建模。子空间聚类[1]是一种流行的无监督学习方法，用于从这些数据中联合学习子空间的并集，并将每个数据点分配到其相应的子空间。许多最近的子空间聚类方法遵循两步方法：（1）学习数据点之间的亲和图，以及（2）将谱聚类[2]应用于该图。特别地，最先进的方法通过利用自我表达属性[3]来学习亲和性，该属性指出子空间的并集中的每个数据点可以被写为其他点的线性组合从现在的空间中。ΣThatis，givevendataX={x1，···，xN}IRD，thereexists{cij}suchthatxj=i=/ jcijxianddcijisnonzeroonlyifxianddxjarfromom相同的子空间。这样的表示{cij}被称为子空间保持。在特别地，如果子空间维度小，则表示可以被认为是稀疏的。基于此观察，稀疏子空间聚类（SSC）[3，4]求解，对于每个j ∈ {1，2，. . . ，N}，稀疏优化问题min cΣ+·x−c x2，（1）J1cj∈RN伊季I2I j其中λ >0且cj= [c1j，· · ·，cNj]λ。随后，任何一对点xi和xj之间的亲和度被定义为|国际新闻报|+的|CJi|.现有的无噪声以及损坏的数据的理论结果表明，在某些条件下，（1）的解是子空间保持的[4-8]，从而证明了SSC的亲和性的正确性。 通过使用SSC，许多方法已经对系数{ cij } [9-14]执行了所使用的差分正则化。稀疏子空间聚类示例子空间聚类稀疏子空间聚类示例子空间聚类聚类精度时间（秒）2基于样本的类不平衡数据子空间聚类3λ尽管SSC及其变体取得了巨大成功，但先前的实验评估主要集中在平衡数据集，即数据集与来自每个聚类的近似相等数量的样本。在实践中，数据集往往是不平衡的，这种偏斜的数据分布可以显着损害SSC的聚类性能，如图1（a）所示。从理论上讲，我们推测，对于xj，在代表性不足的类中，（1）的解更有可能具有与代表性过强的类中的数据点相对应的非零条目这一猜想的证明将是未来工作的主题。许多基于自我表达的子空间聚类方法的另一个问题是它们仅限于小型或中型数据集[15]。图1（b）示出了作为数据点数量N的函数的SSC的运行时间，其大致是N的二次方。纸质捐款。我们提出了一种基于样本的子空间聚类方法来解决不平衡和大规模数据的问题给定一个数据集X，我们的想法是选择一个子集X0，我们称之为样本，并将每个数据点写为X0中的点的线性组合（而不是SSC中的Xmin cΣ+x−cx 2。（二）J1cj∈RNIJI2i：xi∈X0观察到，当X0在类之间平衡时，在寻找子空间保留表示此外，当X0相对于原始数据X小时，可以潜在地比（1）更有效地求解（2）。因此，为了实现对不平衡数据的鲁棒性和对大型数据集的可扩展性，我们需要一种有效的算法来选择在类之间更加平衡的样本X0在本文中，我们提出了一个新的模型，选择一组样本X0的基础上最小化的数据X的最大表示成本。(The本文结果的证明可以在[16]中找到此外，我们引入了一个有效的算法来解决具有线性时间和内存复杂度的优化问题与SSC相比，基于样本的子空间聚类对不平衡数据不太敏感，对大数据更有效（见图1）。此外，我们的工作做出了以下贡献：– 我们提出了一个几何解释，我们的范例选择模型和算法作为一个子集的数据，最好的覆盖整个数据集的Minkowski功能的子集。– 我们证明，当数据位于一个独立的子空间的联合，我们的方法是保证选择足够多的数据点，从每个子空间，并构建正确的数据亲和，即使当数据是不平衡的。– 我们在两个不平衡的图像数据集上评估我们的方法：EMNIST手写字母数据集和GTSRB街道标志数据集。实验结果表明，我们的方法优于国家的最先进的聚类性能和运行时间。– 我们通过在扩展Yale B人脸数据库上的实验证明，我们的模型选择的样本可以用于无监督子集J24C.你C Li，D.罗宾逊河维达尔20选择任务，其中目标是从大数据集中选择可以用于训练分类器的子集，该分类器导致最小的性能损失。2相关工作稀疏字典学习（SDL）。给定数据集的稀疏表示是信号处理和机器学习中研究得很好的问题[17，18]。给定集合XIRD和整数k，SDL计算原子字典DIRD，其中|D| ≤k，使稀疏表示成本最小化。基于SDL，[19]提出了一种线性时间子空间聚类算法，如果字典D中的原子位于与输入数据X相同的子空间的并集中，则该算法保证是正确的。然而，很少有证据表明这样的条件在真实数据中得到满足，因为字典D的原子不被约束为X的子集。另一个最近的工作[20]，使用数据独立的随机矩阵作为字典，也遭受这个问题，缺乏正确性保证。稀疏字典选择。显式地约束要从X中获取的字典原子的SDL模型的三个变型是同时稀疏表示[21]和字典选择[22，23]，其使用贪婪算法来解决它们各自的优化问题，以及组稀疏表示选择[24特别地，当数据是从独立子空间的并集中提取时，[26]中的方法被示出为从每个子空间中选择几个代表然而，这些方法在X中的点数方面具有二次复杂度。此外，基于凸优化的方法在选择期望数量的代表时不灵活，因为子集的大小不能通过调整算法参数来直接控制。子集选择。选择整个数据的代表性子集已经在广泛的背景下进行了研究，例如行列式点过程[30-32]，秩显示QR [33]，列子集选择[34，35]，可分离的然而，他们不建模的数据来自一个联盟的子空间，也没有证据表明，他们可以选择良好的代表，从这样的数据。几个最近的作品[39k-中心和k-中心点。k-中心问题是理论计算机科学和运筹学中研究的数据聚类问题。给定一个集合X和一个整数k，目标是找到一个中心集合X0X，其中|x0的|k表示最小化量maxx∈Xd2（x，X0），其中d2（x，X0）：= minv∈Xx − v2是x到X中最近点的距离的平方。X的一个划分由每个点x∈ X所属的最近中心给出 k-中心点是Σfk-中心点的一个变体，它最小化了平方距离的和，即. 例如， minimizesx∈ Xd2（x，X0）而不是最大距离. 然而，K-中心和k-medoids将数据建模为集中在几个聚类中心，并且通常不适用于位于子空间的并集中的数据。基于样本的类不平衡数据子空间聚类5λ23基于样本的子空间聚类在本节中，我们提出了我们的ESC方法，用于聚类给定的一组数据点X={X1，...，XN}。我们首先制定的模型选择一个子集X0的样本从X。由于该模型是一个组合优化问题，我们提出了一个有效的算法近似求解。最后，我们描述了从样本X0生成聚类分配的过程。3.1基于自我表征成本的在不失一般性的情况下，我们假设X中的所有数据都被归一化为具有单位2范数。回想一下，在SSC中，每个数据点xj∈ X被写为所有其它数据点与系数向量Cj的线性组合。虽然每个cj中的非零项确定了X的一个子集，该子集可以表示系数上具有最小1范数的xj，但所有xj的集合通常需要整个数据集X。在ESC中，目标是找到一个小子集X0X，它代表X中的所有数据点。特别地，集合X0应该包含来自每个子空间的样本，使得针对每个数据点Xj∈ X的解Cj到（2）是子空间保持的，即cj的非零项对应于与xj相同的子空间中的点。在下文中，我们根据（2）中的优化定义成本函数，然后呈现我们的范例选择模型。定义1（自我表征成本函数）。给定X={Xl，· · ·，XN}在IRD中，我们将自表示成本函数Fλ：2X→IR定义为Fλ（X0）：= supfλ（xj，X0），其中（3）xj∈Xf（x，X）：=mincΣ+x−cx2，（4）λ j 0J1cj∈RNIJI2i：xi∈X0λ ∈（1，∞）是一个参数。 按照惯例，我们假设fλ（xj，）= λ，对于所有xj∈ X，其中表示空集.在几何上，fλ（x，X0）度量数据点x∈ X被子集X0覆盖的程度（见第4节）。函数fλ（x，X0）具有以下性质。引理1. 函数fλ（x，·）关于由集合包含定义的偏序是单调的，即，fλ（x，X ′）≥fλ（x，X ′′）.0 0 0 0引理2. fλ（x，X0）的值位于[1−1，λ]中。达到了下界2λ 2当且仅当x ∈ X0或−x∈ X0，且当X0=时达到上界。观察到如果X0包含来自包含xj的子空间的足够样本，并且（4）的最优解cj是子空间保持的，则预期cj将是稀疏的，并且残差xj-X0cj将接近于零。这表明我们应该选择子集X0，使得值fλ（xj，X0）很小。由于值Fλ（X0）是由具有最大值的数据点xj实现的J26C.你C Li，D.罗宾逊河维达尔000000000值f（xj，X0），我们建议通过搜索使自我表示成本函数最小化的子集X* X来执行样本选择，即，X*= arg minFλ（X0），（5）|≤k| ≤k其中k∈Z是样本的目标数量注意目标函数（5）中的Fλ（·）根据以下结果是单调的。引理3. 对于任意的X ′ X ′′ X，我们有Fλ（X ′）≥ Fλ（X ′′）。0 0 0 0求解优化问题（5）通常是NP难的，因为它需要对大小至多为k的每个子集X0评估Fλ（X0）。在下一节中，我们提出了一个计算效率高的近似算法。3.2ESC的最远优先搜索算法在算法1中，我们提出了近似求解（5）的有效算法。该算法逐步增长的候选子集X0（初始化为空集），直到它达到所需的大小k。在每次迭代i，步骤3算法选择由曲线表示最差的点x∈ X通过f λ（x，X（i））测量的租金子集X（i）。对此的几何解释0 0步骤见第4节。特别地，在引理2中示出：fλ（x，X（i））= 1−1，对所有x∈ X（i），且fλ（x，X（i））>1−1，如果x都不∈X（i）02λ0 02λ0n或−x∈X（i）。 因此，x∈/X（i）在Al或i h m1的每个阶段期间。0 0我们还注意到，FFS算法可以被看作是FFS算法的扩展最远第一遍历算法（参见，例如，[42]），这是第2节中讨论的k -中心问题的近似算法。算法1用于样本选择的法拉第优先搜索（FFS）输入：数据X ={X1，. . . ，xN} IRD，参数λ> 1且k N。1：随机选择x∈ X并设置X（1）← {x}。2：对于i=1，···，k−1 do3： X（i+1）=X（i）∪arg maxx∈Xfλ（x，X（i））0 0 04：end forOutput：X（k）有效执行。 观察到算法1的每次迭代都需要对每个x ∈ X计算fλ（x，X（i））。因此，算法1的复杂度在数据点的总数N中是线性的，假设k是固定的并且很小。然而，计算fλ（x，X（i））本身并不容易，因为它需要解决稀疏优化问题。在下文中，我们介绍一种有效的实现，其中我们在每次迭代中跳过针对某些x的fλ（x，X（i））的计算。支撑这种计算节省的想法是fλ（x，·），如3 . 1 节 所 述。也就是说，对于任何X′X′′X我们基于样本的类不平衡数据子空间聚类7000000000000j′j′算法2 FFS输入：数据X ={X1，. . . ，xN} IRD，参数λ> 1和k. 1：随机选择x∈ X并初始化X（1）← {x}。2：对于j = l，…，N，C〇mputebj=fλ（xj，X （1））。3：对于i=1，···，k−1 do4： 设〇1，· · ·，〇N是1，· · ·，N的序，使得当p q时，b〇p彡b〇q<。5：初始化最大成本= 0。6：对于j=1，···，N，7：设置b〇= fλ（xo，X（i））。j j08：ifboj>maxcosthen9：Setmaxcost=boj，newindex=oj。10：如果结束11：ifj=Normaxcost≥boj+1then12：休息13：如果结束14：结束15： X（i+1）=X（i）{xnew index}。0 016：对于输出：X（k）有fλ（xj，X′）≥fλ（xj，X′′）。在FFS算法中，其中集合X（i）是亲-0 0 0如果f λ（xj，X（i））是递增的，这意味着fλ（x j，X（i））在i中是非递增的。使用该结果，我们的高效实现在算法2中概述 在步骤2中，我们iializeij=fλ（xj，X（1）），如果ea chj∈{1，···，N}，其中对于fλ（xj，X（i）），i≥ 1，i i i是上界。在每次迭代i中，我们的目标是找到一个点x∈ X使fλ（x，X（i））最大化为了做到这一点，我们首先找到一个排序o1，···，oN（一），N，使得b〇1彡· · ·彡b〇N （步骤4）。 然后我们计算fλ（·，X）se。，X （ i） ） 的最高值（步骤9）的同时保持跟踪fλ（·，X（ i））一旦maxcost≥boj+1处的条件满足（step11），我们就可以在任何时候确定该条件j′> j，则点xo不是fλ（x，X（i））的最大化者. 这可以从fλ（xo，X（i））= 0j′j′8C.你C Li，D.罗宾逊河维达尔算法3 ESC-FFS子空间聚类输入：数据X ={X 1，. . . ，xN} IRD，参数λ> 1，k和t.1 ： 来 自 Algorithm2 的 C 〇 m pute X 〇 ， 以 及 来 自 （ 2 ） 的 C 〇 mpute{cj} 。Letc~j=cj/cj2。2：SetWij=1ifc~j是一个 由 c~i和0otherwise组成的结构;SetA=W+W i。3：将谱聚类应用于A以获得X的分割。输出：X的分割。使用该观察，我们使用最近邻方法来计算X的分割（参见算法3）。首先，系数向量{c，j}被归一化d，i。例如， wesetc~j=cj/cj2. 对于c~j而言，发现了具有大容量存储器的数据库，该存储器通过c~j 进 行 预 处 理。（尽管它实际上是使用绝对值为t的最大内积，但这种方法在我们的数值实验中表现不佳最后，我们从t-最近邻计算亲和矩阵，并应用谱聚类得到分割。4ESC的理论分析在本节中，我们将对3.1节中的样例选择模型和3.2节中的FFS算法进行几何解释，并研究此操作位于子空间的连接处。为了实现分析，我们假设通过将（4）扩展到λ=∞来严格执行自表示xj=ijcijxi，即，我们让Σf∞（x，X0）= minc1s. t.X=c∈RNi：xi∈X0cijxi.（六）按照惯例，如果优化问题是不可行的，我们设f∞（x，X0）=∞4.1几何解释我们首先提供由（5）选择的样本的几何解释。给定任意X0，我们将对称化数据点的凸包表示为X0为K0，即，K0：= conv（±X0）（参见图2中的示例）。与集合K0相关联的Minkowski泛函[43]由以下给出。定义2（Minkowski泛函[43]）。与集合K0IRD相关联的Minkowski泛函是由下式给出的映射IRD→R∪ {+∞}：x（七）特别地，如果集合{t > 0：x/t∈ K0}是空的，我们定义x K 0：= ∞。我们的几何解释的特点是由 xK0的倒数。闵可夫斯基泛函是在跨距（K0）中的范数，跨距是由K0张成的空间，其单位球是K0。因此，对于任何x∈span（K0），点x/xK0是射线{tx：t≥0}与K0的边界的交点。图2中的绿点和红点分别是x和x/xK0的示例因此，量1/xK0是凸包K0内的射线{tx：t≥0}的长度。基于样本的类不平衡数据子空间聚类90使用定义2，可以证明以下成立[44，5]：对所有x ∈ IR D，xK= f∞（x，X0）.（八）（8）和解译的组合X3xK0XXx2上述1/xK0的作用提供了一个geomet-1−x1f∞（x，X0）的理论解释也就是说，f∞（x，X0）是大的，如果射线的长度−x −x2 3{tx：t≥0}在K0内是小的。在部分-ular，f∞（x，X0）是无穷大，如果x不在X0的跨度内，即，x不能用X0线性表示。通过使用（8），（5）中的范例选择模型等效于计算图二. X={x1，x2，x3}时（5）的解的几何图解。阴影区域是凸包K0。X*= arg max inf 1/2000K。（九）0|≤k| ≤kx∈X0因此，（5）的解是X的子集X。，其对于每个数据x∈ X最大化K0和射线{tx：t≥0}的相交（即，最大化在所有x上的这种交点的最小值）。此外，从（8）我们可以看到，算法1的每次迭代都选择使1/xK0最小的点x∈ X。因此，FFS的每次迭代添加使射线{tx：t >0}与K0的交点最小化的点x。与球面覆盖问题的关系。现在让我们考虑当数据集X与IRD的单位球面重合时的特殊情况，即，X=SD−1。在这种情况下，我们建立（5）与找到最小覆盖半径有关，其在下面定义。定义3（覆盖半径）。点集V的覆盖半径SD−1定义为γ（V）：=Maxmincos −1（mv，w m）.（十）w∈SD−1v∈V集合V的覆盖半径可以解释为最小角度，使得以V中每个点为中心的球冠与此半径的并集覆盖整个单位球面SD−1。下面的结果建立了覆盖半径和我们的成本函数之间的引 理 4.对 任 何 有 限 的 X0X = SD−1 ， 我 们 有 F∞ （ X0 ） = 1/cos γ（±X0）。从引理4得出：|x0的|≤kF∞（X0）= arg min |x0的|≤k γ（±X0）当X=SD−1时，即由（5）选择的样本X0给出了寻找具有最小覆盖半径的子集的问题 注意，具有以下条件的子集X0的覆盖半径γ（±X0）|x0的|当对称化集合±X 0中的点尽可能均匀地分布在球面SD−1上时，≤ k最小。在球面上均匀分布点而不对称它们的问题，即min |x0的|≤kγ（X0），称为球面覆盖问题。这个问题首先由[45]研究，并且在几何学中仍然没有解决[46]。X10C.你C Li，D.罗宾逊河维达尔=1=1S.0=1=1j=14.2子空间并上的ESC现在，我们研究我们的范例选择方法时，适用于从一个联盟的子空间的数据的属性。设X是从一个子空间集合中画出的联系我们尺寸{d}n每个子空间S至少包含d样本跨越S。我们假设子空间是独立的，这通常用于子空间聚类方法的分析[47，3，10，9，48]。假设1. 子空间{S}n是独立的，即，Σnd等于达到…的Σn=1ℓℓ=1=1下一个结果表明（5）的解包含来自每个子空间的足够样本。定理1. 在假设1下，对于所有k≥Σnd，解X*为=1（5）中的优化问题包含至少d个线性无关点每个子空间S。此外，每个点x ∈ X被表示为线性的X *中来自其子空间的点的组合。定理1表明，当k被设置为n时，d，然后是d点被选择从子空间S，而不管该子空间中的点的数量因此，当数据是类不平衡的时，（5）能够选择更平衡的子集这就忽略了将数据点写成线性组合时在X 中的所有点中，更可能选择来自子空间的任意点。定理1还表明，只有n=1 需要数据点来正确表示-重新发送X中的所有数据点。换句话说，所需的样本数量用于表示数据集的X不随数据集X的大小而缩放。尽管3.2节中的FFS算法是近似算法并且不一定给出（5）的解，但以下结果表明，它给出了对于子空间聚类具有吸引人的性质的近似解定理2.定理1的结论对X（k）成立由Algo返回-当k ≥ Σ n时，公式1成立.0d定理2表明，我们的算法FFS是能够选择足够的样本从每个子空间，即使数据集是不平衡的。它还表明，对于X中的每个数据点，在算法3的步骤1中计算的表示向量是子空间保持的。形式上，我们已经建立了以下结果。定理3. 取任意k≥ Σnd.在假设1下，表示向量{cj}N在算法3的步骤1中， cij是非零，仅当xi和xi来自相同的子空间。5实验在本节中，我们演示了ESC在子空间聚类和无监督子集选择任务中算法2的步骤7和算法3的步骤1中的稀疏优化问题（4）由=1基于样本的类不平衡数据子空间聚类11LARS算法的LASSO版本[49]在SPAMS包[50]中实现。算法3的步骤2中的最近邻居通过在VLFeat工具箱[51]中实现的k-d树算法来计算。5.1子空间聚类我们首先展示了ESC的性能，在大规模的类不平衡数据库的子空间聚类。下面将介绍这些数据库数据库。我们使用两个公开的数据库。扩展MNIST（EMNIST）数据集[52]是MNIST数据集的扩展，其包含灰度手写数字和字母。我们采取所有190998图像对应的26个小写字母，并使用它们作为26类聚类问题的数据。该数据集中每个图像的大小为28 x 28。在[48]之后，每个图像由从散射卷积网络[53]计算的特征向量表示，该特征向量是平移不变的 并且变形稳定 的（即， 它线性化小变 形）。因 此，来自EMNIST方法的这些特征遵循子空间模型的联合。德国交通标志识别基准（GTSRB）[54]包含43类街道标志数据，总共超过50，000张图像。我们删除了与限速和三角形标志（除了屈服标志）相关的类别，因为它们很难相互区分，这导致最终的数据集为14个类别的12390张图像每个图像由数据库提供的1，568维HOG特征[55]表示GTSRB中的主要类内变化是照明条件，因此数据可以通过子空间的并集很好地近似[56]。对于EMNIST和GTSRB两者，特征向量被减去均值并且通过PCA投影到维度500并且被归一化为具有单位<2范数。EMNIST和GTSRB数据库都不平衡。例如，在EMNIST中，每个字母的图像数量范围从2，213（字母“j”）到28，723（字母“e”），每个字母的样本数量大约等于它们在英语中的频率。在图3中，我们显示了这两个数据库中每个类的实例数基线。我们将我们的方法与SSC [4]进行比较，以显示样本选择在解决不平衡数据方面的有效性。为了处理大规模数据，我们使用[12]中的有效算法来解决SSC中的稀疏恢复问题为了与ESC进行公平的比较，我们使用与用于ESC相同的过程来计算SSC的亲和图算法3中的过程。我们还比较了我们的方法与k-均值聚类和谱聚类在k-均值聚类上的差异，以及在图和表中的“特殊性”众所周知[57]，Spectral是子空间聚类的可证明正确的方法。使用VLFeat工具箱[51]实现用于计算Spectral中的k-最近邻图的k-均值和k-d树算法此外，我们还比较了其他三种能够处理大规模数据的子空间聚类算法OMP我们将这些方法与ESC-FFS（算法3）进行比较，其中对于EMNIST和GTSRB，λ分别设置为150和15，并且对于两者，t设置为312C.你C Li，D.罗宾逊河维达尔p+R图3.第三章。EMNIST（左）和GTSRB（右）数据库中每个类别的点数数据库。我们还报告了当样本从X中随机选择时的ESC-Rand结果，即，我们通过FFS替换样本选择，算法3的步骤1通过从X中随机选择k个原子以形成X0。评估指标。我们使用的第一个度量标准是聚类精度。它测量在标签的所有可能排列具体地，令{C1，···，Cn}为数据的真实划分，{G1，···，Gn}为相同数据的聚类结果，|CiGj|是C i和G j中的公共对象的数量，并且是{1，···，n}的所有排列的集合。聚类精度定义为100Σn准确度=最大值π∈ΠNi=1ni，π（i）.（十一）在分类的上下文中，当数据集是类不平衡的时，准确性已知是有偏差的[59]。例如，如果一个数据集由来自一个特定类别的99%的样本组成，那么将所有数据点分配给同一个标签将产生至少99%的准确度。 为了解决这个问题，我们还使用F-分数averagedoverallcl作为ses。 Letpij=nij/|GJ|bete recisionanddrij=nij/|Ci|是召回。 聚类结果Gi与真实类Cj之间的F分数被定义为Fij=2pijrij。我们将保留由ij ijF评分=最大值π∈Π100ΣnnFi，π（i）。（十二）i=1EMNIST上的结果。图4显示了EMNIST的结果。从左到右，子图分别示出了作为样本数量（X轴）的函数的准确度、F分数和运行时间（Y轴）。我们可以看到，ESC-FFS显着优于所有的方法，除了SSC的准确性和F-分数时，样本的数量是大于70。回想一下，在SSC中，每个数据点都表示为所有其他点的线性组合通过选择样本的子集并使用这些样本表达点，当样本的数量达到200时，ESC-FFS能够优于SSC。相比之下，ESC-Rand并没有明显优于SSC，这表明FFS选择样本的重要性。在运行时间方面，我们看到ESC-FFS比SSC快很多。具体地，ESC-FFS几乎与ESC-Rand一样有效，这表明所提出的FFS算法2是有效的。基于样本的类不平衡数据子空间聚类13F-score8080105707060605050404030 3010410320100 200 300样本数量(a) 精度20100 200 300样本数量(b) F-score100 200 300样本数量(c) 运行时间图4.第一章EMNIST数据库中26个小写字母图像的子空间聚类GTSRB的结果。表1报告了GT-SRB数据库上的群集性能。除了报告平均性能外，我们还报告标准偏差。1）k均值算法的随机初始化，其（平凡地）用于K均值方法和所有其他方法的谱聚类步骤中，以及2)OLRSC、SBC、ESC-Rand和ESC-FFS中的随机字典初始化。我们观察到，ESC-FFS优于所有其他方法的准确性和F分数。特别是，ESC-FFS优于SSC，这反过来又优于ESC-Rand，从而显示了找到一组有代表性的范例和FFS在实现这一目标的有效性的重要性此外，ESC-Rand的准确性和F分数的标准差都大于ESC-FFS。这表明FFS给出的样本集在给出可靠的聚类结果方面比随机选择的样本集在ESC-Rand。在运行时间方面，ESC-FFS也具有竞争力。5.2无监督子集选择给定一个大规模的未标记数据集，手动注释所有数据是昂贵的。一种解决方案是选择用于手动标记的数据的小子集，然后通过在所选择的子集上训练模型来推断剩余数据的标签。在本节中，我们将评估FFS算法作为为给定数据集选择代表子集的工具的性能。随后利用该子集对整个数据集进行分类。我们使用扩展耶鲁B人脸数据库，其中包含38张人脸的图像，每个人都是在64种不同的照明条件下拍摄的为此表1. GTSRB路标数据库的子空间聚类。对于ESC-Rand和ESC-FFS，参数k固定为160。我们报告准确性、F分数和运行时间（以秒为单位）的平均值和标准差。10个审判K均值光谱OMP SSC OLRSC SBCESC-Rand ESC-FFS精度63岁7± 3。5895±1。382岁8± 0。892。4± 1。1716± 4。374。9± 5。289岁。7 ± 1。693。0 ±1。3F-score五十四4± 2。8798± 2。567岁8± 0。582. 3± 2。8667± 4。七七二。2± 8。575. 5 ± 4。985 3±2。5时间（秒）12个。2± 0。五点四十3± 0。7二十二岁0± 0。2522± 0。七六四9±1。6419± 0。421岁5 ± 0。四点二十五2± 1。2K均值光谱OMPSSCOLRSCSBCESC-RandESC-FFS精度时间（秒）14C.你C Li，D.罗宾逊河维达尔表2.从扩展的Yale B人脸数据库的子集分类我们报告的平均值和标准差的分类精度和运行时间的子集选择从50个试验。兰德k-中心K-中心点kDPPSMRsFFSNN69岁。4±3。269岁。1±3。775. 5±2。8七十5±3。269岁。0±3。167岁5±4。0SRC84. 7±2。284. 9± 2。686岁。0±2。188岁3±2。383岁4±2。391. 4 ±2。4SVM83岁7±2。583岁0±2。8八十五3±2。387岁8±2。182岁1±2。391. 0 ±3。0时间（秒）<1e− 30的情况。26±0。011 .一、5±0。10的情况。57±0。063 .第三章。1±0。20的情况。70±0。08在实验中，我们通过随机选择10个类并从每个类中采样一个子集来创建一个不平衡数据集。我们为这10个类采样的图像数量是前3个类16个，后3个类32个，其余4个类64个。我们首先应用FFS从该数据集中选择100个图像。请注意，在此阶段，我们假设地面真值标签是未知的。然后，我们在所选图像上训练三个分类器，最近邻（NN），基于稀疏表示的分类（SRC）[60]和线性支持向量机（SVM），然后用于对所有图像进行分类。我们将FFS与随机抽样（Rand）、k-中心、K-中心[61]、SMRS [26]和kDPP [32]进行比较。对于k-中心，我们实现最远的第一遍历算法（参见例如[42]）。对于K-中心点，我们使用由在[61]中，算法的实施方式各不相同。 对于SMRS和kDPP，我们使用作者提供的代码。我们在FFS中设置λ= 100在表2中，我们报告了50次试验的平均分类准确度。我们可以看到，NN分类器在K-中心点上的效果最好，但其性能不如SRC和SVM。这是因为相同面部的图像近似地位于子空间中，并且它们的成对距离可能不小。当使用SRC和SVM作为分类器时，我们可以看到我们的方法达到了最佳的性能。6结论提出了一种新的不平衡大规模数据的子空间聚类方法我们的方法从给定的数据集搜索一组样本，使得所有的数据点可以很好地表示的样本在稀疏表示成本。分析上，我们证明了由我们的模型选择的样本集具有这样的性质，即对于所有数据点x∈ X，其对称凸包覆盖尽可能多的射线{tx：t≥0}。在在子空间聚类的背景下，我们证明了我们的方法选择了一组样本，这是小的和平衡的，同时能够代表所有的数据点。我们还介绍了一个算法近似解决样本选择优化问题。经验上，我们证明了我们的方法是有效的子空间聚类和无监督子集选择应用。致谢。C.你D P. Robinson和R. Vidal由NSF在拨款1618637下支持。C. Li由IARPA在赠款127228下支持。基于样本的类不平衡数据子空间聚类15引用1. 维达尔，R.：子空间聚类IEEE信号处理杂志28（3）（2011年3月）522. von Luxburg，U.：光谱聚类教程统计与计算17（4）（2007）39 53. Elhamifar ， E. ， 维 达 尔 ， R. ： 稀 疏 子 空 间 聚 类 。 在 ： IEEE 会 议 上 的CommputerrVisionandPatterrnRecognition。（2009）27904. Elhamifar，E.，维达尔，R.：稀疏子空间聚类：算法、理论与应用。IEEE Transactions on Pattern Analysis and Machine Intelligence 35 （ 11 ）（2013）27655. Soltanolkotabi，M.， Cand d`es，E. J. ：子块空间的几何结构随用户而变化。AnalsofStatistics40（4）（2012）21956. 你C维达尔，R.：子空间稀疏恢复的几何条件。In：Inter-nat_nal_C〇n_fe_nc_e〇n_M_achi_e_a_rn_g. （2015）15857. Wang ， Y.X. ， Xu ， H. ： 噪 声 稀 疏 子 空 间 聚 类 。 Journal of MachineLearningResearch17（12）（2016）18. 你C Robinson，D.维达尔，R.：子空间并中基于可证自我表示的离群点检测。IEEE计算机视觉与模式识别会议。（2017年）9. Liu，G.，林芝，Yu，Y.：低秩表示的鲁棒子空间分割In：Internati n a（2010）66310. Lu，C.Y.，Min，H.，Zhao，Z.Q.，Zhu，L.，中国科学院，Huang，D.S. ， Yan ， S. ： 通 过 最 小 二 乘 回 归 的 鲁 棒 和 在 ： 欧 洲 会 议 上CommputerrVision.（2012）34711. Dyer，E.L.，Sankaranarayanan，A.C.，Baraniuk，R.G.：子空间的贪婪特征选择。JournalofMac hi neLearni ng Reserc h14（1）（2013）248712. 你C Li，C.G.，Robinson，D.维达尔，R.：基于Oracle的可扩展弹性网子空间 聚 类 有 效 集 算 法 。 In ： IEEE Conference on Computer VisionandPatternRecognition. （2016）392813. 杨，Y.，冯杰，Jojic，N.，杨杰，Huang，T.S.：0-稀疏子空间聚类。In：Er opeanConfer enceonCom up uterVison。（20 16）73114. Xin，B.，王玉，Gao，W.，Wipf，D.：将不变性构建到稀疏子空间分类中。IEEETransacti onsonSignalProces sing66（2）（2018）44915. 你C Donnat，C. Robinson，D.维达尔，R.：大规模子空间聚类的分治框架。Asilomar Conference on Signals，Systems and Computers（信号、系统和计算机会议）（2016年）16. 你C Li，C.，Robinson