pca和KPCA的基本介绍

1、第二章主成分分析1.主成分分析的基本原理统计学上PCA的定义为用几个较少的综合指标来代替原来较多的指标，而这些较少的综合指标既能尽多地反映原来较多指标的有用信息，且相互之间又是无关的。作为一种建立在统计最优原则基础上的分析方法，主成分分析具有较长的发展历史。在1901年，Pearson首先将变换引入生物学领 域，并重新对线性回归进行了分析，得出了变换的一种新形式。Hotelling于1933年则将其与心理测验学领域联系起来，把离散变量转变为无关联系 数。在概率论理论建立的同时，主成分分析又单独出现，由Karhunen于1947 年提出，随后Loeve于1963年将其归纳总结。因此，主成分分析也

2、被称为 K-L 变换 1。PCA运算就是一种确定一个坐标系统的直交变换，在这个新的坐标系 统下，变换数据点的方差沿新的坐标轴得到了最大化。这些坐标轴经常被称为是主成分。PCA运算是一个利用了数据集的统计性质的特征空间变换， 这种变换在无损或很少损失了数据集的信息的情况下降低了数据集的维数。PCA的基本原理如下：给定输入数据矩阵 Xmn (通常m n),它由一 些中心化的样本数据Xiim1构成，其中Xi Rn且mXi 0(2-1)i 1PCA通过式(2-2)将输入数据矢量Xi变换为新的矢量S U TXi(2-2)T XiXi其中：U是一个n n正交矩阵，它的第i列Ui是样本协方差矩阵(2-3)的

3、第i个本征矢量。换句话说，PCA首先求解如下的本征问题iUi CUi i 1,.,n(2-4)其中 是C的一个本征值，Ui是相应的本征矢量。当仅利用前面的 P个本 征矢量时(对应本征值按降序排列)，得矩阵S UTX 。新的分量S称为主 分量2 o最大特征值 对应的最大特征向量u就是第一个主成分，这个特征向 量就是数据有最大方差分布的方向。第二主成分也就是第二大特征值对应的 特征向量，数据点沿着这个方向方差有第二大变化， 且这个特征向量与第一 个是正交的。实际过程中原始数据如果没有经过中心化，即式 (2-1)不成立，则也可 以对数据进行标准化处理。即对每一个指标分量作标准化处理Aj AjXij-

