簡介

K最近鄰(KNN, k-NearestNeighbor)是一種常見的機(jī)器學(xué)習(xí)方法，維基百科解釋：

在模式識別領(lǐng)域中，最近鄰居法（KNN算法，又譯K-近鄰算法）是一種用于分類和回歸的非參數(shù)統(tǒng)計(jì)方法。在這兩種情況下，輸入包含特征空間（Feature Space）中的k個(gè)最接近的訓(xùn)練樣本。

• 在k-NN分類中，輸出是一個(gè)分類族群。一個(gè)對象的分類是由其鄰居的“多數(shù)表決”確定的，k個(gè)最近鄰居（k為正整數(shù))，通常較小）中最常見的分類決定了賦予該對象的類別。若k = 1，則該對象的類別直接由最近的一個(gè)節(jié)點(diǎn)賦予。
• 在k-NN回歸中，輸出是該對象的屬性值。該值是其k個(gè)最近鄰居的值的平均值。

由此我們可知, KNN不僅可以用于分類任務(wù)中, 同樣也可以將其用在回歸問題上。

至于什么是非參數(shù)統(tǒng)計(jì)方法，雖然維基百科已經(jīng)給出了解釋，但我習(xí)慣將他理解為消極學(xué)習(xí)（Lazy Learning）。好吧，另外一個(gè)問題出現(xiàn)了，什么又是消極學(xué)習(xí)呢，有消極學(xué)習(xí)一定也會(huì)有積極學(xué)習(xí)吧，以下摘自另一篇博客的解釋：

積極學(xué)習(xí)

這種學(xué)習(xí)方式是指在進(jìn)行某種判斷（例如，確定一個(gè)點(diǎn)的分類或者回歸中確定某個(gè)點(diǎn)對應(yīng)的函數(shù)值）之前，先利用訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練得到一個(gè)目標(biāo)函數(shù)，待需要時(shí)就只利用訓(xùn)練好的函數(shù)進(jìn)行決策，顯然這是一種一勞永逸的方法，SVM就屬于這種學(xué)習(xí)方式。

消極學(xué)習(xí)

這種學(xué)習(xí)方式指不是根據(jù)樣本建立一般化的目標(biāo)函數(shù)并確定其參數(shù)，而是簡單地把訓(xùn)練樣本存儲(chǔ)起來，直到需要分類新的實(shí)例時(shí)才分析其與所存儲(chǔ)樣例的關(guān)系，據(jù)此確定新實(shí)例的目標(biāo)函數(shù)值。也就是說這種學(xué)習(xí)方式只有到了需要決策時(shí)才會(huì)利用已有數(shù)據(jù)進(jìn)行決策，而在這之前不會(huì)經(jīng)歷 Eager Learning所擁有的訓(xùn)練過程。KNN就屬于這種學(xué)習(xí)方式。

簡單理解，積極學(xué)習(xí)需要訓(xùn)練過程，消極學(xué)習(xí)不需要訓(xùn)練（時(shí)間復(fù)雜度為0）過程直接預(yù)測就可以

原理（以分類問題為例）

KNN利用的思想是人們所熟知的一句古話，物以類聚，人以群分。他周圍一定范圍內(nèi)的樣本哪個(gè)類別多就認(rèn)為他是哪個(gè)類別。具體過程如下：

• 計(jì)算預(yù)判斷類別的樣本與其他所有樣本的相似度（時(shí)間復(fù)雜度O(n)）；
• 將結(jié)果按相似度由大到小排序；
• 取前K個(gè)樣本，統(tǒng)計(jì)其類別，將類別最多的一類記為該預(yù)測樣本的類別

我們通過一個(gè)例子來說明，假設(shè)有 ○ 和 □ 兩種數(shù)據(jù)，其分布如下：
[圖片上傳失敗...(image-df2758-1565583011308)]
這時(shí)新增了一個(gè)未知分類的樣本，位置如下，要判斷其類別：

image

那么K值應(yīng)該取什么值比較合理呢，我們再看下另一種極端的情況, 取K=N(N為樣本數(shù))，如下圖：

image

我們算下一共有8個(gè) □，9個(gè) ○，少數(shù)服從多數(shù)，我們認(rèn)為這個(gè)樣本屬于 ○。也不合理

K過大或過小都不合適，最合理的K值應(yīng)該是下邊這種情況：

image

這種情況下樣本會(huì)被正確分為 □

實(shí)際應(yīng)用當(dāng)中我們一般使用交叉驗(yàn)證(Cross-validation)的方法取得最優(yōu)K值，一般不超過20，上限是

相似度

上述示例我們默認(rèn)使用歐氏距離的方法計(jì)算兩個(gè)樣本的距離(相似度)，即：

實(shí)際上計(jì)算相似度的方法還有很多，具體可以參看我的另一篇文章8種相似度度量方式的原理及實(shí)現(xiàn)