在决策树中查找到决策边界的距离
Find Distance to Decision Boundary in Decision Trees
我想在 scikit-learn 中找到样本到经过训练的决策树分类器的决策边界的距离。特征都是数字,特征 space 可以是任意大小。
到目前为止,我有一个基于 here:
的示例 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,可以通过数学计算这个距离 [, , 3]. The rules learned after training a decision trees define the boundaries and may also be helpful to algorithmically calculate the distances [, , 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)
决策树不学习绘制决策边界。它试图根据最大信息增益点来分裂树。对于此过程,决策树算法使用 entropy
或 gini
索引。
由于这个原因,您无法找到点与决策边界之间的距离(没有决策边界)。
如果需要,您可以计算在图形上绘制的点和线之间的距离。所以大概给出了一些结果。
由于一个样本周围可能有多个决策边界,我假设这里的距离是指到最近的决策边界的距离。
解决方案是递归树遍历算法。请注意,决策树不允许样本位于边界上,例如SVM,特征space中的每个样本必须属于类之一。所以在这里我们将继续小步修改样本的特征,每当这导致一个区域具有不同的标签(与训练分类器最初分配给样本的标签不同)时,我们假设我们已经到达决策边界。
详细来说,就像任何递归算法一样,我们要考虑两种主要情况:
- 基本情况,即我们处于叶节点。我们简单地检查当前样本是否有不同的标签:如果是,则 return ,否则 return
None
.
- 非叶节点。有两个分支,我们将样品发送给两个分支。我们不会修改样本以将其发送到它自然会采用的分支。但在将其发送到另一个分支之前,我们查看节点的 (feature, threshold) 对,并修改样本的给定特征,使其恰好足以将其推到阈值的另一侧。
完成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]
这将为我们 return 我们提供一个样本列表,这些样本导致带有不同标签的叶子。我们现在需要做的就是取最近的一个:
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])
举例说明:
蓝色是原始样本,黄色是最近的样本"on"决策边界。
我想在 scikit-learn 中找到样本到经过训练的决策树分类器的决策边界的距离。特征都是数字,特征 space 可以是任意大小。
到目前为止,我有一个基于 here:
的示例 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,可以通过数学计算这个距离 [
# 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)
决策树不学习绘制决策边界。它试图根据最大信息增益点来分裂树。对于此过程,决策树算法使用 entropy
或 gini
索引。
由于这个原因,您无法找到点与决策边界之间的距离(没有决策边界)。
如果需要,您可以计算在图形上绘制的点和线之间的距离。所以大概给出了一些结果。
由于一个样本周围可能有多个决策边界,我假设这里的距离是指到最近的决策边界的距离。
解决方案是递归树遍历算法。请注意,决策树不允许样本位于边界上,例如SVM,特征space中的每个样本必须属于类之一。所以在这里我们将继续小步修改样本的特征,每当这导致一个区域具有不同的标签(与训练分类器最初分配给样本的标签不同)时,我们假设我们已经到达决策边界。
详细来说,就像任何递归算法一样,我们要考虑两种主要情况:
- 基本情况,即我们处于叶节点。我们简单地检查当前样本是否有不同的标签:如果是,则 return ,否则 return
None
. - 非叶节点。有两个分支,我们将样品发送给两个分支。我们不会修改样本以将其发送到它自然会采用的分支。但在将其发送到另一个分支之前,我们查看节点的 (feature, threshold) 对,并修改样本的给定特征,使其恰好足以将其推到阈值的另一侧。
完成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]
这将为我们 return 我们提供一个样本列表,这些样本导致带有不同标签的叶子。我们现在需要做的就是取最近的一个:
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])
举例说明:
蓝色是原始样本,黄色是最近的样本"on"决策边界。