4、j(2-5)Sj1 m其中样本均值:样本标准差：Aj1 Aj(2-6)Sjm11 2)2(2-7)m i 1得到X (Xij)mn,接下来进行以上运算，这就是标准的PCA,这种标准化方 法有效的减少了数据量纲对数据提取的影响 冏。2.主成分分析的实现步骤基于上述主成分分析的基本原理，可以得出主成分分析的计算步骤如下所示：1、将所获得的n个指标(每一指标有m个样品)的一批数据写成一个a11(m n)维数据矩阵A 1 pam12、对矩阵A作标准化处理：即对每一个指标分量进行标准化处理，利用公式(2-5),从而得到X (Xij)mn。3、由式(2-8)计算样本矩阵的相关系数矩阵 1 T一R X X(

5、rj)nn(2-8)m 14、运用Jacobi迭代方法计算R的特征值i,., n,即对应的特征向量Vi,，Vn。5、特征值按降序排序(通过选才¥排序)得1' . n'并对特征向量进行相应调整得Vi',., Vn' o6、通过施密特正交化方法单位正交化特征向量，得到 1,., n。7、计算特征值的累积贡献率Bi,., Bn,根据给定的提取效率p,如果Btp,则提取t个主成分1,., to8、计算已标准化的样本数据X在提取出的特征向量上的投影 Y X ,其中(1,., J。所得的Y即为进行特征提取后的数据也就是数据降维后的数据。第三章基于核的主成分分析1.

6、核方法作为一种由线性到非线性之间的桥梁，核方法的相关研究起源于20世纪初叶，其在模式识别中的应用至少可以追溯到1964年，然而直到最近几年，核方法的研究开始得到广泛的重视，从而相继提出了各种基于核方法的理论和方法。核方法是一系列先进性数据处理技术的总称，其共同特点是这些数据处理方 法都应用了核映射。核函数方法的基本原理是通过非线性函数把输入空间映射到 高维空间，在特征空间中进行数据处理，其关键在于通过引入核函数，把非线性 变换后的特征空间内积运算转换为原始空间的核函数计算，从而大大简化了计算量%从具体操作过程上看，核方法首先采用非线性映射将原始数据由数据空间映射到特征空间，进而在特征空间进行对

7、应的线性操作，如图 3-1所示：由于采用了非线性映射，且这种非线性映射往往是比较复杂的， 从而大大增强了 非线性数据的处理能力。从本质上讲，核方法实现了数据空间、特征空间、和类别空间之间的非线性 变换。设x和Xj为数据空间中的样本点，数据空间到特征空间的映射函数为，核函数的基础是实现向量的内积变换(Xi,Xj) K(Xi,Xj)(Xi) (Xj)(3-1)通常，非线性变换函数 (?)相当复杂，而运算过程中实际用到的核函数K(?,?)则相对简单的多，这正是核方法迷人的地方。数据空间特征空间图3-1核方法框架示意图对于核函数必须满足 Mercer条件：对于任意给定的对称函数 K(x，Xj),它 是

8、某个特征空间中的内积运算的充要条件是对于任意的不包为0的函数g(x)满足g(x)2dx,有 K(x, y)g(x)g(y)dxdy 0(3-2)式(3-2)给出了函数成为核函数的充要条件。考虑到核方法的基础是实现了一种由输入空间到特征空间的非线性映射，假设输入空间数据为xi RdL(i 12|,N),对任意对称、连续且满足 Mercer条件 的函数 2为内)，存在一个Hilbert空间H ,对映射 ：RdL H有dFK(xi,xj)n(xi) (xj)(3-3)n 1式中dF是H空间的维数。常用的核函数有以下几种形式：线性核函数 K(x, x) x xi(3-4)P阶多项式核函数 K(x,xi

9、) (x xi) 1p(3-5)高斯径向基函数(RBF核函数 K(x,xJ exp(卜子)(3-6)多层感知器核函数 K(x,xi) tanhv(xx)c(3-7)2,基于核的主成分分析的基本原理假设xi,x2,.,xm为训练样本，用x表示输入空间。KPCA方法的基本思想 是通过某种隐式方式将输入空间映射到某个高维空间 (常称为特征空间)，并且在 特征空间中实现pca5,6。假设相应的映射为 ，其定义如下核函数通过映射将隐式的实现点x到F的映射，并且由此映射而得的特征空间 中数据满足中心化的条件，即M(x ) 0(3-8)1则特征空间中的协方差矩阵为：1 MT一 一、C(x ) (x )(3-

10、9)M i现求C的特征值0和特征向量V F 0 , C(3-10)即有(x ) C )( (xv) )(3-11)考虑到所有的特征向量可表示为3)，(x2),.,(xm)的线性张成，即Mv i (xi)(3-12)i 1则有M(x)(x) (3-13)1M(x )(xw) (xw) (x )w 1其中v 1,2,，M。定义M M维矩阵KK : ( (x ) (x )(3-14)则式子(3-13)可以简化为M K K2(3-15)显然满足M K(3-16)求解(3-16)就能得到特征值和特征向量，对于测试样本在特征向量空间Vk的投影为Mkk(x)( i) ( (Xi), (x)(3-17)i 1

11、将内积用核函数替换则有M(k (x)( i)kK(x,x)(3-18)当(3-8)不成立时，需进行调整，1(x ) (x ) M则核矩阵可修正为1 MK K ( K wM w 13.基于核的主成分分析的实现步骤 基于上述KPCA的基本原理，可得 1、将所获得的n个指标(每一指标有维数据矩阵aA ,Iam1M(xv)1,.,M(3-19)v 1MM MKw)Kw(3-20)w 1M w, 1KPCA的处理过程如下：' m个样品)的一批数据写成一个(m n)III a1nII 八of p | amn2、计算核矩阵，先选定高斯径向核函数中的参数，再由式 (3-14),计算核 矩阵Ko3、通过

12、(3-20)修正核矩阵得到KL。4、运用Jacobi迭代方法计算KL的特征值1,., n即对应的特征向量Vi,.,%5、特征值按降序排序(通过选择排序)得1' .n'并对特征向量进行相应调整得 v1 ,., vn o6、通过施密特正交化方法单位正交化特征向量，得到 1,., n07、计算特征值的累积贡献率Bi,., Bn ,根据给定的提取效率p ,如果B p, 则提取t个主分量1,., t 08、计算已修正的核矩阵X在提取出的特征向量上的投影 Y KL ，其中(i,., t )。所得的投影Y即为数据经KPCA降维后所得数据。4. PCA和KPCA勺比较主成分分析属于代数特征分析

13、方法，是模式识别领域中一种经典的特征抽取 和降维方法。但是PCA的缺点是需要很大的存储空间和计算复杂度。如果原始 空间的维数是n, PCA需要分解一个n n的非稀疏矩阵。因为PCA是一种线性 映射方法，降维后的表示是由线性映射生成的，它忽略了数据之间高于2阶的相 互关系,所以抽取的特征并不是最优的，这在一定程度上影响了PCA方法的效果口。核主成分分析是线性 PCA的非线性扩展算法，它采用非线性的方法抽取 主成分，即KPCA是在通过映射函数 把原始向量映射到高维空间 F,在F上 进行PCA分析网。KPCA与PCA具有本质上的区别：PCA是基于指标的，而KPCA是基于样 本的。KPCA不仅适合于解

14、决非线性特征提取问题，而且它还能比PCA提供更多的特征数目和更多的特征质量，因为前者可提供的特征数目与输入样本的数目 是相等的，而后者的特征数目仅为输入样本的维数4。KPCA的优势是可以最大 限度地抽取指标的信息；但是 KPCA抽取指标的实际意义不是很明确，计算也 比PCA复杂。PCA的主分量具有如下的特征：1、行矢量S(i),i 1,|U|,p线形无关；2、用最前面的几个主分量表示原输入，其均方逼近误差最小。KPCA勺特征与特征空间中的PCA的特征是一样的。具特征如下：1、前p( p 1.M )个主成分或者是特征向量上的投影，与其余 p个正交 方向相比有较大的方差。2、通过前p个主分量(在任

15、意p个可能的方向中)描绘F中的观测报告所产 生的均方近似误差是最小的。3、主成分之间是线形无关的。4、前p个主分量相对于输入而言拥有最大的共有信息量。这表明典型的PCA的性质在特征空间中依然得到保留，如最大变化的正交 方向、最小的L2-重建误差、相对于输入而言最大的共有信息等9。5.主动学习在基于核的主成分分析中的应用基于核的主成分分析方法是基于样本的，计算所需的时间和内存与输入空间 的维数无关，但与样本数目却密切相关。随着样本数量的增多，计算的时间复杂 度和空间复杂度也随之增加。事实上，各个样本点对降维的贡献是不一样，因此可以通过第一主元对应的 特征向量Vi (vJU，Vm)(其中m为样本的

16、数目)来过滤样本的方法减少样本数 目。具体操作步骤如下：1、取该主元特征向量分量 V (v/Vm)的绝对值，并对所得的绝对值进行 降序排序得到V1 (v1,|“,Vm),并记录其对应的样本标号A (ai,|,am)o2、计算V1的各个分量累计所占比重D (dij",dm),若dk大于给定的值， 提取A中的前k个值，并将所得的k个样本编号升序排序得 A1 (A,|,Ak),以 此样本编号对应的样本组合成新的样本数据，即 XX (XaJMXaJ。3、对XX执行一次KPCA运算，提取出主成分为V,计算投影Y KK V , 其中KK为提取出的样本标号A1对应的核矩阵KL (原始数据对应的修正

17、的核矩 阵)的行组合而成。这种方法能简化计算量，但如果样本数目太多时，上述方法显然不可行。一 是耗费太多的时间，二是运算需要占用太多的内存，比如， 128M内存只能完成 3000个样本的计算4 o这就需要对样本进行分组训练，这种对样本进行筛选方法 叫做AKPCA。设样本数目为N,现在将其分成M组，N MN1 , N1为每一组 中具有的样本数目，设第i(i 1,|,M)组中与第一投影方向相对应的系数向量为i ： i ( 1,|, M) (i 1,|,M),并假设每一组中保留的样本数目为 Li (i 1,|,M), L由下式决定：L 2j 1一r(3-21)式中 为阈值，可根据问题需要确定,越小，

18、筛选掉的样本越多，但也可能产生较大的误差。由i排序得来，满足：1 m o综上，AKPCA的具体计算方法为：1、重采样，形成M组样本；2、对各组样本进行KPCA,对样本进行初步筛选；3、组合初步筛选好的样本，形成新的样本集，并对之进行KPCA,在此基础上，对样本进一步筛选；4、根据问题的规模，重复上述3步，直到形成最终的投影方向4。实际上也可以用前两个主分量的绝对值的和来代替第一主分量的绝对值来 筛选样本，达到简化样本数目的目的。该实验中就是采用了这种方法。6,核主成分分析的应用及进一步研究KPCA由于其特征提取速度快、特征信息保留充分等特征，被广泛的应用到 模式识别中。比如去噪，人脸识别，三维物体识别，遥感图像分析等方面都有广 泛的应用11。KPCA存在三点不足：各特征的物理意义很不明确，一般的 PCA仅是原有 各特征的