首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

决策树算法及应用

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将进一步讨论这个问题。

责编 | 栾 申 罗

指导 | 老薛

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181209G0ZCMH00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券