决策树入门指南：从原理到实践
目录1 决策树的根本原理与理论底子
1.1 根本原理与界说
1.2 决策边界特性
2 特性选择与分别准则
2.1 信息增益与信息增益比
2.2 Gini指数
3 树的生成与剪枝优化
3.1 剪枝的理论底子
3.2 预剪枝计谋
3.2.1根本原理
3.2.2 常用的停止准则
3.3 后剪枝计谋
3.3.1 代表性算法
3.3.2 剪枝效果评估
4 一连值处置惩罚
4.1 理论底子
4.2 二分法处置惩罚计谋
4.2.1 候选分别点选择
4.2.2 最优分别点确定
4.3 多区间离散化
4.3.1 Kettering-Ming方法
4.3.2 ChiMerge算法
一连值处置惩罚
5 缺失值处置惩罚
5.1 理论模子
5.1.1 EM框架
5.2 练习阶段计谋
5.2.1 实例权重法
缺失值处置惩罚
6 主流决策树算法比力
6.1 核默算法对比
6.1.1 ID3 (Iterative Dichotomiser 3)
6.1.2 C4.5 (ID3的改进版本)
6.1.3 CART (Classification And Regression Tree)
6.2 算法性能对比
6.2.1 特性对比矩阵
7 实际应用建议
7.1 场景选择指南
7.2 改进方向比力
7.3 随机丛林优化
1 决策树的根本原理与理论底子
1.1 根本原理与界说
决策树是一种非参数化的监督学习方法，它通过树形结构对特性空间进行分别，从而实现分类或回归。决策树是一种将特性空间分别为多少个单纯地区的分类器。从几何角度看,决策树通过一系列平行于坐标轴的超平面将特性空间递归分别,每个叶节点对应于一个单纯形地区。情势化地说,一棵决策树可以表现为:
https://latex.csdn.net/eq?f%28x%29%3D%5Csum%20_%7Bm%3D1%7D%5E%7BM%7Dc_%7Bm%7DI%28x%5Cin%20R_%7Bm%7D%29
Rm表现第m个叶节点对应的地区,cm为该地区的推测值。这种分段常数的情势使得决策树具有很好的可表明性。
从信息论的角度来看，决策树的构建过程本质上是一个信息增益的最大化过程。在每个节点，我们选择最优的特性及其分割点，使得子节点的纯度相比父节点有最大的提拔。
1.2 决策边界特性
从几何角度看,决策树生成的决策边界具有以下特点:
[*]边界平行于坐标轴
[*]分段线性
[*]具有局部顺应性,即不同地区可以有不同的复杂度
这些特性决定了决策树特别得当处置惩罚非线性但轴平行的决策边界,但对斜向的线性边界则必要许多次分别才能逼近。
这些理论底子不光资助我们更深入地明白决策树的工作原理,也为实践中的参数选择和模子改进提供了重要引导。例如:
[*]信息论视角启发了各种基于熵的分别准则
[*]优化理论表明了为什么要使用贪心计谋
[*]PAC理论和VC维分析引导了剪枝计谋的设计
[*]概率图模子的表明促进了决策树与其他模子的结合
2 特性选择与分别准则
2.1 信息增益与信息增益比
对于分类问题，最常用的分别准则是信息增益和信息增益比。信息增益基于熵的概念：
https://latex.csdn.net/eq?Gain%28D%2Ca%29%3DH%28D%29-%5Csum%20_%7Bv%3D1%7D%5E%7BV%7D%5Cfrac%7B%7CD%5E%7Bv%7D%7C%7D%7B%7CD%7C%7DH%28D%5E%7Bv%7D%29
其中，H(D) 表现数据集D的熵：
https://latex.csdn.net/eq?H%28D%29%3D-%5Csum%20_%7Bk%3D1%7D%5E%7BK%7D%5Cfrac%7B%7CC_%7Bk%7D%7C%7D%7B%7CD%7C%7Dlog_%7B2%7D%5Cfrac%7B%7CC_%7Bk%7D%7C%7D%7B%7CD%7C%7D
为了降服信息增益偏向于选择取值较多的特性的缺点，引入了信息增益比：
https://latex.csdn.net/eq?Gain-Ratio%28D%2Ca%29%3D%5Cfrac%7BGain%28D%2Ca%29%7D%7BH_%7Ba%7D%28D%29%7D
2.2 Gini指数
CART树采用基尼指数作为分别准则：
https://latex.csdn.net/eq?Gini%28D%29%3D1-%7Bk%3D1%7D%5Csum%20_%7Bk%3D1%7D%5E%7BK%7D%28%5Cfrac%7B%7CC_%7Bk%7D%7C%7D%7B%7CD%7C%7D%29%5E%7B2%7D
3 树的生成与剪枝优化
https://i-blog.csdnimg.cn/direct/754dc904b17c4d889cd9d828cd3b4eb1.png
3.1 剪枝的理论底子
剪枝是决策树学习中解决过拟合的关键技术。从毛病-方差分解的角度看,剪枝通过增加模子毛病来低落方差,从而在两者之间寻找最优平衡点。我们可以将剪枝问题情势化为带束缚的优化问题：
https://i-blog.csdnimg.cn/direct/aee139b8825040bcae7dfa9158313cd8.png
其中∣T∣为树的节点数,α为复杂度参数,Rt为叶节点t对应的地区。
3.2 预剪枝计谋
3.2.1根本原理
预剪枝在决策树生长过程中进行,通过及时停止某些分支的生长来防止过拟合。这种"前瞻性"的计谋可以节省练习时间,但可能会太过守旧。
预剪枝是在决策树生成过程中，对每个节点在分别前进行评估。假如当前节点的分别不能带来统计意义上的明显性提拔，则停止分别并将当前节点标志为叶节点。预剪枝的主要优点是可以防止过拟合，缺点是可能会带来欠拟合。
3.2.2 常用的停止准则
基于纯度阈值 当节点的纯度指标(如基尼指数)小于阈值ϵ时停止分别:
https://latex.csdn.net/eq?Gini%28D%29%3D1-%5Csum_%7Bk%3D1%7D%5E%7B%7Cy%7C%7Dp_%7Bk%7D%5E%7B2%7D%3C%20%5Cvarepsilon
基于样本数量 当节点样本数小于阈值时停止分别,制止统计不稳定性:
https://latex.csdn.net/eq?%7CD_%7Bt%7D%7C%3C%20min%5C%3B%20samples%5C%2C%20split
基于信息增益 当最佳分别的信息增益小于阈值时停止:
https://latex.csdn.net/eq?Gain%28D%2CA%29%3C%20min-gain-threshold
基于验证集精度 通过验证集评估分别的必要性:
https://latex.csdn.net/eq?Accuracy%28D_%7Bval%7D%5E%7Bsplit%7D%29%5Cleq%20Accuracy%28D_%7Bval%7D%5E%7Bsplit%7D%29+%5Cdelta
3.3 后剪枝计谋
后剪枝是在决策树完全生成后，自底向上地对非叶节点进行评估。对于每个非叶节点，我们计算假如将该节点及其子树更换为叶节点后的性能变化。假如性能提拔或丧失在可担当范围内，则进行剪枝。后剪枝通常能得到更好的效果，但计算开销较大。
3.3.1 代表性算法
[*]错误率低落剪枝(Reduced Error Pruning, REP)
[*]自下而上遍历内部节点
[*]比力剪枝前后验证集错误率
[*]选择能低落错误率的剪枝操纵
https://latex.csdn.net/eq?Error%28T%5E%7B%27%7D%29%3C%20Error%28T%29
代价复杂度剪枝（Cost-Complexity Pruning）是一种典范的后剪枝方法，其优化目标为：
https://latex.csdn.net/eq?R_%7B%5Calpha%20%7D%28T%29%3DR%28T%29+%5Calpha%20%7CT%7C
其中R(T)为练习误差,α为复杂度参数。
[*]悲观剪枝(Pessimistic Error Pruning, PEP)
[*]使用统计置信上界估计泛化误差:
https://latex.csdn.net/eq?R_%7Bupper%7D%28T%29%3DR%28T%29+%5Csqrt%7B%5Cfrac%7BR%28T%29%281-T%28T%29%29%7D%7BN%7D%7D+%5Cfrac%7B%7CT%7C%7D%7B2N%7D
3.3.2 剪枝效果评估
为了科学评估剪枝效果,我们通常考虑以下指标:
[*]性能度量:
[*]精确率变化
[*]AUC-ROC曲线变化
[*]交叉验证得分
[*]结构度量:
[*]树的深度淘汰比例
[*]节点数淘汰比例
[*]均匀分支因子变化
4 一连值处置惩罚
4.1 理论底子
一连特性的处置惩罚本质上是将一连域离散化的过程。从信息论角度看，这是一个信息压缩的过程，目标是在保留关键信息的同时低落模子复杂度。形式化地，对于一连特性A，我们寻找最优分别点集合：
https://i-blog.csdnimg.cn/direct/2deb24936a06450d8162f9abe7a5bb59.png
4.2 二分法处置惩罚计谋
4.2.1 候选分别点选择
[*]排序法
https://i-blog.csdnimg.cn/direct/8fabfd2a2090464c96baff2b7ffd25cb.png
其中ai为特性A的第i个取值。
[*]分位数法 使用等频或等宽的分位数作为候选分别点：
https://i-blog.csdnimg.cn/direct/47d24b2d3a3a4c83a3494b211cf02885.png
4.2.2 最优分别点确定
1.基于信息增益：
https://i-blog.csdnimg.cn/direct/c440a4ac1827403d85388113c1b6051a.png
2.基于基尼指数：
https://i-blog.csdnimg.cn/direct/57818cbc04ef4ec697bc077c5baaa034.png
4.3 多区间离散化
4.3.1 Kettering-Ming方法
[*]初始化为二分类
[*]递归分别子区间：
https://i-blog.csdnimg.cn/direct/93677be7ecc447f6a6715ad19fcf1ab1.png
其中N为样本数，)Δ(A)为编码长度增量。
4.3.2 ChiMerge算法
基于卡方查验的自底向上归并：
https://i-blog.csdnimg.cn/direct/e49fe8bf566e47cf9dffdbec8820f264.png
一连值处置惩罚
[*]对于高基数一连特性，优先考虑分位数法以控制分别点数量
[*]在计算资源允许的情况下，可以使用动态规划寻找全局最优分别
[*]结合业务知识设定分别点，提高模子可表明性
5 缺失值处置惩罚
5.1 理论模子
5.1.1 EM框架
将缺失值处置惩罚建模为一个EM问题：
[*]E步：估计缺失值的概率分布
[*]M步：基于完整数据优化决策树参数
概率模子：
https://i-blog.csdnimg.cn/direct/14165d1c6ad94066a8d67cede12956df.png
5.2 练习阶段计谋
5.2.1 实例权重法
1.权重计算 对于特性A的取值a：
https://i-blog.csdnimg.cn/direct/7fd81338b8294ce8bd76f96c56ec9f38.png
2.信息增益计算 修正的信息增益公式：
https://i-blog.csdnimg.cn/direct/e49707a4a7394557a7f426988c8f696c.png
其中ρ为无缺失值样本的比例。
缺失值处置惩罚
[*]起首分析缺失机制，选择符合的处置惩罚计谋
[*]对于重要特性，建议使用多重填充或构建更换模子
[*]在推测时，优先使用概率加权法处置惩罚缺失值，提高推测稳定性
6 主流决策树算法比力
6.1 核默算法对比
6.1.1 ID3 (Iterative Dichotomiser 3)
[*]特性选择
[*]使用信息增益作为分别准则：
Gain(D,A) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
[*]主要特点
[*]仅支持离散型特性
[*]没有剪枝计谋
[*]偏向取值较多的特性
[*]无法处置惩罚缺失值
[*]实用场景
[*]小规模数据集
[*]特性都是离散值
[*]对模子规模无严格要求
6.1.2 C4.5 (ID3的改进版本)
[*]改进特性
[*]引入增益率作为分别准则：
GainRatio(D,A) = \frac{Gain(D,A)}{SplitInfo(A)} 其中：
SplitInfo(A) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
[*]功能扩展
[*]支持一连特性处置惩罚
[*]实现了悲观剪枝
[*]能够处置惩罚缺失值
[*]支持属性权重
[*]优化计谋
[*]对一连属性采用二分法
[*]使用MDL(Minimum Description Length)原理
[*]实现了多重填充处置惩罚缺失值
6.1.3 CART (Classification And Regression Tree)
[*]技术特点
[*]使用基尼指数：
Gini(D) = 1 - \sum_{k=1}^{|y|}p_k^2
[*]焦点上风
[*]同时支持分类和回归
[*]生成二叉树结构
[*]实当代价复杂度剪枝
[*]处置惩罚异常值鲁棒性强
[*]特别功能
[*]支持样本权重
[*]可处置惩罚重复变量
[*]提供变量重要性评估
6.2 算法性能对比
6.2.1 特性对比矩阵
特性ID3C4.5CART一连值处置惩罚✗✓✓离散值处置惩罚✓✓✓缺失值处置惩罚✗✓✓剪枝计谋✗✓✓支持回归✗✗✓过拟合处置惩罚差良好良好异常值敏感度高中低 7 实际应用建议
7.1 场景选择指南
[*]选择ID3的情况
[*]数据集较小
[*]特性全为离散值
[*]对模子简单性要求高
[*]用于教学或演示
[*]选择C4.5的情况
[*]混合型特性数据
[*]存在缺失值
[*]必要可表明性强的模子
[*]计算资源充足
[*]选择CART的情况
[*]必要处置惩罚回归问题
[*]对推测精度要求高
[*]数据存在噪声和异常值
[*]必要稳定性好的模子
7.2 改进方向比力
[*]ID3的改进空间
[*]增加一连值处置惩罚能力
[*]添加剪枝机制
[*]优化特性选择准则
[*]C4.5的改进方向
[*]提高数值计算服从
[*]优化剪枝计谋
[*]增强对高维特性的处置惩罚能力
[*]CART的改进重点
[*]低落练习时间
[*]提高并行计算服从
[*]优化超参数选择
7.3 随机丛林优化
基于单棵决策树的局限性，随机丛林通过集成学习的方式提高模子性能：
[*]样本采样：使用bootstrap采样生成不同的练习集
[*]特性采样：在每个节点随机选择特性子集
[*]多树投票：综合多棵树的推测效果
代码详解：
def build_decision_tree(data, max_depth=None, min_samples_split=2):
"""
构建决策树的递归实现
"""
# 基础判断
if (max_depth is not None and max_depth <= 0) or \
len(data) < min_samples_split or \
len(np.unique(data['target'])) == 1:
return create_leaf(data)
# 特征选择
best_feature, best_threshold = find_best_split(data)
# 数据划分
left_data, right_data = split_data(data, best_feature, best_threshold)
# 递归构建子树
left_branch = build_decision_tree(
left_data,
max_depth-1 if max_depth is not None else None,
min_samples_split
)
right_branch = build_decision_tree(
right_data,
max_depth-1 if max_depth is not None else None,
min_samples_split
)
return {'feature': best_feature,
'threshold': best_threshold,
'left': left_branch,
'right': right_branch}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]