1. 維數(shù)災(zāi)難

樣本的特征數(shù)稱為維數(shù)（dimensionality），當(dāng)維數(shù)非常大時(shí)，也就是現(xiàn)在所說的維數(shù)災(zāi)難。
維數(shù)災(zāi)難具體表現(xiàn)在：在高維情形下，數(shù)據(jù)樣本將變得十分稀疏，因?yàn)榇藭r(shí)要滿足訓(xùn)練樣本為“密采樣”的總體樣本數(shù)目是一個(gè)觸不可及的天文數(shù)字，訓(xùn)練樣本的稀疏使得其代表總體分布的能力大大減弱，從而消減了學(xué)習(xí)器的泛化能力；同時(shí)當(dāng)維數(shù)很高時(shí)，計(jì)算距離也變得十分復(fù)雜，甚至連計(jì)算內(nèi)積都不再容易，這也是為什么支持向量機(jī)（SVM）使用核函數(shù)低維計(jì)算，高維表現(xiàn)的原因。

緩解維數(shù)災(zāi)難的一個(gè)重要途徑就是降維，即通過某種數(shù)學(xué)變換將原始高維空間轉(zhuǎn)變到一個(gè)低維的子空間。
在這個(gè)子空間中，樣本的密度將大幅提高，同時(shí)距離計(jì)算也變得容易。這時(shí)也許會(huì)有疑問，這樣降維之后不是會(huì)丟失原始數(shù)據(jù)的一部分信息嗎？這是因?yàn)樵诤芏鄬?shí)際的問題中，雖然訓(xùn)練數(shù)據(jù)是高維的，但是與學(xué)習(xí)任務(wù)相關(guān)也許僅僅是其中的一個(gè)低維子空間，也稱為一個(gè)低維嵌入，例如：數(shù)據(jù)屬性中存在噪聲屬性、相似屬性或冗余屬性等，對(duì)高維數(shù)據(jù)進(jìn)行降維能在一定程度上達(dá)到提煉低維優(yōu)質(zhì)屬性或降噪的效果。

2. K近鄰學(xué)習(xí)（kNN）

k近鄰算法簡(jiǎn)稱kNN（k-Nearest Neighbor），是一種經(jīng)典的監(jiān)督學(xué)習(xí)方法，數(shù)據(jù)挖掘十大算法之一。

工作機(jī)制非常簡(jiǎn)單:給定測(cè)試樣本,基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本,然后基于這k個(gè)“鄰居”的信息來進(jìn)行預(yù)測(cè)。

通常,在分類任務(wù)中可使用“投票法”,即選擇這k個(gè)樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測(cè)結(jié)果;

在回歸任務(wù)中可使用“平均法”,即將這k個(gè)樣本的實(shí)值輸出標(biāo)記的平均值作為預(yù)測(cè)結(jié)果;還可基于距離遠(yuǎn)近進(jìn)行加權(quán)平均或加權(quán)投票,距離越近的樣本權(quán)重越大.

2.1 分析

從上圖中我們可以看到，圖中有兩種類型的樣本，一類是藍(lán)色正方形，另一類是紅色三角形。而那個(gè)綠色圓形是我們待分類的樣本?；趉NN算法的思路，我們很容易得到以下結(jié)論：

如果K=3，那么離綠色點(diǎn)最近的有2個(gè)紅色三角形和1個(gè)藍(lán)色的正方形，這3個(gè)點(diǎn)投票，于是綠色的這個(gè)待分類點(diǎn)屬于紅色的三角形。
如果K=5，那么離綠色點(diǎn)最近的有2個(gè)紅色三角形和3個(gè)藍(lán)色的正方形，這5個(gè)點(diǎn)投票，于是綠色的這個(gè)待分類點(diǎn)屬于藍(lán)色的正方形。

與前面介紹的學(xué)習(xí)方法相比, k近鄰學(xué)習(xí)有一個(gè)明顯的不同之處: 它似乎沒有顯式的訓(xùn)練過程! 事實(shí)上,它是“懶情學(xué)習(xí)” (lazy learning)的著名代表, 此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來,訓(xùn)練時(shí)間開銷為零, 待收到測(cè)試樣本后再進(jìn)行處理（因此樸素貝葉斯也可以懶惰式學(xué)習(xí)，此類技術(shù)在訓(xùn)練階段開銷為零，待收到測(cè)試樣本后再進(jìn)行計(jì)算。）; 相應(yīng)的,那些在訓(xùn)練階段就對(duì)樣本進(jìn)行學(xué)習(xí)處理的方法, 稱為“急切學(xué)習(xí)” (eager learning).

