数据的多流形结构分析7

第十二届第十二届““中关村青联杯中关村青联杯””全国研究生全国研究生数学建模竞赛数学建模竞赛学校重庆理工大学参赛队号11660017队员姓名1.冉小华2.胡猛3.陈华良第十二届第十二届““中关村青联杯中关村青联杯””全国研究生全国研究生数学建模竞赛数学建模竞赛题目数据的多流形结构分析针对多流形结构的聚类问题，本文提出稀疏子空间聚类模型以及改进优化算法对常规的多流形结构数据进行聚类，并用谱多流形聚类模型（SMMC）对混合流形结构数据进行聚类。问题一：需将200个高维数据分为两类，本文首先建立稀疏子空间聚类模型，在此运用交替方向法求出解稀疏系数，然后利用高维数据的稀疏表示系数构造相似度矩阵，最后利用谱聚类方法，得到数据的聚类结果：1-40和141-200之间的样本点划分到一类，41-140之间的样本点为另一类。问题二：针对子问题(a)两条交点不在原点且相互垂直的两条直线进行分类，我们应用稀疏子空间聚类模型并得到较好的分类结果；(b)一个平面和两条直线分成三类和(c)两条不相交的二次曲线分成两类情形，本文建立拉普拉斯特征映射模型，利用拉普拉斯嵌入描述数据的局部几何结构关系进行聚类，最终的分类结果都比较理想；(d)两条相交的螺旋线分成两类，本文采用谱多流形聚类方法进行分类。首先从整个数据中分离出不同的连通或可分离子集，然后进一步将相交的子集分割为相交区域和非相交区域,最后用谱多流形聚类方法得聚类结果比较准确。问题三：针对子问题(a)对十字上的点位置信息进行分类，本文运用谱多流形聚类方法进行聚类，得出具有较好地分类效果；(b)对已提取特征点后的轨迹进行运动分割。在此对稀疏子空间聚类模型中的交替方向法进行改进。调整交替方向法的惩罚参数，将稀疏子空间聚类应用到视频运动分割中，从而得到特征点轨迹的分类结果：1-138之间的特征点划为第2类，139-214之间的特征点划为第3类，215-297之间的特征点划为第1类；(c)将在不同光照下的人脸图形分成两类，本文同样稀疏子空间聚类模型中的交替方向法进行改进，研究线性化的自适应线性交替方向法。同时把稀疏子空间聚类应用到人脸分类中进行分析，得出分类结果：1-5幅图和11-15幅图都被划分到第1类，而6-10幅图和16-20幅图。被划分到第2类,聚类准确率100%。问题四：针对子问题(a)对圆台的点分成三类，由于在运用原始数据分类过程中发现内存溢出，所以本文首先对原始数据采样，然后对采样点进行谱多流形聚类，最后运用邻近分类算法对剩下的数据进行分类，得到理想的分类结果；(b)问题，由于机器工件外部边缘轮廓图较为复杂，而且噪音点较多，本文建立谱多流形聚类模型进行分类，最后分别将其划分为二、三、四、五类，实验结果表面可以有效地将轮廓线中不同的直线和圆弧区分开。关键词：稀疏子空间聚类；交替方向法；拉普拉斯特征映射；谱多流形聚类1一、问题重述我们已经进入了一个信息爆炸的时代，海量的数据不断产生，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。大量的数据降维方法被用来挖掘数据集的低维线性子空间结构，这类方法假设数据集采样于一个线性的欧氏空间。针对单一子空间结构假设的后续讨论主要是两个方面，首先是从线性到非线性的扩展，主要的代表性工作包括流形（流形是局部具有欧氏空间性质的空间，欧氏空间就是流形最简单的实例）学习等。其次是流形或子空间从一个到多个的扩展，即假设数据集采样于多个欧氏空间的混合。子空间聚类（是将数据按某种方式分类到其所属的子空间的过程。通过子空间聚类，可以将来自同一子空间中的数据归为一类，由同类数据又可以提取对应子空间的相关性质。本几何结构分析问题中假设数据分布在多个维数不等的流形上，其特殊情况是数据分布在多个线性子空间上。请按照文献中的方法或以文献中的方法为基础创新新的方法完成以下问题：1.当子空间独立时，子空间聚类问题相对容易。附件一中1.mat中有一组高维数据，它采样于两个独立的子空间。请将该组数据分成两类。2.处理附件二中四个低维空间中的子空间聚类问题和多流形聚类问题：（1）将两条交点不在原点且互相垂直的两条直线，请将其分为两类；（2)对不满足独立子空间的关系时，将一个平面和两条直线，请将其分为三类；(3)将两条不相交的二次曲线划分为两类。(4)将两条相交的螺旋线划分为两类。3.解决以下三个实际应用中的子空间聚类问题。（a）受实际条件的制约，在工业测量中往往需要非接触测量的方式，视觉重建是一类重要的非接触测量方法。特征提取是视觉重建的一个关键环节，如（a）所示，其中十字便是特征提取环节中处理得到的，十字上的点的位置信息已经提取出来，为了确定十字的中心位置，一个可行的方法是先将十字中的点按照“横”和“竖”分两类。请使用适当的方法将（a）中十字上的点分成两类。（b）运动分割是将视频中有着不同运动的物体分开，是动态场景的理解和重构中是不可缺少的一步。基于特征点轨迹的方法是重要的一类运动分割方法，该方法首先利用标准的追踪方法提取视频中不同运动物体的特征点轨迹，之后把场景中不同运动对应的不同特征点轨迹分割出来。已经有文献指出同一运动的特征点轨迹在同一个线性流形上。（b）显示了视频中的一帧，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，请使用适当方法将这些特征点轨迹分成三类。（c）3c.mat中的数据为两个人在不同光照下的人脸图像共20幅（X变量的每一列为拉成向量的一幅人脸图像），请将这20幅图像分成两类。4.作答如下两个实际应用中的多流形聚类问题2实际应用一:对圆台的点云，请将点按照其所在的面分开(即圆台按照圆台的顶、底、侧面分成三类)。实际应用二：机器工件外部边缘轮廓的图像，请将轮廓线中不同的直线和圆弧分类，类数自定。二、基本假设1、采样密度稀疏时，所寻找的局部邻域结构时产生的偏差在可控范围之内。2、在子空间分割中，假设高维数据分布于多个低维子空间的并。3、欧式空间的子集是一个凸集。4、假设数据分布在多个维数不等的流形上。5、当数据的低维特征嵌入在高维的特征空间时,同处在小的局部邻域内样本数据会具有相似的特性,即类别标签属性也是相同。三、符号说明符号含义C样本iy基于数据集Y的稀疏0x向量x的0l-（伪）范数，x中非零元个数Fx矩阵X的1l-范数，jijiFXx2A表示引入的辅助矩阵NNRAz表示平衡两项的权重惩罚因子IN阶单位矩阵表示NNR拉格朗日乘子矩阵W由数据集构造的相似矩阵DDNNW对角矩阵L图拉普拉斯矩阵，-1/21/2LI-DWD表示标准内积()Knnx表示x的K个近邻数据点m表示噪声3四、问题1分析及模型建立与求解4.1问题分析近年来，由于高维数据在很多领域普遍存在，谱聚类的方法已成为高维数据聚类的主流方法。由于稀疏子空间聚类是实现高维数据集聚类的一种有效途径，在此本文将稀疏子空间聚类的方法用于解决问题一。建模思路如下：首先建立稀疏子空间聚类模型，在此运用交替方向法求出解稀疏系数，然后根据表示系数矩阵构造相似度矩阵，最后利用谱聚类方法，获得数据聚类的结果。4.2模型的建立与求解4.2.1稀疏子空间聚类模型稀疏子空间聚类是一种基于稀疏表示的子空间聚类算法[1-3]。假设数据集为12,,,MNNYyyyR，对于每个数据样本而言，直接使用原始数据集作为冗余字典，得每个数据点的稀疏表示ic：20,min2zFCZCZ（4-1）..stYYCZ0iiC1,2,iN上式优化式是非凸的并且是一个NP-hard问题，常使用凸松弛方式（用1范数替代原有的0范数），将上述非凸优化转变如下：21,min2zFCZCZ（4-2）..stYYCZ0iiC1,2,iN求解上式得到每个数据点的稀疏表示，构造相似度矩阵12W,,,NNN。为使W对称，定义如下：TWCC（4-3）从另一方面说，节点i和节点j之间边的权重等于ijjicc。这里W由n个独立子空间生成，每个样本iy可以由属于同一个子空间的其他样本进行稀疏重构，属于不同子空间的样本的稀疏表示系数为零。在相似度矩阵W上用谱聚类算法[4]进行划分。4算法1谱聚类算法输入：n个线性子空间1{}niiS组成的数据点1{}Niiy。输出：原始数据对应的聚类结果。Step1构造基于数据集Y的相似矩阵W；Step2计算相似矩阵W的Laplacian矩阵(L)；Step3求出L的前n个特征值,以及其对应的特征向量1{}kiiuStep4把k个特征（列）向量排列在一起组成一个Nk的矩阵Step5把生产矩阵每一行看做k维空间中的一个向量，利用Kmeans将的行向量分组为n个聚类。4.2.2交替方向法求解算法稀疏子空间模型一般传统常用内点算法CVX优化工具包求解，由于交替算法常常用于具有可分离结构的目标函数凸优化问题。故在此本文用交替方向法[4]对其进行求解。首先根据（4-2）的等式约束。我们可以消除目标函数的Z,并引入NNAR，那么公式（4-2）可以重写成如下形式：21,min2zFCZCZ（4-4）..stAC0iiC1,2,iN引进矩阵RNN拉格朗日乘子，我们可以得到增广拉格朗日函数：221(,,),22zFFLCACYYAACAC（4-5）通过固定,kkC，对L关于A求导可得：(1)(1)0TkkkkzYYYAAC（4-6）化简可得：(1)TkTkkzzYYIAYYC（4-7）一般情况下，TYY为对角阵时，可以得到(1)kA的封闭解：1(1)kTTkkzzAYYIYYC（4-8）固定(1),kkA，对L关于C求导得到1kC，可以得到其封闭解：(1)()kCJdiagJ（4-9）5其中(1)1kkJTA这里()T是收缩阈值操作符，其可以定义成如下形式：,(),0,xxTxxxothers（4-10）这里的x可以是数字，向量或者一个矩阵。当得到11(,)kkCA时，可以更新拉格朗日乘子，如下：111()kkkkAC（4-11）这三步不断重复执行直到收敛完成或达到设定的迭代次数。迭代停止标准为()()()(1)A,kkkkCAA。其中表示容错率，一般取3410,10下面算法展示了交替方向法执行式子（4-2）的过程。算法2稀疏求解的交替方向算法输入：待分类的数据集Y输出：最优稀疏系数矩阵CkC初始化：0k,)0(C,)0(A,)0(为0。while()()A,kkC()(1)kkAA做下面操作：Step1通过求解下列等式更新1Ak：(1)TkTkkzzYYIAYYCStep2更新(1)kC如下：(1)()kCJdiagJ，其中(1)1kkJTA；Step3更新1k如何：111()kkkkAC；Step41kk；endwhile4.2.3实验结果与分析考虑嵌入构造在100维空间中的两个独立空间的子空间21iiS，在子空间里每一个样本点都可以由其所在空间里的点线性表示。在此运用上述模型和算法将1.mat中高维数据进行分类。实验环境为：Windows7系统和Matlab2012b，CPU为i3-2310MCPU和2GB内存。通过多实验调节参数，现做如下设置：最大迭代次数为300，2n，20，1.2z，0.0001