数据的多流形结构分析6

参赛密码（由组委会填写）全全第十二届第十二届““中关村青联杯中关村青联杯””全国研究生全国研究生数学建模竞赛数学建模竞赛学校西安理工大学参赛队号10700027队员姓名1.张岩2.倪超3.毛雯1参赛密码（由组委会填写）第十二届第十二届““中关村青联杯中关村青联杯””全国研究生全国研究生数学建模竞赛数学建模竞赛题目数据的多流形结构分析摘要：在海量数据不断产生的时代，对于数据的处理有了更高的要求，而流形学习已经成为信息科学邻域研究的热点。流形学习就是从高维采样的数据中找到高维空间中的低维流形，以实现维数简约或者数据可视化。针对问题一，由于该组数据的子空间相对独立且维数较高，选用基于低秩表示（LRR）的鲁棒性子空间重构算法建立模型，将这组200个数据分成了两类，具体分类结果见表5.1。同时采用传统PCA+K-means算法对数据分类，与LRR分类结果进行比较，LRR分类结果明显优于传统PCA+K-means方法。针对问题二，四个低维空间中的子空间聚类问题和多流形聚类问题，（a）两条交点不在原点且互相垂直的两条直线，采用谱多流形聚类算法（SMMC）建立数学模型将其分为两类，效果见图5.2(a)。（b）为一个平面和两条直线不满足独立子空间的例子，采用稀疏子空间聚类算法模型（SSC）建立数学模型将其分为三类，效果见图5.3。与谱多流形聚类算法（SMMC）建立模型的分类效果相比更好，说明该算法对非独立子空间的分类能力更强。（c）为两条不相交的曲线，采用谱多流形聚类算法（SMMC）将其分为两类，效果见图5.2(c)，结果分析说明该算法对噪声的鲁棒性也很好。(d)为两条相交的螺旋线，采用谱多流形聚类算法（SMMC）将其分为两类，效果见图5.2(d)。针对问题三，实际应用中的子空间聚类问题，（a）工业测量中的非接触测量方式所用到的特征提取，需要将十字上的点分成两类，采用一维映射中心方法建立数学模型将其分为两类，效果见图5.6，同时采用谱多流形聚类算法建立数学模型（SMMC）将其分为两类，效果见图5.7，与一维映射中心模型结果比2较，后者分类效果较好，但是鲁棒性差，前者效果稍差，但是适用性强，可处理所有同类型问题。（b）视频中的运动目标分割，在基于低秩表示（LRR）的鲁棒性子空间重构算法基础上，提出基于低秩表示与轨迹方向特征的鲁棒性子空间重构算法（LRRTrack）的改进算法，建立数学模型并求解，将运动目标的特征点轨迹分为了3类，效果见图5.8。与LRR算法比较，改进的算法，对背景点与运动目标点误分类问题处理效果更好，效果见图5.11。（c)根据人脸数据的高维特性，采用了稀疏子空间聚类的方法（SSC）将20张人脸图像数据分为2类，见表5-6，同时采用传统PCA+K-means算法分类，并进行比较，结果与SSC分类结果相同，见表5-7。针对问题四，两个实际应用中的多流形聚类问题，（a）需要将圆台上的点云按照圆台的顶、底、侧面分类，采用谱多流形聚类算法（SMMC）建立数学模型并求解，将其点云分为了三类，效果见图5.13。（b）需要将机器工件外部边缘轮廓按照轮廓线中不同的直线和圆弧组合分类，采用谱多流形聚类算法（SMMC）建立模型将其分为3类，结果见图5.14。关键词：流形学习;LRR;SMMC;SSC;LRRTrack;一维映射模型;PCA;3一、问题的重述1.1问题的背景随着信息爆炸时代的到来，数据集增长的更新更快、数据维度更高、非结构化更突出，而技术的落后造成了信息资源的巨大浪费，所以，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图像分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的聚类分析等基本问题，结构分析也格外重要。利用有限高维样本数据进行学习通常会遭遇维数灾难问题，而避免这种问题最常见的方法就是降维。传统的线性子空间方法对非线性结构的数据不能进行有效地处理。高维数据的几何特性使得在低维嵌入流形上建立模型成为可能，予流形方法则是发现高维数据非线性几何结构的有效方法。1.2问题的提出本几何结构分析问题中假设数据分布在多个维数不等的流形上，其特殊情况是数据分布在多个线性子空间上。1.当子空间独立时，子空间聚类问题相对容易。附件一中1.mat中有一组高维数据，它采样于两个独立的子空间。请将该组数据分成两类。2.请处理附件二中四个低维空间中的子空间聚类问题和多流形聚类问题，如图1.1所示。图1.1(a)为两条交点不在原点且互相垂直的两条直线，请将其分为两类；图1.1(b)为一个平面和两条直线，这是一个不满足独立子空间的关系的例子，请将其分为三类。图1.1(c)为两条不相交的二次曲线，请将其分为两类。图1.1(d)为两条相交的螺旋线，请将其分为两类。3.请解决以下三个实际应用中的子空间聚类问题，数据见附件三。（a）受实际条件的制约，在工业测量中往往需要非接触测量的方式，视觉重建是一类重要的非接触测量方法。特征提取是视觉重建的一个关键环节，如图2（a）所示，其中十字便是特征提取环节中处理得到的，十字上的点的位置信息已经提取出来，为了确定十字的中心位置，一个可行的方法是先将十字中的点按照“横”和“竖”分两类。请使用适当的方法将图1.2（a）中十字上的点分成两类。（b）运动分割是将视频中有着不同运动的物体分开，是动态场景的理解和重构中是不可缺少的一步。基于特征点轨迹的方法是重要的一类运动分割方法，该方法首先利用标准的追踪方法提取视频中不同运动物体的特征点轨迹，之后把场景中不同运动对应的不同特征点轨迹分割出来。已经有文献指出同一运动的特征点轨迹在同一个线性流形上。图1.2（b）显示了视频中的一帧，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，请使用适当方法将这些特征点轨迹分成三类。4-101-1-0.500.51-0.8-0.6-0.4-0.200.20.40.60.8(a)(b)(c)(d)图1.1(a)(b)图1.2（c）3c.mat中的数据为两个人在不同光照下的人脸图像共20幅（X变量的每一列为拉成向量的一幅人脸图像），请将这20幅图像分成两类。4.请作答如下两个实际应用中的多流形聚类问题图1.3（a）分别显示了圆台的点云，请将点按照其所在的面分开(即圆台按照圆台的顶、底、侧面分成三类)。图1.3（b）是机器工件外部边缘轮廓的图像，请将轮廓线中不同的直线和圆弧分类，类数自定。5(a)(b)图1.3二、问题的分析2.1问题一的分析已知1.mat所提供的数据是采样于两个独立子空间的一组高维数据，要想直接通过传统的分类方法进行子空间的分类是比较难实现的。因此，根据文献[1]中提出的人脸特征在不同光照下都可以被一个低维子空间近似的原理，考虑对1.mat中的大量数据进行降维，即构造挖掘数据集的低维线性子空间结构，再依据文献[2]提出的运动分割中的特征点数据具有多个混合子空间的结构，判断哪些特征点属于同一子空间，然后通过子空间聚类，将来自同一子空间中的数据归为一类。为此，我们需要从给定的多维子空间集合中抽取其中若干维作为数据样本（向量），以使每个样本聚类到到各自的子空间，并剔除可能的异常值。首先，我们考虑使用传统[3]PCA+K-means算法进行聚类，再根据提出的LRR[4]新的目标函数算法，寻找能够代表数据样本的低秩，在给定样本下作为基的线性组合进行聚类，最后进行比较验证。2.2问题二的分析针对问题二，要求处理第2题数据中四个低微空间中的子空间聚类问题，分析图1.1中给出的四幅图，其中包含了流形良分离和明显交错的情况，文献[5]中表明，传统的谱聚类算法对两性分离的流形结构会给出完全正确的聚类结果，而传统的谱聚类不能很好地分割出交叠的流形结构，从而提出了非对称型规范化谱聚类方法，但是它还是会出现错误信息并严重影响分类结果，因此考虑到需要构造新的相似性矩阵以使得它具有所期望的性质：来自不同流形结构的数据点之间有相对低的相似性权值。基于以上理论，[6]提出了谱多流形聚类算法（SMMC）来实现混合流形聚类，它的基本思想是：从相似性矩阵的角度出发，充分利用流形采样点所内含的自然的局部几何结构信息来辅助构造更合适的相似性矩阵并进而发现正确的流形聚类。62.3问题三的分析1）针对（a）问，受实际条件的制约，在工业测量中往往需要非接触测量的方式，视觉重建是一类重要的非接触测量方法。特征提取是视觉重建的一个关键环节，如图1.2（a）所示，为了确定十字的中心位置，一个可行的方法是先将十字中的点按照“横”和“竖”分两类。根据题目所提供的数据3a.mat，为一个高维的二维点集，横竖两条线可以理解为他们分属于不同的流形，那么问题就转化为混合流形的分类问题。因此，我们采用谱多流形聚类算法（SMMC），将两个混合流形的数据点分为两类，尤其是交叉部分的点能够合理的分属所属的流形空间。2）针对（b）问，运动分割是将视频中有着不同运动的物体分开，是动态场景的理解和重构中不可缺少的一步。基于特征点轨迹的方法是重要的一类运动分割方法，根据场景中不同运动对用不同的特征点轨迹分割出来。由于同一运动的特征点轨迹在同一个线性流形上，那么就可以将问题转化为多线性流形分类的问题。如图1.2（b）所示，是视频中的一帧，有三个不同的运动物体，题目所提供的数据3b.mat中保存了三个不同运动的特征点轨迹的数据，我们采用基于低秩表示（LRR）的鲁棒性子空间重构算法，就可以将三个在分别属于不同的线性子空间的运动物体分开，从而问题得以解决。3）针对（c）问所提供的数据3c.mat,数据矩阵的每一个列向量表示一副人脸图像，它是将一副人脸图像的灰度矩阵拉成了一个高维列向量，其维度达到了2016。在如此高维的数据上进行分类处理难度很大，所以这里想到了稀疏表示[7]（SR）的思想。已经证明了在不同的光照或表情变换条件下的人脸图像可以用一个低维子空间来近似,取自多个人的一组人脸图像可以看作是9维线性子空间的并[1],从而人脸识别问题等价于子空间聚类问题.。根据稀疏表示可以将人脸图像的高维列向量进行降维，但并不会丢失特征信息，再对降维后的数据进行分类，这样降大大减少计算的复杂度。针对降维后数据的分类，由于只有20个人脸数据，需要将这20个人脸数据分为两类，那么谱聚类是一种很好的解决方法。通过以上的分析，那么[8]理论上可以将问题很好的解决。2.4问题四的分析1）针对（a）题，如图1.3（a）所示，分别显示了圆台的点云，要求将数据点所在的面分开（即按照圆台的顶、底、侧面分成三类）。可以将圆台的面理解为流形，那么数据分别采样于圆台的顶，底和侧面不同流形，问题就转化为将数据点所在的流形进行分类，即数据的混合多流形问题。由于混合流形不全是子空间的情况，数据往往具有更复杂的结构，分析这种数据具有更大的挑战性。基于谱聚类的方法仍然是处理该类问题的流行方法。因此，可以采用谱多流形聚类算法（SMMC）。2）针对（b）题，如图1.3（b）所示，是机器工件外部边缘轮廓的图像，题目要求将机器工件外部边缘轮廓的图像根据轮廓线中不同的直线和圆弧的分类，类数自定，那么此问题属于多流形聚类的问题。针对此类问题，采用谱多流形聚类算法（SMMC）是能够解决的。然后根据直线的长短，以及圆弧的长短和圆的半径分类，可以将轮廓线分为5类。7三、模型的假设（1）假设数据的结构为混合多流形更具有一般性；（2）假设数据分布在多个维数不等的流形上，其特殊情况是数据分布在多个线性子空间上；（3）假设数据均匀采样于一个高维欧式空间中的低维流形；（4）假设在谱多流形聚类算法中，每个数据点的局部切空间是已知的。（5）假设在稀疏子空间聚类算法中，稀疏奇异值矩阵也是稀疏的，噪声的误差可用F范数进行衡量；四、符号说明符号符号说明Z对矩阵Z的元素取绝对值得到的矩阵S第个子空间ix，iy输入数据矩阵jc第j个类的类中心W