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

　　前言：人工智能機器學(xué)習有關(guān)算法內容，請參見(jiàn)公眾號“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機器學(xué)習主要有三大類(lèi):1)分類(lèi);2)回歸;3)聚類(lèi)。今天我們重點(diǎn)探討一下K近鄰(KNN)算法。 ^_^

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

　　KNN概念：

　　K近鄰算法KNN就是給定一個(gè)訓練數據集，對新的輸入實(shí)例，在訓練數據集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例(K個(gè)鄰居)，這K個(gè)實(shí)例的多數屬于某個(gè)類(lèi)，就把該輸入實(shí)例分類(lèi)到這個(gè)類(lèi)中。

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

　　通俗地講，就是“物以類(lèi)聚，人以群分”。

　　分類(lèi)策略，就是“少數從屬于多數”。

　　算法描述：

　　KNN沒(méi)有顯示的訓練過(guò)程，在測試時(shí)，計算測試樣本和所有訓練樣本的距離，根據最近的K個(gè)訓練樣本的類(lèi)別，通過(guò)多數投票的方式進(jìn)行預測。具體算法描述如下：

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

　　輸出：實(shí)例x所屬的類(lèi)別

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

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

　　核心思想：

　　當無(wú)法判定當前待分類(lèi)點(diǎn)是從屬于已知分類(lèi)中的哪一類(lèi)時(shí)，依據統計學(xué)的理論看它所處的位置特征，衡量它周?chē)従拥臋嘀?，而把它歸為到權重更大的那一類(lèi)中。

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

　　KNN算法中，所選擇的鄰居都是已經(jīng)正確分類(lèi)的對象。KNN算法在定類(lèi)決策上只依據最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬的類(lèi)別。

　　算法要素：

　　KNN 算法有3個(gè)基本要素：

　　1)K值的選擇：K值的選擇會(huì )對算法的結果產(chǎn)生重大影響。K值較小意味著(zhù)只有與輸入實(shí)例較近的訓練實(shí)例才會(huì )對預測結果起作用，但容易發(fā)生過(guò)擬合;如果 K 值較大，優(yōu)點(diǎn)是可以減少學(xué)習的估計誤差，但缺點(diǎn)是學(xué)習的近似誤差增大，這時(shí)與輸入實(shí)例較遠的訓練實(shí)例也會(huì )對預測起作用，使預測發(fā)生錯誤。在實(shí)際應用中，K 值一般選擇一個(gè)較小的數值，通常采用交叉驗證的方法來(lái)選擇最優(yōu)的 K 值。隨著(zhù)訓練實(shí)例數目趨向于無(wú)窮和 K=1 時(shí)，誤差率不會(huì )超過(guò)貝葉斯誤差率的2倍，如果K也趨向于無(wú)窮，則誤差率趨向于貝葉斯誤差率。

　　2)距離度量：距離度量一般采用 Lp 距離，當p=2時(shí)，即為歐氏距離，在度量之前，應該將每個(gè)屬性的值規范化，這樣有助于防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過(guò)大。

　　對于文本分類(lèi)來(lái)說(shuō)，使用余弦(cosine)來(lái)計算相似度就比歐式(Euclidean)距離更合適。

　　3)分類(lèi)決策規則：該算法中的分類(lèi)決策規則往往是多數表決，即由輸入實(shí)例的K個(gè)最臨近的訓練實(shí)例中的多數類(lèi)決定輸入實(shí)例的類(lèi)別。

　　算法流程：

　　1)準備數據，對數據進(jìn)行預處理。

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

　　3)設定參數，如K。

　　4)維護一個(gè)距離由大到小的優(yōu)先級隊列(長(cháng)度為K)，用于存儲最近鄰訓練元組。隨機從訓練元組中選取K個(gè)元組作為初始的最近鄰元組，分別計算測試元組到這K個(gè)元組的距離，將訓練元組標號和距離存入優(yōu)先級隊列。

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

　　6)進(jìn)行比較。若L>=Lmax，則舍棄該元組，遍歷下一個(gè)元組。若L

　　7)遍歷完畢，計算優(yōu)先級隊列中K個(gè)元組的多數類(lèi)，并將其作為測試元組的類(lèi)別。

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

　　算法優(yōu)點(diǎn)：

　　1)KNN從原理上也依賴(lài)于極限定理，但在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。

　　2)由于KNN方法主要靠周?chē)邢薜泥徑臉颖?，而不是靠判別類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。

　　3)算法本身簡(jiǎn)單有效，精度高,對異常值不敏感,易于實(shí)現，無(wú)需估計參數，分類(lèi)器不需要使用訓練集進(jìn)行訓練，訓練時(shí)間復雜度為0。

　　4)KNN 分類(lèi)的計算復雜度和訓練集中的文檔數目成正比，即，如果訓練集中文檔總數為n，那么KNN的分類(lèi)時(shí)間復雜度為O(n)。

　　5)適合對稀有事件進(jìn)行分類(lèi)。

　　6)特別適合于多分類(lèi)問(wèn)題(multi-modal),對象具有多個(gè)類(lèi)別標簽，kNN比SVM的表現要好。

　　算法缺點(diǎn)：

　　1)當樣本不平衡時(shí)，樣本數量并不能影響運行結果。

　　2)算法計算量較大;

　　3)可理解性差，無(wú)法給出像決策樹(shù)那樣的規則。

　　改進(jìn)策略：

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

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

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

　　改進(jìn)3：事先對已知樣本點(diǎn)進(jìn)行剪輯(editing技術(shù))，事先去除(condensing技術(shù))對分類(lèi)作用不大的樣本。該算法比較適用于樣本容量比較大的類(lèi)域的自動(dòng)分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(chǎn)生誤分。

　　考慮因素：

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

　　應用場(chǎng)景：

　　K 近鄰算法應用場(chǎng)景包括機器學(xué)習、字符識別、文本分類(lèi)、圖像識別等領(lǐng)域。

　　結語(yǔ):

　　K近鄰算法KNN,也叫K最近鄰算法，是機器學(xué)習研究的一個(gè)活躍領(lǐng)域。最簡(jiǎn)單的暴力算法，比較適合小數據樣本。K近鄰算法使用的模型實(shí)際上對應于對特征空間的劃分。KNN算法不僅可以用于分類(lèi)，還可以用于回歸。KNN算法在人工智能之機器學(xué)習、字符識別、文本分類(lèi)、圖像識別等領(lǐng)域有著(zhù)廣泛應用。