K Nearest Neighbor算法又叫KNN算法，這個算法是機器學(xué)習(xí)里面一個比較經(jīng)典的算法， 總體來說KNN算法是相對比較容易理解的算法。其中的K表示最接近自己的K個數(shù)據(jù)樣本。KNN算法和K-Means算法不同的是，K-Means算法用來聚類，用來判斷哪些東西是一個比較相近的類型，而KNN算法是用來做歸類的，也就是說，有一個樣本空間里的樣本分成很幾個類型，然后，給定一個待分類的數(shù)據(jù)，通過計算接近自己最近的K個樣本來判斷這個待分類數(shù)據(jù)屬于哪個分類。你可以簡單的理解為由那離自己最近的K個點來投票決定待分類數(shù)據(jù)歸為哪一類。
Wikipedia上的KNN詞條中有一個比較經(jīng)典的圖如下：
從上圖中我們可以看到，圖中的有兩個類型的樣本數(shù)據(jù)，一類是藍色的正方形，另一類是紅色的三角形。而那個綠色的圓形是我們待分類的數(shù)據(jù)。
- 如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍色的正方形，這3個點投票，于是綠色的這個待分類點屬于紅色的三角形。
- 如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍色的正方形。
我們可以看到，機器學(xué)習(xí)的本質(zhì)——是基于一種數(shù)據(jù)統(tǒng)計的方法！那么，這個算法有什么用呢？我們來看幾個示例。
產(chǎn)品質(zhì)量判斷
假設(shè)我們需要判斷紙巾的品質(zhì)好壞，紙巾的品質(zhì)好壞可以抽像出兩個向量，一個是“酸腐蝕的時間”，一個是“能承受的壓強”。如果我們的樣本空間如下：（所謂樣本空間，又叫Training Data，也就是用于機器學(xué)習(xí)的數(shù)據(jù)）
|
向量X1 耐酸時間（秒） |
向量X2 圧強(公斤/平方米) |
品質(zhì)Y |
|
7 |
7 |
壞 |
|
7 |
4 |
壞 |
|
3 |
4 |
好 |
|
1 |
4 |
好 |
那么，如果 X1 = 3 和 X2 = 7， 這個毛巾的品質(zhì)是什么呢？這里就可以用到KNN算法來判斷了。
假設(shè)K=3，K應(yīng)該是一個奇數(shù)，這樣可以保證不會有平票，下面是我們計算（3，7）到所有點的距離。（關(guān)于那些距離公式，可以參看K-Means算法中的距離公式）
|
向量X1 耐酸時間（秒） |
向量X2 圧強(公斤/平方米) |
計算到 (3, 7)的距離 |
向量Y |
|
7 |
7 |
|
壞 |
|
7 |
4 |
|
N/A |
|
3 |
4 |
|
好 |
|
1 |
4 |
|
好 |
所以，最后的投票，好的有2票，壞的有1票，最終需要測試的（3，7）是合格品。（當然，你還可以使用權(quán)重——可以把距離值做為權(quán)重，越近的權(quán)重越大，這樣可能會更準確一些）
注：示例來自這里，K-NearestNeighbors Excel表格下載
預(yù)測
假設(shè)我們有下面一組數(shù)據(jù)，假設(shè)X是流逝的秒數(shù)，Y值是隨時間變換的一個數(shù)值（你可以想像是股票值）
那么，當時間是6.5秒的時候，Y值會是多少呢？我們可以用KNN算法來預(yù)測之。
這里，讓我們假設(shè)K=2，于是我們可以計算所有X點到6.5的距離，如：X=5.1，距離是 | 6.5 – 5.1 | = 1.4， X = 1.2 那么距離是 | 6.5 – 1.2 | = 5.3 。于是我們得到下面的表：
注意，上圖中因為K=2，所以得到X=4 和 X =5.1的點最近，得到的Y的值分別為27和8，在這種情況下，我們可以簡單的使用平均值來計算：
于是，最終預(yù)測的數(shù)值為：17.5
注：示例來自這里，KNN_TimeSeries Excel表格下載
插值，平滑曲線
KNN算法還可以用來做平滑曲線用，這個用法比較另類。假如我們的樣本數(shù)據(jù)如下（和上面的一樣）：
要平滑這些點，我們需要在其中插入一些值，比如我們用步長為0.1開始插值，從0到6開始，計算到所有X點的距離（絕對值），下圖給出了從0到0.5 的數(shù)據(jù)：
下圖給出了從2.5到3.5插入的11個值，然后計算他們到各個X的距離，假值K=4，那么我們就用最近4個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 一個大表，跟據(jù)K的取值不同，得到下面的圖：
|
|
|
|
|
注：示例來自這里，KNN_Smoothing Excel表格下載
后記
最后，我想再多說兩個事，
1） 一個是機器學(xué)習(xí)，算法基本上都比較簡單，最難的是數(shù)學(xué)建模，把那些業(yè)務(wù)中的特性抽象成向量的過程，另一個是選取適合模型的數(shù)據(jù)樣本。這兩個事都不是簡單的事。算法反而是比較簡單的事。
2）對于KNN算法中找到離自己最近的K個點，是一個很經(jīng)典的算法面試題，需要使用到的數(shù)據(jù)結(jié)構(gòu)是“最大堆——Max Heap”，一種二叉樹。你可以看看相關(guān)的算法。
（全文完）
