决策树.png写在前面的话
这是一个新的系列，主要讲机器学习的相关算法，希望想入门的你能耐心看完《写在前面的话》
说一个比较普遍的现象，不知道能不能符合大多数同学：
看过Python语法、学过NumPy和Pandas、了解过可视化，也看过西瓜书的一些算法，但是一遇到实际的项目就愣住了，不知道怎么去做了。甚至可能会觉得自己前面的知识还没掌握好，又去补前面的知识，补完了回过头发现还是同样的问题......
就拿机器学习算法这部分来说，小一就放弃过三次，最远的一次是学到了神经网络（完全自学的那种）,然后学不下去了...
小一仔细的分析了一下原因，大概有这么几个：
- ①数学推导内容让人头皮发麻（小一数学太渣）
- ②学会了一个算法，但并不会用于实战项目
- ③学了多个算法之后，因为不会用导致混淆概念，学的越多越混乱
- ④觉得自己基础不好，又回过头去补基础内容
- ⑤其他原因坚持不下去
为了能够最大程度的避免以上问题，小一打算用大白话的形式开始机器学习算法系列，中间会穿插一些情景故事，增加文章趣味性。
最主要还是打算通过理论 实战的模式实现每一篇算法的学习
在算法的理论介绍中会比较少的放一些公式推导和专有名词，主意是在入门和实战，公式推导部分就需要自己私下去学习了，希望大家理解。
另外文章中也会不可避免的出现些许错误，欢迎大家在学习的过程中留言指正。小一也在学习过程中，也会犯错误，希望和大家一起学习交流、一起进步。
如果对文章排版不满意的，可以在文末点击原文链接，原文的排版小一花了些功夫的，希望大家喜欢。
情景一：留学归来韩梅梅
都说女大十八变，确实不假，用在韩梅梅身上更甚贴近。
韩梅梅：留学归来，金融硕士，名企上班，不过她最近却遇到了烦心事
韩妈妈与韩爸爸眼看女儿年龄也不小，又刚从国外回来，国内认识的朋友也不多，影响找对象啊！
两老人在着急的同时也发动亲戚朋友帮助张罗一二。
俩老人心里盘算着：首先通过亲戚朋友确定50个男孩子，条件不能比我们家梅梅差，要人品好，有房有车，工作稳定。
然后从这50个人里面筛选一下，长相最好也要能配得上梅梅
最后剩下的人就拟个名单出来。
文章首发：公众号『知秋小一』按照二八法则，最终选出10个男孩子，应该就是这50个人中佼佼者了，韩爸妈计划完心里美滋滋
在被韩妈妈的彻夜长谈之后，韩梅梅决定去挨个见见爸妈选的10个男孩子。
......
......
眼看10个男孩子都快见完了，韩梅梅每次回来的心情却越来越差了
韩妈妈决定去找自己的多年好闺蜜支支招
情景二：媒婆许姨心憔悴
许媒婆：韩妈妈闺中密友，人称媒婆中的智多星
不愧是专业媒婆，面对好闺蜜女儿的问题，许媒婆给出了这样的建议。
许媒婆：既然是给孩子找对象，那肯定不能依你们的标准来啊许媒婆：而且你的亲戚朋友介绍的男孩子，也都在你们那个圈子里，50个人和5个人没啥区别啊
韩妈妈恍然大悟，果然是越着急越误事啊，都忘了征求梅梅的意见，赶忙去将梅梅带过来
韩梅梅大呼无奈，却还是被妈妈逼着来见许媒婆
韩梅梅：害，其实我的标准挺简单的，有上进心进行。工作可以不稳定，但是可以一起奋斗嘛，可以没房没车，这个以后总会有的嘛，最好能热爱生活一些，不然老是工作多无趣啊（说到这，韩梅梅不禁想到了一个人，这次他应该有机会出现在名单里面了吧，嘿嘿）
韩妈妈与许媒婆相视会心一笑，孩子长大了啊！
许媒婆人缘广，资源多，掏出小本本准备从1000个男孩子中拟一个名单出来。
文章首发：公众号『知秋小一』许媒婆：看，树图我都画好了，我们按照这个去筛选，名单上的保准是梅梅喜欢的 韩妈妈：什么图？ 许媒婆：高科技图，我干儿子教我的，保准没错
时间很快过去了
......
......
一个上午过去了，两人只选了三分之一，还有600多男孩子等着被选择
情景三：决策树来斗芳菲
许媒婆：你看我这个傻脑筋，费这功夫干嘛。
说罢，许媒婆从包里拿出她的ipad，打开了一个软件，将韩梅梅的标准输进去，十秒不到，名单拟出来了，恰好李雷雷也在名单里面。
韩妈妈：嚯，你这是什么软件？这么厉害，快告诉我怎么弄的 许媒婆：我干儿子教我的，这是通过决策树算法算出来的，神奇着呢，来我给你讲讲
我先给你介绍一下决策树：
根据给定结果的样本数据集构建一个决策树，使它能够对未知结果的数据进行预测，对未知样本进行正确的分类
决策树是一个：有监督的分类算法
决策树的构造包括三个过程：特征选择、决策树生成和决策树剪枝
再给你说几个很重要的概念，你认真听
信息纯度：即分歧程度。纯度越高，分歧越小，越容易确定。
信息熵：表示信息的纯度（不确定度）。需要注意的是，信息熵的值越小，表示信息的纯度越高（函数性质决定）
信息增益：表示样本纯度的提升（下降）。信息增益越大，即提升越高，越容易划分。
就这几个概念，你先理解理解
韩妈妈：好了好了，可以开始了吗，我都等不及了！ 许媒婆：okok
特征选择
先给你提几个问题，看看你有没有天赋
- 问题一：既然是一个树，那树的根节点应该怎么确定？
- 问题二：怎么计算每个特征对树的影响？
韩妈妈：你还是直接说答案吧，我这笨脑筋
我们是要构造一棵树，所以上面这两个问题至关重要，第一个问题是如何确定第一步，第二个问题是接下来每一步怎么确定
当我们知道第一步选什么，然后确定每一个分叉点怎么选特征，这棵树不就出来了吗？
在整个决策树的特征选择中，就是一个寻找纯净划分的过程。
而如何寻找一个纯净的划分，即基于纯度来划分，就是整个决策树的核心
而经典的”不纯度“的指标有三种，分别是信息增益（ID3算法）、信息增益率（C4.5算法）、基尼指数（CART算法）
韩妈妈：这不就是上面说的几个概念嘛，我可得好好听听
首先来看ID3 算法
ID3 算法计算的是信息增益，即如果我进行特征的划分，肯定是选择纯度提升的特征
前面我们也提过，纯度越高，表示分歧越小，划分效果越好
嗯，这里不得不放一个数学公式进来了
文章首发：公众号『知秋小一』emmm，还得再放一个
文章首发：公众号『知秋小一』稍微解释一下：
- Gain(D,a)表示a特征的划分可以带来的纯度提升，其中a作为D节点的属性选择，Di表示D节点子节点
- Ent(D)表示D节点的信息熵，p(i|t)表示在t的样本集中i出现的概率
其实就是父亲节点的信息熵减去所有子节点的信息熵，只不过在选取子节点的时候有一个选中的概率
所有我们在计算的过程中需要计算下面这些：
- 当前节点(父节点)的信息熵
- 当前节点的所有子节点的信息熵
- 在当前节点确定的条件下选中相应子节点的概率
要不我再举个简单的例子?
韩妈妈：好啊，刚好我听的有点迷糊
文章首发：公众号『知秋小一』这几个特征要构造一棵决策树，考虑一下下面两个问题
- Q1：如何确定根节点
- Q2：如何选择子节点？例如选择了天气之后，如何选择下一个节点?
根节点的确定：
依次计算四个特征（天气、温度、湿度、刮风）下对结果的信息增益
$Gain(D,天气) = Ent(D) - frac{3} {7}Ent(D1) - frac{2} {7}Ent(D2) - frac{2} {7}Ent(D3)$
$Ent(D) = -(frac{4} {7}logfrac{4} {7} frac{3} {7}logfrac{3} {7}) = 0.985$
每个子节点的信息熵可以这样计算：
文章首发：公众号『知秋小一』代入公式就可以计算通过天气进行特征划分的信息增益Gain(D,天气) = 0.02
同样的方法计算出温度、湿度和刮风特征的信息增益，选择信息增益最大的作为根节点（这里温度的信息增益最大）
子节点的选择：
这一步的重点是确定子节点
上一步已经确定根节点是温度，特征分别是：温度高 & 温度中 & 温度低
然后需要确定每个特征的子节点，即温度高的子节点：天气 & 湿度 & 刮风；温度中的子节点...温度低的子节点...
同样的计算规则计算三个子节点的信息增益，选择信息增益最大的
重复同样的步骤
许媒婆：你觉得上面的ID3算法适用于所有情况吗？ 韩妈妈：我觉得应该，，都适用吧？
并不是的，当节点的分支特别多，每个分支仅有一个样本时，此时节点的信息增益会很大，但是训练出来的模型只适用于当前样本集，也就是过拟合现象。
你可以想象，两个节点A、B，都有10个样本，节点①划分为两个分支（5,5），节点②划分为10个分支（1,1...,1），此时节点②的信息增益是远大于节点①的
所以啊：ID3会对取值数据较多的属性有所偏好
#####C4.5算法
科学家是不会允许这样的问题出现的，于是在ID3的基础上做了改进，形成了C4.5算法
还是要放一下公式
文章首发：公众号『知秋小一』你可以理解成，在信息增益的基础上加了一个参数，这个参数可以有效的弥补信息增益的缺点
因为当属性取值数据较多，$frac{1}{IV(a)}$会很小，,此时的信息增益率也会降低
许媒婆：这个时候的C4.5一定是正确的吗？ 韩妈妈：emmm....
万事不绝对，这个时候C4.5也存在一些问题
我们说属性取值数据较多，$frac{1}{IV(a)}$会很小。但是当属性取值数据较少，$frac{1}{IV(a)}$又会很大
所以C4.5会对取值数据较少的属性有所偏好
韩妈妈：有解决方法吗？
有，从候选划分属性中找出信息增益高于平均水平的，然后在选择信息增益率最高的
当然，上面这两个算法都是基于信息增益来计算的，我们还有一个更厉害的算法：CART算法
而且，就算我们的决策树出现问题，还可以通过剪枝进行优化，方法多着呢。
韩妈妈：嗯啊哦好，还是你这个决策树靠谱。刚想起来我还有点事，先走了啊，改天请你吃大餐！
韩妈妈落荒而逃......
许媒婆会心一笑
情景四：穷追不舍没没没
韩梅梅听完母亲描述的《许媒婆之决策树相亲》，一时大感兴趣，自己稍稍补课之后决定来学习学习
需要和韩梅梅一起补课的同学请猛击：大话系列|决策树（上）
韩梅梅：许姨，我稍稍了解了一下决策树，你这个名单是基于决策树哪个算法的？ 许媒婆：（眼睛一亮），梅梅你也懂这个啊，那我来给你说道说道
CART分类树
这个名单是基于CART算法来实现的，先来看CART算法
CART：Classification And Regression Tree 分类回归树。
和前两种算法不同，CART算法是通过基尼指数反映样本的不纯度
韩梅梅：什么是基尼系数？
基尼系数常用在经济学中，它是用来衡量一个国家收入差距的常用指标。
当基尼系数大于 0.4 的时候，说明财富差异悬殊。基尼系数在 0.2-0.4 之间说明分配合理，财富差距不大。
另外啊，ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。
同时 CART 决策树可以作分类树，又可以作回归树。
许媒婆：既然是二叉树，有没有想起一个概率论知识，二项分布？
是了，当一个分支节点的概率为p，另一个就为1-p，这个二项分布的概念，这里也可以拿来用
所以就有了下面这个公式：
文章首发：公众号『知秋小一』也稍微解释一下，当基尼指数越小的时候，说明样本之间的差异性小，越容易区分。
比如：A节点的两个属性概率分别是0.5和0.5，B节点的两个属性概率分别是0.1和0.9，
根据基尼指数：Gini(A) = 0.5， Gini(B) = 0.18，所以选择B节点进行划分
韩梅梅：CART算法在相亲这里怎么用的？
CART算法可用于两类问题，一类就是相亲这种的分类问题，一类就是回归问题。
和上面的例子一样，在每个特征节点通过计算基尼系数，选择基尼系数最小到的特征，然后一直往下划分，最终的决策树就生成了。
其实过程和前面的ID3、C4.5是一样的，只是这里划分特征用的方法不同而已
韩梅梅：懂了懂了，那为什么不在这用CART回归树来解决呢？ 许媒婆：回归树？我猜你还不懂回归是什么吧，我给你讲讲
CART回归树
回归树是用来解决连续变量的问题，预测的也是连续值，像预测身高、预测房价这些都属于回归类问题
在 CART 分类树中采用的是基尼系数作为标准，那么在 CART 回归树中，如何评价“不纯度”呢？
韩梅梅：距离？
对，但不全对，我们根据样本的离散程度来评价“不纯度”
样本的离散程度需要先计算所有样本的均值，然后计算每个样本值到均值的差值。
许媒婆：我来举个例子吧
我们假设 x 为样本的个体，均值为 μ。
为了统计样本的离散程度，我们可以取差值的绝对值，或者方差。
如果取差值的绝对值，也就是使用最小绝对偏差（LAD）进行目标函数最优化。
其中：差值的绝对值=样本值减去样本均值的绝对值：
$$|x-mu|$$
如果取方差，也就是使用最小二乘偏差（LSD）进行目标函数的最优化。
方差为每个样本值减去样本均值的平方和除以样本个数：
$$s = frac{1}{n} Sigma(x-mu)^2$$
其他的过程和分类树是一样的，也就关于不纯度的评价标准不一样
对了，在回归树中，常用最小二乘偏差进行节点划分。
韩梅梅：那这个树是怎么生成的呢？
这个就是决策树的生成问题，我们前面已经说了关于ID3、C4.5和CART算法的特征节点划分，也粗略的说了树的生成过程。
下面我们把整个过程串起来
决策树的生成
首先需要了解几个决策树的概念：
- 根节点：树的最顶端，最开始的那个节点。
- 分支节点：树中间的非叶子节点
- 叶子节点：树最底部的节点，也就是决策结果。
决策树的生成就是要生成一颗由根节点、分支节点和叶子节点组成的树，这棵树可以实现对未知结果的预测
在树的生成过程中，可以通过ID3、C4.5、CART算法自上而下的实现节点的划分
注意：不论是哪种算法，决策树的构造过程始终是一个寻找纯净划分的过程
韩梅梅：对了，许姨，你这个名单的准确率是多少呢？ 许媒婆：（微微一笑）梅梅你的问题可真多噢，是不是对名单里的哪个男孩子动心思了？ 韩梅梅：我保证这是最后一个问题!都还没见面呢，哪有动心的男孩子，许姨说笑了 许媒婆：行，那我就给你透个底
目前我的相亲名册里面已经整理好的数据就几千条
但是你也知道，决策树是一个有监督的分类算法，需要已经打好标签的数据进行模型
人工打标签是很累的，我都整理好几天了，才整理了一小部分
而且你这次要是能相亲成功，又能帮许姨扩充一下训练数据集了
许媒婆狡黠一笑......
情景五：明眸善睐道不对
韩梅梅：许姨，我发现这个决策树有点点问题 许媒婆：什么问题，你说说看？ 韩梅梅：你看这个决策树的图，左下角这个分支不太对，可以直接删掉这个分支
文章首发：公众号『知秋小一』许媒婆：果然是“人漂亮，眼睛也亮”，这个啊，是需要剪枝的 韩梅梅：剪...剪枝？ 许媒婆：来我给你讲讲
为什么要剪枝呢？
剪枝的操作是为了解决决策树的过拟合问题，如果模型不存在过拟合，可以不进行剪枝操作
提到了过拟合问题，举个例子解释一下吧
期末考试前小一老师出了一份模拟试卷，因为是开卷考试，小房同学考了99分，结果期末考试是闭卷，小房同学只考了59分。
从模型拟合的角度讲，小房同学在模拟试卷上表现优秀，但是在期末试卷上表现很差，这叫过拟合。
如果小房同学在模拟试卷上表现很差，但是在期末试卷上表现也很差，这叫欠拟合。
韩梅梅：过拟合和欠拟合懂了，那怎么避免这种现象的发生？
对于决策树的过拟合现象，可以通过剪枝提高模型的预测能力，剪枝包括预剪枝和后剪枝。
剪枝操作如果要细说估计怕是没个几千字说不完，这里就概括一下
预剪枝
顾名思义，预先剪枝。在决策树生成过程中，对每个节点在划分前先进行估计，如果当前节点的划分不能提升模型的预测能力，则停止划分并且将该节点标记为叶子节点
通俗的说，如果当前节点划分了，却没有带来预测能力的提升，那就不用继续下去了
后剪枝
在决策树生成以后，自底向上的对分支节点进行遍历，计算若将分支节点替换为叶子节点能否对预测能力有所提升，若有，则将该子树替换为叶子节点
通俗的讲，在决策树构造好之后，从下向上把每个分支节点变成叶子节点，若有所提升，则进行剪枝
一般来说，预剪枝是在构造决策树的过程中进行剪枝，所有它的时间开销会小很多，但是由于它剪掉的分枝只是当前最优解，所以它的预测能力要弱于后剪枝。
另外，在sklearn 中只提供了决策树的预剪枝的代码接口，需要注意
情景六：媒婆送上纸玫瑰
许媒婆：梅梅啊，名单也给你了，你觉得有什么问题没？ 韩梅梅：(略略紧张)没...没没，没有问题，许姨我再考虑考虑。 许媒婆：好，那剩下的就靠你自己了，我这有个纸玫瑰{玫瑰}送给你，加油噢 许媒婆：看你还对决策树挺感兴趣的，这个给你
稍稍总结一下决策树
决策树的构造包括三步：特征选择、决策树生成和决策树剪枝
特征选择可以通过信息增益（ID3）、信息增益率（C4.5）、基尼指数（CART）三种方式进行特征的划分选择
决策树生成是通过特征选择，将每个特征属性进行组合组成一棵二叉或多叉树
决策树剪枝对决策树进行剪枝操作，以提高决策树模型的预测能力。
决策树算法的区别与优缺点
ID3算法
- 基于信息增益进行特征选择，选择信息增益最大属性进行特征划分
- 可以生成二叉树和多叉树
- 只可对离散型数据进行分类预测
C4.5算法
- 基于信息增益率进行特征选择，在信息增益高于平均水平的属性中选择信息增益率最大的属性进行特征划分
- 可以生成二叉树和多叉树
- 可以将连续数据离散化之后进行分类预测
- 可以针对缺失数据进行预测
CART算法
- 基于基尼指数进行特征选择，选择基尼系数最小的属性进行特征划分
- 只可以生成二叉树
- 可预测分类问题，也可以预测回归问题
最后，请收下这个吧
decision_tree_xmind.png如果思维导图被二压了，大家可以在原文链接中获取，我猜八成会被二压，因为这张图原图2.3M
写在后面的话
大话算法系列第一篇，打算换个风格来写文章
算法很枯燥，少有人看的下去，但这又是进阶必会的技术栈
小一想着尽可能的用大白话去写，除了必要的数学公式会贴出来
虽然没有数学可能会少一些内容，很不严谨，但却可以让新手尽快入门
建议大家私下抽时间看看数学推导，看看延伸内容，很有必要
算法系列文章每篇都会紧跟着一个实战项目，从数据清洗到模型优化，也算是对以前的所有文章有一个很好的总结应用
下节介绍CART算法和剪枝优化，希望你不要和韩妈妈一样落荒而逃
我是小一，我们下节见
原文链接：大话系列 | 决策树（上篇）
原文链接：大话系列 | 决策树（中篇）
原创不易，欢迎点赞噢
文章首发：公众号【知秋小一】 文章同步：掘金，简书，csdn
欢迎三连支持小一，持续更新中
