KPCA維數約簡研究

董虎勝

（蘇州經貿職業(yè)技術學院，蘇州 215009）

KPCA維數約簡研究

董虎勝

（蘇州經貿職業(yè)技術學院，蘇州 215009）

在對數據分析與處理時，為了避免高維數據所帶來的巨大運算開銷，通常需要對原始數據進行維數約簡。與基于線性投影的維數約簡方法相比，基于核方法的維數約簡由于能夠實現對樣本的非線性映射，因此在數據預處理中具有更大的優(yōu)勢。對基于核方法的主成分分析(KPCA)維數約簡方法進行研究，并通過實驗結果證明KPCA不僅能夠實現數據的降維，還具有增強數據線性可分性的優(yōu)勢。

維數約簡；線性投影；核方法；KPCA

0 引言

在數據分析與處理中，由于原始數據的維度比較高，直接使用原始數據進行處理分析一方面會帶來很大的運算開銷，另一方面數據自身可能會存在有大量的噪聲以及不同維度之間可能會存在有較強的相關性，這些都不利于獲得數據內部的模式。為了避免這些問題，通常需要對原始數據進行特征選擇預處理，實現對原始數據的維數約簡[1]。

在數據的維數約簡方法中，主成分分析[1]（Principle Component Analysis,PCA）是最早被提出且應用廣泛的一種通過線性投影實現降維的方法，在人臉識別[2,8]、超分辨率圖像[3]、視頻跟蹤、目標識別以及其他諸多研究中常采用PCA實現降維、去相關與降噪等數據預處理工作。雖然PCA能夠有效地降低數據的維數，但其本質上是通過對原始樣本通過線性投影到低維子空間的方法，這種線性變換在處理具有非線性流形數據時則顯得力不從心，因此研究非線性的維數約簡方法就非常必要。例如，在對具有非線性特征的人臉圖像信息處理時，即需要實現對數據降維的同時保留樣本的非線性結構，又希望投影后的樣本能夠具有線性可分的性質。作為PCA的非線性推廣，KPCA[1]的主要思想即通過核函數實現將樣本由原輸入空間映射到高維Hilbert空間，進而在其中進行線性PCA降維。

本文對KPCA的實現進行了研究，并對PCA與KPCA的差異進行對比分析。實驗結果表明，KPCA具有良好的非線性數據維數約簡與增強數據線性可分的性能。

1 PCA

設原始樣本為X?Rd×n，其中d為樣本維度，n為樣本數，第i個樣本為xi?Rd。PCA維數約簡的目標是通過學習線性投影矩陣W?Rd×d'（d'≤d），對原樣本作線性變換，從而將原始的高維數據投影到低維子空間中表示。但為了保留原始數據的分布特性，PCA要求投影后的樣本在各維度上的方差保持最大化。由于方差信息的保留，也使得PCA是維數約簡中對于原始數據信息丟失最少的一種方法。

