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

　　前言：人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，請(qǐng)參見公眾號(hào)“科技優(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í)際上對(duì)應(yīng)于對(duì)特征空間的劃分。KNN算法不僅可以用于分類，還可以用于回歸。

　　KNN概念：

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

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

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

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

　　算法描述：

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

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

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

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

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

　　核心思想：

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

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

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

　　算法要素：

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

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

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

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

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

　　算法流程：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　算法缺點(diǎn)：

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

　　2)算法計(jì)算量較大;

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

　　改進(jìn)策略：

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

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

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

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

　　考慮因素：

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

　　應(yīng)用場(chǎng)景：

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

　　結(jié)語(yǔ):

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