KNN 最近鄰搜索：KD 樹 C++ 完整實現與原理詳解

KNN 與 KD 樹

K 近鄰需在訓練集中找到與查詢點最近的 K 個點。線性掃描 O(N) 過慢，KD 樹將 K 維空間遞歸劃分，構建平衡二叉樹，查詢平均 O(log N)。

構建 KD 樹

1. 數據集為空返回空節點；單點創建葉子。
2. 選擇切分維度 `depth % k`，計算該維中位數作為切分值。
3. 以切分值將數據分為左右子集（中位數點作為當前節點）。
4. 遞歸構建左右子樹，`depth+1`。

最近鄰搜索

1. 從根遞歸下降：查詢點在切分超平面哪側就進入哪側子樹，直到葉子，作為「當前最近點」。
2. 回溯時：
   a) 若父節點點更近，更新最近點。
   b) 檢查另一側子樹區域是否與「以查詢點為心、半徑=當前最近距離」的超球體相交。相交則遞歸搜索另一側；不相交則剪枝。
3. 回溯至根結束，返回最近點。

代碼亮點

• 模板支援任意維度 `vector`。
• 轉置矩陣提取切分維數值求中位數。
• 距離函數支援歐氏/曼哈頓可擴展。
• 打印函數可視化樹結構。

示例運行

輸入 6 個二維點，查詢 (3, 4.5)，輸出最近鄰 (2,3) 或 (5,4) 視具體實現。

總結

KD 樹是高維最近鄰搜索的經典數據結構，構建 O(N log N)，查詢平均 O(log N)，但高維（>20）效能下降（維度災難），此時需近似最近鄰（LSH、ANN）。本實現代碼完整、註釋詳盡，適合教學與工程參考。