发布时间 : 星期五 文章完整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