周志華 機(jī)器學(xué)習(xí) 西瓜書 全書16章 ppt Chap10降維和度量學(xué)習(xí)

1、丁堯相p k近鄰學(xué)習(xí)p 多維縮放p 主成分分析p 流形學(xué)習(xí)p 度量學(xué)習(xí)k近鄰學(xué)習(xí)的工作機(jī)制pk近鄰(k-Nearest Neighbor, kNN)學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法:l 確定訓(xùn)練樣本，以及某種距離度量。l 對于某個給定的測試樣本，找到訓(xùn)練集中距離最近的k個樣本，對于分類問題使用“投票法”獲得預(yù)測結(jié)果，對于回歸問題使用“平均法”獲得預(yù)測結(jié)果。還可基于距離遠(yuǎn)近進(jìn)行加權(quán)平均或加權(quán)投票，距離越近的樣本權(quán)重越大。l 投票法：選擇這k個樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測結(jié)果。l 平均法：將這k個樣本的實值輸出標(biāo)記的平均值作為預(yù)測結(jié)果。p“懶惰學(xué)習(xí)”(lazy learning): 此類學(xué)習(xí)技術(shù)在

2、訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時間開銷為零，待收到測試樣本后再進(jìn)行處理。p“急切學(xué)習(xí)”(eager learning): 在訓(xùn)練階段就對樣本進(jìn)行學(xué)習(xí)處理的方法。K近鄰學(xué)習(xí)沒有顯式的訓(xùn)練過程，屬于“懶惰學(xué)習(xí)”p k近鄰分類器中的k是一個重要參數(shù)，當(dāng)k取不同值時，分類結(jié)果會有顯著不同。另一方面，若采用不同的距離計算方式，則找出的“近鄰”可能有顯著差別，從而也會導(dǎo)致分類結(jié)果有顯著不同。分析最近鄰分類器（ 1NN ）二分類錯誤率p暫且假設(shè)距離計算是“恰當(dāng)”的，即能夠恰當(dāng)?shù)卣页鰇個近鄰，我們來對“最近鄰分類器”（1NN，即k=1）在二分類問題上的性能做一個簡單的討論。給定測試樣本 ，若其最近鄰樣本為

3、 ，則最近鄰出錯的概率就是 與 類別標(biāo)記不同的概率，即分析1NN二分類錯誤率令 表示貝葉斯最優(yōu)分類器的結(jié)果，有 最近鄰分類雖簡單，但它的泛化錯誤率不超過貝葉斯最優(yōu)分類器錯誤率的兩倍！維數(shù)災(zāi)難 (curse of dimensionality)p上述討論基于一個重要的假設(shè)：任意測試樣本 附近的任意小的 距離范圍內(nèi)總能找到一個訓(xùn)練樣本，即訓(xùn)練樣本的采樣密度足夠大，或稱為“密采樣”。然而，這個假設(shè)在現(xiàn)實任務(wù)中通常很難滿足：l 若屬性維數(shù)為1，當(dāng) =0.001，僅考慮單個屬性，則僅需1000個樣本點平均分布在歸一化后的屬性取值范圍內(nèi)，即可使得任意測試樣本在其附近0.001距離范圍內(nèi)總能找到一個訓(xùn)練樣本

4、，此時最近鄰分類器的錯誤率不超過貝葉斯最優(yōu)分類器的錯誤率的兩倍。若屬性維數(shù)為20，若樣本滿足密采樣條件，則至少需要 個樣本。l 現(xiàn)實應(yīng)用中屬性維數(shù)經(jīng)常成千上萬，要滿足密采樣條件所需的樣本數(shù)目是無法達(dá)到的天文數(shù)字。許多學(xué)習(xí)方法都涉及距離計算，而高維空間會給距離計算帶來很大的麻煩，例如當(dāng)維數(shù)很高時甚至連計算內(nèi)積都不再容易。l 在高維情形下出現(xiàn)的數(shù)據(jù)樣本稀疏、距離計算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為“維數(shù)災(zāi)難”。 p 緩解維數(shù)災(zāi)難的一個重要途徑是降維(dimension reduction)l 即通過某種數(shù)學(xué)變換，將原始高維屬性空間轉(zhuǎn)變?yōu)橐粋€低維“子空間” (subspace

5、)，在這個子空間中樣本密度大幅度提高，距離計算也變得更為容易。p 為什么能進(jìn)行降維？l 數(shù)據(jù)樣本雖然是高維的，但與學(xué)習(xí)任務(wù) 密切相關(guān)的也許僅是某個低維分布，即高維空間中的一個低維“嵌入” (embedding)，因而可以對數(shù)據(jù)進(jìn)行有效的降維。p若要求原始空間中樣本之間的距離在低維空間中得以保持，即得到“多維縮放”(Multiple Dimensional Scaling, MDS)：p假定有m個樣本，在原始空間中的距離矩陣為 ，其第i行j列的元素 為樣本 到 的距離。p目標(biāo)是獲得樣本在 維空間中的歐氏距離等于原始空間中的距離，即 p令 ，其中 為降維后的內(nèi)積矩陣， ，有p 為便于討論，令降維后

