基于核算法的局部線性重構(gòu)

揚(yáng)州大學(xué)廣陵學(xué)院 崔娟娟

基于核算法的局部線性重構(gòu)

揚(yáng)州大學(xué)廣陵學(xué)院 崔娟娟

對(duì)于模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域，圖像的特征抽取是最基本的問(wèn)題之一，而核主成分分析是其中一種經(jīng)典算法。但是，核方法都存在一個(gè)問(wèn)題，當(dāng)訓(xùn)練樣本數(shù)非常多的時(shí)候計(jì)算代價(jià)很大，導(dǎo)致識(shí)別效率低下。針對(duì)這一問(wèn)題，本文提出一種基于核算法的局部線性重構(gòu)，其主要思想就是從大量的訓(xùn)練樣本中選出一部分最具有代表性的樣本代替大量的訓(xùn)練樣本，利用代表樣本構(gòu)造核空間，將所有樣本非線性投影到核空間中，使得樣本線性可分。后續(xù)的實(shí)驗(yàn)證明了本算法的有效性。

主成分分析；特征抽?。环诸?/p>

1.引言

眾所周知，抽取最有效的圖像是模式識(shí)別的首要任務(wù)，運(yùn)用抽取到的特征將原始數(shù)據(jù)映射到某一低維空間后，能得到最反映數(shù)據(jù)本質(zhì)的特征，其中最經(jīng)典是主成分分析（Principal Component Analysis，PCA）和Fisher線性鑒別分析，但是這兩種方法只能保證抽取出來(lái)的各個(gè)分量之間不相關(guān)卻不能保證這些分量之間互相獨(dú)立，因此基于核的非線性特征抽取就變得更加合理。核方法的基本思想就是通過(guò)將實(shí)際問(wèn)題通過(guò)非線性轉(zhuǎn)換到高維甚至是無(wú)窮維特征空間，使其在核空間中線性可分或者是近似可分。但是這些基于核的非線性特征抽取基本上都存在兩類問(wèn)題：（1）核參數(shù)以及核函數(shù)的選擇問(wèn)題；（2）計(jì)算代價(jià)太大，處理效率低下。

本文提出一種基于局部線性重構(gòu)的核主成分分析算法，通過(guò)從大量的訓(xùn)練樣本中選取一部分具有代表性的樣本，利用這些樣本構(gòu)造核空間，然后將所有樣本非線性投影到核空間中，使得樣本線性可分。選取樣本點(diǎn)的算法是參考Cai[1]的局部線性重構(gòu)投影的思想，因?yàn)槊拷M樣本集肯定存在空間的流行結(jié)構(gòu)，而每個(gè)樣本點(diǎn)又能被其近鄰重構(gòu)，通過(guò)這種思想選取出的樣本點(diǎn)不僅具有很高的代表性有保持了樣本之間的流行結(jié)構(gòu)，這樣構(gòu)造出的算法大量減少了計(jì)算機(jī)的計(jì)算代價(jià)。

2.基于局部線性重構(gòu)的核主成分分析

2.1選取最有代表性的樣本子集

本節(jié)主要介紹利用局部線性重構(gòu)的思想從大量的訓(xùn)練樣本空間選取部分具有代表性的樣本。由于在高維空間均勻采集的數(shù)據(jù)樣本存在低維的流行結(jié)構(gòu)，而每個(gè)樣本點(diǎn)又能被其近鄰重構(gòu)，那么肯定存在一組最具有代表性的自己能夠線性重構(gòu)所有的訓(xùn)練樣本集。

式中μ為系數(shù)常量，公式中等號(hào)右邊第一項(xiàng)要求最優(yōu)子集對(duì)自身的重構(gòu)，第二項(xiàng)要求子集對(duì)訓(xùn)練樣本集的重構(gòu)，要求重構(gòu)誤差最小。

在進(jìn)行樣本重構(gòu)時(shí)要求重構(gòu)誤差最小，那么重構(gòu)誤差可以重新定義為：

假設(shè)最優(yōu)樣本子集包含p個(gè)樣本，那么目標(biāo)函數(shù)可以重新定義為：

