2015年数学建模试题B结果

1、参赛密码 （由组委会填写）全第十二届“中关村青联杯”全国研究生数学建模竞赛学 校*参赛队号*队员姓名1.*2.*3.*参赛密码 （由组委会填写） 第十二届“中关村青联杯”全国研究生数学建模竞赛题 目 数据的多流形结构分析摘 要：本文按照题目要求，建立局部稀疏约束特性模型，解决了独立子空间局内问题；建立基于差分演化算法的加强型的软子空间聚类(essc)模型和稀疏子空间聚类(ssc)算法模型，解决了低维子空间聚类问题和多流形聚类问题；建立改进稀疏子空间聚类算法模型，解决了实际应用中的子空间聚类问题；建立谱多流形聚类(smmc)模型解决了实际应用中的多流行聚类问题。针对问题一：先采用局部线性嵌入(l

2、le)算法对题目所给的高维数据进行降维处理，再建立局部稀疏约束特性模型，采用k-means算法对数据进行聚类，最终将序号1-40、141-200的数据点聚一类，序号41-140的数据点聚为另一类，类别比例1:1，样本的类别标签见表5-2。针对问题二：对于两条不相交的二次曲线分类问题，采用k-means算法对其进行聚类，聚类结果如正文图6-4；对于两条交点不在原点且相互垂直的直线和两条相交螺旋线的分类问题，建立基于差分演化算法的加强型的软子空间聚类模型，采用加强型的软子空间聚类算法求解，聚类结果如正文图6-2和图6-3；对于一个平面和两条直线图形分类问题，建立稀疏子空间聚类算法模型，并采用交替方

3、向解法求解，聚类结果如正文图6-5。针对问题三：引入稀疏奇异值矩阵和噪声矩阵，建立了改进的稀疏子空间聚类算法模型进行聚类，对于将十字中的点按照“横”和“竖”分类的聚类结果见正文图(7-1)。对于运动特征点提取问题，聚类得到三类特征点，样本类别标签如正文表7-1，各类别序号分别为：1-138，139-214，215-297，对应于图中小轿车，公交车，树及房屋；并采用基于光流场矢量图的方法验证了运动特征点聚类效果，根据光流场矢量图的趋势，进一步分析出小轿车和摄像者在此序列帧图像中处于运动状态，公交车处于静止状态。对两个人在不同光照下的人脸图像分类问题，聚类得出样本的类别标签为：2222211111

4、2222211111相同的数字标签表示同一个人；采用基于图像复原的方法对人脸识别效果进行验证，结果准确，说明了模型具有可靠性，算法具有一般性。针对问题四：对于两个实际应用中的多流行聚类问题，建立了谱多流形聚类模型，对圆台点云和机器工件外部边缘轮廓线进行聚类。对于圆台点云：模型按照题目要求清晰地将其分为顶、底、侧面三类，结果见正文图8-1；对于机器工件外部边缘轮廓线：按照不同的直线和圆弧几何结构，将其分为四类，具体分类结果见正文图8-2。 关键词： 多流形结构；k-means算法；差分演化；光流场矢量图1.问题重述1.1 问题提出的背景我们已经进入了一个信息爆炸的时代，海量的数据不断产生，迫切需

5、要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础，已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。1.2 需要解决的问题本几何结构分析问题中假设数据分布在多个维数不等的流形上，其特殊情况是数据分布在多个线性子空间上。请按照文献中的方法或以文献中的方法为基础创新新的方法完成以下问题， 创新部分一定要讲清思路，

