資料挖掘十大經典算法——kNN

資料挖掘十大經典算法(8) kNN

1、K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空 間中最鄰近)的樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别。

2、KNN算法中，所選擇的鄰居都是已經正确分類的對象。該方法在定類決策上隻依據最鄰近的一個或者幾個樣本的類别來決定待分樣本所屬的類别。 KNN方法雖然從原理上也依賴于極限定理，但在類别決策時，隻與極少量的相鄰樣本有關。由于KNN方法主要靠周圍有限的鄰近的樣本， 而不是靠判别類域的方法來确定所屬類别的，是以對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為适合。

3、KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，将這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是将不同距離的 鄰居對該樣本産生的影響給予不同的權值(weight)，如權值與距離成正比。

4、 該算法在分類時有個主要的不足是 ，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導緻當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。是以可以采用權值的方法（和該樣本距離小的鄰居權值大）來改進。

算法分類過程如下：

1 首先我們事先定下k值（就是指k近鄰方法的k的大小，代表對于一個待分類的資料點，我們要尋找幾個它的鄰居）。這邊為了說明問題，我們取兩個k值，分别為3和9；

2 根據事先确定的距離度量公式（如：歐氏距離），得出待分類資料點和所有已知類别的樣本點中，距離最近的k個樣本。

3 統計這k個樣本點中，各個類别的數量。根據k個樣本中，數量最多的樣本是什麼類别，我們就把這個資料點定為什麼類别。

訓練樣本是多元特征空間向量，其中每個訓練樣本帶有一個類别标簽。算法的訓練階段隻包含存儲的特征向量和訓練樣本的标簽。 在分類階段，k是一個使用者定義的常數。一個沒有類别标簽的向量 （查詢或測試點）将被歸類為最接近該點的K個樣本點中最頻繁使用的一類。

一般情況下，将歐氏距離作為距離度量，但是這是隻适用于連續變量。在文本分類這種非連續變量情況下，

另一個度量——重疊度量（或海明距離）可以用來作為度量。通常情況下，如果運用一些特殊的算法來計算度量的話，K近鄰分類精度可顯著提高，如運用大邊緣最近鄰法或者近鄰成分分析法。

“多數表決”分類的一個缺點是出現頻率較多的樣本将會主導測試點的預測結果，那是因為他們比較大可能出現在測試點的K鄰域而測試點的屬性又是通過K領域内的樣本計算出來的。解決這個缺點的方法之一是在進行分類時将樣本到測試點的距離考慮進去。

K值得選擇

如何選擇一個最佳的K值取決于資料。一般情況下，在分類時較大的K值能夠減小噪聲的影響。但會使類别之間的界限變得模糊。一個較好的K值能通過各種啟發式技術來擷取，比如，交叉驗證。

噪聲和非相關性特征向量的存在會使K近鄰算法的準确性減小。對于選擇特征向量進行分類已經作了很多研究。一個普遍的做法是利用進化算法優化功能擴充[3]，還有一種較普遍的方法是利用訓練樣本的互資訊進行選擇特征。

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

1、從目标區域抽樣計算歐式或馬氏距離；

2、在交叉驗證後的RMSE基礎上選擇啟發式最優的K鄰域；

3、計算多元k-最近鄰居的距離倒數權重平均。