人工智能之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∈{c1,c2,...,cK}和測試數據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算法在人工智能之機器學習、字符識別、文本分類、圖像識別等領域有著廣泛應用。

關鍵詞： 人工智能 KNN