基本介紹
- 中文名：k最鄰近分類算法
- 外文名：k-NearestNeighbor
- 簡稱：kNN算法
- 含義：每個樣本都可以用它最接近的k個鄰近值來代表
- 範疇：數據挖掘分類技術
- 用途：用於分類，對未知事物的識別
簡介,核心思想,算法流程,優點,缺點,改進策略,
簡介
KNN（K- Nearest Neighbor）法即K最鄰近法，最初由 Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路非常簡單直觀：如果她記拔一個樣本在特徵空間中殃櫻獄采的K個最相似（即特徵空間中最鄰近）的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者付乘凳幾個樣本的類別來決定待分樣本所屬的類別。
該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最鄰近點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種 Reverse KNN法，它能降低KNN算法的計算複雜度，提高分類的效率。
KNN算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域判勸祝採用這種算法比較容易產生誤分。
核心思想
KNN算法的核心思想是，如果一個樣本在特徵空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
算法流程
總體來說，KNN分類算法包括以下4個步驟：
①準備數據，對數據進行預處理。
②計算測試樣本點（也就是待分類點）到其他每個樣本點的距離。
③對每個距離進行排序，然後選擇出距離最小的K個點。
④對K個點所屬的類別進行比較，根據少數服從多數的原則，將測試樣本點歸入在K個點中占比最高的那一類。
優點
KNN方法思路簡單，易於理解，易於實現，無需估計參數。
缺點
該算法在分類時有個主要的不頌姜院足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類烏朽樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。
改進策略
目前對KNN算法改進的方向主要可以分為4類：
一是尋求更接近於實際的距離函式以取頁燥剃邀代標準的歐氏距離，典型的工作包括 WAKNN、VDM；
二是搜尋更加合理的K值以取代指定大小的K值典型的工作包括SNNB、 DKNAW；
三是運用更加精確的機率估測方法去取代簡單的投票機制，典型的工作包括 KNNDW、LWNB、 ICLNB；
四是建立高效的索引，以提高KNN算法的運行效率，代表性的研究工作包括 KDTree、 NBTree。還有部分研究工作綜合了以上的多種改進方法。
四是建立高效的索引，以提高KNN算法的運行效率，代表性的研究工作包括 KDTree、 NBTree。還有部分研究工作綜合了以上的多種改進方法。
