10.降維和度量學(xué)習(xí)

10.1k近鄰學(xué)習(xí)

k近鄰（k-NearestNeighbor，簡稱kNN）學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法，其原理是：給定測試樣本，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本，然后基于這k個(gè)鄰居的信息來進(jìn)行預(yù)測。在分類任務(wù)中，使用投票法，選擇k個(gè)樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測結(jié)果；在回歸任務(wù)中，使用平均法，將這k個(gè)樣本的實(shí)值輸出標(biāo)記的平均值作為預(yù)測結(jié)果。自然，也可基于距離遠(yuǎn)近進(jìn)行加權(quán)平均或加權(quán)投片，距離越近的樣本權(quán)重越大。

k近鄰學(xué)習(xí)方法，沒有顯示的訓(xùn)練過程，是懶惰學(xué)習(xí)（lazy learning），在訓(xùn)練階段僅把樣本保存起來，訓(xùn)練時(shí)間開銷為零，待收到測試樣本后在進(jìn)行處理；相對應(yīng)急切學(xué)習(xí)（eager learning）而言，就是在訓(xùn)練階段就對樣本進(jìn)行學(xué)習(xí)處理的方法。

k近鄰分類器中，k為不同值時(shí)，分類結(jié)果也就不同；同時(shí)，若采用不同的距離計(jì)算方式，則找出的近鄰也有顯著差別，導(dǎo)致分類結(jié)果也顯著不同。假設(shè)距離計(jì)算是恰當(dāng)?shù)?#xff0c;就是不考慮距離導(dǎo)致的差異性，而就從k這個(gè)參數(shù)的差異就最近鄰分類器在二分類問題上的性能進(jìn)行分析。

?

10.2低維嵌入

k近鄰學(xué)習(xí)方法基于一個(gè)重要的假設(shè)：任意測試樣本x附近任意小的 距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本，即訓(xùn)練樣本的采樣密度足夠大，或稱為密采樣（dense sample）。不過這在現(xiàn)實(shí)任務(wù)中一般很難滿足，假設(shè) ，在單個(gè)屬性情況下，僅需1000個(gè)樣本點(diǎn)平均分布在歸一化后的屬性取值范圍內(nèi)[0,1]，即可使得任務(wù)測試樣本在其附近0.001距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本，此時(shí)最近鄰分類器的錯(cuò)誤率不超過貝葉斯最優(yōu)分類器的錯(cuò)誤率的兩倍；但若在多個(gè)屬性情況下，如假定屬性維數(shù)是20，按照密采樣條件要求，至少需要 (〖10〗^3 )^20=〖10〗^60個(gè)樣本。現(xiàn)實(shí)應(yīng)用中屬性維數(shù)眾多，要滿足密采樣條件，所需的樣本數(shù)目將是天文數(shù)字。而且還要考慮距離度量計(jì)算，高維空間對距離計(jì)算來說不是簡單的開銷，當(dāng)維數(shù)很高時(shí)，連計(jì)算內(nèi)積都不容易。

小貼士：宇宙間基本粒子的總數(shù)約為〖10〗^80 ，一?；覊m中含有幾十億個(gè)基本粒子。宇宙之宏大，數(shù)學(xué)之簡單，令人瞠目結(jié)舌。

上文的分析暴露一個(gè)很嚴(yán)重的問題，就是高維情形下，樣本數(shù)的采樣以及距離計(jì)算問題。在高維情形下出現(xiàn)的數(shù)據(jù)樣本稀疏、距離計(jì)算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為維數(shù)災(zāi)難（curse of dimensionality）。

緩解維數(shù)災(zāi)難的兩個(gè)途徑：一是特征選擇；二是本文要重點(diǎn)介紹的降維（dimension reduction）。思路上，這兩種途徑都是減少維數(shù)，不過一個(gè)是在事前，一個(gè)是在事中。降維，也稱維數(shù)約簡，通過某種數(shù)學(xué)變換將原始高維屬性空間轉(zhuǎn)變?yōu)橐粋€(gè)低維子空間（subspace），在子空間中，樣本密度可以大幅提高，距離計(jì)算也相對容易。事實(shí)上，觀測或收集到的數(shù)據(jù)樣本雖然是高維的，但與學(xué)習(xí)任務(wù)相關(guān)的或許只是某個(gè)低維分布，這也是特征選擇可以事前根據(jù)業(yè)務(wù)來定義的。

那么問題自然是？為什么可以降維？降維后的是否影響樣本距離呢？降維后要求樣本空間中樣本之間的距離在低維空間中得以保持，多維縮放（multiple dimensional scaling，MDS）是一種經(jīng)典的降維方法，證明如下。

維屬性向量。若w_i與w_j（i≠j）正交，則新坐標(biāo)系是一個(gè)正交坐標(biāo)系，此時(shí)W為正交變換?？梢?#xff0c;新空間中的屬性是原空間中屬性的線性組合。

對降維效果的評估，通常是比較降維前后學(xué)習(xí)器的性能，若性能有所提高，則認(rèn)為降維起到了作用。若將維數(shù)降至二維或三維，則可通過可視化技術(shù)來直觀地判斷降維效果。

