决策树（Decision tree）算法详解（ID3、C4.5、CART）

一、决策树介绍

决策树是一种树形结构的监督学习算法，其核心思想是通过一系列条件判断对数据进行分类，就像人类在做决策时的逻辑判断过程。

1.1 决策树的结构特征

• 内部节点：表示一个特征上的判断（如"年龄是否大于30"）
• 分支：表示判断结果的输出（如"是"或"否"）
• 叶子节点：表示最终的分类结果（如"同意贷款"或"拒绝贷款"）

1.2 决策树的构建三步骤

1. 特征选择：从众多特征中挑选分类能力最强的特征
2. 树的生成：基于选择的特征递归构建决策树
3. 剪枝优化：防止过拟合，提升模型泛化能力

1.3 决策树构建例子

你有一个朋友正在考虑是否要去参加一个社交活动，他/她/他们可能会这样思考：
朋友问你：这个活动值得去吗？
于是你开始了解情况：
问：这个活动是线上还是线下？
答：线下，在市中心的一个咖啡馆。
问：天气怎么样？
答：那天天气不错。
问：有没有感兴趣的人会去？
答：有，你喜欢的那位也会去。
问：交通方便吗？
答：地铁直达，很方便。
……
于是你的大脑里就构建了这样一棵“决策树”：

绘图代码：

import graphviz

# 创建有向图，并设置中文字体
# 1. 导入Graphviz库：
#    graphviz是Python与Graphviz软件交互的接口，负责生成可视化图形（需提前安装Graphviz软件）
import graphviz  

# 2. 创建有向图对象，并配置中文显示：
#    - comment：给图加注释（仅文档用途，不影响渲染）
#    - format：指定输出文件格式（如png、pdf等）
#    - node_attr/edge_attr/graph_attr：设置节点、边、全局的字体为"SimHei"（微软雅黑），解决中文乱码问题
dot = graphviz.Digraph(
    comment='社交活动决策树',       # 图的描述信息（可选）
    format='png',                  # 输出文件格式
    node_attr={'fontname': 'SimHei'},  # 节点文字用微软雅黑（支持中文）
    edge_attr={'fontname': 'SimHei'},  # 边的标签文字用微软雅黑
    graph_attr={'fontname': 'SimHei'}  # 全局文字（如标题）用微软雅黑
)

# 3. 添加节点（node）：
#    格式：dot.node(节点唯一标识, 显示的文字)
#    节点ID（如'A'）是内部标记，显示文字是图形中实际展示的内容
dot.node('A', '活动类型')         # 根节点：决策起点（活动类型）
dot.node('B', '线上')             # 分支1：活动类型为线上
dot.node('C', '线下')             # 分支2：活动类型为线下
dot.node('D', '天气是否好？')     # 线下活动的子判断：天气条件
dot.node('E', '否')               # 天气分支：不好
dot.node('F', '是')               # 天气分支：好
dot.node('G', '有没有感兴趣的人？') # 天气好时的子判断：兴趣条件
dot.node('H', '否')               # 兴趣分支：没有
dot.node('I', '有')               # 兴趣分支：有
dot.node('J', '去参加')           # 最终决策：参加
dot.node('K', '考虑其他安排')     # 最终决策：不参加

# 4. 添加边（edge）：
#    格式：dot.edge(起点ID, 终点ID, label=边的说明文字)
#    label可选，用于解释分支条件
dot.edge('A', 'B')                # 活动类型 → 线上（无额外条件，直接分支）
dot.edge('A', 'C')                # 活动类型 → 线下（无额外条件，直接分支）
dot.edge('C', 'D')                # 线下活动 → 判断天气
dot.edge('D', 'E', label='否')    # 天气判断 → 否（边标注“否”）
dot.edge('D', 'F', label='是')    # 天气判断 → 是（边标注“是”）
dot.edge('F', 'G')                # 天气好 → 判断是否有感兴趣的人
dot.edge('G', 'H', label='否')    # 兴趣判断 → 否（边标注“否”）
dot.edge('G', 'I', label='是')    # 兴趣判断 → 是（边标注“是”）
dot.edge('I', 'J')                # 有感兴趣的人 → 去参加（最终决策）
dot.edge('H', 'K')                # 没有感兴趣的人 → 考虑其他安排（最终决策）

# 5. 渲染并查看图形：
#    - 第一个参数：输出文件名（生成的文件会是 decision_tree_social_event.png）
#    - view=True：生成后自动用系统默认程序打开图片
#    注意：运行前需确保：
#      ① 系统安装了Graphviz软件（https://graphviz.org/download/）
#      ② Graphviz的bin目录已加入系统环境变量（如 C:\Program Files\Graphviz\bin）
dot.render('decision_tree_social_event', view=True)

二、ID3决策树：基于信息增益的决策模型

2.1 信息增益的公式与符号解析

信息增益公式：
$$g(D,A)=H(D)-H(D|A)$$

• $g(D,A)$：特征$A$对数据集$D$的信息增益
• $H(D)$：数据集$D$的经验熵，衡量数据的不确定性
  $$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$
  其中，$K$为类别数，$|C_k|$为第$k$类的样本数，$|D|$为总样本数。
• $H(D|A)$：特征$A$给定条件下$D$的经验条件熵
  $$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$$
  其中，$n$为特征$A$的取值个数，$|D_i|$为特征$A$取第$i$个值的样本数，$|D_{ik}|$为$D_i$中属于第$k$类的样本数。

2.2 信息增益的意义

信息增益衡量的是某个特征对数据分类不确定性的减少程度。直观来说，它反映了在已知某个特征的取值后，我们对样本分类结果的不确定性降低了多少。
例如，在判断一个人是否适合贷款时，如果“是否有房”这一特征能显著帮助我们确定贷款审批结果，那么这个特征的信息增益就较大。换句话说，信息增益越大，该特征在分类任务中的判别能力越强。

2.3 ID3决策树案例演示：贷款申请分类

以贷款申请数据为例，计算各特征的信息增益并构建ID3决策树。

数据集：

步骤1：计算数据集D的经验熵H(D)
数据集中共有15条样本，其中"同意"类5条，"拒绝"类10条：
$$H(D)=-\frac{5}{15}{\log }_2\frac{5}{15}-\frac{10}{15}{\log }_2\frac{10}{15}=0.9183$$

步骤2：计算各特征的条件熵和信息增益
以"年龄"特征为例，其取值为{青年, 中年, 老年}：

