作者：射命丸咲 Python 与 机器学习 爱好者
往期阅读：
本章用到的 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 函数
先说一下大概的流程：
接受数据和相应的标签
根据信息增益判断是否终止（比如在 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 是否应该被当做 leaf；若是，则 return，否则继续往下走算出各维度的条件熵，记录下最好的条件熵、信息增益和此时关注的数据维度
比如说，如果输入的数据和标签为：
这一章有点长，稍微总结一下：
决策树的生长关键是靠递归。当 node 接收一个数据和标签时，它会选出数据的某个维度、记录下来，然后会根据该维度的各个特征将数据、标签进行划分，分别喂给新的 node、从而能够递归下去
在 node 被判定应该是 leaf 时，要判断它属于哪一类并更新它列祖列宗的 leafs 变量
node 的 prune 函数是用来把 node 变成 leaf 并更新结构的，它本身不是决策树的剪枝算法、但它会在决策树的剪枝算法中被调用
下一章我们就要说说怎么建立一个框架以利用这些 node 来搭建一颗真正的决策树了。可能有童鞋已经敏锐地发现：不就只剩一个剪枝算法没有实现了吗？
事实上正是如此。下一章的框架确实只额外地实现了剪枝算法，剩下的都是封装的活儿
希望观众老爷们能够喜欢~
公众号后台回复关键词学习
回复 人工智能 揭开人工智能的神秘面纱
回复 贝叶斯算法 贝叶斯算法与新闻分类
回复 机器学习 R&Python机器学习
回复 阿里数据 阿里数据系列课程
回复 Python Python机器学习案例实战
回复 Spark 征服Spark第一季
回复 kaggle 机器学习kaggle案例
回复 大数据 大数据系列视频
回复 数据分析 数据分析人员的转型
回复 数据挖掘 数据挖掘与人工智能
回复 机器学习 R&Python机器学习
回复 阿里数据 阿里数据系列课程
回复 R R&Python机器学习入门
