5

Работаю с деревьями решений 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 в массивах намекают на то, что эти вершины являются висячими узлами (далее по тексту - листья). Уже написан большой кусок кода, принимающий на вход полное дерево. И задача, за помощью с которой я обращаюсь к сообществу заключается в приведении неполного дерева к полному .

Нужно реализовать функцию которая на вход принимает дерево и глубину, к которому надо это дерево привести. Алгоритм работы следующий:

  1. Найти количество вершин полного дерева, по сумме элементов геометрической прогрессии: 2*(2**depth - 1) + 1
  2. Подготовить соответствующие параметры для заполнения полного дерева: children_left, children_right, feature, threshold. Длина массивов каждого из которых равна длине вершин полного дерева - 1 (2*(2**depth - 1))
  3. Найти все листья;
  4. Найти к какой глубине соответствует каждый лист;
  5. Итерироваться по листьям и до тех пор пока не достигнута требуемая глубина, создать новую вершину и прицепить к нему лист (если левый - то левому, правый - правому). Индекс новых вершин начинать с количества вершин неполного дерева - 1
  6. Новая создаваемая вершина копирует свойства родителя листа; Картинка дерева: введите сюда описание изображения Ниже приведен код, который должен реализовать описанный алгоритм, что-то я делаю не так:
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))

Буду благодарен любому дельному комментарию, замечанию (плохому, хорошему без разницы) или совету. Спасибо

1
  • Немного с графами столкнулся в задачах полного перебора вершин графа. Нашел хороший факториальный алгоритм Лехмера. Ну а в python есть несколько библиотек для работы с графами. В теории графов начните с изучения понятия "матрица смежности", она в принципе и не такая сложная, как кажется на первый взгляд. Очень много прикладных задач решаются с ее помощью.
    – Assur
    31 июл 2020 в 22:33

1 ответ 1

0
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 leaf_depth_mapper(self):
        return {key: len(value) for key, value in self.leaf_to_path_mapper.items()}

    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) + 1
        new_children_left = np.full((full_tree_node_count,), -1, dtype=int)
        new_children_right = np.full((full_tree_node_count,), -1, dtype=int)
        new_feature = np.full((full_tree_node_count,), -2, dtype=int)
        new_threshold = np.full((full_tree_node_count,), -2, dtype=float)
        new_value = np.full((full_tree_node_count,), 0, dtype=float)

        new_children_left[:self.children_left.shape[0]] = self.children_left
        new_children_right[:self.children_left.shape[0]] = self.children_right
        new_feature[self.nodes] = self.feature[self.nodes]
        new_threshold[self.nodes] = self.threshold[self.nodes]

        new_node_idx = self.children_left.shape[0]
        depth_mapper = self.leaf_depth_mapper()
        left_children = set(self.children_left)
        right_children = set(self.children_right)
        for leaf in range(full_tree_node_count):
            current_depth = depth_mapper.get(leaf,depth)
            while current_depth < depth:
                if leaf in left_children:
                    parent_left_idx = np.where(new_children_left == leaf)[0][0]
                    new_children_left[parent_left_idx] = new_node_idx
                    new_feature[new_node_idx] = new_feature[parent_left_idx]
                    new_threshold[new_node_idx] = new_threshold[parent_left_idx]
                    new_children_left[new_node_idx] = leaf
                    new_value[new_node_idx] = new_value[parent_left_idx]
                    right_children.add(new_node_idx + 1)
                    new_children_right[new_node_idx] = new_node_idx + 1
                elif leaf in right_children:
                    parent_right_idx = np.where(new_children_right == leaf)[0][0]
                    new_children_right[parent_right_idx] = new_node_idx
                    new_feature[new_node_idx] = new_feature[parent_right_idx]
                    new_threshold[new_node_idx] = new_threshold[parent_right_idx]
                    new_children_right[new_node_idx] = leaf
                    new_value[new_node_idx] = new_value[parent_right_idx]
                    left_children.add(new_node_idx + 1)
                    new_children_left[new_node_idx] = new_node_idx + 1

                current_depth += 1
                depth_mapper[new_node_idx+1] = current_depth
                new_node_idx += 2

        return new_children_left, new_children_right, new_threshold, new_feature, new_value

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.