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