基于自適應密度聚類非線性流形學習降維方法研究與實現

陳晉音，鄭海斌，保星彤

(浙江工業大學 信息工程學院， 杭州 310023) E-mail：chenjinyin@zjut.edu.cn

1 引 言

流形學習的方法基于數據是采樣于一個高維的外圍歐式空間的一個低維子流形的假設，流形存在一定的低維內在結構.由于它們在尋求嵌入在高維空間中低維流形表現出突出的結果，并且在實際應用中具有靈活性，因此吸引了大量學者研究.目前具有代表性的流形學習算法有等距映射(Isometric Mapping，ISOMAP)[1]、局部線性嵌入方法(Locally Linear Embedding，LLE)[2]、Laplacian特征映射(Laplacian Eigenmap，LE)[3]等.

但當前普通降維方法降維后對流形產生扭曲，展開后結構發生“畸形”的情況，因此本文希望找到一種方法，這個方法中流形的全局結構可以通過迭代合并相鄰局部模型得到，從而得到流形的低維結構.為了克服普通降維方法降維后對流形產生扭曲，展開后結構發生“畸形”的情況，本文提出了一種新穎的流形學習方法，用分段線性模型來近似流形.

2 基于自適應密度聚類的非線性流形學習降維算法

本流形學習降維算法可以分為四個主要步驟，算法流程圖如圖1所示.

圖1 非線性流形學習降維方法的流程圖Fig.1 Flow chart of nonlinear manifold dimension reduction algorithm

2.1 形成局部線性模型

