决策树的构造

策略：从上往下学习通过recursive divide-and-conquer process（递归分治过程）

1. 首先选择最好的变量作为根节点，给每一个可能的变量值创造分支。
2. 然后将样本放进子集之中，从每个分支的节点拓展一个。
3. 最后：对每个分支进行递归重复，只使用到达该分支的样本
4. 停止递归：如果所有的样本都有着相同的类别，为这个类创建一个叶节点

信息增益（基于熵）

熵衡量的是这个集合相对于类的纯度。

熵越小，数据集的纯度就越大

熵也用于信号压缩，信息论和物理学。

定义

Entropy H(S)
$$H(S)=I(S)=-\sum _i{P}_i\ast lo{g}_2{P}_i$$
$$P_i$$ 代表属于类别i的样本比例

举例

假设现在有 2 个类别， yes 和 no， 这个集合中有9个yes，5个no 交叉熵的计算如下
$$H(S)=-\frac{9}{14}lo{g}_2\frac{9}{14}-\frac{5}{14}lo{g}_2\frac{5}{14}=0.94bits$$

• 熵是用比特来测量的

• 在计算熵的时候，我们会假设 $$lo{g}_{2}0=0$$

• H(S) 的范围是[0,1]

  • 当H(S) = 0 的时候，S的所有元素都属于相同的类，即这个集合是纯净的，拥有最小的Entropy(熵)
  • 当H(S) = 1 的时候，有相同数量的yes和no（假设是两类），即最小的纯净度，最大的Entropy.

信息增益

• 信息增益度量使用属性划分训练示例集所导致的熵减少。
• 它是两个熵的差：增益= T1-T2
• T1为分裂前与父节点相关联的样本集合S的熵
• T2是S中剩余的熵，在S被属性分割后
• 差值越大，信息增益越高
• 最好的属性是信息增益最高的属性
  • 它减少了父节点的熵

案例

选择outlook作为根节点，以此分出3个子集， 各自有5，4，5个样本。
$$T1=H(S)=I(\frac{9}{14},\frac{5}{14})$$
$$T2=H(S|outlook)=\frac{5}{14}H(S_1)+\frac{4}{14}H(S_2)+\frac{5}{14}H(S_3)$$

修剪决策树

• 如果我们生长决策树来完美地分类训练集，树可能会变得过于具体，并过度拟合数据。
• 过拟合-训练daddata的精度高，但新数据的精度低
• 树变得太具体了，主要是记忆数据，而不是提取模式
• 在决策树中什么时候会发生过拟合？
  • 训练数据太小->没有足够的代表性示例来构建一个可以在新数据上很好地泛化的模型
  • 训练数据中的噪音，例如标签错误的例子
• 使用树修剪来避免过拟合

两个主要策略

• pre-pruning
  • 在它达到完美分类训练数据的点之前，尽早停止生长树
• post-pruning
  • 让树完全生长，让它完美地覆盖训练数据，然后修剪它
• 在实践中优先考虑后修剪
• 不同的后剪枝方法：
  • 子树替换
  • 子树的提升
  • 将树转换为规则，然后修剪它们
• 修剪多少？使用验证集来决定

通过子树替换的修剪思想

自下而上-从树的底部到根部

• 每个非叶节点都是修剪的候选节点，对于每个节点：
• 移除根在它上面的子树
• 用class=majority类的例子替换它候选节点
• 比较新树和旧树通过计算两者的验证集的精度
• 如果新树的精度更好或与旧树的精度相同，保持新树（即修剪候选节点）

总结

• 非常流行的ML技术
• 自上而下的学习使用递归的分治过程
• 易于实现
• 可解释的
• 制作的树很容易被非专家和客户可视化和理解
• 可解释性增加了在实践中使用机器学习模型的信任
• 使用修剪来防止过拟合
• 选择最佳属性-信息增益、增益比等