Изучение структуры дерева решений

Обучение классификатора на дереве

Сначала мы обучим DecisionTreeClassifier на наборе данных load_iris.

iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)

clf = DecisionTreeClassifier(max_leaf_nodes=3, random_state=0)
clf.fit(X_train, y_train)

DecisionTreeClassifier(max_leaf_nodes=3, random_state=0)

Структура дерева

У классификатора на дереве есть атрибут tree_, который предоставляет доступ к низкоуровневым атрибутам, таким как node_count, общее число узлов, и max_depth, максимальная глубина дерева. Метод tree_.compute_node_depths() вычисляет глубину каждого узла дерева. tree_ также хранит всю структуру бинарного дерева, представленную в виде нескольких параллельных массивов. i-й элемент каждого массива содержит информацию об узле i. Узел 0 — корень дерева. Некоторые массивы применимы только к листьям или только к узлам разбиения. В этом случае значения для узлов другого типа произвольны. Например, массивы feature и threshold применяются только к узлам разбиения. Поэтому значения в этих массивах для листовых узлов произвольны.

Среди этих массивов есть:

• children_left[i]: идентификатор левого дочернего узла узла i или -1, если это листовой узел
• children_right[i]: идентификатор правого дочернего узла узла i или -1, если это листовой узел
• feature[i]: признак, использованный для разбиения узла i
• threshold[i]: пороговое значение в узле i
• n_node_samples[i]: число обучающих образцов, достигших узла i
• impurity[i]: неоднородность в узле i
• weighted_n_node_samples[i]: взвешенное число обучающих образцов, достигших узла i
• value[i, j, k]: сводка по обучающим образцам, достигшим узла i, для выхода j и класса k (для дерева регрессии класс равен 1). Подробнее о value см. ниже.

Используя массивы, можно обойти структуру дерева и вычислить различные свойства. Ниже мы вычислим глубину каждого узла и определим, является ли он листом.

n_nodes = clf.tree_.node_count
children_left = clf.tree_.children_left
children_right = clf.tree_.children_right
feature = clf.tree_.feature
threshold = clf.tree_.threshold
values = clf.tree_.value

node_depth = np.zeros(shape=n_nodes, dtype=np.int64)
is_leaves = np.zeros(shape=n_nodes, dtype=bool)
stack = [(0, 0)]  # start with the root node id (0) and its depth (0)
while len(stack) > 0:
    # `pop` ensures each node is only visited once
    node_id, depth = stack.pop()
    node_depth[node_id] = depth

    # If the left and right child of a node is not the same we have a split
    # node
    is_split_node = children_left[node_id] != children_right[node_id]
    # If a split node, append left and right children and depth to `stack`
    # so we can loop through them
    if is_split_node:
        stack.append((children_left[node_id], depth + 1))
        stack.append((children_right[node_id], depth + 1))
    else:
        is_leaves[node_id] = True

print(
    "The binary tree structure has {n} nodes and has "
    "the following tree structure:\n".format(n=n_nodes)
)
for i in range(n_nodes):
    if is_leaves[i]:
        print(
            "{space}node={node} is a leaf node with value={value}.".format(
                space=node_depth[i] * "\t", node=i, value=np.around(values[i], 3)
            )
        )
    else:
        print(
            "{space}node={node} is a split node with value={value}: "
            "go to node {left} if X[:, {feature}] <= {threshold} "
            "else to node {right}.".format(
                space=node_depth[i] * "\t",
                node=i,
                left=children_left[i],
                feature=feature[i],
                threshold=threshold[i],
                right=children_right[i],
                value=np.around(values[i], 3),
            )
        )

The binary tree structure has 5 nodes and has the following tree structure:

node=0 is a split node with value=[[0.33  0.304 0.366]]: go to node 1 if X[:, 3] <= 0.800000011920929 else to node 2.
        node=1 is a leaf node with value=[[1. 0. 0.]].
        node=2 is a split node with value=[[0.    0.453 0.547]]: go to node 3 if X[:, 2] <= 4.950000047683716 else to node 4.
                node=3 is a leaf node with value=[[0.    0.917 0.083]].
                node=4 is a leaf node with value=[[0.    0.026 0.974]].

Для чего здесь используется массив values?

Массив tree_.value — это трёхмерный массив формы [n_nodes, n_classes, n_outputs], который содержит долю образцов, достигших узла, для каждого класса и каждого выхода. Для каждого узла имеется массив value, содержащий долю взвешенных образцов, достигших этого узла, для каждого выхода и класса относительно родительского узла.

Чтобы получить абсолютное взвешенное число образцов, достигших узла, можно умножить это значение на tree_.weighted_n_node_samples[node_idx] для данного узла. Обратите внимание: в этом примере веса образцов не используются, поэтому взвешенное число образцов совпадает с числом образцов, достигших узла, так как по умолчанию вес каждого образца равен 1.

