数据的多流形结构分析3

参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校中国矿业大学参赛队号10290012队员姓名1.徐云靖2.冯乐3.师庆民参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目数据的多流形结构分析摘要：几何结构分析是进行数据处理的重要基础，基于谱聚类算法的多流形结构分析是解决几何结构分析的主要方法之一，本论文充分探讨了主成分分析（PrincipalComponentAnalysis，PCA）+K-means聚类模型、共享近邻谱聚类（SharedNearestNeighbors，SNN）、稀疏子空间聚类（SparseSubspaceClustering，SSC）、多流形谱聚类（SpectralMulti-manifoldsClustering，SMMC）、稀疏流形聚类与嵌入模型（SparseManifoldClusteringandEmbedding，SMCE）和变色龙聚类模型（CHAMELEONClustering）等聚类模型，并针对各个问题，分析具体分类目标与各个模型算法特点，对四个问题分别进行了求解，最终对模型进行评判并提出改进意见。针对问题一，将采样于两个独立子空间的高维数据（200*100）进行聚类。本论文采用了传统的主成分分析（PCA）+Kmeans聚类算法，将N=200，D=100的高维数据用前20维（贡献度为98.65）标记，并分为两类；并与稀疏子空间聚类（SSC）模型进行对比，二者分类结果如下图所示，结果一致；1针对问题二，主要是对四个低秩子空间和多流形低秩子空间进行聚类。分别利用SSC、SMMC及SNN聚类方法，成功解决低维空间下非线性子空间的聚类问题（如下图所示），并通过模型特点分析了各自的优劣。认为SSC在解决直线子空间交叉问题更占优势，而SMMC及SNN在解决流形聚类上效果显著。同时，SMMC更适合解决具有交叉的子空间问题。2a2b2c2d针对问题三，在问题二对典型子空间和多流形问题成功聚类的基础上，解决实际问题。题3.1基于SSC的谱聚类算法，成功将特征提取环节中处理得到的十字上的点位置信息提取并分成两类；题3.2基于特征点轨迹追踪对视频的31帧运动进行运动分割，定义并基于原始数据生成了一个基于偏移量的运动轨迹特征矩阵，采用SNN谱聚类算法，将297个特征点准确分成3类，并还原运动轨迹；题3.3针对2016维人脸向量图，分别采用不降维和利用PCA降维至9维（贡献度为99.67）的方法，基于SSC谱聚类算法对20张人脸进行分类和标记，并取得了一致的结果（标签列表如下所示）。11111222221111122222针对问题四，深入探索了谱聚类解决更加复杂的几何结构问题的适用性。分析题4.1中图形的几何特征，通过模型调整几何结构中更具有决定性的几何量的权重，采用SNN谱聚类算法，成功对图形进行聚类（如下图所示）；分析题4.2中图形的几何特征，选用Chameleon算法和SMCE谱聚类算法分别对图形轮廓进行聚类，其结果表明SMCE谱聚类算法不仅能够图形轮廓线中同一流形的连续点进行聚类，并且有噪声干扰的情况下，对于较外的轮廓线，其分类能力较Chameleon聚类算法更加显著（如下图所示）。4a4b最后，基于4个问题的求解与分析，本文认为现阶段谱聚类在图形数据分类中仍然是十分有效的方式，通过将来自不同子空间的高维数据分割到所属的低维子空间中进行聚类，解决了维度高带来的复杂与稀疏问题。但是由于所处低维空间的流形特征与子空间相交的问题，给聚类带来极大困难，目前并没有统一模型同时对多流形与交叉子空间分类进行合理的解决。不论通过低维度的同流形判断还是通过局部密度的相似矩阵建立，都受到了噪声点与数据点缺失以及奇异样本等的影响。算法改进思想在于对噪声和缺失点的判断与消除，通过多次降维或是依据统计分布情况，筛除缺失值和噪声点，同时正则项的适当设定，让数据可以有先验信息，来达到更为准确的判断。关键词：谱聚类；流形；稀疏子空间；降维；运动分割；正则项目录一问题重述..........................................................................................................................1二基本假设及说明..............................................................................................................2三基本符号说明..................................................................................................................2四问题分析..........................................................................................................................34.1问题一分析..............................................................................................................34.2问题二分析..............................................................................................................34.3问题三分析..............................................................................................................34.4问题四分析..............................................................................................................4五模型特点介绍..................................................................................................................55.1PCA+K-means聚类模型..........................................................................................55.2谱聚类（SpectralClustering）.................................................................................55.2.1基于共享近邻的谱聚类（SNN）..................................................................65.2.2稀疏子空间聚类（SSC）..............................................................................65.2.3多流形谱聚类模型（SMMC）......................................................................75.2.4稀疏流形聚类与嵌入模型（SMCE）...........................................................85.3CHAMELEON聚类..................................................................................................8六问题求解..........................................................................................................................96.1问题一求解..............................................................................................................96.2问题二求解............................................................................................................106.2.1图a求解.......................................................................................................106.2.2图b求解......................................................................................................116.2.3图c求解.......................................................................................................126.2.4图d求解......................................................................................................136.3问题三求解............................................................................................................156.3.1题a求解.......................................................................................................156.3.2题b求解......................................................................................................156.3.3题c求解.......................................................................................................186.4问题四求解.............................................................................................................196.4.1图a求解...........................................................................................