查看“︁核主成分分析”︁的源代码

{{NoteTA |G1=Math}}
'''核主成分分析'''（{{lang-en|kernel principal component analysis}}，简称{{lang|en|kernel PCA}}）是[[多变量统计]]领域中的一种分析方法，是使用[[核方法]]对[[主成分分析]]的非线性扩展，即将原数据通过核映射到{{le|再生核希尔伯特空间|Reproducing kernel Hilbert space}}后再使用原本线性的主成分分析。<ref>{{cite journal | doi = 10.1162/089976698300017467 | volume=10 | title=Nonlinear Component Analysis as a Kernel Eigenvalue Problem | year=1998 | journal=Neural Computation | pages=1299–1319 | last1 = Schölkopf | first1 = Bernhard}}</ref>

== 背景：线性主成分分析 ==
线性PCA对于中心化后的数据进行分析，即
:<math>\frac{1}{N}\sum_{i=1}^N \mathbf{x}_i = \mathbf{0}</math>,

其中<math>\mathbf{x}_i</math>是<math>N</math>个多变量样本之一。之后将[[协方差矩阵]]
:<math>C=\frac{1}{N}\sum_{i=1}^N \mathbf{x}_i\mathbf{x}_i^\top</math>

对角化。换言之，即是对协方差矩阵进行[[特征分解]]
:<math>\lambda \mathbf{v}=C\mathbf{v}</math>