6、的樣本 被中心化，即 。顯然，矩陣 的行與列之和均為零，即 易知其中 表示矩陣的跡(trace)， 。令由此即可通過降維前后保持不變的距離矩陣 求取內(nèi)積矩陣 : 21111111,ii jji ji jjimmmmijdistdistdistdistdistdistmmmp 對矩陣 做特征值分解(eigenvalue decomposition) ，其中 為特征值構(gòu)成的對角矩陣， 為特征向量矩陣，假定其中有 個非零正特征值， 它們構(gòu)成對角矩陣 ， 為特征向量矩陣。 令 表示相應(yīng)的特征矩陣，則 可表達(dá)為 。111B000000nnnZVVVV p 對矩陣 做特征值分解(eigenvalue de

7、composition) ，其中 為特征值構(gòu)成的對角矩陣，p 在現(xiàn)實應(yīng)用中為了有效降維，往往僅需降維后的距離與原始空間中的距離盡可能接近，而不必嚴(yán)格相等。此時可取 個最大特征值構(gòu)成對角矩陣 ，令 表示相應(yīng)的特征向量矩陣，則 可表達(dá)為 為特征向量矩陣，假定其中有 個非零正特征值， 它們構(gòu)成對角矩陣 ， 為特征向量矩陣。 令 表示相應(yīng)的特征矩陣，則 可表達(dá)為 。MDS算法的描述p 一般來說，欲獲得低維子空間，最簡單的是對原始高維空間進(jìn)行線性變換。給定 維空間中的樣本 ，變換之后得到 維空間中的樣本p 變換矩陣 可視為 個 維屬性向量。換言之， 是原屬性向量 在新坐標(biāo)系 中的坐標(biāo)軸向量。若 與 正交

8、，則新坐標(biāo)系是一個正交坐標(biāo)系，此時 為正交變換。顯然，新空間中的屬性是原空間中的屬性的線性組合。p 基于線性變換來進(jìn)行降維的方法稱為線性降維方法，對低維子空間性質(zhì)的不同要求可通過對 施加不同的約束來實現(xiàn)。其中 是變換矩陣， 是樣本在新空間中的表達(dá)。主成分分析(Principal Component Analysis, 簡稱PCA)p對于正交屬性空間中的樣本點，如何用一個超平面對所有樣本進(jìn)行恰當(dāng)?shù)谋磉_(dá)？p容易想到，若存在這樣的超平面，那么它大概應(yīng)具有這樣的性質(zhì)：l 最近重構(gòu)性：樣本點到這個超平面的距離都足夠近；l 最大可分性：樣本點在這個超平面上的投影能盡可能分開。p基于最近重構(gòu)性和最大可分性，

9、能分別得到主成分分析的兩種等價推導(dǎo)。最近重構(gòu)性p對樣本進(jìn)行中心化， ，再假定投影變換后得到的新坐標(biāo)系為 ， 其中 是標(biāo)準(zhǔn)正交基向量，p若丟棄新坐標(biāo)系中的部分坐標(biāo)，即將維度降低到 ，則樣本點在低維坐標(biāo)系中的投影是 ， 是 在低維坐標(biāo)下第 維的坐標(biāo)，若基于 來重構(gòu) ，則會得到最近重構(gòu)性p考慮整個訓(xùn)練集，原樣本點 與基于投影重構(gòu)的樣本點 之間的距離為p根據(jù)最近重構(gòu)性應(yīng)最小化上式?？紤]到 是標(biāo)準(zhǔn)正交基， 是協(xié)方差矩陣，有這就是主成分分析的優(yōu)化目標(biāo)。最大可分性p樣本點 在新空間中超平面上的投影是 ，若所有樣本點的投影能盡可能分開，則應(yīng)該使得投影后樣本點的方差最大化。若投影后樣本點的方差是 ，于是優(yōu)化目標(biāo)

