背景
决策树🌲是一种基本的分类和回归的方法【以前总是下意识以为决策树只能用于分类，事实上还可以用于回归】。在分类问题中，决策树基于特征对实例进行分类，这个分类过程可以认为是if-then的规则集合，也可以认为是特征空间与类空间上的条件概率分布。
NOTE:
if—then规则集合具有一个重要的特征：互斥且完备，即每个实例都被一条路径或者一条规则所覆盖，而且只能被一条路径或一条规则所覆盖
优点：简单易理解、分类速度快
过程：利用损失函数最小化原则对训练集进行建模，再利用建立好的模型进行分类。决策树的学习算法通常是递归地选择最优特征，并根据特征对训练集进行分割，最终形成从【根结点->叶子结点】的树模型，但是这样生成的树可以容易发生过拟合，所以需要自底向上修剪✋
决策树学习包括三个步骤：特征选择、决策树生成、决策树修剪
1.当特征数量较多时，在学习之前先进行特征选择
2.决策树生成对应局部最优
3.决策树修剪对应全局最优
目标：选择一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
特征选择
通常，特征选择的准则是信息增益或者信息增益比
先介绍基本概念：
熵
熵用来表示随机变量不确定的程度，熵越大，不确定程度越大。
设$X$是一个取有限值的随机变量，概率分布为$P(X=x_i)=p_i,i=1,2,…,n$
那么熵定义为：
$$H(X)=-\sum_{i=1}^{n}p_ilogp_i,i=1,2,…,n$$
NOTE:
熵只依赖$X$的分布，与$X$的取值无关，定义$0log0=0$。条件熵
条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。
定义为：$$H(Y|X)=\sum_{i=1}^{n}P(X=x_i)H(Y|X=x_i),i=1,2,…,n$$经验熵和经验条件熵
当熵和条件熵中的概率是由数据估计而得到的，所对应的熵和条件熵被称为经验熵和经验条件熵信息增益
特征$A$对训练集$D$的信息增益$g(D,A)$,定义为集合$D$的经验熵与在给定条件$A$下$D$的经验条件熵H(D|A)之差，即
$$g(D,A)=H(D)-H(D|A)$$
特征选择过程：对训练集计算每个特征的信息增益，并比较信息增益的大小，选择信息增益最大是特征。
INPUT:训练数据集$D$和特征$A$
OUTPUT:特征$A$对训练数据$D$的信息增益$g(D,A)$
#计算数据集$D$的经验熵
$$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$
#计算特征$A$对训练数据$D$的经验条件熵$H(D|A)$：
$$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$$
#计算信息增益
$$g(D,A)=H(D)-H(D|A)$$信息增益比
由于以信息增益进行选择，那么会趋于选择取值较多的特征，所以提出使用信息增益比。
信息增益比定义为：其信息增益$g(D,A)$与训练集$D$关于特征$A$的值的熵$H_A(D)$,即
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中${H_A(D)}=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，$n$是特征值$A$的个数。
决策树生成
ID3算法
核心：在决策树各个结点上应用信息增益准则选择特征，然后递归地构建决策树。
过程：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，构建决策树，直到所有的特征信息增益均很小或者没有特征可以选择为止。
ID3相当于用极大似然法进行概率模型的选择
NOTE:
由于ID3算法只有树的生成，所以生成的树模型容易产生过拟合现象。C4.5算法
过程与ID3相似，只是对ID3进行了改进，使用信息增益比来选择特征。
决策树剪枝
决策树的生成过程仅考虑到对训练数据集分类的准确性，这样生成的树模型容易出现过拟合且构建的树过于复杂，所以有必要对其进行剪枝。
剪枝：从已生成的树上裁掉一些子树或者叶结点，并将其根结点或者父结点作为新的叶结点，从而简化分类树模型。剪枝往往是通过极小化决策树的整体损失函数来实现的
定义损失函数：
设树$T$的叶结点个数为$|T|$,$t$是树的叶结点，该叶结点有$N_t$个样本点，其中$k$类的样本点有$N_{tk},k=1,2,…,K$，其中$H_t(T)$是叶子结点$t$的经验熵，$\alpha\geq 0$为参数，决策树学习的损失函数为：
$$C_a(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$
其中$H_t(T)=-\sum_{k=1}^{K}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
所以最终的损失函数表示为：
$$C_a(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}+\alpha|T|$$
公式解释：$-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$是表示模型对训练集的预测误差，即模型与训练集的拟合程度，$|T|$表示模型的复杂度，叶子节点数越大模型越复杂，$\alpha$是调节参数，控制模型的拟合和复杂程度。
当$\alpha$确定时，选择损失函数最小的模型，这里定义的损失函数其实等价于正则化的极大似然估计。
算法：
INPUT: 生成算法产生的整个树$T$，参数$\alpha$
OUPUT: 修剪后的子树$T_a$
1.计算每个结点的经验熵
2.递归地从树的叶结点向上回缩
回缩前后整体树的损失函数比较，如果回缩前的损失函数大于回缩后，进行剪枝。
3.重复2，直到不能继续为止，得到损失函数最小的子树$T_a$
python 代码实现
后期加入
总结：决策树是一种简单快速的分类算法，本文不仅把熵相关的概念给整理了一遍，文中信息增益和信息增益比也可以用于其他模型的特征选择，而最后剪枝部分提到的决策树的损失函数是我之前在专门写的《详述机器学习中的损失函数》博客中没有提到的，这里也是一个补充。
