数据的多流形及子空间的聚类模型研究

参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校北京航空航天大学参赛队号B10006005 队员姓名1.朱日东2.黄博3.王敬凯构建于C向乘CluSM运用经典们采实验及第二类本文取合果；对(c此对分类运动第第十十二二题目本文通过建立了多种CVX的稀疏乘子法的稀stering,SCCCE)和谱多用这些模型第一问中典的K均值采用SSC-C验结果表明第141个数类。第二问中文采用SMM合适的参数SCC对(ac)中的数据第三问中对该数据采类格式，将动的特征点二二届届““数过对子空间聚聚类数学模疏子空间聚稀疏子空间聚C)、稀疏流多流形聚类(完成了数据中，数据在两值聚类与SCVX、SSC所有算法均数据到第200中，要解决四MC,SCC,数，SMMCa),(b)中的数据进行了很好，(a)的数据采用SCC和将数据按照点轨迹进行分““中中关关村村数数学学据的多流摘聚类问题和模型：K均聚类(SparseS聚类(SSC-A流形聚类(SpSpectralMu据的分类，两个独立的SC进行聚类C-ADMM、均可得到相0个数据属四个低维空SMCE三个非常好的对数据进行了很好的分类，据在分布上和SMMC模“横”和“分类。本文村村青青联联学学建建模模流形和子摘要和多流形聚类值聚类、谱SubspaceCADMM)、谱parseManifulti-Manifo并且实现的的子空间，类，得出分SCC、SM相同的分类结属于第一类，空间中的子个模型对四对四组数据很好的分类得到了题目上与第二问模型进行聚“竖”分两类文首先采用参赛联联杯杯””全竞竞赛赛子空间聚类要：类问题的分谱聚类(SpecClustering,S谱曲率聚类foldClusteroldClusterin的聚类效果聚类相对容分类结果。为MCE四个模结果：第1第41个数空间聚类问四组数据分别据进行了分类类，得到了目要求的结中(a)的数据聚类，两种方类。(b)中采此算法进行赛密码（由组委会全全国国研研类模型研分析，针对相ctralClusterSSC-CVX)类(SpectralCringandEmng,SMMC)果是非常可观容易，因此为一步验证模型分别对个数据到第数据到第1问题和多流别进行分类类，得到了题目要求的结果。据具有一定方法都实现采用SSC-A行分类。又会填写）研研究究生生研究相应的数据ering,SC)、、基于交替Curvaturembedding,)模型，并综观的。此我们首先采证分类结果，对数据进行分第40个数据40个数据属流形聚类问题类。其中通过了题目要求的的结果；SM定的相似性，现了题目要求ADMM模型又已知，同一据结基替方综合采用，我分类，据以属第题。过选的结MCE，因求的型对一运动的特征点轨迹在同一个线性流形上。所以我们也尝试采用流形聚类方法：SMCE和SMMC模型对运动特征轨迹分类。为了验证和分析分类结果，我们还采用了K均值、SC模型、SCC模型进行聚类。实验结果表明，以上方法都一致的将第1个数据和第138数据分为同一类，将其余的数据归于其它两类。在第267个数据，第275个数据，第276个数据与第297个数据的分类中存在差异。我们分析这两类运动的特征点轨迹可能较为相似，在移动中，存在相交，因而在这两类运动的相交边界处的特征点轨迹可能会出现分类上的不同。(c)中采用SSC-ADMM模型对人脸进行分类。我们仍先采用此算法对人脸数据进行分类。为验证分类结果，我们采用适宜处理高维数据分类的SCC、SMCE、SSC-CVX模型进行分类实验。通过实验可以发现这几种方法均可得到与SSC-ADMM算法一致的分类结果：第1个到第5个人脸数据以及第11个到第15个人脸数据属于一个人，其余的属于另一个人。第四问中，(a)问题中圆台数据属于多流形结构，所以我们采用SMMC算法对圆台数据进行分类，调整参数的选取，可将圆台的顶、底、侧面分成三类。(b)机器工件外部边缘轮廓的图像数据用SMCE算法分成三类和四类，得到较好的聚类效果。关键词：谱多流形聚类稀疏流形聚类与嵌入稀疏子空间聚类谱曲率聚类谱聚类代，了诸进行分类上求以及关性数据类的维数个独如图两类子，1(d)建是随着计算迫切需要诸多问题成行数据处理类、等模式求解各种数及图象分割性分析、聚据处理及其的多种方法在题目给1.当子空间数据（.mat独立的子空2.请处理图1所示。类；图1(b)请将其分)为两条相3.请解决(a)受实际是一类重要算机技术和互要对这些大数成功解决的关理的重要方法式识别和数据数学模型，也割、运动分割聚类分析等基其应用领域经法解决了子空给定的数据和间独立时，所存矩阵的空间。请将该附件二中四图1(a)为)为一个平面分为三类。图交的螺旋线(a)(c)决以下三个实际条件的制约要的非接触测一互联网的飞数据进行有关键，涌现法,已经被广据分类问题也成为目前割等计算机基本问题，经典的子空空间聚类问和参考文献子空间聚类的每列为一该组数据分四个低维空为两条交点不面和两条直图1(c)为两线，请将其实际应用中约，在工业测量方法。1一、问题重飞速发展，有效的分析现出了大量广泛应用在题，此外，前数据分析机视觉问题结构分析空间聚类的问题和多流行献下，求解以类问题相对一个数据点分成两类。空间中的子空不在原点且直线，这是两条不相交分为两类。图1中的子空间聚业测量中往特征提取----重述我们已经进，以至数据的数据分析在人脸识别、如何快速有与处理领域中。更一般也格外重要求解方法，行聚类问题以下4个问对容易。附件，以下各题空间聚类问且互相垂直的一个不满足的二次曲线聚类问题，往需要非接是视觉重建-1-0.5-0.8-0.6-0.4-0.200.20.40.60.8进入高维和据的分析和析方法。几手写体数有效的在大域亟待解决般地，对于要。而本次并着重使题。题：件一中1.m题均如此）问题和多流的两条直线足独立子空线，请将其(b)(d)数据见附件接触测量的建的一个关00.5和海量数据的和处理方法成几何结构分析数字识别、图大规模高维数决的重要问题于高维数据的次建模就是采使用了基于谱mat中有一组，它采样于流形聚类问题线，请将其分空间的关系的其分为两类。件三的方式，视觉关键环节，如011的时成为析是图像数据题。的相采用谱聚组高于两题，分为的例。图觉重如图-12(a)已经按照构中方法场景特征动的点轨的每台的分类)所示，其中经提取出来照“横”和“竖(b)运动分中是不可缺法首先利用景中不同运征点轨迹在的特征点轨轨迹分成三（c）3c.m每一列为拉4.请作答图3(a)分别的顶、底、图3(b)是类，类数自中十字便是来，为了确定竖”分两类。分割是将视频缺少的一步。用标准的追踪运动对应的不在同一个线性轨迹被提取出三类。(a)mat中的数拉成向量的一答如下两个实别显示了圆侧面分成三是机器工件外定。(a是特征提取定十字的中请使用适当频中有着不。基于特征踪方法提取不同特征点性流形上。出来保存在)数据为两个人一幅人脸图实际应用中圆台的点云三类)。外部边缘轮)2取环节中处理中心位置，当的方法将不同运动的征点轨迹方取视频中不点轨迹分割图2(b)显在3b.mat文图2人在不同光图像），请将中的多流形聚，请将点按轮廓的图像图3理得到的，一个可行的将图2(a)中十物体分开，法是重要的同运动物体出来。已经示了视频中文件中，请使光照下的人脸将这20幅图聚类问题按照其所在，请将轮廓十字上的的方法是先十字上的点是动态场的一类运动体的特征点经有文献指中的一帧，使用适当方(b)脸图像共2图像分成两的面分开(即廓线中不同(b)的点的位置信先将十字中的点分成两类。场景的理解和动分割方法，点轨迹，之后指出同一运动有三个不同方法将这些特20幅（X变两类。即圆台按照同的直线和圆信息的点。和重，该后把动的同运特征变量照圆圆弧3二、模型假设1.假设提供的数据是可信的（只有极小部分受损坏）2.假设数据集分布在多个维数不等的流形上3.假设数据集服从多项分布4.未标记的数据点位于或接近多低维光滑流形三、符号说明符号说明12,,,,inXxxxx数据点集合()JC聚类结果各类总的距离平方和(,)cutABA,B两个子图的代价函数(,)NcutABA,B两个子图的割集准则(,)assocAA子图A内所有顶点连接的权重之和()ijijqqxx两个点,ijxx之间的Euclidean距离ijw两个点,ijxx之间的亲和力值iix处的切空间表示ijp切空间在,ijxx两点之间的相似性()Knnxx的K个附近邻域1nllMn个不同的流形四、问题分析通过对问题的初步分析可知，本题是要求我们用几何结构方法对数据进行分析处理，而我们知道高维空间的数据往往能够在其低维子空间中进行表示，这样的低维表示对于数据的处理是极有帮助的。而经典的子空间聚类方法恰巧能够准确的在低维空间中表示数据，实现子空间聚类问题的方法有很多，包括代数方法、迭代方法、统计学方法、基于谱聚类的方法。各种方法的理论基础不同，在求解过程上也有很大差异。本文主要采取近几年较为流行的基于谱聚类的多种聚类方法并综合运用得到理想的分类结果。问题1:要求我们对附件一中的数据分成2类，由于数据采样于两个独立的子空间，子空间聚类问题相对容易，尝试了K均值聚类，SC，SSC等多种方法进行数据分类，运行结果发现这些方法是合理有效的。问题2:对四个低维空间中子空间聚类问题和多流形聚类问题，由于数据结构性质的变化，简单经典的K均值聚类及SC(谱聚类)方法就无法使用，此时针对问题建立了SCC、SMCE与SMMC模型，得到理想的分类结果。问题3:分析三个实际应用中的子空间聚类问题，(a)中为确定十字的中心位置可以考虑将十字中的点分成横竖两类，这就与问题2中(a)类似。(b)考虑到在文献[5]给出基于ADMM的SCC模型是一种重要运动的分割方法，所以可以将4其应用到(b)题运动特征点轨迹的分类。由已知，相同运动的特征点轨迹属于同一个流形，进而可用流形聚类方法：SMMC与SMCE对进行数据分类；(c)将数据的每一列看成拉成向量的一幅人脸图像，此时每幅图像即变成一个高维数据。本题即变成对高维数据的分类，因为是在不同光照下的人脸，所以需要提取在不同光照干扰下的人脸特征。此时我们考虑用基于ADMM或者CVT的SSC，以及SCC方法对人脸数据进行分类。问题4：对实际问题中的多流行聚类问题(a)及(b)，这些数据都具有复杂结构且其本身无法使用相互表示的方式，但数据的特征可相互表示，因此基于谱聚类的流形聚类方法仍可处理这种问题。五、模型建立5.1K-Means聚类算法模型[1]对于给定的一个包含n个d维数据点的数据集12,,,,inXxxxx，其中dixR，以及要生成数据子集的数目K，K-Means聚类算法将数据对象组织为K个划分,1,2,kCciK。每个划分代表一个类kc，每个类kc有一个类别中心i。选取欧氏距离作为相似性和距离判别准则，计算该类内各点到聚类中心i的距离平方和2()iKkikxCJcx(1)聚类目标是使各类总的距离平方和1()()KkkJCJc昀小。221111()()ikKKKnkikkiikkkxCkiJCJcxdx(2)其中，1,x0,iikiiicdxc，显然根据昀小二乘法和拉格朗日原理，聚类中心k应该取为类别kc类各数据点的平均值。K-Means聚类算法从一个初始的K类别划分开始，然后将各数据点指派到各个类别中，以减少总的距离平方和。因为K-Means聚类算法中总的距离平方和随着类别个数K的增加而趋向于减少。因此，总的距离平方和只能在某个确定的类别个数K下，取得昀小值。5.2谱聚类算法模型(SC)[2,3,4,6]5.2.1图划分准则谱聚类算法建立在图论中的谱图理论基础之上，其本质是将聚类问题转化为图的昀优划分问题，是一种点对聚类算法，谱聚类算法思想来源于谱图划分理论，假定将每个数据样本看作图中的顶点V,根据样本间的相似度将顶点间的边E赋