鄰近算法

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由 Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路非常簡單直觀：如果一個樣本在特徵空間中的K個最相似（即特徵空間中最鄰近）的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別 ^[2]  。

該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最鄰近點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種 Reverse KNN法，它能降低KNN算法的計算複雜度，提高分類的效率 ^[2]  。

KNN算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種算法比較容易產生誤分 ^[2]  。

KNN算法的核心思想是，如果一個樣本在特徵空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來説，KNN方法較其他方法更為適合。

總體來説，KNN分類算法包括以下4個步驟： ^[3] 

①準備數據，對數據進行預處理 ^[3]  。

②計算測試樣本點（也就是待分類點）到其他每個樣本點的距離 ^[3]  。

③對每個距離進行排序，然後選擇出距離最小的K個點 ^[3]  。

④對K個點所屬的類別進行比較，根據少數服從多數的原則，將測試樣本點歸入在K個點中佔比最高的那一類 ^[3]  。

KNN方法思路簡單，易於理解，易於實現，無需估計參數 ^[4]  。

該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數 ^[5]  。

該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點 ^[5]  。

目前對KNN算法改進的方向主要可以分為4類： ^[6] 

一是尋求更接近於實際的距離函數以取代標準的歐氏距離，典型的工作包括 WAKNN、VDM ^[6]  ；

二是搜索更加合理的K值以取代指定大小的K值典型的工作包括SNNB、 DKNAW ^[6]  ；

三是運用更加精確的概率估測方法去取代簡單的投票機制，典型的工作包括 KNNDW、LWNB、 ICLNB ^[6]  ；

四是建立高效的索引，以提高KNN算法的運行效率，代表性的研究工作包括 KDTree、 NBTree。還有部分研究工作綜合了以上的多種改進方法 ^[6]  。