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 となっていることが望ましい.
・・・・・
・・・・・
本日はここまで。
見ていただいた序でとは厚かましい限りですが、
お帰りに投票して頂けるとなお嬉しいです。 ⇒
151020
- 関連記事
-
- AutoIt 学習:HotKeySet 関数 (2015/11/21)
- Python 学習:nkf 利用 (2015/11/15)
- Python 学習:3次元散布図 (2015/11/12)
- Python 学習:scipy.ndimage.filters.convolve (2015/11/09)
- Python 学習:scipy.spatial.KDTree (2015/11/06)
- Python 学習:連立方程式を解く (2015/11/03)
- Python 学習:matplotlib.pyplot.hexbin (2015/10/28)
- Python 学習:numpy.histogram2d 関数 (2015/10/24)
- DISCRETE:multi-exponential decay data 解析ツール (2015/10/18)
スポンサーサイト