从零开始学人工智能-Python·决策树(三)·节点

作者:射命丸咲Python 与 机器学习 爱好者

知乎专栏:https://zhuanlan.zhihu.com/carefree0910-pyml

个人网站:http://www.carefree0910.com

本章用到的 GitHub 地址:

https://github.com/carefree0910/MachineLearning/blob/master/Zhihu/CvDTree/one/CvDTree.py

本章用到的数学相关知识:

https://zhuanlan.zhihu.com/p/24501172

上一章我们把 node 的结构搭好了,这一章要做的就是塞东西进去。为此,我们不妨先看看我们需要实现什么:

一个 fit 函数,它能够根据输入的数据递归生成一颗决策树

一个 handle_terminate 函数,它在 node 成为 leaf 时调用,用于更新它爸爸和它爸爸的爸爸和……等等的信息

一个 prune 函数,用于剪枝

一个 view 函数,用于可视化

大提上来说就是这两点,剩下的就是一些细节。我们分开来说说怎么去实现它们

fit 函数

先说一下大概的流程:

接受数据和相应的标签

判断该 node 是否应该被当做 leaf;若是,则 return,否则继续往下走算出各维度的条件熵,记录下最好的条件熵、信息增益和此时关注的数据维度

比如说,如果输入的数据和标签为:

那么通过计算各个维度的条件熵和信息增益可知,此时该 node 关注的数据维度应该是第一维、也就是 A 对应的那一维。直观来说,这意味着 A 提供的信息量最大(事实上在这个栗子中,A 和 Label 是一样的)

根据信息增益判断是否终止(比如在 ID3 中,如果信息增益小于阈值的话就直接终止。这种判断方法会有比较严重的缺陷,观众老爷们可以想一想为什么 ( σ'ω')σ 【提示:异或数据集】)

根据所选的数据维度的各个特征把数据集切分成几份,分别喂给新的 node、递归,同时把这些 node 记录在自己的 children 里面

由于利用了递归,感觉还是一个比较干净利落的实现。下面就贴一些核心的代码,完整的实现可以参见这里

计算各个维度的条件熵和信息增益,这里就要用到准则章节的东西了

递归

handle_terminate 函数

如果童鞋们还记得我们 node 的结构的话,大概就会知道当一个 node 成为 leaf 后、需要做的事情有两个:

只要分别实现它们就好了:

其中

计算该 leaf 属于哪一类

更新它列祖列宗的 leafs 变量

prune 函数

需要指出的是,node 的 prune 函数不是决策树的剪枝算法、而是会在决策树的剪枝算法中被调用。它仅仅是为了该 node 的所有子孙都切了而已(喂

先说说流程,核心思想其实就是把该 node 变成一个 leaf:

判断该 node 应该属于哪一类

把该 node 的 leafs 中的 leaf 从该 node 的列祖列宗中的 leafs 中删除

把该 node 存进列祖列宗的 leafs 中

把该 node 自身及其所有子孙打上“已被剪枝”的标签

接下来是实现:

其中打标签用的 self.mark_pruned 函数的定义如下:

view 函数

基本思路很简单:如果自己是 leaf、就直接输出相关信息,否则在输出自己相关信息的同时、还要调用自己所有 children 的 view 函数。以下是实现:

这一章有点长,稍微总结一下:

决策树的生长关键是靠递归。当 node 接收一个数据和标签时,它会选出数据的某个维度、记录下来,然后会根据该维度的各个特征将数据、标签进行划分,分别喂给新的 node、从而能够递归下去

在 node 被判定应该是 leaf 时,要判断它属于哪一类并更新它列祖列宗的 leafs 变量

node 的 prune 函数是用来把 node 变成 leaf 并更新结构的,它本身不是决策树的剪枝算法、但它会在决策树的剪枝算法中被调用

下一章我们就要说说怎么建立一个框架以利用这些 node 来搭建一颗真正的决策树了。可能有童鞋已经敏锐地发现:不就只剩一个剪枝算法没有实现了吗?

事实上正是如此。下一章的框架确实只额外地实现了剪枝算法,剩下的都是封装的活儿

希望观众老爷们能够喜欢~

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171229G0ASDW00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券