核函数在主成分分析中的应用

2014-11-04 15:26徐金宝
电脑知识与技术 2014年28期
关键词:主成分分析特征提取

摘要:主成分分析在对线性数据进行降维时非常有效,核函数能够将线性不可分的数据映射到高维希尔伯特空间中可能可分。将核函数应用到主成分分析中成为核主成分分析。从核函数的性质、核函数的参数调整、核函数的构造等方面对核主成分分析进行应用与实现,并结合核Fisher判别分析,对样例数据进行核主成分分析,结论表明,效果良好,但执行速度较慢,需要后续改进。

关键词:核函数;主成分分析;特征提取;协方差矩阵;Gram矩阵

中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2014)28-6659-04

智能时代的到来,模式识别得到了广泛的重视和应用。支持向量机(SVM)由于有着坚实的统计学理论基础,能够实现结构风险最小化,特别是能够克服机器学习中经常遇到的“维数灾难”问题,并且在二类分类中表现出优异的性能,从而在分类中占有重要地位。SVM不仅能够进行线性分类,而且在非线性分类中也表现出良好的性能。这归因于SVM中成功应用了核函数的思想,把在低维空间中不可分的输入数据映射到高维的特征空间(也叫希尔伯特空间)中去,在高维空间中就有可能可分。核函数思想在SVM中的成功应用,打开了核函数的应用领域,从本质上来说,只要一个应用中直接或间接地需要用到两个向量内积的运算,核函数都有可能在该领域有所作为。这样,核函数的应用,并没有改变本来应用的思路,同时,核函数注重的是两个向量之间的内积结果,使得在应用中并不需要知道真正的变换函数是什么,从而方便了分类或聚类等应用。主成分分析(Principal component analysis,PCA)在模式识别中得到了广泛的应用,是一个对线性输入空间进行降维的有效方法,但实际工程应用中的数据空间往往不是线性的,如果能够将核函数的思想应用到PCA中,就能够使得PCA对非线性的数据空间也能够进行有效降维,能够有效改进模式识别的算法效率,降低对存储空间的要求。

当前对核主成分分析的研究取得了很多成果,在应用中也得到了有效应用。但是,核主成分分析的具体实现过程、核函数的参数选择、核函数的直接构造、由函数产生核以及主成分分析不考虑分类类别的改进上,还有很多工作需要做,该文在以上几方面予以分析,并在应用中予以实验验证。

1 核函数

核函数的研究起源于1909年,Mercer提出了核的定理与条件,1940年后,再生核得到研究,1964年Aizermann等人将核的思想运用到机器学习领域,1992年Vapnik等人在SVM中成功应用了核函数,从此核函数得到了深入的研究与应用。

核函数是一个n维欧氏空间Rn到希尔伯特空间H的变换上的内积函数,即K(x1,x2)= (Φ(x1)Φ(x2) )。

核函数具有一个重要特性:一个对称函数K(x1,x2)是核函数,那么K(x1,x2)对应于x1,x2…xn的Gram矩阵非负定;反过来,若K(x1,x2)对应于x1,x2…xn的Gram矩阵非负定,则K(x1,x2)是核函数。

因此寻找核函数可以利用以上性质,只要找到一个对称函数K(x1,x2),做出其对应的Gram矩阵,判断该矩阵的正定性就可以得出K(x1,x2)是否是核函数。当前较为广泛使用并有效的核函数有高斯径向基核函数[K(x1,x2)=exp(-||x1-x2||2/(2σ)2))]、多项式函数K(x1,x2)=((x1x2)+1)d。

但是,在实际工程应用中,有些应用场合,数据分布具有一定的特殊形式,通过多项式核函数或高斯径向基核函数并不能达到最佳效果,即使通过大量的实验,也很难找到最恰当的核函数参数。这时,可以根据数据分布的特点,进行核函数构造,这样构造出的核函数在数据处理上有可能达到很高的效率。

另外,还可以根据某些不是核函数的函数,通过一定的方式,构造出核函数。因为,根据核函数的性质,一个函数若是核函数,它对应的Gram矩阵必是非负定的。那么,若一个函数不满足这个特性,则可以通过一个过渡函数,运用以下公式将它改造为核函数:

[K(x1,x2)=i=1Ntrans(xi,x1)trans(xi,x2)]

