分類演算法實例五：用KD Tree查找最近鄰
- 2020 年 3 月 18 日
- 筆記
1、KNN參數說明
|
參數 |
K Neighbors Classifier（KNN分類）和K Neighbors Regressor（KNN回歸） |
|---|---|
|
weights |
樣本權重，可選參數: uniform（等權重）、distance（權重和距離成反比，越近影響越強）；默認為uniform |
|
n_neighbors |
鄰近數目，默認為5 |
|
algorithm |
計算方式，默認為auto，可選參數: auto、ball_tree、kd_tree、brute；推薦選擇kd_tree |
|
leaf_size |
在使用KD_Tree的時候，葉子數量，默認為30 |
|
metric |
樣本之間距離度量公式，默認為minkowski（閔可夫斯基）；當參數p為2的時候，其實就是歐幾里得距離 |
|
p |
給定minkowski距離中的p值 |
2、KD Tree介紹
（1）KD Tree的適用場景 KD Tree是密度聚類（DBSCAN）演算法中計算樣本和核心對象之間距離來獲取最近鄰以及KNN演算法中用於計算最近鄰的快速、便捷構建方式。 當樣本數據量少的時候，我們可以使用brute這種暴力的方式進行求解最近鄰，即計算到所有樣本的距離。但是當樣本量比較大的時候，直接計算所有樣本的距離，工作量有點大，所以在這種情況下，我們可以使用KD Tree來快速的計算。 （2）KD Tree的構建方式 KD樹採用從m個樣本的n維特徵中，分別計算n個特徵取值的方差，用方差最大的第k維特徵nkn_knk作為根節點。對於這個特徵，選擇取值的中位數nkvn_{kv}nkv作為樣本的劃分點，對於小於該值的樣本劃分到左子樹，對於大於等於該值的樣本劃分到右子樹，對左右子樹採用同樣的方式找方差最大的特徵作為根節點，遞歸即可產生KD樹。 （3）KD Tree示例 二維樣本：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}。
（4）KD Tree查找最近鄰 當我們生成KD樹以後，就可以去預測測試集裡面的樣本目標點了。對於一個目標點，我們首先在KD樹裡面找到包含目標點的葉子節點。以目標點為圓心，以目標點到葉子節點樣本實例的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。然後返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交，如果相交就到這個子節點尋找是否有更加近的近鄰,有的話就更新最近鄰。如果不相交那就簡單了，我們直接返回父節點的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，演算法結束，此時保存的最近鄰節點就是最終的最近鄰。
3、用KD Tree查找最近鄰實例
from sklearn.neighbors import KDTree import numpy as np np.random.seed(0) X = np.random.random((10, 3)) X
tree = KDTree(X, leaf_size=2) tree
dist, ind = tree.query([X[0]], k=3) print(dist) print(ind)
