2015年全国研究生数学建模大赛优秀论文B题3

参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校上海交通大学参赛队号10248118队员姓名1.王齐晖2.徐福梁3.胡子翔参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目数据的多流形结构分析摘要：在如今的信息爆炸时代，大数据分析已经成为了热门话题。本文所阐述的内容就是数据处理的一个重要方法——多流形结构分析。本文根据不同的子空间聚类问题，使用稀疏子空间聚类(SparseSubspaceClustering,SSC)[7],多流形谱聚类(SpectralMulti-ManifoldClustering,SMMC)[8]及其改进算法，共同解决了所有问题。本文所做的主要创新工作和结论如下：第一，基于所给问题，验证和讨论了SSC和SMMC算法的适用范围。正如文献[7]中所说，SSC算法适用于多个线性子空间聚类，并不适用于非线性子空间的聚类。而SMMC算法的适用范围就相对较广，不仅适用于线性子空间聚类，而且对非线性子空间同样适用。SMMC的缺点也同样明显：（1）参数过多，对最佳算数的搜寻较为困难；（2）由于SMMC中引入了概率主成分分析，所以相同的参数偶尔会产生不同的结果；（3）SMMC同样不适用于复杂的混合流形子空间。针对（2）中SMMC的不稳定结果，由于SMMC产生准确结果的概率较大，文中使用了投票的方法：多次运行SMMC程序，根据产生的结果投票，若某个点的第i个聚类标签(记为Label(i))的票数最多，则该点属于Label(i)。第二，基于所给问题，讨论了局部线性嵌入(LocallyLinearEmbedding,LLE)[9]对于高维子空间聚类的指导性意义。文献[9]中结论表明LLE能够降低数据维度，而不改变其局部结构。这说明通过LLE降低维度之后，若数据呈现线性分布，则数据在高维空间也是近似线性的。通过LLE可以处理高维子空间聚类。对于高维数据，如第一题，第三题的(b)和(c)，文中会给出两类结果：直接使用高维数据聚类的结果和使用LLE降维（降到3维）之后聚类的结果。若两类结果不一样，如第三题的(b)，则以高维数据聚类的结果为准。、第三，本文改进了SMMC算法，使得SMMC算法能够很好地解决第四题中的两个混合子空间模型。改进的基本思想如下：（1）对于多个（大于两个）子空间的划分，首先分为2个子空间，然后根据划分的结果改进关系图的亲和矩阵，随后划分为3个子空间，依此类推，逐步划分为要求的子空间个数，命名为逐步多流形谱聚类(GraduallySpectralMulti-ManifoldClustering,GSMMC)。此方法的最主要思想就是把数据分为两个子空间比直接分为多个子空间更容易更准确；（2）探测直线：由于第四题的(b)图中，直线和圆弧组成方式相当复杂，而直线又靠近噪声点，所以本文首先用RANSAC方法[12]将图(b)中的那条较长的直线检测出来，并从数据集中剔除，剩余的模型更为简单。或者将结果作为第一次分类结果，在GSMMC中用来优化亲和矩阵，不过此种方法并没有获得比直接剔除更好的效果，所以有待更进一步地研究；另外，去除直线或线性子空间的影响，对所有的混合子空间模型的聚类都有重大意义。（3）增加数据维度：为了更好地区分数据，可以给数据添加上新的一维或者两维；也可以在GMSSC中每迭代一次，根据划分结果增加维度。由于时间限制本文只是采用了一种较为粗糙和低效的增加维度的方式。若想要获得更一般，更有效的增维方法，需要进一步地研究。使用（1），就能很好地解决第四题的（a），使用（1）、（2）、（3）能够对第四题的（b）做出非常好的聚类。最后，基于本文所做的所有工作、结论和思想，希望对相关研究人员有所启发。关键词：稀疏子空间聚类，逐步多流形谱聚类，直线探测，增加数据维度目录一、问题重述..............................................................................................................................-1-1.1引言.......................................................................................................................................-1-1.2问题的提出...........................................................................................................................-1-二、问题分析..............................................................................................................................-4-2.1问题一...................................................................................................................................-4-2.2问题二...................................................................................................................................-4-2.3问题三...................................................................................................................................-4-2.4问题四...................................................................................................................................-4-三、符号说明..............................................................................................................................-5-四、模型建立与改进..................................................................................................................-6-4.1谱聚类...................................................................................................................................-6-4.2稀疏子空间聚类SSC...........................................................................................................-7-4.3多流形谱聚类SMMC..........................................................................................................-8-4.4局部线性嵌入LLE.............................................................................................................-10-4.5逐步多流形谱聚类GSMMC和增加数据维度................................................................-11-4.6RANSAC.............................................................................................................................-12-五、问题求解............................................................................................................................-15-5.1问题一——子空间独立.....................................................................................................-15-5.2问题二——低维空间中的子空间聚类问题和多流形聚类问题.....................................-16-5.3问题三——实际应用中的子空间聚类问题.....................................................................-20-5.4问题四——实际应用中的多流形聚类问题.....................................................................-24-六、评价与结论........................................................................................................................-30-七、参考文献............................................................................................................................-31-八、附录....................................................................................................................................-32--1-一、问题重述1.1引言一个人在不同光照下的人脸图像可以被一个低维子空间近似[1]，由此产生大量的数据降维方法被用来挖掘数据集的低维线性子空间结构，这类方法假设数据集采样于一个线性的欧氏空间[15]。但是，在实际问题中很多数据具备更加复杂的结构。针对单一子空间结构假设的后续讨论主要是两个方面，首先是从线性到非线性的扩展，主要的代表性工作包括流形（流形是局部具有欧氏空间性质的空间，欧氏空间就是流形最简单的实例）学习等。流形学习的出现，很好地解决了具有非线性结构的样本集的特征提取问题。然而流形学习方法通常计算复杂度较大，对噪声和算法参数都比较敏感，并且存在所谓的样本溢出问题。其次是流形或子空间从一个到多个的扩展，即假设数据集采样于多个欧氏空间的混合。由于混合流形不全是子空间的情况，数据往往具有更复杂的结构，分析这种数据具有更大的挑战性。基于谱聚类的方法仍然是处理该类