K-近鄰演算法

佇咧圖型的方式，最近厝邊隔壁法（KNN演算法，閣譯K-近鄰演算法）是一種用於分類佮迴歸的無母數統計方法。佇這兩款狀況下，輸入包含特徵空間內底的 _k_ 上接近的訓練平本。

* 佇咧 _ k-NN 分類 _ 中，輸出是一个分類族群。一个物件的分類是由厝邊的「多數表決」確定的，_ k _ 個最近厝邊（_ k _ 為正整數，通常較細）上捷看著的分類決定予這个物件的類別。若是 _ k _=  一，則該物件的類別直接由最近的一个節點予。

* 佇咧 _ k-NN 迴歸 _ 中，輸出是該物件的屬性值。該值是其 _ k _ 最近厝邊隔壁的值的平均值。

最近厝邊法採用向量空間模型來分類，概念做仝款類別的案例，彼此的相𫝛度懸，會當藉著計算佮已經知類別案例之相若像度，來評估未知類別案例可能的分類。

K-NN 是一種因為實例的學習，或者是局部近和將所有計算推遲到分類了後的貧性學習。k-近鄰演算法是所有的機器學習演算法內上簡單的之一。

無論是分類抑是迴歸，衡量厝邊的權重攏非常有路用，使較近厝邊的權重較遠厝邊的權重大。比如講，一種捷看的加權方案是予逐个厝邊頭尾權重才值為一 / d，其中 d 是到厝邊的距離。

厝邊攏取自一組已經正確分類（佇回歸的狀況下，指屬性值正確）的東西。雖然無要求明確的訓練步數，但是這嘛會當做是此演算法的一个訓練平本集。

k-近鄰演算法的缺點是對資料的局部結構足敏感的。

K-平均演算法嘛是時行的機器學習技術，這个名和 k-近鄰演算法相倚，猶毋過兩个人無要緊。資料標準化會當大大提高這个該演算法的準確性。

演算法

訓練樣本是多維特徵的空間向量，其中每一个訓練樣本帶有一个類別標籤。演算法的訓練的階段只包含儲存的特徵向量佮訓練平本的標籤。

佇分類階段，_ k _ 是一種使用者定義的常數。一个無類別標籤的向量（查詢抑是測試點）將被歸類做最近該點的 _ k _ 平本點內底上捷捷使用的一類。

一般情形下，將歐氏距離作為距離度量，但是這是干焦適用佇連續變數。佇文字分類這種離散變數情形下，另外一个量——重疊度量（或者是海明距離）會當提來做度量。譬如講對基因表達微陣列資料，_ k _-NN 嘛佮 Pearson 和 Spearman 相關係數敆起來使用。通常情況下，若是運用一寡特殊的演算法來計算度量來講，_ k _ 近鄰分類精度會當提懸，如運用大間隔這陣厝邊抑是厝邊隔壁分析法。

「 多數表決」分類會佇類別分佈歪斜的時出現缺陷。也就是講，出現頻率較濟的樣本將會主導測試點的預測結果，因為𪜶較大可能出現咧試點的 K 鄰域來測試點的屬性閣是通過 _ k _ 鄰域內的模樣本計算出來的。解決這个缺點的方法之一是佇咧進行分類的時陣將樣本到 _ k _ 較近的距離考慮入去。_ k _ 近鄰點內底每一个的分類（對回歸問題來講，是數值）攏乘和試點之間距離的成反比的權重。另外一種克服歪斜的方式是通過資料表示形式的抽象。比如講，佇自組織對映（SOM）中，逐个節點是相仝的點的一个樹仔的代表（中心）， 和𪜶佇原始訓練資料的密度無關係。_ K _-NN 會當應用會著 SOM 中。

參數選擇

按怎選擇一个上好的 K 值得決定的資料。一般情形下，咧分類時陣較大的 K 值會當減少雜訊的影響，毋過會當類別之間的界限變甲霧嗄嗄。一个較好的 K 值能通過各種啟發式技術（見超參數最佳化）來取得。

噪音佮非相關性特徵的存在，抑是特徵尺度佮𪜶的重要性無一致會使 K 近鄰演算法的準確性嚴重降低。對選取佮縮放特徵來改善分類已經作足濟研究。一个普遍的做法是利用進化演算法最佳化功能擴充，猶閣有一種較普遍的方法是利用訓練平本的互相資訊進行選擇特徵。

佇咧二箍（兩類）分類問題當中，選取 _ k _ 為奇數有幫贊避免兩个分類平票的情形。對遮的問題下，選取最佳經驗 _ k _ 值的方法是𪜶自助法。

加權最近鄰分類器

k-最近鄰分類器會當看做是 k 最近厝邊分配權重 $ 一 / k $ 閣再替所有其他的厝邊隔壁分配零權重。這會當推廣到加權最近鄰分類器。也就是講，第 i 近來的厝邊予人權重 $ w _ { ni } $，其中 $ \ sum _ { i=一 } ^ { n } w _ { ni }=一 $。關於加權最近鄰分類器的強一致性的類似結果嘛成立。

設 $ C _ { n } ^ { wnn } $ 表示權重為 $ \ { w _ { ni } \ } _ { i=一 } ^ { n } $ 的加權最近鄰分類器。根據類別分布的規律性條件，超額的風險有以下漸漸展開

