1 决策树模型介绍

1.1 决策树模型概述

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
分类的时候，从根节点开始，当前节点设为根节点，当前节点必定是一种特征，根据实例的该特征的取值，向下移动，直到到达叶节点，将实例分到叶节点对应的类中。

1.2 决策树与if-then规则

可以将决策树看成一个if-then规则的集合：由决策树的根节点到叶节点的每一条路径构建一条规则；路径上的内部结点的特征对应着if条件，叶节点对应着then结论。决策树的每一条路径都具有一个重要的性质：互斥且完备。这就是说，任何一个实例都被且仅被一条路径或规则覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
举个例子：if(明天是晴天）then(我将出去玩)

1.3 决策树主要优点

1.分类速度快；
2.具有可读性；
3.学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新数据集，利用决策树模型进行分类。

1.4 主要步骤

1.特征选择问题
2.决策树的生成
3.决策树的剪枝

2 特征选择

2.1 特征选择问题

特征选择在于选取对训练集具有分类能力的特征。如果利用一个特征进行分类的结果与随即分类的结果没有很大差别，则称这个特征没有分类能力。通常特征选则的准则是信息增益或信息增益比。
特征选择是决定用哪个特征来划分特征空间。

2.1.1 举个例子

下表（表5.1）是由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征（属性），具体信息如表所示：
通过上表所给的训练数据构建一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请是，根据申请人的特征利用决策树决定是否批准贷款申请。
在说明这个例子之前，必须先了解几个定义。

2.2 重要定义

2.2.1 熵

由熵的定义可知，熵只依赖与X的分布，而与X的取值无关，所以也可以将X的熵记作H（p）,即

2.2.2 条件熵

2.2.3 信息增益

一般地，熵H(Y)与条件熵H(Y|X)之差成为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

2.3 信息增益的算法

2.3.1 算法过程

2.3.2 举个例子

3 决策树的生成

3.1 介绍

根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止，决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高，不确定性更小的子集的过程。对于当前数据集的每一次划分，都希望根据某个特征划分之后的各个子集的纯度更高，不确定性更小。
决策树生成算法不唯一，这里仅介绍两种算法——ID3算法和C4.5算法。

3.2 ID3算法

3.2.1 ID3算法核心

核心：是在决策树各个节点上应用信息增益准则选择特征递归地构建决策树。

3.2.2 算法过程

算法的过程为：
　　　1）初始化信息增益的阈值ϵ
　　　2）判断样本是否为同一类Di ，如果是则返回单节点树T。标记类别为Di。
　　　3）判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
　　　4）计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征Ag。
　　　5）如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
　　　6）否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
　　　7）对于所有的子节点，令D=Di,A=A−{Ag} ，递归调用2-6步，得到子树Ti并返回。

3.2.3 举个例子

用ID3算法构建表5.1的决策树过程如下：
构建决策树结果：

3.2.4 ID3算法的不足

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

1. ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2. ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
3. ID3算法对于缺失值的情况没有做考虑。
4. 没有考虑过拟合的问题。

3.3 C4.5算法

C4.5算法与ID3算法很相似，C4.5算法仅仅是对ID3算法做了改进，在生成决策树过程中采用信息增益比来选择特征算法过程没有变化，这里不再赘述。

3.3.1 C4.5算法的不足

C4.5虽然改进了ID3算法的几个主要的问题，仍然有优化的空间。

1. 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
2. C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3. C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4. C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
   　 这4个问题在CART树里面部分加以了改进。所以目前如果不考虑集成学习话，在普通的决策树算法里，CART算法算是比较优的算法了。

4 总结

这篇文章仅简单介绍了决策树的基本内容，主要是决策树的特征选择和生成两部分，后续会继续介绍决策树的剪枝和CART这个比较方便的算法。