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

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

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

　　KNN概念：

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

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

　　通俗地講，就是“物以類聚，人以群分”。

　　分類策略，就是“少數(shù)從屬于多數(shù)”。

　　算法描述：

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

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

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

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

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

　　核心思想：

　　當(dāng)無法判定當(dāng)前待分類點(diǎn)是從屬于已知分類中的哪一類時，依據(jù)統(tǒng)計學(xué)的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重，而把它歸為到權(quán)重更大的那一類中。

　　kNN的輸入是測試數(shù)據(jù)和訓(xùn)練樣本數(shù)據(jù)集，輸出是測試樣本的類別。

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

　　算法要素：

　　KNN 算法有3個基本要素：

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

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

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

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

　　算法流程：

　　1)準(zhǔn)備數(shù)據(jù)，對數(shù)據(jù)進(jìn)行預(yù)處理。

　　2)選用合適的數(shù)據(jù)結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)和測試元組。

　　3)設(shè)定參數(shù)，如K。

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

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

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

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

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

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

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

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

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

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

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

　　6)特別適合于多分類問題(multi-modal),對象具有多個類別標(biāo)簽，kNN比SVM的表現(xiàn)要好。

　　算法缺點(diǎn)：

　　1)當(dāng)樣本不平衡時，樣本數(shù)量并不能影響運(yùn)行結(jié)果。

　　2)算法計算量較大;

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

　　改進(jìn)策略：

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

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

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

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

　　考慮因素：

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

　　應(yīng)用場景：

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

　　結(jié)語:

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