多流形結構數據建模與應用研究

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

多流形結構數據建模與應用研究

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

0　引言

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

在實際問題中很多數據具備復雜的結構。例如，對于具有多個混合子空間結構的特征點數據，判斷哪些特征點屬于同一子空間是其能否有效解決的關鍵。從參考文獻可以看到，傳統的結構分析算法不能很好地處理復雜結構的樣本集特征提取和聚類問題，而流形學習（Manifold Learning）方法能很好地處理此類問題。本文基于流形學習的理論，提出了種子生長模型，探索了多流形結構數據聚類的有效方法。

1　流形學習方法概述

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

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

不同于單流形學習，多流形結構數據建模的目的是把輸入數據集分為若干個類別，使得每個類別中的數據點都來自單一、簡單、低維嵌入流形，如圖1所示（圖中數據建模為三個低維流形）。它有以下三個目標：分析子流形的數目和各自的維數；數據的劃分（數據屬于不同的低維流形）；數據在對應的低維流形中的嵌入。

2　基本假設和符號說明

本文為處理多流形結構數據設計了種子生長模型，通過迭代更新當前種子與分類集合，達到聚類的目的。基本假設如下：

圖1　多流形結構數據建模

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

（2）高維數據都是均勻采樣于一個高維歐氏空間中，通過流形學習找到相應嵌入映射，從而實現維數約簡。

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

P判定后與當前種子同類的樣本集合

U全體樣本集合

Si當前生長過程的第i個種子

r種子生長半徑

Rule種子生長規則 （評價指標包括向量距離vd，向量夾角θ，法向量）

dtheta控制種子生長方向的閾值 （對應Rule中的評價指標）

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

Sn'與當前種子距離小于r的樣本集合的子集，取距離最小的前n個樣本構成

Sn"與當前種子距離大于r的樣本集合的子集，取距離最小的前n個樣本構成

n搜索范圍

3　模型的建立與分析

圖2包含兩條交叉的“線”，可以看作是一種一維多流形結構數據，現以它為例建立模型。

圖2　一維多流型結構數據

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

表1　種子生長模型

圖3　初始種子的選擇

根據建模思想，設計種子生長算法如圖4所示。

圖4　種子生長算法流程圖

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

圖5　聚類結果

圖6包括了一個“面”以及兩條“線”，可以看作是一種二維多流形結構數據，現以它為例建立模型。

圖6　二維多流形結構數據

圖7　建模思路

建模思路是，先按照種子生長模型（以法向量為評判指標）對混合多流形結構數據進行粗分類，將“面”與兩條“線”區分開來；粗分類之后，再應用上一節的種子生長算法（以向量夾角為評判指標）對兩條“線”進行聚類。直觀描述見圖7。

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

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

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

圖9　聚類結果

4　模型的應用研究

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

圖10　工業測量的實例

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

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

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

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

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

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

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

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

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

圖11　初步分類流程圖

初步分類沒有處理的樣本將在后處理部分進行分類。可以利用蒙特卡洛方法處理這些少數樣本點：以樣本點為中心，設置搜索半徑r，若圓中A類的點居多，則認為該樣本點與A類有更大的相似性，將其歸為A類，否則歸為B類。

后處理過程如圖12所示。

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

圖12　后處理部分流程圖

5　結語

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

圖13　生長軌跡和聚類結果

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

［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-），男，陜西咸陽人，在讀碩士研究生，研究方向為衛星遙感技術與應用

2015-11-06

2015-11-15

研究多流形結構的復雜數據的聚類方法，在流形學的基礎上提出種子生長模型。對一維和二維多流形結構數據的建模和分析，表明該模型能夠有效地解決類似的混合子空間聚類問題。以工業測量中的實例為研究對象建立模型，實驗結果達到工業測量的目的，驗證該模型在實際應用中的可行性。

多流形數據；種子生長模型；評判指標；子空間聚類

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.