• 从根节点开始一步步走到叶子节点（决策）
• 所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

决策树从根节点开始到叶子节点中的判断条件是有先后的，要先进行尽可能对的分类任务，再往下的做更加细致的分类（微调）

• 根节点：第一个选择点
• 非叶子节点与分支：中间过程
• 叶子节点：最终的决策结果

• 训练阶段：从给定的训练集构造出来一棵树（从跟节点开始选择特征，
  如何进行特征切分）
• 测试阶段：根据构造出来的树模型从上到下去走一遍

• 问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？
• 目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类
  情况，找出来最好的那个当成根节点，以此类推

熵：熵是表示随机变量不确定性的度量

熵值，类比物体内部的混乱程度，越混乱的，熵值越大

怎么用熵值来做衡量？
决策树经过一次决策之后，通过看它结果的熵值来判断决策的好坏

公式：
H ( X ) = − ∑ P i ∗ l o g P i , i = 1 , 2 , 3 , . . . , n , P i ⊂ [ 0 , 1 ] H(X) = -\sum P_i*logP_i , i=1,2,3,...,n ,P_{i}\subset [0,1] H(X)=−∑Pi​∗logPi​,i=1,2,3,...,n,Pi​⊂[0,1]
公式解读：

P P P 为某个类别在数据总样本的概率
① ○○○○○○○○○○
② ○○○○○○△△△△
假设现在有两组数据，分别为①、②
以 ○ 为例， P ○ P_○ P○​ 为 ○ 在数据总样本的概率， P △ P_△ P△​ 为 △ 在数据总样本的概率:
P ○ 1 = 1 P_{○1}=1 P○1​=1、 P ○ 2 = 0.6 P_{○2}=0.6 P○2​=0.6、 P △ 2 = 0.4 P_{△2}=0.4 P△2​=0.4
∵ P i ⊂ [ 0 , 1 ] \because P_{i}\subset [0,1] ∵Pi​⊂[0,1]
∴ l o g P i < = 0 \therefore logP_{i} <= 0 ∴logPi​<=0
∴ l o g P ○ 1 > l o g P ○ 2 + l o g P △ 2 \therefore logP_{○1} > logP_{○2}+logP_{△2} ∴logP○1​>logP○2​+logP△2​
∴ P ○ 1 ∗ l o g P ○ 1 > P ○ 2 ∗ l o g P ○ 2 + P △ 2 ∗ l o g P △ 2 \therefore P_{○1}*logP_{○1} > P_{○2}*logP_{○2}+P_{△2}*logP_{△2} ∴P○1​∗logP○1​>P○2​∗logP○2​+P△2​∗logP△2​
∴ − P ○ 1 ∗ l o g P ○ 1 < − P ○ 2 ∗ l o g P ○ 2 − P △ 2 ∗ l o g P △ 2 \therefore -P_{○1}*logP_{○1} < -P_{○2}*logP_{○2}-P_{△2}*logP_{△2} ∴−P○1​∗logP○1​<−P○2​∗logP○2​−P△2​∗logP△2​
∴ − ∑ P 1 ∗ l o g P 1 < − ∑ P 2 ∗ l o g P 2 \therefore -\sum P_{1}*logP_{1} < -\sum P_{2}*logP_{2} ∴−∑P1​∗logP1​<−∑P2​∗logP2​

由此可见，① 的熵值要低，因为 ① 里面只有一种类别,而 ② 中有两个类别，① 相对于 ② 的熵值就会小很多。

在分类任务中我们希望通过节点分支后数据类别的熵值大还是小,来判断该分类有没有用，那么如何决策一个节点的选择呢？

信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）

这是一个记录了一个人14天打球的情况的数据集，此数据集中有四种环境变化，我们要用它来构建一个决策树分类方法

对此数据集共有4种数据特征，所以我们有四种分类方式

那么问题来了，决策树是由根节点起始的，这四种分类方式里，谁来当这个根节点呢？
这里就需要通过计算来衡量了，衡量的依据就是信息增益

假设：当这四种分类方式分别为根节点时，得到的分类结果

在原始数据中共14天，其中有9天打球，5天不打球，所以此时的熵应为：

− 9 14 l o g 2 9 14 − 5 14 l o g 2 5 14 = 0.940 -\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940 −149​log2​149​−145​log2​145​=0.940

所以我们得到了原始数据的熵值为 0.940 0.940 0.940

下面我们看一下基于 o u t l o o k outlook outlook 特征分类的结果：