• 青年样本：5条（ID1-5），其中拒绝4条，同意1条
  $$H(青年)=-\frac{4}{5}{\log }_2\frac{4}{5}-\frac{1}{5}{\log }_2\frac{1}{5}=0.7219$$
• 中年样本：5条（ID6-10），其中拒绝2条，同意3条
  $$H(中年)=-\frac{2}{5}{\log }_2\frac{2}{5}-\frac{3}{5}{\log }_2\frac{3}{5}=0.9709$$
• 老年样本：5条（ID11-15），其中拒绝1条，同意4条
  $$H(老年)=-\frac{1}{5}{\log }_2\frac{1}{5}-\frac{4}{5}{\log }_2\frac{4}{5}=0.7219$$
• 条件熵：
  $$H(D|年龄)=\frac{5}{15}\times 0.7219+\frac{5}{15}\times 0.9709+\frac{5}{15}\times 0.7219=0.8049$$
• 信息增益：
  $$g(D,年龄)=0.9183-0.8049=0.1134$$

同理计算其他特征的信息增益：

• $g(D,有工作)=0.3236$
• $g(D,有房子)=0.4208$
• $g(D,信贷情况)=0.3623$

步骤3：选择信息增益最大的特征分裂
"有房子"的信息增益最大（0.4208），作为根节点分裂，得到左右子树：

• 有房子：7条样本（ID4,8,9,10,11,12,14），其中6条同意，1条拒绝
• 无房子：8条样本（ID1,2,3,5,6,7,13,15），其中2条同意，6条拒绝

步骤4：递归构建子树
对每个子树重复上述过程，最终生成完整的ID3决策树。

这是一棵用于 贷款申请分类 的决策树（基于ID3算法，通过信息熵选择分裂特征），核心判断逻辑如下：

根节点：判断“是否有房子”

• 条件：按特征取值分裂（右分支为 有房子 > 0.5，左分支为 有房子 ≤ 0.5）。
• 信息增益：0.42（衡量该特征对分类的贡献度）。
• 样本数：15（全量样本）。
• 类别分布：拒绝6人，同意9人（分布：拒绝=6，同意=9）。

分支逻辑

• 右分支（有房子 > 0.5）

  • 样本：6人（所有“有房”申请人）。
  • 类别分布：同意6人，拒绝0人。
  • 决策：直接判定为 同意（叶子节点）。

• 左分支（有房子 ≤ 0.5）

  • 进入下一层判断 “是否有工作”：

第二层节点：判断“是否有工作”

• 条件：按特征取值分裂（右分支为 有工作 > 0.5，左分支为 有工作 ≤ 0.5）。
• 信息增益：0.918（该特征对剩余样本的分类贡献度）。
• 样本数：9人（所有“无房”申请人）。
• 类别分布：拒绝6人，同意3人（分布：拒绝=6，同意=3）。

最终叶子节点

• 左子节点（有工作 ≤ 0.5）

  • 样本：6人（无房且无工作的申请人）。
  • 类别分布：同意0人，拒绝6人。
  • 决策：拒绝（叶子节点）。

• 右子节点（有工作 > 0.5）

  • 样本：3人（无房但有工作的申请人）。
  • 类别分布：同意3人，拒绝0人。
  • 决策：同意（叶子节点）。

决策树通过 “有房→有工作” 的两步判断，输出贷款决策：

• 有房 → 直接同意；
• 无房但有工作 → 同意；
• 无房且无工作 → 拒绝。

（注：LabelEncoder 按字母序编码类别，此处“同意”为0，“拒绝”为1，节点分布以 拒绝=X，同意=Y 格式展示。）

绘图代码：

# 导入必要的库
import pandas as pd  # 用于数据处理和构建 DataFrame
from collections import Counter  # 用于统计样本数量
from math import log2  # 用于计算对数
from graphviz import Digraph  # 用于可视化决策树
from sklearn.preprocessing import LabelEncoder  # 用于将字符串特征编码为数字


# =============================================
# 1. 数据准备
# =============================================
# 构建训练数据集，包含 5 个特征和 1 个目标变量
data = {
    # 每个样本的唯一编号，容易造成过拟合
    # "ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],

    # 年龄：青年、中年、老年
    "年龄": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年",
             "老年", "老年", "老年", "老年", "老年"],

    # 是否有工作：是、否
    "有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否",
               "否", "否", "是", "是", "否"],

    # 是否有房子：是、否
    "有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是",
               "是", "是", "否", "否", "否"],

    # 信贷情况：一般、好、非常好
    "信贷情况": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好",
                 "非常好", "好", "好", "非常好", "一般"],

    # 类别：是否贷款成功（同意/拒绝）
    "类别": ["拒绝", "拒绝", "同意", "同意", "拒绝", "拒绝", "拒绝", "同意", "同意", "同意",
             "同意", "同意", "同意", "同意", "拒绝"]
}

# 将数据转换为 pandas 的 DataFrame 格式
df = pd.DataFrame(data)

# 提取特征列名列表（所有列除了最后一列）
features = list(df.columns[:-1])  # 特征：ID、年龄、有工作、有房子、信贷情况

# 目标变量列名（最后一列）
target = df.columns[-1]  # 类别列名


# =============================================
# 2. 信息熵与信息增益计算
# =============================================

def entropy(y):
    """
    计算信息熵 H(Y)
    y: 当前样本的目标变量值（如：['拒绝', '同意', ...]）
    返回：当前样本的信息熵
    """
    counts = Counter(y)  # 统计每个类别的数量
    total = len(y)  # 总样本数
    if total == 0:
        return 0  # 防止除以 0
    # 计算 -Σ(p * log2(p))
    return -sum((count / total) * log2(count / total) for count in counts.values())


def conditional_entropy(X_col, y):
    """
    计算条件熵 H(Y|X)
    X_col: 某个特征列的值（如：['青年', '中年', ...]）
    y: 对应的目标变量值
    返回：给定该特征下目标变量的条件熵
    """
    values = set(X_col)  # 获取该特征的所有唯一值
    total = len(y)  # 总样本数
    ent = 0
    for v in values:
        mask = (X_col == v)  # 找到该特征值对应的样本
        y_sub = y[mask]  # 取出这些样本的目标变量
        ent += len(y_sub) / total * entropy(y_sub)  # 加权求和
    return ent


def info_gain(dataset, feature):
    """
    计算某个特征的信息增益 IG(Y, X)
    dataset: 整个数据集
    feature: 当前特征名称（如："年龄"）
    返回：该特征的信息增益
    """
    X_col = dataset[feature]  # 取出该特征列
    y = dataset[target]  # 取出目标变量列
    return entropy(y) - conditional_entropy(X_col, y)  # 信息增益 = 总熵 - 条件熵


