决策树

决策树模型与学习

1. 决策树模型

决策树定义：分类决策树是一种描述对实例进行分类的树型结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶子结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其他子结点；这时，每一个子结点对应着该特征的一个取值，如此递归地对实例进行分配，直至达到叶结点。最后将实例分到叶结点的类中。

如图所示，是一个决策树的示意图：

1.2决策树与if-then规则

可以将决策树看成是if-then规则的集合.将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或者其对应的if-then规则集合具有一个重要的性质：互斥并且完备，即每个实例都被一条路径或者一条规则所覆盖，而且只被一条路径或者一条规则所覆盖，这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或者区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为。X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率比较大的那一类去。

1.3决策树学习

假设给定数据训练数据集

其中，为输入实例（特征向量），n为特征个数，为类标记，，N为样本容量。学习的目标是根据给定的训练数据集建一个决策树模型，使其能够对实例进行正确分类。

决策树本质上是从训练数据集中归纳出分类规则，能对训练数据进行正确分类的决策树，它们可能有多个，可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一角度来看，决策树学习是由训练数据集估计条件概率模型。我们选择的条件概率模型应该不仅对训练数据有很好的拟合效果，而且对未知数据有很好的预测能力。

决策树学习用损失函数表示目标，决策树的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定后，学习问题就变为了损失函数的条件下选择最优决策树的问题。在所有可能的决策树中选取最优决策树是NP完全问题（NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题），所以现实中决策树学习算法通常采用启发式算法，近似求解这一最优化问题，这样获得的决策树是次最优的。

决策树学习的算法通常的是一种递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类过程。这一过程对应着特征空间的划分，也就是决策树的构建。如图所示：

1.4 决策树特点介绍

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以理解不相关特征数据。

缺点：可能会产生过度匹配问题

适用范围：数值型和标称型

问题1：评估每个特征，将原始数据集划分为几个数据子集。

创建分支的伪代码函数createBranch()如下所示：

检测数据集中的每个子项是否属于同一分类：

       if so return  类标签

       else

             寻找划分数据集的最好特征

             划分数据集

             创建分支节点

                    for 每个划分的子集

                          调用函数createBranch并增加返回结果到分支节点中

             return 分支节点

决策树学习算法包含特征选择，决策树的生成和决策树的剪枝过程。由于决策树表示为一个条件概率分布，所以深浅不同的决策树对应着不同复杂程度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成考虑局部最优；相对地，决策树的剪枝则考虑全局最优。

2. 特征选择

特征选择在于选取那些对训练数据具有分类能力的特征，这样可以提高决策树的学习的效率。如果利用一个特征的进行分类的结果与随机分类的结果没有很大差别，则这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度的影响不大。通常特征选择的准则是信息增益或者信息增益比。

例1.表1是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征(属性)：第一个特征年龄，有三个可能值：青年、中年、老年；第二个特征是有工作，有2个可能值：是、否；第三个特征是有自己的房子，有2个可能值：是、否；第四个特征是信贷情况，有3个可能值：非常好、好，一般。表的最后一列是类别，是否同意贷款，取2个值：是，否。

                                                                            表1 贷款申请样本数据表

图(a)和图(b)表示从数据学习到的两个可能的决策树，图(a)表示年龄特征，有三个子结点，图(b)表示有工作的特征，有2个子结点。问题是：我们选择哪个特征更加好些。也就是说我们按照什么样的准则来分割子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就是一个非常好的准则。

2.1 信息增益

在信息论与概率统计中，熵是表示随机变量不确定性的度量。设是一个取有限个值的离散随机变量，其概率分布为

则随机变量的熵的定义为

在式(2.1)中，若，则定义，通常，式(2.1)中的对数以2为底或以e为底（自然对数），这时熵的单位分别称作比特（bit）或者纳特（nat）。有定义可知，熵只依赖于