設 W=[w1,w2,…wk,…,wd']，其中 wk?Rd為一單位投影向量，即由此保證求解的投影矩陣W為正交矩陣。根據PCA的最大方差的目標，可以建立如下的目標函數：

其中C為樣本的協方差矩陣,即：

由于式（2）為一個采用等式約束的優(yōu)化問題，因此可以采用Lagrange乘子法進行求解。首先建立Lagrange方程：

對式（4）求關于W 的導數并令導數為0，可以解得：

考慮W 的第k列wk,式（5）即為求解Cwk=λwk的特征向量wk問題，即wk為協方差矩陣C的k個特征值所對應的特征向量。因此，只需對C作特征值分解，并取前d'個特征向量拼成的矩陣即為所求的投影矩陣W。

2 KPCA

作為PCA的推廣，KPCA(Kernel Principle Component Analysis)的思想是通過非線性映射Φ：Rd∈RF將樣本由原始空間映射到高維、甚至無窮維的Hilbert空間F中，即 xi→Φ(xi)（i=1,2,…,n），然后在新的特征空間F中進行PCA處理。但是直接顯式地向高維空間進行特征映射會帶來相當高的運算代價。為了避免顯式映射，可以利用SVM等領域中的核方法，根據Mercer定理選擇合適的核函數通 過 計 算 核 矩 陣 K?Rn×n（Kij=k(xi,xj)）來隱式的計算特征映射。

對Cv=λv左乘Ψ(xk)T可以獲得如下的等價方程：

式（9）可以采用矩陣表示為：

其中In為所有元素均1/n的n×n矩陣。對?作特征值分解即獲得特征向量α,進一步即可以求得v。與PCA相同，我們希望獲得的投影矩陣為單位正交矩陣，因此需要對 v單位化，即約束‖v‖2=1。由于，有：

因此只需要對求得的α乘上對應特征向量平方根的倒數即可保證v是單位向量。進一步的，將C的各個特征向量拼合，即獲得最終的投影矩陣其中為第i個特征值對應的且經過單位化后的特征向量。

在對核函數的選擇上，可以根據Mercer定理來選擇合適的核函數進行特征映射。實際應用中較為常見的核函數有RBF核函數、多項式核函數與sigmoid核函數等。下面給出這三種核函數的計算方法：

（1）徑向基核函數（Radial Basis Function,RBF）

（3）sigmoid核函數

與SVM類似，對于不同的核函數，其參數會對最終的結果產生比較強的影響，需要根據實際應用進行參數選擇。

（2）多項式核函數（Polynomial Function）

3 KPCA與PCA的比較

KPCA作為PCA的擴展，其通過映射函數Φ把原始樣本映射到了高維Hilbert空間，并在其中進行PCA分析。因此雖然同屬于維數約簡方法，但兩者已具有本質上的區(qū)別。首先PCA是基于指標的，而KPCA是基于樣本的。另外KPCA不僅適合于解決非線性特征提取問題，它還能比PCA提供更多的特征數目和更多的特征質量，并且能夠通過核函數映射，實現對線性不可分樣本增強投影后線性可分性。但是KPCA也具有抽取指標的實際意義不是很明確的不足，計算也比PCA復雜。PCA僅是原有各特征的線性組合，仍能夠通過原始維度給出投影后各維度的解釋，而KPCA經過核函數映射后則難以明確其物理意義。另外在核函數的參數選擇上也會很大的影響維數約簡的效果，所以參數的選擇仍是KPCA改進的方向。

4 實驗結果分析

在合成的數據上采用PCA與KPCA進行了兩組對比實驗，實驗結果如圖1與圖2所示，所生成的合成數據均為2維樣本以方便進行圖示。其中圖1為線性可分的數據，兩類數據均由高斯分布抽樣所得，圖1（a）為原始數據，圖1（b）為采用PCA與KPCA降至1維所獲得的結果，其中KPCA采用了線性核?？梢园l(fā)現PCA與KPCA的投影結果重合。這表明KPCA在不采用核函數的情況下完全可以勝任PCA的線性投影工作。

圖1 對線性可分樣本的PCA與KPCA（線性核）投影結果

圖2對非線性可分樣本的PCA與KPCA投影結果

圖2 中給出對非線性可分樣本的PCA與分別采用了RBF核與多項式核投影后的結果。與圖1實驗不同，這里投影后結果仍選擇為2維。可以發(fā)現PCA投影結果與原始數據完全一致，說明PCA對非線性可分的數據無法找到可行的投影方向。與之相反的是，使用RBF核和多項式核函數的KPCA則能夠將3類樣本經映射到高維空間再作PCA后，實現了3類樣本的線性可分性，也從實驗上證明了KPCA除了維數約簡外，還具有增強樣本類別間線性可分的能力。

5 結語

本文對PCA與KPCA的實現進行了分析研究，并對兩者之間的聯系與區(qū)別作了對比。通過在合成數據上的實驗表明KPCA具有良好的非線性維數約簡能力，而且對于線性不可分的數據在投影后能夠實現或增強線性可分性。在下一步工作中將把KPCA應用到行人外觀驗證的具體研究中。

[1]Cao L J,Chua K S,Chong W K,et al.A Comparison of PCA,KPCA and ICA for Dimensionality Reduction in Support Vector Machine[J].Neurocomputing,2003,55(1-2)：321-336.

[2]Wen Y,He L,Shi P.Face recognition using difference vector plus KPCA[J].Digital Signal Processing,2012,22(1)：140-146.

[3]Kang Q,Wang K,Huang B,et al.Kernel optimization for KPCA Based on Gaussianity Estimation[J].International Journal of Bio-Inspired Computation,2014,6(2)：91-107.

[4]Yuan T,Yang W,Zhou F,et al.Single Image Super-Resolution Via Sparse KPCA and Regression[C].IEEE International Conference on Image Processing.IEEE,2015：2130-2134.

[5]Zhe Li,Kruger,Uwe,Lei Xie,et al.Adaptive KPCA Modeling of Nonlinear Systems[J].IEEE Transactions on Signal Processing,2015,63(9)：2364-2376.

[6]Fan Z,Wang J,Xu B,et al.An Efficient KPCA Algorithm Based on Feature Correlation Evaluation[J].Neural Computing&Applications,2014,24(7-8)：1795-1806.

[7]杜卓明,屠宏,耿國華.KPCA方法過程研究與應用[J].計算機工程與應用,2010,46(7)：8-10.

[8]趙劍華,王順芳,張飛龍.基于組合核函數KPCA的人臉識別研究[J].計算機工程與設計,2014,35(2)：631-635.

Research on Dimensionality Reduction of KPCA

DONG Hu-sheng
（Suzhou Institute of Trade and Commerce,Suzhou 215009）

To lower the heavy computation induced by high dimensional samples in data analysis,the original data is often preprocessed by dimension reduction methods.Due to the nonlinear map capability provided by kernel trick,the dimension reduction methods with kernel have a greater advantage than those based on linear projection.Carries out a research on the Kernel Principle Component Analysis(KPCA),and conducts an experiment on synthesis data.The experimental result shows that not only the dimension reduction but also linear separability can be achieved by KPCA.

Dimension Reduction；Linear Projection;Kernel Method;KPCA

蘇州經貿學院科研項目（No.KY-ZR1407）

1007-1423（2017）31-0003-05

10.3969/j.issn.1007-1423.2017.31.001

董虎勝（1981-），江蘇泗洪人，男，講師，研究方向為機器學習與計算機視覺

2017-09-22

2017-10-28