决策树分类中两片叶子之间的距离

Question

有没有一种计算decision tree中两片叶子之间距离的方法。你知道吗

距离是指从一片叶子到另一片叶子的节点数。你知道吗

例如，在此示例图中：

distance(leaf1, leaf2) == 1
distance(leaf1, leaf3) == 3
distance(leaf1, leaf4) == 4

谢谢你的帮助！你知道吗

Answer 1

一个依赖于其他Python包的示例，即networkx和pydot。因此，人们对解决方案进行了慷慨的评论。这个问题用scikit-learn标记，因此解决方案是用Python表示的。你知道吗

一些数据和一个通用的DecisionTreeClassifier：

# load example data and classifier
from sklearn.datasets import load_wine
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

# for determining distance
from sklearn import tree
import networkx as nx
import pydot

# load data and fit a DecisionTreeClassifier
X, y = load_wine(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
clf = DecisionTreeClassifier(max_depth=3, random_state=42)
clf.fit(X_train, y_train);

此函数使用^{}、^{}、^{}和^{}将fitDecisionTreeClassifier转换为networkx无向MultiGraph。你知道吗

def dt_to_mg(clf):
    """convert a fit DecisionTreeClassifier to a Networkx undirected MultiGraph"""
    # export the classifier to a string DOT format
    dot_data = tree.export_graphviz(clf)
    # Use pydot to convert the dot data to a graph
    dot_graph = pydot.graph_from_dot_data(dot_data)[0]
    # Import the graph data into Networkx 
    MG = nx.drawing.nx_pydot.from_pydot(dot_graph)
    # Convert the tree to an undirected Networkx Graph
    uMG = MG.to_undirected()
    return uMG

uMG = dt_to_mg(clf)

使用^{}查找树中任何两个节点之间的距离。你知道吗

# get leaves
leaves = set(str(x) for x in clf.apply(X))
print(leaves)
{'10', '7', '9', '5', '3', '4'}

# find the distance for two leaves
print(nx.shortest_path_length(uMG, source='9', target='5'))
5

# undirected graph means this should also work
print(nx.shortest_path_length(uMG, source='5', target='9'))
5

shortest_path_length返回source和target之间的边数。这不是OP请求的距离度量。我认为它们之间的节点数应该是n_edges - 1。你知道吗

print(nx.shortest_path_length(uMG, source='5', target='9') - 1)
4

或者找到所有叶子的距离，并将它们存储在字典或其他有用的对象中，以便进行下游计算。你知道吗

from itertools import combinations
leaf_distance_edges = {}
leaf_distance_nodes = {}
for leaf1, leaf2 in combinations(leaves, 2):
    d = nx.shortest_path_length(uMG, source=leaf1, target=leaf2)
    leaf_distance_edges[(leaf1, leaf2)] = d
    leaf_distance_nodes[(leaf1, leaf2)] = d - 1 

leaf_distance_nodes
{('4', '9'): 5,
 ('4', '5'): 2,
 ('4', '10'): 5,
 ('4', '7'): 4,
 ('4', '3'): 1,
 ('9', '5'): 4,
 ('9', '10'): 1,
 ('9', '7'): 2,
 ('9', '3'): 5,
 ('5', '10'): 4,
 ('5', '7'): 3,
 ('5', '3'): 2,
 ('10', '7'): 2,
 ('10', '3'): 5,
 ('7', '3'): 4}