第3章 决策树

本章内容

  • 决策树简介
  • 在数据集中度量一致性
  • 使用递归构造决策树
  • 使用Matplotlib绘制树形图

你是否玩过二十个问题的游戏,游戏的规则很简单:参与游戏的一方在脑海里想某个事物,其他参与者向他提问题,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围。决策树的工作原理与20个问题类似,用户输入一系列数据,然后给出游戏的答案。

我们经常使用决策树处理分类问题,近来的调查表明决策树也是最经常使用的数据挖掘算法1 。不需要了解机器学习的知识,就能搞明白决策树是如何工作的。

1. Giovanni Seni and John Elder, Ensemble Methods in Data Mining: Improving Accuracy Through Combining Predictins, Synthesis Lectures on Data Mining and Knowledge Discovery (Morgan and Claypool, 2010), 28.

如果你以前没有接触过决策树,完全不用担心,它的概念非常简单。即使不知道它也可以通过简单的图形了解其工作原理,图3-1所示的流程图就是一个决策树,长方形代表判断模块(decision block),椭圆形代表终止模块(terminating block),表示已经得出结论,可以终止运行。从判断模块引出的左右箭头称作分支(branch),它可以到达另一个判断模块或者终止模块。图3-1构造了一个假想的邮件分类系统,它首先检测发送邮件域名地址。如果地址为myEmployer.com,则将其放在分类“无聊时需要阅读的邮件”中。如果邮件不是来自这个域名,则检查邮件内容里是否包含单词曲棍球,如果包含则将邮件归类到“需要及时处理的朋友邮件”,如果不包含则将邮件归类到“无需阅读的垃圾邮件”。

enter image description here

图3-1 流程图形式的决策树

第2章介绍的k-近邻算法可以很好地完成分类任务,但是它最大的缺点就是无法给出数据的内在含义,决策树的主要优势就在于数据形式非常容易理解。

本章构造的决策树算法能够读取数据集合,构建类似于图3-1的决策树。决策树的一个重要任务是为了理解数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,这些机器根据数据创建规则的过程,就是机器学习的过程。专家系统中经常使用决策树,而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

现在我们已经大致了解了决策树可以完成哪些任务,接下来我们将学习如何从一堆原始数据中构造决策树。首先我们讨论构造决策树的方法,以及如何编写构造树的Python代码;接着提出一些度量算法成功率的方法;最后使用递归建立分类器,并且使用Matplotlib绘制决策树图。构造完成决策树分类器之后,我们将输入一些隐形眼镜的处方数据,并由决策树分类器预测需要的镜片类型。

目录