胡一帆，胡友彬，李紹輝，趙陽（.解放軍理工大學(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)入了一個信息爆炸的時代，海量的數(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ù)字識別、圖像分割、運動分割等模式識別和計算機視覺問題中。更一般地，對于高維數(shù)據(jù)的相關(guān)性分析、聚類分析等基本問題，結(jié)構(gòu)分析也格外重要。

在實際問題中很多數(shù)據(jù)具備復(fù)雜的結(jié)構(gòu)。例如，對于具有多個混合子空間結(jié)構(gòu)的特征點數(shù)據(jù)，判斷哪些特征點屬于同一子空間是其能否有效解決的關(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上被首次提出，之后逐漸成為了研究熱點。它試圖學(xué)習(xí)出高維數(shù)據(jù)樣本空間中嵌入的低維子流形，并求出相應(yīng)的嵌入映射，以實現(xiàn)維數(shù)約簡和數(shù)據(jù)可視化。

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

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

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

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

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

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

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

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

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

U全體樣本集合

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

r種子生長半徑

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

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

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

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

Sn"與當(dāng)前種子距離大于r的樣本集合的子集，取距離最小的前n個樣本構(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)行分類，即建立種子生長模型。建模過程是，選一個樣本di作為初始種子s0，按照一定的生長規(guī)則以所在的流形M為載體不斷生長 （搜索與傳播），種子si傳播到的樣本點dn將被分到一類，通過種子si的不斷迭代更新，最終遍歷完整個流形M，完成所有樣本的分類。直觀描述見表1。

表1　種子生長模型

圖3　初始種子的選擇

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

圖4　種子生長算法流程圖

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

圖5　聚類結(jié)果

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

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

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

圖9　聚類結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

圖11　初步分類流程圖

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

后處理過程如圖12所示。

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

圖12　后處理部分流程圖

5　結(jié)語

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

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

當(dāng)前信息處理領(lǐng)域的實際應(yīng)用中，往往會產(chǎn)生海量的數(shù)據(jù)，并呈現(xiàn)出高維度、非線性等特征，迫切需要對這些大數(shù)據(jù)進(jìn)行有效的分析。種子生長模型對工業(yè)測量實例的應(yīng)用，表現(xiàn)了較強的應(yīng)用能力和實用價值，可以作為多流型結(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-），男，江蘇徐州人，在讀碩士研究生，研究方向為信號與信息處理

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

李紹輝（1992-），男，河南焦作人，在讀碩士研究生，研究方向為大氣輻射與遙感

趙陽（1991-），男，陜西咸陽人，在讀碩士研究生，研究方向為衛(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è)測量中的實例為研究對象建立模型，實驗結(jié)果達(dá)到工業(yè)測量的目的，驗證該模型在實際應(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.