# =============================================
# 3. 手动实现 ID3 决策树
# =============================================

def id3_tree(dataset, features):
    """
    使用 ID3 算法递归构建决策树
    dataset: 当前数据集
    features: 当前可用特征列表
    返回：当前节点的决策树结构字典
    """
    target_values = dataset[target].unique()  # 获取当前目标变量的唯一值

    # 终止条件1：当前样本全部属于同一类
    if len(target_values) == 1:
        return {'label': target_values[0]}  # 返回叶子节点标签

    # 终止条件2：没有可用特征
    if not features:
        most_common = dataset[target].mode().iloc[0]  # 返回多数类作为预测结果
        return {'label': most_common}

    # 选择信息增益最大的特征
    gains = {f: info_gain(dataset, f) for f in features}  # 计算每个特征的信息增益
    best_feature = max(gains, key=gains.get)  # 选出最大增益的特征

    # 构建当前节点信息
    class_counts = dict(Counter(dataset[target]))  # 统计目标变量分布
    node_info = {
        'feature': best_feature,
        'gain': gains[best_feature],  # 信息增益
        'class_dist': class_counts,  # 类别分布
        'n_samples': len(dataset),  # 样本数量
        'children': {}  # 子节点
    }

    # 递归划分每个特征值
    remaining_features = [f for f in features if f != best_feature]  # 剩余可用特征
    for raw_value in dataset[best_feature].unique():  # 遍历当前特征的每个唯一值
        sub_data = dataset[dataset[best_feature] == raw_value]  # 划分子数据集
        node_info['children'][raw_value] = id3_tree(sub_data, remaining_features)  # 递归生成子树

    return node_info


# =============================================
# 4. 构建特征编码器（用于生成 CART 风格的分割条件）
# =============================================
# 保存每个特征的编码器，便于后续可视化时使用
feature_encoders = {}

for feat in features:
    le = LabelEncoder()  # 创建编码器
    le.fit(df[feat])  # 拟合该特征的编码规则
    feature_encoders[feat] = le  # 保存编码器


# =============================================
# 5. 决策树可视化（CART 风格，支持中文）
# =============================================
def visualize_tree_cart_style(tree, feature_encoders, graph=None, parent_id=None, edge_label=""):
    """
    使用 Graphviz 可视化决策树（CART 风格）
    tree: 当前树节点结构
    feature_encoders: 编码器字典
    graph: 当前图对象
    parent_id: 父节点 ID
    edge_label: 边上的标签
    返回：Graphviz 图对象
    """
    from uuid import uuid4  # 用于生成唯一节点 ID

    if graph is None:
        # 初始化一个空图，设置字体支持中文
        graph = Digraph(
            'DecisionTree',
            format='png',
            node_attr={'fontname': 'SimHei'},  # 支持中文节点
            edge_attr={'fontname': 'SimHei'},  # 支持中文边标签
            graph_attr={'fontname': 'SimHei', 'rankdir': 'TB'}  # 树方向从上往下
        )

    node_id = str(uuid4())  # 生成当前节点的唯一标识符

    if 'label' in tree:
        # 如果是叶子节点，显示类别标签
        label = f"类别: {tree['label']}"
        shape = "box"  # 叶子节点用矩形
    else:
        # 如果是内部节点，显示特征、增益等信息
        feat_name = tree['feature']
        metric = round(tree.get('gain', 0), 3)  # 获取信息增益
        n = tree['n_samples']  # 样本数
        dist = ", ".join([f"{k}={v}" for k, v in tree['class_dist'].items()])  # 分布

        # 构造节点标签
        label = (
            f"{feat_name}\\n"
            f"信息增益={metric}\\n"
            f"样本数={n}\\n"
            f"分布：{dist}"
        )
        shape = "ellipse"  # 内部节点用椭圆

    graph.node(node_id, label=label, shape=shape)  # 添加当前节点到图中

    if parent_id:
        # 如果有父节点，则画边
        graph.edge(parent_id, node_id, label=edge_label)

    if 'children' in tree:
        # 如果有子节点，递归绘制
        feat_name = tree['feature']
        encoder = feature_encoders[feat_name]  # 获取该特征的编码器
        unique_values = df[feat_name].unique()  # 获取原始特征值
        sorted_values = sorted(encoder.transform(unique_values))  # 编码后的排序值

        for raw_value, child in tree['children'].items():
            encoded_value = encoder.transform([raw_value])[0]  # 把原始值转为编码值
            display_label = get_edge_label(feat_name, encoded_value, sorted_values)  # 生成边标签
            # 递归绘制子树
            visualize_tree_cart_style(child, feature_encoders, graph, node_id, display_label)

    return graph


def get_edge_label(feat_name, encoded_value, sorted_values):
    """
    生成边标签，例如：年龄 <= 0.5、年龄 > 0.5
    feat_name: 特征名
    encoded_value: 编码后的特征值
    sorted_values: 排序后的编码值列表
    返回：边标签字符串
    """
    index = sorted_values.index(encoded_value)
    if index == 0:
        threshold = (sorted_values[index] + sorted_values[index + 1]) / 2
        return f"{feat_name} <= {threshold:.1f}"
    elif index == len(sorted_values) - 1:
        threshold = (sorted_values[index - 1] + sorted_values[index]) / 2
        return f"{feat_name} > {threshold:.1f}"
    else:
        low = (sorted_values[index - 1] + sorted_values[index]) / 2
        high = (sorted_values[index] + sorted_values[index + 1]) / 2
        return f"{low:.1f} < {feat_name} <= {high:.1f}"


# =============================================
# 6. 主程序：构建并可视化 ID3 决策树
# =============================================

# 构建模型
tree_id3 = id3_tree(df, features)  # 构建 ID3 决策树

# 设置可视化图例格式
dot_id3 = visualize_tree_cart_style(tree_id3, feature_encoders)  # 可视化 ID3 树

# 保存为 PNG 文件，并自动打开查看
dot_id3.render("id3_decision_tree_with_id", view=True)

2.4 ID3决策树缺陷

ID3决策树的核心优势是计算简单、可解释性强，但存在明显缺陷：倾向于选择取值较多的特征（如"ID"特征可能有最大信息增益），导致过拟合风险。

ID3决策树的缺陷演示：被“ID”特征误导的过拟合

