0
  • 聊天消息
  • 系統(tǒng)消息
  • 評(píng)論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會(huì)員中心
电子发烧友
开通电子发烧友VIP会员 尊享10大特权
海量资料免费下载
精品直播免费看
优质内容免费畅学
课程9折专享价
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識(shí)你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

詳解機(jī)器學(xué)習(xí)分類算法KNN

電子工程師 ? 來源:csdn ? 作者:程序員lamed ? 2019-10-31 17:18 ? 次閱讀

本文主要介紹一個(gè)被廣泛使用的機(jī)器學(xué)習(xí)分類算法,K-nearest neighbors(KNN),中文叫K近鄰算法。

KNN

k近鄰算法是一種基本分類和回歸方法。

KNN實(shí)際上也可以用于回歸問題,不過在工業(yè)界使用得比較廣泛的還是分類問題

KNN的核心思想也非常簡單,如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別,則該樣本也屬于這個(gè)類別,比如下圖,當(dāng)K=3時(shí),節(jié)點(diǎn)會(huì)被預(yù)測(cè)屬于紅色橢圓類。有點(diǎn)“近朱者赤,近墨者黑”的感覺。

算法的原理非常簡單,但這其中隱藏了一些值得被探討的點(diǎn):

? k該如何取值?

? 距離最近中的“距離”是什么,怎么計(jì)算會(huì)更好?

? 如果對(duì)于一個(gè)數(shù)據(jù)要計(jì)算它與模型中所有點(diǎn)的距離,那當(dāng)數(shù)據(jù)量很大的時(shí)候性能會(huì)很差,怎么改善?

? 在一些情況下明明數(shù)據(jù)離某一個(gè)點(diǎn)特別近,但有另外兩個(gè)同類的點(diǎn)離得很遠(yuǎn)但被K包含在內(nèi)了,這種情況把數(shù)據(jù)劃為這兩個(gè)點(diǎn)的同類是不是不太合理?

? 如果訓(xùn)練數(shù)據(jù)不均衡(Imbalance data)怎么辦?

? 特征的緯度量綱跨越很大(比如10和10000)怎么辦?

? 特征中含有類型(顏色:紅黃藍(lán)綠)怎么處理?

下面我們一一來解決與KNN相關(guān)的一些問題

超參數(shù)(Hyperparameter)K的選取

超參數(shù)是在開始學(xué)習(xí)過程之前設(shè)置值的參數(shù),而不是通過訓(xùn)練得到的參數(shù)數(shù)據(jù)。比如:

? 訓(xùn)練神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)速率。

? 學(xué)習(xí)速率

? 用于支持向量機(jī)的C和sigma超參數(shù)。

? K最近鄰的K。

KNN中,K越大則類與類的分界會(huì)越平緩,K越小則會(huì)越陡峭。當(dāng)K越小時(shí)整個(gè)模型的錯(cuò)誤率(Error Rate)會(huì)越低(當(dāng)然過擬合的可能就越大)。

由于KNN一般用于分類,所以K一般是奇數(shù)才方便投票

一般情況下,K與模型的validation error(模型應(yīng)用于驗(yàn)證數(shù)據(jù)的錯(cuò)誤)的關(guān)系如下圖所示。

K越小則模型越過擬合,在驗(yàn)證數(shù)據(jù)上表現(xiàn)肯定一般,而如果K很大則對(duì)某個(gè)數(shù)據(jù)的預(yù)測(cè)會(huì)把很多距離較遠(yuǎn)的數(shù)據(jù)也放入預(yù)測(cè),導(dǎo)致預(yù)測(cè)發(fā)生錯(cuò)誤。所以我們需要針對(duì)某一個(gè)問題選擇一個(gè)最合適的K值,來保證模型的效果最好。本文僅介紹一種“交叉驗(yàn)證法”,

交叉驗(yàn)證法(Cross Validation)

在機(jī)器學(xué)習(xí)里,通常來說我們不能將全部用于數(shù)據(jù)訓(xùn)練模型,否則我們將沒有數(shù)據(jù)集對(duì)該模型進(jìn)行驗(yàn)證,從而評(píng)估我們的模型的預(yù)測(cè)效果。為了解決這一問題,有如下常用的方法:

? The Validation Set Approach

? Cross-Validation

