决策树，决策树算法
决策树，决策树算法
1. 什么是决策树（Decision Tree）
- 决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别。
- 决策树是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知数据进行分类。
2. 例子
|
ID |
拥有房产 |
婚姻情况 |
年收入 |
无法偿还债务 |
|
1 |
是 |
单身 |
125 |
否 |
|
2 |
否 |
已婚 |
100 |
否 |
|
3 |
否 |
单身 |
70 |
是 |
|
4 |
是 |
已婚 |
120 |
否 |
|
5 |
否 |
离婚 |
75 |
是 |
|
6 |
否 |
已婚 |
60 |
否 |
|
7 |
是 |
离婚 |
220 |
否 |
|
8 |
否 |
单身 |
85 |
否 |
|
9 |
否 |
已婚 |
75 |
否 |
|
10 |
否 |
单身 |
90 |
否 |
由上表的数据构造决策树如下：
新用户：无房产，单身，年收入55K，那么根据上面的决策树，可以预测他无法偿还债务。
3. 什么情况下适合使用决策树
1） 使用场景：预测
2） 决策树的变量
- 数字型(Numeric)
整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件
- 名称型(Nominal)
类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”。使用“=”来分割
4. 决策树的核心问题
l 决策树的生长
1）生长过程
决策树的生长过程本质是对训练样本的反复分组过程。当对某组数据继续分组不再有意义时，决策树对应的分枝便不再生长；当所有数据组的继续分组均不再有意义时，决策树的生长过程结束。
2） 决策树的分枝准则
- 如何从众多的输入变量中选择一个当前最佳的分组变量？
- 如何从分组变量的众多取值中找到一个最佳的分割点？
l 决策树的剪枝
1） 为什么要剪枝
完整的决策树对训练样本特征的描述“过于精确”，随着决策树生长和样本数量不断减少，所体现的数据特征越个性化，一般性就越差，因此完整的决策树并不是一棵分类预测新数据对象的最佳树。比如极端情况下可能产生这样的推理规则：“年收入大于50000元且年龄大于50岁且姓名是张三的人购买某种商品”。这条推理虽然精确但是失去了一般性，很可能因其失去一般代表性而无法用于对新数据的分类预测（过度拟合）。
2） 剪枝的方法
Ø 预修剪
- 事先指定决策树生长的最大深度
- 为防止某个树节点上的样本数过少，事先指定一个最小样本量
Ø 后修剪
边修剪边检验(使用检验样本)的过程。在剪枝过程中，它不断计算当前决策子树对输出变量的预测精度或误差。可以事先指定一个允许的最大错误率，当剪枝达到某个深度时，当前的错误率高于允许的最大值，则停止剪枝，否则继续剪枝。
| 决策树算法 | 适用范围 | 改进的方式 | 改进的效果 |
|---|---|---|---|
| ID3 | 离散型属性数据 | -- | -- |
| C4.5 | 离散型 连续型属性数据 |
对连续型属性的离散化 采用GainRatio作为分割变量准则 |
使其适用范围更广泛 避免ID3算法的过度拟合问题 |
| C5.0 | 处理大数据集 | 采用Boosting/BoostingTrees方式 | 提高模型准确率，计算速度比较快，占用内存资源较少 |
1） 如何从众多的输入变量中选择一个当前最佳的分组变量？
2） 如何从分组变量的众多取值中找到一个最佳的分割点？
试想：如何评估分割点的好坏
如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”。
扩展：
量化“纯度”
1）不纯度
- Gini不纯度：
- 熵(Entropy)：
- 错误率(Error)：
上面三种计算纯度的公式均为值越大，表示越“不纯”，越小表示越“纯”。实践证明三种公式的选择对最终分类准确率的影响并不大，一般使用熵公式。
例子：
以C5.0算法为例，使用信息增益率（GainRatio）为标准确定最佳分组变量和分割点。
在信息论中信息传递过程看作是一个由信源、信道和信宿组成的传递系统实现的，信源是信息的发送端，信宿是信息的接收端。在2中的例子，拥有房产（T1），婚姻情况（T2），年收入（T3）作为输入变量，无法偿还债务为输出变量。决策树将输出变量（无法偿还债务）看作信源发出的信息U，输入变量看作信宿接收到的一系列信息V。
(单身：4(3,1) 离婚：2(1,1) 已婚：4(4,0))
由上面的计算可知，T1的信息增益率（0.133）大于T2的信息增益率（0.130），因此应选择T1作为最佳分组变量。
在婚姻情况中有3个属性，分别为单身，离婚，已婚，如何选择分割点？
由上面的计算可知，已婚的信息增益率（1.444）大于单身的信息增益率（0.795）和离婚的信息增益率（1.127），因此应选择已婚作为最佳分组变量。
3） 如何剪枝
C5.0采用后修剪方法从叶节点向上逐层剪枝，其关键是错误率即误差的估计及剪枝标准的设置。
Ø 误差估计
利用统计学置信区间的估计方法，直接在训练样本集中估计误差。
Ø 剪枝标准
在得到误差估计后，采用“减少-误差”法判断是否剪枝。即先计算待剪子树中叶节点的加权误差，然后与父节点的误差进行比较，如果大于父节点的误差则剪掉。
5. 决策树的优点
l 决策树模型可读性好，具有描述性，有助于人工分析。
l 效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
l 可以很自然的嵌入专家的先验知识
参考资料
1. http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html
2. http://www.cnblogs.com/bourneli/archive/2012/11/17/2775405.html
3. http://blog.csdn.net/soso_blog/article/details/5755457
4. clementine数据挖掘方法及应用
版权声明：本文为博主原创文章，未经博主允许不得转载。
评论暂时关闭