书名：计算机视觉40例从入门到深度学习：OpenCV-Python
作者：李立宗
出版社：电子工业出版社
出版时间：2022-07-01
ISBN：9787121436857

第15章 机器学习导读

15.3 OpenCV中的机器学习模块

15.3.2 决策树

一、熵

• 香农提出使用熵来度量信息量。
  熵度量的是一条信息的不确定性，即该条信息是由信源发出的所有可能信息中的一条的概率。
  信息越有规律，包含的信息量越大，对应概率越低，对应熵值越低；信息越混乱（均衡分布），对应概率越高，对应熵值越大。

  
  图15-23 例图
• 图15-23（a）中是有序排列的点组成的“OPENCV”，它的熵小；
  图15-23（b）中的点是混乱（分布相对均衡）的，它的熵大。

二、节点纯度

• 决策树借助信息熵表示节点纯度，并据此选择划分属性。
• 决策树使用属性把一个样本集划分为若干个子集。
  例如，使用颜色可以将土豆划分为白色、黄色、紫色等不同子集。
• 我们希望分支结点包含的样本尽可能属于同一类，即结点的纯度越高越好。
  信息熵是衡量样本集的纯度一种指标，其值越小，对应样本集的纯度越高。

三、信息增益

• 如果将样本集的信息熵标注为D，使用属性划分后各个子集的信息熵之和标注为AD，那么差值D-AD被称为信息增益。
  可以看出，信息增益越大，与D相比AD的值越小，也就是说子集的纯度越高。
• 实践中，使用正样本的占比来衡量信息增益值。
  因此，可以根据信息增益，选择决策树的划分属性。
  例如，ID3决策树学习算法将信息增益作为依据来确定划分属性。
• 这里有一个问题，如果信息熵从100减至90，则信息增益为100-90=10；而信息熵从10减少到5，则信息增益为5。
  我们看到，前者信息增益虽然大，但信息熵只有10%的变化；
  后者信息增益虽然小，但信息熵有50%的变化。
  因此，使用增益率作为选择决策的划分属性更适用于可取数目较少的属性。
  例如，C4.5决策树算法采用增益率作为依据来确定划分属性。

四、基尼系数

• 另外，基尼系数也可用来衡量样本集的纯度。
  基尼系数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。
  显然，基尼系数值越低，数据集的纯度越高。
  例如，CART决策树采用基尼系数作为确定划分属性。

五、避免过拟合

• 决策树使用剪枝避免过拟合。
  在构建决策树的过程中，决策树会逐渐长得枝繁叶茂，这时会把测试数据的特征学习得过好，以至于会把测试数据的个别特征作为所有数据的特征，从而导致过拟合。
  通常情况下，采用剪枝去掉一些分支以达到降低过拟合的目的。
  剪枝的基本策略是预剪枝和后剪枝，二者分别对应训练前后的剪枝过程。