10、可寫為 顯然與 等價。PCA的求解p對優(yōu)化式使用拉格朗日乘子法可得 只需對協(xié)方差矩陣 進(jìn)行特征值分解，并將求得的特征值排序： ，再取前 個特征值對應(yīng)的特征向量構(gòu)成 ，這就是主成分分析的解。PCA算法p 降維后低維空間的維數(shù) 通常是由用戶事先指定，或通過在 值不同的低維空間中對k近鄰分類器（或其它開銷較小的學(xué)習(xí)器）進(jìn)行交叉驗證來選取較好的 值。對PCA，還可從重構(gòu)的角度設(shè)置一個重構(gòu)閾值，例如 ，然后選取使下式成立的最小 值：p PCA僅需保留 與樣本的均值向量即可通過簡單的向量減法和矩陣-向量乘法將新樣本投影至低維空間中。p 降維雖然會導(dǎo)致信息的損失，但一方面舍棄這些信息后能使得樣本的采樣密度增

11、大，另一方面，當(dāng)數(shù)據(jù)受到噪聲影響時，最小的特征值所對應(yīng)的特征向量往往與噪聲有關(guān)，舍棄可以起到去噪效果。 p 線性降維方法假設(shè)從高維空間到低維空間的函數(shù)映射是線性的，然而，在不少現(xiàn)實任務(wù)中，可能需要非線性映射才能找到恰當(dāng)?shù)牡途S嵌入：核化主成分分析 (Kernelized PCA, 簡稱KPCA)p非線性降維的一種常用方法，是基于核技巧對線性降維方法進(jìn)行“核化” (kernelized)。p假定我們將在高維特征空間中把數(shù)據(jù)投影到由 確定的超平面上，即PCA欲求解p其中 是樣本點 在高維特征空間中的像。令 ，核化主成分分析 (Kernelized PCA, 簡稱KPCA)p假定 是由原始屬性空間中的

12、樣本點 通過映射 產(chǎn)生，即 p若 能被顯式表達(dá)出來，則通過它將樣本映射至高維空間，再在特征空間中實施PCA即可，即有并且p 一般情形下，我們不清楚 的具體形式，于是引入核函數(shù)p 又由 代入優(yōu)化式 ，有 p 上式為特征值分解問題，取 最大的 個特征值對應(yīng)的特征向量得到解。核化主成分分析 (Kernelized PCA, 簡稱KPCA)其中 為 對應(yīng)的核矩陣， p 對新樣本 ，其投影后的第 維坐標(biāo)為核化主成分分析 (Kernelized PCA, 簡稱KPCA)其中 已經(jīng)過規(guī)范化， 是 的第 個分量。由該式可知，為獲得投影后的坐標(biāo)，KPCA需對所有樣本求和，因此它的計算開銷較大。 p流形學(xué)習(xí)(ma

13、nifold learning)是一類借鑒了拓?fù)淞餍胃拍畹慕稻S方法?！傲餍巍笔窃诰植颗c歐氏空間同胚的空間，換言之，它在局部具有歐氏空間的性質(zhì)，能用歐氏距離來進(jìn)行距離計算。p若低維流形嵌入到高維空間中，則數(shù)據(jù)樣本在高維空間的分布雖然看上去非常復(fù)雜，但在局部上仍具有歐氏空間的性質(zhì)，因此，可以容易地在局部建立降維映射關(guān)系，然后再設(shè)法將局部映射關(guān)系推廣到全局。p當(dāng)維數(shù)被降至二維或三維時，能對數(shù)據(jù)進(jìn)行可視化展示，因此流形學(xué)習(xí)也可被用于可視化。等度量映射(Isometric Mapping，Isomap)p低維流形嵌入到高維空間之后，直接在高維空間中計算直線距離具有誤導(dǎo)性，因為高維空間中的直線距離在低維嵌

14、入流形上不可達(dá)。而低維嵌入流形上兩點間的本真距離是“測地線”(geodesic)距離。等度量映射(Isometric Mapping，Isomap)p測地線距離的計算：利用流形在局部上與歐氏空間同胚這個性質(zhì)，對每個點基于歐氏距離找出其近鄰點，然后就能建立一個近鄰連接圖，圖種近鄰點之間存在連接，而非近鄰點之間不存在連接，于是，計算兩點之間測地線距離的問題，就轉(zhuǎn)變?yōu)橛嬎憬忂B接圖上兩點之間的最短路徑問題。p最短路徑的計算可通過Dijkstra算法或Floyd算法實現(xiàn)。得到距離后可通過多維縮放方法獲得樣本點在低維空間中的坐標(biāo)。等度量映射(Isometric Mapping，Isomap)局部線性嵌入

