人工智慧–K近鄰演算法

人工智慧之K近鄰演算法（KNN）

前言：人工智慧機器學習有關演算法內容，請參見公眾號「科技優化生活」之前相關文章。人工智慧之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下K近鄰（KNN）演算法。 ^_^

K近鄰KNN(k-Nearest Neighbor)演算法,也叫K最近鄰演算法，1968年由 Cover 和 Hart 提出，是機器學習演算法中比較成熟的演算法之一。K近鄰演算法使用的模型實際上對應於對特徵空間的劃分。KNN演算法不僅可以用於分類，還可以用於回歸。

KNN概念：

K近鄰演算法KNN就是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例（K個鄰居），這K個實例的多數屬於某個類，就把該輸入實例分類到這個類中。

如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。K近鄰演算法使用的模型實際上對應於對特徵空間的劃分。

通俗地講，就是「物以類聚，人以群分」。

分類策略，就是「少數從屬於多數」。

演算法描述：

KNN沒有顯示的訓練過程，在測試時，計算測試樣本和所有訓練樣本的距離，根據最近的K個訓練樣本的類別，通過多數投票的方式進行預測。具體演算法描述如下：

輸入：訓練數據集T={(x1,y1),(x2,y2),...,(xn,yn)}，其中xi∈Rn,yi∈和測試數據x

輸出：實例x所屬的類別

1) 根據給定的距離度量，在訓練集T中找到與x距離最近的k個樣本，涵蓋這k個點的x的鄰域記作Nk(x)。

2）在Nk(x)中根據分類規則(如多數表決)確定x的類別y：

核心思想：

當無法判定當前待分類點是從屬於已知分類中的哪一類時，依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為到權重更大的那一類中。

kNN的輸入是測試數據和訓練樣本數據集，輸出是測試樣本的類別。

KNN演算法中，所選擇的鄰居都是已經正確分類的對象。KNN演算法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

演算法要素：

KNN演算法有3個基本要素：

1）K值的選擇：K值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，使預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。

2）距離度量：距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規範化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。

對於文本分類來說，使用餘弦(cosine)來計算相似度就比歐式(Euclidean)距離更合適。

3）分類決策規則：該演算法中的分類決策規則往往是多數表決，即由輸入實例的K個最臨近的訓練實例中的多數類決定輸入實例的類別。

演算法流程：

1)準備數據，對數據進行預處理。

2)選用合適的數據結構存儲訓練數據和測試元組。

3)設定參數，如K。

4)維護一個距離由大到小的優先順序隊列（長度為K），用於存儲最近鄰訓練元組。隨機從訓練元組中選取K個元組作為初始的最近鄰元組，分別計算測試元組到這K個元組的距離，將訓練元組標號和距離存入優先順序隊列。

5)遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L與優先順序隊列中的最大距離Lmax。

6)進行比較。若L>=Lmax，則捨棄該元組，遍歷下一個元組。若L

7)遍歷完畢，計算優先順序隊列中K個元組的多數類，並將其作為測試元組的類別。

8)測試元組集測試完畢後計算誤差率，繼續設定不同的K值重新進行訓練，最後取誤差率最小的K值。

演算法優點：

1）KNN從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。

2）由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

3）演算法本身簡單有效，精度高,對異常值不敏感,易於實現，無需估計參數，分類器不需要使用訓練集進行訓練，訓練時間複雜度為0。

4）KNN 分類的計算複雜度和訓練集中的文檔數目成正比，即，如果訓練集中文檔總數為n，那麼KNN的分類時間複雜度為O(n)。

5）適合對稀有事件進行分類。

6）特別適合於多分類問題(multi-modal),對象具有多個類別標籤，kNN比SVM的表現要好。

演算法缺點：

1）當樣本不平衡時，樣本數量並不能影響運行結果。

2）演算法計算量較大；

3）可理解性差，無法給出像決策樹那樣的規則。

改進策略：

KNN演算法因其提出時間較早，隨著其他技術的不斷更新和完善，KNN演算法逐漸顯示出諸多不足之處，因此許多KNN演算法的改進演算法也應運而生。演算法改進目標主要朝著分類效率和分類效果兩個方向。

改進1：通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。

改進2：將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比（1/d），即和該樣本距離小的鄰居權值大，稱為可調整權重的K最近鄰居法WAKNN(weighted adjusted K nearestneighbor)。但WAKNN會造成計算量增大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。

改進3：事先對已知樣本點進行剪輯(editing技術)，事先去除(condensing技術)對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

考慮因素：

實現 K 近鄰演算法時，主要考慮的因素是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時是非常必要的。

應用場景：

K 近鄰演算法應用場景包括機器學習、字元識別、文本分類、圖像識別等領域。

結語:

K近鄰演算法KNN,也叫K最近鄰演算法，是機器學習研究的一個活躍領域。最簡單的暴力演算法，比較適合小數據樣本。K近鄰演算法使用的模型實際上對應於對特徵空間的劃分。KNN演算法不僅可以用於分類，還可以用於回歸。KNN演算法在人工智慧之機器學習、字元識別、文本分類、圖像識別等領域有著廣泛應用。

------以往文章推薦------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！