机器学习算法实战之决策树

标题：

设计决策树

构造决策树

获取数据

计算给定样本的信息熵

计算给定节点的信息增益

划分节点

树体构建

创建树

创建节点

构造注解树

用matplotlib注解功能绘制节点

获取叶节点的数目与树的层数

计算叶节点的数目

计算树的层数

绘制树

绘制函数

主函数

经过两章关于决策树的理论讲解，我们是时候通过Python来实践编写一棵简单的决策树了。这一次我们仍然使用Python2.7，如果有读者使用Python3，您可能需要在实践的时候作出一些小小的修改，但问题不大，而实际上如果可以的话，使用Python3或许会更适合这方面的学习。这次我们使用的数据集依然是是西瓜书的西瓜数据集2.0，因为这能与我们之前两章的内容有个比较好的照应，同时也有助于我们理解。

现在让我们来开始着手编写自己的决策树：

1.设计决策树

在实际上手构造之前，我们首先要确定我们的决策树是一种什么样的结构，并确定它的保存方式。我这里直接使用了python内置的词典来构造决策树，优点是方便快捷，缺点就是数据集如果太大，时间和空间开销也会比较大。

但为了方便起见，这里还是不从头写一个树形结构而是直接开始构造我们的决策树比较好。

因此，我们设计的决策树的架构就是词典的层层嵌套，用图形来表示，就像这样：

把图片中蓝色块与箭头看作是组合成的决策树，那么右边的那个词典就是这棵决策树在Python中的结构对象。

在确定好决策树的架构之后，我们就可以开始着手构造啦。

2. 构造决策树

a. 获取数据

我们上面讲过，这次用的数据集是西瓜书中的西瓜数据集2.0，下图是它的具体内容：

如果有需要的话，您可以在网上搜索到这个数据集，或者在小编在文章末尾附上的github链接中下载到，不仅如此，该github仓库中还会包含我们之前的文章中写的代码和相关的数据集，如果您发现有部分缺失（实际上肯定会有...因为我们也还在补充中），可以在后台留言提醒我们将缺失部分补齐。

现在我们写一个获取数据的函数，这个函数非常简单：

这里我使用了pandas库，它是一个基于NumPy构建的第三方库，在理解和读取数据方面，pandas的效果会比直接使用NumPy更佳。特别是像上图的那种用逗号分隔的数据，第一行为特征名称和类别名称，下面是特征及其对应标签，pandas有专门为这种数据设计的读取方式，不过这种数据更常见的后缀名是而不是上面代码中的，另外，excel文档也提供了保存为格式的选项，因此csv文件会是数据处理相关工作中比较常用的数据格式。

代码中第一行是对本地数据集的提取操作，我们设置编码格式是因为这一次我们读取的数据是中文的。这行读取代码可以直接将读取而来的数据集转化为pandas中DataFrame的格式，接下来我们也将会使用比较多的pandas库的内容。

DataFrame取出来的数据集格式如下

（其实有经验的读者会发现这里我们可以直接在中添加参数来将编号设置为索引，那样子会使得数据更加简洁，但因为小编希望将对这部分的处理也加入到代码中，因此决定还是保留这列）

另外，需要补充的一点是，如果您使用的是Windows平台下的Python2.7，并且在显示中文方面出现了问题，那么为了使代码能够更好的对中文进行适配，可能还需要在脚本开头添加如下一段代码：

这部分代码的作用一方面是让idle的console显示中文时不会出现乱码，另一方面能够让matplotlib能够支持对中文的显示，当然，这只是小编找到的一个可能的解决方案，如果您依然无法显示中文，可以考虑寻找其他方法或者改用英文的数据集。当然这里我们就不介绍这段代码的具体含义了，因为不是本章的重点，如果有感兴趣的读者可以自行了解。

b. 计算给定样本集的信息熵

决策树的一大重点就是计算样本集的信息增益来作为划分数据集的依据，而在这之前，就需要我们先计算数据集的信息熵。计算信息熵的公式为：

然后，根据公式编写计算数据集信息熵的函数：

函数通过接收当前节点上包含的训练样本集和当前节点的名字来计算所有在该节点上的属性的信息熵。

