kd木とは – 多次元検索を高速化する空間インデックス
概要
- kd木 (k‑d tree) は k 次元 の点データを高速に検索するための 空間インデックス
- 再帰的な二分割で空間を整理し、範囲検索・最近傍探索などを平均 O(log n) で実現
- k 近傍法や点群処理、ゲームの衝突判定など、あらゆる「距離計算がボトルネック」になる場面で威力を発揮
キーワード: 空間分割, 二分探索, 最近傍探索, 次元の呪い
kd木の基本概念
-
構築手順
- ①
k次元のうち 分散が最大 などの基準で軸を選択 - ② 軸上の中央値でデータを左右に分割
- ③ 部分集合ごとに再帰 … 葉 には少数点を保持
- ①
-
ノード情報
- 分割軸 (例: x, y, z…)
- 分割値 (軸上のしきい値)
- 境界ボックス (BBox) – 枝刈り計算に使用
-
探索アルゴリズムの肝
- 検索点からまず“近そう”な枝へ降下
- 必要に応じ もう一方の枝 を距離上界で枝刈り
- 高次元になるほど枝刈り率が低下 → “次元の呪い”
図1: 2 次元 kd 木の分割イメージ
代表的ユースケース
-
k‑NN 推論の高速化
- scikit‑learn で
algorithm="kd_tree"を指定すると内部で自動使用
- scikit‑learn で
-
3D 点群処理 (LiDAR, Photogrammetry)
- 近傍探索をフルスキャンごとに行う場合、平面探索より 10–100× 高速化
-
ゲーム / 物理シミュレーションの衝突判定
- 移動オブジェクトの空間インデックスとして BVH 代わりに採用
-
レコメンド候補の絞り込み
- ユーザ埋め込みベクトルの類似検索で HNSW や Annoy が重い時の軽量代替
Python で触ってみる
import numpy as np
from scipy.spatial import KDTree
# 100 万点・3 次元のダミーデータ
pts = np.random.rand(1_000_000, 3)
kd = KDTree(pts) # kd 木構築 (≈ O(n log n))
query = np.array([0.1, 0.2, 0.3])
# 5 近傍検索
dists, idxs = kd.query(query, k=5)
print(dists)
print(pts[idxs])
ワンポイント: sklearn.neighbors.KDTree も同等仕様で、
from sklearn.neighbors import KDTree
kdt = KDTree(pts, leaf_size=40) # leaf_size で枝刈り効率が変わる
kd木・k 近傍・決定木を使い分ける
| 視点 | kd木 | k‑NN | 決定木 |
|---|---|---|---|
| 主な役割 | 多次元点集合の高速検索インデックス | 距離に基づく分類・回帰アルゴリズム | 条件分岐で特徴を分割して予測する教師ありモデル |
| 構築 / 学習 | 非教師あり (中央値分割などで木を構築) | Lazy 学習 (学習時は保存のみ) | 教師あり (情報利得・ジニ不純度で最適分割を学習) |
| 分割・判定基準 | 座標値 (幾何的) | 距離計算 (ユークリッドなど) | ラベル純度指標 |
| 出力 | 点のインデックス・距離 | 近傍のラベル多数決 / 平均値 | 予測ラベル / 数値 |
| 推論計算量 | 平均 O(log n) | 平均 O(k log n) (kd木利用時) | 木深さ O(depth) |
| 高次元での性能 | 悪化 (次元の呪い) | 悪化 (距離が集中) | 比較的安定 (ただし過学習注意) |
| 代表実装 |
scipy.spatial.KDTree, sklearn.neighbors.KDTree
|
sklearn.KNeighbors* (内部で kd木/ball-tree/Brute) |
sklearn.tree.DecisionTree* |
Tip: 実運用では k‑NN の近傍探索エンジンとして kd木を指定 (
algorithm="kd_tree") することで、数十〜数百倍の高速化が期待できます。
まとめ & 実践 Tips
- leaf_size を調整: 小さすぎると深くなり再帰コスト↑、大きすぎると葉内探索が重い – 経験則: 20–50
- 距離計算をカスタム: kd 木は L₂ が前提。コサイン類似度なら点を正規化してユークリッド距離として扱う
- 次元の呪い対策: PCA や AutoEncoder で前処理 → kd 木の枝刈り率を復活
- 動的データ: 頻繁な挿入・削除が必要なら Balanced kd tree や Approximate NN を検討
kd木は“木”と名が付くが分類モデルではなく、検索エンジン。 目的に応じて k‑NN や決定木と組み合わせ、距離計算コストを最小化しよう。
おわりに
実業務で k‑NN や近傍探索がボトルネックになったら、まず kd 木を試してみる価値は大きい。少ないコード変更でレスポンスが数十倍改善することも珍しくない。ぜひ手元でベンチマークしてみてほしい。