① 01 KNN演算法 - 概述
KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）
KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。
KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。
KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。
KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。
多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。
平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。
再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。
k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。
距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。
加權多數表決法：
平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6
加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。
2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。
② K-近鄰演算法簡介
1.K-近鄰(KNearestNeighbor,KNN)演算法簡介 ：對於一個未知的樣本，我們可以根據離它最近的k個樣本的類別來判斷它的類別。
以下圖為例，對於一個未知樣本綠色小圓，我們可以選取離它最近的3的樣本，其中包含了2個紅色三角形，1個藍色正方形，那麼我們可以判斷綠色小圓屬於紅色三角形這一類。
我們也可以選取離它最近的5個樣本，其中包含了3個藍色正方形，2個紅色三角形，那麼我們可以判斷綠色小圓屬於藍色正方形這一類。
3.API文檔
下面我們來對KNN演算法中的參數項做一個解釋說明：
'n_neighbors'：選取的參考對象的個數（鄰居個數），默認值為5，也可以自己指定數值，但不是n_neighbors的值越大分類效果越好，最佳值需要我們做一個驗證。
'weights': 距離的權重參數，默認uniform。
'uniform': 均勻的權重，所有的點在每一個類別中的權重是一樣的。簡單的說，就是每個點的重要性都是一樣的。
'distance'：權重與距離的倒數成正比，距離近的點重要性更高，對於結果的影響也更大。
'algorithm':運算方法，默認auto。
'auto'：根絕模型fit的數據自動選擇最合適的運算方法。
'ball_tree'：樹模型演算法BallTree
'kd_tree'：樹模型演算法KDTree
'brute'：暴力演算法
'leaf_size'：葉子的尺寸，默認30。只有當algorithm = 'ball_tree' or 'kd_tree'，這個參數需要設定。
'p'：閔可斯基距離，當p = 1時，選擇曼哈頓距離；當p = 2時，選擇歐式距離。
n_jobs：使用計算機處理器數目，默認為1。當n=-1時，使用所有的處理器進行運算。
4.應用案例演示
下面以Sklearn庫中自帶的數據集--手寫數字識別數據集為例，來測試下kNN演算法。上一章，我們簡單的介紹了機器學習的一般步驟：載入數據集 - 訓練模型 - 結果預測 - 保存模型。這一章我們還是按照這個步驟來執行。
[手寫數字識別數據集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits
5.模型的方法
每一種模型都有一些它獨有的屬性方法（模型的技能，能做些什麼事），下面我們來了解下knn演算法常用的的屬性方法。
6.knn演算法的優缺點
優點：
簡單，效果還不錯，適合多分類問題
缺點：
效率低（因為要計算預測樣本距離每個樣本點的距離，然後排序），效率會隨著樣本量的增加而降低。
③ 02 KNN演算法 - KD Tree
KD Tree 是KNN演算法中用於計算最近鄰的快速簡便的構建方式。
當樣本量少的時候，用 brute 直接搜索最近鄰的方式是可行的。即計算到所有樣本的距離。但當樣本量龐大時，直接計算所有樣本距離的工作量很大，這種情況使用 KD Tree 可以節約大量時間成本。
KD樹採用從m個樣本的n維特徵中，分別計算n個特徵取值的方差，用 方差最大 的第k維特徵n k 作為 根節點 。對於這個特徵，選擇取值中的 中位數 n kv 作為樣本的劃分點，對於小於該值的樣本劃分到 左子樹 ，對於大於等於該值的樣本劃分到 右子樹 ，對左右子樹採用同樣的方式找 方差最大的特徵 作為 根節點 ，遞歸產生KD Tree。
為什麼要選擇方差最大的進行劃分？
構建樹的目的是加快我的搜索過程。
既然我想加快我的搜索過程，要就意味著我最終的數據落在某個葉子節點上。我希望只需搜索整個二叉樹的某一些列即可，那麼最好的劃分方式，就是讓我的每個分支上數據的差異性最大化。
那麼衡量數據差異性的最基礎的數學指標是什麼？
是方差。方差越大，意味著數據的離散程度就越大，我將離散程度由大到小的數據一分為二，方差小意味著數據更集中到了一起。
現在有一個二維樣本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、計算x1和x2每一列對應的方差
a、通過pandas計算出的是 樣本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通過numpy計算出的是 總體方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一個樹的劃分：基於x 1 進行劃分
[2,4,5,7,8,9]的中位數是5和7的平均值6。
雖然嚴格意義上說中位數是6，但是在計算機中我們人為得定義x 1 的中位數是7。
左側：（2,3）（5,4）（4,7） （7,2）
右側: （9,6）（8,1）
第二個樹的劃分：根據右側（9,6）（8,1）的x 2 進行劃分
下側：x 2 ≤ 6；上側x 2 ＞6
第二個樹的劃分：根據左側（2,3）（5,4）（4,7） （7,2）的x 2 進行劃分
尋找2、3、4、7的中位數 4 進行劃分
....
注意：每次生成的劃分都是一個矩形。當葉子節點無法被繼續劃分的時候，KD樹的構建完成，遞歸結束。
我們生成了KD Tree後，現在就可以去預測測試集裡面的樣本目標點了。
1、對於一個目標點，先在KD樹里找到包含目標點的葉子節點。
2、以目標點為圓心，以 目標點 到 葉子節點樣本實例 的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。
3、然後返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交。
4、如果相交就倒這個子節點尋找著是否有更加近的近鄰，有的話就更新最近鄰。
5、如果不相交，直接返回父節點中的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，演算法結束。
6、此時保存的最近鄰節點就是最終的最近鄰。
如果現在想找(2,4.5)這點的最近鄰，該如何操作？
1、畫出二叉樹：
2、尋找(2,4.5)這點：
一個比較好的理解方式：首先找到第一個最近鄰，然後畫出一個圓。然後逐漸收縮圓的半徑，查看每次縮小後的圓是否能夠和矩形相交於一個更小的最近鄰點，如果有則更新。直到回到根節點。