有高維樣本M，M的每一個樣本為一個點x，這個點通常是一個數學表示的對象.從嵌入了的低維流形(n<

算法的初始步驟是對流形M中的數據對象運用自適應密度聚類算法進行聚類[4]，自動確定初始的聚類中心a，并且把M分成c個類，每個類為Cn(n?c).一旦X被分割成c個類簇，就可以形成局部線性模型.第k個簇的線性模型為Ck類中所有的數據點XCk投影到超平面，其中超平面的基向量由在數據XCk上運行局部ICA得到的特征向量定義.在每個聚類上運行ICA，將聚類樣本映射到n+1維且不改變聚類的關聯情況，形成局部低維線性模型.

由于在這個階段，數據是局部n維的，下一步是對齊局部線性模型建立全局一致的全局模型.這種全局模型仍將被嵌入N維空間，但在局部模型和全局模型是n維的，所以簡單的ICA轉換將數據的維度降低到n維.

2.2 建立最小穿越樹MST

全局遍歷的步驟通過將相鄰模型的基本向量迭代地遍歷合并，并將先前訪問的點投影到當前模型的基向量上來執行，如圖2所示是按照一定順序迭代每個模型的過程示意圖.

圖2 迭代過程示意圖Fig.2 Iteration process illustration

對每個線性模型線性模型，采用其聚類中心作為線性模型代表，將所有聚類中心建立一個MST樹.MST遍歷起點的選擇和當存在多個子節點時遍歷順序的選擇，對本方法設計結果的影響為零.通過將訪問模型合并成全局數據表示，迭代地形成全局模型.最小生成樹(MST)提供了局部模型拓撲的表示，因此形成模型訪問順序的基礎.模型MST的定義如公式(1)所示.

(1)

其中d(ai,aj)是兩個聚類中心ai和aj的歐式距離，也是MST樹的連邊.判斷是否能夠將聚類中心間連線看作MST樹的條件是，要求MST消除所有首尾連接且連邊權重最小.

針對已構建的MST，由于在流形上構建的MST不同于普通二叉樹每個節點只有兩個子樹，先序遍歷等遍歷無法滿足本方法的要求，因此設計了一種能夠簡便遍歷含有兩個以上子樹的MST的方法，該方法實現在遍歷過程中能同時對當前和下一個遍歷節點進行平行映射.按MST樹為基礎遍歷順序的具體流程如圖3，其中由于返回映射的流程較為復雜，本文單獨在圖4的流程圖中展示.

圖3 遍歷流形的全局MST流程圖Fig.3 Flow chart of MST global manifold process

圖4 返回映射的流程圖Fig.4 Flow chart of backward mapping

2.3 遍歷流形的全局MST

對于前向映射，已訪問的模型被投影到當前模型上，使得它們位于相同的坐標空間中.為了減少失真，需要兩個模型先平行，這是本流形學習降維算法中關鍵概念之一的投影的平行化.

前向映射的主要原則是，如果兩個模型的法向量對齊，意味著兩個模型是平行的，相當于兩個模型之間的二面角等于零.因此，目標是找到已訪問模型與當前模型對齊所需的旋轉角度，使得它們能夠旋轉后平行.給定兩個模型的基向量Vi和Vj，目標是找到將Vi與Vj對齊所需的旋轉矩陣Φ，然后應用該旋轉矩陣將已訪問模型的所有數據點XCi映射到由Vj定義的子空間上.對于每個類的基向量，有子空間的法向量作為基向量組的第(n+1)個向量，因此，矩陣Vi的大小為N×(n+1).

找到旋轉矩陣Φ后可以很容易將模型的映射變為點集的映射問題.假設基向量現在為Vi=[v1,v2,...,vn+1]，應用公式(2)對每組基向量乘以縮放系數，其中相同向量前的系數的絕對值選取不影響旋轉結果，再并上求反的向量組.這樣做是為了排除兩個軸在相反的方向的情況，并且縮放確保了求得的旋轉矩陣唯一.

Vi=[v1,2v2,…,(n+1)vn+1,-1.5v1,-2.5v2,…,-(n+1.5)vn+1]

(2)

Φ=YVT

(3)

求出旋轉矩陣后對XCi應用公式(4)將兩個模型做平行化處理：

(4)

其中-Φ為Φ的求反.兩個模型平行后將更新Ppre的軸Vi=ViΦ，更新后的V取前n維.然后利用公式(5)將已訪問的模型映射到當前模型：

(5)

兩個模型的旋轉及映射步驟分解過程如圖5所示.

圖5 模型的旋轉及映射步驟分解Fig.5 Model rotation and its mapping steps

(6)

返回映射和前向映射，都需要對所有之前遍歷過的線性模型都施行.

2.4 找到低維嵌入結構

一旦在上述遍歷中訪問了所有節點，將獲得嵌入在N維空間內的流形的n維表示.通過在全局超線性模型上運行ICA再對高維空間的低維線性模型降維，將低維線性模型在低維空間中顯示，也就真正實現了對數據高維到低維的降維.

3 性能評價及實驗分析

3.1 性能評價及分析

所采用的三個評估條件中的兩個涉及到嵌入的局部穩定性，一個用于測量拓撲穩定性(可信度)，另一個用于測量幾何穩定性(錯誤率).第三個評估條件是關于數據的全局距離以及此全局結構的維持程度(殘差方差誤差).

3.1.1 可信度

可信度(TW)衡量鄰居在高維空間和低維空間之間的保留.值得信賴的高價值是衡量當地社區在低維空間中的重建程度的一個很好的衡量標準.按照與[6]相同的術語和方法，嵌入在鄰域大小區域k的可信度定義為公式(7)：

(7)

其中Ck是在低維空間中但不在高維空間中的xi的k鄰域中的數據樣本集合.d(xi,xj)是根據在高維空間中與xi的距離的排序中的數據樣本xj的等級.可信度值為1時表示流形學習沒有發生局部鄰域失真.

3.1.2 映射錯誤率

映射錯誤率(PE)測量由于流形學習而引入的局部失真.由于該誤差度量是基于Procrustes分析，它測量高維空間中的鄰域與低維空間中相同鄰域之間的旋轉變化.錯誤度量被定義為公式(8)：

(8)

其中K(xi,xj)為圍繞xi和xj的鄰域的Procrustes統計量.PE為0表示在高空間和低維空間中的給定鄰域之間的旋轉沒有變化.函數Rk對縮放敏感，因此會突出那些規范化數據或引入局部尺度變化的技術.

3.1.3 殘差方差誤差

殘差方差誤差(RV)測量高維和低維空間中所有點之間距離的差異[7].誤差測量為公式(9)：

R=1-V2(Bx,By)

(9)

其中Bx是包含高維空間中所有點之間的距離的正方形對稱矩陣(由k個最近鄰居形成的測地距離圖測量).By是低維空間中的點之間的歐幾里德距離矩陣.V2取自Bx和By的所有線性相關系數.RV值為0將表示兩個距離矩陣之間的完美相關.

3.1.4 數據集密度分析

處理稀疏數據的能力是多元學習中的開放性問題之一.設置四種不同的數據集大小用于表示數據從稀疏到密集的變化.使用瑞士卷數據集作為測試數據集取樣，數據集大小分別設為n=250,500,1000和2000個數據點.

從表1中可以看出，當數據密度低(n<1000)時，特別是當考慮殘差時，所有的算法性能都大幅下降，因為稀疏數據中包含的局部和全局信息通常不足以正確地近似流形的形狀.當n≥1000時，本算法表現最佳，因為它能夠恢復流形的局部和全局屬性.通過值的變化，可以看出本算法的性能隨著密度的增加而提高.密度低時，本流形學習降維算法的性能將降低，但不會導致算法不可用.因此，只要數據被很好地采樣，本降維算法的性能勝過其他流形學習算法.

3.1.5 噪聲分析

在實驗中使用的噪聲模型是平均值為0的高斯噪聲，σ=[0,1]范圍內的標準偏差.盡管在σ=1的情況下，瑞士卷數據集并不會完全降級，但是許多流形學習算法仍然難以用這種噪聲量來獲取流形的真實結構.

表1 本算法與典型降維算法針對不同密度數據集的比較Table 1 Comparison between proposed algorithm and baselines

從本流形學習降維算法來看，噪聲會影響聚類步驟，因此不僅會導致不正確的模型形成，而且還會產生不正確的MST.如果聚類步驟無法產生準確的數據本地模型，則本流形學習降維算法算法不可能恢復流形的真實嵌入.使用數據集大小為n=2000來排除密度的影響，保證變量僅僅集中在噪聲的影響上.圖6中表示使用n=2000和σ=1的本算法創建的MST.

圖6 用n=2000和σ=1的本流形學習降維算法創建的MSTFig.6 MST generation for proposed manifold dimension reduction algorithm when n=2000 and σ=1

可以看到，跨越流形的MST中出現了短路.這些短路將導致嵌入的失真和重疊，因為合并步驟將合并兩個不是拓撲相鄰的模型.這就是可信度降低的原因：重疊導致點在非連接鄰居之間跳躍.

3.2 仿真實驗與分析

3.2.1 人工數據

該方法已在瑞士卷(Swiss Roll)人造數據集上測試算法的性能，并將該方法與五個同樣數據集上的其他領先算法進行比較.ISOMAP[7]和LLE[8]被用來代表全局和本地的多元化學習方法.由于本流形學習降維算法是局部到全局方法，因此使用三種領先的局部或全局算法分別為局部切空間排列算法(Local Tangent Space Alignment，LTSA)[9]，流形學習圖表(Manifold Charting)[10]和局部線性協調(Locally Linear Coordination，LLC)[11]，降維結果如圖7.

圖7 (a)至(g)分別為原瑞士卷數據集和ISOMAP、LLE、LTSA、Manifold Charting、LLC及本算法的流形學習降維算法應用于瑞士卷數據集時的結果Fig.7 From (a) to (g)，they are switch roll data set，dimension reduction results based on ISOMAP，LLE，LTSA，Manifold Charting，LLC and proposed algorithm respectively

根據降維結果所示，本文可以看出本論文降維算法不僅能完成數據集降維處理的目標，并且相較于其它算法，不會產生數據內在結構的畸形，極大程度保證了本算法結果的正確率和可信度.

3.2.2 COIL-20數據集

COIL-20數據集由圍繞一個軸旋轉的3維物體的72張圖像組成.每個圖像的大小為128×128像素，該72個樣本形成的流形等同于嵌入在16384維空間內的圓形流形.因此COIL-20數據集在實驗中形成的MST的排序沒有分支，是一個一維鏈狀模型.同樣，可以在MST中的首位兩個模型之間建立連接，按照相同順序在MST的任意一處斷開，并不會影響實驗結果.由于COIL-20數據集本身是一個封閉的圓柱流形，因此本算法會導致環形流形中某部分斷開分裂到低維嵌入的兩邊，如圖8所示是將COIL-20數據集降至二維的低維嵌入，流形的低維嵌入結構并不明顯.

圖8 將COIL-20數據集降至二維的低維嵌入結構Fig.8 Two dimension mapping structure for COIL-20 data set

進一步將COIL-20數據集視為一維流形，嵌入到一維空間中.使用本算法將COIL-20數據集嵌入一維空間的量化結果如圖9所示.通過將數據嵌入到一維空間中，本算法能夠較準確的捕獲數據的結構，并清楚地按照對象的旋轉度顯示.因此，在二維嵌入中不明顯的結構在一維表示中能被識別.

圖9 將COIL-20數據集降至一維的低維嵌入結構坐標圖和結果圖Fig.9 One dimension mapping location and results based on proposed algorithm for COIL-20 data set

3.2.3 FERET數據集

FERET人臉數據集包括200個人，每個人7張80×80的照片，即一個1400個樣本的6400維數據集，每組照片存在不同的膚色、姿態、光照和表情變化.為了找到人臉圖片中最重要的幾個變化參數，使用本算法降維到三維后結果如圖10所示.

圖10 將FERET數據集降至三維的低維嵌入圖Fig.10 Three dimension mapping based on proposed algorithm for FERET data set

可以看出，根據姿勢變化，沿垂直軸移動的路徑從上到下表示從向右看到正視到向左看的姿勢；根據亮度不同，水平路徑表示照明條件發生變化而姿勢保持不變.

4 總 結

在本文中，提出了一種基于自適應密度聚類的非線性流形學習降維方法.針對當前普通降維方法降維后對流形產生扭曲導致流形展開后結構發生“畸形”的情況，運用平面的平行映射克服原數據集因為通過降維而產生的畸變.設計算法性能評估指標，針對流形學習參數對降維的影響，設計實驗分別并對不同數據集密度和噪聲對算法結果影響展開分析，最終驗證了提出方法的有效性.并且通過實驗測試，證明在人造和實際圖像數據集上，本流形學習降維算法與現有最先進的流形學習算法相比，產生良好的降維效果，同時對實驗中揭示出的算法在實際應用范圍做出相應闡述和分析.