1. 构造含干扰特征的数据集
   在原有贷款数据中加入 “ID” 特征（唯一标识，与贷款结果无实际关联），数据如下：

（共15条，ID=1~15，类别不变）

2. 信息增益计算（核心对比）

   ① 总熵 ( H(D) )
   总样本15条，同意=9，拒绝=6：
   $$H(D)=-\frac{9}{15}{\log }_2\frac{9}{15}-\frac{6}{15}{\log }_2\frac{6}{15}\approx 0.918$$

   ② “ID”特征的信息增益
   “ID”有15个唯一值（每个ID对应1条样本），每个子集 $D_i$ 只有1条样本（纯类别，熵为0）：
   $$H(D|\text{ID})=\sum _{i=1}^{15}\frac{1}{15}\times 0=0\Rightarrow g(D,\text{ID})=0.918-0=0.918$$

   ③ 有效特征“有房子”的信息增益
   “有房子”分两类（无房=8条，有房=7条），条件熵计算得 $H(D|\text{有房子})\approx 0.497$，故：
   $$g(D,\text{有房子})\approx 0.918-0.497=0.421$$

3. 缺陷暴露：被“ID”误导的过拟合

   • 增益排序：g(D, ID) > g(D, 有房子)，ID3会优先选 “ID” 作为根节点。
   • 逻辑荒谬：“ID”是纯标识（与贷款结果无关），但因取值唯一，决策树会分裂出15个叶子节点（每个ID对应一个结果），导致 模型仅记忆样本，无法泛化新数据（如ID=16的新样本，树无法判断）。

这就是ID3的核心缺陷：盲目追求“信息增益最大”，倾向选择取值多的特征（如ID），最终导致过拟合。

三、C4.5决策树：信息增益率的优化

3.1 信息增益率的公式与符号解析

信息增益率公式：
$$\text{Gain\_Ratio}(D,A)=\frac{g(D,A)}{\text{IV}(A)}$$

• $\text{Gain\_Ratio}(D,A)$：特征$A$的信息增益率
• $g(D,A)$：特征$A$的信息增益
• $\text{IV}(A)$：特征$A$的内在信息（分裂信息）
  $$\text{IV}(A)=-\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$
  其中，$n$为特征$A$的取值个数，$|D_i|$为特征$A$取第$i$个值的样本数。

3.2 信息增益率的意义

信息增益率通过引入一个称为内在信息（Intrinsic Value，IV）的指标对信息增益进行归一化处理。其目的是解决ID3算法中偏向于选择取值较多特征的问题。

内在信息 $\text{IV}(A)$ 反映了特征 $A$ 取值分布的均匀程度。分布越均匀，$\text{IV}(A)$ 的值就越大。通过将信息增益除以 $\text{IV}(A)$，信息增益率有效降低了那些取值数量多、但划分意义不大的特征的优先级。

可以将其理解为：信息增益是一个“原始得分”，而信息增益率是根据题目难度调整后的“加权得分”。对于取值较少但具有明显分类效果的特征，它会得到更高的认可，从而避免模型错误地偏好那些取值繁多但实际判别能力一般的特征。

3.3 C4.5决策树：信息增益率修正ID3的过拟合缺陷

含ID特征的数据集构造 ：
在原贷款数据中加入ID列（取值1~15，唯一标识，与贷款结果无关），数据集如下：

步骤1：计算数据集总熵$H(D)$
总样本15条，同意=9，拒绝=6：
$$H(D)=-\frac{9}{15}{\log }_2\frac{9}{15}-\frac{6}{15}{\log }_2\frac{6}{15}\approx 0.918$$

步骤2：计算“ID”特征的信息增益率

• 信息增益 $g(D,\text{ID})$：
  ID有15个唯一值，每个子集仅1条样本（纯类别，熵为0）：
  $$H(D|\text{ID})=\sum _{i=1}^{15}\frac{1}{15}\times 0=0\Rightarrow g(D,\text{ID})=0.918-0=0.918$$

• 内在信息 $\text{IV(ID)}$：
  $$\text{IV(ID)}=-\sum _{i=1}^{15}\frac{1}{15}{\log }_2\frac{1}{15}\approx 3.907$$

• 信息增益率：
  $$\text{Gain\_Ratio}(D,\text{ID})=\frac{0.918}{3.907}\approx 0.235$$

步骤3：计算“有房子”特征的信息增益率

• 信息增益 $g(D,\text{有房子})$：
  有房=7条（同意6，拒绝1），无房=8条（同意2，拒绝6）：
  $$H(D|\text{有房子})=\frac{7}{15}\left(-\frac{6}{7}{\log }_2\frac{6}{7}-\frac{1}{7}{\log }_2\frac{1}{7}\right)+\frac{8}{15}\left(-\frac{2}{8}{\log }_2\frac{2}{8}-\frac{6}{8}{\log }_2\frac{6}{8}\right)\approx 0.497$$

  $$g(D,\text{有房子})=0.918-0.497=0.421$$

• 内在信息 $\text{IV(有房子)}$：

  $$\text{IV(有房子)}=-\frac{7}{15}{\log }_2\frac{7}{15}-\frac{8}{15}{\log }_2\frac{8}{15}\approx 0.998$$

• 信息增益率：
  $$\text{Gain\_Ratio}(D,\text{有房子})=\frac{0.421}{0.998}\approx 0.422$$

特征选择对比

步骤4：递归构建子树

• 分裂子节点：以信息增益率最高的特征（ “有房子” ）为根节点分裂后，得到两个子节点：左子节点：无房样本（8 条，同意 2，拒绝 6）右子节点：有房样本（7 条，同意 6，拒绝 1）递归应用
• C4.5 逻辑：对每个子节点数据集，重复步骤 1-3：计算子节点数据集的总熵 $H(D_i)$；计算各特征（年龄、有工作、信贷情况、ID）的信息增益率；选择信息增益率最大的特征分裂（若存在）。
• 终止条件（满足任一条件则停止分裂）：子节点所有样本属于同一类别（如右子节点 “有房” 样本中 6 同意 1 拒绝，若继续分裂可能得到纯类别节点）；信息增益率小于预设阈值（避免无意义分裂）；特征已全部使用或样本数少于最小阈值。
  $$ID3决策树$$

$$C4.5决策树$$

绘图代码：

# 导入必要的库
import pandas as pd  # 用于数据处理和构建 DataFrame
from collections import Counter  # 用于统计样本数量
from math import log2  # 用于计算对数
from graphviz import Digraph  # 用于可视化决策树
from sklearn.preprocessing import LabelEncoder  # 用于将字符串特征编码为数字


