Работаю с деревьями решений sklearn: DecisionTreeClassifier. Под капотом модели деревья реализованы следующим образом: деревья однозначно идентифицируются целыми числами и имеются следующие характеристики представляющие их взаимосвязь графов:
- children_left = np.array([1, -1, 3, 5, -1, -1, -1]) # индексы левых потомков
- children_right = np.array([2, -1, 4, 6, -1, -1, -1]) # индексы правых потомков
- feature = np.array([1, -2, 2, 3, -2, -2, -2]) # номер сравниваемой колонки входящей инфы
- threshold = np.array([0.8, -2, 0.7, 4.2, -2, -2, -2]) # величина сравниваемого значения
Параметры выше представлены в виде numpy массивов: на нулевой позиции находятся характеристики нулевой (корневой вершины), то есть левый потомок имеет индекс вершины - 1, правый - 2, индекс сравниваемой колонки - 1, значение с чем сравниваем 0,8. Числа -1 и -2 в массивах намекают на то, что эти вершины являются висячими узлами (далее по тексту - листья). Уже написан большой кусок кода, принимающий на вход полное дерево. И задача, за помощью с которой я обращаюсь к сообществу заключается в приведении неполного дерева к полному .
Нужно реализовать функцию которая на вход принимает дерево и глубину, к которому надо это дерево привести. Алгоритм работы следующий:
- Найти количество вершин полного дерева, по сумме элементов геометрической прогрессии: 2*(2**depth - 1) + 1
- Подготовить соответствующие параметры для заполнения полного дерева: children_left, children_right, feature, threshold. Длина массивов каждого из которых равна длине вершин полного дерева - 1 (2*(2**depth - 1))
- Найти все листья;
- Найти к какой глубине соответствует каждый лист;
- Итерироваться по листьям и до тех пор пока не достигнута требуемая глубина, создать новую вершину и прицепить к нему лист (если левый - то левому, правый - правому). Индекс новых вершин начинать с количества вершин неполного дерева - 1
- Новая создаваемая вершина копирует свойства родителя листа;
Картинка дерева:
Ниже приведен код, который должен реализовать описанный алгоритм, что-то я делаю не так:
from collections import OrderedDict
from typing import Dict, List, Optional
import numpy as np
# INPUTS
left_children = np.array([1, -1, 3, 5, -1, -1, -1])
right_children = np.array([2, -1, 4, 6, -1, -1, -1])
features = np.array([1, -2, 2, 3, -2, -2, -2])
thresholds = np.array([0.8, -2, 0.7, 4.2, -2, -2, -2])
# OUTPUTS
Это ожидаемый результат (индексы могут различаться, но колонки не должны)
new_left_children = np.array([7, -1, 3, 5, -1, -1, -1, 8, 1, 11, -1, -1, -1, 14, -1])
new_right_children = np.array([2, -1, 13, 6, -1, -1, -1, 9, 10, 12, -1, -1, -1, 4, -1])
new_features = np.array([1, -2, 2, 3, -2, -2, -2, 1, 1, 1, -2, -2, -2, 2, -2])
new_thresholds = np.array([0.8, -2, 0.7, 4.2, -2, -2, -2, 0.8, 0.8, -0.8, -2, -2, -2, 0.7, -2])
class Tree:
def __init__(self, lefts, rights, feature, threshold, value):
self.children_left = lefts
self.children_right = rights
self.feature = feature
self.threshold = threshold
self.value = value
self.leaves = np.argwhere(self.children_left == -1).squeeze(axis=1)
self.nodes = np.argwhere(self.children_left != -1).squeeze(axis=1)
@property
def leaf_to_path_mapper(self) -> Dict[int, List[int]]:
"""
The method returns a ordered dictionary where the key is the
index of the leaf and the value is the list of indices
of nodes showing the path to the root of tree
{leaf_idx: [node_idx0, node_idx1, ...], ...}
:return: {leaf_idx: [node_idx0, node_idx1, ...], ...}
{5:[3,1,0]}
"""
helper_dict = {
int(k): idx
for idx, (right, left) in enumerate(zip(self.children_left, self.children_right))
if right != -1
for k in (right, left)
}
return OrderedDict({int(key): self._get_leaf_path(helper_dict, int(key)) for key in self.leaves})
def get_leaf_depth(self, leaf):
return {key: len(value) for key, value in self.leaf_to_path_mapper.items()}.get(leaf)
def _get_leaf_path(self, data: Dict[np.int64, int],
key: int,
res: Optional[List] = None) -> List[int]:
"""
Method returns path to leaf as list of indices
:param data: dictionary {leaf: parent_leaf,...}
:param key: leaf_idx
:param res: prep list for path
:return: path to leaf
"""
if res is None:
res = []
val = data.get(int(key))
if val is None:
return res
return res + [val] + self._get_leaf_path(data, val, res)
def complete_tree(self, depth):
# Preparing data
full_tree_node_count = 2 * (2 ** depth - 1)
new_children_left = np.full((full_tree_node_count,), -1)
new_children_right = np.full((full_tree_node_count,), -1)
new_feature = np.full((full_tree_node_count,), -2)
new_threshold = np.full((full_tree_node_count,), -2)
new_value = np.full((full_tree_node_count,), 0)
# print(self.feature[self.nodes], new_feature[self.nodes])
new_feature[self.nodes] = self.feature[self.nodes]
new_threshold[self.nodes] = self.threshold[self.nodes]
# new_value[self.leaves] = self.value[self.leaves]
# Copy data from self.tree nodes and leafs
for leaf in self.leaves:
current_depth = self.get_leaf_depth(leaf)
new_node_idx = self.children_left.shape[0]
while current_depth < depth:
if leaf in self.children_left:
parent_left_idx = np.where(self.children_left == leaf)[0][0]
new_children_left[new_node_idx] = parent_left_idx
new_feature[new_node_idx] = self.feature[parent_left_idx]
new_threshold[new_node_idx] = self.threshold[parent_left_idx]
new_node_idx += 1
new_children_right[new_node_idx] = new_node_idx
# new_value[new_node_idx] = self.value[parent_idx]
elif leaf in self.children_right:
parent_right_idx = np.where(self.children_right == leaf)[0][0]
new_feature[new_node_idx] = self.feature[parent_right_idx]
new_threshold[new_node_idx] = self.threshold[parent_right_idx]
new_children_right[new_node_idx] = parent_right_idx
new_node_idx += 1
new_children_left[new_node_idx] = new_node_idx
# new_value[new_node_idx] = self.value[parent_idx]
new_node_idx += 1
current_depth += 1
return new_children_left, new_children_right, new_threshold, new_feature,
if __name__ == '__main__':
tree = Tree(left_children, right_children, features, thresholds, 7)
print(tree.complete_tree(3))
Буду благодарен любому дельному комментарию, замечанию (плохому, хорошему без разницы) или совету. Спасибо