多流形結(jié)構(gòu)數(shù)據(jù)建模與應(yīng)用研究

胡一帆，胡友彬，李紹輝，趙陽（.解放軍理工大學(xué)氣象海洋學(xué)院，南京　0；.北京應(yīng)用氣象研究所，北京　000）

多流形結(jié)構(gòu)數(shù)據(jù)建模與應(yīng)用研究

胡一帆1，胡友彬1，李紹輝1，趙陽2
（1.解放軍理工大學(xué)氣象海洋學(xué)院，南京211101；2.北京應(yīng)用氣象研究所，北京100101）

0　引言

我們已經(jīng)進(jìn)入了一個(gè)信息爆炸的時(shí)代，海量的數(shù)據(jù)不斷產(chǎn)生，以至數(shù)據(jù)的分析和處理方法成為了諸多問題成功解決的關(guān)鍵，涌現(xiàn)出了大量的數(shù)據(jù)分析方法。幾何結(jié)構(gòu)分析是進(jìn)行數(shù)據(jù)處理的重要基礎(chǔ)，已經(jīng)被廣泛應(yīng)用在人臉識別、手寫體數(shù)字識別、圖像分割、運(yùn)動分割等模式識別和計(jì)算機(jī)視覺問題中。更一般地，對于高維數(shù)據(jù)的相關(guān)性分析、聚類分析等基本問題，結(jié)構(gòu)分析也格外重要。

在實(shí)際問題中很多數(shù)據(jù)具備復(fù)雜的結(jié)構(gòu)。例如，對于具有多個(gè)混合子空間結(jié)構(gòu)的特征點(diǎn)數(shù)據(jù)，判斷哪些特征點(diǎn)屬于同一子空間是其能否有效解決的關(guān)鍵。從參考文獻(xiàn)可以看到，傳統(tǒng)的結(jié)構(gòu)分析算法不能很好地處理復(fù)雜結(jié)構(gòu)的樣本集特征提取和聚類問題，而流形學(xué)習(xí)（Manifold Learning）方法能很好地處理此類問題。本文基于流形學(xué)習(xí)的理論，提出了種子生長模型，探索了多流形結(jié)構(gòu)數(shù)據(jù)聚類的有效方法。

1　流形學(xué)習(xí)方法概述

流形（Manifoldness）是描述許多自然現(xiàn)象的一種空間形式，是局部具有歐幾里得空間性質(zhì)的空間，也是歐幾里得空間中的曲線、曲面等概念的推廣。流形學(xué)習(xí)于2000年在著名雜志Science上被首次提出，之后逐漸成為了研究熱點(diǎn)。它試圖學(xué)習(xí)出高維數(shù)據(jù)樣本空間中嵌入的低維子流形，并求出相應(yīng)的嵌入映射，以實(shí)現(xiàn)維數(shù)約簡和數(shù)據(jù)可視化。

流形學(xué)習(xí)可分為線性算法和非線性算法，非線性流形學(xué)習(xí)算法包括等距映射（Isomap）、拉普拉斯特征映射（Laplacian Eigenmaps，LE）、局部線性嵌入（Locally-Linear Embedding，LLE）等。而線性方法則是對非線性方法的線性擴(kuò)展，如主成分分析 （Principal Component Analysis，PCA）、多維尺度變換（Multi Dimensional Scaling，MDS）等。

不同于單流形學(xué)習(xí)，多流形結(jié)構(gòu)數(shù)據(jù)建模的目的是把輸入數(shù)據(jù)集分為若干個(gè)類別，使得每個(gè)類別中的數(shù)據(jù)點(diǎn)都來自單一、簡單、低維嵌入流形，如圖1所示（圖中數(shù)據(jù)建模為三個(gè)低維流形）。它有以下三個(gè)目標(biāo)：分析子流形的數(shù)目和各自的維數(shù)；數(shù)據(jù)的劃分（數(shù)據(jù)屬于不同的低維流形）；數(shù)據(jù)在對應(yīng)的低維流形中的嵌入。

2　基本假設(shè)和符號說明

本文為處理多流形結(jié)構(gòu)數(shù)據(jù)設(shè)計(jì)了種子生長模型，通過迭代更新當(dāng)前種子與分類集合，達(dá)到聚類的目的。基本假設(shè)如下：