# =============================================
# 1. 数据准备（含 ID）
# =============================================
# 构建训练数据集，包含 5 个特征和 1 个目标变量
data = {
    # 每个样本的唯一编号，容易造成过拟合
    "ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],

    # 年龄：青年、中年、老年
    "年龄": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年",
             "老年", "老年", "老年", "老年", "老年"],

    # 是否有工作：是、否
    "有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否",
               "否", "否", "是", "是", "否"],

    # 是否有房子：是、否
    "有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是",
               "是", "是", "否", "否", "否"],

    # 信贷情况：一般、好、非常好
    "信贷情况": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好",
                 "非常好", "好", "好", "非常好", "一般"],

    # 类别：是否贷款成功（同意/拒绝）
    "类别": ["拒绝", "拒绝", "同意", "同意", "拒绝", "拒绝", "拒绝", "同意", "同意", "同意",
             "同意", "同意", "同意", "同意", "拒绝"]
}

# 将数据转换为 pandas 的 DataFrame 格式
df = pd.DataFrame(data)

# 提取特征列名列表（所有列除了最后一列）
features = list(df.columns[:-1])  # 特征：ID、年龄、有工作、有房子、信贷情况

# 目标变量列名（最后一列）
target = df.columns[-1]  # 类别列名


# =============================================
# 2. 信息熵与信息增益计算
# =============================================

def entropy(y):
    """
    计算信息熵 H(Y)
    y: 当前样本的目标变量值（如：['拒绝', '同意', ...]）
    返回：当前样本的信息熵
    """
    counts = Counter(y)  # 统计每个类别的数量
    total = len(y)  # 总样本数
    if total == 0:
        return 0  # 防止除以 0
    # 计算 -Σ(p * log2(p))
    return -sum((count / total) * log2(count / total) for count in counts.values())


def conditional_entropy(X_col, y):
    """
    计算条件熵 H(Y|X)
    X_col: 某个特征列的值（如：['青年', '中年', ...]）
    y: 对应的目标变量值
    返回：给定该特征下目标变量的条件熵
    """
    values = set(X_col)  # 获取该特征的所有唯一值
    total = len(y)  # 总样本数
    ent = 0
    for v in values:
        mask = (X_col == v)  # 找到该特征值对应的样本
        y_sub = y[mask]  # 取出这些样本的目标变量
        ent += len(y_sub) / total * entropy(y_sub)  # 加权求和
    return ent


def info_gain(dataset, feature):
    """
    计算某个特征的信息增益 IG(Y, X)
    dataset: 整个数据集
    feature: 当前特征名称（如："年龄"）
    返回：该特征的信息增益
    """
    X_col = dataset[feature]  # 取出该特征列
    y = dataset[target]  # 取出目标变量列
    return entropy(y) - conditional_entropy(X_col, y)  # 信息增益 = 总熵 - 条件熵


def split_info(X_col):
    """
    计算分裂信息（Split Information），用于 C4.5 增益率计算
    X_col: 某个特征列的值
    返回：该特征的分裂信息
    """
    counts = Counter(X_col)  # 统计每个特征值出现的次数
    total = len(X_col)  # 总样本数
    # 计算 -Σ(|D_v|/|D| * log2(|D_v|/|D|))
    return -sum((count / total) * log2(count / total) for count in counts.values())


def gain_ratio(dataset, feature):
    """
    计算增益率 GainRatio(Y, X)
    dataset: 整个数据集
    feature: 当前特征名称
    返回：该特征的增益率
    """
    ig = info_gain(dataset, feature)  # 先计算信息增益
    si = split_info(dataset[feature])  # 再计算分裂信息
    return ig / si if si != 0 else float('inf')  # 增益率 = IG / SI


# =============================================
# 3. 手动实现 ID3 和 C4.5 决策树
# =============================================

def id3_tree(dataset, features):
    """
    使用 ID3 算法递归构建决策树
    dataset: 当前数据集
    features: 当前可用特征列表
    返回：当前节点的决策树结构字典
    """
    target_values = dataset[target].unique()  # 获取当前目标变量的唯一值

    # 终止条件1：当前样本全部属于同一类
    if len(target_values) == 1:
        return {'label': target_values[0]}  # 返回叶子节点标签

    # 终止条件2：没有可用特征
    if not features:
        most_common = dataset[target].mode().iloc[0]  # 返回多数类作为预测结果
        return {'label': most_common}

    # 选择信息增益最大的特征
    gains = {f: info_gain(dataset, f) for f in features}  # 计算每个特征的信息增益
    best_feature = max(gains, key=gains.get)  # 选出最大增益的特征

    # 构建当前节点信息
    class_counts = dict(Counter(dataset[target]))  # 统计目标变量分布
    node_info = {
        'feature': best_feature,
        'gain': gains[best_feature],  # 信息增益
        'class_dist': class_counts,  # 类别分布
        'n_samples': len(dataset),  # 样本数量
        'children': {}  # 子节点
    }

    # 递归划分每个特征值
    remaining_features = [f for f in features if f != best_feature]  # 剩余可用特征
    for raw_value in dataset[best_feature].unique():  # 遍历当前特征的每个唯一值
        sub_data = dataset[dataset[best_feature] == raw_value]  # 划分子数据集
        node_info['children'][raw_value] = id3_tree(sub_data, remaining_features)  # 递归生成子树

    return node_info


def c45_tree(dataset, features):
    """
    使用 C4.5 算法递归构建决策树（基于增益率）
    dataset: 当前数据集
    features: 当前可用特征列表
    返回：当前节点的决策树结构字典
    """
    target_values = dataset[target].unique()

    # 终止条件1：当前样本全部属于同一类
    if len(target_values) == 1:
        return {'label': target_values[0]}

    # 终止条件2：没有可用特征
    if not features:
        most_common = dataset[target].mode().iloc[0]
        return {'label': most_common}

    # 选择增益率最大的特征
    gains = {f: gain_ratio(dataset, f) for f in features}
    best_feature = max(gains, key=gains.get)

    # 构建当前节点信息
    class_counts = dict(Counter(dataset[target]))
    node_info = {
        'feature': best_feature,
        'gain_ratio': round(gains[best_feature], 3),
        'class_dist': class_counts,
        'n_samples': len(dataset),
        'children': {}
    }

    # 递归划分每个特征值
    remaining_features = [f for f in features if f != best_feature]
    for raw_value in dataset[best_feature].unique():
        sub_data = dataset[dataset[best_feature] == raw_value]
        node_info['children'][raw_value] = c45_tree(sub_data, remaining_features)

    return node_info


