多流形数据的结构分析研究

摘要：在大数据的时代，面对着大量的多流形数据，对多流形数据的结构分析进行研究是十分有必要的。为了提高对多流形数据的分析能力，在已有的聚类技术基础上，结合流形学习的方法和谱聚类的方法，发展出了谱多流形聚类方法。而在研究多流形数据的结构以及谱多流形聚类的基础上，又提出了稀疏谱聚类方法来进一步改进对多流形数据的结构分析研究。

关键词：多流形数据；数据几何结构分析；谱聚类；谱多流形聚类；稀疏谱多流形聚类

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）09-0003-03

Research on Structure Analysis of Multi-Manifold Data

HAN Yang

（College of Electronics and Information Engineering， Tongji University， Shanghai 201804， china）

Abstract： In the era of big data， it is very necessary to study the structure analysis method of multi-manifold data， facing a large number of multi-manifold data. To improve the analysis ability of the multi-manifold data， the spectral manifold clustering method is developed， which based on the existing clustering techniques and combined with manifold learning method and spectral clustering method. On the basis of studying the structure of multi manifold data and the clustering of spectral manifold， the sparse spectral clustering method is proposed to improve the structure analysis of multi manifold data.

Key words： multi-manifold data；data geometry structural analysis；spectral clustering；spectral clustering on multiple manifolds； sparse spectral clustering on multiple manifolds

1 概述

现今，我们已经进入了大数据的时代。在这个技术飞速进步，信息爆炸的时代，数据的量从K到M，从M到G，从G到T，从T到P……。随着数据量的迅速增加，对分析方法的需求也有了进一步的增加。而在对数据的分析中，一个重要的方向是将数据集中属于不同集合的数据分开，这也就是所谓的聚类分析[1]。传统的聚类方法，例如，K均值聚类，即通过比较所有点到每个类的中心距离与重置类中心的方法，已经不能够满足解决许多问题的实际需求。

在对实际问题的分析中，可以发现，有许多的数据集，实质上是由多个几何结构组合而成。几何结构分析已被广泛应用于对象识别、图像分类等模式识别和分类问题。同时，对于高维数据的相关性分析、聚类分析等的基本问题而言，基于结构的分析也非常重要。而流形，在数学中就是用于描述几何结构的，并且为研究各种维度下曲线、曲面的可微性提供了最一般的抽象[2，3]。流形的微观结构使得它能够容纳微分结构，从而可以用局部线性去近似它；而它的宏观结构却又使得它可以作为对抗局部扰动的理想数学模型。因此，对多流形数据的结构分析进行研究是十分有必要的。

2 背景介绍

对于多流形数据，其中不存在交叠混合的情况相对而言比较少，而且由于不相交的情况相对比较简单，用传统的聚类方法即可解决，本文不再过多讨论。实际中存在困难的，是多流形交叠混合的情况。在现实环境中，尤其是机器视觉中，大量存在需要对多流形数据进行识别的问题。现在的流形学习算法能处理的情况还比较弱，而前提假设的条件比较强，特别是对于不同维数的多流形混合的问题，目前还没有完全解决的方法。而此又恰恰是模式识别中一个合理且常见的情况。虽然针对多流形交叠混合的非线性学习已经存在许多成熟的模型，如ISOMAP、谱聚类（SC）等等，但都有各自缺陷[4-7]：

ISOMAP方法能够正确地将靠近流形交叠的部分样本点进行聚类，但是仅限于流形交叠部分附近的样本点。这是由其使用测地线做相似性度量的性质所导致的，因此即使两类样本集并不相交也不一定能进行正确的区分。

谱聚类（SC）的情况则与前述的ISOMAP正相反，能正确区分间隔的不同类样本集，但是对于流形交叠处附近的样本点则表现不佳。

此外，由于流形空间一般被认为是局部具有欧氏空间性质的拓扑空间，因此可以直观上认为是将多个线性空间拼接起来形成一个近似非线性流形空间[2，3]。

4 实验分析

使用实验分析常用的图1，其是视频中的一帧，有三个不同运动的特征点轨迹被提取出来，需要这些特征点轨迹分成三类。在实验中，分别了使用传统的PCA+K-means方法、谱多流形聚类和稀疏谱多流形聚类的方法。传统的PCA+K-means方法，无法很好分出位置相邻但不属于同一流形的点集；谱多流形聚类对流形区域做了处理，但因为两个流形之间存在距离过近的部分，而且分错区域与该流形区域大部分点距离较大，虽然结果有改善，但是还有错误；稀疏谱多流形聚类相比谱多流形聚类又有了改进，实现了正确分类。

5 结束语

随着大数据时代的到来，多流形数据的结构分析越来越成为重要的课题。与传统方法相比，新的方法不断涌现，也能够更好地解决问题。谱多流形聚类的出现，就是一个很好的例子。不过，我们仍然需要不断改进我们的方法，去进一步满足解决实际问题的需要。虽然我们提出了稀疏谱多流形聚类来改进谱多流形聚类，但是后续依然有广泛的空间需要进一步的研究。

参考文献：

[1] Richard O. Duda， Peter E. Hart， David G. Stork. 《模式分类》[M]，北京：机械工业出版社， 2013， P94-96.

[2] R. Souvenir， R. Pless. Manifold clustering[C]. in Proceedings of the 10th International Conference on Computer Vision （ICCV 2005）， 2005： 648-653.

[3] Y. Wang， Y. Jiang， Y. Wu， Z.-H. Zhou， Multi-manifold clustering[C]， 11th Pacific Rim International Conference on Artificial Intelligence（PRICAI 2010）， 2010：280-291.

[4] Tenenbaum J B， V. de Silva， et al. A global geometric framework for nonlinear dimensionality reduction， 2000， 290（5500）：2319-2323

[5] A. Ng， M. Jordan， Y. Weiss， On spectral clustering： Analysis and an algorithm[C]. in Proc. Adv. Neural Inf. Process. Syst. 14， 2001：849-856.

[6] Shay Deutsch， Gérard Medioni. Intersecting Manifolds： Detection， Segmentation，and Labeling[C]. IJCAI， 2015：3445-3452.

[7] J. Shi， J. Malik， Normalized cuts and image segmentation[J]. IEEE Transactions Pattern Analysis Machine Intelligence， 2000，22（8）：888-905.

[8] Y. Wang， Y. Jiang， Y. Wu， Z.-H. Zhou. Spectral clustering on multiple manifolds[J]. IEEE Transactions on Neural Networks， 2011， 22（7）：1149-1161.

[9] E. Elhamifar， R. Vidal. Sparse subspace clustering： Algorithm， theory， and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（11）：2765C2781.

[10] M. E. Tipping， C. M. Bishop， Mixtures of probabilistic principal component analyzers[J]， Neural Comput， 1999， 11（2）：443-482.