韓陽

摘要：在大數(shù)據(jù)的時(shí)代，面對(duì)著大量的多流形數(shù)據(jù)，對(duì)多流形數(shù)據(jù)的結(jié)構(gòu)分析進(jìn)行研究是十分有必要的。為了提高對(duì)多流形數(shù)據(jù)的分析能力，在已有的聚類技術(shù)基礎(chǔ)上，結(jié)合流形學(xué)習(xí)的方法和譜聚類的方法，發(fā)展出了譜多流形聚類方法。而在研究多流形數(shù)據(jù)的結(jié)構(gòu)以及譜多流形聚類的基礎(chǔ)上，又提出了稀疏譜聚類方法來進(jìn)一步改進(jìn)對(duì)多流形數(shù)據(jù)的結(jié)構(gòu)分析研究。

關(guān)鍵詞：多流形數(shù)據(jù)；數(shù)據(jù)幾何結(jié)構(gòu)分析；譜聚類；譜多流形聚類；稀疏譜多流形聚類

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

現(xiàn)今，我們已經(jīng)進(jìn)入了大數(shù)據(jù)的時(shí)代。在這個(gè)技術(shù)飛速進(jìn)步，信息爆炸的時(shí)代，數(shù)據(jù)的量從K到M，從M到G，從G到T，從T到P……。隨著數(shù)據(jù)量的迅速增加，對(duì)分析方法的需求也有了進(jìn)一步的增加。而在對(duì)數(shù)據(jù)的分析中，一個(gè)重要的方向是將數(shù)據(jù)集中屬于不同集合的數(shù)據(jù)分開，這也就是所謂的聚類分析[1]。傳統(tǒng)的聚類方法，例如，K均值聚類，即通過比較所有點(diǎn)到每個(gè)類的中心距離與重置類中心的方法，已經(jīng)不能夠滿足解決許多問題的實(shí)際需求。

在對(duì)實(shí)際問題的分析中，可以發(fā)現(xiàn)，有許多的數(shù)據(jù)集，實(shí)質(zhì)上是由多個(gè)幾何結(jié)構(gòu)組合而成。幾何結(jié)構(gòu)分析已被廣泛應(yīng)用于對(duì)象識(shí)別、圖像分類等模式識(shí)別和分類問題。同時(shí)，對(duì)于高維數(shù)據(jù)的相關(guān)性分析、聚類分析等的基本問題而言，基于結(jié)構(gòu)的分析也非常重要。而流形，在數(shù)學(xué)中就是用于描述幾何結(jié)構(gòu)的，并且為研究各種維度下曲線、曲面的可微性提供了最一般的抽象[2，3]。流形的微觀結(jié)構(gòu)使得它能夠容納微分結(jié)構(gòu)，從而可以用局部線性去近似它；而它的宏觀結(jié)構(gòu)卻又使得它可以作為對(duì)抗局部擾動(dòng)的理想數(shù)學(xué)模型。因此，對(duì)多流形數(shù)據(jù)的結(jié)構(gòu)分析進(jìn)行研究是十分有必要的。

2 背景介紹

對(duì)于多流形數(shù)據(jù)，其中不存在交疊混合的情況相對(duì)而言比較少，而且由于不相交的情況相對(duì)比較簡單，用傳統(tǒng)的聚類方法即可解決，本文不再過多討論。實(shí)際中存在困難的，是多流形交疊混合的情況。在現(xiàn)實(shí)環(huán)境中，尤其是機(jī)器視覺中，大量存在需要對(duì)多流形數(shù)據(jù)進(jìn)行識(shí)別的問題?，F(xiàn)在的流形學(xué)習(xí)算法能處理的情況還比較弱，而前提假設(shè)的條件比較強(qiáng)，特別是對(duì)于不同維數(shù)的多流形混合的問題，目前還沒有完全解決的方法。而此又恰恰是模式識(shí)別中一個(gè)合理且常見的情況。雖然針對(duì)多流形交疊混合的非線性學(xué)習(xí)已經(jīng)存在許多成熟的模型，如ISOMAP、譜聚類（SC）等等，但都有各自缺陷[4-7]：

ISOMAP方法能夠正確地將靠近流形交疊的部分樣本點(diǎn)進(jìn)行聚類，但是僅限于流形交疊部分附近的樣本點(diǎn)。這是由其使用測(cè)地線做相似性度量的性質(zhì)所導(dǎo)致的，因此即使兩類樣本集并不相交也不一定能進(jìn)行正確的區(qū)分。

譜聚類（SC）的情況則與前述的ISOMAP正相反，能正確區(qū)分間隔的不同類樣本集，但是對(duì)于流形交疊處附近的樣本點(diǎn)則表現(xiàn)不佳。

此外，由于流形空間一般被認(rèn)為是局部具有歐氏空間性質(zhì)的拓?fù)淇臻g，因此可以直觀上認(rèn)為是將多個(gè)線性空間拼接起來形成一個(gè)近似非線性流形空間[2，3]。

4 實(shí)驗(yàn)分析

使用實(shí)驗(yàn)分析常用的圖1，其是視頻中的一幀，有三個(gè)不同運(yùn)動(dòng)的特征點(diǎn)軌跡被提取出來，需要這些特征點(diǎn)軌跡分成三類。在實(shí)驗(yàn)中，分別了使用傳統(tǒng)的PCA+K-means方法、譜多流形聚類和稀疏譜多流形聚類的方法。傳統(tǒng)的PCA+K-means方法，無法很好分出位置相鄰但不屬于同一流形的點(diǎn)集；譜多流形聚類對(duì)流形區(qū)域做了處理，但因?yàn)閮蓚€(gè)流形之間存在距離過近的部分，而且分錯(cuò)區(qū)域與該流形區(qū)域大部分點(diǎn)距離較大，雖然結(jié)果有改善，但是還有錯(cuò)誤；稀疏譜多流形聚類相比譜多流形聚類又有了改進(jìn)，實(shí)現(xiàn)了正確分類。

5 結(jié)束語

隨著大數(shù)據(jù)時(shí)代的到來，多流形數(shù)據(jù)的結(jié)構(gòu)分析越來越成為重要的課題。與傳統(tǒng)方法相比，新的方法不斷涌現(xiàn)，也能夠更好地解決問題。譜多流形聚類的出現(xiàn)，就是一個(gè)很好的例子。不過，我們?nèi)匀恍枰粩喔倪M(jìn)我們的方法，去進(jìn)一步滿足解決實(shí)際問題的需要。雖然我們提出了稀疏譜多流形聚類來改進(jìn)譜多流形聚類，但是后續(xù)依然有廣泛的空間需要進(jìn)一步的研究。

參考文獻(xiàn)：

[1] Richard O. Duda， Peter E. Hart， David G. Stork. 《模式分類》[M]，北京：機(jī)械工業(yè)出版社， 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）：2765–2781.

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