# =============================================
# 4. 构建特征编码器（用于生成 CART 风格的分割条件）
# =============================================
# 保存每个特征的编码器，便于后续可视化时使用
feature_encoders = {}

for feat in features:
    le = LabelEncoder()  # 创建编码器
    le.fit(df[feat])  # 拟合该特征的编码规则
    feature_encoders[feat] = le  # 保存编码器


# =============================================
# 5. 决策树可视化（CART 风格，支持中文）
# =============================================
def visualize_tree_cart_style(tree, feature_encoders, graph=None, parent_id=None, edge_label=""):
    """
    使用 Graphviz 可视化决策树（CART 风格）
    tree: 当前树节点结构
    feature_encoders: 编码器字典
    graph: 当前图对象
    parent_id: 父节点 ID
    edge_label: 边上的标签
    返回：Graphviz 图对象
    """
    from uuid import uuid4  # 用于生成唯一节点 ID

    if graph is None:
        # 初始化一个空图，设置字体支持中文
        graph = Digraph(
            'DecisionTree',
            format='png',
            node_attr={'fontname': 'SimHei'},  # 支持中文节点
            edge_attr={'fontname': 'SimHei'},  # 支持中文边标签
            graph_attr={'fontname': 'SimHei', 'rankdir': 'TB'}  # 树方向从上往下
        )

    node_id = str(uuid4())  # 生成当前节点的唯一标识符

    if 'label' in tree:
        # 如果是叶子节点，显示类别标签
        label = f"类别: {tree['label']}"
        shape = "box"  # 叶子节点用矩形
    else:
        # 如果是内部节点，显示特征、增益等信息
        feat_name = tree['feature']
        metric = round(tree.get('gain', tree.get('gain_ratio', 0)), 3)  # 获取指标值
        metric_label = "信息增益" if 'gain' in tree else "信息增益率"
        n = tree['n_samples']  # 样本数
        dist = ", ".join([f"{k}={v}" for k, v in tree['class_dist'].items()])  # 分布

        # 构造节点标签
        label = (
            f"{feat_name}\\n"
            f"{metric_label}={metric}\\n"
            f"样本数={n}\\n"
            f"分布：{dist}"
        )
        shape = "ellipse"  # 内部节点用椭圆

    graph.node(node_id, label=label, shape=shape)  # 添加当前节点到图中

    if parent_id:
        # 如果有父节点，则画边
        graph.edge(parent_id, node_id, label=edge_label)

    if 'children' in tree:
        # 如果有子节点，递归绘制
        feat_name = tree['feature']
        encoder = feature_encoders[feat_name]  # 获取该特征的编码器
        unique_values = df[feat_name].unique()  # 获取原始特征值
        sorted_values = sorted(encoder.transform(unique_values))  # 编码后的排序值

        for raw_value, child in tree['children'].items():
            encoded_value = encoder.transform([raw_value])[0]  # 把原始值转为编码值
            display_label = get_edge_label(feat_name, encoded_value, sorted_values)  # 生成边标签
            # 递归绘制子树
            visualize_tree_cart_style(child, feature_encoders, graph, node_id, display_label)

    return graph


def get_edge_label(feat_name, encoded_value, sorted_values):
    """
    生成边标签，例如：年龄 <= 0.5、年龄 > 0.5
    feat_name: 特征名
    encoded_value: 编码后的特征值
    sorted_values: 排序后的编码值列表
    返回：边标签字符串
    """
    index = sorted_values.index(encoded_value)
    if index == 0:
        threshold = (sorted_values[index] + sorted_values[index + 1]) / 2
        return f"{feat_name} <= {threshold:.1f}"
    elif index == len(sorted_values) - 1:
        threshold = (sorted_values[index - 1] + sorted_values[index]) / 2
        return f"{feat_name} > {threshold:.1f}"
    else:
        low = (sorted_values[index - 1] + sorted_values[index]) / 2
        high = (sorted_values[index] + sorted_values[index + 1]) / 2
        return f"{low:.1f} < {feat_name} <= {high:.1f}"


# =============================================
# 6. 主程序：构建并可视化两种树
# =============================================

# 构建模型
tree_id3 = id3_tree(df, features)  # 构建 ID3 决策树
tree_c45 = c45_tree(df, features)  # 构建 C4.5 决策树

# 设置可视化图例格式
dot_id3 = visualize_tree_cart_style(tree_id3, feature_encoders)  # 可视化 ID3 树
dot_c45 = visualize_tree_cart_style(tree_c45, feature_encoders)  # 可视化 C4.5 树

# 保存为 PNG 文件，并自动打开查看
dot_id3.render("id3_decision_tree_with_id", view=True)
dot_c45.render("c45_decision_tree_with_id", view=True)

3.4 结论：C4.5如何解决过拟合

• ID3的缺陷：ID特征因信息增益最大（0.918）被优先选择，导致树分裂为15个叶子节点，完全记忆训练数据（过拟合）。
• C4.5的修正：ID的信息增益虽高，但内在信息$V(ID)$=3.907极大，导致信息增益率（0.235）低于“有房子”（0.422），因此C4.5选择 “有房子” 作为根节点，避免被ID特征误导。
• 本质原因：信息增益率通过IV(A)惩罚了取值多但分类意义小的特征（如ID），使模型更关注真正有判别力的特征，降低过拟合风险。

3.5 C4.5的局限性

• 对取值少的特征仍有偏向：若某特征取值少且IV(A)小，可能被过度优先选择（如两取值特征，IV=1时信息增益率=信息增益）。
• 计算复杂度高：需额外计算IV(A)，比ID3耗时更多。

通过信息增益率的归一化，C4.5在保留ID3可解释性的同时，有效缓解了“取值多特征偏好”问题，是决策树从理论到工程应用的重要改进。

四、CART决策树：基于基尼指数的二叉树模型

CART 决策树是一种基于基尼指数（或平方误差）的二叉树模型，广泛应用于分类和回归任务中。它通过最小化基尼指数来选择最优划分特征，确保每一步划分都能带来最大纯度提升。相较于 ID3 或 C4.5 等多叉树模型，CART 结构简单、计算效率高、鲁棒性强，是工业界常用的一种决策树实现方式。

4.1 基尼指数的公式与符号解析

基尼指数相关公式：

• 数据集$D$的基尼值：
  $$\text{Gini}(D)=1-\sum _{k=1}^K{\left(\frac{|C_k|}{|D|}\right)}^2$$

