在进行决策树的了解之前，首先需要对信息熵等概念有一个大致的了解。
| A | B | C | D |
|---|---|---|---|
| 00 | 01 | 10 | 11 |
| P(A)=1/4 | P(B)=1/4 | P(C)=1/4 | P(D)=1/4 |
由这一组变量X组成的序列为：CCDBBCA，若将这个序列通过二进制进行传输，则其编码为：101011010100
可见，我们可以使用两个Bit位来表示一个随机的变量
| A | B | C | D |
|---|---|---|---|
| 0 | 10 | 110 | 111 |
| P(A)=1/2 | P(B)=1/4 | P(C)=1/8 | P(D)=1/8 |
此时，描述一个变量不再需要两个比特了，而是1.75个bit即可，如下所示：
\[
E = 1\times\frac{1}{2}+2\times\frac{1}{4}+3\times\frac{1}{8}+3\times\frac{1}{8}=1.75
\]
\[ E = -log_2(\frac{1}{2})\times\frac{1}{2}-log_2(\frac{1}{4})\times\frac{1}{4}-log_2(\frac{1}{8})\times\frac{1}{8}-log_2(\frac{1}{8})\times\frac{1}{8}=1.75 \]
假设随机变量X具有m个值 ，分别为: \(V_1,V_2,....,V_m\) ，每个值出现的概率如下：
| \(P(X=V_1)=p_1\) | \(P(X=V_2)=p_2\) | \(P(X=V_3)=p_3\) | ... ... | \(P(X=V_m)=p_m\) |
|---|
使用这些变量的期望来表示每个变量需要多少个比特位来描述信息，如下：
\[
E = -p_1log_2(p_1)-p_1log_2(p_1)-...-p_1log_2(p_1)=-\sum_{i=1}^{m}{p_ilog_2(p_i)}
\]
\[ H(X)=-\sum_{i=1}^{m}{p_ilog_2(p_i)} \]
对64个球队进行冠军的预测，若在毫无信息的情况下，最多需要猜测6次
\[ log_264=6(bit) \]
而当你知道了一些信息时，此时可能就不需要进行6次猜测才能猜出谁是冠军了，因为其信息熵改变了；香农指出，此时预测的准确的信息量应为：
\[ H = -(p_1lgp_1 + p_2lgp_2 + ... + p_{64}lg_{64}) \]
其中，\(p_1,p_2, ......, p_{64}\)为队伍夺冠的概率；H则为信息熵，单位为比特
\[ H(Y|X)=\sum_{i=1}^{n}{P(X=v_i)H(Y|X=v_i)} \]
| 专业（X） | 性别（Y） |
|---|---|
| 数学 | M |
| 计算机 | M |
| 英语 | F |
| 数学 | F |
| 数学 | M |
| 计算机 | M |
| 英语 | F |
| 数学 | F |
当X为数学时，Y的信息熵如下：
\[
H(Y|X=数学)=H(Y=F|X=数学)+H(Y=M|X=数学)
\]
\[ =-\frac{1}{2}log_2\frac{1}{2}--\frac{1}{2}log_2\frac{1}{2}=1 \]
同理，当X分别计算机和英语时，Y的信息熵如下：
\[
H(Y|X=计算机)=H(Y=F|X=计算机)+H(Y=M|X=计算机)=0-1\log_21=0
\]
\[ H(Y|X=英语)=H(Y=F|X=英语)+H(Y=M|X=英语)=-1\log_21+0=0 \]
由上述，条件熵表示了在已知随机变量X的条件下随机事件
\[
H(Y|X)=p(X=数学)H(Y|X=数学)+p(X=计算机)H(Y|X=计算机)+p(X=英语)H(Y|X=英语)
\]
\[ =\frac{1}{2}*1+\frac{1}{4}*0+\frac{1}{4}*0=0.5 \]
\[ H(Y|X) = H(X,Y)-H(X) \]
详细推导过程如下：
\[ H(X,Y)=-\sum_{x,y}{p(x,y)log(p(x,y))} \]\[ =-\sum_{x,y}{p(x,y)log(p(y|x)p(x))} \]
\[ =-\sum_{x,y}{p(x,y)log(p(y|x))}-\sum_{x,y}{p(x,y)log(p(x))} \]
\[ =H(Y|X)-\sum_{x,y}{p(x,y)log(p(x))} \]
\[ =H(Y|X)-\sum_{x}\sum_{y}{p(x,y)log(p(x))} \]
\[ =H(Y|X)-\sum_{x}{log(p(x))}\sum_{y}{p(x,y)} \]
\[ =H(Y|X)-\sum_{x}{log(p(x))p(x)} \]
\[ =H(Y|X)-\sum_{x}{p(x)log(p(x))} \]
\[ =H(Y|X)+H(X) \]
举个例子：
比如环境温度是低还是高，和我穿短袖还是外套这两个事件可以组成联合概率分布H(X,Y)，因为两个事件加起来的信息量肯定是大于单一事件的信息量的。假设 H(X)对应着今天环境温度的信息量，由于今天环境温度和今天我穿什么衣服这两个事件并不是独立分布的，所以在已知今天环境温度的情况下，我穿什么衣服的信息量或者说不确定性是被减少了。当已知H(X)这个信息量的时候，H(X,Y)剩下的信息量就是条件熵。
总结：
描述X和Y所需的信息是描述X自己所需的信息,加上给定X的条件下具体化Y所需的额外信息。
\[ g(D,A)=H(D)?H(D∣A) \]
根据信息增益的准则，特征选择方法是：对于训练数据集D，计算其中每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征
计算流程：
\[ H(D)=-\sum_{k=1}^{K}{\frac{|C_k|}{|D|}log\frac{|C_k|}{|D|}} \]\[ 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{|C_{ik}|}{|D_i|}log\frac{|C_{ik}|}{|D_i|}}} \]
将上述结果代入公式，得出信息增益：
\[ g(D,A)=H(D)?H(D∣A) \]
其中
\[ D:样本数据集；|D|:样本个数；|C_k|:k类别个数；A：特征A； \]\[ D_i:根据特征A将总体样本集划分成n个数据集；|D_{ik}|：在划分的第i个数据集中，第k个类别占据的数量 \]
需要注意的是，当在计算熵时，其中的类别的概率由数据估计(即从样本数据)得到时，所定义的熵称为经验熵(empirical entropy)
在有了上述前提知识后，正式进入决策树的内容。
决策树模型呈树形结构，其中每个内部节点表示一个属性的测试 ；
分类问题中，表示基于特征对实例进行分类的过程，它可以认为是if-then规则的集合；
通常决策树学习包括三个步骤：特征选择、决策树的生成和决策树的修剪
决策树分为两大类：分类树和回归树，常用算法有ID3、C4.5、CART等
\[ MSE=\frac{1}{n}\sum_{i=1}^{n}{(y_i-y_{i}^{pred})^2} \]
决策树的构建就是进行属性选择，递归的选择最优特征，根据该特征对训练数据进行划分，使得划分的各个子集尽可能的‘纯‘（让一个分裂子类中待分类的项尽可能的属于同一个类别）
决策树的分割，只是考虑在当前数据特征情况下最好的分割方式，不能进行回溯操作；
选择“纯度”越高的特征属性作为当前需要分割的数据集进行分割操作，持续迭代，直到得到最终结果，决策树是通过“纯度”来选择分割特征属性点的
对数据特征量化“纯度“一般有以下三种方式：
Gini系数\[ Gini=1-\sum_{i=1}^{n}{P_i^2} \]
Entropy熵\[ H(X)=-\sum_{i=1}^{n}{p_ilog_2(p_i)} \]
Error错误率\[ Error=1-max_{i=1}^{n}{p_i} \]
当计算出各个特征属性的量化纯度后，可使用信息增益来选择出当前数据集的分割属性：
决策树构建是一个递归的过程，必须给出停止的条件：
可以通过混淆矩阵来计算准确率、召回率、精确率...
可以采用叶子节点的纯度值总和来评估算法的效果，其值越小，效果越好
\[
C(T)=\sum_{t=1}^{leaf}{\frac{|D_t|}{|D|}H(t)}
\]
决策树的生成主要有以下几种算法：ID3，C4.5，CART(Classfication And Regression Tree)
内部使用信息熵和信息增益来进行构建；每次迭代选择信息增益最大的特征属性作为分隔属性
\[
H(D)=-\sum_{i=1}^{n}{P(i)log_2(P(i))}
\]
\[ Gain(A)=H(D)-H(D|A) \]
优点：
缺点：
在ID3算法的基础上提出：
信息增益率
\[
Gain-ratio=\frac{Gain(A)}{H(A)}
\]
优点 :
缺点：
使用基尼系数作为数据纯度的量化指标来构建的决策树算法就叫做CART(Classification And Regression Tree，分类回归树)算法。
CART算法使用Gini增益作为分割属性选择的标准，选择Gini增益最大的作为当前数据集的分
割属性；可用于分类和回归两类问题。
\[
Gini=1-\sum_{i=1}^{n}{P(i)^2}
\]
\[ Gain=Gini(D)-Gini(D|A) \]
注意事项：CART算法只能构建二叉树
剪枝优化：决策树过渡拟合一般情况是由于节点太多导致的，剪枝优化对决策树的正确率影响是比较
大的，也是最常用的一种优化方式
随机森林：利用训练数据随机产生多个决策树，形成一个森林。然后使用这个森林对数据进行预测，
选取最多结果作为预测结果
决策树的剪枝，是决策树算法中最基本、最有用的一种优化方案，主要分为：
前置剪枝的效果没有后置剪枝的效果好，但是后置剪枝存在计算效率问题，存在一定的浪费问题
对于给定的决策树\(T_0\)
计算所有内部非叶子节点的剪枝系数
查找最小剪枝系数的节点，将其子节点进行删除操作，得到决策树\(T_1\)
重复上述操作，直到产生的剪枝决策树\(T_k\)只有一个节点
得到决策树\(T_0,T_1,T_2,...,T_K\)
使用验证集选择最优子树\(T_a\)
\[ loss=\sum_{t=1}^{K}{\frac{|D_t|}{|D|}H(t)} \]
最小剪枝系数计算：
叶子节点越多，决策树就越复杂，损失越大；
因此对损失函数添加剪枝系数，如下
\[
loss_\alpha=loss+\alpha \times n_{leaf}
\]
考虑根节点为r的子树，剪枝后只保留r本身，而删除所有的叶子：
\[ loss_\alpha(R)=loss(R)+\alpha \times n_{leaf} \]
\[ loss_\alpha(r)=loss(r)+\alpha \times 1 \]
当剪枝前后损失函数相等时，求得剪枝系数：
\[ \alpha=\frac{loss(r)-loss(R)}{n_{leaf}-1} \]
https://github.com/zhuChengChao/ML-DecisionTree
原文：https://www.cnblogs.com/zhuchengchao/p/11663888.html