很容易看出：kNN算法的核心在于k值的選取以及距離的度量。k值選取太小，模型很容易受到噪聲數(shù)據(jù)的干擾，例如：極端地取k=1，若待分類樣本正好與一個(gè)噪聲數(shù)據(jù)距離最近，就導(dǎo)致了分類錯(cuò)誤；若k值太大， 則在更大的鄰域內(nèi)進(jìn)行投票，此時(shí)模型的預(yù)測(cè)能力大大減弱，例如：極端取k=訓(xùn)練樣本數(shù)，就相當(dāng)于模型根本沒有學(xué)習(xí)，所有測(cè)試樣本的預(yù)測(cè)結(jié)果都是一樣的。一般地我們都通過交叉驗(yàn)證法（簡(jiǎn)單來說，就是一部分樣本做訓(xùn)練集，一部分做測(cè)試集）來選取一個(gè)適當(dāng)?shù)膋值。

對(duì)于距離度量，不同的度量方法得到的k個(gè)近鄰不盡相同，從而對(duì)最終的投票結(jié)果產(chǎn)生了影響，因此選擇一個(gè)合適的距離度量方法也十分重要。在上一篇聚類算法中，在度量樣本相似性時(shí)介紹了常用的幾種距離計(jì)算方法，包括閔可夫斯基距離，曼哈頓距離，VDM等（距離度量方法總結(jié)可參考博客）。在實(shí)際應(yīng)用中，kNN的距離度量函數(shù)一般根據(jù)樣本的特性來選擇合適的距離度量，同時(shí)應(yīng)對(duì)數(shù)據(jù)進(jìn)行去量綱/歸一化處理來消除大量綱屬性的強(qiáng)權(quán)政治影響。

2.2 KNN最近鄰分類算法的過程

1. 計(jì)算測(cè)試樣本和訓(xùn)練樣本中每個(gè)樣本點(diǎn)的距離（常見的距離度量有歐式距離，馬氏距離等）；
2. 對(duì)上面所有的距離值進(jìn)行排序；
3. 選前 k 個(gè)最小距離的樣本；
4. 根據(jù)這 k 個(gè)樣本的標(biāo)簽進(jìn)行投票，得到最后的分類類別；

3. MDS算法

不管是使用核函數(shù)升維還是對(duì)數(shù)據(jù)降維，我們都希望原始空間樣本點(diǎn)之間的距離在新空間中基本保持不變，這樣才不會(huì)使得原始空間樣本之間的關(guān)系及總體分布發(fā)生較大的改變。**“多維縮放”（Multiple Dimensional Scaling，MDS）**正是基于這樣的思想，MDS要求原始空間樣本之間的距離在降維后的低維空間中得以保持。

令降維后的樣本坐標(biāo)矩陣Z被中心化，中心化是指將每個(gè)樣本向量減去整個(gè)樣本集的均值向量，故所有樣本向量求和得到一個(gè)零向量，即

這樣易知：矩陣B的每一列以及每一列求和均為0，因?yàn)樘崛」蜃雍蠖加幸豁?xiàng)為所有樣本向量的和向量。

根據(jù)上面矩陣B的特征，我們很容易得到以下等式：

MDS的算法流程如下圖所示：

4. 主成分分析（PCA）

該部分可參考博客。

主成分分析(Principal Component Analysis,簡(jiǎn)稱 PCA)是最常用的一種降維方法。不同于MDS采用距離保持的方法，主成分分析（PCA）直接通過一個(gè)線性變換，將原始空間中的樣本投影到新的低維空間中。簡(jiǎn)單來理解這一過程便是：PCA采用一組新的基來表示樣本點(diǎn)，其中每一個(gè)基向量都是原來基向量的線性組合，通過使用盡可能少的新基向量來表出樣本，從而達(dá)到降維的目的。

在介紹PCA之前,不妨先考慮這樣一個(gè)問題:對(duì)于正交屬性空間中的樣本點(diǎn),如何用一個(gè)超平面(直線的高維推廣)對(duì)所有樣本進(jìn)行恰當(dāng)?shù)谋磉_(dá)?
容易想到,若存在這樣的超平面,那么它大概應(yīng)具有這樣的性質(zhì):

• 最近重構(gòu)性:樣本點(diǎn)到這個(gè)超平面的距離都足夠近;

• 最大可分性:樣本點(diǎn)在這個(gè)超平面上的投影能盡可能分開.

這里十分神奇的是：最近重構(gòu)性與最大可分性雖然從不同的出發(fā)點(diǎn)來定義優(yōu)化問題中的目標(biāo)函數(shù)，但最終這兩種特性得到了完全相同的優(yōu)化問題：

接著使用拉格朗日乘子法求解上面的優(yōu)化問題，得到：

因此只需對(duì)協(xié)方差矩陣進(jìn)行特征值分解即可求解出W，PCA算法的整個(gè)流程如下圖所示：

