决策树

于是有了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