KNN算法全稱是K近鄰算法 （K-nearst neighbors，KNN）
KNN是一種基本的機器學習算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它最接近的k個鄰近位置的樣本來代替。
KNN是個相對比較簡單的算法，比起之前提過的回歸算法和分類算法更容易。如果一個人從來沒有接觸過機器學習的算法，拿到數(shù)據(jù)后最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然后你們發(fā)現(xiàn)我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。
KNN算法即可以應用于分類算法中，也可以應用于回歸算法中。
KNN在做回歸和分類的主要區(qū)別，在于最后做預測時候的決策不同。在分類預測時，一般采用多數(shù)表決法。在做回歸預測時，一般使用平均值法。
多數(shù)表決法：分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。
平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。
KNN算法原理
思考： 圖中綠色圓圈屬于哪個分類？方塊還是三角？
我們發(fā)現(xiàn)當樣本取值為k=1時，圓圈周圍的三角更多，我們認為圓圈屬于三角的分類。
當樣本取值為k=2，圓圈周圍的方塊比三角多，我們認為圓圈屬于方塊分類。
再舉個例子：
分別根據(jù)甜度和脆度兩個特征來判斷食物的種類。
根據(jù)樣本我們普遍發(fā)現(xiàn)：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質(zhì)。
不甜，比較脆的食物是蔬菜。
于是根據(jù)目標的樣本甜度和脆度兩個特征，我們可以對其進行分類了。
KNN三要素
k值的選擇:
先選一個較小的值，然后通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至于過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。
距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常采用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
決策規(guī)劃:
分類：多數(shù)表決法、加權多數(shù)表決法。
回歸：平均值法、加權平均值法。
加權多數(shù)表決法：
平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6
加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
KNN算法的實現(xiàn)方式
1、蠻力實現(xiàn)(brute)：
計算預測樣本到所有訓練集樣本的距離，然后選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特征數(shù)多、樣本數(shù)多時，算法的效率比較低。
2、KD樹 (kd_tree)：
首先對訓練數(shù)據(jù)進行建模，構建KD樹，然后根據(jù)建好的模型來獲取鄰近樣本數(shù)據(jù)。
后續(xù)內(nèi)容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現(xiàn)要少檢索多少數(shù)據(jù)。