5. 核化線性降維

線性降維方法假設(shè)從高維空間到低維空間的函數(shù)映射是線性的,然而,在不少現(xiàn)實(shí)任務(wù)中,可能需要非線性映射才能找到恰當(dāng)?shù)牡途S嵌入,圖10.6給出了一個(gè)例子,樣本點(diǎn)從二維空間中的矩形區(qū)域采樣后以S形曲面嵌入到三維空間,若直接使用線性降維方法對(duì)三維空間觀察到的樣本點(diǎn)進(jìn)行降維,則將丟失原本的低維結(jié)構(gòu),為了對(duì)“原本采樣的”低維空間與降維后的低維空間加以區(qū)別,我們稱前者為“本真”(intrinsic)低維空間。

正如SVM在處理非線性可分時(shí)，通過引入核函數(shù)將樣本投影到高維特征空間，接著在高維空間再對(duì)樣本點(diǎn)使用超平面劃分。這里也是相同的問題：若我們的樣本數(shù)據(jù)點(diǎn)本身就不是線性分布，那還如何使用一個(gè)超平面去近似表出呢？因此也就引入了核函數(shù)，即先將樣本映射到高維空間，再在高維空間中使用線性降維的方法。下面主要介紹**核化主成分分（KPCA）**的思想。

5.1 基本思想

若核函數(shù)的形式已知，即我們知道如何將低維的坐標(biāo)變換為高維坐標(biāo)，這時(shí)我們只需先將數(shù)據(jù)映射到高維特征空間，再在高維空間中運(yùn)用PCA即可。但是一般情況下，我們并不知道核函數(shù)具體的映射規(guī)則，例如：Sigmoid、高斯核等，我們只知道如何計(jì)算高維空間中的樣本內(nèi)積，這時(shí)就引出了KPCA的一個(gè)重要?jiǎng)?chuàng)新之處：即空間中的任一向量，都可以由該空間中的所有樣本線性表示。

6. 流形學(xué)習(xí)

流形學(xué)習(xí)（manifold learning）是一種借助拓?fù)淞餍胃拍畹慕稻S方法，流形是指在局部與歐式空間同胚的空間，即在局部與歐式空間具有相同的性質(zhì)，能用歐氏距離計(jì)算樣本之間的距離。這樣即使高維空間的分布十分復(fù)雜，但是在局部上依然滿足歐式空間的性質(zhì)，基于流形學(xué)習(xí)的降維正是這種**“鄰域保持”的思想。其中等度量映射（Isomap）試圖在降維前后保持鄰域內(nèi)樣本之間的距離，而局部線性嵌入（LLE）則是保持鄰域內(nèi)樣本之間的線性關(guān)系**，下面將分別對(duì)這兩種著名的流行學(xué)習(xí)方法進(jìn)行介紹。

6.1 等度量映射（Isomap）

等度量映射(Isometric Mapping, 簡(jiǎn)稱 Isomap) 的基本出發(fā)點(diǎn)是：認(rèn)為低維流形嵌入到高維空間之后,直接在高維空間中計(jì)算直線距離具有誤導(dǎo)性,因?yàn)楦呔S空間中的直線距離在低維嵌入流形上是不可達(dá)的。

如圖10.7(a)所示,低維嵌入流形上兩點(diǎn)間的距離是“測(cè)地線”(geodesic)距離: 想象一只蟲子從一點(diǎn)爬到另一點(diǎn),如果它不能脫離曲面行走,那么圖10.7(a)中的紅色曲線是距離最短的路徑,即S曲面上的測(cè)地線,測(cè)地線距離是兩點(diǎn)之間的本真距離,顯然,直接在高維空間中計(jì)算直線距離是不恰當(dāng)?shù)?

利用流形在局部上與歐式空間同胚的性質(zhì)，可以使用近鄰距離來逼近測(cè)地線距離**，即對(duì)于一個(gè)樣本點(diǎn)，它與近鄰內(nèi)的樣本點(diǎn)之間是可達(dá)的，且距離使用歐式距離計(jì)算，這樣整個(gè)樣本空間就形成了一張近鄰圖，高維空間中兩個(gè)樣本之間的距離就轉(zhuǎn)為最短路徑問題?？刹捎弥?strong>Dijkstra算法或Floyd算法計(jì)算最短距離，得到高維空間中任意兩點(diǎn)之間的距離后便可以使用MDS算法來其計(jì)算低維空間中的坐標(biāo)。

