如何迭代合并叶子节点相同的树分支以简化决策树结构？

背景数据与树结构生成 #

我们有一个包含特征x1、x2、x3和结果y的DataFrame，可通过以下代码生成所有特征组合的数据集：

import pandas as pd
import numpy as np

def crossing(df1: pd.DataFrame, df2: pd.DataFrame) -> pd.DataFrame:
    return pd.merge(df1.assign(key=1), df2.assign(key=1), on='key').drop(columns='key')

def crossing_many(*args):
    from functools import reduce
    return reduce(crossing, args)

df = crossing_many(
    pd.DataFrame({'x1': ['A', 'B', 'C']}),
    pd.DataFrame({'x2': ['X', 'Y', 'Z']}),
    pd.DataFrame({'x3': ['xxx', 'yyy', 'zzz']}),
).assign(y = lambda d: np.random.choice([0, 1], size=len(d)))

使用bigtree库可快速绘制对应树结构：

from bigtree import dataframe_to_tree, tree_to_dot
def view_pydot(pdot):
    from IPython.display import Image, display
    plt = Image(pdot.create_png())
    display(plt)

features = ['x1', 'x2', 'x3']
tree = (
    df
    .assign(y=lambda d: d['y'].astype('str'))
    .assign(root='Everyone')
    .assign(path=lambda d: d[['root'] + features + ['y']].agg('/'.join, axis=1))
    .pipe(dataframe_to_tree, path_col='path')
)

view_pydot(tree_to_dot(tree))

简化树结构的需求 #

当前生成的树结构过于复杂，需要完成以下处理：

• 迭代合并所有层级上叶子节点结果相同的分支或节点，生成最简树结构，最终能得到类似IF x1=A AND x2=X THEN 1的最短决策路径
• 移除覆盖特征所有取值的节点（例如合并后出现的xxx|yyy|zzz这类包含该特征全部可能值的节点）

内容的提问来源于stack exchange，提问作者mihagazvoda