$ { \ mathcal { R } } _ { \ mathcal { R } } ( C _ { n } ^ { wnn } )-{ \ mathcal { R } } _ { \ mathcal { R } } ( C ^ { Bayes } )=\ left ( B _ { 一 } s _ { n } ^ { 二 } + B _ { 二 } t _ { n } ^ { 二 } \ right ) \ { 一 + o ( 一 ) \ } , $

嘿常數 $ B _ { 一 } $ and $ B _ { 二 } $ 當 $ s _ { n } ^ { 二 }=\ sum _ { i=一 } ^ { n } w _ { ni } ^ { 二 } $ 並且 $ t _ { n }=n ^ { 鋪二 / d } \ sum _ { i=一 } ^ { n } w _ { ni } \ { i ^ { 一 + 二 / d }-( i 影一 ) ^ { 一 + 二 / d } \ } $。

最佳加權方案 $ \ { w _ { ni } ^ { * } \ } _ { i=一 } ^ { n } $ 用佇平衡面頂顯示中的兩項，如下所示：令 $ k ^ { * }=\ lfloor Bn ^ { \ frac { 四 } { d + 四 } } \ rfloor $，

$ w _ { ni } ^ { * }={ \ frac { 一 } { k ^ { * } } } \ left [一 + { \ frac { d } { 二 } }-{ \ frac { d } { 二 { k ^ { * } } ^ { 二 / d } } } \ { i ^ { 一 + 二 / d }-( i 影一 ) ^ { 一 + 二 / d } \ } \ right] $ 著 $ i=一 , 二 , \ dots , k ^ { * } $ 並且

$ w _ { ni } ^ { * }=零 $ 著 $ i=k ^ { * } + 一 , \ dots , n $ .

利用最佳權重，超額風險的漸漸展開中的主項是 $ { \ mathcal { O } } ( n ^ {-{ \ frac { 四 } { d + 四 } } } ) $。當使用 bagged 最近鄰分類器時，類似的結果嘛是按呢。

屬性

原始素素的演算法通過算測試點著儲存樣本點的距離是較會實現的，毋過伊屬於有計算密集型的，特別是做訓練平本集變大時，計算量嘛會綴咧增加。久年來，真濟用來減少無必要距離評價的近鄰搜揣演算法已經予提出來。使用一款合適的近鄰搜揣演算法會當使 K 近鄰演算法的計算變著簡單真濟。

近鄰演算法具有較強的一致性結果。綴資料無限制，演算法保證錯誤率袂超過貝葉斯演算法錯誤率的兩倍。對一寡 K 值，K 近鄰保證錯誤率袂超過貝葉斯的。

決策彼號邊界

近鄰演算法能用一種有效的方式隱含的計算決策邊界。另外咧，伊嘛會當顯式的計算決策佇邊界，以及有效率的按呢做計算，予得計算複雜度是邊界複雜度的函數。

連續變數估計

K 近鄰演算法嘛會當用佇連續變數估計，比如講適用反距離加權平均加个 K 近鄰點確定測試點的值。該演算法的功能有：

一 . 對目標區域抽樣計算歐式抑是馬氏距離； 二 . 佇交叉驗證後的 RMSE 基礎上選擇啟發式上好的 K 鄰域； 三 . 計算多元 k-最近厝邊的距離倒數加權平均。

發展

毋過 k 最近厝邊法因為計算量不止仔大，所以相當的耗時，Ko 佮 Seo 提出一演算法TCFP（textcategorization usingfeatureprojection）， 去試驗利用特徵投影法來降低佮分類無關係的特徵對系統的影響，而且提昇系統效能，其實驗結果顯示其分類效果佮 k 最近厝邊隔壁法相倚，毋過其運算所需時間干焦需要 k 最近厝邊法運算時間的五十分之一。

除了針對檔案分類的效率，尚有研究針對按怎促進 _ k _ 最近厝邊法咧檔案分類方面的效果，如 Han 等人佇二空空二年試利用貪婪法，針對檔案分類實在做會調整權重的 k 最近厝邊隔壁法'WAkNN（weightedadjustedk'nearestneighbor）， 以促進分類的效果；而且 Li 等人佇二空空四年提出因為無仝分類的檔案本身有數量有差，所以嘛應該愛按照訓練集合中各種分類的檔案數量，選無仝數目的最近厝邊，來參與分類。

拓展閱讀

• When Is " Nearest Neighbor " Meaningful ?
• Belur V . Dasarathy ( 編 ) . Nearest Neighbor ( NN ) Norms : NN Pattern Classification Techniques . 一千九百九十一 . ISBN  空九八千一百八十六分八千九百三十五七 .
• Shakhnarovish , Darrell , and Indyk ( 編 ) . Nearest-Neighbor Methods in Learning and Vision . MIT Press . 兩千空五 . ISBN  空五二百六十二鋪一四九千五百四十七-X .
• Mäkelä H Pekkarinen A . Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data . Forest Ecology and Management . 二千空四淋七鋪二十六 ,一百九十六( 二–三 ) : 兩百四十五–兩百五十五 . doi : 十曉一空一六 / j . foreco . 二千空四孵空二 . 四十九 .
• Fast k nearest neighbor search using GPU . In Proceedings of the CVPR Workshop on Computer Vision on GPU , Anchorage , Alaska , USA , June 兩千空八 . V . Garcia and E . Debreuve and M . Barlaud .
• Scholarpedia article on _ k _-NN
• google-all-pairs-similarity-search