6、要具有一般性(例如不仅适应低维数据也适应高维数据)。回答方式：第1题，第3题的b与c请制作一个表格输出样本的类别标签，每行20个，其余题目请将分类结果画出：问题一：问题一为子空间独立时，子空间聚类问题，题目要求将附件一1.mat中采样于两个独立的子空间的一组高维数据分成两类。问题二：请处理附件二中四个低维空间中的子空间聚类问题和多流形聚类问题，如图1-1所示：1) 将图1-1(a)中两条交点不在原点且互相垂直的两条直线分为两类；2) 将图1-1(b)中一个平面和两条直线分为三类；3) 将图1-1(c)中两条不相交的二次曲线分为两类；4) 将图1-1(d)中两条相交的螺旋线分为两类。(a) (b

7、)(c) (d)图1- 1问题三：解决以下三个实际应用中的子空间聚类问题，数据见附件三：1) 使用适当的方法将图1-2(a)中十字上的点分成两类；2) 图1-2(b)显示了视频中的一帧，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，请使用适当方法将这些特征点轨迹分成三类；3) 3c.mat中的数据为两个人在不同光照下的人脸图像共20幅(x变量的每一列为拉成向量的一幅人脸图像)，请将这20幅图像分成两类。(a) (b)图1- 2问题四：请作答如下两个实际应用中的多流形聚类问题:1) 图1-3(a)分别显示了圆台的点云，请将点按照其所在的面分开(即圆台按照圆台的顶、底、侧面分成三

8、类)；2) 图1-3(b)是机器工件外部边缘轮廓的图像，请将轮廓线中不同的直线和圆弧分类，类数自定。 (a) (b)图1- 32.模型假设与符号说明2.1 模型假设假设1：对高维数据降维时，数据可能失真的部分对分析的影响不计； 假设2：数据集的特征提取过程中，不存在忽略部分；假设3：题目中提供的数据集存在去噪的处理；2.2 符号说明符号说 明计算权值矩阵稀疏表示的系数向量v初始聚类中心向量c样本基于数据集y的稀疏表示每个数据点的稀疏表示类中数据对象的均值p类中的空间点表示范数表示范数w相似度矩阵惩罚因子表示标准内积是收缩阈值操作符拉格朗日乘子l增广拉格朗日函数a辅助矩阵e稀疏奇异值矩阵z噪声矩

9、阵局部化模型数流形维数注：其余未注符号在使用时具体说明.3.问题分析3.1 问题一的分析问题一要求我们将采样于两个独立子空间的高维数组分为两类，当子空间独立时，子空间的聚类问题相对比较容易，根据稀疏表示的基本思想：高维信号可完全或近似的由少量的一组原子数据对象线性组合表示，其可以用来支撑高维数据对象的相似对象选择，相应的线性组合系数可以视为相似度。因此，本文考虑利用稀疏表示实现高维缺失数据填补中的数据对象选择及相似度确定过程，将传统的稀疏表示方法进行扩展，针对给定的目标数据对象，学习同时具有稀疏性、局部结构特征及光滑性的表示系数，在自动选择数据对象的同时，保留局部结构特征并避免过拟合问题。针对

10、这一问题的具体求解思路为：首先要采用lle算法对高维数据进行降维，然后建立基于高维数据的局部稀疏约束特性模型表示该数组，由于该独立子空间聚类问题比较简单，我们打算采用k-means算法以欧氏距离作为相似性测度来对该问题进行分类。3.2 问题二的分析针对题目中涉及的四个低维空间中的子空间聚类和多流形聚类问题，考虑到题目中简单介绍的稀疏子空间聚类和低秩子空间聚类的方法，同时结合当前使用的一些聚类方法及其改进型，结合题目中数据的特点，本文打算建立对应的聚类模型来求解题目中的这些数据的聚类问题。首先，从题目所给的要求进行分类的四张图片的直观特征来看，我们可以将四张图形归按照求解难易程度分为三类：图1-

11、1(c)的图形为两条不相交的二次曲线，特征比较容易区分，求解起来会比较容易，单独归为一类；图1-1(a)为两条交点不在原点且相互垂直的两条直线，图1-1(d)两条相交螺旋线，要分类的特征存在交叉，分类的难度较图1-1(c)增大，可以将这两个待分类的图形归为第二类；图1-1(b)由于所给图形为一个平面和两条直线，是一个不满足独立子空间关系的例子，求解比较复杂，归为第三类。对于以上三类图形的分类问题，通过查阅相关文献资料，发现目前为止，还尚未找到一种统一的模型可以同时解决这三类问题的分类求解，因此我们针对不同类型的分类问题，准备采用不同的聚类模型来解决相应的图形分类。对于图1-1(c)由于特征比较

12、容易区分，跟问题一的求解有相似之处，因此我们采用问题一中建立的聚类模型对其进行分类；对于题图1-1(a)和图1-1(d)本文准备建立基于差分演化算法的essc模型分别对其分类；对于题图1-1(b)由于所给图形不满足独立子空间关系，求解比较复杂，因此本文打算建立稀疏子空间聚类算法(ssc)模型，并采用交替方向解法求解该分类问题。3.3 问题三的分析问题三要解决的是实际应用中子空间的聚类问题，其中图1-2(a)主要考察的是视觉重建在工业测量中非接触测量方法的运用，要解决的关键问题是特征提取；图1-2(b)考察的是采用运动分割，利用标准的追踪方法提取视频中不同运动物体的特征点轨迹，把场景中不同运动对

