完整word版,决策树算法总结,推荐文档 下载本文

决策树

于是有了CART算法

CART算法:也是基于ID3算法优化而来,支持分类和回归,使用基尼系数(分类树)或者均方差(回归树)替代熵的作用,减少运算难度。使用二叉树代替多叉树建模,降低复杂度。

基尼系数的计算:

均方差的计算:

计算举例,假设有如下数据源

看电视时间 婚姻情况 职业 年龄 3 未婚 学生 12 4 未婚 学生 18 2 已婚 老师 26 5 已婚 上班族 47 2.5 已婚 上班族 36 3.5 未婚 老师 29 武汉中原电子信息有限公司

6

决策树

4 已婚 学生 21

如果将婚否作为标签,该问题是一个分类问题,所以使用基尼系数

假设使用职业作为特征分支,对于看电视和年龄,都是连续数据,需要按照C4.5的算法排序后处理,这里先分析简单的按照职业开始划分。

又因为,CART算法的建模是二叉树,所以,针对职业来说,有以下组合,学生|非学生,老师|非老师,上班族|非上班族,到底怎么划分,就要通过基尼系数来判断了。

gini = 3 / 7 * (1 – 2 / 3 * 2 /3 – 1 / 3 * 1 / 3) + 4 / 7 * (1 – 3 / 4 * 3 / 4 – 1 / 4 * 1 / 4) = 0.4

gini = 2 / 7 * (1 – 1 / 2 * 1 / 2 – 1 / 2 * 1 / 2) + 5 / 7 * (1 – 2 / 5 * 2 / 5 – 3 / 5 * 3 / 5) = 0.49

武汉中原电子信息有限公司

7

决策树

gini = 2 / 7 * (1 – 1 * 1) + 5 / 7 * (1 – 3 / 5 * 3 / 5 – 2 / 5 * 2 / 5) = 0.34

所以,如果选择职业来划分,那么首先应该按照上班族|非上班族划分

如果将年龄作为标签,该问题是一个回归问题,所以使用均方差 同样,先考虑使用职业来划分

mean = 开方(12 * 12 + 18 * 18 + 21 * 21 – 3 * 17 * 17) + 开方(26 * 26 + 47 * 47 + 36 * 36 + 29 * 29 – 5 * 32.5 * 32.5) = 34.71 其他情况略。

武汉中原电子信息有限公司

8

决策树

可以看到选择分裂属性这一步骤会比较麻烦,首先要遍历所有特征,找到每一个特征的最优分裂方法,然后在选择最优的分裂特征。

功能

树结构

特征选取

连续值处缺失值处剪枝 理

ID3 C4.5 CART 分类 分类 分类/回归 多叉 多叉 二叉 信息增益 信息增益率

不支持 支持

理 不支持 支持 支持 不支持 支持 支持 基尼系数(分支持 类) ,均方差(回归)

武汉中原电子信息有限公司

9