人工智能之K近鄰算法(KNN)
前言:人工智能機(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)用。
您可能也感興趣:
今日熱點(diǎn)
為您推薦
8家險(xiǎn)企股權(quán)被掛牌轉(zhuǎn)讓?zhuān)瑸楹坞U(xiǎn)企股權(quán)不再被追捧?
深圳最低工資標(biāo)準(zhǔn)調(diào)整為2360元/月 失業(yè)保險(xiǎn)金為2124元/月
遼寧實(shí)施失業(yè)保險(xiǎn)省級(jí)統(tǒng)籌 對(duì)缺口核定等作出詳細(xì)規(guī)定
更多
- 蕪湖釋放創(chuàng)新“N次方”效應(yīng) 數(shù)字賦能驅(qū)動(dòng)產(chǎn)業(yè)升級(jí)
- 重慶:激發(fā)人才創(chuàng)新活力,到2025年創(chuàng)新要素活躍度顯著增強(qiáng)
- 西寧加快知識(shí)產(chǎn)權(quán)強(qiáng)市建設(shè)步伐 去年兌現(xiàn)資助資金200萬(wàn)元
- 無(wú)錫錫山區(qū)全面啟動(dòng)實(shí)施“雙招雙引” 引進(jìn)高端創(chuàng)新資源
- 重慶巴南區(qū)落實(shí)創(chuàng)新驅(qū)動(dòng)發(fā)展戰(zhàn)略 以科技創(chuàng)新引領(lǐng)五大產(chǎn)業(yè)集...
- 朝陽(yáng)北票經(jīng)開(kāi)區(qū)加快推進(jìn)數(shù)字經(jīng)濟(jì)發(fā)展 推動(dòng)體制機(jī)制創(chuàng)新
- 湖北省先進(jìn)低碳冶金產(chǎn)業(yè)技術(shù)創(chuàng)新聯(lián)合體組建 打造五千億級(jí)產(chǎn)...
- 重慶渝北將優(yōu)化創(chuàng)新生態(tài)環(huán)境 培育打造一批引領(lǐng)型的科創(chuàng)載體
更多
- 山東抓投資抓項(xiàng)目 新興領(lǐng)域投資規(guī)模持續(xù)擴(kuò)大
- 2021年各地引資成績(jī)單亮眼 迸發(fā)出巨大經(jīng)濟(jì)活力
- 多地重大項(xiàng)目投資規(guī)模力度明顯加大 新基建項(xiàng)目成重要發(fā)力點(diǎn)
- 年內(nèi)湖北新開(kāi)工城建項(xiàng)目160個(gè) 集中在道路交通等方面
- 去年我國(guó)對(duì)外投資合作平穩(wěn)發(fā)展 境外經(jīng)貿(mào)合作區(qū)建設(shè)成效顯著
- 荊州集中簽約39個(gè)項(xiàng)目 重點(diǎn)涵蓋高端裝備制造、電子信息等領(lǐng)域
- 廣東打出一系列穩(wěn)外貿(mào)政策“組合拳” 外貿(mào)逆勢(shì)創(chuàng)新高
- 蘭州新區(qū)再獲“最具投資吸引力新區(qū)” 去年新增市場(chǎng)主體5427戶(hù)
排行
最近更新
- 蕪湖釋放創(chuàng)新“N次方”效應(yīng) 數(shù)字賦能驅(qū)動(dòng)產(chǎn)業(yè)升級(jí)
- 去年快遞服務(wù)全程時(shí)限水平有較大提升 干線運(yùn)輸時(shí)限縮短
- 住建部:推動(dòng)長(zhǎng)江經(jīng)濟(jì)帶高質(zhì)量發(fā)展,打造區(qū)域協(xié)調(diào)發(fā)展新樣板
- 江蘇發(fā)布重大項(xiàng)目清單 增資擴(kuò)產(chǎn)項(xiàng)目明顯增多
- 山東抓投資抓項(xiàng)目 新興領(lǐng)域投資規(guī)模持續(xù)擴(kuò)大
- Gucci在2月將投放 10 個(gè)“SuperGucci”NFT
- 美國(guó)銀行:美國(guó)CBDC將保持美元作為世界儲(chǔ)備貨幣的地位
- 美股三大指數(shù)尾盤(pán)集體轉(zhuǎn)漲
- 光伏發(fā)電概念股有哪些?光伏發(fā)電概念龍頭股一覽
- The new iPad屏幕對(duì)比評(píng)測(cè)
- 電源接通延時(shí)器
- 汽車(chē)電子穩(wěn)定系統(tǒng)(ESP)詳解
- 聯(lián)想B520一體機(jī)拆解
- 焦炭相關(guān)股票有哪些?焦炭概念股票龍頭一覽
- 增強(qiáng)信號(hào) 3G無(wú)線上網(wǎng)卡改裝拆解全攻略
- 盤(pán)點(diǎn)全球五大智能手機(jī)生產(chǎn)商 華為聯(lián)想入圍
- 三星新平板 Galaxy Note 10.1全拆解
- 智能監(jiān)控防盜報(bào)警系統(tǒng)
- 格力電器未來(lái)三年股東回報(bào)規(guī)劃:每年累計(jì)分紅不低于當(dāng)年凈利潤(rùn)50%
- 消息稱(chēng)京東科技計(jì)劃2022年在港IPO,募資10億至20億美元
- 恒大集團(tuán):呼吁境外債權(quán)人不采取任何激進(jìn)的法律行動(dòng)
- 海航董事長(zhǎng)劉璐因個(gè)人原因辭職,在海航已近28年
- 青青稞酒預(yù)計(jì)2021年?duì)I收增長(zhǎng)30%-40%,四季度凈虧損超1500萬(wàn)
- 2022年在港上市募資10億美元?京東科技:不予置評(píng)
- 財(cái)政部修訂出臺(tái)《財(cái)政行政處罰聽(tīng)證實(shí)施辦法》
- 賣(mài)房子需要交什么稅?賣(mài)房子必須攜帶哪些證件?
- 醫(yī)??ǖ氖褂梅秶心男垦a(bǔ)牙可以使用醫(yī)保報(bào)銷(xiāo)嗎?
- 小產(chǎn)權(quán)房能過(guò)戶(hù)嗎?購(gòu)買(mǎi)小產(chǎn)權(quán)房有什么風(fēng)險(xiǎn)?
- 奕東電子的實(shí)際控制人是誰(shuí)?奕東電子股票上市了嗎?
- 百合股份是一家什么公司?百合股份的股票何時(shí)上市?
今日要聞
- 蕪湖釋放創(chuàng)新“N次方”效應(yīng) 數(shù)字賦能驅(qū)動(dòng)產(chǎn)業(yè)升級(jí)
- 去年快遞服務(wù)全程時(shí)限水平有較大提升 干線運(yùn)輸時(shí)限縮短
- 住建部:推動(dòng)長(zhǎng)江經(jīng)濟(jì)帶高質(zhì)量發(fā)展,打造區(qū)域協(xié)調(diào)發(fā)展新樣板
- 山東抓投資抓項(xiàng)目 新興領(lǐng)域投資規(guī)模持續(xù)擴(kuò)大
- Gucci在2月將投放 10 個(gè)“SuperGucci”NFT
- 美國(guó)銀行:美國(guó)CBDC將保持美元作為世界儲(chǔ)備貨幣的地位
- 美股三大指數(shù)尾盤(pán)集體轉(zhuǎn)漲
- The new iPad屏幕對(duì)比評(píng)測(cè)
- 電源接通延時(shí)器
- 汽車(chē)電子穩(wěn)定系統(tǒng)(ESP)詳解