K Nearest Neighbor算法又叫KNN算法,，這個(gè)算法是機(jī)器學(xué)習(xí)里面一個(gè)比較經(jīng)典的算法,， 總體來(lái)說(shuō)KNN算法是相對(duì)比較容易理解的算法。其中的K表示最接近自己的K個(gè)數(shù)據(jù)樣本,。KNN算法和K-Means算法不同的是,，K-Means算法用來(lái)聚類，用來(lái)判斷哪些東西是一個(gè)比較相近的類型,，而KNN算法是用來(lái)做歸類的,，也就是說(shuō)，有一個(gè)樣本空間里的樣本分成很幾個(gè)類型,，然后,，給定一個(gè)待分類的數(shù)據(jù)，通過(guò)計(jì)算接近自己最近的K個(gè)樣本來(lái)判斷這個(gè)待分類數(shù)據(jù)屬于哪個(gè)分類,。你可以簡(jiǎn)單的理解為由那離自己最近的K個(gè)點(diǎn)來(lái)投票決定待分類數(shù)據(jù)歸為哪一類,。

Wikipedia上的KNN詞條中有一個(gè)比較經(jīng)典的圖如下：

從上圖中我們可以看到,，圖中的有兩個(gè)類型的樣本數(shù)據(jù),，一類是藍(lán)色的正方形,，另一類是紅色的三角形,。而那個(gè)綠色的圓形是我們待分類的數(shù)據(jù)。

• 如果K=3,，那么離綠色點(diǎn)最近的有2個(gè)紅色三角形和1個(gè)藍(lán)色的正方形,，這3個(gè)點(diǎn)投票,，于是綠色的這個(gè)待分類點(diǎn)屬于紅色的三角形。

• 如果K=5，那么離綠色點(diǎn)最近的有2個(gè)紅色三角形和3個(gè)藍(lán)色的正方形,，這5個(gè)點(diǎn)投票，于是綠色的這個(gè)待分類點(diǎn)屬于藍(lán)色的正方形,。

我們可以看到，機(jī)器學(xué)習(xí)的本質(zhì)——是基于一種數(shù)據(jù)統(tǒng)計(jì)的方法,！那么,，這個(gè)算法有什么用呢？我們來(lái)看幾個(gè)示例,。

產(chǎn)品質(zhì)量判斷

假設(shè)我們需要判斷紙巾的品質(zhì)好壞,，紙巾的品質(zhì)好壞可以抽像出兩個(gè)向量，一個(gè)是“酸腐蝕的時(shí)間”,，一個(gè)是“能承受的壓強(qiáng)”,。如果我們的樣本空間如下：（所謂樣本空間，又叫Training Data,，也就是用于機(jī)器學(xué)習(xí)的數(shù)據(jù)）

那么,，如果 X1 = 3 和 X2 = 7,， 這個(gè)毛巾的品質(zhì)是什么呢,？這里就可以用到KNN算法來(lái)判斷了,。

假設(shè)K=3，K應(yīng)該是一個(gè)奇數(shù),，這樣可以保證不會(huì)有平票,，下面是我們計(jì)算（3,，7）到所有點(diǎn)的距離。（關(guān)于那些距離公式,，可以參看K-Means算法中的距離公式）

所以,，最后的投票，好的有2票,，壞的有1票，最終需要測(cè)試的（3,，7）是合格品,。（當(dāng)然,，你還可以使用權(quán)重——可以把距離值做為權(quán)重,，越近的權(quán)重越大,，這樣可能會(huì)更準(zhǔn)確一些）

注：示例來(lái)自這里,，K-NearestNeighbors Excel表格下載

預(yù)測(cè)

假設(shè)我們有下面一組數(shù)據(jù)，假設(shè)X是流逝的秒數(shù),，Y值是隨時(shí)間變換的一個(gè)數(shù)值（你可以想像是股票值）

那么,，當(dāng)時(shí)間是6.5秒的時(shí)候，Y值會(huì)是多少呢,？我們可以用KNN算法來(lái)預(yù)測(cè)之。

這里,，讓我們假設(shè)K=2,，于是我們可以計(jì)算所有X點(diǎn)到6.5的距離,，如：X=5.1，距離是 | 6.5 – 5.1 | = 1.4,， X = 1.2 那么距離是 | 6.5 – 1.2 | = 5.3 ,。于是我們得到下面的表：

注意，上圖中因?yàn)镵=2,，所以得到X=4 和 X =5.1的點(diǎn)最近,，得到的Y的值分別為27和8，在這種情況下,，我們可以簡(jiǎn)單的使用平均值來(lái)計(jì)算：

于是,，最終預(yù)測(cè)的數(shù)值為：17.5

注：示例來(lái)自這里，KNN_TimeSeries Excel表格下載

插值,，平滑曲線

KNN算法還可以用來(lái)做平滑曲線用,，這個(gè)用法比較另類。假如我們的樣本數(shù)據(jù)如下（和上面的一樣）：

要平滑這些點(diǎn),，我們需要在其中插入一些值,，比如我們用步長(zhǎng)為0.1開始插值，從0到6開始,，計(jì)算到所有X點(diǎn)的距離（絕對(duì)值）,，下圖給出了從0到0.5 的數(shù)據(jù)：

下圖給出了從2.5到3.5插入的11個(gè)值，然后計(jì)算他們到各個(gè)X的距離,，假值K=4,，那么我們就用最近4個(gè)X的Y值,，然后求平均值,，得到下面的表：

于是可以從0.0, 0.1, 0.2, 0.3 …. 1.1, 1.2, 1.3…..3.1, 3.2…..5.8, 5.9, 6.0 一個(gè)大表，跟據(jù)K的取值不同,，得到下面的圖：

注：示例來(lái)自這里,，KNN_Smoothing Excel表格下載

后記

最后，我想再多說(shuō)兩個(gè)事,，

1） 一個(gè)是機(jī)器學(xué)習(xí),，算法基本上都比較簡(jiǎn)單，最難的是數(shù)學(xué)建模,，把那些業(yè)務(wù)中的特性抽象成向量的過(guò)程,，另一個(gè)是選取適合模型的數(shù)據(jù)樣本。這兩個(gè)事都不是簡(jiǎn)單的事,。算法反而是比較簡(jiǎn)單的事,。

2）對(duì)于KNN算法中找到離自己最近的K個(gè)點(diǎn)，是一個(gè)很經(jīng)典的算法面試題,，需要使用到的數(shù)據(jù)結(jié)構(gòu)是“最大堆——Max Heap”,，一種二叉樹,。你可以看看相關(guān)的算法。

（全文完）