一、什麼是最近鄰類算法
最近鄰類算法（Nearest Neighbor, NN） 的核心問題是：
在給定空間中，找到與目標樣本“距離最近”的一個或多個樣本。
形式化描述：
- 已知數據集：( D = {x_1, x_2, ..., x_n} )
- 給定查詢點：( q )
- 定義距離函數：( dist(x, q) )
目標：
- 最近鄰（NN）：找到 ( \arg\min dist(x_i, q) )
- K 最近鄰（KNN）：找到距離最小的 K 個樣本
二、距離度量（算法基礎）
最近鄰算法的靈魂不是搜索，而是距離定義。
1. 常見距離函數
| 距離 | 公式 | 適用場景 | ||||
|---|---|---|---|---|---|---|
| 歐氏距離 | ( \sqrt{\sum (x_i-y_i)^2} ) | 連續數值特徵 | ||||
| 曼哈頓距離 | ( \sum | x_i-y_i | ) | 網格/路徑 | ||
| 餘弦距離 | ( 1-\frac{x·y}{ | x | y | } ) | 向量相似度 | |
| 漢明距離 | 不同位數 | 二進制/編碼 |
工程實踐中，80% 的效果來自特徵和距離選擇，而非算法本身。
三、樸素最近鄰（暴力法）
1. 算法思想
- 對查詢點 q
- 計算其與所有樣本的距離
- 排序或維護最小堆
2. 時間複雜度
- 單次查詢：
O(n · d) - 空間複雜度：
O(1)
3. 優缺點
優點：
- 實現簡單
- 無訓練成本
缺點：
- 數據量大時極慢
- 無法在線高頻查詢
數據量 < 1 萬時，暴力法依然是最優解。
四、KNN 算法（分類 / 迴歸）
1. 基本流程
- 計算 q 與所有樣本距離
- 選取最近的 K 個
- 分類：多數投票
- 迴歸：均值 / 加權均值
2. K 的選擇
- K 小：對噪聲敏感
- K 大：邊界模糊
經驗值：
K ≈ sqrt(n)
3. 特點總結
- 懶惰學習（Lazy Learning）
- 無模型、無參數
- 強依賴數據分佈
五、空間加速結構（精確最近鄰）
1. KD-Tree
歸類：數據結構 + 搜索算法
原理
- 按維度遞歸劃分空間
- 二叉樹結構
特點
- 構建複雜度：
O(n log n) - 查詢平均：
O(log n) - 高維退化為 O(n)
適用：
- 低維（≤ 20 維）
2. Ball Tree
- 使用超球體劃分空間
- 對非歐氏距離友好
比 KD-Tree 更穩健，但構建更復雜。
六、近似最近鄰（ANN，工業主流）
當數據規模達到百萬 / 億級：
精確最近鄰在工程上不可行
1. 核心思想
- 放棄“絕對最近”
- 換取數量級性能提升
2. 主流 ANN 算法
（1）LSH（局部敏感哈希）
- 相似樣本高概率落入同一桶
- 適合高維稀疏數據
（2）HNSW（主流）
- 分層小世界圖
- 搜索複雜度接近
O(log n)
工業事實：
向量檢索領域事實標準
（3）FAISS
- Facebook 開源
- 多種 ANN 算法封裝
- 支持 GPU
七、算法對比總結
| 算法 | 精度 | 速度 | 規模 | 是否工業級 |
|---|---|---|---|---|
| 暴力 NN | 100% | 慢 | 小 | ❌ |
| KD-Tree | 100% | 中 | 中 | ⚠️ |
| LSH | 近似 | 快 | 大 | ✅ |
| HNSW | 高 | 極快 | 極大 | ✅ |
