K最近鄰分類演算法
出自 MBA智库百科(https://wiki.mbalib.com/)
K最近鄰分類演算法（K-NearestNeighbor Classification Algorithm）
目錄 |
K最近鄰(KNN，K-NearestNeighbor)分類演算法是指數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是K個最近的鄰居的意思，說的是每個樣本都可以用它最接近的K個鄰居來代表。
KNN演算法的核心思想是如果一個樣本在特征空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的K個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。
1. 準備數據，對數據進行預處理。
3. 設定參數，如K。
4.維護一個大小為K的的按距離由大到小的優先順序隊列，用於存儲最近鄰訓練元組。隨機從訓練元組中選取K個元組作為初始的最近鄰元組，分別計算測試元組到這K個元組的距離，將訓練元組標號和距離存入優先順序隊列。
5. 遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L與優先順序隊列中的最大距離Lmax。
6. 進行比較。若L>=Lmax，則捨棄該元組，遍歷下一個元組。若L<Lmax，刪除優先順序隊列中最大距離的元組，將當前訓練元組存入優先順序隊列。
7. 遍歷完畢，計算優先順序隊列中K個元組的多數類，並將其作為測試元組的類別。
8. 測試元組集測試完畢後計算誤差率，繼續設定不同的K值重新進行訓練，最後取誤差率最小的K值。
優點
1.簡單，易於理解，易於實現，無需估計參數，無需訓練；
2. 適合對稀有事件進行分類；
3.特別適合於多分類問題(multi-modal,對象具有多個類別標簽)， KNN比SVM的表現要好。
缺點
該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。 該演算法只計算“最近的”鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。
可理解性差，無法給出像決策樹那樣的規則。
KNN演算法因其提出時間較早，隨著其他技術的不斷更新和完善，KNN演算法的諸多不足之處也逐漸顯露，因此許多KNN演算法的改進演算法也應運而生。
針對以上演算法的不足，演算法的改進方向主要分成了分類效率和分類效果兩方面。
分類效率：事先對樣本屬性進行約簡，刪除對分類結果影響較小的屬性，快速的得出待分類樣本的類別。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
分類效果：採用權值的方法（和該樣本距離小的鄰居權值大）來改進，Han等人於2002年嘗試利用貪心法，針對文件分類實做可調整權重的K最近鄰居法WAKNN (weighted adjusted K nearest neighbor)，以促進分類效果；而Li等人於2004年提出由於不同分類的文件本身有數量上有差異，因此也應該依照訓練集合中各種分類的文件數量，選取不同數目的最近鄰居，來參與分類。
如右圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下麵，我們就要解決這個問題：給這個綠色的圓分類。
我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特征的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據麽，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。
如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。
於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特征，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