13、应的不同特征点轨迹分割出来，从而将视频一帧中有着不同运动物体分开问题；图1-2(c)则需要将两个人在不同光照下的人脸图像进行分类的问题。针对图1-2(a)的求解，本文打算采用问题二中的建立的稀疏子空间聚类算法(ssc)模型求解，对于图1-2(b) 运动图像的分割和1-2(c)人脸识别分类的问题，由于存在在噪声和稀疏奇异值，本文准备通过引入噪声矩阵和稀疏奇异值矩阵改进ssc算法模型，从而解决相应的分类问题。3.4 问题四的分析问题四要解决的是实际应用中的多流行聚类问题，对于图1-3(a)给出的圆台的点云，题目要求我们将点按照所在的面分开，也就是说，我们要根据圆台的顶面、底面和侧面数据点的特征特性

14、将所给的点云分为顶面、底面和侧面三类，归结为面的分类问题；图1-3(b)所给的图形为机器工件的外部边缘轮廓的图像，按照题目的要求，我们需根据轮廓线中不同的直线和圆弧分类，具体的分类数可以自己设定分类标准，并按照所给的标准进行相应的类别划分，归结为线的分类问题。考虑到实际问题，对象所处的情况可能包含高维与低维或线性与非线性、良分离的非线性结构或相互交叠的非线性结构等特点，面对实际的理论问题要求建立的求解模型兼顾这些常规特点，这就需要进行混合流形聚类，混合流形聚类能够确定潜在流形的聚类数目及其本征维数；混合流形聚类还能够将给定的数据采样划分到其所属的潜在流形，这就非常符合这类复杂的数据集。针对该题

15、中的圆台点云按面分类和机器工件外部边缘轮廓图像按轮廓线分类问题，结合上面的分析，同时考虑模型的通用性，我们建立基于谱多流形聚类方法的混合流行聚类模型来求解该题。4.数据的处理与分析4.1 数据的编译处理 (1)编译题附件一中1.mat的高维数据，得到一个的数据矩阵，表明该数据共200个数据点，每个数据点有100维，摘取该高维数据的部分数据信息如表4-1，详细信息见附件1：表4-1 附件1.mat数据信息维度1219920010.1686240.095744-0.22365-0.0583420.1209940.1038470.0019110.055234100-0.129070.013696-0

16、.30917-0.08746(2)编译题附件二中的四个低维数据，分别得到、和的数据矩阵，表明每组数据的数据点和维度，2b.mat中的数据有3维，分别摘取每组数据的前三个和最后三个数据点信息如表4-2，详细信息见附件1：表4-2 附件2.mat数据信息维度1232542552a.mat1-0.38932-0.678391.5526951.8270460.44568820.7404553.017583-0.51482-0.740571.2971252b.mat10000.0811770.75408720.2472980.6621810.5530680.55883-0.2643930.2472980

17、.6621810.51228900.0577172c.mat10.2166070.4427970.048850.204726-0.1022520.1407560.5882070.007159-0.05809-0.089542d.mat10.7601410.011508-0.734050.085275-1.5105920.113927-0.03336-0.06127-0.147190.470211(3)同理，可分别将题附件三和题附件四中的*.mat文件分别转换为对应的矩阵信息，具体转换结果见附件1，本文在此作统一处理方法说明，后文将不赘述该数据处理过程。4.2 数据的可视化处理 针对题目中的第四

18、小问提供的*.mat文件和给出的图片，我们对相关数据进行了比较清晰的图像还原可视化处理，结果如下。图2- 1 数据的可视化图形重构5.问题一：独立子空间聚类模型5.1 模型的准备5.1.1 基于lle算法数据降维lle算法是基于几何直觉的，即把高维空间数据点按维数映射到低维嵌入空间，即。具体的降维步骤为： 1)计算或寻找数据点的相邻数据点设原始数据由n维d的实值向量组成，记做，由于数据由真正光滑的多面体取样而来，故每个数据点和它的邻居点位于或近似位于该多面体的局部线性平面上。这样就能通过线性组合系数刻画出局部平面的几何特征。在lle中，通过欧氏距离的方法可找到每个数据点的k个最近邻居数据点。每

19、个数据点的重构错误用成本函数来衡量： (5-1)2)计算权值矩阵并通过与邻居数据点构造数据点权值说明第j个数据点对重构第i个数据点所做的贡献。为了得到合适的权值，在下面两个条件下，对成本函数进行最小值计算。条件一，每个数据点来构造，并且当某个数据点不属于所重构数据点的邻近数据点时；条件二，权值矩阵每行的所有元素之和等于1，即。最优权值将通过计算其最小平方得到。在限制条件下，通过最小化重构错误得到的最优权值遵循如下对称特性，即对于特定的数据点，在其本身和邻居数据点有旋转、缩放、平移操作时将保持原有性质不变。旋转和缩放不变性从式(5-1)得到，而平移的不变性则由条件二保证。由于这种对称性，重构权值

