目录
1、大纲
2、知识点
2.1、ID3
2.1.1、计算公式
2.1.2、缺点
2.2、C4.5/C5.0
2.2.1、计算公式
2.2.2、处理数值型数据
2.3、剪枝
2.3.1、修剪法
2.4、CART分类回归树
2.5、CHAID
2.5.1、核心思想
2.5.2、流程
2.6、CART回归树
1、大纲
ID3
决策树算法（
ID3
的字段选择方式、如何使用决策树来进行分类预测、决策树与决策规则间的关系、ID3
算法的弊端）
C4.5
决策树算法，包括
C4.5
的字段选择方式、
C4.5
的数值型字段处理方式、
C4.5
的空值处理方式、C4.5
的剪枝方法（预剪枝法、悲观剪枝法）
CART
决策树算法（分类树与回归树、
CART
分类树的字段选择方式、
CART
分类树的剪枝方法）
CART
回归树算法（
CART
回归树的字段选择方式、如何利用模型树来提升
CART
回归树的效能）
2、知识点
2.1、ID3
2.1.1、计算公式
在没有通过决策树模型进行分类的时候，我们可以先计算一下这
14
笔数据的总熵值
entropy = -9/14*LOG(9/14,2)-5/14*LOG(5/14,2)=0.94
接下来，我们需要计算每一个属性的熵值。我们可以先从年龄入手：
age
＜
=30
的人中，买电脑（
yes
）有
2
人，没有买电脑（
no
）的有
3 人，即 entropy（age<=30）= -3/5*LOG(3/5,2)-2/5*LOG(2/5,2)=0.97
30
＜
age
＜
41
的人中，买电脑的有
4
人，没买电脑的有
0
人，即 entropy（30<age<40）=0
age
＞
40
的人中，买电脑的有
3
人，没买电脑的有
2 人，即 entropy（40<age）=0.97
所以用属性
age
划分数据得到的熵值为：
entropy（age）=5/14*entropy（age<=30）+4/14*entropy（30<age<40）+5/14*entropy（40<age）=0.69
信息增益ig（age）=entropy-entropy（age）=
0.94-0.69=0.25
信息增益是用来衡量由于划分所造成的
Entropy
减小的程度，ig越大，根据该属性产生的划分越纯，因此，选择信息增益最大的属性作为最佳划分属性。
2.1.2、缺点
（1）信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
（2）不能handle数值型，只处理类别型
（3）
不能处理具有缺失数据的属性
（4）
没有对决策树进行修剪的过程，噪声比较大。
2.2、C4.5/C5.0
C4.5
算法是
ID3
算法的修订版，采用信息增益率（Gain Ratio
）来加以改进，避免
ID3
算法过度配适的问题。
C5.0
算法则又是
C4.5 算法的修订版，适用于处理大数据集。
2.2.1、计算公式
接上案例age的分支度计算，age分三枝，数量分别为4、5、4：
iv（age）= -5/14*LOG(5/14,2)-4/14*LOG(4/14,2)-5/14*LOG(5/14,2)=1.577
igr（age）=ig（age）/iv（age）=0.25/1.577
2.2.2、处理数值型数据
具体的操作方法为：
先将数值型数据从小到大排序，如 v1
，
v
2
，
…v
n
，选取每相邻两点的中间点，如（
v
i
+v
i+1
）/2 点，将数据自动离散化为两群，分别计算每一次分割所得的信息增益率（
Gain Ratio
）， 选取信息增益率（Gain Ratio
）最大的点作为切割点
增加age字段，
第一切：（age=28.5左右为切割点）
计算entropy =
=-4/10*LOG(4/10,2)-6/10*LOG(6/10,2)=0.97
entropy（age<28.5）= 0
entropy（age>28.5）=1
entropy（age）=1/10*entropy（age<28.5）+9/10*entropy（age>28.5）=0.9
ig = entropy - entropy（age） = 0.07
iv = -1/10*LOG(1/10,2)-9/10*LOG(9/10,2) = 0.469
igr = ig/iv = 0.07/0.469 = 0.15
第二切：（age=32.5左右为切割点）
....
寻找max（igr）的切割点
2.3、剪枝
由于训练数据中存在噪音或者训练数据太少，就会出现过度拟合（
Overfitting
）现象
两种方法：（1）修剪法：自下而上，如C4.5/CART。（2）盆栽法：自上而下，如CHAID
2.3.1、修剪法
假定confidence level（CF）=25%。CF越小的值导致更多的修剪
U
25%
（
0,1
）
=0.750
U
25%
（
0,6
）
=0.206
U
25%
（
0,9
）
=0.143
随着笔数越多，预测错误率降低。
节点错误率e估算公式：
N：总笔数
E：错误的笔数
F：错误率，E/N
z：25%置信区间下，固定为0.69
2.4、CART分类回归树
该算法与
ID3
、
C5.0
的不同之处在于：
1.
该算法是一种建构二元（Binary
）分类回归树的算法，也即，决策树在每次分叉的时候，只能分出两支数值；
2.
该算法在字段选择时，使用
Gini Index
作为评估指标；
3.C5.0
是通过计算预测错误率来剪枝，
CART
通过训练数据产生决
策树，再用验证数据集判断剪枝。
初始gini index = 1-（9/14）^2-（5/14）^2=0.459。
Gini Index
为
0
，则纯度最高；
Gini Index
的值越大，0.5，则纯度越低。
gini gain= 初始gini index-gini index（道路距离）
2.5、CHAID
2.5.1、核心思想
根据给定的目标变量和经过筛选的特征指标（即预测变量）对样本进行最优分割，按照卡方检验的显著性进行多元列联表的自动判断分组。
2.5.2、流程
首先选定分类的目标变量，然后用分类指标与目标变量进行交叉分类，产生一系列二维分类表【数值型自动分箱】。
分别计算二维分类表的卡方 X
2
值，比较
P
值的大小，以
P
值最小的二维表作为最佳初始分类表， 在最佳二维分类的基础上继续使用分类指标对目标变量进行分类
重复上述过程直到 P
大于设定的有统计意义的α值时则分类停止。
卡方越大，代表字段与目标字段关系越密切，越是重要的条件字段。p-value是 决定数是否继续往下长
2.6、CART回归树
1、使用平均数
2、model tree使用多元线性回归，最差情况下=线性回归