基于線性變換來進(jìn)行降維的方法稱為線性降維方法，符合Z=W^TX形式，不同之處是對低維空間的性質(zhì)有不同要求，相當(dāng)于對W施加了不同的約束。若要求低維子空間對樣本具有最大可分性，則將得到一種極為常用的線性降維方法，見下節(jié)。

10.3主成分分析

主成分分析（PrincipalComponent Analysis,PCA）是最常用的一種降維方法。對于正交屬性空間中的樣本點(diǎn)，如何用一個(gè)超平面（直線的高維推廣）對所有樣本進(jìn)行恰當(dāng)?shù)谋磉_(dá)？若存在這樣的超平面，應(yīng)具有如下兩點(diǎn)性質(zhì)：

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

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

基于最近重構(gòu)性和最大可分性，能分別得到主成分分析的兩種等價(jià)推導(dǎo)。

PCA僅需保留W與樣本的均值向量即可通過簡單的向量減法和矩陣-向量乘法將新樣本投影至低維空間中。顯然，低維空間與原始高維空間必有不同，因?yàn)閷?yīng)于最小的d-d*個(gè)特征值的特征向量被舍棄了，這是降維導(dǎo)致的后果。但舍棄這部分信息卻又是必要的，一方面是舍棄后可使樣本的采樣密度增大，這是降維的初衷；另一方面，當(dāng)數(shù)據(jù)受到噪聲影響時(shí)，最小特征值所對應(yīng)的特征向量往往與噪聲有關(guān)，一定程度上舍棄后可以起到去噪效果。

10.4核化線性降維

線性降維方法假設(shè)從高維空間到低維空間的函數(shù)映射是線性的，不過，在現(xiàn)實(shí)任務(wù)中可能需要非線性映射才能找到恰當(dāng)?shù)牡途S嵌入。這一節(jié)主要就是說非線性降維，以為保持本真（intrinsic）低維空間。非線性降維方法的一種常用方法，是基于核技巧對線性降維方法進(jìn)行核化（kernelized）。下文說明核主成分分析（Kernelized PCA，KPCA）。

?

10.5流形學(xué)習(xí)

流形學(xué)習(xí)（manifoldlearning）是一類借鑒了拓?fù)淞餍胃拍畹慕稻S方法。流形是在局部與歐式空間同胚的空間，換言之，它在局部具有歐式空間的性質(zhì)，能用歐式距離來進(jìn)行距離計(jì)算。若低維流形嵌入到高維空間中，則數(shù)據(jù)樣本在高維空間的分布雖然看上去非常復(fù)雜，但在局部上仍具有歐式空間的性質(zhì)，如此，可以容易地在局部建立降維映射關(guān)系，然后再設(shè)法將局部映射推廣到全局。當(dāng)維數(shù)被降至二維或三維時(shí)，能對數(shù)據(jù)進(jìn)行可視化展示。

對此，我的理解是，在一個(gè)曲面上，跨越彎曲的兩點(diǎn)，無法用歐式距離，但在曲面的某部分切面是可以用歐式距離來計(jì)算。

1）等度量映射

等度量映射（IsometricMapping，Isomap）的基本出發(fā)點(diǎn)，是認(rèn)為低維流形嵌入到高維空間之后，直接在高維空間中計(jì)算直線距離具有誤導(dǎo)性，因?yàn)楦呔S空間中的直線距離在低維嵌入流形上是不可達(dá)的。S曲面上的測地線距離是兩點(diǎn)之間的本真距離，直接在高維空間中計(jì)算直線距離是不恰當(dāng)?shù)?#xff0c;因?yàn)榭缭搅藦澢鷧^(qū)域。那么如何計(jì)算測地線距離呢？可利用流形在局部上與歐式空間同胚的性質(zhì)，對每個(gè)點(diǎn)基于歐式距離找出其近鄰點(diǎn)，然后就能建立一個(gè)近鄰連接圖；圖中近鄰點(diǎn)之間存在連接，而非近鄰點(diǎn)之間不存在連接；于是，兩點(diǎn)之間測地線的距離，就轉(zhuǎn)變?yōu)橛?jì)算近鄰連接圖上兩點(diǎn)之間的最短路徑問題。

這樣理解，在曲面上的一定平滑區(qū)域內(nèi)基于歐式距離找出近鄰點(diǎn)，構(gòu)成一個(gè)圖，然后求解圖中兩個(gè)點(diǎn)的最短距離，這個(gè)思想就是用近鄰距離來接近測地線距離。在近鄰接圖上計(jì)算兩點(diǎn)間的最短路徑，可采用著名的Dijkstra算法或Floyd算法（http://blog.csdn.net/fjssharpsword/article/details/52953640），得到兩點(diǎn)距離之后，可用MDS方法來獲得樣本點(diǎn)在低維空間中的坐標(biāo)。算法描述如下：

輸入：樣本集D={x₁,x₂,…,x_m}；

????? 近鄰參數(shù)k；???????

????? 低維空間數(shù)d*；

過程：fori=1,2,…,m do