The Validation Set Approach指的是最簡單的,也是很容易就想到的。我們可以把整個(gè)數(shù)據(jù)集分成兩部分,一部分用于訓(xùn)練,一部分用于驗(yàn)證,這也就是我們經(jīng)常提到的訓(xùn)練集(training set)和驗(yàn)證集(Validation set)

然而我們都知道,當(dāng)用于模型訓(xùn)練的數(shù)據(jù)量越大時(shí),訓(xùn)練出來的模型通常效果會(huì)越好。所以訓(xùn)練集和測(cè)試集的劃分意味著我們無法充分利用我們手頭已有的數(shù)據(jù),所以得到的模型效果也會(huì)受到一定的影響。

基于這樣的背景有人就提出了交叉驗(yàn)證法(Cross-Validation)。

這里簡單介紹下k-fold cross-validation,指的是將所有訓(xùn)練數(shù)據(jù)折成k份,如下圖是當(dāng)折數(shù)k=5時(shí)的情況。

我們分別使用這5組訓(xùn)練-驗(yàn)證數(shù)據(jù)得到KNN超參數(shù)K為某個(gè)值的時(shí)候,比如K=1的5個(gè)準(zhǔn)確率,然后將其準(zhǔn)確率取平均數(shù)得到超參數(shù)K為1時(shí)的準(zhǔn)確率。然后我們繼續(xù)去計(jì)算K=3 K=5 K=7時(shí)的準(zhǔn)確率,然后我們就能選擇到一個(gè)準(zhǔn)確率最高的超參K了。

KNN中的距離

K近鄰算法的核心在于找到實(shí)例點(diǎn)的鄰居,那么鄰居的判定標(biāo)準(zhǔn)是什么,用什么來度量?這在機(jī)器學(xué)習(xí)領(lǐng)域其實(shí)就是去找兩個(gè)特征向量的相似性。機(jī)器學(xué)習(xí)中描述兩個(gè)特征向量間相似性的距離公式有很多:

歐氏距離

常見的兩點(diǎn)之間或多點(diǎn)之間的距離表示法

詳解機(jī)器學(xué)習(xí)分類算法KNN

曼哈頓距離

曼哈頓距離指的是在向量在各坐標(biāo)軸上投影的距離總和,想象你在曼哈頓要從一個(gè)十字路口開車到另外一個(gè)十字路口,駕駛距離是兩點(diǎn)間的直線距離嗎?顯然不是,除非你能穿越大樓。而實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”,此即曼哈頓距離名稱的來源, 同時(shí),曼哈頓距離也稱為城市街區(qū)距離(City Block distance)。

詳解機(jī)器學(xué)習(xí)分類算法KNN

馬氏距離(Mahalanobis Distance)

由印度統(tǒng)計(jì)學(xué)家馬哈拉諾比斯(P. C. Mahalanobis)提出,表示數(shù)據(jù)的協(xié)方差距離。是一種有效的計(jì)算兩個(gè)未知樣本集的相似度的方法。與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系(例如:一條關(guān)于身高的信息會(huì)帶來一條關(guān)于體重的信息,因?yàn)閮烧呤怯嘘P(guān)聯(lián)的),并且是尺度無關(guān)的(scale-invariant),即獨(dú)立于測(cè)量尺度。如果協(xié)方差矩陣為單位矩陣,那么馬氏距離就簡化為歐氏距離。

詳解機(jī)器學(xué)習(xí)分類算法KNN

其他

? 切比雪夫距離(Chebyshev distance)

? 閔可夫斯基距離(Minkowski Distance)

? 標(biāo)準(zhǔn)化歐氏距離 (Standardized Euclidean distance )

? 巴氏距離(Bhattacharyya Distance)

? 漢明距離(Hamming distance)

? 夾角余弦(Cosine)

? 杰卡德相似系數(shù)(Jaccard similarity coefficient)

? 皮爾遜系數(shù)(Pearson Correlation Coefficient)

大數(shù)據(jù)性能優(yōu)化

從原理中很容易知道,最基本的KNN算法的時(shí)間復(fù)雜度是O(N),因?yàn)閷?duì)于某一個(gè)數(shù)據(jù),必須計(jì)算它必須與模型中的所有點(diǎn)的距離。有沒有辦法優(yōu)化這部分性能呢?這里主要說下兩個(gè)方法。

K-d tree

K-d trees are a wonderful invention that enable O( klogn) (expected) lookup times for the k nearest points to some point x. This is extremely useful, especially in cases where an O(n) lookup time is intractable already.