o u t l o o k = s u n n y outlook = sunny outlook=sunny 时，熵值为 − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 = 0.971 -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971 −52​log2​52​−53​log2​53​=0.971
o u t l o o k = o v e r c a s t outlook = overcast outlook=overcast 时，熵值为 − l o g 2 1 = 0 -log_21=0 −log2​1=0
o u t l o o k = r a i n y outlook = rainy outlook=rainy 时，熵值为 − 3 5 l o g 2 3 5 − 2 5 l o g 2 2 5 = 0.971 -\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971 −53​log2​53​−52​log2​52​=0.971

算出每个分类结果的熵值之后，需要乘上权重再加和

根据数据统计， o u t l o o k outlook outlook 取值分别为 s u n n y sunny sunny， o v e r c a s t overcast overcast， r a i n y rainy rainy 的概率分别为 P s u n n y = 5 14 P_{sunny} = \frac{5}{14} Psunny​=145​， P o v e r c a s t = 4 14 P_{overcast}=\frac{4}{14} Povercast​=144​， P r a i n y = 5 14 P_{rainy}=\frac{5}{14} Prainy​=145​

此时熵值计算结果为：
5 14 ∗ 0.971 + 4 14 ∗ 0 + 5 14 ∗ 0.971 = 0.693 \frac{5}{14} * 0.971 + \frac{4}{14} * 0 + \frac{5}{14} * 0.971 = 0.693 145​∗0.971+144​∗0+145​∗0.971=0.693

信息增益：系统的熵值从原始的 0.940 0.940 0.940 下降到了 0.693 0.693 0.693，增益为 0.247 0.247 0.247
同样的方式可以计算出其他特征的信息增益，计算完的四种分类结果所得的信息增益如下：

$g\; a\; i\; n\; (\; t\; e\; m\; p\; e\; r\; a\; t\; u\; r\; e\; )\; =\; 0.029\; gain(temperature)=0.029g\; a\; i\; n\; (\; h\; u\; m\; i\; d\; i\; t\; y\; )\; =\; 0.152\; gain(humidity)=0.152g\; a\; i\; n\; (\; w\; i\; n\; d\; y\; )\; =\; 0.048\; gain(windy)=0.048$

那么我们选择最大的信息增益的分类特征作为根节点就可以了，相当于是遍历了一遍特征，找出来了最大的信息增益，然后再其余的中继续使用以上的方法计算信息增益往下寻找

关于信息增益（ID3），有一个问题，就是不适合去解决种类特别多的数据分类，例如：像ID 这类数据，将其作为数据集中的一种特征放入分类训练中时，ID = 1.2.3.4… 它确实可以很好的做出分类，甚至分类后的熵值可以为0，但是，如果是我们在判断是否出门打球的分诶任务中，ID 是没有用的，我们不可能通过一个 ID 的序列号就来断定一个人去不去打球。

为了解决 ID3 的问题，就出现了信息增益率（C4.5），它考虑到了自身的熵值，计算方法： C 4.5 = 信 息 增 益 自 身 熵 值 C4.5 = \frac{信息增益}{自身熵值} C4.5=自身熵值信息增益​

CART：使用 g i n i gini gini 系数来当做衡量标准

g i n i gini gini 系数：
G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p) = \sum_{k=1}^{K}p_k(1-p_k)=1- \sum_{k=1}^{K}p_k^2 Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​

（和熵的衡量标准类似，计算方式不相同， g i n i gini gini 系数越小效果越好）

为什么要进行剪枝？

想象一下，如果树足够庞大，理论上可以完全分得开数据，每个叶子节点就只会剩一个数据，这样决策树过拟合风险很大

决策树剪枝策略分为预剪枝和后剪枝，预剪枝是边建立决策树边进行剪枝的操作，后剪枝是当建立完决策树后来进行剪枝操作

预剪枝：在建立决策树的过程当中，就可以进行剪枝操作。即限制深度、叶子节点个数、叶子节点样本数、信息增益量等

后剪枝：

后剪枝：当建立完决策树后来进行剪枝操作

公式：
C α ( T ) = C ( T ) + α ∗ ∣ T l e a f ∣ C_{\alpha}(T)=C(T)+\alpha*|T_{leaf}| Cα​(T)=C(T)+α∗∣Tleaf​∣

C ( T ) = g i n i ∗ s a m p l e s C(T)=gini*samples C(T)=gini∗samples
T l e a f T_{leaf} Tleaf​：叶子节点的个数
α \alpha α：自定义参数。 α \alpha α 越大，树模型越不过拟合，效果不一定太好； α \alpha α 越小，效果会好，但可能会出现过拟合，
C α ( T ) C_{\alpha}(T) Cα​(T)相当于一个损失，叶子节点越多，损失越大

分类问题中，可用熵值判断
回归问题中，可用方差判断

预剪枝：限制深度、叶子节点个数、叶子节点样本数、信息增益量
后剪枝： α \alpha α