質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

機械学習

機械学習は、データからパターンを自動的に発見し、そこから知能的な判断を下すためのコンピューターアルゴリズムを指します。人工知能における課題のひとつです。

Q&A

解決済

1回答

755閲覧

KDTree内の木を確認したい

nobodytolove123

総合スコア61

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

機械学習

機械学習は、データからパターンを自動的に発見し、そこから知能的な判断を下すためのコンピューターアルゴリズムを指します。人工知能における課題のひとつです。

0グッド

0クリップ

投稿2019/11/25 05:40

お世話になります。

現在、sklearn.neighbors.NearestNeighborsというAPIを使って最近旁探索の機能を作成しています。

NearestNeighborsalgorithmパラメーターにkd_treeを指定して、検索の効率化を図っていますが
kd木内がどの様に構築されているのかが確認出来ません。

sklearn.tree.DecisionTreeClassifiersklearn.tree.plot_treeの様に可視化はできないものなのでしょか?

一応KDTree(X).__getstate__()で内部で保持している値は取得はできるのですが、何を意味しているのかは分かりません。

可視化は出来なくとも、木がどの様に分かれているのかは確認したいです...

投げやり気味になってしまい申し訳ございませんが、ご回答の程お願い致します。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

ソースコードのコメントを見ると、木構造は KDTree オブジェクトの node_data 属性に格納されている1次元配列で管理されているようです。

コメントによると、KDTree.node_data[0] がルートノードで、ノード KDTree.node_data[i] の2つの子ノードは KDTree.node_data[2 * i + 1] 及び KDTree.node_data[2 * i + 2] を参照すればよいようです。

KDTree.node_data の各要素の意味等はソースコードのコメント等を見てください。(3000行ぐらいあり、全部は読んでないので実装の細部まではわかりません。)

KDTree クラスは BinaryTree クラスを継承しているので、以下の2つが該当のコードです。

# In a typical KD Tree or Ball Tree implementation, the nodes are implemented # as dynamically allocated structures with pointers linking them. Here we # take a different approach, storing all relevant data in a set of arrays # so that the entire tree object can be saved in a pickle file. For efficiency, # the data can be stored in such a way that explicit pointers are not # necessary: for node data stored at index i, the two child nodes are at # index (2 * i + 1) and (2 * i + 2); the parent node is (i - 1) // 2 # (where // indicates integer division).

1次元配列を木構造にして確認する格納するコード

python

1# 木構造の可視化に anytree という外部ライブラリを使っています。 2# pip install anytree でインストールできます。 3import numpy as np 4from anytree import Node, RenderTree 5from sklearn.neighbors import KDTree 6 7np.random.seed(0) 8X = np.random.randint(0, 101, (20, 2)) 9 10tree = KDTree(X, leaf_size=2) 11 12 13def tarverse(i=0, parent=None): 14 node = Node(i, parent) 15 16 if i * 2 + 1 < len(tree.node_data): 17 tarverse(i * 2 + 1, node) 18 tarverse(i * 2 + 2, node) 19 20 return node 21 22 23tree = tarverse() 24print(RenderTree(tree))
Node('/0') ├── Node('/0/1') │ ├── Node('/0/1/3') │ │ ├── Node('/0/1/3/7') │ │ └── Node('/0/1/3/8') │ └── Node('/0/1/4') │ ├── Node('/0/1/4/9') │ └── Node('/0/1/4/10') └── Node('/0/2') ├── Node('/0/2/5') │ ├── Node('/0/2/5/11') │ └── Node('/0/2/5/12') └── Node('/0/2/6') ├── Node('/0/2/6/13') └── Node('/0/2/6/14')

投稿2019/11/25 09:09

tiitoi

総合スコア21956

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

nobodytolove123

2019/11/26 06:39

ご連絡遅くなってしまい申し訳ございません。 ご回答ありがとうございます! とても参考になります、ソースの確認まで、、、 ありがとうございます!!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問