决策树模型

树模型是有监督学习类算法中应用广泛的一类模型，同时可应用于分类问题和回归问题，其中用于解决分类问题的树模型常被称为分类树，而用于解决回归问题的树模型被称为回归树。

树模型通过递归式切割的方法来寻找最佳分类标准，进而最终形成规则。其算法原理虽然简单，但模型本身使用面极广，且在分类问题和回归问题上均有良好的表现，外加使用简单，无需人为进行过多变量调整和数据预处理，同时生成规则清晰，模型本身可解释性非常强，因此在各个行业均有广泛应用。

决策树（Decision Tree）是一种实现分治策略的层次数据结构，它是一种有效的非参数学习方法，并可以用于分类和回归，我们主要讨论分类的决策树。分类决策树模型表示一种基于特征对实例进行分类的属性结构（包括二叉树和多叉树）。

决策树节点

决策树由节点（Node）和有向边（Directed edge）组成，树中包含三种节点：

  • 根节点（Root Node）：包含样本全集，没有入边，但有零条或多条出边
  • 内部节点（Internal Node）：对应于属性测试条件，恰有一条入边，和两条或多条出边
  • **叶节点（Leaf Node）或终节点（Terminal Node）：对应于决策结果，恰有一条入边，但没有出边

决策树基本流程

从根节点到每个叶子节点的路径对应了一个判定测试序列，其基本流程遵循了简单且直观的”分而治之”策略。由此，局部区域通过少数几步递归分裂确定，每个决策节点实现一个具有离散输出的属性测试函数，标记分支。

决策与条件概率分布

决策树是一种基于概率统计的机器学习模型，其本质可以理解为在给定决策节点下对类别变量的条件概率分布建模。

  1. 概率分布的定义与划分：

    • 决策树将特征空间 X 划分为若干个互不重叠的区域 R1, R2,…, Rm
    • 在每个区域 Rj 上定义了一个条件概率分布 P(Y|X ∈ Rj)
    • 这个概率分布定义在类别变量 Y 的所有可能取值上

  2. 树结构的概率解释：

    • 根节点对应整个特征空间的初始划分
    • 每个内部决策节点代表对当前区域的进一步细分
    • 随着从根节点到叶节点的路径延伸，特征空间被递归地划分为更小的子区域
    • 最终每个叶节点对应特征空间的一个特定区域 Rj

  3. 条件概率的特性：

    • 在训练过程中，通过统计落入每个区域的样本类别分布来估计 P(Y|X ∈ Rj)
    • 通常情况下，叶节点上的条件概率会呈现明显偏向性，即某个类别的概率显著高于其他类别
    • 例如，在二分类问题中，某个叶节点可能得到 P(Y=1|X ∈ Rj)=0.85，P(Y=0|X ∈ Rj)=0.15

  4. 分类决策过程：

    • 对于新样本 x，决策树会将其路由到对应的叶节点（区域 Rj）
    • 根据该节点的条件概率分布，采用最大后验概率(MAP)准则进行分类：
    ŷ = argmax_y P(Y=y|X ∈ Rj)
    • 这意味着即使某个类别的概率不是100%，决策树仍会将该样本强行划分到概率最大的类别

这种概率解释框架为理解决策树的工作原理提供了理论基础，也解释了为什么决策树容易在训练数据上达到100%准确率（通过不断细分直到每个叶节点只包含单一类别的样本）。

学习算法

决策树学习是一种通过归纳训练数据集来构建分类规则的机器学习方法，也称为”树归纳”过程。

  1. 模型选择原则：

    • 对于同一个训练数据集，可能存在无数棵能够完美分类的决策树。我们追求的是其中”最小”的树
    • 从概率角度解释，决策树实际上是在估计条件概率模型

  2. 算法执行过程：

    • 算法开始时，整个训练数据集位于根节点
    • 在每个划分步骤中，算法会对连续值属性寻找最优分割点，对离散值属性根据属性值划分
    • 划分标准通常基于：信息增益（ID3算法）、信息增益比（C4.5算法）、基尼指数（CART算法）
    • 递归地对每个子集重复上述过程，直到满足停止条件

  3. 停止条件：

    • 当前子集中的样本基本属于同一类别（如95%以上）
    • 没有合适的特征可供继续划分
    • 达到预设的树深度限制

决策树学习算法包括特征选择、决策树的生成与决策树的剪枝。由于决策树表示一个条件概率的分布，所以深浅不同的决策树对应着不同复杂度的概率模型，其中决策树的生成只考虑局部最优，相对的，决策树的剪枝则考虑全局最优。

香农熵的计算

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点纯度（purity）越来越高。

在信息论与概率统计中，熵是表示随机变量不确定性的度量。这里我们使用的熵也叫做香农熵，这个名字来源信息论之父克劳德·香农。

香农熵公式：

H(X) = -∑p(xi)log₂(p(xi))

对于二分类问题：

  • 如果 p1=1 而 p2=0，熵为0（确定性）
  • 如果 p1 = p2 = 0.5，熵为1（最大不确定性）

其他不纯度度量

除了香农熵，还有其他常用的不纯度度量方法：

  1. 基尼指数（Gini Index）：

    Gini = 1 - ∑p(xi)²

  2. 误分类率（Misclassification Error）：

    Error = 1 - max(p)

三种方法都在类分布均衡时（即当 p=0.5 时）达到最大值，而当所有记录都属于同一个类时（p=1 或 p=0）达到最小值。

香农熵的Python代码实现

import pandas as pd
import numpy as np

row_data = {
    '是否陪伴': [0,0,0,1,1],
    '是否玩游戏': [1,1,0,1,1],
    '渣男': ['是','是','不是','不是','不是']
}

dataSet = pd.DataFrame(row_data)

def calEnt(dataSet):
    # 数据集总行数
    n = dataSet.shape[0]
    # 标签的所有类别
    iset = dataSet.iloc[:,-1].value_counts()
    # 每一类标签所占比
    p = iset/n
    # 计算信息熵
    ent = (-p*np.log2(p)).sum()
    return ent

calEnt(dataSet)

熵越高，信息的不纯度就越高，则混合的数据就越多。也就是说，单从判断的结果来看，如果你从这5个人中瞎猜，要准确判断其中一个人是不是”bad boy”是不容易的。

常见错误速查

症状根因定位修复
训练集准确率极高，测试集明显下降树太深、叶子样本数过小，持续细分导致过拟合预剪枝（max_depth/min_samples_leaf）、后剪枝
划分结果不稳定、轻微数据扰动树结构大变决策树高方差模型用集成方法（RandomForest/GBDT）或限制深度
连续特征划分效果差连续变量切分点选择不佳检查候选切分点枚举逻辑；采用基于不纯度的最优切分点搜索
类别极不均衡时，叶子节点概率偏置明显叶节点概率被多数类主导代价敏感学习/类权重/重采样
熵计算得到 NaN/inf概率为0导致 log(0)对概率加极小值 epsilon