决策树算法简单总结

·来自&＃xff1a;https://mp.weixin.qq.com/s/tevVm0jlS6vZ3LCnczWD0w

前言

李航老师《统计学习方法》详细的描述了决策树的生成和剪枝。根据书的内容&＃xff0c;做总结如下。

目录

1. 决策树不确定性的度量方法
2. 决策树的特征筛选准则
3. 决策函数的损失函数评估
4. 决策树最优模型的构建步骤
5. 决策树的优缺点分析

a. 决策树不确定性的度量方法

1. 不确定性理解

下图为事件A是否发生的概率分布&＃xff0c;事件发生记为1&＃xff0c;讨论事件A的不确定性。

&＃xff08;1&＃xff09;一种极端情况&＃xff0c;若p&＃61;1或p&＃61;0&＃xff0c;表示为事件A必定发生或事件A不可能发生。

&＃xff08;2&＃xff09;若p>1/2&＃xff0c;即事件A发生的概率大于事件A不发生的概率&＃xff0c;我们倾向于预测事件A是发生的&＃xff1b;若 p<1/2&＃xff0c;即事件A不发生的概率小于事件A发生的概率&＃xff0c;我们倾向于预测事件A是不发生的&＃xff1b;若 p&＃61;1/2&＃xff0c;即事件A发生的概率等于事件A不发生的概率&＃xff0c;我们无法作出预测。

2. 决策树不确定性的度量方法

这里用熵和基尼指数去衡量数据集的不确定性&＃xff0c;假设数据集包含K类&＃xff0c;每个类的大小和比例分别为Di和pi&＃xff0c;i &＃61; 1&＃xff0c;2&＃xff0c;...&＃xff0c;k。

&＃xff08;1&＃xff09;熵的不确定性度量方法

信息论和概率统计中&＃xff0c;熵是表示随机变量不确定性的度量&＃xff0c;令熵为H(p)&＃xff0c;则&＃xff1a;

熵越大&＃xff0c;数据集的不确定性就越大。

&＃xff08;2&＃xff09;基尼指数的不确定度量方法

数据集的基尼指数定义为&＃xff1a;

基尼指数越大&＃xff0c;数据集不确定性越大。

b. 决策树特征筛选准则

假设数据集A共有K个特征&＃xff0c;记为xi&＃xff0c;i &＃61; 1,2,...,K。数据集A的不确定性越大&＃xff0c;则数据集A包含的信息越多。假设数据集A的信息为H(A)&＃xff0c;经过特征xi筛选后的信息为H(A|xi)&＃xff0c;定义信息增益g(A, xi)为两者的差值&＃xff0c;即&＃xff1a;

g(A, xi) &＃61; H(A) - H(A|xi)

选择使数据集A信息增益最大的特征作为决策树当前节点&＃xff0c;数学表示为&＃xff1a;

x &＃61; max( g(A,xi) ) &＃61; max( H(A) - H(A|xi) )

C. 决策树的损失函数评估

令决策树的叶节点数为T&＃xff0c;损失函数为&＃xff1a;

其中C(T)为决策树的训练误差&＃xff0c;决策树模型用不确定性表示&＃xff0c;不确定性越大&＃xff0c;则训练误差亦越大。T表示决策树的复杂度惩罚&＃xff0c;α参数权衡训练数据的训练误差与模型复杂度的关系&＃xff0c;意义相当于正则化参数。

考虑极端情况&＃xff1a;当α趋于0的时候&＃xff0c;最优决策树模型的训练误差接近 0&＃xff0c;模型处于过拟合&＃xff1b;当α趋于无穷大的时候&＃xff0c;最优决策树模型是由根节点组成的单节点树。

d. 决策树最优模型的构建步骤

将数据集A通过一定的比例划分为训练集和测试集。

决策树的损失函数&＃xff1a;

决策树最优模型的构建步骤包括训练阶段和测试阶段&＃xff1a;

训练阶段&＃xff1a;

&＃xff08;1&＃xff09;最小化决策树的不确定性值得到的生成模型&＃xff0c;即决策树生成&＃xff1b;

&＃xff08;2&＃xff09;通过决策树剪枝&＃xff0c;得到不同的正则化参数α下的最优决策树模型&＃xff0c;即决策树剪枝。

 下面重点讨论训练阶段的决策树生成步骤和决策树剪枝步骤。

决策树生成步骤&＃xff1a;

&＃xff08;1&＃xff09; 根据决策树的特征筛选准则&＃xff0c;选择数据集信息增益最大的特征&＃xff1b;

&＃xff08;2&＃xff09; 重复第一个步骤&＃xff0c;直到所有叶节点的不确定性为0 。

决策树剪枝步骤&＃xff1a;

&＃xff08;1&＃xff09;将正则化参数α从小到大分成不同的区间

e. 决策树优缺点

优点&＃xff1a;模型很强的解释性

缺点&＃xff1a;容易过拟合。即训练误差很小&＃xff0c;测试误差很大。为避免过拟合&＃xff0c;使用时结合集成算法。如&＃xff1a;bagging算法、boosting算法。