这个语句是一个pandas提供的筛选语句，它返回一个包含所有属性“好瓜”值为“是”的DataFrame。实际上这是一个比较麻烦的写法，并且限制很大（像这里，因为明确写出了数据集的属性，所以这一块就会导致只能对该数据集生效，若是更改数据集，这个地方就要重写），我这里只是做了一个尝试，后面用函数能够更加方便地对DataFrame进行分组。而且要注意的是，对DataFrame的分组和索引切片都不改变原来的DataFrame，并且，被赋值的变量（如上面举的例子中的“goodSet”）都是对原先的DataFrame的一部分进行的深拷贝，这能很大程度上节约计算开销。

也是pandas提供的一个相当方便的计数函数，它能够对指定的DataFrame属性列下所有的属性值进行统计，像是本例中对西瓜的颜色，这个函数就可以分别统计出“青绿”西瓜的数量，“乌黑”西瓜的数量以及“浅白”西瓜的数量，并且以这三个属性（青绿，乌黑，浅白）为索引，对应的数量为值，构建并返回一个DataFrame。

然后是函数，它能够将DataFrame按照指定的属性值分组。在对DataFrame结构的拆分与聚合中起到非常重要的作用。

另外就是计算信息熵的公式部分写的相当的冗杂，读者完全可以对其进行改进。

c. 计算给定节点的信息增益

计算信息增益的公式：

对应的函数代码并不复杂，它接收当前节点的样本集合，节点名称以及属性集合（就是有多少属性需要用来计算信息增益）作为参数，并返回一个包含所有属性的信息增益的词典：

我们这里用了来判断当前结点是不是根节点，如果是根节点，则需要用“好瓜”属性的信息熵作为计算信息增益的当前节点信息熵。

另外，我们只计算属性集里面的属性的信息增益，因为在生成子节点的过程中，子节点相比父节点会少一个属性，因此我们需要通过属性集来传递这种随着节点生成，要计算信息增益的属性渐渐变少的变化。

类似于计算信息熵的函数，这个函数，会返回一个包含当前节点所有属性（即属性集内的属性）的信息增益的字典，格式为。

d. 划分节点

得到一个节点的所有属性的信息增益后，我们就可以根据信息增益来对节点进行划分：

函数接收样本集合，节点名字和属性集合，它内部调用的函数就是我们用来算信息增益的函数。然后经过比较，挑选出信息增益最大的属性的名字，放入并返回。

e. 树体构建

i. 创建树

这是创建一棵树的主函数代码：

代码中使用的也是DataFrame提供的一个用于切片DataFrame的方式，注意中的第二个参数是左右包含的，也就是说这里是选取样本集合DataFrame第一列到倒数第二列的全部内容，以方便我们将样本集中除了“编号”和“好瓜”属性之外所有的属性名称放入属性集合中。

函数是构建树节点的函数，这是我们接下来要写的。

ii. 创建节点

一般来说，在Python中我们会常用递归来实现创建树形结构的节点，主要是可解释强并且方便理解，具体内容如下：

这里，我们参照的编写方式是《机器学习》(周志华著)中的树的基本算法：

至此，我们就算是完整地构造了一棵决策树，可以用下面的代码试着查看一下我们的决策树：

3. 构造注解树

一棵树用字典的表示形式还是比较难以理解的，因此为了能够更直观地表现我们的决策树，我们可以用matplotlib构图的形式来绘制一棵决策树。

如果有读者曾经看过之前一篇在C中嵌入matplotlib绘制B树的文章的话，那么您可以直接跳过关于matplotlib注解函数的功能解释部分，因为反正和之前是一样的。但是关于绘制树的具体算法可以了解一下，因为之前的文章利用了B树的特殊结构简化了绘制算法，而这里的算法是参照Peter Harrington的《Python机器学习实战》中的绘制算法，能够适配更多不同的树形结构。

a. 用matplotlib注解功能绘制节点

matplotlib提供了一个用于编写注解的工具“annotations”，它可以在数据图形上添加文本注释。

藉由它，我们就可以编写一个带有箭头指向的节点，如图：

创建一个节点的函数如下：

是由函数提供的一个类型为matplotlib画板的全局变量，这个函数我们将在后面编写。

