k近鄰學(xué)習(xí)
kNN學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法即彪。
- 工作機(jī)制
給定測(cè)試樣本街州，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本晴音，然后根據(jù)這k個(gè)“鄰居”的信息來(lái)進(jìn)行預(yù)測(cè)刑顺。
對(duì)于kNN學(xué)習(xí)中氯窍，最重要的是對(duì)k的選取和對(duì)距離的定義。
對(duì)于最近鄰分類器（1NN蹲堂，即k=1）狼讨，其出錯(cuò)的概率為：
其中x為測(cè)試樣本，其最近鄰樣本為z柒竞，假設(shè)樣本獨(dú)立同分布政供，且對(duì)任意x和任意小正數(shù)距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本. 令
表示貝葉斯最有分類器的結(jié)果, 則可以推導(dǎo)出：
最近鄰分類器雖簡(jiǎn)單，但它的泛化錯(cuò)誤率不超過(guò)貝葉斯最優(yōu)分類器的錯(cuò)誤率的兩倍朽基。
低維嵌入
前面的討論的都是基于假設(shè)：對(duì)任意和任意小正數(shù)
, 在
附近
距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本布隔。但是這在現(xiàn)實(shí)任務(wù)中是很難實(shí)現(xiàn)的而且隨著特征維數(shù)增加，所需要的樣本數(shù)飛速增長(zhǎng)稼虎，高維特征也會(huì)使距離運(yùn)算量更大衅檀，耗費(fèi)時(shí)間更長(zhǎng)。
-
維度災(zāi)難
在高維情形下出現(xiàn)的數(shù)據(jù)樣本稀疏霎俩，距離計(jì)算困難等問(wèn)題哀军，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙沉眶。
MDS算法(多維縮放)
多為縮放是一種經(jīng)典的降維算法传藏。假設(shè)個(gè)樣本在原始空間的距離矩陣為
, 其中第
行第
列的元素
為兩個(gè)樣本
和
之間的距離，而我們的目標(biāo)就是獲得樣本在
維空間的表示
, 且任意兩個(gè)樣本在
維空間中的歐氏距離等于原始空間中的距離,即
.令
, 其中
為降維后樣本的內(nèi)積矩陣,
, 有:
為了便于討論, 令降維后的樣本被中心化了, 則推導(dǎo)后可以得到:
由此可以利用降維前的距離矩陣來(lái)求降維后的內(nèi)積矩陣
, 并對(duì)其做特征值分解
, 其中
為特征值組成的對(duì)角矩陣,
為特征向量矩陣. 假設(shè)其中有
個(gè)非零特征值, 它們組成的對(duì)角矩陣
和特征向量矩陣
則有以下關(guān)系:
實(shí)際中, 為了有效降維(降到), 則不一定要求降維后的距離嚴(yán)格相等, 此時(shí)取前
個(gè)非零特征值對(duì)應(yīng)的
和
:
MDS算法流程：
除了MDS算法彤守，基于線性變換來(lái)進(jìn)行降維的線性降維是最簡(jiǎn)單的降維方法, 這類方法被稱作線性降維方法毯侦，下一節(jié)將以PCA主成分分析為例進(jìn)行介紹。
主成分分析
主成分分析(PCA)是最常用的一種降維方法具垫。對(duì)于一個(gè)能夠?qū)⑺袠颖具M(jìn)行恰當(dāng)表達(dá)的超平面侈离，基于其最近重構(gòu)性（樣本點(diǎn)到這個(gè)超平面的距離都足夠近）主成分分析的優(yōu)化目標(biāo)為:
而基于其最大可分性（樣本點(diǎn)在這個(gè)超平面上的投影盡可能分開(kāi)）主成分分析的優(yōu)化目標(biāo)：
對(duì)以上兩個(gè)式子使用拉格朗日乘子法得到：
于是，對(duì)協(xié)方差矩陣做特征值分解筝蚕，對(duì)所求得的特征值排序卦碾，取前個(gè)特征值構(gòu)成的特征向量構(gòu)成，就得到PCA的解起宽。
算法流程:
維數(shù)由降到了
洲胖。 這里的
值可以人工指定，也可以通過(guò)其他開(kāi)銷小的學(xué)習(xí)器來(lái)交叉驗(yàn)證坯沪，也可通過(guò)重構(gòu)閾值來(lái)設(shè)定绿映，例如設(shè)
,選擇合適的
使得:
PCA僅需保留與樣本的均值向量即可通過(guò)簡(jiǎn)單的向量減法和矩陣-向量乘法將新樣本投影至低維空間中。
核化線性降維
線性降維方法假設(shè)從高維空間到低維空間的函數(shù)映射是線性的腐晾，但現(xiàn)實(shí)任務(wù)中叉弦，可能需要非線性映射才能找到恰當(dāng)?shù)牡途S嵌入。進(jìn)行非線性降維的常用方法便是基于核技巧來(lái)對(duì)線性降維方法進(jìn)行核化藻糖。
核主成分分析（KPCA）算法：
假定將在高維特征空間中把數(shù)據(jù)投影到由W確定的超平面上淹冰，即PCA欲求解：
其中是樣本點(diǎn)在高維特征空間中的像，于是有：
然后引入映射颖御，即有.再引入核函數(shù)：
最后代入化簡(jiǎn)得：,其中K為核函數(shù)對(duì)應(yīng)的核矩陣榄棵。
流形學(xué)習(xí)
流形學(xué)習(xí)是一類借鑒了拓?fù)淞餍胃拍畹膶榉椒ǎ餍问侵冈诰植颗c歐式空間同胚的空間（即在局部與歐式空間具有相同的性質(zhì)）潘拱，能用歐氏距離計(jì)算樣本之間的距離。
等度量映射（Isomap）
其基本出發(fā)點(diǎn)是認(rèn)為低維流形嵌入到高維空間后拧略，然后直接在高維空間中計(jì)算直線距離具有誤導(dǎo)性芦岂，因?yàn)楦呔S空間中的直線距離在低維嵌入流形上是不可達(dá)的。因此利用流形在局部上與歐式空間同胚的性質(zhì)垫蛆，可以使用近鄰距離來(lái)逼近測(cè)地線距離禽最。例如在一維空間中有一直線腺怯，將其嵌入二維空間時(shí)變成了非線形，兩端點(diǎn)的距離就會(huì)發(fā)生改變川无，此時(shí)就產(chǎn)生了距離計(jì)算的偏差呛占。
在近鄰連接圖上計(jì)算兩點(diǎn)間的最短距離，可以采用Dijkstra算法或者Floyd算法懦趋，在得到任意兩點(diǎn)的距離之后晾虑。可通過(guò)MDS方法來(lái)獲得樣本點(diǎn)在低維空間中的坐標(biāo)仅叫。
Isomap算法的流程：
最近鄰圖的構(gòu)建有兩種方法:
1帜篇、指定近鄰點(diǎn)數(shù)目，與kNN一樣選取k個(gè)最近的鄰居诫咱；
2笙隙、指定鄰域半徑，距離小于該閾值的選定為其近鄰點(diǎn)坎缭。
對(duì)于兩種方法竟痰，會(huì)有以下問(wèn)題：
1、鄰域范圍指定過(guò)大掏呼，則會(huì)造成“短路問(wèn)題”坏快，即距離很遠(yuǎn)的點(diǎn)也可能會(huì)被誤認(rèn)為近鄰；
2哄尔、鄰域范圍指定過(guò)小假消，則會(huì)造成“斷路問(wèn)題”，即有些區(qū)域和其他區(qū)域不可互達(dá)岭接。
LLE算法（局部線性嵌入）
局部線性嵌入試圖保持鄰域內(nèi)樣本間的線性關(guān)系富拗。
假設(shè)樣本點(diǎn)通過(guò)它的領(lǐng)域樣本的坐標(biāo)通過(guò)線性組合重構(gòu)得到：
LLE算法分為兩步：
1鸣戴、根據(jù)近鄰關(guān)系計(jì)算出所有樣本的鄰域重構(gòu)系數(shù)w
2啃沪、根據(jù)鄰域重構(gòu)系數(shù)不變，求解低維坐標(biāo)
其中式(10.27)：
度量學(xué)習(xí)
對(duì)高維進(jìn)行降維的主要目的是找到一個(gè)合使的低維空間窄锅，實(shí)際上就是在尋找一個(gè)合使的距離度量创千。度量學(xué)習(xí)便是嘗試學(xué)習(xí)出一個(gè)合使的距離度量。
對(duì)于兩個(gè)d維樣本和
入偷，它們之間的平方歐式距離：
其中表示
和
在第k維上的距離.
假定各個(gè)屬性有其不同的重要性追驴，即引入w,于是有：
其中W的非對(duì)角元素均為零，故可以將W替換為一個(gè)普通的半正定對(duì)稱矩陣M（協(xié)方差矩陣的逆疏之，即）殿雪，于是得到馬氏距離：
而度量學(xué)習(xí)即是對(duì)M的學(xué)習(xí)，為了保持距離非負(fù)且對(duì)稱锋爪，于是M必須是正定對(duì)稱矩陣丙曙，即滿足必有正交基P使得.
對(duì)M的學(xué)習(xí)的前提是要設(shè)定一個(gè)目標(biāo)爸业，比如希望提高近鄰分類器的性能，則可以將M嵌入到近鄰分類器的評(píng)價(jià)指標(biāo)中去亏镰，通過(guò)優(yōu)化該性能指標(biāo)從而求得M.
我們不僅能夠?qū)㈠e(cuò)誤率等這種監(jiān)督學(xué)習(xí)目標(biāo)作為度量學(xué)習(xí)的優(yōu)化目標(biāo)扯旷，還可以在度量學(xué)習(xí)種引入領(lǐng)域知識(shí)，比如已知一些樣本類似索抓，一些樣本不相似钧忽。于是相似樣本的樣本距離盡可能小，不相似的樣本之間的距離盡可能大纸兔。
和分別表示相似集合和不相似集合惰瓜。
度量學(xué)習(xí)習(xí)得的半正定對(duì)稱距離度量矩陣M，若其是低秩矩陣汉矿，則可以對(duì)其進(jìn)行特征值分解崎坊，總能找到一組正交基小于元素。于是度量學(xué)習(xí)學(xué)得的結(jié)果可以衍生出一個(gè)降維矩陣以用于降維之目的洲拇。
