数据的多流形结构分析

参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校上海交通大学参赛队号10248091队员姓名1.杨晓宇2.张哲3.甄诚参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目数据的多流形结构分析摘要：进入信息时代,人们生活的各个方面都离不开数据的处理,对大规模数据的分析与处理在科学研究领域占据着越来越重要的地位。基于流形学习的聚类算法，是当前计算机模式识别领域的新思路。本文通过引入基于流形学习的聚类方法来解决复杂数据集的聚类问题，主要采用了PCA,SSC,SMMC,mum-Cluster,LSC等算法以及其相应的改进算法解决了一系列不同数据特征、不同实际场景的聚类问题，其中包括独立与非独立子空间聚类问题、多流形聚类问题以及多种实际问题，并且在参数调节过程中，提出了一种基于PID的参数调节算法，这在本文的问题解决过程中起到了至关重要的作用。在问题一中，我们采用了PCA算法获得了一个基本解，并从中得到启发，采用了基于流形学习的SSC算法来进行数据的聚类，通过调节SSC的参数，得到合理的相似度矩阵，通过K-means聚类算法得到了高精度的聚类结果，分类结果为前40个点和最后60个点为一类，中间100个点分为一类。在问题二中，我们采用一种算法统一解决四种不同类型的数据，引入了SMMC算法，其核心思想是：从相似性矩阵的角度出发，充分利用流形采样点所内含的自然局部集合结构信息来辅助构造更合适的相似性矩阵并而发现正确的流形聚类。相对而言，题目中的四个数据集可以利用基本局部几何结构构造辅助信息来得到正确的结果，但SMMC受参数影响明显，参数的合理调节确实为一个难点，参数的好坏直接影响到分类结果的好坏，我们根据SMMC算法的经验公式，创新性地提出一种基于PID思想的参数调节策略，能够快速合理的逼近所需要的参数组合，得到所需要的聚类结果。同时，考虑到聚类算法的效能，我们在文中针对SMMC算法做了时间复杂度的分析。在问题三中，首先3(a)是一个大样本量的线性交叉的数据集合，针对其数据的特点我们引入了多流形聚类方法（mum-Cluster）方法。它直接从整个数据中找出流形交叠的部分并拆开不同的流形结构,从而构造出更忠实于流形结构的近邻图来实现混合流形聚类，通过PID参数调节策略，得出了理想的分类结果，在3(b)运动分割问题中，我们引入了加权SSC算法来进行运动分割，将视频序列分成多个时空区域。这种以高斯相似度作为权重的算法很好的解决了SSC算法出现的局部子块分类不准确的问题，结果在全部31帧数据中都能准确的聚类数据，实现了运动分割的预期效果。分类结果为1到138个数据属于同一流形，为背景信息；139到214个数据点属于同一流形，为公共汽车；215到297个数据点属于同一流形，为小汽车。针对3(c)中的人脸识别问题，我们首先采用了经典的PCA算法来进行启发式聚类，但是对于光照不同的特征提取不是很准确，导致了聚类结果的精度不高。因此，我们采用了2DIMPCA算法来进行了人脸识别，达到了完全精确的聚类效果。同时，我们也采用了RPCA先进行图像的预处理后，在采用SSC算法进行人脸识别，也可以达到同样的效果，分类结果为1到5,11到15属于一类，为外国人。6到10,16到20属于一类，为中国人。我们对4种算法的识别效率和运行时间进行了比较，发现2DIMPCA算法可以又快又准处理不同光照下的人脸视频问题。在问题四中，问题4(a)是一个大样本的数据集，我们根据问题二的求解经验，选择采用了SMMC算法进行了启发式聚类，但是基本的SMMC算法定义的自然局部集合结构信息来辅助构造的相似性矩阵并不能满足圆台两侧的聚类要求，所以，我们通过改变SMMC算法的局部集合构造信息，从点的信息转变成小的子块的信息，从而使相似性矩阵能更好的反映数据的特点，使侧面的数据能够精确的关联，经过改进后的SMMC算法，在我们PID参数调试策略的指导下，可以较为精确的完成数据集的分类。问题4(b)，我们根据数据的特点采用了LSC算法来进行聚类，其算法思想是：既考虑局部近邻信息又充分考虑流形结构数据所内含的额外的结构信息来指导近邻点的选取，以尽量地从同一个潜在流形上选取近邻点而不是整个欧氏空间。这样的流形结构在理论上可以达到我们的聚类的目的，从聚类结果上看，LSC算法基本实现了聚类要求。本文有以下的创新点，首先，我们引入了SSC算法去解决高维数据，然后，我们引入了SMMC算法去解决聚类问题，采用了SSC+RPCA算法和2DIMPCA解决了有噪声（光照不同）情况下的人脸识别问题，并对算法进行对比。引入了mum-Cluster算法去解决高密度有汇聚数据的聚类问题。更为重要的是，我们根据实际的经验结合算法理论提出了一套基于PID思想的参数调节策略，很好的解决了SMMC等算法的调节问题。针对SMMC所依赖的流形结构，我们采用了定义新的流形解决了自然流形无法聚类的问题，最后我们针对特殊的复杂的数据采用了LSC算法去定义一个近邻点的流形，可以有效的解决特殊的分类问题。关键词：流形学习、稀疏子空间聚类(SSC)、多流形聚类方法(SMMC)、PID策略、二维广义主成分分析(2DIMPCA)、局部与结构一致性方法(LSC)目录一．背景回顾................................................................................................................11.1问题引出.........................................................................................................11.2流形学习简述.................................................................................................21.3流形学习方法的分类.....................................................................................21.4稀疏子空间聚类与低秩子空间聚类.............................................................3二．问题一的建模与求解............................................................................................42.1问题重述.........................................................................................................42.2模型建构与方法分析.....................................................................................42.2.1稀疏子空间聚类..................................................................................42.2.2K-means聚类算法...............................................................................52.3问题求解.........................................................................................................6三．问题二的建模与求解............................................................................................93.1问题重述.........................................................................................................93.2多流形聚类方法（SMMC）.......................................................................103.2.1相似性矩阵........................................................................................113.2.2局部切空间........................................................................................123.2.3SMMC算法及其计算复杂度分析....................................................143.2.4参数对算法的影响............................................................................153.2.5基于PID的参数调节方法...............................................................153.3问题求解........................................................................................................163.3.1问题2(a)............................................................................................163.3.2问题2(b)............................................................................................183.3.3问题2(c)............................................................................................203.3.4问题2(d)............................................................................................21四．问题三的建模与求解..........................................................................................224.1问题重述.......................................................................................................224.2问题3(a).......................................................................................................234.2.1mum-Cluster方法...................................................