Например, в дереве выше, построенном на наборе данных iris, корневой узел имеет значение value = [0.33, 0.304, 0.366], то есть в корневом узле 33% образцов принадлежат классу 0, 30,4% — классу 1 и 36,6% — классу 2. Чтобы получить абсолютное число образцов, можно умножить эти значения на число образцов, достигших корневого узла, то есть на tree_.weighted_n_node_samples[0]. Тогда корневой узел будет иметь значение value = [37, 34, 41], то есть в корневом узле 37 образцов класса 0, 34 образца класса 1 и 41 образец класса 2.

При обходе дерева образцы разделяются, и в результате массив value для каждого узла изменяется. Левый дочерний узел корневого узла имеет значение value = [1., 0, 0] (или value = [37, 0, 0] при преобразовании в абсолютное число образцов), поскольку все 37 образцов в левом дочернем узле относятся к классу 0.

Примечание: в этом примере n_outputs=1, однако классификатор на дереве также может работать с задачами с несколькими выходами. В этом случае массив value в каждом узле будет двумерным.

Мы можем сравнить приведённый выше результат с графиком дерева решений. Здесь показаны доли образцов каждого класса, достигающих каждого узла, в соответствии с фактическими элементами массива tree_.value.

tree.plot_tree(clf, proportion=True)
plt.show()

Путь принятия решения

Также можно получить путь принятия решения для интересующих нас образцов. Метод decision_path возвращает матрицу-индикатор, с помощью которой можно определить узлы, через которые проходят интересующие нас образцы. Ненулевой элемент матрицы-индикатора в позиции (i, j) означает, что образец i проходит через узел j. Или, для одного образца i, позиции ненулевых элементов в строке i матрицы-индикатора указывают идентификаторы узлов, через которые проходит этот образец.

Идентификаторы листьев, достигнутых интересующими нас образцами, можно получить с помощью метода apply. Он возвращает массив идентификаторов узлов-листьев, достигнутых каждым интересующим нас образцом. Используя идентификаторы листьев и decision_path, можно получить условия разбиения, использованные для предсказания для одного образца или группы образцов. Сначала выполним это для одного образца. Обратите внимание, что node_index — разреженная матрица.

node_indicator = clf.decision_path(X_test)
leaf_id = clf.apply(X_test)

sample_id = 0
# obtain ids of the nodes `sample_id` goes through, i.e., row `sample_id`
node_index = node_indicator.indices[
    node_indicator.indptr[sample_id] : node_indicator.indptr[sample_id + 1]
]

print("Rules used to predict sample {id}:\n".format(id=sample_id))
for node_id in node_index:
    # continue to the next node if it is a leaf node
    if leaf_id[sample_id] == node_id:
        continue

    # check if value of the split feature for sample 0 is below threshold
    if X_test[sample_id, feature[node_id]] <= threshold[node_id]:
        threshold_sign = "<="
    else:
        threshold_sign = ">"

    print(
        "decision node {node} : (X_test[{sample}, {feature}] = {value}) "
        "{inequality} {threshold})".format(
            node=node_id,
            sample=sample_id,
            feature=feature[node_id],
            value=X_test[sample_id, feature[node_id]],
            inequality=threshold_sign,
            threshold=threshold[node_id],
        )
    )

Rules used to predict sample 0:

decision node 0 : (X_test[0, 3] = 2.4) > 0.800000011920929)
decision node 2 : (X_test[0, 2] = 5.1) > 4.950000047683716)

Для группы образцов можно определить общие узлы, через которые они проходят.

sample_ids = [0, 1]
# boolean array indicating the nodes both samples go through
common_nodes = node_indicator.toarray()[sample_ids].sum(axis=0) == len(sample_ids)
# obtain node ids using position in array
common_node_id = np.arange(n_nodes)[common_nodes]

print(
    "\nThe following samples {samples} share the node(s) {nodes} in the tree.".format(
        samples=sample_ids, nodes=common_node_id
    )
)
print("This is {prop}% of all nodes.".format(prop=100 * len(common_node_id) / n_nodes))

The following samples [0, 1] share the node(s) [0 2] in the tree.
This is 40.0% of all nodes.

Общее время выполнения скрипта: (0 минут 0.085 секунды)

Download Jupyter notebook: plot_unveil_tree_structure.ipynb

Download Python source code: plot_unveil_tree_structure.py

Download zipped: plot_unveil_tree_structure.zip

Связанные примеры

Построение дендрограммы иерархической кластеризации

Постобрезка деревьев решений с помощью обрезки по критерию стоимости-сложности

Регрессия на дереве решений

Построение поверхности принятия решений для деревьев, обученных на наборе данных iris