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

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

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

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

主成分分析；特征抽??；分類

1.引言

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

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

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

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

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

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

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

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

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

2.2本文算法

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

這樣就得到一個近似的特征空間：

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

3.Yale庫上的實驗結(jié)果及分析

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

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

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

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

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

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

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

圖4　選取不同的近鄰數(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.