数据的多流形结构分析9

   参赛密码（由组委会填写） 第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛     学    校 解放军理工大学 参赛队号 90006058队员姓名 1.石树杰2.怀开展3.杨柳     参赛密码（由组委会填写） 第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目         数据的多流形结构分析 摘要： 数据的多流形结构的本质是揭示数据的潜在空间分布规律，从海量的复杂数据中提取用户所需要的有价值信息。其思想是把一组在高维空间中的数据在其潜在的低维空间流形中表示出来，其主要目的是期望寻找产生数据集的内在规律性，即从观测的现象中去寻找其本质。本文主要以谱聚类算法为研究手段，主要工作和创新点包括以下几个方面：1.问题一中采用谱聚类的独立子空间分割模型，将独立子空间中的高维数据分成两类；进一步采用基于共享近邻的自适应谱聚类模型，克服了传统谱聚类模型依赖于人工设定参数的限制，分类结果见附录1。2.为了解决谱聚类模型无法解决有交叉区域的分割问题，在处理问题二中四个低维空间的聚类问题时采用了基于谱多流形算法的聚类模型，该模型充分利用流形采样点所内含的自然局部几何结构信息来辅助构造更合适的相似性矩阵，进而发现正确的流形聚类；分别采用F-measure值、RI值、NMI值作为评价测度，仿真结果表明，谱多流形聚类算法明显优于谱聚类算法；分析了算法主要参数对分类性能的影响，并分析了该算法的复杂度。   3.对于子空间聚类在实际中的应用，首先通过分离宽十字交叉点来验证谱多流形聚类对于交叉区域的鲁棒性；为建立不同帧上同一特征点的运动联系，建立了基于昀小矢量差的谱多流形聚类模型，分类结果见附录2；将人脸图像向量数据转化为矩阵，加强同一人脸图像上像素点之间的关联性，采用谱多流形聚类算法将所有人脸图像分成两类，结果表明,该算法将人脸图像按照地缘特征严格地分成两类，即10个欧美人脸图像为一组，10个亚洲人脸图像为另外一组，分类结果见附录3，同时针对一般图片的高像素问题，给出了降低算法复杂度的数据处理方法并通过分类结果验证其有效性。4.问题四为混合多流形聚类在实际中的应用问题，采用谱多流形聚类算法能够利用点云特别是交叉点云的局部空间的几何结构信息，克服了单纯的基于距离的远近分类点集，将圆台点云有效地分割为顶、底以及侧面三类；对于工件轮廓线的分类问题，提出了一种改进的分部谱聚类算法，通过粗聚类划分连通集、细聚类划分流形，能够明显提升轮廓线分类的准确率，昀终轮廓线被分成10类，包括4类直线和6类圆弧线。关键词：高维，局部空间，子空间，谱多流形聚类，分部谱聚类   目录1问题重述................................................................12基本假设................................................................23主要符号说明............................................................24问题分析................................................................25谱聚类的相关知识........................................................55.1谱聚类理论基础.......................................................55.1.1图的基本概念.....................................................55.1.2相似矩阵和图的Laplacian矩阵.....................................65.2谱聚类评价测度.......................................................86问题一：独立子空间高维数据聚类问题.....................................116.1模型一：基于谱聚类的独立子空间分割模型..............................116.1.1模型建立........................................................116.1.2模型求解........................................................126.2模型二：基于共享近邻的自适应谱聚类模型..............................156.2.1模型准备........................................................156.2.2模型建立与求解..................................................177问题二：低维空间中的子空间与多流形聚类问题.............................187.1模型三：基于谱多流形算法的聚类模型..................................187.1.1模型建立........................................................187.1.2模型求解........................................................187.1.3问题二分类效果及分析............................................208问题三：子空间聚类在实际中的应用.......................................258.1宽交叉十字形数据点群的分类问题......................................258.2多帧图像运动特征点轨迹分类问题......................................268.2.1模型四：基于昀小矢量差的谱多流形聚类模型........................288.2.2模型求解与讨论分析：............................................298.3人脸图像分类问题....................................................31   8.3.1数据预处理......................................................318.3.2问题求解........................................................328.3.3求解过程的简化：数据再处理......................................339问题四：实际应用中的多流形聚类问题的探讨...............................369.1三维点云的分类问题..................................................379.1.1谱多流形聚类方法分类圆台点云....................................379.1.2实验结果与分析..................................................389.2工件轮廓线的分类问题................................................3810总结.................................................................43参考文献...................................................................44附录...................................................................45  1 1问题重述在如今这个信息爆炸的时代，海量的数据不断产生，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。数据结构分析的难点在于以下几个方面：一是从线性到非线性的扩展，流形学习的出现，很好地解决了具有非线性结构的样本集的特征提取问题。然而流形学习方法通常计算复杂度较大，对噪声和算法参数都比较敏感，并且存在所谓的样本溢出问题；二是流形或子空间从一个到多个的扩展，子空间聚类是将数据按某种方式分类到其所属的子空间的过程，通过子空间聚类，可以将来自同一子空间中的数据归为一类，由同类数据又可以提取对应子空间的相关性质，然而有些实际问题的数据并不符合混合子空间结构的假设，假设数据的结构为混合多流形更具有一般性，由于混合流形不全是子空间的情况，数据往往具有更复杂的结构，分析这种数据具有更大的挑战性。本文主要解决以下问题：1.将1.mat中采样于两个独立子空间的高维数据分成两类。2.处理四个低维空间中的子空间聚类问题和多流形聚类问题：（a）将两条交点不在原点且互相垂直的两条直线分为两类；（b）将不满足独立子空间关系的一个平面和两条直线分为三类；（c）将两条不相交的二次曲线分为两类；（d）将两条相交的螺旋线分为两类。3.解决三个实际应用中的子空间聚类问题：（a）将宽交叉十字上的数据点分成两类；（b）视频的一帧中，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，将这些特征点轨迹分成三类；（c）3c.mat中的数据为两个人在不同光照下的人脸图像共20幅（X变量的每一列为拉成向量的一幅人脸图像），将这20幅图像分成两类。  2 4.解决两个实际应用中的多流形聚类问题：（a）将圆台中的点云按照其所在的面分开(即圆台按照圆台的顶、底、侧面分成三类)；（b）将机器工件外部边缘轮廓线中不同的直线和圆弧分类，类数自定。2基本假设1、假设题目所给数据都是有效数据，即不存在噪声。3主要符号说明V图顶点的集合W边权值矩阵L拉普拉斯矩阵D度矩阵S相似矩阵i局部切空间k分类数K近邻点数4问题分析在过去的几十年里，随着人类社会的发展，电子计算机和各种数据采集工具（如摄像头、传感器等）不断地得到普及并融入人们的日常生活中。随之而来的是，从多个数据源得到的多种形态的数据不断地成指数级的爆炸，人们已经能够在不分时间和地域的情况下，方便地获取各种数据和信息。如何对这些海量的观测数据进行压缩、存储、阅读、分析、处理，从它们中学习和发现某些内在的规律性，进而探讨隐藏在大千世界纷繁复杂的观察表象背后的事物本质，成为人们迫切想知道和亟需解决的问题。近年来，聚类正在蓬勃发展，聚类分析在多个研 3 究领域都有了很大贡献，包括数据挖掘、机器学习、统计学、空间数据库技术、生物信息学以及市场营销等。问题一给出了一组高维数据，代表高维空间中的点分布情况。当子空间独立时，聚类问题相对容易，但是当数据维数较高的时候，其受到随机因素的影响较大，同时数据处在高维空间中，分布较为离散。因而可采用先降维后聚类的方式，即先对高维数据进行降维预处理，再用谱聚类算法对数据进行聚类。而谱聚类算法中，相似矩阵的构建是一个关键，在相似矩阵的构建过程中如果能有