• 欢迎访问数智,大数据学习

【ML第三节】:机器学习之决策树算法详解

机器学习 Raybra_Wei 2年前 (2018-07-10) 252次浏览 0个评论 扫描二维码
文章目录[隐藏]

决策树

备注:关于决策树的学习资料主要来源《机器学习实战》

基本认识:决策树是一类常见的机器学习方法,它是一个类似于流程图的树结构。其中每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或类分布,树的最顶层根节点;比较浅显易懂的说吧:一个游戏名叫猜数,游戏由两人组层,一人首先想好一个数字,比如是 56,另一个人进行猜测,比如他猜是 100,想数的人对这个猜测进行判断,给多大于或者小于,这样不断的执行下去,猜数的人会最终得出答案,决策树的工作原理与这个猜数游戏类似,用户输入一系列问题,然后给出答案。决策树的一张经典的图片:

【ML 第三节】:机器学习之决策树算法详解

该图也能很好的阐述决策树的工作原理。

优点:计算复杂度不高,输出结果容易理解,对中间值的缺失不敏感,可以处理不相关特征数据;

缺点:可能产生过拟合问题

适用数据:数值型和标称型

一般流程:

(1)收集数据:可以使用任何方法。

(2)准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。

(3)分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。

(4)训练算法:构造树的数据结构。

(5)测试算法:使用经验树计算错误率。

(6)使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

决策树的构造

决策树的构造,首要问题是当前数据集的那个特征划分数据时起了决定性作用?所以,为了找到这个(或这些)决定性的特征,划分出最好的结果,我们必须评估每个特征。我们对这个特征进行划分测试后,数据集会被分为几个数据子集,他们会分到各个分支上,如果该分支的数据仍然不属于统一分类,那么我们还要继续对这个数据子集进行划分,直到所有具有相同类型的数据均在同一个数据子集中;

伪代码 CreateDTree()如下:

这里的伪代码使用了递归的方法进行实现;

为了更加详细的描述该算法,在这里引入一个样例数据—海洋生物数据,它包含是两个特征和一个标签:

【ML 第三节】:机器学习之决策树算法详解

当我们进行标签分类的时候,首先选择哪一个特征进行分类呢?在解决这个问题之前,我们要通过量化的方法判断如何划分数据;那么划分数据有什么方法或者原则呢。下面我介绍一个划分数据的常用方法—信息增益;

信息增益

划分数据的最大原则是:将无序的数据变的更加有序;组织杂乱无章的数据一种方法是使用信息论度量消息。我们可以在划分数据之前使用信息论量化度量信息的内容;

信息增益:划分数据集之前之后信息发生的变化称为信息增益。那么在一系列特征中,我们选择信息增益最大的特征作为第一划分数据集的特征;

计算信息增益:集合信息的度量方式称为香农熵或者简称熵(源于信息论之父克劳德·香农)。

下面的代码是我第一次进行信息熵算法编写的,代码存在缺陷,没有考虑到特征向量的个数:

运算结果如下:

改进后的信息熵算法:

结果:

熵越高,代表着混合的数据越多,我们可以在数据集添加更多的分类,观察熵值的变化。

在计算熵之后,就可以利用最大信息增益的方法划分数据集。另外一个度量集合无序程度的方法是基尼不纯度,简单的说就是从一个数据集中随机选取一个子项,度量其被错误的斐裂到其他分组的概率。

划分数据集

   数据集的划分根据上述描述的最大信息增益的方法得出最好的数据划分方式,代码如下:

在这个函数里面,参数 dataset 代表传入的数据集,axis 代表当前选择的特征或者属性,value 代表标签分类。通过与标签的比较将同一类的标签的值划分到一个列表中。

在这个函数中,我将所有的特征进行了数据划分比较,这里共涉及两个特征向量;save 和 foot,经过数据划分算法后,第一个特征的信息增益最大,因此在本轮数据划分中应该选择第一个特征作为数据划分的依据。

总结:前面做法很不严谨,总是在 dataframe 与 list 数据结构中做转换,所以最后全部换为 list 数据结构做算法,知识在读取数据集时用了 dataframe。所以代码以最终版本为标准,前面的算法也加了注释封装在源代码中

选择最好的划分方式:

递归构建决策树

构建决策树的原理如下:原始数据集基于最好的特征值分类,经过数据划分之后,将数据传递到树分支上继续上述步骤,直到遍历完所有数据集的特征,或者每个分支所有实例属性具有相同的分类。

结果如下:

测试算法

【ML 第三节】:机器学习之决策树算法详解

 

 

 


数智 Lab , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:【ML 第三节】:机器学习之决策树算法详解
喜欢 (0)
[]
分享 (0)
关于作者:
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址