圖1　多流形結(jié)構(gòu)數(shù)據(jù)建模

（1）數(shù)據(jù)分布在多個(gè)維數(shù)不等的流形上，即任意選取一個(gè)樣本si，該樣本一定分布于某一個(gè)流形上；

（2）高維數(shù)據(jù)都是均勻采樣于一個(gè)高維歐氏空間中，通過流形學(xué)習(xí)找到相應(yīng)嵌入映射，從而實(shí)現(xiàn)維數(shù)約簡。

以下是模型中出現(xiàn)的符號說明（向量符號加箭頭，集合加粗體）：

P判定后與當(dāng)前種子同類的樣本集合

U全體樣本集合

Si當(dāng)前生長過程的第i個(gè)種子

r種子生長半徑

Rule種子生長規(guī)則 （評價(jià)指標(biāo)包括向量距離vd，向量夾角θ，法向量）

dtheta控制種子生長方向的閾值 （對應(yīng)Rule中的評價(jià)指標(biāo)）

dist（→A，→B）向量→A與向量→B的距離

Sn'與當(dāng)前種子距離小于r的樣本集合的子集，取距離最小的前n個(gè)樣本構(gòu)成

Sn"與當(dāng)前種子距離大于r的樣本集合的子集，取距離最小的前n個(gè)樣本構(gòu)成

n搜索范圍

3　模型的建立與分析

圖2包含兩條交叉的“線”，可以看作是一種一維多流形結(jié)構(gòu)數(shù)據(jù)，現(xiàn)以它為例建立模型。

圖2　一維多流型結(jié)構(gòu)數(shù)據(jù)

建模思路是，模擬種子的生長傳播過程對多流形結(jié)構(gòu)數(shù)據(jù)進(jìn)行分類，即建立種子生長模型。建模過程是，選一個(gè)樣本di作為初始種子s0，按照一定的生長規(guī)則以所在的流形M為載體不斷生長 （搜索與傳播），種子si傳播到的樣本點(diǎn)dn將被分到一類，通過種子si的不斷迭代更新，最終遍歷完整個(gè)流形M，完成所有樣本的分類。直觀描述見表1。

表1　種子生長模型

圖3　初始種子的選擇

根據(jù)建模思想，設(shè)計(jì)種子生長算法如圖4所示。

圖4　種子生長算法流程圖

應(yīng)用上述算法，得到聚類結(jié)果如圖5所示。從圖中可以看到，除了少數(shù)樣本點(diǎn)沒有劃分或劃分有誤外，幾乎所有的樣本點(diǎn)都被成功地劃分為“紅”、“藍(lán)”兩類，構(gòu)成了紅藍(lán)兩條相交線。這說明在類似的多線性子空間數(shù)據(jù)中，種子生長模型能夠較好地解決子空間聚類問題。

圖5　聚類結(jié)果

圖6包括了一個(gè)“面”以及兩條“線”，可以看作是一種二維多流形結(jié)構(gòu)數(shù)據(jù)，現(xiàn)以它為例建立模型。

圖6　二維多流形結(jié)構(gòu)數(shù)據(jù)

圖7　建模思路

建模思路是，先按照種子生長模型（以法向量為評判指標(biāo)）對混合多流形結(jié)構(gòu)數(shù)據(jù)進(jìn)行粗分類，將“面”與兩條“線”區(qū)分開來；粗分類之后，再應(yīng)用上一節(jié)的種子生長算法（以向量夾角為評判指標(biāo)）對兩條“線”進(jìn)行聚類。直觀描述見圖7。

當(dāng)樣本點(diǎn)以高密度呈現(xiàn)在一個(gè)近似平面或曲面的流形上時(shí)，局部特征可能會高低起伏，導(dǎo)致幾何特性在局部區(qū)域并不明顯。所以，為了盡可能準(zhǔn)確地體現(xiàn)某個(gè)區(qū)域的特征，需要找到一個(gè)“最可靠法向量”。我們知道，在某一個(gè)區(qū)域中，應(yīng)盡量選取從當(dāng)前種子出發(fā)模值最大的兩個(gè)向量來生成法向量，才能最可靠地體現(xiàn)該區(qū)域的幾何特征。如圖8所示，兩條紅色向量所構(gòu)成的法向量比黑色向量更“可靠”。

圖8　選取“最可靠法向量”

