决策树算法及应用

1

决策树

决策树∈分类算法∈监督学习∈机器学习

1.1数学原理

决策树是一种简单高效并且具有强解释性的模型，广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树，可以是二叉树或非二叉树。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

上篇推文中KNN算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。

1.2决策树的构造

（1）信息增益和划分数据集

划分数据集的大原则是：将无序的数据变得更加有序。划分数据集可以根据数据的多个属性来划分，那根据哪个属性来划分是最好的？由此我们引入信息增益的概念，即在划分数据集前后信息发生的变化，对每个属性划分数据集的结果计算一次信息增益，然后判断按照哪个属性划分数据集是最好的划分方式。而计算信息增益就要用到香农熵或者简称为熵。

熵定义为信息的期望值，公式为：

其中n是分类的数目，p(xi)是选择该分类的概率，-log2p(xi)是该分类的信息，计算所有类别所有可能值包含的信息期望值便得到熵。

（2）递归构建决策树

构造决策树其工作原理如下：得到原始数据集，然后采用递归思想多次基于最好的属性值来划分数据集，得到决策树。由于每次划分数据集时属性值可能多于两个，因此可能存在大于两个分支的数据集划分。递归结束的条件是①程序遍历完所有划分数据集的属性；或者②每个分支下的所有实例都具有相同的分类。

2

决策树算法实现

2.1导入数据集

算法实现：

运行结果：

2.2计算香农熵

算法实现：

运行结果：

函数说明（一）

【1】log函数，需要引入math模块中的log函数。语法为log(x,base)，其中：

①x表示数值表达式；

②base表示底数，默认为 e。

算法示例：

运行结果：

【2】math模块的其他常用方法包括

【3】len(s)——用于返回对象s（字符、列表、元组等）长度或项目个数。

算法示例：

运行结果：

2.3划分数据集

算法实现：

运行结果：

函数说明（二）

【1】访问列表

list[i]——访问列表正数第i+1个值

list[-i]——访问列表倒数第i个值

list[i:j]——访问列表正数第i+1到第j+1个值

算法示例：

运行结果：

除此之外，如果列表中的元素也是列表的话，可以通过list[i][j]求出list第i+1个列表中第j+1个元素。

算法示例：

运行结果：

【2】更新列表

append(x)——添加x这个列表

extend(x)——添加列表x中的值

算法示例：

运行结果：

【3】删除列表元素

del list[i]——删除第i+1个元素

运行结果：

2.4 选择最佳数据集划分方式

算法实现：

函数说明（三）

【1】set(x)——将对象x转换为集合类型

算法示例：

运行结果：

【2】float(x)——将对象x转换为float类型

算法示例：

运行结果：

2.5构造决策树

算法实现：

函数说明（四）

【1】operator模块

因为这里需要用到itemgetter，所以需要导入operator模块。operator.itemgetter(item)——返回一个可调用的对象，如果指定了多个item，返回查找值的元组。

算法示例：

运行结果：

【2】count()——统计字符串里某个字符出现的次数。

语法为：str.count(sub, start= 0,end=len(string))。其中：

①sub表示待搜索的子字符串；

②start 表示字符串开始搜索的位置。默认为第一个字符（索引值为0）；

③end表示字符串中结束搜索的位置。字符中第一个字符的索引为 0。默认为字符串的最后一个位置。

算法示例：

运行结果：

2.6 输入新数据测试决策树算法

算法实现：

运行结果：

函数说明（五）

【1】 keys()——以列表方式返回一个字典所有的键。

算法示例：

运行结果：

【2】index(str)—返回子字符串str的开始索引值。基本语法为str.index(str, beg=0, end=len(string))，其中：

①str表示检索的字符串；

②beg表示开始索引，默认为0；

③end表示结束索引，默认为字符串的长度。

算法示例：

运行结果：

【3】type(x)——返回对象x的数据类型

算法示例：

运行结果：

3

决策树应用

下面我们通过一个隐形眼镜选择的例子来应用前面构造的决策树，从而预测患者需要佩戴的隐形眼镜类型。使用小数据集，我们就可以利用构造的决策树学到很多知识，如眼科医生是如何判断患者需要佩戴的镜片类型；一旦理解了决策树的工作原理，我们甚至可以帮助人们去判断需要佩戴的镜片类型。

3.1 数据分析

隐形眼镜数据集是非常著名的数据集，它包含很多患者眼部状况的观察条件以及医生推荐的隐形眼镜类型。隐形眼镜类型包括“硬材质(hard)”、“软材质(soft)”以及“不适合佩戴隐形眼镜(no lenses)”。我们的数据集存在“lenses.txt”这个文本文件中，如下图：

可以看到我们的数据分为五列，前四列为数据属性列，描述患者眼部状况，每个属性有不同的分支条件；最后一列是适合佩戴的眼镜类型。前四列对应的数据属性和分支条件见下表：

3.2 代码实现

算法实现：

运行结果：

函数说明（六）

【1】open()——用于打开一个文件

函数语法：open(name[, mode[, buffering]])。其中：

①name：表示用字符串表示的文件名；

②mode：表示打开文件的模式：只读(r)，写入(w)，追加(a)等。所有的可取值见如下列表，默认文件访问模式为只读(r)；

③buffering：如果 buffering 的值被设为 0，就不会有寄存；如果 buffering 的值取 1，访问文件时会寄存行；如果将 buffering 的值设为大于 1 的整数，表明了这就是的寄存区的缓冲大小；如果取负值，寄存区的缓冲大小则为系统默认。

【2】strip()——用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。

注意：该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。

基本语法：str.strip([chars])

算法示例：

运行结果：

【3】split()——通过指定分隔符对字符串进行切片

基本语法：str.split(str="", num=string.count(str))。其中：

①str为分隔符，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等；

②num为分割次数。

算法示例：

运行结果：

3.3 总结

决策树非常好地匹配了实验数据，然而这些匹配选项可能太多了,我们将这种问题称之为过度匹配。为了解决过度匹配问题，我们可以裁剪决策树，去掉一些不必要的叶子节点，即如果叶子节点只能增加少许信息，则可以删除该节点，并将它归入到其他叶子节点中。我们后续介绍的另一个决策树构造算法 CART将进一步讨论这个问题。

责编 | 栾 申 罗

指导 | 老薛