其中,N为输入空间中样本的个数,x1、x2是输入空间的向量,trans()是一个过渡函数。实际上,Sigmoid核函数f(x)=1/(1+e-x)在手写数字识别领域得到了应用并取得较好效果,但是Sigmoid函数对应的Gram矩阵不具有非负定特性,因此,严格意义上来说Sigmoid函数不是一个真正的核函数,而是一个经过某个过渡函数改造成的核函数。[1]

2 主成分分析

2.1 主成分分析(PCA)

在对输入数据进行模式识别时,经常会发现样本数和输入的向量的维数很大的情况,这对处理时间和所占用的空间有很高的要求,处理得不好,会导致主存溢出的情况。因此,对于很大的维数,往往需要通过某种手段,将维数降低。实际上,这种情况是可行的。因为,在采集的数据样本中,很多属性之间有着关联。例如对学生考试进行分析,若有七门功课:语文、数学、英语、政治、生物、物理、化学,这些科目的成绩中很多科目成绩之间是相关的;再如,在定制衬衣时,需要身高、胸围、坐高、臂长、腰围、肋围等六项数据,但这些数据往往是相关的,实际中只要身高、胸围、腰围几项即可。

主成分分析(PCA)是数据降维的有效手段,特别是对于线性数据。PCA通过变换使得结果具有最大的均方差,在二维空间中,能够将每个样本投影到一个一维空间中。对于n维空间,可以将输入数据样本的协方差矩阵求出。协方差矩阵cov为:

[cov(A)pXp=1N-1i=1p(xi-x)(xj-x)] A为nXp数据输入矩阵

協方差矩阵是个对称矩阵,对角线上diag(cov(A))的元素即为对应向量的标准差。协方差矩阵保持了原始输入空间的信息,特别是,若原始输入空间数据满足高斯分布,则该输入数据的所有信息都在协方差矩阵中反映出来。

将协方差矩阵cov(A)求出特征值和特征向量,并将这些向量按照特征值的大小按降序排列。根据应用的需要,对特征值进行分析。将特征值的累计贡献率计算出来,并根据应用的要求,若一般应用环境,累计贡献率取85%即可;对于一些精度要求高的应用,累计贡献率取95%甚至以上。这样,将大于累计贡献率的特征值取出,将对应的特征向量排列成矩阵,将输入空间的数据通过该特征向量矩阵进行转换,就得到降维后的输入数据。

例如,当一个输入空间有30个数据,每个数据7个特征,经过计算得到7X7的协方差矩阵,对此协方差矩阵求特征值、特征向量,假设根据累计贡献率的要求,只需要4个主特征,得到一个7X4的特征向量矩阵。用输入样本数据或测试样本乘以这个矩阵,就得到降维后的数据。当然,数据原始信息会有一定的损失,但很小,一般不影响分类结果。

经过PCA降维后的数据,可以通过降维过程的逆操作,恢复成原来的数据。累计贡献率阈值越大,恢复数据的精度也就越高。注意降维过程减去了均值,恢复数据要加上这个均值。

2.2 Fisher判别分析(FDA)

PCA主要应用在线性数据降维上,在降维的过程中,可以发现主要通过协方差矩阵,对原始输入数据进行处理,并没有用到类别的信息,因此PCA是一种无监督的线性降维方式,这种降维方式对于有些分类,对导致较大偏差。

Fisher判别分析(FDA)在对主要成分进行分析时,不仅要进行原始数据的处理,同时要关注类别信息,因此,被称为有监督的主成分分析。FDA采用类间散布矩阵和类内散布矩阵,然后计算特征值和对应的特征向量。

Fisher判别分析(FDA)采用类内聚集程度与类间离散程度的比值也决定,该比值越大,说明对分类的贡献越大,该成分就有可能成为是主成分。

2.3 核主成分分析与核Fisher判别分析

主成分分析(PCA)对线性输入空间数据有良好的降维效果,采用核函数的思想,将核函数应用到PCA中,形成核主成分分析,这样,将在低维空间非线性很难降维的数据通过核函数映射到高维特征空间(希尔伯特空间)中,通过选择适当的核函数与参数,就有可能在高维空间中进行有效降维。FDA也可以采用核函数思想改进为核Fisher判别分析。