20、仅能够刻画每一个邻居数据点的几何属性，而不是依据特定的参考框架的属性。假定数据位于或近乎位于一个维数的光滑的非线性多面体上，为了得到好的近似，存在一个线性映射(包含平移、旋转、缩放)，这个映射能映射该多面体上每个邻近数据点的高维坐标值到一个单一的内部坐标系统(也即多面体本质属性所确定的内部坐标系统)。故重构权值能反映旋转不变的内在几何属性，而重构原始d维空间的权值也能用于在低维d空间重构对应的数据点。3)通过权值矩阵计算低维向量基于上述思想，高维观察值被映射为低维向量，正好反映了该多面体的真正维数。d维向量通过最小化成本函数得到： (5-2)该成本函数是基于局部线性重构错误的。上式中的嵌入成本

21、函数是向量的一个二次方的形式，为简化，可通过求解稀疏矩阵的特征向量求解最小值。它的最下面的d个非零特征向量提供了一组有序的以原点为中心的正交坐标系统。由于该算法只有一个参数，即每个数据点的邻居点数k，一旦k值选定，通过线性代数就可以计算出最优权值和每个数据点对应的低维空间的数据点。5.1.2 lle算法降维结果通过采用lle算法把高维空间数据点按维数映射到低维嵌入空间，将题目所给的的数据矩阵降维，本文考虑了降维至二维和三维两种两种情况，降维结果如图5-1所示，其中图5-1(a)为降至二维的结果，图5-1(b)为降至三维的结果。(a)二维降维结果 (b)三维降维结果图5- 1不同降维维度的降维结

22、果对比列举降维结果如表5-1所示，取前3组和最后2组的数据点表示如下，详细降维结果见附件1：表5- 1 基于lle算法数据点的降维结果维度12319920010.8926210.6832530.8024510.9310050.9487632-0.99264-0.70606-0.82528-1.00529-0.988953-0.10596-0.01486-0.21007-0.221180.031995.2 局部稀疏约束特性模型的建立5.2.1 局部稀疏约束模型本问提出的局部约束稀疏表示(lcsr)对传统的稀疏表示方法进行扩展，针对给定的高维目标数据对象，学习同时具有稀疏性、局部结构特征及光滑性的

23、表示系数，提出的lcsr能在自动选择数据对象的同时，保留局部结构特征并避免过拟合问题。1) 目标函数已知一个过完备字典，目标数据对象y可以表示为在字典上的线性组合，表示系数向量记为。lscr同时结合稀疏和局部约束，在寻找稀疏表示求解系数时考虑过完备字典中每个数据对象与目标数据对象的距离，将距离惩罚约束的范数正则化项和范数正则化项引入标准的稀疏表示框架，得到如下的优化求解目标函数： (5-3)其中，表示稀疏表示系数向量；和为正则化约束参数，分别给定系数向量和光滑性在目标函数中的权重。2) 求解优化已知过完备字典和目标数据对象(y，b)及距离向量d，参数，公式(5-3)可以按如下的步骤转化： 通过

24、下式定义人工扩展数据集(y，b) (5-4) (5-5) (5-6)其中表示p维列向量，i表示p维单位矩阵。假设，则优化求解目标函数模型重写为： (5-7)综上所述，建立的优化求解目标函数模型为：5.2.2 求解流程图图5- 2 独立子空间聚类模型求解流程图5.3 模型的求解5.3.1 k-means算法原理k-means算法以欧式距离作为相似性测度，求对应某一初始聚类中心向量最优分类，使得评价指标值最小。采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为：。其中是类中数据对象的均值，p是类中的空间点。5.3.2 k-means算法的求解思路及步骤算法首先随机选取k个点作为初始聚

25、类中心，然后计算各个样本到聚类中心的距离，把样本归到离它最近的那个聚类中心所在的类；对调整后的新类计算新的聚类中心，如果相邻两次的聚类中心没有任何变化，样本调整结束，聚类准则函数收敛。该算法属于动态聚类法(也称逐步聚类法)，其迭代过程采用按批修改方法，即在每次迭代中都要考察每个样本的分类是否正确，若不正确就要调整，待所有样本均调整完后，再修改聚类中心，进入下一次迭代。若在一次迭代算法中所有样本被正确分类，则不用调整，聚类中心也不会有任何变化，表明已经收敛，算法结束。该算法的具体实施步骤如下：1) 给定大小为n的数据集，另i=1，选取k个初始聚类中心；2) 计算每个数据对象与聚类中心的距离 如果

