Найти расстояние до границы решения в деревьях решений

Question

Я хочу найти расстояние выборок до границы решения обученного классификатора деревьев решений в scikit-learn . Все функции имеют числовое значение c, и пространство функций может быть любого размера.

У меня пока есть эта визуализация для примера 2D-случая, основанного на здесь :

import numpy as np
import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_moons

# Generate some example data
X, y = make_moons(noise=0.3, random_state=0)

# Train the classifier
clf = DecisionTreeClassifier(max_depth=2)

clf.fit(X, y)

# Plot
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1))

Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.contourf(xx, yy, Z, alpha=0.4)
plt.scatter(X[:, 0], X[:, 1], c=y, s=20, edgecolor='k')
plt.xlabel('a'); plt.ylabel('b');

Я понимаю, что для некоторых других классификаторов, таких как SVM, это расстояние может быть математически рассчитано [ 1 , 2 , 3 ]. Правила, изученные после обучения деревьев решений, определяют границы и могут также быть полезны для алгоритмического расчета расстояний [ 4 , 5 , 6 ]:

# Plot the trained tree
from sklearn import tree
import graphviz 
dot_data = tree.export_graphviz(clf, feature_names=['a', 'b'],  class_names=['1', '2'], filled=True)  
graph = graphviz.Source(dot_data)  

Answer 1

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

Решение представляет собой алгоритм рекурсивного обхода дерева. Обратите внимание, что дерево решений не позволяет образцу находиться на границе, как, например, SVM, каждый образец в пространстве признаков должен принадлежать одному из классов. Поэтому здесь мы продолжим модифицировать функцию образца небольшими шагами, и всякий раз, когда это приводит к области с другой меткой (чем та, которая изначально была назначена для образца обученным классификатором), мы предполагаем, что достигли границы принятия решения.

Подробно, как и любой рекурсивный алгоритм, мы должны рассмотреть два основных случая:

1. Базовый случай, т. Е. Мы находимся в листовом узле. Мы просто проверяем, имеет ли текущая выборка другую метку: если так, то возвращаем ее, в противном случае возвращаем None.
2. Неконечные узлы. Есть две ветви, мы отправляем образец в обе. Мы не модифицируем образец, чтобы отправить его в ветку, которую он, естественно, взял бы. Но прежде чем отправить его в другую ветвь, мы смотрим на пару (функция, порог) узла и модифицируем данную особенность образца так, чтобы она выглядела на sh на противоположной стороне порога.

Заполните python код:

def f(node,x,orig_label):
    global dt,tree
    if tree.children_left[node]==tree.children_right[node]: #Meaning node is a leaf
        return [x] if dt.predict([x])[0]!=orig_label else [None]

    if x[tree.feature[node]]<=tree.threshold[node]:
        orig = f(tree.children_left[node],x,orig_label)
        xc = x.copy()
        xc[tree.feature[node]] = tree.threshold[node] + .01
        modif = f(tree.children_right[node],xc,orig_label)
    else:
        orig = f(tree.children_right[node],x,orig_label)
        xc = x.copy()
        xc[tree.feature[node]] = tree.threshold[node] 
        modif = f(tree.children_left[node],xc,orig_label)
    return [s for s in orig+modif if s is not None]

Это вернет нам список образцов, которые приводят к листьям с другой этикеткой. Все, что нам нужно сделать сейчас, это взять ближайший:

dt =  DecisionTreeClassifier(max_depth=2).fit(X,y)
tree = dt.tree_
res = f(0,x,dt.predict([x])[0]) # 0 is index of root node
ans = np.min([np.linalg.norm(x-n) for n in res]) 

Для иллюстрации:

Оригинальный синий образец, желтый - ближайшая выборка "на" границе решения.

Answer 2

Дерево решений не учится рисовать границы решений. Он пытается разбить дерево на основе максимальной точки получения информации. Для этого процесса алгоритм дерева решений использует индексы entropy или gini.

По этой причине вы не можете найти расстояние между точками и границей решения (границы решения не существует).

Если вы хотите, вы можете рассчитать расстояние между точками и линиями, которые вы рисуете на графике c. Это примерно дает некоторые результаты.