????????? 確定x_i的k近鄰；

????????? x_i與k近鄰點(diǎn)之間的距離設(shè)置為歐式距離，與其他點(diǎn)的距離設(shè)置為無窮大；

????? end for

????? 調(diào)用最短路徑算法計(jì)算任意兩樣本點(diǎn)之間的距離dist(x_i,x_j)；

????? 將dist(x_i,x_j)作為MDS算法的輸入；

????? return MDS算法的輸出

輸出：樣本集D在低維空間的投影Z={z₁,z₂,…,z_m}

Isomap得到了訓(xùn)練樣本在低維空間的坐標(biāo)，對于新樣本，如何將其映射到低維空間？常用解決方案是，將訓(xùn)練樣本的高維空間坐標(biāo)作為輸入、低維空間坐標(biāo)作為輸出，訓(xùn)練一個(gè)回歸學(xué)習(xí)器來對新樣本的低維空間坐標(biāo)進(jìn)行預(yù)測。文中說不是最佳之法，卻也沒有更好的。

對近鄰圖的構(gòu)建有兩種做法：一種是指定近鄰點(diǎn)個(gè)數(shù)，如歐式距離最近的k個(gè)點(diǎn)為近鄰點(diǎn)，稱為k近鄰圖；另一種是指定距離閾值 ，距離小于閾值的點(diǎn)被認(rèn)為是近鄰點(diǎn)，稱為 近鄰圖。兩種方法均有不足，若近鄰范圍指定過大，則距離很遠(yuǎn)的點(diǎn)可能被誤認(rèn)為是近鄰，出現(xiàn)短路問題；近鄰范圍指定過小，則圖中有些區(qū)域可能與其他區(qū)域不存在連接，出現(xiàn)斷路問題。斷路和短路都會(huì)給后續(xù)的最短路徑計(jì)算造成誤導(dǎo)。

2）局部線性嵌入

與Isomap試圖保持近鄰樣本之間的距離不同，局部線性嵌入（Locally Linear Embedding,LLE）試圖保持鄰域內(nèi)樣本間的線性關(guān)系。假定樣本點(diǎn)x _i的坐標(biāo)能通過它的鄰域樣本x _j、x _k、x _l的坐標(biāo)通過線性組合而重構(gòu)出來，即：x _i=w _ijx _j+ w _ikx _k+w _ilx _l，自然該式在低維空間中需要保持。

算法中對于不在樣本x_i鄰域區(qū)域的樣本x_j，無論其如何變化都對x_i和z_i沒有任何影響，這種將變動(dòng)限制在局部的思想在許多地方都很有用。可以發(fā)現(xiàn)算法思想的重要性，如近似、貪心、局部等概念。

10.6度量學(xué)習(xí)

在機(jī)器學(xué)習(xí)中，對高維數(shù)據(jù)進(jìn)行降維的主要目的是找到一個(gè)合適的低維空間，在該空間中進(jìn)行學(xué)習(xí)能比原始空間性能更好。每個(gè)空間對應(yīng)了在樣本屬性上定義的一個(gè)距離度量，而尋找合適的空間，本質(zhì)上就是尋找一個(gè)合適的距離度量。度量學(xué)習(xí)（metric learning）的基本動(dòng)機(jī)就是去學(xué)習(xí)一個(gè)合適的距離度量。

降維的核心在在于尋找合適空間，而合適空間的定義就是距離度量，所以學(xué)習(xí)合適的距離度量就是度量學(xué)習(xí)的目的。要對距離度量進(jìn)行學(xué)習(xí)，要有一個(gè)便于學(xué)習(xí)的距離度量表達(dá)形式。

其中M稱為度量矩陣，度量學(xué)習(xí)就是對M進(jìn)行學(xué)習(xí)。為保持距離非負(fù)且對稱，M須是半正定對稱矩陣，即必有正交基P使得M能寫為M=PP^T。

至此，已構(gòu)建了學(xué)習(xí)的對象是M這個(gè)度量矩陣，接下來就是給學(xué)習(xí)設(shè)定一個(gè)目標(biāo)從而求得M。假定是希望提高近鄰分類器的性能，則可將M直接嵌入到近鄰分類器的評價(jià)指標(biāo)中去，通過優(yōu)化該性能指標(biāo)相應(yīng)地求得M，以近鄰成分分析（Neighbourhood Component Analysis，NCA）進(jìn)行討論。

近鄰分類器判別時(shí)通常采用多數(shù)投票法，領(lǐng)域中的每個(gè)樣本投1票，領(lǐng)域外的樣本投0票。將其替換為概率投票法，對任意樣本x_j，它對x_i分類結(jié)果影響的概率為：

本章的核心是降維，涉及到最基礎(chǔ)的PCA及其非線性核化，再而就是流形學(xué)習(xí)和度量學(xué)習(xí)，都可起到降維的目標(biāo)。為什么要降維呢？因?yàn)楦呔S無法滿足密采樣以及計(jì)算開銷大。

總結(jié)

以上是生活随笔為你收集整理的机器学习笔记(十)降维和度量学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。