26、满足，则；3) 计算误差平方和准则函数：4) 若则算法结束；否则，计算k个新的聚类中心，返回步骤2)。5.4 求解结果 为了考察不同的降维维度对结果的影响，我们分别做出了将为二维数组和降为三维数组的情况时，数据点的分类情况如图5-3所示，不用的类别用不同的颜色加以区分，其中图5-3(a)为降至二维的聚类结果，图5-3(b)为降至三维的聚类结果。(a)二维聚类结果 (b)三维聚类结果图5- 3不同降维维度的聚类结果对比首先通过采用lle算法将原始的的高维数据点降维至，然后建立基于高维数据得局部稀疏约束特性模型，采用k-means算法聚类稀疏表示的高维特征数据，得到如表5-2所示的聚类结果，表中第

27、一行表示1-20的数据点分类，后面的依次为21-200的数据点分类特征，0为一类，1表示另一类：表5- 2 问题一样本类别标签222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112222222222222222222222222222222222222222222222222222222222225.5 结果分析从图5-3可知，无论是降维至二维还是降维至三维，我们都能很

28、好的将这200个数据点分为两类，二维的分类结果从视觉上更易区分，三维的分类结果从空间上看更加形象和具体。从表5-2的求解结果可知，我们将题目所给的200个数据点共分成了两类，表中的0表示为一类，1表示为另一类，也就是说，我们按照建立的基于高维数据的局部稀疏约束独立子空间聚类模型，我们将序号1-40和141-200的数据点分为一类，序号41-140的数据点归为另一类，各类的比例分别占总体的50%。6.问题二：低维子空间和多流形聚类模型6.1模型的分析6.1.1 软子空间聚类子空间聚类方法分为软字空间聚类方法和硬子空间聚类方法，应用于数据集处理的大多偏向于软子空间聚类方法。常规的软字空间聚类方法中

29、的划分矩阵和权值矩阵的容易受到更新公式中的参数影响，从而导致类内相似性变化很大，同时导致类内距离作为类内相似性的度量被广泛使用，忽略了类间相似性的作用。为详细了解类间相似性的产生原理及不让这一元素被忽略，同时避免外在参数对更新公式的影响，重新引入新的参数提升了软子空间聚类方法的性能，对于求解低维子空间数据集聚类具有很好的效果。6.1.2 稀疏子空间聚类：稀疏子空间聚类方法，是对子空间表示系数进行稀疏约束的一类子空间聚类方法。子空间聚类的最终结果是将同一子空间的数据归为一类。在子空间相互独立的情况下，属于某一子空间的数据只由这个子空间的基的线性组合生成，而在其他子空间中的表示系数为零。这样高维数

30、据的表示系数就具有稀疏的特性。同一子空间中的数据，因为都仅在这一子空间中有非零的表示系数，表现为相同的稀疏特性，通过对表示系数稀疏约束的求解，突出了数据表示系数的这种稀疏特性，进而为数据的正确聚类提供支持。6.2 交叉特征聚类模型的建立6.2.1 essc算法模型在以往的软子空间聚类算法中，类内距离作为类内相似性的度量被广泛运用，而类间相似性却一直被忽略，本文采用的增强的软子空间聚类(enhanced soft subspace clustering，essc)算法，在熵加权k-均值算法的基础上，结合用于度量类间相似性的加权类间分离度，进一步提高了软子空间聚类算法的性能。建立的基于差分演化算法

31、的essc模型定义如下：目标函数： 约束条件：其中，。6.2.2 essc算法更新公式基于局部搜索策略的软子空间聚类算法首先提出一个加权目标函数，然后采用基于梯度下降的技术迭代地优化目标值函数值，最终收敛于局部最优解，essc算法通过引入类间相似性，结合类内相似性，权值的计算与聚类中心矩阵紧密结合，进一步提高了软子空间聚类算法的性能，更新公式如下： (6-1) (6-2) (6-3) (6-4) (6-5)6.2.3 essc算法流程图图6- 1 essc算法求解流程图6.3 不满足独立子空间聚类模型的建立6.3.1 稀疏子空间聚类模型稀疏子空间聚类是一种基于稀疏表示的子空间聚类算法。假设数据

