一. 前言
在前文講述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ì)稱的，等等本刽。這里不做深入探討鲸湃，畢竟不是數(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ì)稱軸的作用遏插；sigma控制著函數(shù)的胖瘦，也就是作用范圍纠修。下圖中胳嘲，距離對(duì)稱軸小于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ì)稱矩陣名船，所得的解向量彼此之間肯定是正交的绰上。
注意，這里的特征向量α只是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ù)鳍征。