在分类中,有了降维后的数据,时间和空间效率能够提升,但在核主成分分析时没有对类别信息加以利用,因此在实际的分类中,可以采用核主成分分析结合核Fisher判别分析进行,这样对有些难以分类的数据集能够有效进行分类。

3 核主成分分析及其应用

3.1 核主成分分析的过程

传统PCA中,首先需要计算协方差矩阵:

[cov(A)pXp=1N-1i=1p(xi-x)(xj-x)]

采用核函数的特征空间的协方差矩阵为:

[cov(A)pXp=1N-1i=1p(?(xi)-?(x))(?(xj)-?(x))],其中[K(xi,xj)=?(xi)?(xj)]

若输入空间数据满足“中心化”,即[?(x)]=0,则上式可简化为:

[cov(A)pXp=1N-1i=1p(?(xi)(?(xj)]

根据PCA的特点及再生核理论,最优投影轴应该是特征空间中的样本的线性组合,写成拉格朗日函数形式并对线性相关系数求导,得:

[Kα=λα],其中[α]为特征空间的样本之间线性組合的系数。到了这一步,就可以对K矩阵求特征值和特征向量即可。

以上核主成分分析是假设数据的中心化即均值为零的情况。若不满足此条件,可以通过对特征空间的所有数据在希尔伯特空间平移一个均值的距离,这样的平移不改变特征数据的形状。

在进行核主成分分析时,也可以通过以下公式进行核矩阵K的中心化(标准化):

[K_new=K-U*K-K*U+U*K*U,其中U=(1)N*N/N(N是样本的个数)]

3.2 核主成分分析的应用与实现要点

Matlab在模式识别上具有直观、有强大的计算能力以及绘图能力,下面以Matlab 7.1作为平台,对核主成分分析进行实现。

3.2.1 传统PCA在Matlab上的实现

传统PCA在Matlab中有两个函数可以完成数据降维。

若输入数据的协方差矩阵已知,则可以通过pcacov()函数进行PCA降维。设协方差矩阵为V,则通过[c,l,e]=pcacov(V)就能得到V的所有特征值的降序排列l,每个主成分的贡献率e以及主成分系数c。可以通过函数barttest()进行Bartlett维数校验,通过pcares()函数进行主成分的残差分析。

最常用的做PCA分析的函数是pcacomp(),只需要输入数据矩阵X,就可以通过:

[c,s,l ,t2]=princomp进行PCA降维分析。C代表主成分的系数矩阵,s代表主成分矩阵,l代表降序排列的样本协方差矩阵的特征值,t2代表某个样品对应的霍特林(Hotelling) T2的统计量,这个统计量可以用来进行设备运行的故障检测,用来表示某个观测值与观测数据中心的距离,可以用作异常点分析。

在对输入数据矩阵计算协方差矩阵时,需要进行数据的标准化。可以用三种方法进行标准化(设输入数据矩阵为X,是一个nXp矩阵):

1) s=std(X)

stds=X./s(ones(n,1),:)

[c,s,l ,t2]=princomp(stds)

2) s=std(X)

stds=X./repmat(s,n,1)

[c,s,l ,t2]=princomp(stds)

3) s=zscore(X)

[c,s,l ,t2]=princomp(stds)

此外,在协方差的计算上,计算的顺序将会大大影响最终的结果。如100个样本30维特征,应该计算出的协方差矩阵是30X30,若没有注意到这一点,最终可能算出的协方差矩阵是100X100。

3.2.2 核主成分分析在Matlab上的实现

Matlab在模式识别工具箱stprtool里提供了进行核主成分分析的kpca()函数。stprtool工具箱不是Matlab 7.1的标准工具箱,需要下载后并设置到Matlab路径下。

%X是数据输入矩阵,数据分布可以不是线性,可以是圆状、椭圆状等

opt.ker=rbf%opt是结构变量,ker分量指出核函数类型,arg是参数

opt.arg=5

opt.new_dim=2 %new_dim是输出维数

Y=kpca(X,opt)

采用kpca函数很简单,但并不灵活。下面采用类Matlab来进行核主成分分析的算法实现。由于很多场合下的数据分布接近高斯分布,并且高斯分布的协方差矩阵对原始信息无丢失,下面核函数采用高斯径向基函数,高斯径向基函数需要输入一个参数。步骤如下:

