数据的多流形结构分析8

《数据的多流形结构分析8》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、参赛密码（（（（由组委会填写由组委会填写）））第十二届“““中关村青联杯“中关村青联杯”””全国研究生”全国研究生数学建模竞赛国防科学技术大学学学学校校校90002105参赛队号1.许许许强强强队员姓名2.刘晓聪3.邹邹邹桥桥桥参赛密码（（（（由组委会填写由组委会填写）））第十二届“““中关村青联杯“中关村青联杯”””全国研究生”全国研究生数学建模竞赛题目数据的多流形结构分析摘要：本文以稀疏子空间聚类以及低秩子空间聚类等基本谱聚类算法为基础，通过运用核映射算法，融合与数据本身结构相关的局部切线空间函数以及主成分分析算法建立了可以应对独

2、立子空间聚类、非独立子空间聚类、非线性聚类、混合多流体聚类问题以及多种含有大数据量的实际问题，包括处理运动分割、人脸识别、工件识别等情况中的多种类型数据分类的聚类算法，并且引入Map-Reduce并行处理方法优化了算法的计算效率，算法整体处理步骤如下图所示。待分类数据是否处于同局部相切函核函数映射否否否一流形上数数数是否PCA降维待分类数据是否位于独立子空间输入数据数据矩阵以及待分类数据是是是系数矩阵相似度矩阵Ncut聚类方法是否满足线性条件件件整个处理方法具有“通用性”，能够解决相关类的绝大部分问题。文章中问题二、问题三（a）以及问

3、题四等可视实验结果验证了算法的有效性。本文的算法基础在问题一的模型求解中给出。基于参考文献中的基础谱算法，本文提出了基于SSC与LRR相结合的正则项RZ()=Z+lZ，同时考虑了数据1*1可能存在误差的情况，提出了新的保真项FE()=bE，并且通过增广拉格朗日-2,1交替极小化求解方法得到模型的表示系数，还通过附加相似度权值计算了改进方法的相似度矩阵，然后利用Ncut算法得到了聚类结果，最后计算得出了整个处理22算法的计算复杂度NMt(+dt)+kt)+ON((+kN))。123问题二中出现的非线性数据分类，非独立子空间分类以及混合流

4、体分类等情况。本文首先采用了核映射算法，即通过一个非线性变换式将输入模式空间R中的数据映射到高维特征空间F中，解决了无法在低维空间处理非线性和非独立子空间的问题，这里采用的是高斯核函数()22kxy,=exp(-xy-/2p)。其次，考虑到聚类的主旨在于将数据集分类，即确保类内结构的相似性尽可能大，类间相似性尽可能小。我们将结合数据的部分原始信息和可靠的几何信息来构造局部切线空间函数，融合原有的相似度函数，改进相似度矩阵得到新的融合函数S'=fp(,q)，ijijij从而解决当数据来自混合流体时的一些列问题，进而得到正确的聚类。实验结

5、果表明，该聚类算法能够很好地解决上述问题。问题三中主要涉及到算法在实际场景中的运用，针对问题（a）将采用原有算法，首先将其核映射到高维空间，其次根据前文所述算法计算其相似度矩阵，从而获得聚类结果。针对问题三中的人脸识别以及运动分割等问题，本文提出了利用主成分分析方法进行降维处理，在保留原始图像数据所需要的大部分有用信息的前提下，用一个低维的子空间图像数据来描述人脸以及运动图像，减少了算法的运算量。针对问题四中的大数据，前文的算法已经能够解决该类问题。但是考虑到数据处理的实时性和算法的效率，我们结合Map-Reduce算法，提出了用于本

6、文的并行处理方法，大大缩减了运行时间。最后通过对问题四场景中的数据聚类进行实验验证，结论证明本文所提出的算法能够很好地解决该类问题。关键词：谱聚类，稀疏，核映射，局部切线21.问题的重述几何结构分析是进行数据处理的重要基础,特别是在对于高维数据的相关性分析和聚类分析等基本问题上结构分析格外重要。为了挖掘数据集的低维线性子空间结构，我们常用数据降维方法处理数据，这类方法以假设数据集采样于一个线性的欧氏空间为前提。但是，往往在实际问题中很多数据具备更加复杂的结构。针对单一子空间结构假设的后续讨论主要分为两个方面，首先是从线性到非线性的扩展

7、，主要的代表性工作包括流形（局部具有欧氏空间性质的空间定义为流形，而欧氏空间就是流形最简单的实例）学习等。其次是流形或子空间从一个扩展到多个的问题，即考虑处理的数据集采样于多个欧氏空间的混合。子空间聚类（又称为子空间分割，假设数据分布于若干个低维子空间的并集）是将数据按某种分类准则划分到其所属的子空间的过程。通过子空间聚类，可以将来自同一子空间中的数据归为一类，再由同类数据可以提取相应子空间的相关性质。子空间聚类的求解方法包括代数方法、迭代方法、统计学方法以及基于谱聚类的方法。在众多算法中，基于谱聚类的方法在近几年较为流行，通常情况下

8、使用这类方法一般都能得到正确的分类结果，其中代表性的谱聚类子空间分割方法包括低秩表示和稀疏表示等。假设数据的结构为混合多流形，因为多数境况下数据来自混合子空间。虽然也有些实际问题的数据并不符合混合子空间结构的假设，但这种