核主成分分析

核主成分分析（英語：kernel principal component analysis，簡稱kernel PCA）是多變量統計領域中的一種分析方法，是使用核方法對主成分分析的非線性擴展，即將原數據通過核映射到再生核希爾伯特空間（英語：Reproducing kernel Hilbert space）後再使用原本線性的主成分分析。^[1]

背景：線性主成分分析

線性PCA對於中心化後的數據進行分析，即

${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}\mathbf {x} _{i}=\mathbf {0} }$,

其中${\displaystyle \mathbf {x} _{i}}$是${\displaystyle N}$個多變量樣本之一。之後將協方差矩陣

${\displaystyle C={\frac {1}{N}}\sum _{i=1}^{N}\mathbf {x} _{i}\mathbf {x} _{i}^{\top }}$

對角化。換言之，即是對協方差矩陣進行特徵分解

${\displaystyle \lambda \mathbf {v} =C\mathbf {v} }$

或寫作

${\displaystyle \lambda \mathbf {x} _{i}^{\top }\mathbf {v} =\mathbf {x} _{i}^{\top }C\mathbf {v} \quad \forall i\in [1,N]}$.^[2]

引入核方法

一般而言，N個數據點在${\displaystyle d<N}$維空間中是線性不可分的，但它們在${\displaystyle d\geq N}$維空間中則是幾乎必然線性可分的。這也意味着，如果我們能將N個數據點${\displaystyle \mathbf {x} _{i}}$映射到一個N維空間

${\displaystyle \Phi (\mathbf {x} _{i})}$ 其中 ${\displaystyle \Phi :\mathbb {R} ^{d}\to \mathbb {R} ^{N}}$

中，就能很容易地構建一個超平面將數據點作任意聚類。不過由於經${\displaystyle \Phi }$映射後的向量是線性無關的，我們無法再像在線性PCA中那樣顯式地對協方差進行特徵分解。

而在核PCA中，我們能夠使用任意非平凡的函數${\displaystyle \Phi }$，但無需顯式地計算在高維空間中的值，使我們得以使用非常高維的${\displaystyle \Phi }$。為了避免直接在${\displaystyle \Phi }$-空間（即特徵空間）中操作，我們可以定義一個${\displaystyle N\times N}$的核

${\displaystyle K=k(\mathbf {x} ,\mathbf {y} )=(\Phi (\mathbf {x} ),\Phi (\mathbf {y} ))=\Phi (\mathbf {x} )^{T}\Phi (\mathbf {y} )}$

來代表特徵空間的內積空間（見格拉姆矩陣）。這一對偶形式使我們能夠進行主成分分析，同時又不用直接在${\displaystyle \Phi }$-空間中解協方差矩陣的特徵值與特徵向量。K中每一列的N個元素代表了轉換後的一個數據點與所有N個數據點的點積。

由於我們並不在特徵空間中進行計算，核PCA方法不直接計算主成分，而是計算數據點在這些主成分上的投影。特徵空間中的一點在第k個主成分${\displaystyle V^{k}}$上的投影為

${\displaystyle {\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} )}$

其中${\displaystyle \Phi (\mathbf {x_{i}} )^{T}\Phi (\mathbf {x} )}$代表點積，即核${\displaystyle K}$中的元素。上式中剩下的部分${\displaystyle \mathbf {a_{i}} ^{k}}$可以通過解特徵方程

${\displaystyle N\lambda \mathbf {a} =K\mathbf {a} }$

得到，其中N為數據點的數量，${\displaystyle \lambda }$與${\displaystyle \mathbf {a} }$則分別為${\displaystyle K}$的特徵值與特徵向量。為了歸一化${\displaystyle \mathbf {a} ^{k}}$，我們要求

${\displaystyle 1=(\mathbf {V} ^{k})^{T}\mathbf {V} ^{k}}$

值得注意的是，無論是否在原空間中對${\displaystyle x}$中心化，我們無法保證數據在特徵空間中是中心化的。由於PCA要求對數據中心化，我們可以對K「中心化」：

${\displaystyle K'=K-\mathbf {1_{N}} K-K\mathbf {1_{N}} +\mathbf {1_{N}} K\mathbf {1_{N}} }$

其中${\displaystyle \mathbf {1_{N}} }$代表一個每個元素值皆為${\displaystyle 1/N}$的${\displaystyle N\times N}$矩陣。於是我們可以使用${\displaystyle K'}$進行前述的核PCA計算。^[2]

在使用核PCA時，還有一點值得注意。在線性PCA中，我們可以通過特徵值的大小對特徵向量進行排序，以度量每個主成分所能夠解釋的數據方差。這對於數據降維十分有用，而這一技巧也可以用在核PCA中。不過，在實踐中有時會發現得到所有方差皆相同，這通常是源於錯誤選擇了核的尺度。

大數據集

在實踐中，大數據集會使K變得很大，從而導致存儲問題。一種解決方式是先對數據集聚類，然後再對每一類的均值進行核PCA計算。有時即便使用此種方法仍會導致相對很大的K，此時我們可以只計算K中最大的P個特徵值及相對應的特徵向量。

示例

應用核PCA前的數據點

使用核${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=({\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {y}}+1)^{2}}$進行核PCA分析後的數據點

使用高斯核進行核PCA分析後的數據點

考慮圖中所示的三組同心點雲，我們試圖使用核PCA識別這三組。圖中各點的顏色並不是算法的一部分，僅用於展示各組數據點在變換前後的位置。

首先，我們使用核

${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=({\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {y}}+1)^{2}}$

進行核PCA處理，得到的結果如第二張圖所示。

其次，我們再使用高斯核

${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=e^{\frac {-||{\boldsymbol {x}}-{\boldsymbol {y}}||^{2}}{2\sigma ^{2}}},}$

該核是數據接近程度的一種度量，當數據點重合時為1，而當數據點相距無限遠時則為0。結果為第三張圖所示。

此時我們注意到，僅通過第一主成分就可以區別這三組數據點。而這對於線性PCA而言是不可實現的，因而線性PCA只能在給定維（此處為二維）空間中操作，而此時同心點雲是線性不可分的。

應用

核PCA方法還可用於新奇檢測（novelty detection）^[3]與數據降噪^[4]等。

參考文獻

1. Schölkopf, Bernhard. Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation. 1998, 10: 1299–1319. doi:10.1162/089976698300017467.
2. Nonlinear Component Analysis as a Kernel Eigenvalue Problem (Technical Report) (PDF). [2018-09-15]. （原始內容存檔 (PDF)於2020-09-19）.
3. Kernel PCA for Novelty Detection. Pattern Recognition. 2007, 40: 863–874 [2018-09-15]. doi:10.1016/j.patcog.2006.07.009. （原始內容存檔於2020-02-06）.
4. Kernel PCA and De-Noising in Feature Spaces. NIPS, 1999. [2018-09-15]. （原始內容存檔於2010-07-02）.