應(yīng)用上述改進(jìn)的種子生長算法，得到聚類結(jié)果如圖9所示。從圖中可以看到，同樣除了少數(shù)樣本點(diǎn)沒有劃分或劃分有誤，幾乎所有的樣本點(diǎn)都被成功地劃分為“紅”、“綠”、“藍(lán)”三類，構(gòu)成了相交的藍(lán)色平面和紅綠兩線。這說明種子生長模型也能夠很好地解決類似的混合多流形結(jié)構(gòu)數(shù)據(jù)的分類問題，即同時(shí)適用于高維數(shù)據(jù)和低維數(shù)據(jù)。

圖9　聚類結(jié)果

4　模型的應(yīng)用研究

受實(shí)際條件的制約，在工業(yè)測量中往往需要非接觸測量的方式，視覺重建是一類重要的非接觸測量方法。特征提取是視覺重建的一個(gè)關(guān)鍵環(huán)節(jié)，如圖10所示，其中十字便是特征提取環(huán)節(jié)中處理得到的，十字上的點(diǎn)的位置信息已經(jīng)提取出來，為了確定十字的中心位置，一個(gè)可行的方法是先將十字中的點(diǎn)按照“橫”和“豎”分兩類。

圖10　工業(yè)測量的實(shí)例

該問題是低維多流形數(shù)據(jù)的一種特殊情況，即數(shù)據(jù)采樣于兩個(gè)獨(dú)立的線性子空間，直觀的看就是兩個(gè)十字交叉的條帶，同樣可以建立種子生長模型。但是由于現(xiàn)實(shí)數(shù)據(jù)樣本的密集性以及噪音所帶來的孤立點(diǎn)這兩個(gè)特性，還需要考慮三個(gè)問題：

（1）如果離種子的距離在閾值之內(nèi)的點(diǎn)過多，種子生長會失控，模型求解的效率也會大大降低。

（2）要控制種子的生長方向，如果種子向四周360度生長，則原有模型的方向判別式將會失效。

（3）種子最開始不能種在孤立點(diǎn)上，否則將不會沿著所在的流形生長。

為了解決上述問題，我們對模型進(jìn)行了一些改進(jìn)：

（1）取前n個(gè)距離種子最近的樣本參與算法，也就是通過控制每一次搜查的樣本個(gè)數(shù)來避免高密度數(shù)據(jù)帶來的混亂。

（2）為了避免初始種子種在孤立點(diǎn)上，用計(jì)算歐氏距離的方式先去除孤立點(diǎn)。

（3）由于樣本過于密集，顯然有一些樣本會被遺忘，即永遠(yuǎn)不會排入前n位參與分類，對于這些沒有被分類的點(diǎn)，采用蒙特卡洛方法處理。

初步分類過程如圖11所示。

圖11　初步分類流程圖

初步分類沒有處理的樣本將在后處理部分進(jìn)行分類?？梢岳妹商乜宸椒ㄌ幚磉@些少數(shù)樣本點(diǎn)：以樣本點(diǎn)為中心，設(shè)置搜索半徑r，若圓中A類的點(diǎn)居多，則認(rèn)為該樣本點(diǎn)與A類有更大的相似性，將其歸為A類，否則歸為B類。

后處理過程如圖12所示。

最后結(jié)果如圖13所示。從生長軌跡可以看出，種子以兩個(gè)各自有規(guī)律的流形為載體，根據(jù)它所在流形的規(guī)律自由生長。從聚類結(jié)果可以看出，高數(shù)據(jù)密集性的樣本點(diǎn)（藍(lán)色部分）被成功地劃分為“紅”、“綠”兩類，構(gòu)成了紅綠兩個(gè)相交條帶。由此可以確定十字中心的位置，以實(shí)現(xiàn)工業(yè)測量的目的，從而很好地驗(yàn)證了種子生長模型處理問題的有效性和在實(shí)踐中的應(yīng)用能力。

圖12　后處理部分流程圖

5　結(jié)語

