3.1　构建决策树的准备工作

在介绍决策树的构造前，先来了解决策树的适应数据类型及其优缺点。

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

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

适用数据类型：数值型和标称型。

使用决策树做预测的每一个步骤都很重要。数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树；数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树。从算法方面看，决策树的构建是核心内容。

决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和修剪。

3.1.1　特征选择

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的标准是信息增益（information gain）或信息增益比。为了简单起见，本节使用信息增益作为选择特征的标准。什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表，见表3-1。

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

特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根节点构成。

图3-2（a）所示根节点的特征是年龄，有3个取值，对应于不同的取值有不同的子节点。图3-2（b）所示根节点的特征是工作，有2个取值，对应于不同的取值有不同的子节点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上讲，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益能够很好地表示这一直观的准则。

什么是信息增益呢？在划分数据集之前、之后信息发生的变化称为信息增益，知道如何计算信息增益，就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

1．香农熵

在可以评测哪种数据划分方式是最好的之前，必须学习如何计算信息增益。集合信息的度量方式称为香农熵或简称熵（entropy），这个名字来源于信息论之父克劳德·香农。

熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。如果待分类的事务可能划分在多个分类之中，则符号的信息定义为

式中，为选择该分类的概率。通过上式，可以得到所有类别的信息。为了计算熵，需要计算所有类别所有可能值包含的信息期望值（数学期望），通过下面的公式可得到：

式中，为分类的数目。熵越大，随机变量的不确定性就越大。

当熵中的概率由数据估计（特别是最大似然估计）得到时，所对应的熵称为经验熵（empirical entropy）。什么叫由数据估计？比如，有10个数据，包括两种类别，即类和类。其中有7个数据属于类，则该类的概率为7/10。其中有3个数据属于类，则该类的概率为3/10。浅显的解释就是，此概率是我们根据数据数出来的。定义贷款申请样本数据表中的数据为训练数据集，则的经验熵为，表示其样本容量及样本个数。设有个类，，为属于类的样本个数，则经验熵公式可以写为

根据此公式计算经验熵，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷，所以数据集的经验熵为

经过计算可知，数据集的经验熵的值为0.971。

2．编写代码计算经验熵

在编写代码前，先对数据集进行属性标注。

● 年龄：0代表青年；1代表中年；2代表老年。

● 有工作：0代表否；1代表是。

● 有自己的房子：0代表否；1代表是。

● 信贷情况：0代表一般；1代表好；2代表非常好。

● 类别（是否给贷款）：no代表否；yes代表是。

确定这些之后，就可以创建数据集，并计算经验熵了。代码编写如下：

运行程序，输出如下：

3．信息增益

在前面已经说过，选择特征需要看信息增益。也就是说，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们应该选择对最终分类结果影响最大的那个特征作为分类特征。

在讲解信息增益定义之前，我们还需要明确一个概念，即条件熵。

条件熵表示在已知随机变量的条件下随机变量的不确定性，定义给定条件下的条件概率分布的熵对的数学期望：

其中

同理，当条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的条件熵称为经验条件熵。

明确了条件熵和经验条件熵的概念。接下来说说信息增益。前面也提到了，信息增益是相对于特征而言的，所以，特征对训练数据集的信息增益定义为集合的经验熵与特征给定条件下的经验条件熵之差，即

一般地，熵与条件熵之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

设特征有个不同的取值，根据特征的取值将划分为个子集，即，为的样本个数。记子集中属于的样本集合为，即，为的样本个数。于是经验条件熵的公式为

下面以贷款申请样本数据表为例进行说明。看一下年龄一列的数据，也就是特征，一共有3个类别，分别是青年、中年和老年。我们只看年龄是青年的数据，年龄是青年的数据有5个，所以年龄是青年的数据在训练数据集出现的概率是5/15，也就是1/3。同理，年龄是中年和老年的数据在训练数据集出现的概率也是1/3。现在我们只看青年数据最终得到贷款的概率为2/5，因为在5个数据中，只有两个数据显示拿到了最终贷款，同理，中年和老年数据最终得到贷款的概率分别为3/5和4/5，所以计算年龄的信息增益的过程如下：

同理，计算其余特征的信息增益、和，分别为

最后，比较特征的信息增益，由于特征（有自己的房子）的信息增益值最大，所以选择为最优特征。

4．编写代码计算信息增益

我们已经学会了通过公式计算信息增益，接下来编写代码，计算信息增益，选择最优特征。

splitDataSet函数是用来选择各个特征子集的，如选择年龄（第0个特征）的青年（用0代表），我们可以调用splitDataSet（dataSet，0，0），返回的子集就是年龄为青年的5个数据集。chooseBestFeatureToSplit是选择最优特征的函数。

运行程序，输出如下：

对比自己的计算结果，发现结果完全正确！最优特征的索引值为2，也就是特征（有自己的房子）。

3.1.2　决策树的生成和修剪

我们已经学习了从数据集构造决策树算法所需要的子功能模块，包括经验熵的计算和最优特征的选择，其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个节点。在这个节点上，我们可以再次划分数据集。因此，我们可以采用递归的原则处理数据集。

构建决策树的算法很多，如C4.5、ID3和CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。由于特征数目并不是每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定问题。目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的决策树往往对训练数据的分类很准确，但对未知的测试数据的分类没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。