决策树模型概述

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树)。
其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。
使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树可以表示如下
当我们构建好一个决策树后，我们就可以根据特征的取值来判断一个待分类项的类别

举个例子 现在有一个西瓜 它的纹理很清晰，根蒂稍蜷，色泽乌黑，触感硬滑 判断它是一个好瓜还是坏瓜？

根据之前建立的决策树 我们可以找到这样一条路径 说明这个西瓜是一个好瓜
所以说当我们构建完决策树后可以很快速的来根据待分类数据的特征值来判断待分类项的类别

那么如何构建一棵好的决策树呢？

我们将从特征选择，决策树的生成，决策树的剪枝三个部分来进行讲解
本篇首先讲述

特征选择

如果数据中的特征数量过多，在决策树学习开始时，可以先对特征进行选择，只留下对训练数据有足够分类能力的特征，以提高决策树学习效率。

什么样的特征是不具有分类能力的呢？ 如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。

通常特征选择的准则是信息增益或信息增益比。

下面介绍下 信息熵，条件熵，信息增益，以及信息增益比

信息熵是表示随机变量不确定性的度量。

设X是一个取有限个值的离散随机变量 其概率分布如下
则随机变量X的熵可以表示为

对信息熵公式的讲解见我的另一篇博客

信息熵公式的详细讲解
https://blog.csdn.net/qq_44822951/article/details/109254549

熵越大说明随机变量的不确定性越大
这句话是什么意思呢？

比如随机变量 X 只有两个取值 0，1
X的分布是这样的
P(X=1)=p P(X=0)=1-p 0<=p <=1
那么它的熵为 h ( p ) =-plog₂p -(1-p)log₂(1-p)
它的图像是这样的

当p=0，p=1 时h( p ) =0 熵值最小 完全没有不确定性 这也很容易理解 当p=0,或者 p=1 时 X只能取一个值 1或者 0 只能取一个值 当然很确定了

当 p=0.5 时 h( p ) =1 熵值最大 相应的不确定性也达到最大 也是可以解释的 X=1 和 X=0的概率相等 我们很难估计 X=? 只能随缘啦

条件熵
条件熵H(Y|X) 表示在已知随机变量X的条件下随机变量Y的不确定性 。
条件熵H(Y|X)定义为 X给定条件下Y的条件概率分布的熵对X的数学期望。

条件熵，是指在给定某个数（某个变量为某个值）的情况下，另一个变量的熵是多少？

因为条件熵中X也是一个变量，意思是在一个变量X的条件下（变量X的每个值都会取），另一个变量Y的熵对X的期望。

条件熵的推导公式为

当熵和条件熵中的概率由数据估计得到，所对应的熵和条件熵也称为经验熵和经验条件熵。

信息增益

信息增益指的是已知特征X的信息而使得类 Y 的信息的不确定性减少的程度。
前面已经介绍了 熵和条件熵，信息增益实际上是 熵和条件熵的差值

下面给出其正式定义

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

那么决策树如何应用信息增益来进行特征选择呢 ？

给定训练数据集 D 以及一个特征A
H(D) 说明了对初始时对数据集 D分类的不确定性有多大
H(D|A) 说明在特征A给定的条件下，对数据集D分类的不确定性是多大
信息增益 G(D,A) 说明了在特征A给定的条件下 对数据集D分类的不确定性的减少程度
信息增益依赖于所选特征，信息增益大的特征，可以更好的对数据集D进行分类。

根据信息增益准则的特征选择方法是:对训练数据集(或子集) D， 计算其每个特征的信息增益，井比较它们的大小，选择信息增益最大的特征。

所以对于一个具体的数据集 怎么对每一个特征求它的信息增益呢？

下面给出一个具体例子
这是一个贷款申请表 特征分别是:年龄 {青年，中年，老年} ,有工作{是，否} 有自己的房子 {是，否} 信贷情况{非常好， 好，一般} 。这是一个二分类问题 ,根据以上特征的取值判断是否准许贷款

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

拿出小本本计算一下哪个特征的信息增益最大

D表示训练数据集
总共数据15条 其中准许贷款的数据有9条，不准许贷款的数据有6 条
则·$$p(准许贷款)=\frac{9}{15}$$ $$p(不准许贷款)=\frac{6}{15}$$
首先计算熵

当选择特征为年龄时

同理 可以求出 g(D,是否有工作)=0.324
g(D,是否有房子)=0.420
g(D,信贷情况)=0.363

因为是否有房子这个特征信息增益最大所以选择它作为首选特征

信息增益的改善- 信息增益比
然而信息增益并不是作为特征选择的最好衡量标准
在以上贷款数据中，如果将没有什么意义的ID也作为一个特征，因为ID和类别是一 一 对应的，所以如果将ID作为划分类别的特征，将不具有任何不确定性，它的信息增益必将是最大的，但是拿ID 作为划分数据的最优特征，毫无意义。所以这也是信息增益的一个缺陷。

因此引出了信息增益比来解决这个问题,定义如下:
根据特征 A 的取值将 D 划分为 n个子集 D₁， D₂… ， D_n