一種面向高維相交多流形的識別算法D-MPPCA

高小方，劉杰飛，梁吉業

1(山西大學 計算智能與中文處理教育部重點實驗室，太原 030006)2(山西大學 計算機與信息技術學院，太原 030006)

1 引 言

流形學習已經成為機器學習與數據挖掘領域的一個重要的研究課題.經典的流形學習算法，包括ISOMAP[1]、LLE[2]、LE[3]、HLLE[4]以及LTSA[5]等，總是假設高維數據位于同一個單流形上，但在實際生活中存在大量位于多流形上的高維數據，而且這些流形往往是不連續或者相互交叉重疊.例如在手寫體數字識別中，每個數字在特征空間中雖然都形成了各自的流形，但其中一些數字比如數字1和數字7由于手寫體的相似，在特征空間中形成的流形往往交叉在一起，如果不能準確的將二者的流形結構分解，會對手寫體數字的識別準確率造成較大影響.再例如，在不同人臉圖像形成的特征空間中，當某些人臉的相似度較高時，在特征空間中的流形也會發生一定程度的交叉，降低人臉識別的準確率.因此，多流形數據的分解和識別已經成為流形學習研究中是一個重要的組成部分.

針對多流形數據識別的研究主要基于四種思想：基于Manifold Clustering[6]、譜聚類[7-13]、拓撲結構擴展[14,15]和監督/半監督[16-18]的思想.基于Manifold Clustering思想的算法，例如k-manifolds[6]，部分地考慮了多流形數據內在的拓撲結構，但是對于相交多流形數據的分解精度并不高，事先需要知道多流形的個數或者聚類個數.也就是說，這種算法并沒有真正脫離聚類的范疇.基于譜聚類[7-10]思想的算法，例如SMMC[7]，通過樣本點間的歐式距離對其進行粗劃分而不考慮其內在的流形拓撲結構，使得對彼此分離的多流形數據分解精度反而不高，而且這類算法必須預先知道存在的聚類個數，難以解決實際應用問題.第三種基于拓撲結構擴展[14,15]思想的算法，例如DC-ISOMAP[14]，依據流形自身的拓撲結構，通過相鄰樣本點的切空間擴展將多流形數據分解成若干個子流形.雖然計算切空間的算法復雜度較高，但是不需要事先確定子流形個數，而且分解精度較高，尤其適用于彼此分離的多流形數據.基于監督或半監督思想[16-18]的算法通過對交叉區域附近樣本點的標簽信息來識別交叉區域樣本點的流形結構，或者根據其標簽信息來增大不同流形樣本之間距離或縮小同一流形內部樣本之間距離從而實現多流形的識別，但標簽信息花費較大.

對多流形數據相交區域的樣本點進行識別，是多流形學習問題的難點.相交區域的樣本點由于距離相近，難以獲得其所屬子流形的信息，諸如近鄰關系、切空間等.因為MPPCA模型[19]可以同通過EM算法將數據樣本點分解成若干“不相交塊”，且這些塊屬于同一子流形，本文基于MPPCA模型提出了一種面向相交多流形的識別算法D-MPPCA.首先通過動態鄰域算法[20]得到每個樣本點的近鄰關系和切空間；然后通過MPPCA模型將相交多流形數據分解成若干“不相交塊”，選擇采樣密度最大的樣本點所在的“塊”作為擴展起始塊；不斷尋找與“已擴展塊”內所有樣本點切空間夾角最小的“新樣本”所在的塊進行擴展，直到無法擴展時形成新的子流形.實驗結果證明，該算法能夠有效地應用于人工多流形數據和實際圖像數據的分解和識別.

2 相關工作

經典的流形學習算法中通采用奇異值分解算法計算樣本點的切空間.但是在多流形相交部位，來自于不同流形的與由于距離相近，使得二者的局部近鄰有極大的交疊重合，導致得到切空間非常相似，使得不同流形上的與無法計算出正確的鄰域關系或者切空間而導致多流形無法被分解和識別[7].流形的本質在于局部線性.由于主成分分析(PCA)模型能夠穿過相交的線性流形，可以采用MPPCA模型對多流形數據進行初步分解，通過樣本點的邊緣概率分布將相交多流形分割成多個“不相交塊”，以便下一步的切空間擴展.

2.1 混合概率主成分分析法MPPCA