32、集，对于每个数据样本而言，直接使用原始数据集作为冗余字典，得每个数据点的稀疏表示： (6-6) (6-7)其中，c是样本基于数据集y的稀疏表示，表示范数，即表示矩阵中非零元个数。为范数。上式优化式是非凸的并且是一个np-hard问题，常使用凸松弛方式(用范数代替原有的范数)，将上述非凸优化转变如下： (6-8) (6-9)求解上式得到每个数据点的稀疏表示，构造相似度矩阵 。为了是w对称，定义如下： (6-10)w由n个独立子空间生成，每个样本可以由属于同一个自己空间的其它样本进行稀疏重构，属于不同子空间的样本稀疏表示系数为0。综上所述，建立的稀疏子空间聚类模型为：6.3.2 交替方向法求解算法

33、稀疏子空间模型一般传统常用内点算法cvx优化工具包求解，本文用交替方向对其进行求解。首先根据式(6-9)的等式约束，参数用来平衡两项的权重，消除目标函数的z，并引入辅助矩阵，将式(6-8)和(6-9)重写成如下形式： (6-11) (6-12)引进矩阵拉格朗日乘子，可以得到增广拉格朗日函数： (6-13)其中，为惩罚因子，表示标准内积。通过固定，对l关于a求导可得： (6-14)化简可得： (6-15)一般情况下，为对角阵时，可以得到的封闭解： (6-16)固定，对l关于c求导得到，可以得到其封闭解： (6-17) (6-18)是收缩阈值操作符，可以定义成如下形式： (6-19)这里的x表示数

34、字、向量或者一个矩阵。当得到时，可以更新拉格朗日乘子如下： (6-20) 这三步不断重复执行直到收敛完成或达到设定的迭代次数，当 且时，迭代停止。一般取。6.4 求解结果图6-2(a)和图6-2(b)为将相交直线按照一定的特征聚类后，每一类的分解图，图6-2(c)为合并在一起的分类图，合并图中用不同的颜色和记号区分不同的类。(a) (b)(c)图6- 2 相交垂直直线的聚类分解图图6-3(a)至图6-3(c)为将不满足独立子空间关系的一个平面和两条直线按照一定的特征聚类后，每一类的分解图，图6-3(d)为合并在一起的分类图，合并图用不同的颜色区分不同的类。(a) (b)(c) (d)图6- 3

35、 不满足独立子空间关系的聚类分解图图6-4(a)和图6-4(b)为将两条不相交的二次曲线按照一定的特征聚类后，每一类的分解图，图6-4(c)为合并在一起的分类图，合并图用不同的颜色和记号区分不同的类。(a) (b)(c)图6- 4 不相交二次曲线的聚类分解图图6-5(a)和图6-5(b)为将两条不相交的二次曲线按照一定的特征聚类后，每一类的分解图，图6-5(c)为合并在一起的分类图，合并图用不同的颜色和记号区分不同的类。(a) (b)(c)图6- 5两条相交螺旋线的聚类分解图综上所述，对于图形为两条不相交的二次曲线，特征比较容易区分，采用问题一中的k-means算法对其进行分类，分类结果如图6

36、-2(c)；对于两条交点不在原点且相互垂直的两条直线、两条相交螺旋线分类，本文建立了基于差分演化算法的essc模型进行聚类求解，分类结果如图6-2(a)和图6-2(d)，不同的类别用颜色加以区分；对于一个平面和两条直线，不满足独立子空间关系的图形的分类，求解比较复杂，因此本文建立了稀疏子空间聚类模型，并采用交替方向解法求解该分类问题，最终将所给图形按照对应特征分为三类，不同的分类仍旧按不同的颜色区分。综上所述，问题二所给四个图形的聚类结果表达如图6-6所示：(a) (b)(c) (d)图6- 6 问题二图形最终求解结果6.5 结果分析从以上模型求解分类结果图中可以看出，本文所建立的模型能很好的

37、解决对应的图形特征分类问题，并得到较理想的分类结果，对于没有交叉、特征较明显的图形分类问题，采用问题一中的k-means算法就能解决；对于较复杂的有交叉的图形分类问题，本问中的essc算法能够很好的解决；对于更为复杂的不满足独立子空间关系的分类，则需要用到稀疏模型交替方向求解算法来解决对应问题。总的来说，本问所建立的模型能很好的一一应对解决相应分类问题，虽然不能有一个通用的模型来解决本题所涉及的四个不同的分类问题，这是以后的研究中需要去完善的地方，但能够对同一类型的分类问题有一个较好的分类结果。7.问题三：改进的稀疏子空间聚类算法模型7.1 改进稀疏最优化模型建立位于线性或仿射空间高维数据稀疏

