K-近邻算法

在圖型識別領域中，**最近鄰居法**（**KNN** 演算法，又譯 **K - 近鄰演算法**）是一種用於分類和迴歸的無母數統計方法。在這兩種情況下，輸入包含特徵空間中的_**k**_個最接近的訓練樣本。

　
: * 在 _k-NN 分類_中，輸出是一個分類族群。一個物件的分類是由其鄰居的「多數表決」確定的，_k_ 個最近鄰居（_k_ 為正整數，通常較小）中最常見的分類決定了賦予該物件的類別。若 _k_= 1，則該物件的類別直接由最近的一個節點賦予。

　
: * 在 _k-NN 迴歸_中，輸出是該物件的屬性值。該值是其 _k_ 個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN 是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k - 近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是迴歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為 1/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 最近鄰居分配權重 $1/k$ 以及為所有其他鄰居分配 0 權重。這可以推廣到加權最近鄰分類器。也就是說，第 i 近的鄰居被賦予權重 $w_{ni}$ ，其中 $\sum _{i=1}^{n}w_{ni}=1$ 。關於加權最近鄰分類器的強一致性的類似結果也成立。

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

　
: ${\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$

對常數 $B_{1}$ and $B_{2}$ 當 $s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}$ 並且 $t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}$ 。

最佳加權方案 $\{w_{ni}^{*}\}_{i=1}^{n}$ 用於平衡上面顯示中的兩個項，如下所示：令 $k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor $ ，

　
: $w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]$ 對 $i=1,2,\dots ,k^{*}$ 並且

　
: $w_{ni}^{*}=0$ 對 $i=k^{*}+1,\dots ,n$ .

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

## 屬性

原始樸素的演算法通過計算測試點到儲存樣本點的距離是比較容易實現的，但它屬於計算密集型的，特別是當訓練樣本集變大時，計算量也會跟著增大。多年來，許多用來減少不必要距離評價的近鄰搜尋演算法已經被提出來。使用一種合適的近鄰搜尋演算法能使 K 近鄰演算法的計算變得簡單許多。

近鄰演算法具有較強的一致性結果。隨著資料趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些 K 值，K 近鄰保證錯誤率不會超過貝葉斯的。

## 決策邊界

近鄰演算法能用一種有效的方式隱含的計算決策邊界。另外，它也可以顯式的計算決策邊界，以及有效率的這樣做計算，使得計算複雜度是邊界複雜度的函數。

## 連續變數估計

K 近鄰演算法也適用於連續變數估計，比如適用反距離加權平均多個 K 近鄰點確定測試點的值。該演算法的功能有：

1. 從目標區域抽樣計算歐式或馬氏距離；
2. 在交叉驗證後的 RMSE 基礎上選擇啟發式最佳的 K 鄰域；
3. 計算多元 k - 最近鄰居的距離倒數加權平均。

## 發展

然而 k 最近鄰居法因為計算量相當的大，所以相當的耗時，Ko 與 Seo 提出一演算法 **TCFP**（**t**ext **c**ategorization using **f**eature **p**rojection），嘗試利用特徵投影法來降低與分類無關的特徵對於系統的影響，並藉此提昇系統效能，其實驗結果顯示其分類效果與 k 最近鄰居法相近，但其運算所需時間僅需 k 最近鄰居法運算時間的五十分之一。

除了針對檔案分類的效率，尚有研究針對如何促進 _k_ 最近鄰居法在檔案分類方面的效果，如 Han 等人於 2002 年嘗試利用貪婪法，針對檔案分類實做可調整權重的 k 最近鄰居法 **WAkNN**（**w**eighted **a**djusted **k** **n**earest **n**eighbor），以促進分類效果；而 Li 等人於 2004 年提出由於不同分類的檔案本身有數量上有差異，因此也應該依照訓練集合中各種分類的檔案數量，選取不同數目的最近鄰居，來參與分類。

## 參見

## 注釋

## 參考文獻

### 參照

### 來源

## 拓展閱讀

* When Is "Nearest Neighbor" Meaningful?（頁面存檔備份，存於網際網路檔案館）
* Belur V. Dasarathy (編). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. 1991. ISBN 0-8186-8930-7.
* Shakhnarovish, Darrell, and Indyk (編). Nearest-Neighbor Methods in Learning and Vision. MIT Press. 2005. ISBN 0-262-19547-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. 2004-07-26, **196** (2–3): 245–255. doi:10.1016/j.foreco.2004.02.049.
* Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
* Scholarpedia article on _k_-NN （頁面存檔備份，存於網際網路檔案館）
* google-all-pairs-similarity-search （頁面存檔備份，存於網際網路檔案館）