由于線性局部重構(gòu)的組合性質(zhì)，直接優(yōu)化是很難實(shí)現(xiàn)的，本文引入貪婪算法機(jī)制來(lái)解決式6的優(yōu)化問(wèn)題。相關(guān)優(yōu)化算法詳見參考文獻(xiàn)1。

2.2本文算法

由定義1可以看出，當(dāng)訓(xùn)練樣本量非常大時(shí)，假設(shè)n＞5000，將所有的訓(xùn)練樣本全部投影到核空間計(jì)算量非常龐大，所涉及的計(jì)算量復(fù)雜度是O(n3)，因此通過(guò)選取代表性的點(diǎn)可以減少大量的計(jì)算。

這樣就得到一個(gè)近似的特征空間：

那么判別式就可以重新定義為：

3.Yale庫(kù)上的實(shí)驗(yàn)結(jié)果及分析

本節(jié)我們將會(huì)在兩個(gè)不同的人臉庫(kù)上驗(yàn)證本節(jié)算法。關(guān)于的參數(shù)μ，一般選取0.1，這對(duì)實(shí)驗(yàn)結(jié)果的影響不大，但是值為0.1時(shí)算法的性能最好。在支持向量機(jī)中常用的核函數(shù)有高斯核函數(shù)，多項(xiàng)式核函數(shù)，其中σ、c和d都是常數(shù)，本實(shí)驗(yàn)中我們只選用高斯核。

Yale人臉圖像數(shù)據(jù)庫(kù)共有165幅圖像，包含15個(gè)人，每人有11幅圖像，分別在不同表情、姿態(tài)和光照條件下拍攝，每張圖的分辨率為100×80。圖1為該人臉庫(kù)中某人的11幅圖像。

圖1　Yale數(shù)據(jù)庫(kù)中某人的26幅人臉圖像

在實(shí)驗(yàn)中，每個(gè)人選取5個(gè)隨機(jī)樣本作為訓(xùn)練樣本，也就是說(shuō)訓(xùn)練樣本總數(shù)為75人,剩余的樣本都用來(lái)測(cè)試，共90張測(cè)試樣本。投影軸數(shù)從1選到40依次增加，步長(zhǎng)為2。代表性樣本數(shù)從15到65，步長(zhǎng)為10。最小距離分類器將被用于分類。

這里定義選擇的代表性樣本數(shù)為k，投影到核空間后的樣本維數(shù)為k×k。本次試驗(yàn)我們分別對(duì)比了na?ve KPCA,ESKPC和ALSKPCA三個(gè)算法在同等條件下的最高識(shí)別率。從圖3可以看出隨著k值的增加，兩種算法的識(shí)別率也在不斷升高，當(dāng)k為45時(shí)，也就是說(shuō)取45個(gè)樣本時(shí)本算法已經(jīng)開始收斂，而ESKPC則到55時(shí)才收斂，本算法收斂速度較快，效率較高。圖2顯示，在k=45的情況下，本算法的識(shí)別率也有明顯優(yōu)勢(shì)，這是因?yàn)楸舅惴ㄔ谶x取最優(yōu)樣本時(shí)加入了流形信息，選擇的樣本更合理，可以張成的空間范圍更大。另外圖4顯示ESKPC的運(yùn)算時(shí)間隨著k的增大而不斷增大，趨勢(shì)非常明顯，而本文算法在一定的范圍內(nèi)選擇樣本的速度更快，而且受到的影響也極小，基本沒有變化。

圖2　不同的投影軸數(shù)與識(shí)別率的關(guān)系圖

圖3　一次重構(gòu)的識(shí)別率對(duì)比圖

圖4　選取不同的近鄰數(shù)的識(shí)別率比較

[1]Active Learning Based on Locally Linear Reconstruction. Lijun Zhang, Chun Chen, Jiajun Bu, Deng Cai, Xiaofei He, Thomas S. Huang IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 10, pp. 2026-2038, 2011.

[2]S.T. Roweis and L.K. Saul, “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” Science, vol. 290, no. 5500, pp. 2323-2326, Dec. 2000.