K-近鄰演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的無母數統計方法，由美國統計學家伊芙琳·費克斯和小約瑟夫·霍奇斯於1951年首次提出，後來由托馬斯·M·寇弗擴展。在這兩種情況下，輸入包含特徵空間中的k個最接近的訓練樣本。

- 在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k = 1，則該對象的類別直接由最近的一個節點賦予。
- 在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

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

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

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-平均演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關係。數據標準化可以大大提高該演算法的準確性。

## 演算法

<image>

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

在分類階段，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 ^{wnn}_n$表示權重為$\{w_{ni}\}_{i = 1}^n$的加權最近鄰分類器。根據類別分布的規律性條件，超額風險具有以下漸近展開

$$\mathcal{R}_\mathcal{R}(C^{wnn}_{n}) - \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 B n ^{\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} })$。當使用自助聚合時，類似的結果也是如此。

## 屬性

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

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

## 決策邊界

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

## 連續變量估計

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

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

## 發展

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

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

## 拓展閱讀

- When Is "Nearest Neighbor" Meaningful?
- 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