19.3 决策树学习方法

19.3 决策树的学习

AI导览

本节将带你了解决策树学习的基础框架，说明如何用信息增益来进行属性选择，并介绍模型的表达能力及一些常见改进方向。决策树由于具有良好的可解释性，且能较灵活地处理离散与连续数据，因此在早期人工智能与当代数据挖掘中都发挥了重要作用。不过，实际应用中也需要留意过拟合、树的深度以及缺失数据等问题。

决策树（decision tree）对应一类函数：它把属性值组成的向量映射为单一的输出结果，也就是“决策”。决策树通过执行一系列测试来完成判断：从根节点开始，沿着合适的分支向下走，直到抵达叶节点。图中每个内部节点都代表对某个输入属性的检验；该节点的各个分支会对应该属性的所有可能取值。最终叶节点给出函数需要返回的值。

一般而言，函数的输入与输出既可能是离散，也可能是连续。在这里我们只关注输入为离散值、输出为真（正样例）或假（负样例）的情形。此类设置称为布尔分类（Boolean classification）。我们用字母j表示样例（xj表示第j个样例的输入向量，yj表示该样例的输出）。同时，xj,i用于表示第j个样例的第i个属性。结合图19-3，图中展示了SR在餐厅等待问题上的决策函数。沿着树的路径观察可知：当Patrons=Full且WaitEstimate位于0到10之间时，这些样例将被判定为正，也就是输出“yes”，用于表示要等待餐厅。

图19-3 判断是否在餐厅等待的决策树