先看到，这就是用于创建注解的函数，它与绘制散点图的或者绘制直方图的等绘图函数用的地方相同。

第一个参数接受节点的名字，这个名字会被放在上图中的”finalLoc”的位置，即箭头指向的位置。

参数接收一个tuple (x,y)作为箭头起点的坐标，则接收一个tuple作为箭头指向终点的坐标。

接受表示起点坐标的坐标系，表示（0，0）作为左下角，（1，1）作为右上角。同理。

接受箭头终点节点在图上的形状的类型，我们这里设置了两个类型：

第一个是子节点的形状，第二个是叶节点的形状。

则接受箭头类型：

b. 获取叶节点的数目与层数

在绘制之前，我们还需要构造两个用于计算绘制点坐标的函数。一个是计算叶节点数目的函数，用来计算横坐标，一个是计算树的层数的函数，用来计算纵坐标。

i. 计算叶节点的数目

计算当前节点下叶节点数目的函数如下：

ii. 计算树的层数

然后是当前节点下树的层数的函数：

另外，如果想测试下自己写的函数的效果，还可以手动编写一个小型的测试用的树，其实就是一个多层嵌套的词典，这里我就不再赘述。

c. 绘制树

绘制树的主要函数有两个，一个以递归形式调用绘制节点函数来绘制整个树，一个作为主函数整合绘制函数。

i. 绘制函数

中间编码unicode的部分需要我们在前面写的导入并重写包的内置函数的代码支持：

(详细内容参考[Python中的str与unicode处理方法](http://python.jobbole.com/81244/))

这里采用的计算绘制坐标的计算方式来自《机器学习实战》（Peter Harrington著），我们会在下一个函数后面讲解一下这个计算方式。

ii. 主函数

主函数提供了上面几个函数用到的全局变量，包括决策树的宽（），高（），画板（）等等。清屏函数用来将画板上可能有的之前绘制的内容清除掉，如果是脚本形式编写这个函数用处不大，但如果是交互式编写那么就很有必要了。

绘制函数绘制树形图的原理大致如下，首先将画布水平中心垂直顶部作为起始位置（0.5,1.0），用作为决策树一层的高度，也就是说，从最高点开始，绘制完一层节点后用它来控制绘制的下一层节点的位置（语句使得绘制点下降一层）。函数利用递归原理，先绘制一个节点便直接垂直下降一层，直到绘制完该节点的所有子节点后再垂直上升，切换到同一层的下一个节点。叶节点的水平位置也是用同样的方式控制（便是每个叶节点的宽度）。

设置了绘制点的初始水平位置，之所以这样设置，是为了保证根节点的绘制能够在决策树的中上方。因为我们用于计算每个节点的横坐标的方式是通过绘制点的水平推移：

因此，为了保证第一个绘制的根节点能在所有叶节点的中央，需要有：

最后的最后，将决策树“字典”传入这个函数:

我们就可以看到我们的决策树的图形表示了：

尽管在这篇推文中小编采用了中文数据集，并在整个脚本中都采用的是对中文属性的处理，但实际上这样的做法是非常捞的，用中文数据集的理由仅是为了能与前面的文章相照应，结合对中文属性的处理增加代码的可读性。但在实际任务中，不论是用哪种语言（并不仅限于中文，也包括英文，或者其它语言）描述的数据集的特征，最好都能处理成数字编码，例如在我们使用的西瓜例子中，将色泽中的用来表示，这么做的原因是处理为数字编码后的属性操作起来会更加简单，省去很多麻烦，而且能够方便的做特征工程，像是标准化，归一化，统计起来也会更加方便。至于输出的时候，属性名称像“色泽”要不要换成“color”，属性内容要不要用代替，就仁者见仁智者见智了，用中文或许会增添很多编写时的不便（因为一些字符编码问题），但是输出的结果的可读性却也更高，就像我们在上面的图片中展示的一样，不会让人摸不清头脑，就不会出现不知道像例如这样的决策节点在表示什么的情况。

资料来源参考：

人民邮电出版社 Peter Harrington《机器学习实战》

清华大学出版社 周志华 《机器学习》

数据集与源代码：https://github.com/yzhihao/ML_practice_code

AI遇见机器学习

mltoai

··