精通数据科学算法

第3章　决策树

决策树是数据在树状结构中的排列，根据节点处属性值的不同，数据将被分到不同的分支中。

本章将使用一个标准的ID3学习算法来构建一个决策树，该算法选择一个数据的属性，以最大化信息增益（一种基于信息熵的度量）为目标对数据样本进行分类。

本章将学习以下内容：

• 什么是决策树，以及如何将“游泳偏好”例子中的数据用决策树表示；
• 首先从理论角度说明信息论中信息熵和信息增益的概念，随后将其实际应用于“游泳偏好”例子中；
• 用Python实现一个ID3算法，并从数据训练开始构造一个决策树；
• 如何使用在“游泳偏好”例子中构建的决策树来对新的数据项进行分类；
• 如何使用决策树替代第2章西洋棋游戏中的分析方法，以及两种算法所得的结果有哪些差异；
• 加深读者对何时使用决策树作为分析方法的理解；
• 在“购物”例子中，如何处理在建立决策树过程中数据不一致的问题。

3.1　游泳偏好——用决策树表示数据　

例如，人们可能会对何时游泳有一定的偏好。偏好结果记录在表3-1中：

表3-1

泳衣	水温	游泳偏好
None	Cold	No
None	Warm	No
Small	Cold	No
Small	Warm	No
Good	Cold	No
Good	Warm	Yes

这个表中的数据可以用图3-1所示的决策树分支表示。

图3-1

在根节点有这么一个问题：是否有泳衣？问题的答案将可用数据分成3组，每组有两行记录。如果属性“泳衣”为none，则属性“游泳偏好”为no。不需要进一步知道关于水温的偏好了，因为所有属性“泳衣”为none的样本将被分类为no。属性“泳衣”为“small”的情况也是如此。在“泳衣”为“合适”的情况下，剩下的两行记录可以分为两类：no和yes。 ...