在将点添加到节点之前是否预先制作了二进制分区树？
Are binary partition trees premade before points are added to nodes?
我正在尝试在 Python 中实现 this algorithm，但由于我对树结构缺乏了解，我对分区树的创建过程感到困惑。
简要说明:
linked 的算法用于将 high-dimensional 特征 space 划分为内部节点和叶节点，以便可以快速执行查询。
它使用特定的随机测试划分了一个大 space，超平面将一个大单元格一分为二。
This answer explains everything much more precisely.
（取自上面的link）
代码片段:
def random_test(self, main_point): # Main point is np.ndarray instance
dimension = main_point.ravel().size
random_coefficients = self.random_coefficients(dimension)
scale_values = np.array(sorted([np.inner(random_coefficients, point.ravel())
for point in self.points]))
percentile = random.choice([np.percentile(scale_values, 100 * self.ratio), # Just as described on Section 3.1
np.percentile(scale_values, 100 * (1 - self.ratio))])
main_term = np.inner(main_point.ravel(), random_coefficients)
if self.is_leaf():
return 0 # Next node is the center leaf child
else:
if (main_term - percentile) >= 0: # Hyper-plane equation defined in the document
return -1 # Next node is the left child
else:
return 1 # Next node is the right child
self.ratio 如上面的算法 link 所述，它决定了树的平衡和浅度，在 1/2 它应该生成最平衡和浅的树树.
然后我们进入迭代部分，树不断地划分 space 直到它 到达 叶节点（注意关键字 到达)，问题是，它将永远不会真正到达叶节点。
因为上面linked文档中叶节点的定义是这样的：
def is_leaf(self):
return (self.capacity * self.ratio) <= self.cell_count() <= self.capacity
其中 self.cell_count() 是单元格中的点数，self.capacity 是单元格可以拥有的最大点数，self.ratio 是拆分比率。
My full code should basically divide the feature space by creating new nodes at initial iteration until the leaf node is created (but the leaf node is never created). See the fragment that contains the division process.
（摘自 link 上面的文档）
tl;博士：
在我们向它们添加任何点之前是否准备好二叉分区树（用空节点填充）？如果是这样，我们是否需要定义树的级别（深度）？
如果不是，二叉划分树是不是边加点边创建的？如果是这样，那么第一个点（从第一次迭代开始）是如何添加到树中的？
它们是随着您的前进而建造的。第一个节点在第 1 行的右侧或左侧。然后下一个级别询问第 2 行的右侧或左侧...您提供的论文中的插图显示了这一点，其中编号的行与为查找节点而提供的选择相关联。
当然右或左并不准确。一些线被水平切割。但是创建的空间是二进制的。
我已经能够测试评论中提到的新方法，并且效果非常好。
The algorithm that was linked above，隐含声明该点应单独下降到分区树中，通过所有随机测试并在下降时创建新节点。
但是这种方法有一个很大的问题，因为为了有一个平衡的高效和浅树，左右节点必须均匀分布。
因此，为了分裂节点，在树的每一层，节点的每个点都必须传递给左节点或右节点（通过随机测试），直到树达到所有节点的深度该级别的节点是叶节点。
用数学术语来说，根节点包含一个向量space，它被分割成左右两个包含凸多面体的节点，这些凸多面体由分离超平面以支持超平面为界：
方程的负项（我相信我们可以称之为偏差），是分光比开始发挥作用的地方，它应该是100*r到100*(1-r)之间所有节点的百分位数，这样树就更均匀地分开了，也更浅了。基本上它决定了超平面分离应该有多均匀，这就是为什么我们需要包含所有点的节点。
我已经能够实现这样的系统：
def index_space(self):
shuffled_space = self.shuffle_space()
current_tree = PartitionTree()
level = 0
root_node = RootNode(shuffled_space, self.capacity, self.split_ratio, self.indices)
current_tree.root_node = root_node
current_tree.node_array.append(root_node)
current_position = root_node.node_position
node_array = {0: [root_node]}
while True:
current_nodes = node_array[level]
if all([node.is_leaf() for node in current_nodes]):
break
else:
level += 1
node_array[level] = []
for current_node in current_nodes:
if not current_node.is_leaf():
left_child = InternalNode(self.capacity, self.split_ratio, self.indices,
self._append(current_position, [-1]), current_node)
right_child = InternalNode(self.capacity, self.split_ratio, self.indices,
self._append(current_position, [1]), current_node)
for point in current_node.list_points():
if current_node.random_test(point) == 1:
right_child.add_point(point)
else:
left_child.add_point(point)
node_array[level].extend([left_child, right_child])
其中 node_array 包含树的所有节点（根、内部和叶）。
不幸的是，node.random_test(x)方法：
def random_test(self, main_point):
random_coefficients = self.random_coefficients()
scale_values = [np.inner(self.random_coefficients(), point[:self.indices].ravel())
for point in self.points]
percentile = np.percentile(scale_values, self.ratio * 100)
main_term = np.inner(main_point[:self.indices].ravel(), random_coefficients)
if self.is_leaf():
return 0 # Next node is the center leaf child
else:
if (main_term - percentile) >= 0: # Hyper-plane equation defined in the document
return -1 # Next node is the left child
else:
return 1 # Next node is the right child
效率低下，因为计算百分位数需要太多时间。因此，我必须找到另一种方法来计算百分位数（可能通过执行短路二分搜索来优化百分位数）。
结论：
这只是 Clinton Ray Mulligan 的回答的一个很大的扩展——它简要地解释了创建这种树的解决方案，因此将作为一个公认的答案保留下来。
我刚刚添加了更多详细信息，以防有人对实现随机二叉分区树感兴趣。
我正在尝试在 Python 中实现 this algorithm，但由于我对树结构缺乏了解，我对分区树的创建过程感到困惑。
简要说明:
linked 的算法用于将 high-dimensional 特征 space 划分为内部节点和叶节点，以便可以快速执行查询。
它使用特定的随机测试划分了一个大 space，超平面将一个大单元格一分为二。
This answer explains everything much more precisely.
（取自上面的link）
代码片段:
def random_test(self, main_point): # Main point is np.ndarray instance
dimension = main_point.ravel().size
random_coefficients = self.random_coefficients(dimension)
scale_values = np.array(sorted([np.inner(random_coefficients, point.ravel())
for point in self.points]))
percentile = random.choice([np.percentile(scale_values, 100 * self.ratio), # Just as described on Section 3.1
np.percentile(scale_values, 100 * (1 - self.ratio))])
main_term = np.inner(main_point.ravel(), random_coefficients)
if self.is_leaf():
return 0 # Next node is the center leaf child
else:
if (main_term - percentile) >= 0: # Hyper-plane equation defined in the document
return -1 # Next node is the left child
else:
return 1 # Next node is the right child
self.ratio 如上面的算法 link 所述，它决定了树的平衡和浅度，在 1/2 它应该生成最平衡和浅的树树.
然后我们进入迭代部分，树不断地划分 space 直到它 到达 叶节点（注意关键字 到达)，问题是，它将永远不会真正到达叶节点。
因为上面linked文档中叶节点的定义是这样的：
def is_leaf(self):
return (self.capacity * self.ratio) <= self.cell_count() <= self.capacity
其中 self.cell_count() 是单元格中的点数，self.capacity 是单元格可以拥有的最大点数，self.ratio 是拆分比率。
My full code should basically divide the feature space by creating new nodes at initial iteration until the leaf node is created (but the leaf node is never created). See the fragment that contains the division process.
（摘自 link 上面的文档）
tl;博士：
在我们向它们添加任何点之前是否准备好二叉分区树（用空节点填充）？如果是这样，我们是否需要定义树的级别（深度）？
如果不是，二叉划分树是不是边加点边创建的？如果是这样，那么第一个点（从第一次迭代开始）是如何添加到树中的？
它们是随着您的前进而建造的。第一个节点在第 1 行的右侧或左侧。然后下一个级别询问第 2 行的右侧或左侧...您提供的论文中的插图显示了这一点，其中编号的行与为查找节点而提供的选择相关联。
当然右或左并不准确。一些线被水平切割。但是创建的空间是二进制的。
我已经能够测试评论中提到的新方法，并且效果非常好。
The algorithm that was linked above，隐含声明该点应单独下降到分区树中，通过所有随机测试并在下降时创建新节点。
但是这种方法有一个很大的问题，因为为了有一个平衡的高效和浅树，左右节点必须均匀分布。
因此，为了分裂节点，在树的每一层，节点的每个点都必须传递给左节点或右节点（通过随机测试），直到树达到所有节点的深度该级别的节点是叶节点。
用数学术语来说，根节点包含一个向量space，它被分割成左右两个包含凸多面体的节点，这些凸多面体由分离超平面以支持超平面为界：
方程的负项（我相信我们可以称之为偏差），是分光比开始发挥作用的地方，它应该是100*r到100*(1-r)之间所有节点的百分位数，这样树就更均匀地分开了，也更浅了。基本上它决定了超平面分离应该有多均匀，这就是为什么我们需要包含所有点的节点。
我已经能够实现这样的系统：
def index_space(self):
shuffled_space = self.shuffle_space()
current_tree = PartitionTree()
level = 0
root_node = RootNode(shuffled_space, self.capacity, self.split_ratio, self.indices)
current_tree.root_node = root_node
current_tree.node_array.append(root_node)
current_position = root_node.node_position
node_array = {0: [root_node]}
while True:
current_nodes = node_array[level]
if all([node.is_leaf() for node in current_nodes]):
break
else:
level += 1
node_array[level] = []
for current_node in current_nodes:
if not current_node.is_leaf():
left_child = InternalNode(self.capacity, self.split_ratio, self.indices,
self._append(current_position, [-1]), current_node)
right_child = InternalNode(self.capacity, self.split_ratio, self.indices,
self._append(current_position, [1]), current_node)
for point in current_node.list_points():
if current_node.random_test(point) == 1:
right_child.add_point(point)
else:
left_child.add_point(point)
node_array[level].extend([left_child, right_child])
其中 node_array 包含树的所有节点（根、内部和叶）。
不幸的是，node.random_test(x)方法：
def random_test(self, main_point):
random_coefficients = self.random_coefficients()
scale_values = [np.inner(self.random_coefficients(), point[:self.indices].ravel())
for point in self.points]
percentile = np.percentile(scale_values, self.ratio * 100)
main_term = np.inner(main_point[:self.indices].ravel(), random_coefficients)
if self.is_leaf():
return 0 # Next node is the center leaf child
else:
if (main_term - percentile) >= 0: # Hyper-plane equation defined in the document
return -1 # Next node is the left child
else:
return 1 # Next node is the right child
效率低下，因为计算百分位数需要太多时间。因此，我必须找到另一种方法来计算百分位数（可能通过执行短路二分搜索来优化百分位数）。
结论：
这只是 Clinton Ray Mulligan 的回答的一个很大的扩展——它简要地解释了创建这种树的解决方案，因此将作为一个公认的答案保留下来。
我刚刚添加了更多详细信息，以防有人对实现随机二叉分区树感兴趣。