10万個の点から一番近い点を見つける 〜KD treeを例とした効率的なアルゴリズムの設計〜

2024年12月17日、VRChatの技術イベント「CS集会」での発表スライドです。
※ CSとはComputer Scienceのことです！

一見簡単な問題でも、単純な計算方法では計算量が爆発して解けなくなってしまう問題を例にし、
クイズも交えてKD treeのような分割法がなぜ有用なのかを解説しています。

その上で、最後に大胆などんでん返しがあります！

Transcript

1. 10万個の点から 一番近い点を見つける 〜KD treeを例とした効率的なアルゴリズムの設計〜 (x) (y) Level 1: x軸で分割 Level 2: y軸で分割 Level 3: x軸で分割 x=250 Root x=150 左部分⽊ x=350 右部分⽊ x=80 (80,300) x=180 (180,350) x=300 (300,150) x=400 (400,200) x=50 (50,100) x=100 (100,200) x=40 葉 x=60 葉 同様の分割を繰り返し
2. 📝自己紹介 😊 さめ(meg-ssk) 🧑‍💻 フリーランスのソフトウェアエンジニア 得意分野: 📸 コンピュータビジョン (画像認識/ 点群処理) 🌍 空間情報処理 (GIS/リモートセンシ ング) ☁️ クラウドインフラ設計/IaC (AWS) GitHub: Speaker Deck: LinkedIn: s-sasaki-earthsea-wizard syotasasaki593876 syota-sasaki-878901320
3. 問題提起: 一番近い点はどれ？ 平面上に4つの点があります (A, B, C, D) 点Aに一番近いのはどの点でしょ う？ 点Bに一番近いのはどの点でしょ う？ 点Cに一番近いのはどの点でしょ う？ 点Dに一番近いのはどの点でしょ う？ すべての点の一番近い点を計算す るには？ A B C D
4. 📏 シンプルな解き方 点Aに一番近い点を探す AB, AC, ADの長さ(ノルム)を計算す る 言うなれば「定規で長さを測る」 あとはこの中の最小値を選べばOK！ 合計3回の計算で解決！ A B C D min(||𝐴𝐵||, ||𝐴𝐶||, ||𝐴𝐷||)
5. 🔁📏 長さを測ることを繰り返す 点Bに一番近い点を探す BC, BDの長さを計算する BAの長さはすでに計算済み A B C D 合計2回の計算で解決！ 点Cに一番近い点を探す CDの長さを計算する CA, CBの長さはすでに計算済み A B C D 合計1回の計算で解決！ 3回 + 2回 + 1回 = 6回の計算で解決！ なんだ簡単じゃん！めでたしめでたし！ ...ではない！
6. 💥計算量の爆発 点の数が10万個になったら？ 点Aに一番近い点を計算するためには99,999回の 計算が必要 点Bに一番近い点を計算するためには99,998回の 計算が必要 (以下略...) 合計約50億回の計算が必要！ 💥 計算量が爆発する！ ❌💻 現実的な時間、計算リソースでは計算不可能！ ❌🕰️ リアルタイムでの計算は不可能！ 🤔 もっと賢く計算できないかな？
7. ⁉️ 😮 突然ですがクイズです！ 4本のワインがあります 🍷🍷🍷🍷 その中に毒入りワインが1本あります 🍷☠️ 飲んでから1日後に毒の効果が現れます 🍷🤮 毒入りワインを見つけるためには何人の毒見係が必 要? 🧑‍🤝‍🧑👭 4人以下の毒見係で毒入りワインを見つける方法があります! 🙋 有名なクイズなので、答えを知ってる人は手を挙げてください!
8. 👩🏼 答え: 2人 👨🏾‍🦲 👩🏼アリスと 👨🏾‍🦲ボブの2人が毒見係をします 以下の左の表のように2人がワインを飲みます 👩🏼 👨🏾‍🦲 🍷1 ⭕️ ⭕️ 🍷2 ⭕️ ❌ 🍷3 ❌ ⭕️ 🍷4 ❌ ❌ 1日後... 👩🏼☠️ かつ 👨🏾‍🦲☠️ → 🍷1 が ☠️ 👩🏼☠️ かつ 👨🏾‍🦲✅ → 🍷2 が ☠️ 👩🏼✅ かつ 👨🏾‍🦲☠️ → 🍷3 が ☠️ 👩🏼✅ かつ 👨🏾‍🦲✅ → 🍷4 が ☠️
9. ワインが8本に増えたら？ 🍷 x 8 3人の毒見係( 👩🏼👨🏾‍🦲👨🏼‍🦰)で毒ワイン 🍷☠️を特定できる 👩🏼 👨🏾‍🦲 👨🏼‍🦰 🍷1 ⭕️ ⭕️ ⭕️ 🍷2 ⭕️ ⭕️ ❌ 🍷3 ⭕️ ❌ ⭕️ 🍷4 ⭕️ ❌ ❌ 🍷5 ❌ ⭕️ ⭕️ 🍷6 ❌ ⭕️ ❌ 🍷7 ❌ ❌ ⭕️ 🍷8 ❌ ❌ ❌ まったく同じ方法で: 16本のワイン 🍷x16 4人の毒味係で毒ワイン 🍷☠️を 発見可能 32本のワイン 🍷x32 5人の毒味係で毒ワイン 🍷☠️を 発見可能 🤔 10万本の 🍷があったら？
10. n人の毒見係がいれば 2n本のワインを毒見できる 組み合わせの工夫でn人の毒見係がいれば2n本のワ インから1本の毒入りワインを発見できる 10万本のワインがあっても、17人の毒見係がいれ ば1本の毒入りワインを発見できる！ 217 = 131072 > 100000 少ない人数で多くのワインを毒見できる! 効率的な毒見係の配置が重要! 🤔これを応用して、10万個の点の中から一番近い点を探す方法は ないかな？
11. 効率化の鍵: KD Tree 🌳✂️ 🌿 x軸に平行な線で空間を分割！ 1回の分割でおおまかに候補を半分に絞り込める！ Query Point First Split (x-axis) 🤔 この分割を繰り返したらどうなる？ 💡 候補がどんどん減って、より効率的な探索ができそう！
12. 分割のチカラ 全探索: 12点から最近傍を求める場合、 11回の距離計算が必要 KD-treeでの探索 (理想的なケース): 軸方向に沿った分割で探索候補を 大幅に減らせる Query Point First Split (x-axis) Second Split (y-axis) Third Split (x-axis) わずか3回の分割で最も近い点がわかった！
13. ➖ 引き算型 vs ➗ 割り算型 引き算型(線形探索): 1回の計算で「候補を1つずつ」し か減らせない 10万個の候補点があれば10万回 もチェックを繰り返す すべてのペアを計算: 10万x10万/2 = 約50億回の計 算 😨 割り算型(KD-Treeでの探索): 1回の分割で候補を約半分に減ら せる 10万個が1回で約5万個、2回 で約2万5千個… わずか17回で探索終了 ✅ すべてのペアを計算: 10万+10万/2+10万/4+10 万/8+ ... = 約20万回の計算 😊 候補が引き算で減る vs 候補が割り算で減る 分割を繰り返すほど、探索範囲が爆発的に縮む (理想的には!) 割り算で減らしていく方が圧倒的に速い
14. 計算量と Big-O 記号 全探索: n個の点がある場合、すべてのペ ア(n×n)を調べるから O(n2) ここで O(...) はnに対する計算 量の増え方の目安 (Big-O 記号) KD-Tree(理想的な場合): 分割を重ねて候補を絞るから、平 均的に O( n log n) nが大きくなっても、全探索よ りずっと速くなる
15. ☐ 平面から空間へ 🗳️ KD-Treeは、R2(2次元)だけでなく、 R3(3次元)に も拡張可能 分割する平面を交互に変えながら、3次元空間を効 率的に絞り込む 3次元: y-z平面 → z-x平面 → x-y平面 → y-z平面 → ... でサイクリックに平面で分割 3Dデータの解析などで威力を発揮！ 筆者は普段のお仕事でよく使ってます！
16. さらなる高次元へ 🚀 KD-treeはRd(d次元)にも拡張可能！ 超平面H0 → H1 → ... → Hd → H0 → ... で分割 高次元空間の探索でこそ、KD-Treeの真価が発揮される! : ( ) ⋅ = 𝐻0 , , . . . , 𝑥1 𝑥2 𝑥𝑑 𝑤0 → 𝑏0 : ( ) ⋅ = 𝐻1 , , . . . , 𝑥0 𝑥2 𝑥𝑑 𝑤1 → 𝑏1 ⋮ : ( ) ⋅ = 𝐻𝑑 , , . . . , 𝑥0 𝑥1 𝑥𝑑−1 𝑤𝑑 → 𝑏𝑑
17. 🌳😣 KD-treeが苦手な場面 一直線に並んだ点 -・-・-・-・- 全探索と同じ O(n2) の計算量に 📈 現実の3Dデータでは局所的に点が一直線に並 ぶことは十分あり得る 🏢ビル、 🛣️道路、 🏞️堤防、などの人工構造物 横方向の分割に意味がない！縦方向の分割だけでは全探索と同じ！ KD treeは一様分布のデータに最適化されている
18. 🌳🔍 KD-treeの応用例 1. 点群データ解析 3DスキャンやLiDARデータの効率的な解析 点群の間引き、ノイズ除去 2. 特徴量ベクトルの類似度 趣味や好みの近いユーザーの探索 画像の類似度計算 3. Hausdorff距離の計算 機械学習モデルのトレーニングの損失関数 物体の形状比較
19. アルゴリズムの現実的な使い方 😮‍💨新しいアルゴリズムを作るのは本 当に大変 正しさの証明 性能の評価 アイディアの独自性 そもそも新しいアルゴリズムを開発 すれば自分の名前がつくレベルの難 しさ！ エドガー・ダイクストラの"ダイク ストラ法" カジミェシュ・クラワトスキの"ク ラワトスキ定理" ティム・ピーターズの"ティムソー ト" ✨既存のアルゴリズムの宝庫を活用 しよう 自分の課題に使えるアルゴリズム があるはず！ アルゴリズムの理論的な背景を知 っておくに越したことはない... でもただ単に使うだけならコピペ でOK！ 豊富なサンプルコードと応用例 コピペを恥じる必要はない！
20. 🎁 現代のエンジニアの強み 充実したライブラリ scikit-learn: 統計 / データ分析 / 機械学習 SciPy: 科学技術計算 NetworkX: ネットワーク解析 / グラフ理論 OpenCV: 画像処理 実装済みの高品質なコード ドキュメントや応用例が豊富！ サンプルコードも充実！ 多くのユーザーによるフィードバック テスト済み
21. 🌟 まとめ: 宝物は足元にある KD-treeを例に見てきたこと: 単純な全探索 → 賢い分割で効率化 理想的な場合は劇的な性能向上 不得意なケースを理解して適切な使い分け 先人の知恵を活用しよう！ アルゴリズムの宝庫が既にそこにある 実装済みライブラリを有効活用 異分野のアイディアを組み合わせる (適切に)パクリまくるのは恥ずかしくない！ 一緒に宝物を探しに行きましょう！ 🤝🚀🎉