在MPPCA模型中，首先通過訓練M個分析器估計樣本切空間[19]，每個分析器將將觀測到的D維數據x用其潛在的d維向量y的線性表示，則第m個分析器模型中觀測數據x與潛在向量y之間的關系如下：

x=Vmy+μm+εm

(1)

(2)

通過EM算法對觀測數據集X={xi，i=1，…，N}利用以下對數似然最大確定參數模型中的參數：

(3)

(4)

用K-means初始化EM學習過程，最終xi的切空間可以由如下給出：

Θi=span(Vj)

(5)

2.2 切空間擴展算法

在DC-ISOMAP[14]中為了分解離散多流形提出了切空間擴展算法.首先選擇具有較大局部采樣密度的樣本點作為擴展起始點.局部采樣密度可以通過和它的最近的個節點的距離來粗糙地估計：

(6)

則擴展起始點為：

xstart=argmaxi(density(xi),i∈(1，…,n))

(7)

樣本點xi和xj之間的切空間偏差可以定義為：

(8)

xj=argminj(vij)

(9)

直到沒有樣本點可以擴充為止，開始擴展一個新的子流形.

3 面向高維相交多流形數據的D-MPPCA識別算法

在D-MPPCA算法中，首先計算樣本點的鄰域關系和切空間，為了提高算法精度，D-MPPCA采用動態鄰域[20]依次計算樣本的近鄰和局部切空間.然后利用MPPCA[19]將多流形數據分解成若干“不相交塊”；最后通過切空間擴展的方法將多流形分解成子流形.具體算法參見算法1.

算法1.D-MPPCA算法描述

輸入：X={x1，…，xn}，多流形數據；d，本征維數；θ，切空間偏差閾值；M，MPPCA模型數；

輸出：sX={sX1，…，sXk}，子流形集合；

1.調用動態鄰域算法計算樣本的動態鄰域N={N1，…，Nn}和切空間T={T1，…，Tn}；

2.利用MPPCA模型將相交多流形數據分解成個M個“不相交塊”，塊信息保存在P中；

3.通過切空間擴展分解子流形：

XH=X；

sX=[]；

while(XH≠φ)

tempSX=φ；

根據公式(6)和公式(7)在XH中選取采樣密度最大的樣本點Xstart，在P中查找Xstart所在的塊Mstart作為起始擴展塊；

tempSX=tempSX∪Mstart；

XH=XH-tempSX；

找到與當前擴展塊鄰近的未擴展樣本，并構成近鄰對

MK={(xi，xj)|xi∈tempSX，xj?XH，xj∈Nxi)}；while(MK≠φ)

逐對根據公式(8)和公式(9)計算MK中點對的切空間偏差vij，找到最小vij且vij<θ的新擴展樣本xj，并在P中查找所占塊作為下一個擴展塊Mxj.并且從MK中刪除所有vij>θ的點對；

tempSX=tempSX∪Mxj；

XH=XH-Mxj；

MK=MK∪{(xi，xj)|xi∈Mxj，xj?XH，xj∈Nxi)}；

MK=MK-(xi，xj)；

end while；

sX=[sXtempSX]；

end while；

3.1 計算鄰域和切空間

鄰域圖的構建是流形學習算法的關鍵問題之一.只有正確地構造鄰域圖，才能重構流形的拓撲結構.流形學習算法通常采用k-NN和ε-NN算法構建鄰域.但是鄰域大小的設定應該是數據驅動的，而且依賴于很多因素，諸如采樣密度和流形曲率，因為流形上的采樣密度和曲率總是在不停變化的，一個固定的鄰域大小顯然不適用于所有樣本點，影響流形學習算法最終的計算精度[20].D-MPPCA算法采用了動態鄰域算法計算樣本的鄰域以及構成的切空間，盡管增加了算法的復雜度，但有效提高了算法整體的精度.

3.2 切空間擴展分解多流形

在切空間擴展過程中，因為MPPCA模型已經將多流形數據初步分解成“不相交塊”，D-MPPCA算法不需要在“塊”內進行切空間擴展.即默認MPPCA模型分解的“不相交塊”在同一子流形上.每當計算出與“已擴展塊”中鄰近點切空間偏差最小的樣本時，將該樣本點所在的塊直接擴展.由于是“不相交塊”在擴展，整個D-MPPCA算法的運行效率將會大幅提高.

