KD Tree是KNN算法中用于計算最近鄰的快速簡便的構(gòu)建方式。

當(dāng)樣本量少的時候，用brute直接搜索最近鄰的方式是可行的带兜。即計算到所有樣本的距離。但當(dāng)樣本量龐大時吨灭，直接計算所有樣本距離的工作量很大刚照，這種情況使用KD Tree可以節(jié)約大量時間成本。

KD Tree構(gòu)建方式

KD樹采用從m個樣本的n維特征中喧兄，分別計算n個特征取值的方差无畔，用方差最大的第k維特征n_k 作為根節(jié)點(diǎn)。對于這個特征吠冤，選擇取值中的中位數(shù) n_kv 作為樣本的劃分點(diǎn)浑彰，對于小于該值的樣本劃分到左子樹，對于大于等于該值的樣本劃分到右子樹拯辙，對左右子樹采用同樣的方式找方差最大的特征作為根節(jié)點(diǎn)郭变，遞歸產(chǎn)生KD Tree。

為什么要選擇方差最大的進(jìn)行劃分涯保？
構(gòu)建樹的目的是加快我的搜索過程诉濒。
既然我想加快我的搜索過程，要就意味著我最終的數(shù)據(jù)落在某個葉子節(jié)點(diǎn)上遭赂。我希望只需搜索整個二叉樹的某一些列即可循诉，那么最好的劃分方式，就是讓我的每個分支上數(shù)據(jù)的差異性最大化撇他。

那么衡量數(shù)據(jù)差異性的最基礎(chǔ)的數(shù)學(xué)指標(biāo)是什么茄猫？
是方差狈蚤。方差越大，意味著數(shù)據(jù)的離散程度就越大划纽，我將離散程度由大到小的數(shù)據(jù)一分為二脆侮，方差小意味著數(shù)據(jù)更集中到了一起。

KD Tree

示例 KD_Tree的構(gòu)建：

現(xiàn)在有一個二維樣本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}

1勇劣、計算x1和x2每一列對應(yīng)的方差

a靖避、通過pandas計算出的是樣本方差:
/ (n-1)

import numpy as np
import pandas as pd

data = np.array([
        [2,3],
        [5,4],
        [9,6],
        [4,7],
        [8,1],
        [7,2]
    ])

df = pd.DataFrame(data)
df.var()

0| 6.966667
1| 5.366667
dtype: float64

b、通過numpy計算出的是總體方差:
/ n

import numpy as np
import pandas as pd
data = np.array([
        [2,3],
        [5,4],
        [9,6],
        [4,7],
        [8,1],
        [7,2]
    ])
print(data)
mean =np.mean(data,axis = 0)
var = np.var(data,axis = 0)
a_var = np.sum(pow(data-mean,2),axis = 0)/6
print(var)
print(a_var)

[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]

特征空間的劃分

第一個樹的劃分：基于x₁進(jìn)行劃分
[2,4,5,7,8,9]的中位數(shù)是5和7的平均值6比默。
雖然嚴(yán)格意義上說中位數(shù)是6幻捏，但是在計算機(jī)中我們?nèi)藶榈枚xx₁的中位數(shù)是7。

左側(cè)：（2,3）（5,4）（4,7） （7,2）
右側(cè): （9,6）（8,1）

第一次劃分生成的區(qū)域

第二個樹的劃分：根據(jù)右側(cè)（9,6）（8,1）的x₂進(jìn)行劃分

下側(cè)：x₂ ≤ 6；上側(cè)x₂＞6

第二次劃分的區(qū)域

第二個樹的劃分：根據(jù)左側(cè)（2,3）（5,4）（4,7） （7,2）的x₂進(jìn)行劃分

尋找2醋奠、3榛臼、4、7的中位數(shù) 4 進(jìn)行劃分

第三次劃分的區(qū)域

....

注意：每次生成的劃分都是一個矩形窜司。當(dāng)葉子節(jié)點(diǎn)無法被繼續(xù)劃分的時候沛善，KD樹的構(gòu)建完成，遞歸結(jié)束塞祈。

KD Tree查找最近鄰

我們生成了KD Tree后金刁，現(xiàn)在就可以去預(yù)測測試集里面的樣本目標(biāo)點(diǎn)了。

1织咧、對于一個目標(biāo)點(diǎn)胀葱，先在KD樹里找到包含目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)漠秋。

2笙蒙、以目標(biāo)點(diǎn)為圓心，以目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)樣本實(shí)例的距離為半徑庆锦，得到一個超球體捅位，最近鄰的點(diǎn)一定在這個超球體內(nèi)部。

3搂抒、然后返回葉子節(jié)點(diǎn)的父節(jié)點(diǎn)艇搀，檢查另一個子節(jié)點(diǎn)包含的超矩形體是否和超球體相交。

4求晶、如果相交就倒這個子節(jié)點(diǎn)尋找著是否有更加近的近鄰焰雕，有的話就更新最近鄰。

5芳杏、如果不相交矩屁，直接返回父節(jié)點(diǎn)中的父節(jié)點(diǎn)辟宗，在另一個子樹繼續(xù)搜索最近鄰。當(dāng)回溯到根節(jié)點(diǎn)時吝秕，算法結(jié)束泊脐。

6、此時保存的最近鄰節(jié)點(diǎn)就是最終的最近鄰烁峭。

如果現(xiàn)在想找(2,4.5)這點(diǎn)的最近鄰容客，該如何操作？

1约郁、畫出二叉樹：

2缩挑、尋找(2,4.5)這點(diǎn)：

一個比較好的理解方式：首先找到第一個最近鄰，然后畫出一個圓鬓梅。然后逐漸收縮圓的半徑调煎，查看每次縮小后的圓是否能夠和矩形相交于一個更小的最近鄰點(diǎn)，如果有則更新己肮。直到回到根節(jié)點(diǎn)士袄。