学习内容

• Decision tree structure
• Learning with decision trees
• Random forests

What is a decision tree?

为了获得更好的泛化，需要使用少量节点

How to construct a decision tree?

**从信息论的知识中我们知道：信息熵越大，从而样本纯度越低。**ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

目的：找到一个与训练实例相一致的小树 思路：（递归）选择 "最重要 "的属性作为（子）树的根。

<aside> 💡 一个好的属性将例子分成（理想情况下）"全部为正面 "或 "全部为负面 "的子集。

</aside>