15、 (Locally Linear Embedding，LLE)p局部線性嵌入試圖保持鄰域內(nèi)的線性關(guān)系，并使得該線性關(guān)系在降維后的空間中繼續(xù)保持。局部線性嵌入 (Locally Linear Embedding，LLE)pLLE先為每個樣本 找到其近鄰下標(biāo)集合 ，然后計算出基于 的中的樣本點對 進(jìn)行線性重構(gòu)的系數(shù) ：其中 和 均為已知，令 ， 有閉式解局部線性嵌入 (Locally Linear Embedding，LLE)pLLE在低維空間中保持 不變，于是 對應(yīng)的低維空間坐標(biāo) 可通過下式求解：p令p則優(yōu)化式可重寫為右式，并通過特征值分解求解。局部線性嵌入 (Locally Linear Em

16、bedding，LLE)研究動機(jī)p在機(jī)器學(xué)習(xí)中，對高維數(shù)據(jù)進(jìn)行降維的主要目的是希望找到一個合適的低維空間，在此空間中進(jìn)行學(xué)習(xí)能比原始空間性能更好。事實上，每個空間對應(yīng)了在樣本屬性上定義的一個距離度量，而尋找合適的空間，實質(zhì)上就是在尋找一個合適的距離度量。那么，為何不直接嘗試“學(xué)習(xí)”出一個合適的距離度量呢？p 欲對距離度量進(jìn)行學(xué)習(xí)，必須有一個便于學(xué)習(xí)的距離度量表達(dá)形式。對兩個 維樣本 和 ，它們之間的平方歐氏距離可寫為 p 其中 表示 與 在第 維上的距離。若假定不同屬性的重要性不同，則可引入屬性權(quán)重 ，得到 p 其中 是一個對角矩陣， ，可通過學(xué)習(xí)確定。 p 的非對角元素均為零，這意味著坐標(biāo)軸

17、是正交的，即屬性之間無關(guān)；但現(xiàn)實問題中往往不是這樣，例如考慮西瓜的“重量”和“體積”這兩個屬性，它們顯然是正相關(guān)的，其對應(yīng)的坐標(biāo)軸不再正交。為此將 替換為一個普通的半正定對稱矩陣 ，于是就得到了馬氏距離(Mahalanobis distance)。其中 亦稱“度量矩陣”，而度量學(xué)習(xí)則是對 進(jìn)行學(xué)習(xí)。注意到為了保持距離非負(fù)且對稱， 必須是（半）正定對稱矩陣，即必有正交基 使得 能寫為 。 p 對 進(jìn)行學(xué)習(xí)當(dāng)然要設(shè)置一個目標(biāo)。假定我們是希望提高近鄰分類器的性能，則可將 直接嵌入到近鄰分類器的評價指標(biāo)中去，通過優(yōu)化該性能指標(biāo)相應(yīng)地求得 。近鄰成分分析(Neighbourhood Component

18、Analysis, NCA)p近鄰成分分析在進(jìn)行判別時通常使用多數(shù)投票法，鄰域中的每個樣本投1票，鄰域外的樣本投0票。不妨將其替換為概率投票法。對于任意樣本 ，它對 分類結(jié)果影響的概率為 p當(dāng) 時， 最大。顯然， 對 的影響隨著它們之間距離的增大而減小。若以留一法(LOO)正確率的最大化為目標(biāo)，則可計算 的留一法正確率，即它被自身之外的所有樣本正確分類的概率為 其中 表示與 屬于相同類別的樣本的下標(biāo)集合。 近鄰成分分析(Neighbourhood Component Analysis, NCA)p整個樣本集上的留一法正確率為p由 和 ，則NCA的優(yōu)化目標(biāo)為 求解即可得到最大化近鄰分類器LOO正確率的距離度量矩陣 。 p 實際上，我們不僅能把錯誤率這樣的監(jiān)督學(xué)習(xí)目標(biāo)作為度量學(xué)習(xí)的優(yōu)化目標(biāo)，還能在度量學(xué)習(xí)中引入領(lǐng)域知識。p 若已知某些樣本相似、某些樣本不相似，則可定義“必連”(must-link)約束集合 與“勿連”(cannot-link)約束集合