3.3 算法時間復雜度分析

假定多流形數據的樣本集有n個數據，其維度為D，本文提出的基于MPPCA的相交多流形識別算法D-MPPCA主要分三步，首先需要分別計算出每個樣本的局部切空間與近鄰關系信息，其時間復雜度為o(nlog(n))；然后通過MPPCA模型用線性模型估計其切空間，將其分解成M個數據“塊”，其中需要E-M算法與K-means算法初始化該模型參數，其時間復雜度為o(nDM(t1+dt2))，其中t1，t2分別是K-means算法與EM算法各自收斂前的迭代次數，d為本征維度；第三步在切空間擴展的時間復雜度為o(nlog(n)).因此算法整體的時間復雜度為o(nlog(n)+nDM(t1+dt2)+nlog(n))，由于d<

4 實驗結果及分析

本節分別進行了三組實驗，第一組實驗比較了參數對D-MPPCA算法識別子流形精度的影響.其他兩組實驗分別對本文提出的D-MPPCA算法和K-means、k-manifolds[6]、SC[8]、D-C[15]、SMMC[7]五種算法在人工數據和實際圖像數據上的可視化結果、精度和時間比較.

4.1 參數對相交多流形分解算法精度的影響

算法D-MPPCA有兩個參數：MPPCA模型分解“不相交塊”的個數M和在進行切空間偏差閾值θ.在Hybrid data數據集上運行D-MPPCA算法，每次僅令一個參數發生變化，算法D-MPPCA分解相交多流形數據的最優精度與平均精度的變化見圖1.

實驗結果表明：

1)在MPPCA模型中，隨著混合模型個數M的增大，“不相交塊”不斷變小，有效地提高了D-MPPCA算法整體的識別精度(見圖1(a)).當M增大到一定程度，相交區域的“不相交塊”過小，而鄰近樣本點的局部切空間相近似，導致擴展算法將非同一子流形上的樣本點選為被擴展樣本，反而導致D-MPPCA算法的識別精度降低，因此在算法訓練過程中可以通過識別精度降低的拐點確定M值；

圖1 Hybrid datas數據中D-MPPCA算法的參數對多流形識別精度的影響Fig.1 Influence of parameter of D-MPPCA on the recognition accuracy of Hybrid datas

2)當切空間偏差的閾值θ設定較小時，流形很難從一個數據“塊”擴展到另一個數據“塊”，導致分解的子流形個數過多.當該閾值設定過大時，造成相交子流形無法識別.另外，該閾值的設定受到相交區域樣本采樣密度的影響，采樣密度大，該閾值的設定能有效提高算法精度，采樣密度小，由于樣本點的切空間計算誤差較大，該閾值對D-MPPCA算法的影響較??；

3)D-MPPCA算法總能找到一個恰當的參數，而切空間偏差閾值 則需要根據數據的實際情況做細微調整.

4.2 人工數據上的實驗

在Hybrid data、Three linear planes、Two spirals三組相交多流形數據上分別運行K-means、k-manifolds、SC、D-C、SMMC和D-MPPCA六種算法，可視化結果見圖2，精度和時間的比較結果見表1.其中Hybrid data數據是從一個S-Curve曲面流形隨機選取1000個樣本點和一個與之交叉的平面流形中隨機選取500個樣本點組成；Three_Linear_Planes數據是由三個兩兩相交的平面流形各隨機選取400個樣本組成；Two_Spirals數據是由兩個相互交叉的二維螺旋流形各自隨機選取500個樣本組成.

實驗結果表明：

1)K-means算法只是對數據簡單聚類，所需時間最短，但識別精度最低，不能有效地分解多流形；

2)k-manifolds算法雖然在算法設計上考慮識別多流形，但識別精度不高，而且由于EM迭代過程造成算法所需運行時間最長；

3)SC算法的分解精度除了依賴自身參數的設定還受其選擇訓練機的不同而改變，識別多流形的精度不高；

4)D-C算法主要用于分解相互獨立的多流形數據，無法有效處理相交多流形數據；

5)D-MPPCA算法與SMMC算法均可以較準確地識別相交多流形，分解精度方面明顯優于其他算法.而且D-MPPCA算法由于其“塊擴展”過程使得算法效率明顯優于SMMC；

