KDTree内の木を確認したい

Question

お世話になります。

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

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

sklearn.tree.DecisionTreeClassifierをsklearn.tree.plot_treeの様に可視化はできないものなのでしょか？

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

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

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

Answer 1

ソースコードのコメントを見ると、木構造は 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つが該当のコードです。

• scikit-learn/_binary_tree.pxi
• scikit-learn/_kd_tree.pyx

# 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次元配列を木構造にして確認する格納するコード

# 木構造の可視化に anytree という外部ライブラリを使っています。
# pip install anytree でインストールできます。
import numpy as np
from anytree import Node, RenderTree
from sklearn.neighbors import KDTree

np.random.seed(0)
X = np.random.randint(0, 101, (20, 2))

tree = KDTree(X, leaf_size=2)


def tarverse(i=0, parent=None):
    node = Node(i, parent)

    if i * 2 + 1 < len(tree.node_data):
        tarverse(i * 2 + 1, node)
        tarverse(i * 2 + 2, node)

    return node


tree = tarverse()
print(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')

Comments

[nobodytolove123]

ご連絡遅くなってしまい申し訳ございません。
ご回答ありがとうございます！

とても参考になります、ソースの確認まで、、、
ありがとうございます！！！