李航 统计学习方法 第五章 决策树 课后 习题 答案

决策树是一种基本的分类和回归方法。决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。（ID3、C4.5、CART）

特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。

熵是表示随机变量不确定性的度量。 X 是一个取有限个值的离散随机变量，其概率分布为

设有随机变量 (X,Y) ，其联合概率分布为

信息增益：特征 A 对训练数据集 D 的信息增益 g(D,A) ，定义为集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件熵 H(D|A) 之差，即

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。（取值较多的特征，可以这样理解，这个特征取值特别多，每条实例一个值，如果选择这个特征，那么每个分支都只有一条实例，也就是每个分支都属于同一个类，这个分支的熵就是0，这个特征的条件熵也就是0。这对其他的特征是不公平的，所以将信息增益除于这个特征的熵）

信息增益比：特征 A 对训练数据集 D 的信息增益比 gR(D,A) 定义为其信息增益 g(D,A) 与训练数据集 D 关于特征 A 的值的熵 HA(D) 之比，即

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

C4.5用信息增益比来选择特征

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。设树 T 的叶节点个数为 |T| ， t 是树 T 的叶节点，该叶节点有 Nt 个样本点，其中 k 类的样本点有 Ntk 个， k=1,2,…,K ， Ht(T) 为叶节点 t 上的经验熵， α≥0 为参数，则决策树学习的损失函数可以定义为

c4.5和id3生成算法源码： https://github.com/zhouna/ml_python/tree/master/decisionTree

classification and regression tree, CART 分类与回归树，假设决策树是二叉树。 决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

5.1 根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。

输入： A1={ 1,2,3},A2={ 1,2},A3={ 1,2},A4={ 1,2,3} 输出： C={ 0,1}

其中 Ai,i=1,2,3,4 分别代表年龄，有工作，有自己的房子，信贷情况； C 代表类别。 A1 的取值 1,2,3 分别代表青年、中年和老年； A2，A3 的取值 1,2 分别代表是和否； A4 的取值 1,2,3 分别代表一般、好喝非常好； C 的取值 0,1 分别代表否和是。

首先在数据集 D 上计算各个特征的信息增益比，选取信息增益比最大的特征作为分支的依据。

首先计算数据集 D 的经验熵 H(D) ： H(D)=−615log