6)在算法實現過程中，SMMC算法必須設定聚類個數，而D-MPPCA算法不需要事先知道子流形個數，完全通過切空間擴展識別子流形.

該實驗驗證了D-MPPCA算法對多流形數據識別的有效性，不僅能較高精度地實現多流形數據的識別，而且運行速度較快.

圖2 K-means、k-manifolds、SC、D-C、SMMC、D-MPPCA算法在三組數據集上識別多流形的可視化結果比較Fig.2 Visualization results comparison of K-means，k-manifolds，SC，D-C，SMMC andD-MPPCA algorithms on the three datasets.

4.3 實際數據上的實驗

在實際人臉數據集UMist_Cropped與圖像集COIL_Cropped上運行K-means、k-manifolds、SC、D-C和D-MPPCA算法.UMist_Cropped與COIL_Cropped分別是從人臉集UMist與圖像集COIL-20上剪裁得來，由于實驗環境的限制，僅從UMist中選出8組不同人臉照片共241張，每張圖片像素為112*92.COIL-20數據集上選取五種不同物品的72張圖片，共計360張，每張圖片的像素為64*64.兩個圖像集的典型圖片如圖3所示，六種算法的精度和時間比較結果見表2.

實驗結果表明：

表1 比較圖2中三組數據的分解精度(均值(標準差，括號中為最高精度)和平均運算時間(秒)Table 1 Comparison of the decomposing accuracy (Mean(Std.Followed by the highest accuracy in the parentheses) and average computation time (seconds) of three datasets in Fig.2

1)D-MPPCA算法在實際數據集上的分解結果明顯高于其他算法；

2)SC算法對高維相交多流形數據的處理能力最差，其分解精度最低；

3)由實驗結果可知，由于COIL_Cropped數據集是五個形狀差異較大的物體，相比于UMist_Cropped人臉數據集，其中各個子流形之間相互獨立性較強，而D-C算法對獨立多流形的處理效果較好，因此D-C算法對COIL_Cropped數據集的分解效果相較于K-means、SC算法要明顯好的多；

4)k-manifolds算法在對實際數據進行處理的時候由于無法構建近鄰圖而無法執行，故未做比較；

5)K-means算法是基于距離進行聚類的方法，因此對高維數據的處理相對消耗的時間較多，相對應的其精度并不高；

圖3 UMist集的典型圖像與COIL-20集中的物品圖像Fig.3 UMist set typical image of the concentrated face and COIL-20 images of the concentrated image

6)由于D-MPPCA算法是基于擴展的方式，充分考慮了數據本身的內在結構，因此相較于SMMC算法，在精度上有了一定的提高.

表2 在實際圖像集上比較各算法的分解精度(均值(標準差，后面括號中為最高精度)和平均運算時間(秒)Table 2 Comparison of decomposition accuracy (Mean(Std.Followed by the highest accuracy in the parentheses) and average computation time (seconds) on actual images datasets

此實驗結果進一步驗證了D-MPPCA算法在實際相交多流形數據集上的有效性，不同于其他算法需要事先了解聚類或者子流形的個數信息，通過擴展的方式可以有效的將實際相交多流形數據很好的分解開.

5 結 論

本文基于MPPCA模型提出了一種面向高維相交多流形數據的分解算法D-MPPCA算法.該算法首先通過動態鄰域算法得到相交多流形中每個樣本點的切空間與近鄰關系，然后通過MPPCA模型將相交多流形數據分解成若干“不相交塊”，最后通過切空間擴展將分解和識別多流形數據.

實驗結果表明D-MPPCA算法在人工數據集與實際圖像數據集上均驗證了其算法的有效性.相較于其他多流形識別方法，D-MPPCA在相交多流形的識別上有很好的效果.這是由于D-MPPCA算法基于擴展的方式，充分考慮了流形的內部拓撲結構，而且不需要事先了解聚類或子流形的個數.而且基于MPPCA模型，通過相交區域樣本點的邊緣概率分布來判斷樣本屬于哪一個流形，極大的提高了相交區域樣本的分解精度.但是，D-MPPCA算法目前仍有一點不足在于對混合維度的相交多流形數據的處理，而且該算法尚不具備增量能力.該算法將繼續改進，以致最終能夠實現混合維度相交多流形的分解及其增量學習算法.