fc2ブログ

Python 学習:scipy.spatial.KDTree

2015-11-06 :  PCクリニック
先月末(2015-10-28)の記事:
Python 学習:matplotlib.pyplot.hexbin
で書いた、
  ・・・・・
  ・・・・・
  前回(2015-10-24)の記事:
  「
  で出てきた“hexbin”について。
  ・・・・・
  ・・・・・
は、つまりは、
  “Stack Overflow”のQ&A:
  「Generate a heatmap in MatPlotLib using a scatter data set
です。

で、“hexbin”については、回答の 71 番でした。

その後の回答 77 番が“histogram2d”ですね。


その後、もっとページの下の方を見ていたら、・・・・・

回答の 3 番に、
  this answer Efficient method of ・・・ introduced more methods
   about how to do it more efficiently and precisely.
  hope it can helps
とある。
(翻訳すると)
  この答えの不規則な間隔の点の密度を計算する効率的な方法より
  効率的かつ正確にそれを行う方法についてのより多くの方法を導入しました。
  できることを望む
?????

ここにあるリンク先を見ると、
  ・・・・・
  ・・・・・
  My final attempt was to store the data in an KDTree, and ・・・

なる件があった。


“KDTree”って何?
Google 検索:KDTree
で出てくる最初は、
kd木 - Wikipedia」ですね。
  kd木(英: kd-tree, k-dimensional tree)は、
  k次元のユークリッド空間にある点を分類する空間分割データ構造である。
  kd木は、多次元探索鍵を使った探索(例えば、範囲探索や最近傍探索)
  などの用途に使われるデータ構造である。
  kd木はBSP木の特殊ケースである。
  ・・・・・
  ・・・・・

BSP=バイナリ空間分割 ?


バイナリ・ツリー構造=binary tree structure の拡張した様なもの?


scipy.spatial.KDTree - SciPy v0.14.0 Reference Guide
  kd-tree for quick nearest-neighbor lookup

つまり、
  最近傍(最も近いもの)を素早く見つけるためのKD木


・・・・・・・・・・


・・・・・・・・・・


・・・・・・・・・・


結局、
探すのは速くなるが、作るのは難しいですね。
参照したサイト:
最近傍探索のあれこれ 主にk-d tree: 御手洗特急途中下車
  ・・・・・
  ・・・・・
  どうやって空間を二分割するか

  図では簡単のために単純にど真ん中で空間を分割しているが,
  点の座標値の中央値で分割するとk-d treeは平衡木になる.
  平衡木になると探索の計算量がほぼO(log n)になるのでお得.
  全点を対象として中央値を計算すると木の構築に時間がかかるので,
  点をランダムサンプリングして中央値を計算する方法もある.

  高次元にはおすすめできない

  高次元データをk-d treeに展開すると結局ほとんどの点を
  調べることになり,全探索とあまり変わらなくなる.
  k-d treeを採用するときには,
  次元数: d
  点の個数: n
  としたとき
  n >> 2^d となっていることが望ましい.
  ・・・・・
  ・・・・・


本日はここまで。


見ていただいた序でとは厚かましい限りですが、
お帰りに投票して頂けるとなお嬉しいです。 ⇒ blogram投票ボタン


151020
関連記事
スポンサーサイト



コメントの投稿

管理者にだけ表示を許可する

人気blog Ranking



最新記事
カレンダー
02 | 2024/03 | 04
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 - - - - - -
月別アーカイブ
カテゴリ
最新コメント
検索フォーム
リンク
プロフィール

<紙>

Author:<紙>
ようこそ。
「パソコンヲタクの雑記帳」
もろもろなことを綴っています。
パソコン ヲタクってねくら?
画像は kami でなく kani です。

FC2 / i2i / Google




Google Analytics
ブックマーク