(十一)KPCA非线性降维与核函数

一. 前言

在前文讲述PCA降维算法时提到，PCA只能处理线性数据的降维，本质上都是线性变换，并且它仅是筛选方差最大的特征，去除特征之间的线性相关性。对于线性不可分的数据常常效果很差。

二. KPCA算法

KPCA算法其实很简单，数据在低维度空间不是线性可分的，但是在高维度空间就可以变成线性可分的了。利用这个特点，KPCA只是将原始数据通过核函数（kernel）映射到高维度空间，再利用PCA算法进行降维，所以叫做K PCA降维。因此KPCA算法的关键在于这个核函数。

假设现在有映射函数φ（不是核函数），它将数据从低维度映射到高维度。得到高维度数据后，我们还需要计算协方差矩阵，从前文可以看出，协方差矩阵每个元素都是向量的内积。映射到高维度空间后，向量维度增加，计算量大幅度增大。即便计算量不是问题，那么这个φ应该把数据映射到多少维度呢？怎么求这个φ呢？这些都是很困难的。但是核函数刚好可以解决这个问题，下面我们看一下什么是核函数。

三. 核函数

1. 核函数定义

核函数K（kernel function）可以直接得到低维数据映射到高维后的内积，而忽略映射函数具体是什么，即
K(x, y) = <φ(x), φ(y)>，其中x和y是低维的输入向量，φ是从低维到高维的映射，<x, y>是x和y的内积。

核函数是一个非常有趣和强大的工具。 它是强大的，因为它提供了一个从线性到非线性的连接以及任何可以只表示两个向量之间的点积的算法。如果我们首先将我们的输入数据映射到更高维的空间，那么我在这个高维的空间进行操作出的效果，在原来那个空间就表现为非线性。

在KPCA中，刚好可以利用核函数的特点，反正我们的目的就是求数据在高维空间的内积而已（协方差矩阵），又何必知道怎么映射的呢？

2. 常见核函数

核函数有很多限制要求，比如要求是连续的，对称的，等等。这里不做深入探讨，毕竟不是数学系的，不用深入研究（恩，其实是看不懂）。下面列举一些常用的核函数，至于怎么选择，恩，目前是世界性难题。

• 线性核
  函数简单，只是将2个向量求内积加上个常数，只能解决线性可分问题，如果我们将线性核函数应用在KPCA中，我们会发现，推导之后和原始PCA算法一模一样。

  
  
  

  参数C可以调整。

• 多项式核
  比线性核稍微复杂一点，由于多了指数d，所以可以处理非线性问题。 这里要求a大于0，c大于等于0。多项式内核非常适合于所有训练数据都归一化的问题。这个核函数是比较好用的，就是参数比较多，但是还算稳定。

  
  
  

  参数a,c,d都可以调。

• 高斯核
  高斯核是径向基函数核（RBF）的一个典型代表。非常好用，用的也很多。
  高斯核在计算中涉及到两个向量的欧式距离（2范数）计算，可调参数只有一个sigma，它控制着函数的作用范围。

  
  

以二维向量为例，如果y固定，那么y就充当着对称轴的作用；sigma控制着函数的胖瘦，也就是作用范围。下图中，距离对称轴小于sigma的范围内，图像是有高度的，sigma之外的范围，函数基本没有高度（没起作用）。

sigma=1 sigma=5

• 指数核
  也是RBF代表，和高斯核很像，只是将L2范数变成L1。

  
  

• 拉普拉斯核
  拉普拉斯核完全等价于指数核，唯一的区别在于前者对参数的敏感性降低，也是一种RBF。

  
  

四. KPCA的简单推导

为了进一步理解KPCA，我们这里做一个简单的推导，看看KPCA究竟是什么鬼东西！

假设原始数据是如下矩阵X：（数据每一列为一个样本，每个样本有m个属性，一共有n个样本）

将每个样本通过函数φ映射到高维空间，得到高维空间的数据矩阵φ（X）。

用同样的方法计算高维空间中数据的协方差矩阵，进一步计算特征值与特征向量。

定理：空间中的任一向量（哪怕是基向量），都可以由该空间中的所有样本线性表示，这点对KPCA很重要。
所以根据这个定理，我们就可以用所有样本来表示特征向量：
将这个线性组合带回到特征向量公式，替换特征向量，得到：

进一步，等式两边同时左乘一个 φ（X）的转置：（目的是构造2个φ（X）的转置 乘 φ（X））


等式两边同时除以K，得到：

得到了与PCA相似度极高的求解公式。
下面来看一下这个K，到底怎么求呢？我们的核函数闪亮登场了！

注意，协方差矩阵是X乘X的转置，落实到计算是任意2个特征（行）的点积；而此处的核矩阵K是反过来的，X的转置乘X，它落实到计算是任意2个样本（列）的点积。这个核矩阵是n维的，维度和样本数相同，而不是特征数。

根据核函数的性质，上面这个核矩阵K可以直接在低维空间计算得到：

接下来，和PCA相同，求K最大的几个特征值所对应的特征向量，由于K为对称矩阵，所得的解向量彼此之间肯定是正交的。
注意，这里的特征向量α只是K的特征向量，不是高维空间中的特征向量。看之前那个定理，高维空间的特征向量 W 与映射函数有关是 φ（X）α。既然α不是高维空间的坐标轴，那它是什么呢？它其实是全部样本在这个轴上的投影了，也即是我们所需的进行降维后的数据了。
由于K是n（样本数）维方阵，所以最多有n个特征值，所以理论上讲KPCA的降维结果最高可以达到n维，会比降维之前的特征多。但是核心信息都在前几个轴上面，至于取几个轴，就看经验啦。

五. 总结一下KPCA算法的计算过程

1. 去除平均值，进行中心化。
2. 利用核函数计算核矩阵K。
3. 计算核矩阵的特征值和特征向量。
4. 将特征相量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵P。
5. P即为降维后的数据。