其算法的核心思想是分而治之,即將整個(gè)空間劃分為幾個(gè)小部分。

詳解機(jī)器學(xué)習(xí)分類算法KNN

注意K-D樹對(duì)于數(shù)據(jù)緯度d來說是指數(shù)級(jí)的復(fù)雜度,所以只適合用在數(shù)據(jù)緯度較小的情況。

Locality Sensitivity Hasing(LSH)

詳解機(jī)器學(xué)習(xí)分類算法KNN

LSH的基本思想是將數(shù)據(jù)節(jié)點(diǎn)插入Buckets,讓距離近的節(jié)點(diǎn)大概率插入同一個(gè)bucket中,數(shù)據(jù)間距離遠(yuǎn)的兩個(gè)點(diǎn)則大概率在不同的bucket,這使得確定某點(diǎn)最臨近的節(jié)點(diǎn)變得更為容易。

所以LSH不能保證一定準(zhǔn)確

詳解機(jī)器學(xué)習(xí)分類算法KNN

樣本的重要性

在一些情況下明明數(shù)據(jù)離某一個(gè)點(diǎn)特別近,但有另外兩個(gè)同類的點(diǎn)離得很遠(yuǎn)但被K包含在內(nèi)了,這種情況把數(shù)據(jù)劃為這兩個(gè)點(diǎn)的同類是不是不太合理。

例如下圖,當(dāng)K=3時(shí),紅點(diǎn)會(huì)被投票選舉成Offer類,但實(shí)際上這個(gè)點(diǎn)可能更加適合分類為No Offer。

詳解機(jī)器學(xué)習(xí)分類算法KNN

為了解決這一問題有一種方法Distance-weighted nearest neighbor,其核心思想是讓距離近的點(diǎn)可以得到更大的權(quán)重。

