基于核算法的局部線性重構

揚州大學廣陵學院 崔娟娟

基于核算法的局部線性重構

揚州大學廣陵學院 崔娟娟

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

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

1.引言

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

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

2.基于局部線性重構的核主成分分析

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

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

式中μ為系數常量，公式中等號右邊第一項要求最優子集對自身的重構，第二項要求子集對訓練樣本集的重構，要求重構誤差最小。

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

假設最優樣本子集包含p個樣本，那么目標函數可以重新定義為：

由于線性局部重構的組合性質，直接優化是很難實現的，本文引入貪婪算法機制來解決式6的優化問題。相關優化算法詳見參考文獻1。

2.2本文算法

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

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

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

3.Yale庫上的實驗結果及分析

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

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

圖1　Yale數據庫中某人的26幅人臉圖像

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

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

圖2　不同的投影軸數與識別率的關系圖

圖3　一次重構的識別率對比圖

圖4　選取不同的近鄰數的識別率比較

[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.