董虎勝

（蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院，蘇州 215009）

KPCA維數(shù)約簡研究

董虎勝

（蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院，蘇州 215009）

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

維數(shù)約簡；線性投影；核方法；KPCA

0 引言

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

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

本文對KPCA的實(shí)現(xiàn)進(jìn)行了研究，并對PCA與KPCA的差異進(jìn)行對比分析。實(shí)驗(yàn)結(jié)果表明，KPCA具有良好的非線性數(shù)據(jù)維數(shù)約簡與增強(qiáng)數(shù)據(jù)線性可分的性能。

1 PCA

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

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

其中C為樣本的協(xié)方差矩陣,即：

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

對式（4）求關(guān)于W 的導(dǎo)數(shù)并令導(dǎo)數(shù)為0，可以解得：

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

2 KPCA

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

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

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

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

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

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

（1）徑向基核函數(shù)（Radial Basis Function,RBF）

（3）sigmoid核函數(shù)

與SVM類似，對于不同的核函數(shù)，其參數(shù)會對最終的結(jié)果產(chǎn)生比較強(qiáng)的影響，需要根據(jù)實(shí)際應(yīng)用進(jìn)行參數(shù)選擇。

（2）多項(xiàng)式核函數(shù)（Polynomial Function）

3 KPCA與PCA的比較

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5 結(jié)語

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

[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方法過程研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(7)：8-10.

[8]趙劍華,王順芳,張飛龍.基于組合核函數(shù)KPCA的人臉識別研究[J].計(jì)算機(jī)工程與設(shè)計(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

蘇州經(jīng)貿(mào)學(xué)院科研項(xiàng)目（No.KY-ZR1407）

1007-1423（2017）31-0003-05

10.3969/j.issn.1007-1423.2017.31.001

董虎勝（1981-），江蘇泗洪人，男，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)與計(jì)算機(jī)視覺

2017-09-22

2017-10-28