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 耐酸時(shí)間（秒）	向量X2 圧強(qiáng)(公斤/平方米)	品質(zhì)Y
7	7	壞
7	4	壞
3	4	好
1	4	好

那么，如果 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算法中的距離公式）

向量X1 耐酸時(shí)間（秒）	向量X2 圧強(qiáng)(公斤/平方米)	計(jì)算到 (3, 7)的距離	向量Y
7	7		?壞
7	4		?N/A
3	4		?好
1	4		?好

所以，最后的投票，好的有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開(kāi)始插值，從0到6開(kāi)始，計(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”，一種二叉樹(shù)。你可以看看相關(guān)的算法。

（全文完）

from: http://coolshell.cn/articles/8052.html

總結(jié)

以上是生活随笔為你收集整理的K Nearest Neighbor 算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。