pca和KPCA的基本介绍.doc

第二章 主成分分析
第二章 主成分分析

1. 主成分分析的基本原理
统计学上PCA的定义为用几个较少的综合指标来代替原来较多的指标，而这些较少的综合指标既能尽多地反映原来较多指标的有用信息，且相互之间又是无关的。作为一种建立在统计最优原则基础上的分析方法，主成分分析具有较长的发展历史。在1901年，Pearson首先将变换引入生物学领域，并重新对线性回归进行了分析，得出了变换的一种新形式。Hotelling于1933年则将其与心理测验学领域联系起来，把离散变量转变为无关联系数。在概率论理论建立的同时，主成分分析又单独出现，由Karhunen于1947年提出，随后Loeve于1963年将其归纳总结。因此，主成分分析也被称为K-L变换[1]。
PCA运算就是一种确定一个坐标系统的直交变换，在这个新的坐标系统下，变换数据点的方差沿新的坐标轴得到了最大化。这些坐标轴经常被称为是主成分。PCA运算是一个利用了数据集的统计性质的特征空间变换，这种变换在无损或很少损失了数据集的信息的情况下降低了数据集的维数。
PCA的基本原理如下：给定输入数据矩阵 (通常)，它由一些中心化的样本数据构成，其中且
(2-1)
PCA通过式(2-2)将输入数据矢量变换为新的矢量
(2-2)
其中：U是一个正交矩阵，它的第列是样本协方差矩阵
(2-3)
的第个本征矢量。换句话说，PCA首先求解如下的本征问题
(2-4)
其中是的一个本征值，是相应的本征矢量。当仅利用前面的个本征矢量时(对应本征值按降序排列)，得矩阵 。新的分量称为主分量[2]。最大特征值对应的最大特征向量就是第一个主成分,这个特征向量就是数据有最大方差分布的方向。第二主成分也就是第二大特征值对应的特征向量，数据点沿着这个方向方差有第二大变化，且这个特征向量与第一个是正交的。
实际过程中原始数据如果没有经过中心化，即式(2-1)不成立，则也可以对数据进行标准化处理。即对每一个指标分量作标准化处理
(2-5)
其中样本均值： (2-6)
样本标准差： (2-7)
得到，接下来进行以上运算，这就是标准的PCA，这种标准化方法有效的减少了数据量纲对数据提取的影响[3]。
2. 主成分分析的实现步骤
基于上述主成分分析的基本原理，可以得出主成分分析的计算步骤如下所示：
1、将所获得的个指标(每一指标有个样品）的一批数据写成一个()维数据矩阵．
2、对矩阵A作标准化处理：即对每一个指标分量进行标准化处理，利用公式(2-5)，从而得到。
3、由式(2-8)计算样本矩阵的相关系数矩阵
(2-8)
4、运用Jacobi迭代方法计算R的特征值，即对应的特征向量。
5、特征值按降序排序(通过选择排序)得并对特征向量进行相应调整得。
6、通过施密特正交化方法单位正交化特征向量，得到。
7、计算特征值的累积贡献率，根据给定的提取效率，如果,则提取个主成分。
8、计算已标准化的样本数据X在提取出的特征向量上的投影，其中。
所得的Y即为进行特征提取后的数据也就是数据降维后的数据。
第三章 基于核的主成分分析

1. 核方法
作为一种由线性到非线性之间的桥梁，核方法的相关研究起源于20世纪初叶，其在模式识别中的应用至少可以追溯到1964年，然而直到最近几年，核方法的研究开始得到广泛的重视，从而相继提出了各种基于核方法的理论和方法。
核方法是一系列先进性数据处理技术的总称，其共同特点是这些数据处理方法都应用了核映射。核函数方法的基本原理是通过非线性函数把输入空间映射到高维空间，在特征空间中进行数据处理，其关键在于通过引入核函数，把非线性变换后的特征空间内积运算转换为原始空间的核函数计算，从而大大简化了计算量[4]。
从具体操作过程上看，核方法首先采用非线性映射将原始数据由数据空间映射到特征空间，进而在特征空间进行对应的线性操作，如图3-1所示：
由于采用了非线性映射，且这种非线性映射往往是比较复杂的，从而大大增强了非线性数据的处理能力。
从本质上讲，核方法实现了数据空间、特征空间、和类别空间之间的非线性变换。设和为数据空间中的样本点，数据空间到特征空间的映射函数为，核函数的基础是实现向量的内积变换
(3-1)
通常，非线性变换函数相当复杂，而运算过程中实际用到的核函数则相对简单的多，这正是核方法迷人的地方。
核方法
由特征空间回到数据空间
非线性映射
数据空间
特征空间
由数据空间回到特征空间

非线性操作
SVM
SVR
KPCA
KFD

线性操作：
分类
回归
PCA
FD

图3-1 核方法框架示意图
对于核函数必须满足Mercer条件：对于任意给定的对称函数，它是某个特征空间中的内积运算的充要条件是对于任意的不恒为0的函数满足
，有 (3-2)
式(3-2)给出了函数成为核函数的充要条件。
考虑到核方法的基础是实现了一种由输入空间到特征空间的非线性映射，假设输入空间数据为，对任意对称、连续且满足Mercer条件的函数，存在一个Hilbert空间,对映射有
(3-3)
式中是空间的维数。
常用的核函数有以下几种形式：
线性核函数 (3-4)
P阶多项式核函数 (3-5)
高斯径向基函数（RBF）核函数 (3-6)
多层感知器核函数 (3-7)
2. 基于核的主成分分析的基本原理
假设为训练样本，用表示输入空间。KPCA方法的基本思想是通过某种隐式方式将输入空间映射到某个高维空间(常称为特征空间)，并且在特征空间中实现PCA[5,6] 。假设相应的映射为，其定义如下

核函数通过映射将隐式的实现点到F的映射，并且由此映射而得的特征空间中数据满足中心化的条件，即
(3-8)
则特征空间中的协方差矩阵为：
(3-9)
现求的特征值和特征向量
， (3-10)
即有
(3-11)

考虑到所有的特征向量可表示为的线性张成，即
(3-12)
则有
(3-13)
其中。定义维矩阵K
(3-14)
则式子(3-13)可以简化为
(3-15)
显然满足
(3-16)
求解(3-16)就能得到特征值和特征向量，对于测试样本在特征向量空间的投影为
(3-17)
将内积用核函数替换则有
(3-18)
当(3-8)不成立时，需进行调整，
(3-19)
则核矩阵可修正为
(3-20)
3. 基于核的主成分分析的实现步骤
基于上述KPCA的基本原理，可得KPCA的处理过程如下：
1、将所获得的个指标(每一指标有个样品)的一批数据写成一个()维数据矩阵
。
2、计算核矩阵，先选定高斯径向核函数中的参数，再由式(3-14)，计算核矩阵K。
3、通过(3-20)修正核矩阵得到KL。
4、运用Jacobi迭代方法计算KL的特征值即对应的特征向量。
5、特征值按降序排序(通过选择排序)得并对特征向量进行相应调整得。
6 、通过施密特正交化方法单位正交化特征向量，得到。
7、计算特征值的累积贡献率，根据给定的提取效率，如果,则提取个主分量。
8、计算已修正的核矩阵在提取出的特征向量上的投影，其中。
所得的投影即为数据经KPCA降维后所得数据。
4. PCA和KPCA的比较
主成分分析属于代数特征分析方法，是模式识别领域中一种经典的特征抽取和降维方法。但是PCA的缺点是需要很大的存储空间和计算复杂度。如果原始空间的维数是, PCA需要分解一个的非稀疏矩阵。因为PCA是一种线性映射方法，降维后的表示是由线性映射生成的，它忽略了数据之间高于2阶的相互关系，所以抽取的特征并不是最优的，这在一定程度上影响了PCA方法的效果[7]。核主成分分析是线性PCA的非线性扩展算法，它采用非线性的方法抽取主成分，即KPCA是在通过映射函数把原始向量映射到高维空间F，在F上进行PCA分析[8]。
KPCA与PCA具有本质上的区别：PCA是基于指标的，而KPCA是基于样本的。KPCA不仅适合于解决非线性特征提取问题，而且它还能比PCA提供更多的特征数目和更多的特征质量，因为前者可提供的特征数目与输入样本的数目是相等的，而后者的特征数目仅为输入样本的维数[4]。KPCA的优势是可以最大限度地抽取指标的信息；但是KPCA抽取指标的实际意义不是很明确，计算也比PCA复杂。
PCA的主分量具有如下的特征：
1、行矢量线形无关;
2、用最前面的几个主分量表示原输入，其均方逼近误差最小[9]。
KPCA的特征与特征空间中的PCA的特征是一样的。其特征如下：
1、前()个主成分或者是特征向量上的投影，与其余个正交方向相比有较大的方差。
2、通过前个主分量(在任意个可能的方向中)描绘中的观测报告所产生的均方近似误差是最小的。
3、主成分之间是线形无关的。
4、前个主分量相对于输入而言拥有最大的共有信息量。
这表明典型的PCA的性质在特征空间中依然得到保留，如最大变化的正交方向、最小的L2-重建误差、相对于输入而言最大的共有信息等[9]。
5. 主动学习在基于核的主成分分析中的应用
基于核的主成分分析方法是基于样本的，计算所需的时间和内存与输入空间的维数无关，但与样本数目却密切相关随着样本数量的增多，计算的时间复杂度和空间复杂度也随之增加。
事实上，各个样本点对降维的贡献是不一样，因此可以通过第一主元对应的特征向量(其中为样本的数目)来过滤样本的方法减少样本数目。具体操作步骤如下：
1、取该主元特征向量分量的绝对值，并对所得的绝对值进行降序排序得到，并记录其对应的样本标号。
2、计算的各个分量累计所占比重，若大于给定的值，提取中的前个值，并将所得的个样本编号升序排序得，以此样本编号对应的样本组合成新的样本数据，即。
3、对XX执行一次KPCA运算，提取出主成分为V，计算投影，其中KK为提取出的样本标号对应的核矩阵KL(原始数据对应的修正的核矩阵)的行组合而成。
这种方法能简化计算量，但如果样本数目太多时，上述方法显然不可行。一是耗费太多的时间，二是运算需要占用太多的内存，比如，128M内存只能完成3000个样本的计算[4]。这就需要对样本进行分组训练，这种对样本进行筛选方法叫做AKPCA 。设样本数目为N，现在将其分成M组，，为每一组中具有的样本数目，设第组中与第一投影方向相对应的系数向量为：，并假设每一组中保留的样本数目为，由下式决定：
(3-21)
式中为阈值，可根据问题需要确定，越小，筛选掉的样本越多，但也可能产生较大的误差。由排序得来，满足：。
综上，AKPCA的具体计算方法为：
1、重采样，形成组样本；
2、对各组样本进行KPCA，对样本进行初步筛选；
3、组合初步筛选好的样本，形成新的样本集，并对之进行KPCA，在此基础上，对样本进一步筛选；
4、根据问题的规模，重复上述3步，直到形成最终的投影方向[4]。
实际上也可以用前两个主分量的绝对值的和来代替第一主分量的绝对值来筛选样本，达到简化样本数目的目的。该实验中就是采用了这种方法。
6. 核主成分分析的应用及进一步研究
KPCA由于其特征提取速度快、特征信息保留充分等特征，被广泛的应用到模式识别中。比如去噪，人脸识别，三维物体识别，遥感图像分析等方面都有广泛的应用[11]。
KPCA存在三点不足：各特征的物理意义很不明确，一般的PCA仅是原有各特征的线性叠加，还可以勉强找出其含义，而KPCA是不可能明确其物理意义的；求投影所需的计算相对要难得多；测试样本在空间向量上的投影太复杂。
对于第一个不足是不可避免的，因为这是非线性变换引起的，而核方法必须经过非线性变换。后两个不足实际上涉及到的是一个问题就是如何减少样本的数目。故如何从学习样本集中选择具有代表性的学习样本是KPCA的一个研究方向，或许主动学习(active learning)是解决这一问题的有效途径。另外由于核函数的参数会影响特征提取效果，故参数的选择也是KPCA改进的方向。虽然上文中也简单介绍到这两方面，但KPCA方法的改进仍需研究。