本文主要介紹一個(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)之間的距離表示法
曼哈頓距離
曼哈頓距離指的是在向量在各坐標(biāo)軸上投影的距離總和,想象你在曼哈頓要從一個(gè)十字路口開車到另外一個(gè)十字路口,駕駛距離是兩點(diǎn)間的直線距離嗎?顯然不是,除非你能穿越大樓。而實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”,此即曼哈頓距離名稱的來源, 同時(shí),曼哈頓距離也稱為城市街區(qū)距離(City Block distance)。
馬氏距離(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é)方差矩陣為單位矩陣,那么馬氏距離就簡化為歐氏距離。
其他
? 切比雪夫距離(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è)小部分。
注意K-D樹對(duì)于數(shù)據(jù)緯度d來說是指數(shù)級(jí)的復(fù)雜度,所以只適合用在數(shù)據(jù)緯度較小的情況。
Locality Sensitivity Hasing(LSH)
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)確
樣本的重要性
在一些情況下明明數(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。
為了解決這一問題有一種方法Distance-weighted nearest neighbor,其核心思想是讓距離近的點(diǎn)可以得到更大的權(quán)重。
責(zé)任編輯:zl
-
神經(jīng)網(wǎng)絡(luò)
+關(guān)注
關(guān)注
42文章
4810瀏覽量
102918 -
KNN
+關(guān)注
關(guān)注
0文章
22瀏覽量
10967 -
機(jī)器學(xué)習(xí)
+關(guān)注
關(guān)注
66文章
8493瀏覽量
134164
發(fā)布評(píng)論請(qǐng)先 登錄
【Firefly RK3399試用體驗(yàn)】之結(jié)項(xiàng)——KNN、SVM分類器在SKlearn機(jī)器學(xué)習(xí)工具集中運(yùn)用
使用KNN進(jìn)行分類和回歸
基于中心向量的多級(jí)分類KNN算法研究

人工智能機(jī)器學(xué)習(xí)之K近鄰算法(KNN)
各類機(jī)器學(xué)習(xí)分類算法的優(yōu)點(diǎn)與缺點(diǎn)分析
如何使用Arduino KNN庫進(jìn)行簡單的機(jī)器學(xué)習(xí)?

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

KNN算法、分類回歸樹、隨機(jī)森林的優(yōu)缺點(diǎn)及應(yīng)用實(shí)例
機(jī)器學(xué)習(xí)算法匯總 機(jī)器學(xué)習(xí)算法分類 機(jī)器學(xué)習(xí)算法模型
機(jī)器學(xué)習(xí)有哪些算法?機(jī)器學(xué)習(xí)分類算法有哪些?機(jī)器學(xué)習(xí)預(yù)判有哪些算法?
機(jī)器學(xué)習(xí)算法原理詳解
【每天學(xué)點(diǎn)AI】KNN算法:簡單有效的機(jī)器學(xué)習(xí)分類器

評(píng)論