• 特征$A$的基尼指数：
  $$\text{Gini\_index}(D,A)=\sum _{i=1}^n\frac{|D_i|}{|D|}\text{Gini}(D_i)$$

• $\text{Gini}(D)$：衡量数据集$D$的不纯度，值越小纯度越高

• $\text{Gini\_index}(D,A)$：特征$A$的基尼指数，用于选择最优分裂特征

• $K$：类别数，$|C_k|$：第$k$类的样本数，$|D|$：总样本数

• $n$：特征$A$的取值个数，$|D_i|$：特征$A$取第$i$个值的样本数

4.2 基尼指数的意义

• 基尼指数衡量的是从数据集中随机抽取两个样本时，它们类别不一致的概率。这个指标越小，说明数据集的纯度越高；反之，则表示数据越混杂。

• 在决策树构建过程中，当我们使用某个特征对数据集进行划分后，会分别计算每个子集的基尼指数，并通过加权求和得到整体的基尼指数（即 $\text{Gini\_index}(D,A)$ ）。该值越小，意味着划分后的各子集纯度越高，分类效果越好。

• 可以形象地理解为：假设你有一袋球，颜色各异。如果你随手抓出两个球，颜色不一样的可能性越大，说明这袋球越“混乱”（基尼值高）。我们的目标是找到一种分法（特征），让每次分出来的每一小袋都尽可能接近“同色”，也就是让每袋的基尼指数尽可能小。

4.3 CART决策树案例演示：贷款申请的基尼指数计算

沿用前例，计算特征"有房子"的基尼指数（CART为二叉树，需将多取值特征转化为二叉分裂）。

步骤1：计算数据集D的基尼值
$$\text{Gini}(D)=1-{\left(\frac{5}{15}\right)}^2-{\left(\frac{10}{15}\right)}^2=0.4444$$

步骤2：计算"有房子"特征的基尼指数

• 有房子：7条样本，6同意，1拒绝
  $$\text{Gini}(有房子)=1-{\left(\frac{6}{7}\right)}^2-{\left(\frac{1}{7}\right)}^2=0.2449$$
• 无房子：8条样本，2同意，6拒绝
  $$\text{Gini}(无房子)=1-{\left(\frac{2}{8}\right)}^2-{\left(\frac{6}{8}\right)}^2=0.375$$
• 基尼指数：
  $$\text{Gini\_index}(D,有房子)=\frac{7}{15}\times 0.2449+\frac{8}{15}\times 0.375=0.3176$$

步骤3：计算其他特征的基尼指数
以"年龄"特征为例，需转化为二叉分裂（如"青年"vs"非青年"）：

• 青年：5样本，4拒绝，1同意
  $$\text{Gini}(青年)=1-{\left(\frac{4}{5}\right)}^2-{\left(\frac{1}{5}\right)}^2=0.32$$
• 非青年：10样本，6拒绝，4同意
  $$\text{Gini}(非青年)=1-{\left(\frac{6}{10}\right)}^2-{\left(\frac{4}{10}\right)}^2=0.48$$
• 基尼指数：
  $$\text{Gini\_index}(D,年龄)=\frac{5}{15}\times 0.32+\frac{10}{15}\times 0.48=0.4267$$

步骤4：选择基尼指数最小的特征
"有房子"的基尼指数0.3176最小，作为分裂特征，生成二叉树：

• 左子树：有房子，基尼值0.2449（更纯）
• 右子树：无房子，基尼值0.375（较不纯）

步骤5：递归构建子树
在完成当前节点的最佳划分特征选择后（如“有房子”），CART 决策树会基于该特征的不同取值，将数据集划分为两个子集，并对每个子集递归地重复以下过程：

• 判断是否满足终止条件：
  • 若当前子集中所有样本属于同一类别（基尼值为 0），则将其设为叶子节点，直接返回类别结果。
  • 若达到预设的最大深度（如 max_depth=3）或样本数过少（如小于 min_samples_split），也停止继续分裂。
• 否则，继续进行最优划分特征的选择：
  • 对当前子集重新计算各个特征的基尼指数。
  • 选择基尼指数最小的特征作为新的划分依据。
  • 再次划分数据集并生成新的左右子节点：
  • 每个子节点代表一个划分后的子集。
  • 对每个子节点递归执行上述步骤，直到满足终止条件为止。
• 最终形成一棵完整的二叉决策树：

绘图代码：

# 导入必要的库
import pandas as pd  # 用于构建 DataFrame 数据结构
from sklearn.tree import DecisionTreeClassifier, plot_tree  # 构建和可视化决策树
from sklearn.preprocessing import LabelEncoder  # 对字符串特征进行编码
import matplotlib.pyplot as plt  # 可视化工具

# 设置中文字体显示（解决中文乱码问题）
plt.rcParams['font.sans-serif'] = ['SimHei']  # 将默认字体设置为"SimHei（黑体）"，确保中文标签正常显示
plt.rcParams['axes.unicode_minus'] = False  # 修复负号显示为方块的问题（确保特殊符号渲染正常）

# =============================================
# 1. 数据准备（含 ID）
# =============================================
# 构建训练数据集，包含 5 个特征和 1 个目标变量
data = {
    # 每个样本的唯一编号，容易造成过拟合
    "ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],

    # 年龄：青年、中年、老年
    "年龄": ["青年", "青年", "青年", "青年", "青年", "中年", "中年", "中年", "中年", "中年",
             "老年", "老年", "老年", "老年", "老年"],

    # 是否有工作：是、否
    "有工作": ["否", "否", "是", "是", "否", "否", "否", "是", "否", "否",
               "否", "否", "是", "是", "否"],

    # 是否有房子：是、否
    "有房子": ["否", "否", "否", "是", "否", "否", "否", "是", "是", "是",
               "是", "是", "否", "否", "否"],

    # 信贷情况：一般、好、非常好
    "信贷情况": ["一般", "好", "好", "一般", "一般", "一般", "好", "好", "非常好", "非常好",
                 "非常好", "好", "好", "非常好", "一般"],

    # 类别：是否贷款成功（同意/拒绝）
    "类别": ["拒绝", "拒绝", "同意", "同意", "拒绝", "拒绝", "拒绝", "同意", "同意", "同意",
             "同意", "同意", "同意", "同意", "拒绝"]
}

# 将数据转换为 pandas 的 DataFrame 格式
df = pd.DataFrame(data)

