一種面向圖像分類的流形學習降維算法

劉開南 馮新揚 邵 超

1(三亞學院信息與智能工程學院 海南 三亞 572022)2 (河南財經政法大學計算機與信息工程學院 河南 鄭州 450000)

0 引 言

在人工智能與數據挖掘問題中，最常見的是高維數據的提取與分析。近年來提出的高維數據降維算法和特征提取算法，它們在模式識別、圖像分類中已取得了較好的結果[1-3]，這些算法關注于尋找原始數據集特征表示中有價值的信息，在圖像分類技術中得到了廣泛應用。

降維算法的目的是為了揭示出在高維數據空間中樣本數據的固有的組成特性[4-6]。傳統的線性降維算法有主成分分析法(principal component analysis,PCA)、線性判別分析法(linear discriminant analysis,LDA)、多維尺度分析法(multi-dimensional scaling,MDS)等。基于流形學習的降維方法有核函數主成分分析法(kernel PCA[7])、局部線性嵌入分析法(locally linear embedding,LLE)[8]、黑塞局部線性嵌入方法[9]、ISOMAP分析法、拉普拉斯特征映射(Laplacian Eigenmaps,LE)，局部保持投影分析法(locality preserving projections,LPP)和局部切空間對齊分析法(local tangent space alignment,LTSA)。這些算法都可以針對樣本數據在高維數據空間完成降維[10-12]。但是同時它們也會破壞原始數據固有的組成結構，而且當高維數據空間中數據點處于非均勻性狀態時，會導致降維后數據的嵌入結果比較差。

為了解決這個問題，本文提出了一種面向圖像分類的新型流形學習算法，它是針對局部線性嵌入算法的改進，稱為Mod-LLE。Mod-LLE算法整合了識別信息來更好地改善優化效果，這樣就可以保證高維原始數據固有的拓撲組成結構信息。把Mod-LLE算法應用到數據挖掘的圖像分類領域，通過實驗證明，Mod-LLE方法與LLE降維算法比較起來，可以獲得比較好的圖像分類效果和降維效果。

1 算法描述

本節主要描述高維數據降維算法Mod-LLE，它主要針對圖像的分類這個數據挖掘類應用。把高維圖像樣本數據映射到低維圖像數據的過程中，Mod-LLE算法整合了圖像數據的識別信息，這樣就可以保證原始數據的相互組成關系信息。整體來說，Mod-LLE算法通過尋求高維數據固有的拓撲結構來更好地發現數據之間隱藏的關系，同時尋找具有代表性的維度信息。

1.1 LLE分類算法描述及缺陷

原始LLE降維算法中，假設X={x1,x2,…,xN}是在RD空間中N個樣本的數據集，這里xi∈RD(i=1,2,…,N),D是數據集的維度。

在每個數據點xi處，使用xi所選擇的k個鄰居來表示局部線性組成情況。優化權重是通過下面的優化方法來完成的：

通過權重矩陣W={wi=(wi1,wi2,…,wiN)}T來完成重構，LLE算法把X={x1,x2,…,xN}映射到Y={y1,y2,…,yN}，這里Y是一個低維數據空間，根據下式，Y中保持了高維數據的局部固有屬性。

(2)

s.t.YYT=I

這里I是一個具有N×N的單位矩陣，LLE算法通過這些過程完成優化，它可以獲得d個特征向量，這樣就可以把Y構造到一個低維數據空間。當高維空間中樣本數據是均勻的時候，LLE算法被認為是一個好的降維算法;但是當高維空間中樣本數據是非均勻的時候，LLE算法破壞了原始數據的局部固有拓撲組成，會導致一個比較壞的低維嵌入結果。圖1顯示了這種情況,把3維數據空間降到2維數據空間，可以看到LLE算法完全改變了原始局部數據固有拓撲結構組成。

圖1 利用LLE算法將3D降維到2D數據局部嵌入結果

1.2 改進分類算法描述

LLE算法使用重新構造權重{wij}來保證原始數據的固有拓撲組成，但是對于每個xi, LLE算法不能反映出與信息最相近的k個鄰居密度信息。

