KPCA维数约简研究

董虎胜

（苏州经贸职业技术学院，苏州 215009）

KPCA维数约简研究

董虎胜

（苏州经贸职业技术学院，苏州 215009）

在对数据分析与处理时，为了避免高维数据所带来的巨大运算开销，通常需要对原始数据进行维数约简。与基于线性投影的维数约简方法相比，基于核方法的维数约简由于能够实现对样本的非线性映射，因此在数据预处理中具有更大的优势。对基于核方法的主成分分析(KPCA)维数约简方法进行研究，并通过实验结果证明KPCA不仅能够实现数据的降维，还具有增强数据线性可分性的优势。

维数约简；线性投影；核方法；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）为一个采用等式约束的优化问题，因此可以采用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分析。因此虽然同属于维数约简方法，但两者已具有本质上的区别。首先PCA是基于指标的，而KPCA是基于样本的。另外KPCA不仅适合于解决非线性特征提取问题，它还能比PCA提供更多的特征数目和更多的特征质量，并且能够通过核函数映射，实现对线性不可分样本增强投影后线性可分性。但是KPCA也具有抽取指标的实际意义不是很明确的不足，计算也比PCA复杂。PCA仅是原有各特征的线性组合，仍能够通过原始维度给出投影后各维度的解释，而KPCA经过核函数映射后则难以明确其物理意义。另外在核函数的参数选择上也会很大的影响维数约简的效果，所以参数的选择仍是KPCA改进的方向。

4 实验结果分析

在合成的数据上采用PCA与KPCA进行了两组对比实验，实验结果如图1与图2所示，所生成的合成数据均为2维样本以方便进行图示。其中图1为线性可分的数据，两类数据均由高斯分布抽样所得，图1（a）为原始数据，图1（b）为采用PCA与KPCA降至1维所获得的结果，其中KPCA采用了线性核。可以发现PCA与KPCA的投影结果重合。这表明KPCA在不采用核函数的情况下完全可以胜任PCA的线性投影工作。

图1 对线性可分样本的PCA与KPCA（线性核）投影结果

图2对非线性可分样本的PCA与KPCA投影结果

图2 中给出对非线性可分样本的PCA与分别采用了RBF核与多项式核投影后的结果。与图1实验不同，这里投影后结果仍选择为2维。可以发现PCA投影结果与原始数据完全一致，说明PCA对非线性可分的数据无法找到可行的投影方向。与之相反的是，使用RBF核和多项式核函数的KPCA则能够将3类样本经映射到高维空间再作PCA后，实现了3类样本的线性可分性，也从实验上证明了KPCA除了维数约简外，还具有增强样本类别间线性可分的能力。

5 结语

本文对PCA与KPCA的实现进行了分析研究，并对两者之间的联系与区别作了对比。通过在合成数据上的实验表明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