机器学习：降维算法核主成分分析KPCA算法原理推导

我的小程序&＃xff1a;

说真的&＃xff0c;刚开始接触机器学习&＃xff0c;一看到带“核”字的算法就头疼&＃xff08;-…-&＃xff09;&＃xff0c;没高人指引&＃xff0c;总觉得理解起来费劲&＃xff0c;也不确定理解的对不对。可能是因为这个“核”有点抽象&＃xff0c;没有具体形式&＃xff08;形式不确定&＃xff09;&＃xff0c;操作很风骚。当然到现在也不敢说自己有多理解&＃xff0c;只能扯扯目前所理解到的核主成分分析KPCA。

PCA是简单的线性降维的方法&＃xff0c;KPCA则是其非线性的扩展&＃xff0c;可以挖掘到数据集中的非线性信息。

KPCA的主要过程是&＃xff1a;

1. 首先将原始数据非线性映射到高维空间&＃xff1b;
2. 再把第1步中的数据从高维空间投影降维到需要的维数d&＃39;

可以看出&＃xff0c;KPCA只是比PCA多了一步映射到高维空间的操作&＃xff0c;降维的操作是一样的。所以&＃xff0c;KPCA最终投影到的超平面也应满足PCA中的最近重构性或最大可分性。于是KPCA最终的投影向量也应满足PCA中的等式&＃xff08;参见&＃xff1a;机器学习&＃xff1a;降维算法-主成分分析PCA算法两种角度的推导&＃xff09;&＃xff1a;

.

即&＃xff1a;

.

其中是样本点映射到的高维空间中的像。进一步得&＃xff1a;

.

其中是的第j个分量。

假设是由原始空间的样本通过映射产生&＃xff0c;即.若映射已知&＃xff0c;那么容易求到和投影向量&＃xff0c;问题就解决了。但通常情况下&＃xff0c;是不知道的具体形式的&＃xff08;后面会发现&＃xff0c;我们不用知道的具体形式一样能求解&＃xff01;&＃xff09;。不管怎样&＃xff0c;先表达出这种映射关系&＃xff1a;

将写成&＃xff1a;

................................................................(1)

将写成&＃xff1a;

..................................................................................(2)

将(2)式代入(1)式得&＃xff1a;

................................(3)

记&＃xff1a;

,

.

将和代入(3)式得&＃xff1a;

................................................................................(4)

关键的地方到了&＃xff0c;接下来引入核函数&＃xff1a;

.

核函数本质上也就是个函数&＃xff0c;跟y&＃61;kx没啥区别&＃xff0c;特殊之处在于&＃xff0c;它的计算结果表达了变量在高维空间的内积值。就是说&＃xff0c;本来是在高维空间&＃xff08;甚至无限维空间&＃xff09;计算的内积&＃xff0c;可以在原始较低维的空间通过核函数计算得到。

有常见的几种核函数&＃xff0c;到底选用哪种核函数&＃xff0c;可能需要去尝试&＃xff0c;看哪种核函数产生的效果好&＃xff08;比如在KPCA中&＃xff0c;就是看哪种核函数带来的降维效果更好&＃xff09;。

之所以引入核函数&＃xff0c;可以认为有两方面原因&＃xff1a;

1. 映射关系未知&＃xff1b;
2. 映射到的高维空间维数可能非常高&＃xff08;甚至无限维&＃xff09;&＃xff0c;在高维空间计算开销太大&＃xff0c;十分困难。

核函数对应的核矩阵为&＃xff1a;

.

(4)式两边左乘得&＃xff1a;

&＃xff0c;

把核矩阵K代入上式&＃xff0c;可得&＃xff1a;

&＃xff1a;

两边去掉K&＃xff0c;得&＃xff1a;

.

&＃xff08;这里还是没搞清楚&＃xff0c;为什么能直接去掉K&＃xff0c;理论上K是可逆矩阵时才能直接消去。但核函数确定的核矩阵只要求是半正定的&＃xff0c;半正定矩阵又不一定是可逆的。这里去掉K的依据是什么&＃xff1f;望博友指点。&＃xff09;

可以看到&＃xff0c;通过核函数的这一波操作&＃xff0c;原始空间到高维空间的映射变得无形了&＃xff0c;最终得到的式子并没有看到映射的影子&＃xff0c;这就是“核”操作的风骚之处。我们不知道映射的具体形式&＃xff0c;我们也不用知道它的形式。

显然&＃xff0c;上式是特征分解问题&＃xff0c;取K的最大的d&＃39;个特征值对应的特征向量即可。

对于新样本x&＃xff0c;其投影后第维坐标为&＃xff1a;

.

可以看到&＃xff0c;KPCA需要对所有样本求和&＃xff0c;计算开销还是挺大的。

参考资料&＃xff1a;周志华《机器学习》

参考博文&＃xff1a;

核主成分分析(Kernel Principal Component Analysis, KPCA)的公式推导过程 

机器学习&＃xff1a;核函数和核矩阵简介

相关博文&＃xff1a;机器学习&＃xff1a;降维算法-主成分分析PCA算法两种角度的推导