或写作
:<math>\lambda \mathbf{x}_i^\top \mathbf{v}=\mathbf{x}_i^\top C\mathbf{v} \quad\forall i\in [1,N]</math>.<ref name=scholkopf>{{Cite web |url=http://www.face-rec.org/algorithms/Kernel/kernelPCA_scholkopf.pdf |title=Nonlinear Component Analysis as a Kernel Eigenvalue Problem (Technical Report) |access-date=2018-09-15 |archive-date=2020-09-19 |archive-url=https://web.archive.org/web/20200919182306/https://www.face-rec.org/algorithms/Kernel/kernelPCA_scholkopf.pdf |dead-url=no }}</ref>

== 引入核方法 ==
一般而言，''N''个数据点在<math>d < N</math>维空间中是线性不可分的，但它们在<math>d \geq N</math>维空间中则是[[几乎必然]]线性可分的。这也意味着，如果我们能将''N''个数据点<math>\mathbf{x}_i</math>映射到一个''N''维空间
:<math>\Phi(\mathbf{x}_i)</math> 其中 <math>\Phi : \mathbb{R}^d \to \mathbb{R}^N</math>
中，就能很容易地构建一个[[超平面]]将数据点作任意聚类。不过由于经<math>\Phi</math>映射后的向量是线性无关的，我们无法再像在线性PCA中那样显式地对协方差进行特征分解。

而在核PCA中，我们能够使用任意非平凡的函数<math>\Phi</math>，但无需显式地计算在高维空间中的值，使我们得以使用非常高维的<math>\Phi</math>。为了避免直接在<math>\Phi</math>-空间（即特征空间）中操作，我们可以定义一个<math>N\times N</math>的核
:<math>K = k(\mathbf{x},\mathbf{y}) = (\Phi(\mathbf{x}),\Phi(\mathbf{y})) = \Phi(\mathbf{x})^T\Phi(\mathbf{y})</math>

来代表特征空间的[[内积空间]]（见[[格拉姆矩阵]]）。这一对偶形式使我们能够进行主成分分析，同时又不用直接在<math>\Phi</math>-空间中解协方差矩阵的特征值与特征向量。''K''中每一列的''N''个元素代表了转换后的一个数据点与所有''N''个数据点的点积。

由于我们并不在特征空间中进行计算，核PCA方法不直接计算主成分，而是计算数据点在这些主成分上的投影。特征空间中的一点在第k个主成分<math>V^k</math>上的投影为
:<math>{\mathbf{V}^k}^T\Phi(\mathbf{x}) =\left(\sum_{i=1}^N \mathbf{a_i}^k\Phi(\mathbf{x_i})\right)^T\Phi(\mathbf{x}) </math>

其中<math>\Phi(\mathbf{x_i})^T\Phi(\mathbf{x})</math>代表点积，即核<math>K</math>中的元素。上式中剩下的部分<math>\mathbf{a_i}^k</math>可以通过解特征方程
:<math>N \lambda\mathbf{a}  =K\mathbf{a}</math>

得到，其中''N''为数据点的数量，<math>\lambda</math>与<math>\mathbf{a}</math>则分别为<math>K</math>的特征值与特征向量。为了归一化<math>\mathbf{a}^k</math>，我们要求
:<math>1 = (\mathbf{V}^k)^T \mathbf{V}^k</math>

值得注意的是，无论是否在原空间中对<math>x</math>中心化，我们无法保证数据在特征空间中是中心化的。由于PCA要求对数据中心化，我们可以对K“中心化”：
:<math>K' = K - \mathbf{1_N} K - K \mathbf{1_N} + \mathbf{1_N} K \mathbf{1_N}</math>

其中<math>\mathbf{1_N}</math>代表一个每个元素值皆为<math>1/N</math>的<math>N\times N</math>矩阵。于是我们可以使用<math>K'</math>进行前述的核PCA计算。<ref name=scholkopf />

在使用核PCA时，还有一点值得注意。在线性PCA中，我们可以通过特征值的大小对特征向量进行排序，以度量每个主成分所能够解释的数据方差。这对于数据降维十分有用，而这一技巧也可以用在核PCA中。不过，在实践中有时会发现得到所有方差皆相同，这通常是源于错误选择了核的尺度。

== 大数据集 ==
在实践中，大数据集会使K变得很大，从而导致存储问题。一种解决方式是先对数据集聚类，然后再对每一类的均值进行核PCA计算。有时即便使用此种方法仍会导致相对很大的K，此时我们可以只计算K中最大的P个特征值及相对应的特征向量。

== 示例 ==
[[Image:Kernel pca input.png|thumb|300px|应用核PCA前的数据点]]
[[Image:Kernel pca output.png|thumb|300px|使用核<math>k(\boldsymbol{x},\boldsymbol{y}) = (\boldsymbol{x}^\mathrm{T}\boldsymbol{y} + 1)^2</math>进行核PCA分析后的数据点]]
[[Image:Kernel pca output gaussian.png|thumb|300px|right|使用高斯核进行核PCA分析后的数据点]]

考虑图中所示的三组同心点云，我们试图使用核PCA识别这三组。图中各点的颜色并不是算法的一部分，仅用于展示各组数据点在变换前后的位置。

首先，我们使用核
: <math>k(\boldsymbol{x},\boldsymbol{y}) = (\boldsymbol{x}^\mathrm{T}\boldsymbol{y} + 1)^2</math>

进行核PCA处理，得到的结果如第二张图所示。

其次，我们再使用高斯核
: <math>k(\boldsymbol{x},\boldsymbol{y}) = e^\frac{-||\boldsymbol{x} - \boldsymbol{y}||^2}{2\sigma^2},</math>

该核是数据接近程度的一种度量，当数据点重合时为1，而当数据点相距无限远时则为0。结果为第三张图所示。

此时我们注意到，仅通过第一主成分就可以区别这三组数据点。而这对于线性PCA而言是不可实现的，因而线性PCA只能在给定维（此处为二维）空间中操作，而此时同心点云是线性不可分的。

== 应用 ==
核PCA方法还可用于新奇检测（novelty detection）<ref>{{cite journal | last1 =  | first1 =  | year = 2007 | title = Kernel PCA for Novelty Detection | url = http://www.heikohoffmann.de/kpca.html | journal = Pattern Recognition | volume = 40 | issue =  | pages = 863–874 | doi = 10.1016/j.patcog.2006.07.009 | access-date = 2018-09-15 | archive-date = 2020-02-06 | archive-url = https://web.archive.org/web/20200206080817/http://www.heikohoffmann.de/kpca.html | dead-url = no }}</ref>与数据降噪<ref>{{Cite web |url=http://citeseer.ist.psu.edu/old/mika99kernel.html |title=Kernel PCA and De-Noising in Feature Spaces. NIPS, 1999 |access-date=2018-09-15 |archive-date=2010-07-02 |archive-url=https://web.archive.org/web/20100702001240/http://citeseer.ist.psu.edu/old/mika99kernel.html |dead-url=no }}</ref>等。

== 参考文献 ==
{{reflist}}

[[Category:多变量统计]]
[[Category:信号处理]]
[[Category:機器學習演算法]]