决策树

笔记参考呆呆的猫机器学习实战（三）——决策树

1.决策树

??决策树（decision tree）：是一种基本的分类与回归方法，此处主要讨论分类的决策树。
??在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

??决策树通常有三个步骤：特征选择、决策树的生成和决策树的修剪。
??用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。在损失函数的意义下，选择最优决策树的问题。
决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数：正则化的极大似然函数
决策树学习的测试：最小化损失函数
??决策树原理和问答猜测结果游戏相似，根据一系列数据，然后给出游戏的答案。
??下图为决策树示意图，原点为内部节点，方框为叶节点；

??决策树实例，或者说决策树流程图，正方形方框表示判断，椭圆表示分类结果，可以终止运行，左右箭头叫做分支。

2.决策树的构造

??决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
??构建过程分为四步：
?1）开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
?2）如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。

?3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。

?4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

??决策树的特点：

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配的问题
适用数据类型：数值型和标称型

使用决策树做预测需要以下过程：

收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。
准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。
分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。
训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。
测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。
使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

2.1 信息增益

2.1.1 熵和经验熵

??划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

??举个例子，通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。

??特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。
在这里插入图片描述
??图(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

??在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
??熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号 $x_i$ 的信息定义为：
$l(x_i)=-log_2p(x_i)$ ??其中， $p(x_i)$ 是选择该分类的概率。而计算的所有类别的信息期望值得到熵：
$H=-\sum_{i=1}^{n}p(x_i)log_2p(x_i)$ ??其中，n为分类数目，熵越大，随机变量的不确定性越大。而当熵中的概率由数据估计（特别是最大似然估计）得到时，所对应的熵成为经验熵（empirical entropy）。数据估计浅显来说就是根据已有数据得到的概率而来。经验熵的公式可以写为下面的公式：
在这里插入图片描述

2.1.2 条件熵和信息增益

??信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。
??条件熵H ( Y ∣ X ) 表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：
在这里插入图片描述
??当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令 $0 l o g 0 = 0$

??信息增益：信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：在这里插入图片描述
??一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。