lecture 9：决策树Decision Tree

目录

1决策树基础

决策树（decision tree）是一种基本的分类与回归方法，主要用于分类。可以看做是if-then规则的集合。

优点：分类速度快，模型具有可读性

• 决策树学习的3个步骤：特征选择、决策树生成、决策树修剪
• 决策树算法：ID3、C4.5、CART

2特征选择

2.1信息熵

特征选择：在于选取对训练数据具有分类能力的特征，可以提高决策树的学习效率。

特征选择的准则是信息增益或信息增益比。

奥姆剃须刀原理：be simple，切勿浪费较多东西，去做“用较少的东西就能做好的事情”

• 熵：描述事物无序性的参数， 熵越大则无序性越强,在信息领域定义为“熵越大， 不确定性越大” （香浓， 1948年）
• 信息熵：衡量信息不确定性的量化指标

不确定性的变化跟什么有关？

• 跟事情的可能结果的数量有关
• 跟概率有关

一个事件的信息量就是这个事件发生的概率的负对数。−log(p(x))$-log(p(x))$
信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是信息量的期望。

我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的纯度越来越高。

2.2信息增益

ID3算法利用信息增益为准则，来选择划分属性

2.3根据信息增益选择属性的例子

2.4增益率

3决策树生成算法

ID3、C4.5、CART

• ID3算法利用信息增益为准则，来选择划分属性，对取值数目较多的属性有所偏好（如西瓜编号属性），容易过拟合，不具有泛化能力，对新样本的预测能力差
• C4.5算法利用信息增益率选择属性，但并不是直接选择信息增益率最大的候选划分属性，而是使用启发式，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
• CART使用“基尼系数”来选择划分属性，从数据集随机抽取两个样本，类别标记不一致的概率，Gini(D)越小，数据集的纯度越高

4剪枝处理

• 剪枝是防止过拟合的主要手段
• 有预剪枝、后剪枝