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数据挖掘方法及应用