基于KD樹的KNN算法優(yōu)化
一、介紹
KD樹是一顆二叉樹，是對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)
KNN最簡單的實現(xiàn)是線性掃描，每個測試樣本都要與所有訓(xùn)練樣本計算距離。當(dāng)數(shù)據(jù)量很大時，計算非常耗時，為了提高搜索效率，使用樹形結(jié)構(gòu)存儲訓(xùn)練集來減少計算距離的次數(shù)。通過選擇不同維度對空間劃分，以選擇訓(xùn)練實例在選定維度上的中位數(shù)為劃分點。
最簡單的KD樹也就是常見的二叉排序樹，此時的K=1，劃分維度也只有一個。
以 [5, 7]，[3, 8]，[6, 3]，[8, 5]，[15, 6]，[10, 4]，[12, 13]，[9, 10]，[11, 14] 為例，一顆二維KD樹如下圖所示：
首先，將所有的樣本排序，關(guān)鍵字為第0個維度，取中位數(shù)作為根節(jié)點
其次，將剩下的兩個部分，依次作為根節(jié)點的左右子樹
最后，左右子樹的建立就和重新建立一顆樹一樣，由遞歸調(diào)用完成
那么KD樹是如何提高搜索效率?
其實道理就和二叉排序樹相同，例如我們在二叉排序樹上找一個小于根節(jié)點的數(shù)，只需要在左子樹里面搜索即可。KD樹通過不同維度的劃分來在每一個維度上構(gòu)建了類似的二叉排序樹，通過判斷來排除右子樹是否還需要遍歷。
但是這時候有人會有疑問，某個節(jié)點只是在某一維度上有序，但是我們需要衡量的是節(jié)點到測試樣本點的距離，如果在這一維度上我們舍棄了某個點，但由于在其他維度上離樣本點很接近導(dǎo)致這個點也有可能是距離比較小的點。其實這里KD樹會在遍歷的時候不斷記錄和更新K個最近點（這里的K是KNN中的K并非KD Tree中的K），如果當(dāng)前遍歷的節(jié)點在當(dāng)前維度上離測試樣本點的距離小于K個最近點中最遠的那個點到測試樣本點的距離，那么我們會考慮右子樹上可能有更近的點，但是如果在當(dāng)前維度上離測試樣本點的距離大于K個最近點中最遠的那個點到測試樣本點的距離，那說明右子樹中不可能有更近的點，此時就可以舍棄右子樹的點。
二、KD Tree的創(chuàng)建
1. 節(jié)點數(shù)據(jù)結(jié)構(gòu)
2.?樹的創(chuàng)建