機(jī)器學(xué)習(xí)的一大優(yōu)點(diǎn)就是可以靈活地構(gòu)建由大量參數(shù)刻畫的模型，由機(jī)器自動處理數(shù)據(jù)，使得信息的提取與分類過程盡可能地實(shí)現(xiàn)自動化。流形學(xué)習(xí)是機(jī)器學(xué)習(xí)理論中的一種基本方法，它從觀測到的現(xiàn)象中尋找事物的本質(zhì)，找到產(chǎn)生事物的內(nèi)在規(guī)律。模型一表明，種子生長算法可以很好地解決多線性子空間中的數(shù)據(jù)聚類問題；模型二表明，種子生長算法可適用于高維數(shù)據(jù)和低維數(shù)據(jù)，具有解決問題的一般性。

圖13　生長軌跡和聚類結(jié)果

當(dāng)前信息處理領(lǐng)域的實(shí)際應(yīng)用中，往往會產(chǎn)生海量的數(shù)據(jù)，并呈現(xiàn)出高維度、非線性等特征，迫切需要對這些大數(shù)據(jù)進(jìn)行有效的分析。種子生長模型對工業(yè)測量實(shí)例的應(yīng)用，表現(xiàn)了較強(qiáng)的應(yīng)用能力和實(shí)用價(jià)值，可以作為多流型結(jié)構(gòu)數(shù)據(jù)聚類的一種有效途徑。必須指出，本文尚存在需要研究改進(jìn)的地方。在尋找控制種子生長的閾值上，只考慮了向量距離和向量方向，如果能找到更多的閾值控制變量，結(jié)果會更加準(zhǔn)確。

［1］R.Basri，D.W.Jacobs.Lambertian Reflectance and Linear Subspaces.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（2）：218-233.

［2］R.Vidal.Subspace Clustering.IEEE Signal Processing Magazine，2011，28（2）：52-68.

［3］G.Liu，Z.Lin，S.Yan，J.Sun，Y.Yu，Y.Ma.Robust Recovery of Subspace Structures by Low-Rank Representation.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（1）：171-184.

［4］E.Elhamifar，R.Vidal.Sparse Subspace Clustering:Algorithm，Theory，and Applications.IEEE Transactions on Pattern Analysis and Machine Intelligence，35（11）:2765-2781，2013.

［5］Y.Wang，Y.Jiang，Y.Wu，Z.Zhou.Spectral Clustering on Multiple Manifolds.IEEE Transactions on Neural Networks，2011，22（7）: 1149-1161.

Multiple Manifold Data；Seeds Growth Model；Judge Standard；Subspace Clustering

Research on Modeling and Application of Multiple Manifold Structure Data

HU Yi-fan1，HU You-bin1，LI Shao-hui1，ZHAO Yang2
（1.College of Marine Meteorological，The PLA University of Science and Technology，Nanjing 211101；2.Beijing Meteorological Institute，Beijing 100101）

1007-1423（2015）35-0008-06

10.3969/j.issn.1007-1423.2015.35.002

胡一帆（1991-），男，江蘇徐州人，在讀碩士研究生，研究方向?yàn)樾盘柵c信息處理

胡友彬（1967-），男，江蘇鹽城人，碩士，副教授

李紹輝（1992-），男，河南焦作人，在讀碩士研究生，研究方向?yàn)榇髿廨椛渑c遙感

趙陽（1991-），男，陜西咸陽人，在讀碩士研究生，研究方向?yàn)樾l(wèi)星遙感技術(shù)與應(yīng)用

2015-11-06

2015-11-15

研究多流形結(jié)構(gòu)的復(fù)雜數(shù)據(jù)的聚類方法，在流形學(xué)的基礎(chǔ)上提出種子生長模型。對一維和二維多流形結(jié)構(gòu)數(shù)據(jù)的建模和分析，表明該模型能夠有效地解決類似的混合子空間聚類問題。以工業(yè)測量中的實(shí)例為研究對象建立模型，實(shí)驗(yàn)結(jié)果達(dá)到工業(yè)測量的目的，驗(yàn)證該模型在實(shí)際應(yīng)用中的可行性。

多流形數(shù)據(jù)；種子生長模型；評判指標(biāo)；子空間聚類

Studies the clustering method of multiple manifold structure complex data，and proposes the seeds growth model on the basis of the manifold learning.One-dimensional and two-dimensional multiple manifold structure data modeling and their analysis，shows that the model can effectively solve the similar mixed subspace clustering problem.Takes the living example in Industrial measurement as the object of the study for modeling，the result achieves the purpose of industrial measurement，and verifies the feasibility of the model in practical application.