非负低秩亲和度图的构建

非负低秩亲和度图的构建

1非负局部约束低秩子空间算法在过去几十年中，他研究了子空间。谱聚类算法的关键步骤在于构建亲和度图。构建亲和度图的方案分为基于局部距离和基于全局线性表示两种。基于局部距离的方法利用成对点之间的欧氏距离建立亲和度图,如拉普拉斯特征图稀疏子空间聚类算法与基于稀疏方法相比,基于低秩的方法旨在找到所有数据的最低秩表示,即rank(Z),s.t.X=XZ。此方法更适合追求数据空间的全局和内在信息。然而,低秩表示算法不能利用数据之间局部线性结构,这将导致构造的亲和度矩阵通常是密集的,并且低秩表示中的负值在构建亲和度矩阵上没有任何意义。为了兼顾数据的全局和局部结构,本文提出了非负局部约束低秩子空间算法,该算法在低秩表示的基础上,将数据的局部稀疏结构作为约束集成到统一公式中。此外,原始数据作为字典不具有代表性,基于学习的字典对噪声有良好的鲁棒性。考虑到最终结果的准确性,在预处理数据时,采用Wei2相关工作2.1子空间的集合令X=[x其中第i个块Z2.2低秩表示算法低秩表示算法旨在探索多个子空间结构,从而找到一组数据向量的最低秩表示。对于无噪声的情况,低秩表示算法将数据本身作为字典,并寻找最低秩表示矩阵Z:由于秩函数不是凸的难以求得最优值,式(2)最优化问题可以放宽到以下凸优化问题:其中||⋅||对于存在噪声的情况,低秩表示算法通过向目标函数(3)添加列和范数项处理噪声数据,使得噪声稀疏:虽然实验结果表明直观地,该模型消除了大部分噪声,并采用干净数据作为字典,当数据本身严重损坏时,最终的聚类效果比低秩表示算法有明显提升。3正则项参数平衡稀疏与低秩约束及法典更新在2.1节中,说明了对于块对角矩阵Z如果字典是过于完备的(比如用数据本身作为字典)可以有无穷多个可行解,为了解决这个问题,对所求的表示矩阵Z加入稀疏与低秩约束:式(6)中β>0是正则项参数平衡稀疏性与低秩性,表示矩阵Z的每一列z其中||⋅||同时,也要考虑到噪声的影响,加入噪声项E的同时,对字典进行更新:典D根据2.2节Wei该模型具体来说,每个数据点由其他数据点的线性组合得到,表示矩阵Z是非负且稀疏的3.2交替方向乘子法对于式(8),虽然在求解过程时固定其他变量求解单一变量可以确保函数为凸函数,但计算量仍非常巨大。因此在确定字典时,基于Wei根据引理1可以将式(8)近似地转化为如下两式:式(9)用核范数近似替代秩函数(rank),利用增广拉格朗日方法去除约束条件后,借由Lin具体迭代求解流程见算法1,其中Θ对于式(10),交替方向乘子法(ADM)在求解时需要引入两个辅助变量,每个变量迭代都需要庞大的矩阵计算。因此,采用线性交替方向自适应法(LADMAP)首先,引入辅助变量H使目标函数变量可分离:式(12)的增广拉格朗日方程为:为后续计算简便,式(13)化简为:线性交替方向自适应法(LADMAP)通过求解单一变量时,固定其他变量为最小值来交替更新变量Z、H和E,其中二次项其中∇为关于Z的偏微分操作,Θ、S、Ω分别是奇异值阈值操作、收缩阈值操作、l完整迭代算法流程见算法2。3.3亲水矩阵的建立得到表示系数矩阵Z3.4非负局部限制低质子空间算法定义亲和度矩阵W后,剩下工作为构建亲和度图,图中的每个顶点对应着每个数据点x4视觉任务性能本章将评估非负局部约束低秩子空间算法(NLRSI)对合成数据和实际计算机视觉任务(运动分割和手写数字聚类)的性能。为了直观表达效果,将与基于谱聚类的最先进的子空间聚类算法,如稀疏子空间算法(SSC)对于比较的算法,采用引用文献中的参数作为输入参数,其中对于Hopkins155运动分割数据库4.1局部约束低秩算法当p=0与p=0.3时,图2与图3显示了亲和度矩阵W或者表示系数矩阵Z通过图2与图3的对比可以看出,非负低秩稀疏表示算法(NNLRSR)与非负局部约束低秩算法(NLRSI)对噪声的鲁棒性能较好,这表明通过局部约束强制更改矩阵结构可以消除大量无关噪声,使得聚类效果提升,这也在图1的准确率变化趋势图中有所体现。4.2hopcs1-pcr聚类误差运动分割是指从视频序列中提取一组二维点轨迹,将轨迹对应于不同的刚体运动。这里,数据矩阵X的尺寸为2F×N,其中N是二维轨迹的数量,F是视频中的帧数。在仿射投影模型下,n个不同运动对象相关联的二维轨迹位于n个仿射子空间的组成的R本部分采用Hopkins155数据库表1显示了Hopkins155数据库中155个序列聚类误差,图5与图6展示了155个序列应用非负局部约束低秩子空间算法(NLRSI)各自的聚类误差,明显的,二物体比三物体聚类误差更小。同时从表1中的数据可以看出NLRSI算法的聚类误差比其他算法误差小,虽然低秩表示算法(LRR)的中位值更低,但是从平均值结果来看,低秩表示算法对于某些序列的聚类效果不稳定,导致了误差过大,拉高了平均值。4.3写数字手写数字聚类是指由不同人笔迹构成的一组数字图像,将数字相同的图像分离出。这里采用美国邮政手5聚类算法的比较本文提出了非负局部约束低秩子空间算法(NLRSI),该算法利用数据的局部稀疏结构和子空间的全局低秩特征,构造体现数据向量之间特点的亲和度矩阵。理论分析保证了算法获得的最优亲和度矩阵具有良好的聚类效果。同时实验结果表明,非负局部约束低秩子空间算法在运动分割和手写数字聚类任务中,优于现存的几种最先进的聚类算法。但是该算法也