一. 前言
在前文講述PCA降維算法時(shí)提到，PCA只能處理線性數(shù)據(jù)的降維，本質(zhì)上都是線性變換，并且它僅是篩選方差最大的特征，去除特征之間的線性相關(guān)性。對(duì)于線性不可分的數(shù)據(jù)常常效果很差。
二. KPCA算法
KPCA算法其實(shí)很簡(jiǎn)單，數(shù)據(jù)在低維度空間不是線性可分的，但是在高維度空間就可以變成線性可分的了。利用這個(gè)特點(diǎn)，KPCA只是將原始數(shù)據(jù)通過(guò)核函數(shù)（kernel）映射到高維度空間，再利用PCA算法進(jìn)行降維，所以叫做K PCA降維。因此KPCA算法的關(guān)鍵在于這個(gè)核函數(shù)。
假設(shè)現(xiàn)在有映射函數(shù)φ（不是核函數(shù)），它將數(shù)據(jù)從低維度映射到高維度。得到高維度數(shù)據(jù)后，我們還需要計(jì)算協(xié)方差矩陣，從前文可以看出，協(xié)方差矩陣每個(gè)元素都是向量的內(nèi)積。映射到高維度空間后，向量維度增加，計(jì)算量大幅度增大。即便計(jì)算量不是問(wèn)題，那么這個(gè)φ應(yīng)該把數(shù)據(jù)映射到多少維度呢？怎么求這個(gè)φ呢？這些都是很困難的。但是核函數(shù)剛好可以解決這個(gè)問(wèn)題，下面我們看一下什么是核函數(shù)。
三. 核函數(shù)
1. 核函數(shù)定義
核函數(shù)K（kernel function）可以直接得到低維數(shù)據(jù)映射到高維后的內(nèi)積，而忽略映射函數(shù)具體是什么，即
K(x, y) = <φ(x), φ(y)>，其中x和y是低維的輸入向量，φ是從低維到高維的映射，<x, y>是x和y的內(nèi)積。
核函數(shù)是一個(gè)非常有趣和強(qiáng)大的工具。 它是強(qiáng)大的，因?yàn)樗峁┝艘粋€(gè)從線性到非線性的連接以及任何可以只表示兩個(gè)向量之間的點(diǎn)積的算法。如果我們首先將我們的輸入數(shù)據(jù)映射到更高維的空間，那么我在這個(gè)高維的空間進(jìn)行操作出的效果，在原來(lái)那個(gè)空間就表現(xiàn)為非線性。
在KPCA中，剛好可以利用核函數(shù)的特點(diǎn)，反正我們的目的就是求數(shù)據(jù)在高維空間的內(nèi)積而已（協(xié)方差矩陣），又何必知道怎么映射的呢？
2. 常見(jiàn)核函數(shù)
核函數(shù)有很多限制要求，比如要求是連續(xù)的，對(duì)稱(chēng)的，等等。這里不做深入探討，畢竟不是數(shù)學(xué)系的，不用深入研究（恩，其實(shí)是看不懂）。下面列舉一些常用的核函數(shù)，至于怎么選擇，恩，目前是世界性難題。
-
線性核
函數(shù)簡(jiǎn)單，只是將2個(gè)向量求內(nèi)積加上個(gè)常數(shù)，只能解決線性可分問(wèn)題，如果我們將線性核函數(shù)應(yīng)用在KPCA中，我們會(huì)發(fā)現(xiàn)，推導(dǎo)之后和原始PCA算法一模一樣。
參數(shù)C可以調(diào)整。
-
多項(xiàng)式核
比線性核稍微復(fù)雜一點(diǎn)，由于多了指數(shù)d，所以可以處理非線性問(wèn)題。 這里要求a大于0，c大于等于0。多項(xiàng)式內(nèi)核非常適合于所有訓(xùn)練數(shù)據(jù)都?xì)w一化的問(wèn)題。這個(gè)核函數(shù)是比較好用的，就是參數(shù)比較多，但是還算穩(wěn)定。
參數(shù)a,c,d都可以調(diào)。
-
高斯核
高斯核是徑向基函數(shù)核（RBF）的一個(gè)典型代表。非常好用，用的也很多。
高斯核在計(jì)算中涉及到兩個(gè)向量的歐式距離（2范數(shù)）計(jì)算，可調(diào)參數(shù)只有一個(gè)sigma，它控制著函數(shù)的作用范圍。
以二維向量為例，如果y固定，那么y就充當(dāng)著對(duì)稱(chēng)軸的作用；sigma控制著函數(shù)的胖瘦，也就是作用范圍。下圖中，距離對(duì)稱(chēng)軸小于sigma的范圍內(nèi)，圖像是有高度的，sigma之外的范圍，函數(shù)基本沒(méi)有高度（沒(méi)起作用）。
-
指數(shù)核
也是RBF代表，和高斯核很像，只是將L2范數(shù)變成L1。
-
拉普拉斯核
拉普拉斯核完全等價(jià)于指數(shù)核，唯一的區(qū)別在于前者對(duì)參數(shù)的敏感性降低，也是一種RBF。
四. KPCA的簡(jiǎn)單推導(dǎo)
為了進(jìn)一步理解KPCA，我們這里做一個(gè)簡(jiǎn)單的推導(dǎo)，看看KPCA究竟是什么鬼東西！
假設(shè)原始數(shù)據(jù)是如下矩陣X：（數(shù)據(jù)每一列為一個(gè)樣本，每個(gè)樣本有m個(gè)屬性，一共有n個(gè)樣本）
將每個(gè)樣本通過(guò)函數(shù)φ映射到高維空間，得到高維空間的數(shù)據(jù)矩陣φ（X）。
用同樣的方法計(jì)算高維空間中數(shù)據(jù)的協(xié)方差矩陣，進(jìn)一步計(jì)算特征值與特征向量。
定理：空間中的任一向量（哪怕是基向量），都可以由該空間中的所有樣本線性表示，這點(diǎn)對(duì)KPCA很重要。
所以根據(jù)這個(gè)定理，我們就可以用所有樣本來(lái)表示特征向量：
將這個(gè)線性組合帶回到特征向量公式，替換特征向量，得到：
進(jìn)一步，等式兩邊同時(shí)左乘一個(gè) φ（X）的轉(zhuǎn)置：（目的是構(gòu)造2個(gè)φ（X）的轉(zhuǎn)置 乘 φ（X））
等式兩邊同時(shí)除以K，得到：
得到了與PCA相似度極高的求解公式。
下面來(lái)看一下這個(gè)K，到底怎么求呢？我們的核函數(shù)閃亮登場(chǎng)了！
注意，協(xié)方差矩陣是X乘X的轉(zhuǎn)置，落實(shí)到計(jì)算是任意2個(gè)特征（行）的點(diǎn)積；而此處的核矩陣K是反過(guò)來(lái)的，X的轉(zhuǎn)置乘X，它落實(shí)到計(jì)算是任意2個(gè)樣本（列）的點(diǎn)積。這個(gè)核矩陣是n維的，維度和樣本數(shù)相同，而不是特征數(shù)。
根據(jù)核函數(shù)的性質(zhì)，上面這個(gè)核矩陣K可以直接在低維空間計(jì)算得到：
接下來(lái)，和PCA相同，求K最大的幾個(gè)特征值所對(duì)應(yīng)的特征向量，由于K為對(duì)稱(chēng)矩陣，所得的解向量彼此之間肯定是正交的。
注意，這里的特征向量α只是K的特征向量，不是高維空間中的特征向量?？粗澳莻€(gè)定理，高維空間的特征向量 W 與映射函數(shù)有關(guān)是 φ（X）α。既然α不是高維空間的坐標(biāo)軸，那它是什么呢？它其實(shí)是全部樣本在這個(gè)軸上的投影了，也即是我們所需的進(jìn)行降維后的數(shù)據(jù)了。
由于K是n（樣本數(shù)）維方陣，所以最多有n個(gè)特征值，所以理論上講KPCA的降維結(jié)果最高可以達(dá)到n維，會(huì)比降維之前的特征多。但是核心信息都在前幾個(gè)軸上面，至于取幾個(gè)軸，就看經(jīng)驗(yàn)啦。
五. 總結(jié)一下KPCA算法的計(jì)算過(guò)程
- 去除平均值，進(jìn)行中心化。
- 利用核函數(shù)計(jì)算核矩陣K。
- 計(jì)算核矩陣的特征值和特征向量。
- 將特征相量按對(duì)應(yīng)特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P。
- P即為降維后的數(shù)據(jù)。
