第五种方法：核主成分分析（KPCA）
姓名：何源 学号：21011210073 学院：通信工程学院
转载：KPCA实现
【嵌牛导读】核主成分分析算法介绍（KPCA）
【嵌牛鼻子】KPCA
【嵌牛提问】核算法是什么？KPCA算法的步骤是什么？
【嵌牛正文】
KPCA算法介绍
KPCA算法实际上就是加核的PCA算法，它主要针对于非线性可分问题，给出了一种对该类问题进行特征提取的有效方式。与PCA特征提取算法类似，KPCA算法只是先将原始非线性可分数据通过某种变换映射到线性可分的高维空间，然后将该高维空间看成是新的原始空间，再对此空间内的数据通过PCA算法来提取特征，得到特征提取结果。
核方法
核方法背景
布尔异或函数（不能用线性鉴别函数进行分类）：
或者
显而易见,我们找不到任何一条直线能够将两个正例(“+”）和负例(“-”)分开。然而我们可以对初始的模式向量进行扩展,使之包括新的特征,这些新的特征是原始输入特征的二阶组合。即将 %5ET)
映射为)
,则4个训练样本能够被正确地分类。几何上,我们看到点(1,1)在第3维上升高了,则最终的分布可以很容易地通过一个平面将这两类样本正确地分开,如图1所示。如果一个分类问题在其定义的空间中非线性可分的,可以通过某种映射（变换） 把数据从原始空间映射到一个高维空间,使数据在高维空间中线性可分,从而可以用简单的线性判决函数来解决十分复杂的问题。把这种变换空间中的线性判决函数称为原问题的广义线性判决函数。然而,这种高维空间的维数往往很高,极易陷入所谓的“维数灾难”,使得这种变换思想在实际中很难实现。核方法则借助基于核函数的非线性映射方法,巧妙地克服了这一问题。
核方法思想
首先设法通过非线性变换
将
映射到另一高维特征空间
中,如图2所示。原问题转化为高维特征空间F中的线性问题。为了避免直接计算 ，定义了核函数
核函数
设
维的随机矢量是一个非空集合, 为一个内积空间, 为到的非线性映射函数,如果函数 满足：对任意
，有%3D%5Cphi%20(x_i).%5Cphi(x_j))
，则称为核函数。
核函数必须满足 Mercer 条件：对于任意给定的对称函数 
它是某个特征空间中内积运算的充分必要条件是对于任意的不恒为
的函数 )
，且%5E2%20dx%3C%5Cpropto%20)
，有g(x)g(y)dxdy%5Cgeq%200)
。考虑到核方法的基础是实现一种由输入空间到特征空间的非线性映射，假设输入空间数据 )
,对任意对称、连续且满足Mercer条件的函数，存在一个Hilbert空间
,对映射:
,有%3D%5Csum_%7Bn%3D1%7D%5E%7Bd_F%7D%20%5Cphi%20(x_i)%5ET%5Cphi(x_j))
,其中，
为的维数空间。上式进一步说明，输入空间的核函数实际上与特征空间的内积相等价。由于在核方法的各种实际应用中，只需要应用特征空间的内积，而不需要了解映射 的具体形式。换句话说，在使用核方法时只需要考虑如何选定一个适当的核函数，而无需关心与之对应的映射 可能具有复杂的表达式和很高的维数。
常用的核函数：
（1）多项式核函数：![k(x,y)=[(x.y)+b]^d](https://math.jianshu.com/math?formula=k(x%2Cy)%3D%5B(x.y)%2Bb%5D%5Ed)
（2）高斯核函数：%3Dexp(-%5Cfrac%7B%7C%7Cx-y%7C%7C%5E2%7D%7Bc%7D)%20)
（3）Sigmoid核函数:![k(x,y)=tanh[v(x,y)+c]](https://math.jianshu.com/math?formula=k(x%2Cy)%3Dtanh%5Bv(x%2Cy)%2Bc%5D)
KPCA实现步骤
假设](https://math.jianshu.com/math?formula=X%3D%5Bx_1%2Cx_2%2C...%2Cx_m%5D(x_1%2Cx_2%2C...%2Cx_m%5Cin%20R%5Ed))
表示
个原始特征组成的原始样本集，](https://math.jianshu.com/math?formula=Y%3D%5By_1%2Cy_2%2C...%2Cy_m%5D(y_1%2Cy_2%2C...%2Cy_m%5Cin%20R%5Ep))
表示输出特征集，且
，核函数为，正定核为
，则：
（1）根据给定的核函数，求得正定核,%3D%5Cphi%20(x_i).%5Cphi(x_j)%3D%5Cphi(x_i)%5ET%5Cphi(x_j))
,根据
求出
，其中矩阵
表示每一个元素值都为
的方阵。
（2）计算矩阵的所有特征值，对这些特征值进行排序，选择前
个特征值
，然后计算他们对应的特征向量
（3）根据公式
，其中![Q=[\phi (x_1),\phi (x_2),...,\phi (x_m)]](https://math.jianshu.com/math?formula=Q%3D%5B%5Cphi%20(x_1)%2C%5Cphi%20(x_2)%2C...%2C%5Cphi%20(x_m)%5D)
,得到![W=[w_1,w_2,...,w_p]](https://math.jianshu.com/math?formula=W%3D%5Bw_1%2Cw_2%2C...%2Cw_p%5D)
，即特征提取算法中所用到的特征提取矩阵。
（4）根据![y_i=W^T\phi(x)=\frac{1}{\sqrt{\lambda _i} }Q^Tv_i^{T}\phi(x)=\frac{1}{\sqrt{\lambda _i} }v_i^T[k(x_1,x),k(x_2,x),...,k(x_m,x)]，i=1,2,...,p](https://math.jianshu.com/math?formula=y_i%3DW%5ET%5Cphi(x)%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B%5Clambda%20_i%7D%20%7DQ%5ETv_i%5E%7BT%7D%5Cphi(x)%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B%5Clambda%20_i%7D%20%7Dv_i%5ET%5Bk(x_1%2Cx)%2Ck(x_2%2Cx)%2C...%2Ck(x_m%2Cx)%5D%EF%BC%8Ci%3D1%2C2%2C...%2Cp)
计算得到
，由![Y=[y_1,y_2,...,y_p]](https://math.jianshu.com/math?formula=Y%3D%5By_1%2Cy_2%2C...%2Cy_p%5D)
组成的特征集就是输出特征集。
