Я смог протестировать новый метод, как упомянуто в комментариях, и он отлично работал.
Алгоритм, который был связан выше , неявно утверждает, что точка должнабыть индивидуально выпадающим в дерево разделов, проходя все случайные тесты и создавая новые узлы по мере его выпадения.
Но есть существенная проблема с этим методом, поскольку для обеспечения сбалансированногоэффективное и неглубокое дерево, левый и правый узлы должны быть распределены равномерно.
Следовательно, чтобы разделить узел, на каждом уровне дерева каждая точка узла должна быть передана либо левому, либо правому узлу (путем случайного теста), пока дерево не достигнет глубины, гдевсе узлы на этом уровне являются листовыми.
В математических терминах корневой узел содержит векторное пространство, которое разделено на два левых и правых узла, содержащих выпуклые многогранники, ограниченные опорными гиперплоскостями разделяющей гипер-плоскость:
Отрицательный член уравнения (я думаю, что мы можем назвать его смещением), где соотношение проигрывания начинает играть, оно должно бытьпроцентиль всех узловых точек от 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
неэффективен, поскольку вычисление процентиля занимает слишком много времени.Следовательно, мне нужно найти другой способ вычисления процентиля (возможно, путем выполнения короткого двоичного поиска для оптимизации процентиля).
Заключение:
Это просто большое продолжение ответа Клинтона Рэя Маллигана - которое кратко объясняет решение для создания таких деревьев и, следовательно, останется в качестве принятого ответа.
Я только что добавил больше подробностей на случай, если кто-то заинтересован в реализации рандомизированных бинарных деревьев разделов.