38、地用同一个子空间的点线性或者仿射表示，按如下的稀疏表示技巧将题目所给的数据稀疏表示。设有n个d维数据，处于空间的n个线性子空间中，子空间的，子空间的维数分别为，定义一个矩阵y为： (7-1)其中，是一个秩为dl的矩阵，表示第l个子空间数据组成的矩阵。为未知的置换矩阵。子空间聚类目的就是获得矩阵。6.2节中提出了稀疏子空间的聚类模型能很好地解决低噪声或无噪声的数据点分类问题，但在实际的问题中如将视频中有着不同运动的物体分开、人脸识别等，这些问题的处理中，数据点中通常混合着稀疏的奇特值和噪声，而且，数据常常处于仿射子空间的并内而不是线性子空间。为了解决这些问题，本问中将传统的稀疏最优化模型进行转化

39、，得到改进的稀疏最优化模型为： (7-2) (7-3)其中，c为稀疏稀疏矩阵，e为稀疏奇异值矩阵，z为噪声矩阵，系数。 (7-4) (7-5)稀疏代表的获得转化为一个凸优化的问题。该稀疏最优化模型只对独立的子空间和不相交的子空间有效，不需要提前获知子空间的个数和维数，稀疏最优化模型获得的稀疏矩阵c是对角块矩阵，根据对角块矩阵的个数可以知道子空间的个数和维数，该优化的求解通过admm框架完成。综上所述，建立的改进稀疏最优化模型为：7.2 模型的求解将获得的稀疏系数矩阵c应用到谱聚类算法中，从而对数据进行聚类，称为稀疏子空间聚类(ssc)算法。本文对原有的ssc算法进行改进，选择一个高效的谱聚类算

40、法，得到改进的ssc算法。7.2.1谱聚类算法谱聚类是建立在图谱理论基础上的一种数据聚类方法，本文的算法步骤为：首先根据给定的样本数据集建立数据间的相似度矩阵，然后通过寻找图的最优划分构造加权图，实现数据聚类的目的，接着根据所述的稀疏表示的方法建立相似度矩阵，最后根据加权图的最优划分准则，产生不同的laplacian矩阵。正则化laplacian (7-6) (7-7)其中，d度矩阵为对角矩阵，对角线上的元素为，。l对应于划分准则ratiocut。而正则化laplacian对应于划分准则ncut。谱聚类算法寻求相似加权图的最优划分，要求类间切割权值最小而类内相似权值最大，正则化谱聚类能很好的满

41、足这两个条件。谱聚类算法涉及特征向量的计算，由两种laplacian矩阵的特性可知，的特征向量计算比的更为简单。另外，当数据点的度值变化较大，并处于很小值时，对应的特征向量值也会很小，从而使聚类算法比较困难。本文经过研究与实验比较选择了，产生改进的ssc算法。7.2.2谱聚类算法求解步骤谱聚类算法的定义为：给定一个数据可以构造一个无向加权图 g =v,e，其表示形式为一对称矩阵：，其中表示连接顶点 i与j的权值。其中 v是顶点的集合。集合表示基于某一相似性度量计算的两点间的相似度。用w表示待聚类数据点的相似度矩阵，将其看作是该图的邻接矩阵，它包含了聚类所需的所有信息。本文算法在获得稀疏系数矩阵

42、之后，选择正则化谱聚类算法，算法步骤描述如下：step1：输入n个d维的数据点；step2：数据点利用稀疏最优化模型(7-2)和(7-3)，解决此凸优化问题，获得稀疏系数矩阵c；step3：对稀疏矩阵c进行预处理：对矩阵c的每一列进行正则化操作，即step4：根据稀疏系数矩阵建立相似加权图，每个数据点只与其稀疏表示中的数据点连接，不同子空间的数据点无连接，权值矩阵为，其中，；step5：把相似加权图应用到谱聚类算法中，求laplacian矩阵，对其求特征值，子空间个数n为特征值零的次数，获得前n个小特征值，把其对应的特征向量形成的矩阵u；step6：把u的每一行作为n维空间的一个向量，对u进行

43、k-means聚类。n行所对应的类就是其n个数据点所对应的类；step7：聚类并输出。7.3 求解结果 对于题图3(a)十字中的点按照“横”和“竖”分类的求解问题，本文采用上个章节中建立的稀疏子空间聚类算法模型求解，得到如图7-1所示的分类结果，不同的分类用不同的颜色加以区分：图7- 1 十字按照“横”和“竖”分类的结果对于题图3(b)将视频中有着不同运动的物体的分类问题，本文通过改进稀疏子空间聚类算法模型，引入稀疏奇异值矩阵e和噪声矩阵z，得到改进的ssc算法模型，将该算法应用与视频中一帧的运动分割和人脸识别分类问题，得到如图7-2和表7-1、表7-2的类别标签输出结果：对视频中一帧的特征点

