数据挖掘-04

目录

决策树

组成

画法

剪枝

优点

缺点

构建

---

决策树

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法。它是一种监督学习，所谓监督学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

通常使用的分类回归树（class and regress tree）是一个二叉树。它的形式一般为：

每个方框代表一个节点. 每个非叶子节点有2个分支, 一个是判定True, 一个判定False. 分别走两个不同的分支. 叶子节点具有决策权. 任何一个输入从root出发, 总是会达到且唯一到达一个叶子节点. 这就是决策树的工作原理.

决策树有两种节点： 中间节点和叶子节点。 1. 每个中间节点有4个参数：
a) 判定函数。 是一个特征的取值。 当特征小于等于这个值得时候决策路径走左边， 当特征大于这个值得时候决策树走右边。
b) 不纯度值(impurity value). 是当前节点的不纯度值. 关于不纯度值得意义后面会讲到. 他反应了当前节点的预测能力.
c) 覆盖样本个数(n_samples). 是指参与此节点决策的样本个数. 父亲节点§和两个孩子节点(l,r)的样本个数的关系为: n_samples§ = n_samples(l) + n_samples 覆盖样本个数越多, 说明判定函数越稳定. 实际上很容易看出来, 所有的叶子节点所对应的样本是总样本的一个划分.
d) 节点取值(node value). 节点取值是一个数组. 数组的长度为类目个数. value = [997, 1154] 表示在2151个样本数中, 有997个属于class1, 1154属于class2. (这是分类树的意义, 会归数的取值规则后面会讲.)
2. 每个叶子节点有3个参数. 除了没有决策函数之外, 其他参数意义一样. 

组成

①决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

②状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

③结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

画法

机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

一个决策树包含三种类型的节点：

1. 决策节点：通常用矩形框来表示

2. 机会节点：通常用圆圈来表示

3. 终结点：通常用三角形来表示

决策树学习也是资料探勘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。

决策树如果依靠数学的计算方法可以取得更加理想的效果。 数据库已如下所示：

(x, y) = (x1, x2, x3…, xk, y)

相关的变量 Y 表示我们尝试去理解，分类或者更一般化的结果。 其他的变量x1, x2, x3 等则是帮助我们达到目的的变量。

剪枝

剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。

优点

决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。 [3] 

对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 [4] 

易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。

缺点

1)对连续性的字段比较难预测。

2)对有时间顺序的数据，需要很多预处理的工作。

3)当类别太多时，错误可能就会增加的比较快。

4)一般的算法分类的时候，只是根据一个字段来分类。

构建

 广度优先

名称	图像	说明
广度优先		广度优先按照层次来构建树的. 首先根据合适的不纯度函数来分裂root成2个节点; 然后依次分裂第二层的2个节点; 依次递推.
深度优先		深度优先采用递归的思想, 在每个节点都是优先有左边的子树建好, 再建右边子树

不管是深度优先还是广度优先, 决策树算法都需要知道什么时候一个节点应该作为叶子节点. 如果没有约束决策树会一直建设下去知道节点只有一个类目(或者只有一个取值)才停止. 这样会导致决策树变得非常庞大, 引发过拟合问题.

一般来说, 当如下条件其中之一满足的时候, 当前节点停止构建, 作为决策树的叶子节点.

参数	意义	终止条件
min_samples_split	当前节点允许分裂的最小样本数	当前节点样本数小于这个值时候
min_samples_leaf	叶子节点最少样本数	任何分裂不能导致子节点的样本数小于此值, 否则禁止分裂
min_impurity_split	分裂的不纯度阈值	当前节点不纯度小于此值时不分裂
max_path	数的最大深度	当前节点的深度大于等于此值是不分裂

这些控制条件可以控制数的规模, 因为根据不纯度变化的定义, 将所有的节点都放在唯一的叶子节点(这样每个叶子节点不纯度都是0)中不纯度变化最大. 这显然不是我们想要的.