1) 准备好训练数据T,测试数据TT,并设置高斯径向基函数的参数rbf,累计贡献率大小为thres;

2) 训练数据T、测试数据TT标准化;

3) 运用高斯核函数计算核矩阵,由于核矩阵是对称的,只需要计算出上三角矩阵即可,另一半元素用赋值完成,可以提高运算效率;

K(i,j)=exp(-norm(T(i,:)-T(j,:))^2/rbf);

4) 运用K_new=K-U*K-K*U+U*K*U中心化高斯核矩阵;

5) 对K_new进行特征值及特征向量的计算:[ev,evalues]=eig(K_new);

6) 计算累计贡献率;

7) 找出累计贡献率大于或等于thres的特征值,将对应的特征向量组成矩阵;

8) 对测试数据TT进行测试。

上述算法可以看出,采用了核函数,PCA成为核主成分分析,但具体的实现过程与传统的PCA很类似,但带来的效果是可以进行非线性降维。并且采用了核函数,从线性空间向高维空间的转换并不需要具体关心转换函数的形式。

3.3 核主成分分析的效果

下面用上述的核主成分分析算法对Matlab 7.1自带的cities.mat数据进行分析。cities.mat共收集了美国329个城市在历史上一段时期内城市生活质量的数据统计,共有9个指标:艺术、住房、健康、气候、娱乐、犯罪率、经济、交通和教育。

不同指标的数据值相差很大,需要进行标准化处理。

图1 核主成分分析后的第1主成分和第3主成分

圖2 cities的主成分pareto图

从运行的结果看,核主成分分析能够对cities.mat的数据进行降维,效果与传统PCA精度相当,运用tic、toc指令进行计时,传统PCA执行时间约 2.6秒,核主成分分析需时4.6秒,这是因为核主成分分析需要计算核矩阵,高斯核需要计算二范数以及exp运算。但核主成分分析由于采用了核,计算量上有所增加,但对线性、非线性输入空间都能进行有效降维。

4 结束语

核主成分分析在传统的主成分分析的基础上,有机地结合了核函数的思想,从而使得核主成分分析能够有效处理非线性的输入空间数据的降维。核主成分分析如果结合核聚类、核Fisher判别分析,充分利用输入数据的特点和分类类别,进行数据维度的降低,不仅能够加速分类的效率,而且能够提高精度。由于核函数的引入,因此,对于核函数的参数选择,核函数根据数据输入特点的直接构造,或从任一函数生成一个核函数就显得至关重要。未来的进一步应用将会在核函数的生成与核主成分分析、核Fisher判别分析的结合上,作为模式识别的预处理,将做深入的探讨。

参考文献:

[1] 徐勇,张大鹏,杨健.模式识别中的核方法及其应用[M].北京:国防工业出版社,2010:27-39,138-142.

[2] 邓乃扬,田英杰.支持向量机-理论、算法与拓展[M].北京:科学出版社,2009:92-96,105-114.

[3] 万家强,王越,刘羽.改进KPCA对分类数据的特征提取[J].计算机工程与设计,2010,31(18):4085-4092.

[4] 汪司飞,黄斐.基于K-均值聚类的KPCA在故障诊断中的应用[J].计算机应用与软件,2013,3(4):120-130.

[5] 邓貌,陈旭,陈天翔,等.采用核聚类分析的KPCA改进算法[J].智能系统学报,2010,5(3):221-226.

[6] 杜卓明,屠宏,耿国华.KPCA方法过程研究与应用[J].计算机工程与应用,2010,46(7) :8-10.

[7] 周品.MATLAB概率与数理统计[M].北京:清华大学出版社,2012:373-382.

猜你喜欢
主成分分析特征提取
基于Gazebo仿真环境的ORB特征提取与比对的研究
基于Daubechies(dbN)的飞行器音频特征提取
一种基于LBP 特征提取和稀疏表示的肝病识别算法
基于NAR模型的上海市房产税规模预测
主成分分析法在大学英语写作评价中的应用
江苏省客源市场影响因素研究
SPSS在环境地球化学中的应用
服务贸易结构优化路径研究
基于DSP的直线特征提取算法
基于MED和循环域解调的多故障特征提取