責(zé)任編輯:zl

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請(qǐng)聯(lián)系本站處理。 舉報(bào)投訴
收藏 0人收藏

    評(píng)論

    相關(guān)推薦
    熱點(diǎn)推薦

    【Firefly RK3399試用體驗(yàn)】之結(jié)項(xiàng)——KNN、SVM分類器在SKlearn機(jī)器學(xué)習(xí)工具集中運(yùn)用

    已知分類的訓(xùn)練數(shù)據(jù)集,然后用這些數(shù)據(jù)及其分類去訓(xùn)練分類器,然后再用測(cè)試數(shù)據(jù)輸入訓(xùn)練器,訓(xùn)練器對(duì)這些數(shù)據(jù)做出分類,這也是一般機(jī)器
    發(fā)表于 07-20 22:26

    KNN算法原理

    KNN(K近鄰算法
    發(fā)表于 11-01 09:14

    機(jī)器學(xué)習(xí)KNN介紹

    機(jī)器學(xué)習(xí)(李航統(tǒng)計(jì)學(xué)方法)之KNN
    發(fā)表于 04-07 16:20

    KNN分類算法及python代碼實(shí)現(xiàn)

    kNN分類算法的Python實(shí)現(xiàn)
    發(fā)表于 06-05 12:02

    使用KNN進(jìn)行分類和回歸

    的模型,可以用于回歸和分類任務(wù)。大部分的機(jī)器學(xué)習(xí)算法都是用它的名字來描述的KNN也是一樣,使用一個(gè)空間來表示鄰居的度量,度量空間根據(jù)集合成員
    發(fā)表于 10-28 14:44

    基于中心向量的多級(jí)分類KNN算法研究

    針對(duì)KNN算法在中文文本分類時(shí)的兩個(gè)不足:訓(xùn)練樣本分布不均,分類時(shí)計(jì)算開銷大的問題,在已有改進(jìn)算法的基礎(chǔ)上進(jìn)行了更深入的研究,提出多級(jí)
    發(fā)表于 11-17 14:43 ?3次下載
    基于中心向量的多級(jí)<b class='flag-5'>分類</b><b class='flag-5'>KNN</b><b class='flag-5'>算法</b>研究

    人工智能機(jī)器學(xué)習(xí)之K近鄰算法KNN

    K近鄰KNN(k-Nearest Neighbor)算法,也叫K最近鄰算法,1968年由 Cover 和 Hart 提出,是機(jī)器學(xué)習(xí)
    發(fā)表于 05-29 06:53 ?3080次閱讀

    各類機(jī)器學(xué)習(xí)分類算法的優(yōu)點(diǎn)與缺點(diǎn)分析

    機(jī)器學(xué)習(xí)中有許多分類算法。本文將介紹分類中使用的各種機(jī)器學(xué)習(xí)
    發(fā)表于 03-02 09:50 ?3875次閱讀

    如何使用Arduino KNN庫進(jìn)行簡單的機(jī)器學(xué)習(xí)?

    優(yōu)勢(shì)在于,一旦Arduino獲得了一些示例數(shù)據(jù),就可以立即對(duì)其進(jìn)行分類。我們已經(jīng)發(fā)布了一個(gè)新的Arduino庫,可以快速輕松地將KNN導(dǎo)入在程序中,且無需進(jìn)行設(shè)備外培訓(xùn)或其他工具。 在本文中,我們將使用顏色分類器示例來介紹
    的頭像 發(fā)表于 04-01 10:07 ?3853次閱讀
    如何使用Arduino <b class='flag-5'>KNN</b>庫進(jìn)行簡單的<b class='flag-5'>機(jī)器</b><b class='flag-5'>學(xué)習(xí)</b>?

    可檢測(cè)網(wǎng)絡(luò)入侵的IL-SVM-KNN分類

    為滿足入侵檢測(cè)的實(shí)時(shí)性和準(zhǔn)確性要求,通過結(jié)合支持向量機(jī)(SVM)和K最近鄰(KNN算法設(shè)ⅡL-SM-KNN分類器,并采用平衡k維樹作為數(shù)據(jù)結(jié)構(gòu)提升執(zhí)行速度。訓(xùn)練階段應(yīng)用增量
    發(fā)表于 04-29 15:55 ?7次下載
    可檢測(cè)網(wǎng)絡(luò)入侵的IL-SVM-<b class='flag-5'>KNN</b><b class='flag-5'>分類</b>器

    KNN算法分類回歸樹、隨機(jī)森林的優(yōu)缺點(diǎn)及應(yīng)用實(shí)例

    KNN屬于一種監(jiān)督學(xué)習(xí)分類算法,用于訓(xùn)練的數(shù)據(jù)集是完全正確且已分好類的。
    的頭像 發(fā)表于 11-11 10:11 ?6547次閱讀

    機(jī)器學(xué)習(xí)算法匯總 機(jī)器學(xué)習(xí)算法分類 機(jī)器學(xué)習(xí)算法模型

    機(jī)器學(xué)習(xí)算法匯總 機(jī)器學(xué)習(xí)算法分類
    的頭像 發(fā)表于 08-17 16:11 ?1466次閱讀

    機(jī)器學(xué)習(xí)有哪些算法?機(jī)器學(xué)習(xí)分類算法有哪些?機(jī)器學(xué)習(xí)預(yù)判有哪些算法?

    機(jī)器學(xué)習(xí)有哪些算法?機(jī)器學(xué)習(xí)分類算法有哪些?
    的頭像 發(fā)表于 08-17 16:30 ?2348次閱讀

    機(jī)器學(xué)習(xí)算法原理詳解

    機(jī)器學(xué)習(xí)作為人工智能的一個(gè)重要分支,其目標(biāo)是通過讓計(jì)算機(jī)自動(dòng)從數(shù)據(jù)中學(xué)習(xí)并改進(jìn)其性能,而無需進(jìn)行明確的編程。本文將深入解讀幾種常見的機(jī)器學(xué)習(xí)
    的頭像 發(fā)表于 07-02 11:25 ?2195次閱讀

    【每天學(xué)點(diǎn)AI】KNN算法:簡單有效的機(jī)器學(xué)習(xí)分類

    過程,其實(shí)就是一個(gè)簡單的分類問題,而KNN(K-NearestNeighbors)算法正是模仿這種人類決策過程的機(jī)器學(xué)習(xí)
    的頭像 發(fā)表于 10-31 14:09 ?787次閱讀
    【每天學(xué)點(diǎn)AI】<b class='flag-5'>KNN</b><b class='flag-5'>算法</b>:簡單有效的<b class='flag-5'>機(jī)器</b><b class='flag-5'>學(xué)習(xí)</b><b class='flag-5'>分類</b>器

    電子發(fā)燒友

    中國電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會(huì)員交流學(xué)習(xí)
    • 獲取您個(gè)性化的科技前沿技術(shù)信息
    • 參加活動(dòng)獲取豐厚的禮品