44、轨迹进行运动分割，得出样本的类别标签输出结果见表7-1，用数字“1”、“2”、“3”分别表示不同的类，共分成三类：表7- 1视频中一帧的运动分割分为三类的类别标签111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111333333333333333333333333333333333333333333333333333333333333333333333333333322222

45、222222222222222222222222222222222222222222222222222222222222222222222222222222将表7-1的分类结果的提取图与原图放在一起对比，以便更直观的反映我们的分类结果与实际结果的符合度，如图7-2所示：图7- 2 视频中一帧的分类结果与原图的对比对两个人在不同光照下的人脸图像进行分类，得出样本的类别标签输出结果见表7-2，用数字“1”和“2”分别表示不同的类，共分成两类：表7- 2人脸识别中20幅图像分为两类的类别标签222221111122222111117.4 模型检验7.4.1基于光流场的运动分割结果检验3b.mat给出

46、了三类不同运动特征点的轨迹，要求把属于不同运动物体的轨迹点提取出来，上面的模型求解出了结果，但由于没有原始的帧图像像素值，我们无法确定模型求解结果的准确性。问题属于视频运动分割的范涛，我们可以采用基于光流场的运动分割对上面求解的结果进行有效的检验。光流场是图像中所有像素点构成的一种二维(2d)瞬时速度场，具有显著的光学运动特征。光流表达了图像的变化,它包含运动目标的信息,可以用来确定运动目标情况，例如有灰度的象素点。观察数据的特点，我们可以发现3b.mat的数据是由32帧图像包含的三个不同物体的297个特征点的像素点组成的。每一个特征点在32帧图像中都有一个对应像素点，一个特征点的32个像素点

47、可以按帧时间顺序组成一个光流矢量，297个特征点就有297个光流矢量。按照上面模型求解的结果，我们将三类不同的矢量用图像表示出来如下图：(a) (b)(c) (d)图7- 3 运动特征分割光流矢量图从上面的图中可以明显的发现三类趋势矢量，图7-3(a)代表原帧序列中树的光流矢量图，图7-3(b)代表原帧序列中公交车的光流矢量图，图7-3(c)代表原帧序列中小轿车的光流矢量图。其中树是静止不动的，却具有明显趋势的矢量图，说明摄像者在摄像过程中具有运动；树和公交车的光流矢量图具有相同的趋势，说明公交车此序列没有运动；树和小轿车的光流矢量图具有不同的趋势，说明小轿车在此序列具有运动。模型检验此模型效

48、果显著。7.4.2基于图像复原的人脸识别结果检验3c.mat给出了两个人在不同光照下人脸图像的相关灰度数据，要求把属于不同人的人脸灰度数据提取出来，上面的模型求解出了结果，但不明确结果是否准确上面的模型求解出了结果。因此，我们采用了基于图像复原的人脸与模型标签结果比对，验证此模型是否有效。观察数据特点并参考文献，发现由2016个数据组成的向量，是来源于的矩阵，从一维向量中恢复出二维矩阵，就可得到20张人脸图像如下图排列：图7- 4 原始人脸顺序图从上面恢复的人脸图像中，可以明显发现两个人的不同特征，一个人脸的左边有一颗痣，另一个人脸的嘴比较大，1-5，11-15，属于同一个人的人脸；6-10，

49、16-20属于另外一个人的人脸。按照同一人的人脸排列在同一行，重新排列结果如下： 图7- 5 聚类后的人脸图人脸图像恢复序列按照人的标签，与前面的模型求解的聚类标签保持100%一致，说明上面模型对此问题的解决十分有效。模型检验此模型效果显著。7.5 结果分析从图7-1可以看出，我们采用问题二所述的稀疏子空间聚类模型，将“十”字图形按照“横”和“竖”分成了两类，图中红色表示对特征为“横”的数据点的聚类，绿色表示对“竖”的数据点的聚类。从表。7-1可以看出，我们将运动视频中的一帧按照运动特性的不同将其分为了三类，其中，数据点1-138号为一类用数字“1”标记，表示路边静止的树和房屋；数据点139-214为一类，用数字“3”标记，表示移动的公交车，数据点215-297为一类，用数