数据挖掘-决策树

数据挖掘论文——决策树
1. 什么是决策树
1. 决策树(Decision Tree）是在已知各种情况发生概率的基础上，通
过构成决策树来求取净现值的期望值大于等于零的概率，评价项目
风险，判断其可行性的决策分析方法，是直观运用概率分析的一种
图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策
树。
2. 决策树图示

1.
3. 实例描述
1. 女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
2. 这个女孩的决策过程就是典型的分类树决策。相当
于通过年龄、长相、收入和是否公务员对将男人分
为两个类别：见和不见。假设这个女孩对男人的要
求是：30岁以下、长相中等以上并且是高收入者或
中等以上收入的公务员，那么这个可以用下图表示
女孩的决策逻辑：
2.
4. 决策树的组成
1. □——决策点，是对几种可能方案的选择，即最后选择的最佳方案。
如果决策属于多级决策，则决策树的中间可以有多个决策点，以决
策树根部的决策点为最终决策方案。[1]
2. ○——状态节点，代表备选方案的经济效果（期望值），通过各状
态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方
案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出
现的自然状态数目每个分枝上要注明该状态出现的概率。[1]
1. ——结果节点，将每个方案在各种自然状态下取得的损益值
标注于结果节点的右端
5. 决策树的构建
1. 不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属
性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策
树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结
构。
2. 构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点
处按照某一特征属性的不同划分构造不同的分支，其目标是让各个
分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集
中待分类项属于同一类别。分裂属性分为三种不同的情况：
6. 属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一
个分支。
7. 属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行
测试，按照“属于此子集”和“不属于此子集”分成两个分支。
8. 属性是连续值。此时确定一个值作为分裂点split_point，按
照>split_point和<=split_point生成两个分支。
9. 量化纯度算法选择
1. 构造决策树的关键性内容是进行属性选择度量，属性选择度量是一
种选择分裂准则，是将给定的类标记的训练集合的数据划分D“最
好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点
split_point的选择。
2. 我们采用熵公式来进行纯度选择计算
10. 公式及算法描述
1. 熵（entropy）:刻画了任意样例集的纯度（purity）。
2. 熵确定了要编码集合S中任意成员（即以均匀的概率随机抽出
的一个成员）的分类所需要的最小二进制位数。
3. 如果目标属性具有c个不同的值，那么S相对c个状态（c-wise）
的分类的熵定义为：

4.
1. Pi是S中属于类别i的比例。

5. 信息增益（information gain）：一个属性的信息增益就是由于使
用这个属性分割样例而导致的期望熵降低。

6.
1. Values(A)是属性A所有可能值的集合，Sv 是S中属性A的
值为v的子集。
7. 例如，假定S包含14个样例-[9+,5-]。在这14个样例中，假定正
例中的6个和反例中的2个有Wind=Weak，其他的有Wind=Strong。
由于按照属性Wind分类14个样例得到的信息增益可以计算如下。
1. Values(Wind)=Weak,Strong
2. S=[9+,5-]
3. SWeak←[6+,2-]
4. Sstrong←[3+,3-]
5. =Entropy(S)-(8/14)Entropy(SWeak)-(6/14)Entropy(Sstrong)
6. =0.940-(8/14)0.811-(6/14)1.00
7. =0.048
11. 停止条件
1. 决策树的构建过程是一个递归的过程，所以需要确定停止条件，否
则过程将不会结束。一种最直观的方式是当每个子节点只有一种类
型的记录时停止，但是这样往往会使得树的节点过多，导致过拟合
问题（Overfitting）。另一种可行的方法是当前节点中的记录数低
于一个最小的阀值，那么就停止分割，将max(P(i))对应的分类作
为当前叶节点的分类。
12. 过渡拟合
1. 采用上面算法生成的决策树在事件中往往会导致过滤拟合。也就是
该决策树对训练数据可以得到很低的错误率，但是运用到测试数据
上却得到非常高的错误率。过渡拟合的原因有以下几点：
13. 噪音数据：训练数据中存在噪音数据，决策树的某些节点有噪音数据作为
分割标准，导致决策树无法代表真实数据。
14. 缺少代表性数据：训练数据没有包含所有具有代表性的数据，导致某一类
数据无法很好的匹配，这一点可以通过观察混淆矩阵（Confusion Matrix）
分析得出。
15. 多重比较（Mulitple Comparition）：举个列子，股票分析师预测股票涨
或跌。假设分析师都是靠随机猜测，也就是他们正确的概率是0.5。每一
个人预测10次，那么预测正确的次数在8次或8次以上的概率为

，只有5%左右，比较低。但是如果50
个分析师，每个人预测10次，选择至少一个人得到8次或以上的人作为

代表，那么概率为 ，概率十分大，随着分
析师人数的增加，概率无限接近1。但是，选出来的分析师其实是打酱油
的，他对未来的预测不能做任何保证。上面这个例子就是多重比较。这一
情况和决策树选取分割点类似，需要在每个变量的每一个值中选取一个作
为分割的代表，所以选出一个噪音分割标准的概率是很大的。
16. 优化方案
1. 以修剪枝叶为例：
2. 决策树过渡拟合往往是因为太过“茂盛”，也就是节点过多，
所以需要裁剪（Prune Tree）枝叶。裁剪枝叶的策略对决策
树正确率的影响很大。主要有两种裁剪策略。
3. 前置裁剪 在构建决策树的过程时，提前停止。那么，会将
切分节点的条件设置的很苛刻，导致决策树很短小。结果就
是决策树无法达到最优。实践证明这中策略无法得到较好的
结果。
4. 后置裁剪 决策树构建好后，然后才开始裁剪。采用两种方
法：1）用单一叶节点代替整个子树，叶节点的分类采用子
树中最主要的分类；2）将一个字数完全替代另外一颗子树。
后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪
了，导致有点浪费。
17. 准确值估计
1. 决策树T构建好后，需要估计预测准确率。直观说明，比如N条测
试数据，X预测正确的记录数，那么可以估计acc = X/N为T的准
确率。但是，这样不是很科学。因为我们是通过样本估计的准确率，
很有可能存在偏差。所以，比较科学的方法是估计一个准确率的区
间，这里就要用到统计学中的置信区间（Confidence Interval）。
2. 设T的准确率p是一个客观存在的值，X的概率分布为X ~ B(N,p)，
即X遵循概率为p，次数为N的二项分布（Binomial Distribution），
期望E(X) = N*p，方差Var(X) = N*p*(1-p)。由于当N很大时，
二项分布可以近似有正太分布（Normal Distribution）计算，一
般N会很大，所以X ~ N(np,n*p*(1-p))。可以算出，acc = X/N
的期望E(acc) = E(X/N) = E(X)/N = p，方差Var(acc) = Var(X/N)
= Var(X) / N2 = p*(1-p) / N，所以acc ~ N(p,p*(1-p)/N)。这
样，就可以通过正太分布的置信区间的计算方式计算执行区间了。

1. 正太分布的置信区间求解如下：

18. 将acc标准化，即
19. 选择置信水平α= 95%，或其他值，这取决于你需要对这个区间有多自信。
一般来说，α越大，区间越大。

20. 求出 α/2和1-α/2对应的标准正太分布的统计量 和
（均为常量）。然后解下面关于p的不等式。acc可以有样本估计得出。
即可以得到关于p的执行区间

1.
2. 参考文献： 百度百科
知乎