劉開南 馮新?lián)P 邵 超

1(三亞學(xué)院信息與智能工程學(xué)院 海南 三亞 572022)2 (河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 鄭州 450000)

0 引 言

在人工智能與數(shù)據(jù)挖掘問題中，最常見的是高維數(shù)據(jù)的提取與分析。近年來提出的高維數(shù)據(jù)降維算法和特征提取算法，它們?cè)谀Ｊ阶R(shí)別、圖像分類中已取得了較好的結(jié)果[1-3]，這些算法關(guān)注于尋找原始數(shù)據(jù)集特征表示中有價(jià)值的信息，在圖像分類技術(shù)中得到了廣泛應(yīng)用。

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

為了解決這個(gè)問題，本文提出了一種面向圖像分類的新型流形學(xué)習(xí)算法，它是針對(duì)局部線性嵌入算法的改進(jìn)，稱為Mod-LLE。Mod-LLE算法整合了識(shí)別信息來更好地改善優(yōu)化效果，這樣就可以保證高維原始數(shù)據(jù)固有的拓?fù)浣M成結(jié)構(gòu)信息。把Mod-LLE算法應(yīng)用到數(shù)據(jù)挖掘的圖像分類領(lǐng)域，通過實(shí)驗(yàn)證明，Mod-LLE方法與LLE降維算法比較起來，可以獲得比較好的圖像分類效果和降維效果。

1 算法描述

本節(jié)主要描述高維數(shù)據(jù)降維算法Mod-LLE，它主要針對(duì)圖像的分類這個(gè)數(shù)據(jù)挖掘類應(yīng)用。把高維圖像樣本數(shù)據(jù)映射到低維圖像數(shù)據(jù)的過程中，Mod-LLE算法整合了圖像數(shù)據(jù)的識(shí)別信息，這樣就可以保證原始數(shù)據(jù)的相互組成關(guān)系信息。整體來說，Mod-LLE算法通過尋求高維數(shù)據(jù)固有的拓?fù)浣Y(jié)構(gòu)來更好地發(fā)現(xiàn)數(shù)據(jù)之間隱藏的關(guān)系，同時(shí)尋找具有代表性的維度信息。

1.1 LLE分類算法描述及缺陷

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

在每個(gè)數(shù)據(jù)點(diǎn)xi處，使用xi所選擇的k個(gè)鄰居來表示局部線性組成情況。優(yōu)化權(quán)重是通過下面的優(yōu)化方法來完成的：

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

(2)

s.t.YYT=I

這里I是一個(gè)具有N×N的單位矩陣，LLE算法通過這些過程完成優(yōu)化，它可以獲得d個(gè)特征向量，這樣就可以把Y構(gòu)造到一個(gè)低維數(shù)據(jù)空間。當(dāng)高維空間中樣本數(shù)據(jù)是均勻的時(shí)候，LLE算法被認(rèn)為是一個(gè)好的降維算法;但是當(dāng)高維空間中樣本數(shù)據(jù)是非均勻的時(shí)候，LLE算法破壞了原始數(shù)據(jù)的局部固有拓?fù)浣M成，會(huì)導(dǎo)致一個(gè)比較壞的低維嵌入結(jié)果。圖1顯示了這種情況,把3維數(shù)據(jù)空間降到2維數(shù)據(jù)空間，可以看到LLE算法完全改變了原始局部數(shù)據(jù)固有拓?fù)浣Y(jié)構(gòu)組成。

圖1 利用LLE算法將3D降維到2D數(shù)據(jù)局部嵌入結(jié)果

1.2 改進(jìn)分類算法描述

LLE算法使用重新構(gòu)造權(quán)重{wij}來保證原始數(shù)據(jù)的固有拓?fù)浣M成，但是對(duì)于每個(gè)xi, LLE算法不能反映出與信息最相近的k個(gè)鄰居密度信息。

為了克服這個(gè)缺陷， Mod-LLE算法可以保證原始數(shù)據(jù)的本身固有的拓?fù)浣M成結(jié)構(gòu)。在Mod-LLE中，使用識(shí)別信息來更好地提取高維數(shù)據(jù)內(nèi)部類的距離信息。這樣做的目的是在映射一個(gè)非均勻分布的高維數(shù)據(jù)避免一起帶入了不同類的樣本點(diǎn)。如圖2所示。

圖2 Mod-LLE算法的局部相鄰區(qū)域的優(yōu)化結(jié)果

這里設(shè)計(jì)的目標(biāo)函數(shù)使用下面的公式來描述：

s.t.YYT=I

式中：α和β是兩個(gè)比例因子，用來統(tǒng)一與調(diào)整不同的權(quán)重所占的比例，α+β=1。

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

輸入:D維數(shù)據(jù)空間中N個(gè)樣本中的X個(gè)數(shù)據(jù)集；

步驟1：對(duì)每個(gè)xi，尋找k個(gè)最接近鄰居;

步驟2：根據(jù)式 (1)計(jì)算局部重構(gòu)權(quán)重{wij};

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

步驟4：通過優(yōu)化式(3)的目標(biāo)函數(shù)來對(duì)Y進(jìn)行優(yōu)化，得到最后的結(jié)果；

輸出: 降維嵌入后的結(jié)果Y。

2 實(shí)驗(yàn)與性能分析

2.1 圖像分類效果分析

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

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

(a)

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

%

2.2 降維效果分析

這個(gè)部分主要測(cè)試Mod-LLE算法的降維性。測(cè)試的數(shù)據(jù)集來自于圖4所示R3空間的人工智能S-curve數(shù)據(jù)集。圖5顯示的是S-curve數(shù)據(jù)集的散點(diǎn)圖?？梢钥闯觯琒-curve的數(shù)據(jù)由2 000個(gè)高維、非線性、流形隨機(jī)產(chǎn)生的點(diǎn)組成。在最接近鄰居個(gè)數(shù)k=16的情況下，把S-curve數(shù)據(jù)集從3維空間嵌入到2維流形空間中。Mod-LLE 和 LLE的計(jì)算結(jié)果如圖6和圖7所示。

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

圖4 S-curve 數(shù)據(jù)集

圖5 S-curve 數(shù)據(jù)集在N=2 000情況下樣本點(diǎn)散點(diǎn)圖

圖6 LLE針對(duì)S-curve 數(shù)據(jù)集的2維嵌入效果

圖7 Mod-LLE針對(duì)S-curve 數(shù)據(jù)集的2維嵌入效果

3 結(jié) 語

本文提出了一個(gè)面向圖像分類的流形學(xué)習(xí)降維算法Mod-LLE，它基于局部鄰居優(yōu)化策略，整合了圖像識(shí)別信息用于高維數(shù)據(jù)集降維。Mod-LLE在低維數(shù)據(jù)空間中可以獲得比較好的內(nèi)部類分類效果，并保持了高維原始數(shù)據(jù)固有的拓?fù)浣M成信息。實(shí)驗(yàn)結(jié)果表明，Mod-LLE算法在人臉圖像分類算法上有很好的分類效果，在降維效果上優(yōu)于之前的LLE算法。