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

本文主要介紹一個(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