從MDS算法的描述中我們可以知道：MDS先求出了低維空間的內(nèi)積矩陣B，接著使用特征值分解計(jì)算出了樣本在低維空間中的坐標(biāo)，但是并沒有給出通用的投影向量w，因此對(duì)于需要降維的新樣本無從下手，書中給出的權(quán)宜之計(jì)是是將訓(xùn)練樣本的高維空間坐標(biāo)作為輸入、低維空間坐標(biāo)作為輸出,訓(xùn)練一個(gè)回歸學(xué)習(xí)器來對(duì)新樣本的低維空間坐標(biāo)進(jìn)行預(yù)測(cè)。

Isomap算法流程如下圖：

對(duì)近鄰圖的構(gòu)建通常有兩種做法,一種是指定近鄰點(diǎn)個(gè)數(shù),例如歐氏距離最近的k個(gè)點(diǎn)為近鄰點(diǎn),這樣得到的近鄰圖稱為k近鄰圖；另一種是指定距離閾值$?$，距離小于$閾值?$的點(diǎn)被認(rèn)為是近鄰點(diǎn),這樣得到的近鄰圖稱為$??$近鄰圖。

兩種方式均有不足：

若鄰域范圍指定過大，則會(huì)造成“短路問題”，即本身距離很遠(yuǎn)卻成了近鄰，將距離近的那些樣本扼殺在搖籃。
若鄰域范圍指定過小，則會(huì)造成“斷路問題”，即有些樣本點(diǎn)無法可達(dá)了，整個(gè)世界村被劃分為互不可達(dá)的小部落。

6.2 局部線性嵌入(LLE)

與Isomap試圖保持近鄰樣本之間的距離不同,局部線性嵌入(Locally Linear Embedding, 簡(jiǎn)稱LLE) 試圖保持鄰域內(nèi)樣本之間的線性關(guān)系.如圖10.9所示,假定樣本點(diǎn)$xj,xk,xlxi?$的坐標(biāo)能通過它的鄰域樣本$xj,xk,xlxj?,xk?,xl?$的坐標(biāo)通過線性組合而重構(gòu)出來,即

7. 度量學(xué)習(xí)

在機(jī)器學(xué)習(xí)中,對(duì)高維數(shù)據(jù)進(jìn)行降維的主要目的是希望找到一個(gè)合適的低維空間,在此空間中進(jìn)行學(xué)習(xí)能比原始空間性能更好,事實(shí)上,每個(gè)空間對(duì)應(yīng)了在樣本屬性上定義的一個(gè)距離度量,而尋找合適的空間,實(shí)質(zhì)上就是在尋找一個(gè)合適的距離度量,那么,為何不直接嘗試“學(xué)習(xí)”出一個(gè)合適的距離度量呢?這就是度量學(xué)習(xí)(metric learning)的基本動(dòng)機(jī).

首先要學(xué)習(xí)出距離度量必須先定義一個(gè)合適的距離度量形式。對(duì)兩個(gè)樣本$xixi?$與$xjxj?$，它們之間的平方歐式距離為：

若各個(gè)屬性重要程度不一樣即都有一個(gè)權(quán)重，則得到加權(quán)的平方歐式距離：

此時(shí)各個(gè)屬性之間都是相互獨(dú)立無關(guān)的，但現(xiàn)實(shí)中往往會(huì)存在屬性之間有關(guān)聯(lián)的情形，例如：身高和體重，一般人越高，體重也會(huì)重一些，他們之間存在較大的相關(guān)性。這樣計(jì)算距離就不能分屬性單獨(dú)計(jì)算，于是就引入經(jīng)典的馬氏距離(Mahalanobis distance):

標(biāo)準(zhǔn)的馬氏距離中M是協(xié)方差矩陣的逆，馬氏距離是一種考慮屬性之間相關(guān)性且尺度無關(guān)（即無須去量綱）的距離度量。

換句話說：度量學(xué)習(xí)便是對(duì)度量矩陣進(jìn)行學(xué)習(xí)。

現(xiàn)在來回想一下前面我們接觸的機(jī)器學(xué)習(xí)不難發(fā)現(xiàn)：機(jī)器學(xué)習(xí)算法幾乎都是在優(yōu)化目標(biāo)函數(shù)，從而求解目標(biāo)函數(shù)中的參數(shù)。同樣對(duì)于度量學(xué)習(xí)，也需要設(shè)置一個(gè)優(yōu)化目標(biāo)，書中簡(jiǎn)要介紹了錯(cuò)誤率和相似性兩種優(yōu)化目標(biāo)，此處不再展開。

降維是將原高維空間嵌入到一個(gè)合適的低維子空間中，接著在低維空間中進(jìn)行學(xué)習(xí)任務(wù)；

度量學(xué)習(xí)則是試圖去學(xué)習(xí)出一個(gè)距離度量來等效降維的效果，兩者都是為了解決維數(shù)災(zāi)難帶來的諸多問題。