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

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

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è)類(lèi)，就把該輸入實(shí)例分類(lèi)到這個(gè)類(lèi)中。

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

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

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

算法描述：

KNN沒(méi)有顯示的訓(xùn)練過(guò)程，在測(cè)試時(shí)，計(jì)算測(cè)試樣本和所有訓(xùn)練樣本的距離，根據(jù)最近的K個(gè)訓(xùn)練樣本的類(lèi)別，通過(guò)多數(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所屬的類(lèi)別

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

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

核心思想：

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

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

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

算法要素：

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

1)K值的選擇：K值的選擇會(huì)對(duì)算法的結(jié)果產(chǎn)生重大影響。K值較小意味著只有與輸入實(shí)例較近的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用，但容易發(fā)生過(guò)擬合;如果 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ì)超過(guò)貝葉斯誤差率的2倍，如果K也趨向于無(wú)窮，則誤差率趨向于貝葉斯誤差率。

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

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

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

算法流程：

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ù)類(lèi)，并將其作為測(cè)試元組的類(lèi)別。

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

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

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

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

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

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

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

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

算法缺點(diǎn)：

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

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

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

改進(jìn)策略：

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

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

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

改進(jìn)3：事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯(editing技術(shù))，事先去除(condensing技術(shù))對(duì)分類(lèi)作用不大的樣本。該算法比較適用于樣本容量比較大的類(lèi)域的自動(dòng)分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(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í)別、文本分類(lèi)、圖像識(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算法不僅可以用于分類(lèi)，還可以用于回歸。KNN算法在人工智能之機(jī)器學(xué)習(xí)、字符識(shí)別、文本分類(lèi)、圖像識(shí)別等領(lǐng)域有著廣泛應(yīng)用。

關(guān)鍵詞： 人工智能 KNN