為了克服這個缺陷， Mod-LLE算法可以保證原始數據的本身固有的拓撲組成結構。在Mod-LLE中，使用識別信息來更好地提取高維數據內部類的距離信息。這樣做的目的是在映射一個非均勻分布的高維數據避免一起帶入了不同類的樣本點。如圖2所示。

圖2 Mod-LLE算法的局部相鄰區域的優化結果

這里設計的目標函數使用下面的公式來描述：

s.t.YYT=I

式中：α和β是兩個比例因子，用來統一與調整不同的權重所占的比例，α+β=1。

Mod-LLE針對高維圖像分類降維方法可以用下面的流程來表示。

輸入:D維數據空間中N個樣本中的X個數據集；

步驟1：對每個xi，尋找k個最接近鄰居;

步驟2：根據式 (1)計算局部重構權重{wij};

步驟3： 在Rd低維數據空間中映射數據集X→Y；

步驟4：通過優化式(3)的目標函數來對Y進行優化，得到最后的結果；

輸出: 降維嵌入后的結果Y。

2 實驗與性能分析

2.1 圖像分類效果分析

為了測試Mod-LLE算法的性能，選擇臉部圖像分類為示例，這些數據來自于FFace數據集[8]。為了測試算法在面對非均勻分布數據的效果，隨機選擇了300幅人臉作為樣本，這些都是有高維空間的觀察數據。根據圖像面部表情，利用Mod-LLE把這些數據集分到5個不同的類別中：正常臉部表情(neutral)；高興臉部表情(happiness); 生氣臉部表情(anger); 吐舌臉部表情(tongued); 撅嘴臉部表情(pouty)。

表1顯示了LLE方法和Mod-LLE的識別精度。其中，圖3(a)和(b)顯示了FFace 數據集中這些圖像Mod-LLE方法和LLE方法分類到2維空間后的效果，在最接近鄰居個數k=6的情況下LLE和 Mod-LLE算法完成了性能比較。從表1和圖3可以清楚地看出，Mod-LLE算法可以在2維數據空間中清楚地分離出高興臉部表情、生氣臉部表情和正常臉部表情，精度都達到90%以上，人臉圖片分類效果明顯優于LLE算法。

(a)

(b)圖3 局部線性嵌入LLE算法分類效果

%

2.2 降維效果分析

這個部分主要測試Mod-LLE算法的降維性。測試的數據集來自于圖4所示R3空間的人工智能S-curve數據集。圖5顯示的是S-curve數據集的散點圖。可以看出，S-curve的數據由2 000個高維、非線性、流形隨機產生的點組成。在最接近鄰居個數k=16的情況下，把S-curve數據集從3維空間嵌入到2維流形空間中。Mod-LLE 和 LLE的計算結果如圖6和圖7所示。

值得注意的是，k是每個樣本點xi被選擇的最接近鄰居個數，從圖7中可以清楚的看到，Mod-LLE算法可以很好地保持S-curve數據集固有的拓撲組成情況。LLE算法正好相反，圖6顯示它對S-curve數據集的固有的拓撲組成情況進行了很大改變，沒有保持多維數據的一致性。分析原因是Mod-LLE算法在重新構造權重矩陣時{wij}可以保證原始數據的固有拓撲組成。而且式(3)是線性無關，具有最優近似解，α和β是兩個比例因子，它們和最接近鄰居個數k都很好進行調整，使Mod-LLE有很好的降維效果。

圖4 S-curve 數據集

圖5 S-curve 數據集在N=2 000情況下樣本點散點圖

圖6 LLE針對S-curve 數據集的2維嵌入效果

圖7 Mod-LLE針對S-curve 數據集的2維嵌入效果

3 結 語

本文提出了一個面向圖像分類的流形學習降維算法Mod-LLE，它基于局部鄰居優化策略，整合了圖像識別信息用于高維數據集降維。Mod-LLE在低維數據空間中可以獲得比較好的內部類分類效果，并保持了高維原始數據固有的拓撲組成信息。實驗結果表明，Mod-LLE算法在人臉圖像分類算法上有很好的分類效果，在降維效果上優于之前的LLE算法。