数据的多流形结构分析2

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

1、参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校上海交通大学参赛队号102481181.王齐晖队员姓名2.徐福梁3.胡子翔参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目数据的多流形结构分析摘要：在如今的信息爆炸时代，大数据分析已经成为了热门话题。本文所阐述的内容就是数据处理的一个重要方法——多流形结构分析。本文根据不同的子空[7]间聚类问题，使用稀疏子空间聚类(SparseSubspaceClustering,SSC),多流形谱[8]聚类(SpectralMulti-Manifold

2、Clustering,SMMC)及其改进算法，共同解决了所有问题。本文所做的主要创新工作和结论如下：第一，基于所给问题，验证和讨论了SSC和SMMC算法的适用范围。正如[7]文献中所说，SSC算法适用于多个线性子空间聚类，并不适用于非线性子空间的聚类。而SMMC算法的适用范围就相对较广，不仅适用于线性子空间聚类，而且对非线性子空间同样适用。SMMC的缺点也同样明显：（1）参数过多，对最佳算数的搜寻较为困难；（2）由于SMMC中引入了概率主成分分析，所以相同的参数偶尔会产生不同的结果；（3）SMMC同样不适用于复杂的混合流形子空间。针对（

3、2）中SMMC的不稳定结果，由于SMMC产生准确结果的概率较大，文中使用了投票的方法：多次运行SMMC程序，根据产生的结果投票，若某个点的第i个聚类标签(记为Label(i))的票数最多，则该点属于Label(i)。[9]第二，基于所给问题，讨论了局部线性嵌入(LocallyLinearEmbedding,LLE)对于高维子空间聚类的指导性意义。文献[9]中结论表明LLE能够降低数据维度，而不改变其局部结构。这说明通过LLE降低维度之后，若数据呈现线性分布，则数据在高维空间也是近似线性的。通过LLE可以处理高维子空间聚类。对于高维数据，

4、如第一题，第三题的(b)和(c)，文中会给出两类结果：直接使用高维数据聚类的结果和使用LLE降维（降到3维）之后聚类的结果。若两类结果不一样，如第三题的(b)，则以高维数据聚类的结果为准。、第三，本文改进了SMMC算法，使得SMMC算法能够很好地解决第四题中的两个混合子空间模型。改进的基本思想如下：（1）对于多个（大于两个）子空间的划分，首先分为2个子空间，然后根据划分的结果改进关系图的亲和矩阵，随后划分为3个子空间，依此类推，逐步划分为要求的子空间个数，命名为逐步多流形谱聚类(GraduallySpectralMulti-Manifo

5、ldClustering,GSMMC)。此方法的最主要思想就是把数据分为两个子空间比直接分为多个子空间更容易更准确；（2）探测直线：由于第四题的(b)图中，直线和圆弧组成方式相当复杂，而[12]直线又靠近噪声点，所以本文首先用RANSAC方法将图(b)中的那条较长的直线检测出来，并从数据集中剔除，剩余的模型更为简单。或者将结果作为第一次分类结果，在GSMMC中用来优化亲和矩阵，不过此种方法并没有获得比直接剔除更好的效果，所以有待更进一步地研究；另外，去除直线或线性子空间的影响，对所有的混合子空间模型的聚类都有重大意义。（3）增加数据维度

6、：为了更好地区分数据，可以给数据添加上新的一维或者两维；也可以在GMSSC中每迭代一次，根据划分结果增加维度。由于时间限制本文只是采用了一种较为粗糙和低效的增加维度的方式。若想要获得更一般，更有效的增维方法，需要进一步地研究。使用（1），就能很好地解决第四题的（a），使用（1）、（2）、（3）能够对第四题的（b）做出非常好的聚类。最后，基于本文所做的所有工作、结论和思想，希望对相关研究人员有所启发。关键词：稀疏子空间聚类，逐步多流形谱聚类，直线探测，增加数据维度目录一、问题重述..............................

7、................................................................................................-1-1.1引言.......................................................................................................................................-1-1.2问题的提出.....................

8、......................................................................................................-