# 提取特征和目标变量
X = df.drop("类别", axis=1)  # 特征：年龄、有工作、有房子、信贷情况
y = df["类别"]  # 目标变量：类别（是否贷款成功）

# =============================================
# 2. 特征编码（将字符串特征转为数字）
# =============================================
# 创建 LabelEncoder 并对每个特征列进行编码
encoders = {}  # 存储每个特征的编码器
for col in X.columns:
    le = LabelEncoder()
    X[col] = le.fit_transform(X[col])  # 转换为数字
    encoders[col] = le  # 保存编码器供后续反编码用

# 对目标变量进行编码：'拒绝' -> 0, '同意' -> 1
y = LabelEncoder().fit_transform(y)

# =============================================
# 3. 构建 CART 决策树模型
# =============================================
# 创建 CART 分类器，使用默认的 gini 指数作为划分标准
clf = DecisionTreeClassifier(criterion='gini', max_depth=3)

# 训练模型
clf.fit(X, y)

# =============================================
# 4. 使用 matplotlib 可视化决策树结构
# =============================================
# 设置绘图风格
plt.figure(figsize=(10, 6))  # 设置画布大小

# 绘制决策树结构图
plot_tree(
    clf,  # 决策树模型
    feature_names=X.columns,  # 特征名称
    class_names=["拒绝", "同意"],  # 类别名称（中文支持）
    filled=True,  # 使用颜色填充节点
    fontsize=10,  # 字体大小
    proportion=False,  # 显示样本数量而非比例
    rounded=True  # 圆角矩形显示节点
)

# 设置图像标题并调整布局
plt.title("CART 决策树结构（基于基尼指数）")
plt.tight_layout()  # 自动调整子图参数，防止重叠

# 显示图像
plt.show()

4.4 Scikit-learn 中 CART 决策树的 API

1. 分类树：DecisionTreeClassifier
   用于离散标签分类（如是否贷款），基于基尼指数或信息熵生成二叉树。

• 核心参数：
  criterion 控制分裂标准（gini为默认基尼指数，entropy为信息熵）；
  max_depth 限制树深度（避免过拟合，如设为3-10）；
  min_samples_split 规定节点分裂的最小样本数（默认2）；
  min_samples_leaf 设定叶子节点最小样本数（默认1）。
• 关键方法：
  fit(X, y) 训练模型（X为特征矩阵，y为离散标签）；
  predict(X) 预测类别；
  predict_proba(X) 输出类别概率；
  score(X, y) 计算准确率。

2. 回归树：DecisionTreeRegressor
   用于连续值预测（如房价），基于均方误差或平均绝对误差分裂。

• 核心参数：
  criterion 可选mse（均方误差，默认）或mae（平均绝对误差）；
  其他参数（如max_depth、min_samples_split）与分类树逻辑一致。
• 关键方法：
  fit(X, y) 训练模型（y为连续值）；
  predict(X) 输出回归值；
  score(X, y) 计算R²系数（越接近1拟合越好）。

3. 核心共通点

• 分裂策略：splitter='best'（全局最优）或'random'（随机分裂防过拟合）；
• 特征重要性：训练后通过feature_importances_属性获取；
• 可视化：用sklearn.tree.export_graphviz或plot_tree展示树结构。

4. 分类与回归差异
   分类树用基尼/熵衡量纯度，输出类别概率；回归树用MSE/MAE衡量误差，输出连续值预测，评估指标为R²而非准确率。

4.5 小结

CART决策树的核心优势在于：

1. 始终生成二叉树，结构更简单
2. 基尼指数计算效率高于熵运算
3. 同时支持分类和回归任务（回归时使用平方误差最小化）
4. 对噪声数据和缺失值的处理更鲁棒

五、三大决策树模型对比总结

决策树的发展历程体现了机器学习算法的优化思路——从简单有效到复杂精准，再到平衡效率与性能。实际应用中，可根据数据特点和任务需求选择合适的决策树模型，或采用集成学习（如随机森林）进一步提升模型效果。

六、其他重要决策树算法

6.1 CHAID：基于统计检验的决策树

核心思想：使用卡方检验（分类目标）或F检验（连续目标）评估特征与目标的相关性

公式示例：
$${\chi }^2=\sum \frac{(O_i-E_i{)}^2}{E_i}$$
其中$O_i$为观察频数，$E_i$为期望频数

优势：

• 支持多叉分裂，直观展示特征交互作用
• 自动处理缺失值
• 可生成非二叉树结构

应用场景：市场细分、客户画像分析

6.2 QUEST：快速无偏决策树

核心思想：通过统计检验选择分裂特征，避免CART对连续特征的偏向

算法流程：

1. 使用ANOVA F-test选择最佳分裂特征
2. 应用二次判别分析确定最优分裂点
3. 递归构建二叉树

优势：

• 无偏特征选择
• 计算效率高
• 处理高维数据能力强

应用场景：基因表达数据分析、高维生物信息学

6.3 条件推断树：统计驱动的决策树

核心思想：基于置换检验（Permutation Test）选择分裂变量和分裂点

算法特点：

1. 计算特征与目标的统计相关性
2. 评估分裂显著性的p值
3. 仅当p值小于阈值时才进行分裂

公式核心：
$$p\text{-value}=P(|T|\ge |t||H_0)$$
其中$T$为检验统计量，$t$为观察值，$H_0$为无关联假设

优势：

• 有效控制变量选择偏差
• 适用于混合类型特征（离散+连续）
• 提供统计显著性评估

应用场景：临床试验数据分析、社会科学研究

6.4 斜决策树（Oblique Decision Tree）

核心思想：允许使用特征的线性组合进行分裂（如$0.5\times \text{年龄}+0.8\times \text{收入}>50$）

数学表示：
$$\sum _{j=1}^p{w}_j{x}_j>\theta$$
其中$w_j$为特征权重，$\theta$为阈值

优势：

• 构建更紧凑的树结构
• 提升模型泛化能力
• 更好处理相关特征

挑战：

• 分裂点优化复杂度高
• 需结合线性规划求解
• 训练时间显著增加

应用场景：图像识别、金融风险评估

6.5 流数据决策树（Hoeffding Tree）

核心思想：基于Hoeffding不等式，在有限内存下处理无限数据流

核心公式：
$$n>\frac{R^2\ln (1/\delta )}{2{ϵ}^2}$$
其中$n$为所需样本数，$R$为随机变量范围，$\delta$为置信度，$ϵ$为误差界

优势：

• 单次遍历数据
• 实时更新模型
• 有限内存需求

应用场景：实时交易监控、物联网设备数据分析