k 近鄰(k-Nearest Neighbor，簡稱 kNN)學習是一種常用的監督學習方法， 其工作機制非常簡單: 給定測試樣本?基于某種距離度量找出訓練集中與其最 靠近的 k 個訓練樣本，然后基于這 k 個"鄰居"的信息來進行預測. 通常， 在分 類任務中可使用"投票法" 即選擇這 k 個樣本中出現最多的類別標記作為預 測結果;在回歸任務中時使用"平均法" ，即將這 k 個樣本的實值輸出標記的 平均值作為預測結果;還可基于距離遠近進行加權平均或加權投票，距離越近 的樣本權重越大.
與前面介紹的學習方法相比， k 近鄰學習有一個明顯的不同之處: 它似乎 沒有顯式的訓練過程!事實上，它是"懶惰學習" (lazy learning)的著名代表， 此類學習技術在訓練階段僅僅是把樣本保存起來，訓練時間開銷為零，待收到 測試樣本后再進行處理;相應的，那些在訓練階段就對樣本進行學習處理的方 法，稱為"急切學習" (eager learning).
假設樣本獨立罔分布，且對任意 m 和任意小E數 8，在 z 附近 6 距離范圍 內總能找到一個訓練樣本;換言之，對任意測試樣本，總能在任意近的范圍內找 到式(10.1)中的訓練樣本 z.
上一節的討論是基于一個重要假設:任意測試樣本 a 附近任意小的 6 距 離范圍內總能找到一個訓練樣本，即訓練樣本的來樣密度足夠大，或稱為"辛苦 來樣" (dense sample). 然而，這個假設在現實任務中通常很難滿足，例如若 8 = 0.001，僅考慮單個屬性，則僅需 1000 個樣本點平均分布在歸一化后的屬 性取值范圍內，即可使得任意測試樣本在其附近 0.001 距離范圍內總能找到一 個訓練樣本，此時最近鄰分類器的錯誤率不超過貝葉斯最優分類器的錯誤率 的兩倍.然而，這僅是屬性維數為 1 的情形，若有更多的屬性，則情況會發生 顯著變化.例如假定屬性維數為 20，若要求樣本滿足密來樣條件，則至少需 (103)20 = 1060 個樣本.現實應用中屬性維數經常成千上萬，要滿足密采樣條件 所需的樣本數目是無法達到的天文數字.此外，許多學習方法都涉及距離計算， 而高維空間會給距離計算帶來很大的麻煩，例如當維數很高時甚至連計算內積都不再容易.
事實上，在高維情形下 出 現的數據樣本稀疏、 距離計算困難等問 題， 是所有機器學習方法共同面 臨 的嚴重障礙， 被稱為" 維數災難" (curse of
dimensionality) .
緩解維數災難的一個重要途徑是降維(dimension red uction) ， 亦稱"維數 約簡 PP ，即通過某種數學變換將原始高維屬性空間轉變為一個低維"子空 間" (subspace)，在這個子空間 中樣本密度大幅提高， 距離計算也變得更為容 易為什么能進行降維?這是因為在很多時候， 人們觀測或收集到的數據樣本 雖是高維的?但與學習任務密切相關的也許僅是某個低維分布，即高維空間中 的一個低維"嵌入" (embedding). 原始高維 空間中的樣本點，在這個低維嵌入子空間中更容易進行學習.
若要求原始空間中樣本之間的距離在低維空間中得以保持，即得到"多維縮放" (Multiple Dimensional Scaling，簡稱 MDS) [Cox and Cox, 2001] 這樣一種經典的降維方法. 下面做一個簡單的介紹.
假定 m 個樣本在原始空間的距離矩陣為 D ε J?mx氣 其第 4 行 j 列的元 素 distij 為樣本 Xi 到 Xj 的距離. 我們的目標是獲得樣本在 d’ 維空間的表示 Z E ]Rd’xm , d’ ~三 d， 且任意兩個樣本在 d’ 維空間中的歐氏距離等于原始空間中 的距離，即 IIZi - zjll = distij.
降維后低維空間的維數 d’ 通常是由用戶事先指定，或通過在 d’ 值不同的 低維空間中對 k 近鄰分類器(或其他開銷較小的學習器)進行交叉驗證來選取 較好的 d’ 值.PCA 僅需保留 W 與樣本的均值向量即可通過簡單的向量減法和矩陣"向 量乘法將新樣本投影至低維空間中. 顯然，低維空間與原始高維空間必有不同， 因為對應于最小的 d-d’ 個特征值的特征向量被舍棄了，這是降維導致的結果. 但舍棄這部分信息往往是必要的- 一方面舍棄這部分信息之后能使樣本的采 樣密度增大，這正是降維的重要動機; 另一方面，當數據受到噪聲影響時， 最小 的特征值所對應的特征向量往往與噪聲有關?將它們舍棄能在一定程度上起到 去噪的效果.

總結

以上是生活随笔為你收集整理的k 近邻降维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。