数据的多流形结构分析8

参赛密码（（（（由组委会填写由组委会填写由组委会填写由组委会填写））））第十二届第十二届第十二届第十二届““““中关村青联杯中关村青联杯中关村青联杯中关村青联杯””””全国研究生全国研究生全国研究生全国研究生数学建模竞赛数学建模竞赛数学建模竞赛数学建模竞赛学学学学校校校校国防科学技术大学国防科学技术大学国防科学技术大学国防科学技术大学参赛队号参赛队号参赛队号参赛队号90002105队员姓名队员姓名队员姓名队员姓名1.许许许许强强强强2.刘晓聪刘晓聪刘晓聪刘晓聪3.邹邹邹邹桥桥桥桥1参赛密码（（（（由组委会填写由组委会填写由组委会填写由组委会填写））））第十二届第十二届第十二届第十二届““““中关村青联杯中关村青联杯中关村青联杯中关村青联杯””””全国研究生全国研究生全国研究生全国研究生数学建模竞赛数学建模竞赛数学建模竞赛数学建模竞赛题目数据的多流形结构分析摘要：本文以稀疏子空间聚类以及低秩子空间聚类等基本谱聚类算法为基础，通过运用核映射算法，融合与数据本身结构相关的局部切线空间函数以及主成分分析算法建立了可以应对独立子空间聚类、非独立子空间聚类、非线性聚类、混合多流体聚类问题以及多种含有大数据量的实际问题，包括处理运动分割、人脸识别、工件识别等情况中的多种类型数据分类的聚类算法，并且引入Map-Reduce并行处理方法优化了算法的计算效率，算法整体处理步骤如下图所示。待分类数据是否待分类数据是否待分类数据是否待分类数据是否位于独立子空间位于独立子空间位于独立子空间位于独立子空间以及待分类数据以及待分类数据以及待分类数据以及待分类数据是否满足线性条是否满足线性条是否满足线性条是否满足线性条件件件件输入数据输入数据输入数据输入数据数据矩阵数据矩阵数据矩阵数据矩阵系数矩阵系数矩阵系数矩阵系数矩阵相似度矩阵相似度矩阵相似度矩阵相似度矩阵是是是是Ncut聚类方法聚类方法聚类方法聚类方法核函数映射核函数映射核函数映射核函数映射待分类数据待分类数据待分类数据待分类数据是否处于同是否处于同是否处于同是否处于同一流形上一流形上一流形上一流形上局部相切函局部相切函局部相切函局部相切函数数数数PCA降维降维降维降维否否否否是是是是否否否否整个处理方法具有“通用性”，能够解决相关类的绝大部分问题。文章中问题二、问题三（a）以及问题四等可视实验结果验证了算法的有效性。本文的算法基础在问题一的模型求解中给出。基于参考文献中的基础谱算法，本文提出了基于SSC与LRR相结合的正则项1*()RZZZλ=+，同时考虑了数据2可能存在误差的情况，提出了新的保真项2,1()FEEβ=，并且通过增广拉格朗日-交替极小化求解方法得到模型的表示系数，还通过附加相似度权值计算了改进方法的相似度矩阵，然后利用Ncut算法得到了聚类结果，最后计算得出了整个处理算法的计算复杂度22123())(())NMtdtktONkN++++。问题二中出现的非线性数据分类，非独立子空间分类以及混合流体分类等情况。本文首先采用了核映射算法，即通过一个非线性变换式将输入模式空间R中的数据映射到高维特征空间F中，解决了无法在低维空间处理非线性和非独立子空间的问题，这里采用的是高斯核函数()()22,exp/2kxyxyp=--。其次，考虑到聚类的主旨在于将数据集分类，即确保类内结构的相似性尽可能大，类间相似性尽可能小。我们将结合数据的部分原始信息和可靠的几何信息来构造局部切线空间函数，融合原有的相似度函数，改进相似度矩阵得到新的融合函数'(,)ijijijSfpq=，从而解决当数据来自混合流体时的一些列问题，进而得到正确的聚类。实验结果表明，该聚类算法能够很好地解决上述问题。问题三中主要涉及到算法在实际场景中的运用，针对问题（a）将采用原有算法，首先将其核映射到高维空间，其次根据前文所述算法计算其相似度矩阵，从而获得聚类结果。针对问题三中的人脸识别以及运动分割等问题，本文提出了利用主成分分析方法进行降维处理，在保留原始图像数据所需要的大部分有用信息的前提下，用一个低维的子空间图像数据来描述人脸以及运动图像，减少了算法的运算量。针对问题四中的大数据，前文的算法已经能够解决该类问题。但是考虑到数据处理的实时性和算法的效率，我们结合Map-Reduce算法，提出了用于本文的并行处理方法，大大缩减了运行时间。最后通过对问题四场景中的数据聚类进行实验验证，结论证明本文所提出的算法能够很好地解决该类问题。关键词关键词关键词关键词：谱聚类，稀疏，核映射，局部切线31.问题的重述几何结构分析是进行数据处理的重要基础,特别是在对于高维数据的相关性分析和聚类分析等基本问题上结构分析格外重要。为了挖掘数据集的低维线性子空间结构，我们常用数据降维方法处理数据，这类方法以假设数据集采样于一个线性的欧氏空间为前提。但是，往往在实际问题中很多数据具备更加复杂的结构。针对单一子空间结构假设的后续讨论主要分为两个方面，首先是从线性到非线性的扩展，主要的代表性工作包括流形（局部具有欧氏空间性质的空间定义为流形，而欧氏空间就是流形最简单的实例）学习等。其次是流形或子空间从一个扩展到多个的问题，即考虑处理的数据集采样于多个欧氏空间的混合。子空间聚类（又称为子空间分割，假设数据分布于若干个低维子空间的并集）是将数据按某种分类准则划分到其所属的子空间的过程。通过子空间聚类，可以将来自同一子空间中的数据归为一类，再由同类数据可以提取相应子空间的相关性质。子空间聚类的求解方法包括代数方法、迭代方法、统计学方法以及基于谱聚类的方法。在众多算法中，基于谱聚类的方法在近几年较为流行，通常情况下使用这类方法一般都能得到正确的分类结果，其中代表性的谱聚类子空间分割方法包括低秩表示和稀疏表示等。假设数据的结构为混合多流形，因为多数境况下数据来自混合子空间。虽然也有些实际问题的数据并不符合混合子空间结构的假设，但这种境况处理相对简单。此外，混合流形不全是子空间的情况，数据往往具有更复杂的结构，分析这种数据具有更大的挑战性。本文在几何结构分析问题中假设数据分布在多个维数不等的流形上，其特殊情况是数据分布在多个线性子空间上。下面对问题进行简要重述：1.附件一中1.mat中有一组高维数据（.mat所存矩阵的每列为一个数据点，以下各题均如此），数据结构未知，需要使用合适的方法将该组数据分成两类。2.图1(a)为两条交点不在原点且互相垂直的两条直线，将其分为两类；图1(b)为一个平面和两条直线，需要按要求将其分为三类。图1(c)为两条不相交的二次曲线，按要求将其分为两类。图1(d)为两条相交的螺旋线，结构相对复杂需按要求将其分为两类。(a)(b)-101-1-0.500.51-0.8-0.6-0.4-0.200.20.40.60.84(c)(d)图13.解决以下三个实际应用中的子空间聚类问题：（a）如图2（a）所示，使用适当的方法将图2（a）中十字上的点分成两类。（b）图2（b）显示了物体运动视频中的一帧，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，使用适当方法将这些特征点轨迹分成三类。(a)(b)图2（c）3c.mat中的数据为两个人在不同光照下的人脸图像共20幅（X变量的每一列为拉成向量的一幅人脸图像），需要将这20幅图像分成两类。4.解答如下两个实际应用中的多流形聚类问题图3(a)分别显示了圆台的点云，将点按照其所在的面分开(即圆台按照圆台的顶、底、侧面分成三类)。图3(b)是机器工件外部边缘轮廓的图像，将轮廓线中不同的直线和圆弧分类，类数自定。5(a)(b)图32.模型的假设1、假设本文中题目数据的噪声分布都处于分析中的理想状态；2、人脸数据、运动序列都来自于单独的子空间；3、在计算算法运行时间的时候假设计算机每次计算的时间均相同；3.符号说明符号符号说明id数据点MRM维空间D干净数据MNR×MN×维空间S相似度矩阵ijZ表示系数11ℓ范数F2ℓ范数,pq混合范数，()1/1/,qppjiijpqX=ΣΣ6*核范数()Zσ矩阵Z的奇异值构成的向量ZC系数矩阵Z的约束集合λ正则化参数()FE数据项或者保真项()RZ正则项或者惩罚项,,,YWPQ拉格朗日乘子矩阵μ罚参数*Z最优近似解G无向图V无向图顶点E无向图顶点之间的边llD×度矩阵RF→R到F的映射(),Kxy核函数()xφ变换函数ijp相似结构体iΘ数切线空间o可调参数()Knnx与x相似的聚类()iNd数据id在该子空间的最近邻域x∑局部样本协方差矩阵mθ模型参数7mμ数据的鲁棒均值y潜变量mε噪声iα加权系数iϕ基向量Is抽样因子()rank矩阵的秩SSC稀疏子空间聚类LRR低秩子空间聚类SVD奇异值分解PCA主成分分析Ncut规范化分割法4.问题的分析根据题目要求本文主要讨论子空间聚类相关问题。在过去的二十年中，解决子空间聚类问题的方法层出不穷，根据算法的原理可以将这些方法分为四大类，即统计算法，迭代算法，代数算法以及基于谱聚类框架的方法。在本文当中，我们在谱聚类算法的基本框架上进行了进一步研究，包括稀疏子空间聚类（SparseSubspaceClustering，SSC），低秩表示（LowRankRepresentation，LRR）及在此基础之上建立的推广模型。问题一中要求对来自于两个独立子空间的高维数据进行聚类。本文主要采用谱聚类方法，该类算法基于相似矩阵进行聚类。由于谱聚类算法的聚类分割效果的好坏几乎完全依赖于相似矩阵的质量，因此，相似矩阵的好坏直接影响聚类效果。所以，这里最主要的过程就是建立给定高维数据的空间表示模型，寻求其在低维空间的表示系数，然后根据表示系数矩阵构造出相似度矩阵，最后对相似度矩阵运用谱聚类方法，如规范化割（Normalizedcut，Ncut）获得数据的聚类结果。稀疏子空间聚类的基本框架如图4所示。这也是本文解决题目问题的基础。8图4稀疏子空间聚类的基本框架对于问题二中的问题，其中，图1（a）中的数据来自于二维空间中两条相互垂直的直线，显然，这些数据虽然是来自两个仿射空间，但是两者相互垂直，因此可以按照问题一中的求解方式进行解答。然而图（b）中为一个平面和两条直线，这是一个不满足独立子空间关系的情况。图（c）中为两条曲线，在二维空间中它们不是非线性的结构。图（d）中两条螺纹曲线之间拥有显著交叉点，需要进行分类的数据来源于不同的两个流形结构。因此如果仍然采用原有的谱聚类方法，对于后面三个问题的聚类结果将无法满足题目要求。在前文中，基于本文所提出的改进聚类算法，能够得到较好的子空间分割概率。但是要基于一个基本的前提，即所分类的数据来自于独立子空间这个条件。然而，在本题目问题（b）、问题（c）和问题（d）中都不是完全满足该条件的，因此为了成功对以上情况进行聚类，本文将对上述算法进行改进。本文主要采用两种方法解决上述问题。第一种方法是针对在目前的空间内不存在非独立可分的线性子空间的情况。此时，可行的解决方案是向高维空间转化，使其变得线性可分，具体方法是通过核映射的思想改进模型的构建，从而使不处于独立子空间的数据在特征空间内变得线性可分。第二种方法是针对问题中分类的数据来自于混合流形的情况，此时不同流形体类间存在明显交叉，那么相似度矩阵就会因为极差的两两相似度而发生错误分类的情况。传统的谱聚类方法在属于不同类的相似值相对较低时才有效。因此传统方法对于这种交叉情况并不适合。对于此问题，我们的基础想法是结合采样数据的部分原始信息和可靠的几何信息来构造合适的相似度矩阵，进而得到正确的聚类。具体来讲，虽然整体上看图（d）数据位于或者靠近于多个平滑非线性流形，但局部上每个数据点和它的邻近点都位于该流形的一条线性路径上。此外，在每个点处的切线空间为非线性流形的局部集合结构提供了很好的低维线性近似。显而易见的是，在不同流形的交叉区域内，同一个流形上的数据点拥有相似的局部切线空间，而不同流形上的点数据的局部切线空间是不相似的。因此，此类局部几何信息可以用于帮助构造相似矩阵。对于相对较远的点数据，我们很难只用局部几何信息判断它们是否属于同一个流形，