《大话机器学习算法》决策树—看这一篇就够了
写在前面的话
这是一个新的系列，主要讲机器学习的相关算法，期望想入门的你能耐心看完《写在前面的话》
说一个比较遍及的现象，不知道能不能符合大多数同学：
看过Python语法、学过NumPy和Pandas、了解过可视化，也看过西瓜书的一些算法，可是一遇到实践的项目就愣住了，不知道怎样去做了。甚至可能会觉得自己X m e } V前面的常识还没把握好，又去补前面的常识，补完了回过头发现仍是相同的V f c 7 A n问题......
就拿机器学习算法这部分来说，小一就抛弃过三次，最远的一次是学到了神经网络（完全自学的那种）,然I $ P后学不下去了…
小一仔细的剖析了一下原因，大概有这么几个：
- ①数学推导内容让人头皮发麻（小一数学太渣）
- ②学会了一个算法，但并不会用于实战项目
- ③学了多个算法之@ ~ { – B R – i ^后，由于不会用导致混淆概念，学的越多越紊乱
- ④觉得自己基础欠好，又回过头去补基础内容 ] b
- ⑤其他原N R Z = ~因坚持不下去
为了能够最大程度的防止以上问题，小一计划} 9 l ( 6 p b u ?用大白话的方式开端机器学习算法系列，中间会交叉一些情形故事，添加文章趣味性。
最主要仍是计划经过理论+实战* z K j ] R f的模式实现每一篇算法的w Q % L @ ^学习
在算法的理论介绍中会比较少的放一些公3 ( t ) Y E u C式推导和专有名词，主意是在入门和4 Y 5 @实战，公式推导部分就需求自己暗里去学习了，期望咱们了解。
别的文章中也会不可防止的呈现少许错误，欢迎咱们在学习的进程中留言纠正。小一也在学习进程中，也会犯错误，期望和咱们一同学习交流、一同前进。
假如对文章排版不满意的，t W I ^ H能够在文末点击原文链接，原文的K N e B X [ 1 3 N排版小一花了些功夫的，期望咱F 2 { O b 1 O们4 = I $ x喜爱。
情形一@ J e : b c F U：留学归来韩梅梅
都说女大十八变，确实不假，用在韩梅梅身上更甚靠近P # 1 7 : A 。
韩梅梅：留学归来，金融硕士，名企上班，不过她最近却遇到了烦心事{ : 3
韩妈妈与韩爸爸眼看女儿年龄也不小，又刚从国外回来，国内知道的朋友也不多，影响找对象啊！
两老人在着急的同时也发动亲戚朋友帮助张罗一二。
俩老Q l Z 9 k 6 F l人心里盘算着：首要经过亲戚朋友确认50个男孩子，条件不能比咱们家w N % K – 0 i梅梅差，要人品好，有房有车，作业稳定。
然后从这50个人里边挑选一下，长相最好也要能配得上梅梅
终究剩余的人就拟个名单| b 7 %出来。
按照二八法则，终究选出10个男: g d 0 a x i *孩子，应该便是这50个人中佼佼者了，韩爸妈计划完心里乐滋滋
在被韩妈妈的彻夜长谈之后，韩梅梅决议去1 b v X F R挨个见见爸妈选的10个男孩子。
……
……
眼看10个男孩子都快见完了，韩梅梅每v F m [ j n .次回来的心境却越来越差了
韩妈妈决议E p Z I s w {去找自己的多年好闺蜜支支招
情形二：V ! 2 9 @ L媒婆许姨心瘦弱H 5 N r . ; ]
许媒婆：韩妈妈闺中密友U k O R，人称媒婆中的智多星
不愧是专业媒婆，面对好闺蜜女儿的问题，许媒婆给出了这样的主张。
许媒婆：既然是给孩子找对象，那必定不能依你们的规范来啊
许媒婆：并且你的亲戚朋友介绍的男} # X孩子，也都在你们那个圈子里，50个人和5个人没啥差异啊
韩妈妈茅塞顿开，果然是越着急越误1 7 J +事啊，都忘了寻求梅梅的定见，急忙去将梅梅带过来
韩梅梅大喊无奈，却仍是被妈妈逼着来见许媒婆
韩梅梅：害，其H u Q O实我的规范挺简略的，有上进心进行。作业能够不稳定，可是能够一同奋斗嘛，能够没房没车，这个* – 2 ; ]今后总会有的嘛，最好能热爱生活一些，否e l Z A ] ~ %则老是作业多无趣啊（提到这，韩梅梅不禁想到0 = A i J z % + G了一个人，这次他应该有机会呈现在名单_ % Y ~ i里边了吧，嘿嘿）
韩妈h B b ( 4 p L 3 z妈与? M j } e p }许媒婆相– D S f Y W % I视会心一笑，孩子长大了啊！
许媒婆分缘广，资源多，掏出小本本预备从1000个男孩子中拟一个@ n c % .名单出来P j 1。
许媒婆：看，树图我都画好了，咱们按照这个去挑选，名单上的保准I P U o = @ Z ! s是梅梅喜爱的
韩妈妈：什么图？
许媒婆：高科技图，) } c X我干儿子教我的，保准没错
时刻很快过去了
……
……
一个上午过去了，两人只选了三分之一，还有600多男孩子等着被挑选
情形三 [ # A : {：决议计划树来斗芳香
许媒婆Z K o a K i G @ K：你看我这个傻脑筋，费这功夫干嘛。
说罢，许媒婆从包里拿出她的ipad，打开了一个软件，将e B P韩梅梅的规范X q ` } w E输进去，十秒不到，名单拟出来了，恰好李雷雷也在名单里边。
韩妈妈：嚯，你这是什么软件？这么凶 I S 6 X . v H 1猛，快告诉我怎样弄的
许媒婆：我干儿子教我的，这是经过决议N p Q @ F计划树算法算出来的，神奇着呢，来我给你讲讲
我先给你介绍一下决议计划树：
依据给定成果的样本数据集` $ R A u b 4构建一个决议计划树，使它能够对不知道成果的数据进行猜测，对不知道样本进行正确的分类
决议计划树是一个：有监督的分类算法
决议计划@ d L树的结构包含三个进程：特征挑选、决议计划树生成和决议计划– c . A /树剪枝
再给你说几个很重要的概b S z X 5 ? .念，你认真听
信息纯度：即不合程度。纯度越高，不合越小，越简略确认。
信息熵：表明信息的纯度（不确认度）。需求留意P B j | w的是，信y 5 [ ` 3 ;息熵的值越小，表明信息的纯度越高, o ) _ L I h = M（函数性质决议）
信息增益L & ~ y ) ; v ：表明样本纯度的提高（下降）。信息增益越大，即提高越高，越简略区分。
就这几个概念，你先了解了解
韩妈妈：好了好了，能够开端了吗，我都等不及了！
许媒婆：ol / [ 7 Tk4 f s W Nok
特征挑选
先给你提几个问题，看看你有没有天分
-
问题一：既然是一个树，那树的根节点应该怎样确认？
-
问题二：怎样核算每个特征对树N q D F : Z的影响？
韩妈妈：你仍{ W Z G } { ] O u是直接说答案吧，我这笨脑筋
咱们是要结构一G ` g ? 3 @ # M棵树，所以上面这两个问题至关重要，第一个问题是怎么确认第一步4 7 } 5 s / }，第二个问题是接下来每一步怎样确认
当咱们知道第一步选什么，然后确认每一个分叉点怎样选特征，这棵树不就出R k A 5来了吗？
在C , ? : ? 3 ) 3整个决议计划树的特征挑选中，便是一个寻觅纯洁区分的进程。
而怎么寻觅一个纯洁的区分，即依据纯度来区分，便是整个决议计划树的中心
而经典的”不纯度“的方针有三种，分别是信息增益（ID3算法）、信息增益率（C4.5算法）、基尼指数（CART算法）
韩妈妈：这不便是上面说的几个概念嘛，我可得好好听听
首要来看ID3 算法
ID3 算法核算的是信息增益，b n 3即假如我进行特征的区分，必定是挑选纯度提高的特征
前面咱们也提过，q K i纯度越高，表明不合越小，L & t K t T : –区分效果越好
嗯，这儿不得不放一个数学公式进来了
emmm，还得再放一个
略微解释一下：
-
Gain(D,a)表明a特征的区分能够带来的纯度, U f &提高，其间a作为D节点的特点挑选，Di表明D节点子节点
-
Ent(D)表明D节点的信息熵，p(i|t)) h I F表明在t的样本会集i呈现的概率
其实便是父亲节点的信息熵减去一切子节点e 1 的信息熵，只不过在选取子节点的时分有一个选中的概率
一切咱们在核算的进% 2 c * J程中需求核算下面这些：
- 当时节点(父节点)的信息熵
- 当时节点的一切子节点的信息熵
- 在当时节点确认的条件下选中相应子节点的概率
要不V f a我再举个简略的比方?
韩妈妈：好啊，刚好我听的有点迷糊
这几个特征要结构一棵决议计划树，考虑一下下面两个问题
-
Q1：怎么确认根节点
-
Q2：怎么挑选子节点？例如挑选了气候之后，怎么挑选下一个节点?
根节点的确认：
顺次核算四个特征（气候、温度、湿度、刮风）下对成果的信息增益
每个子节点的信息熵能够这样核算：
代入公式就能够核算经过气候进行特征区分的信息增益Gain(D,气候) = 0.02
相N d @ p 1 x同的办法核算j A q R v : 7 ] _出温度、湿度和j X a刮风特征的信息增益，挑选信息增益最大的作为根节点（这儿温度的信息增益最大）
子节点的挑选：
这一步的重点是确认子节点
上一步现已确认根节点是温度，特征分别是：温度高 & 温度中 & 温度低
然后需求确认每个特征的子节点，& 3 Q E i ^ f $即温度高的子节点：气候 & 湿度 & 刮风；温度中的子节点…温度低的子节点…
相同的核算规矩核算三个子节点的信息增益，挑选信息增益最大的
重复相同的进程
许媒婆：你觉得上面的ID3算法适用于一切情况吗？
韩妈妈：我觉得应该，，都适用吧？
并不是的，当节点的分支特别多，每个分支仅有一个样本时，此刻节点的信息增益会很大，可是训练出来的模型只适用于当时样本集，也便是过拟合现象。
你能够幻想，两个节点A、B，都有10个样本，节点①区分为两个分支（5,5），节点②区分为10个分支（1,1…,1），此k 1 h P 2 ~ Y J A刻节点②的信息增益是远大于节{ 1 b . O s点①的
所以啊：ID3X % 1 K h e会对取值数据较多的特点有所偏好
C4.5算法
科学家是不会允许这样的问题呈现的，于是t l 7 Y在ID3的基础上做了改善，形成了* Z = l 0 LC4.5算法
仍是要放一下公式
你能够了解成，在信息增益的基D I q O S % T础上加了一个参数，这个参数能够有效的补偿信息增益的缺陷
由于当特点取值数据较多，会很小，,此刻的信息增益率也会下降
许媒婆：这个时分的C4.5一定是正N D A v I 5 o q G确的吗？
韩妈妈：emmm…q S g @ y f 5 ; o.
万事不肯定，这个时分C4y m Y b | i P S $.5也存在一些问/ w m & i题
咱们说特点取值数据较多，会很小。可是当特点取值数据较少，又会很大
所以C4.5会对取值数据较少的特点有所偏好
韩妈妈：有处理办法吗？
有，从候选区分特点中找出信息增益高于平均水平的，然后在挑选信息增益率最高的
当然，上面这两个算法都是依据信| z *息增益来核算的，咱们I r | u w还有一个更凶猛的算法：CART算法
并且，就算咱们w ? d / Y的决议计划树呈现问题，还能够= Q I Q p % q J经过剪枝进行优化，办法多着呢。
韩妈妈：嗯啊哦好，仍是你这个决议计划树靠谱。刚想起来我还有点事，先走了啊，改天请你吃大餐！
韩妈妈一败涂地……
许媒婆会心一笑
情形四：穷追不舍没没没
韩梅梅听完母亲描述的《许媒婆之决议计划树相亲》，一时大感兴趣，自己稍稍补课之后决议来学习学习
需求和韩梅梅一同补课的同学请猛击：鬼话系列|决议计划树（上）
韩梅梅：许姨，我稍稍了解了一下决议计划树，你这个名单是依据决议计划树哪个算法的？
许媒婆：（眼睛一亮），梅梅你也懂这个啊，那我来给你说道说道
CART分E X 8 ) R w类树
这个名单是依据CART算法来实现的，先来看CART算法J ^ k d ^ r ^
CC L e L [ j N m EART：Classificationh d t S R | c q And Regression Tree 分类回归树。
和前两种算法不; / l p [同，C0 & _ r T ) m T –ART算法是经过基尼指数反映样本的不纯度
韩{ & ~ u h梅梅：什么是基尼系数？
基尼系数常用在经济学中，它是用来衡量一个国家收入差距的常用方针。
当基尼系数大于 0.4 的时分，阐明财富差异悬殊。基尼系数在 0.2-0.0 4 w Y 4 8 $ o M4 之间阐明分6 @ M a [ J x配合理，财富差距不大。
别的啊，ID3 和 C4.5 算法能够生成二叉树或多叉树，而 CART 只支持二叉树。
同时 CART 决议计划树能7 k w / l够作分类树，又能够作回归树。
许媒婆：@ ~ D u @ `既然是二叉树，有没有想起一Y ) e h 2 6 9个概率论常识，二项分布^ / % ( { {？
是了，当一个, K ) Y ) * ^ a C分支节点的概率为p，@ u ? A K * 9 R 2另一个就为1-p，这个二r D O ? F项分布的概念，这儿也能够拿来用
所以就有了下面这个公式：
也略微解释一下，当基尼指数越小的时分，阐明样本之间的差异性小，越8 i $ c n简略区分。
比方：A节点的两个特点概率分别是t , ? E 60.5和0.5，B节点的两个特点概率分别是0.1和0.9p 4 w t ; ` q I ,，
依据基尼指数：Gini(A) = 0.5， Gini(B) = 0.18，所以挑选B节点进行区分
韩梅梅：CART| p M W y算法在相亲这儿怎样j @ I d [用的？
CART算法可用于两类问题，一类便是相亲这种的分类问题，一类便是回归问题。
和上面的比方相同，在每个特征节点经过核算基尼系数，挑选基尼系数最小到的n , G p _ L特征，然后一向往下区分，终究的决议计划树就生成了。
其实进程和前面的ID3、C4.5是相同的，仅仅这儿区分特征用的办法不同罢了
韩梅梅：懂了懂了，那为什么不在这用CART回归树来处理呢？
许媒婆：回归树？我猜你还不懂回归是什么吧，我给你讲讲
CAZ u zRT回归树
回归树是用来处理接连变量的问题，3 q w ` b [猜测的也是接连值，像猜测身高、猜测房价这些都属于回归类问题
在 CART 分类树. x _ u # Z中选用的是基尼系数作为规范，那么在 CART 回归树中，怎么G l N t e L @ w J点评“不纯度”呢？
韩梅梅：间隔？
对，但不全对，咱们依据样本的离散程度来点评“不纯度”
样本的离散程度需求先核算一切样本的均值，_ y R 9 L H然后核算每个样本值到均值的差值。K u e * :
许媒婆：我来举个比方吧
咱们假定 x 为样本的个别，均值为 。
为了计算样本的离散程度，咱们能够取差值的肯定值，或许方差。
假如取差y L X值的肯定值，也便是使用最小肯定误差（L: ! t 5 E ZAD）进行方针函数最优化。
其间：差值的肯定值=样本值减去样本均M 1 h e ` g = D值的肯定值：
假如取方差，也便是使用最小二w ( @ n 3 9 R _乘误差（LSD）进行方针函数的最优化。
方差为每个样本值减去样* R }本均值的平方和除以样本个数：
其他的进程和分类树是相同的，也就关于不纯度的点评规范F ! u $ N = u 7不相同
对了，在回归树中，常用最小二乘误差进行节点区分。
韩梅梅：那这个树是怎样生成的呢？
这个便是决议计划树的生成问题，咱们前面现已说了关于ID3、C4.5和CART算法的@ G K $ K D ^特征节点区分，也大略的说了2 * X E U o树的生成进程。
下面咱们把整个进程串起来
决议计划树的生成
首要需求了解几个决议计划树的概念：
- 根节点：树的最顶端L E ，最开端的那个节点。
- 分支节点：树中间的非叶子节点
- 叶子节点：树最底部的节点，也便是决议计划成果。
决议计划树的生成便是要生成一颗由根节点、分支节点和叶子节点组成的树，这棵树能够实现对不知道成果的猜测
在树的生成进程中，能够经过ID3、C4.5、CART算法自上而下的实现节点的区分
留意：不论是哪种算法，决议计划树的结构进程始终是一个寻觅纯洁区分的进程
韩梅梅：对了，许姨，你这个名单的准确率是多少呢？
许媒婆：（微微一笑）梅梅你的问题可真多噢，是不是对名单里的哪个) u 5 u S V M F 0男孩子动心思了？
韩梅梅：我确保这是终究一个问题!都还没碰头呢，哪有M [ &动心的男孩子，许姨说笑了
许媒婆：行，那我就给你透个底
目前我的相i 6 z 4 i亲名册里边现已整d m %理好的数据就几千条
可是你也知道，决议计划树是一个有监督的分类算法，需求现已打好标签的数据进行模型
人工打标签是很累的，我都整理好几天了，才整理了一小部分
并且你这次要是能相亲成功，又能帮许姨扩充一下训练数据集了
[许媒婆狡黠一笑……]
情形X % e五：明眸善睐道不对
韩梅梅：许姨，我发现这个决议计划树有点点问题
许媒婆：什么问题，你说说看？
韩梅梅：你看这个决议计划树的图，左下角这个分支不太对，能够直接删掉这个分支
许+ ; ? E k ~ X W M媒婆：果J % + 8 0 1然是“人漂亮，眼睛也亮”N * + h，这个啊，是需求剪枝的
韩梅梅：剪…剪枝？
许媒婆：来我给你讲讲
为什么要6 1 v剪枝呢？
剪枝的操作是为了处理决议计划树的过拟合问题，假如模型不存在过拟合，能够不进行剪枝操作
提到了过拟合问题，举个比方解释一下吧
期末考试前小一教师出了一份模仿试卷，由于是开卷考试，斗室同学考了99分，成果期末考试是闭卷，P w 1 1 C @斗室V T [ | . V同学只考了59分。
从模型拟合的角度讲，斗室同学在模仿试卷上体现优秀，可是在期末试卷上体现很差，这叫过拟合。
假如斗室同学在模仿试卷上体O x ]现很差，可是d k q u在期末试卷上体现也很差，这叫欠拟合。
韩梅梅：过拟合和欠拟合懂了，那怎样防止这种现象的发作？
关于决议计划树的过拟合现象，] 7 j : o O | U V能够经过剪枝提高模型的猜测才能，剪枝包含预剪枝和后剪枝。
剪枝操作假如要细说估计怕是没个几千字说不完，这+ 5 `儿就归纳w . _ ^一下
预剪枝
望文生义，预先剪枝。在决议计划树生成进程中，对每个Y T / H :节点在区分前先进行估计，假如当时节点的区分不能提高模型的猜测才能，则停止区分并且将该节点标记为叶子节点
浅显的说，假如当时节点区分了，却没有带来猜测才能的提高，那就不用k { M * a R h继续下去了
后剪枝
在决议计划树生成今后，自底向上的对分支节点进行遍历，核算若将分支节点替换为叶子节点能否对猜测才能有所提高，若有，则将该子树替换为叶子节点
浅显的讲，在决议计划树结构好之后，从下向上把每个分支节点变成叶子节点，若有所提高，j ~ R j则进行剪枝
一般来说，预剪枝是在结构决议计划树的进程中进行剪枝，一切它的时刻开销会小许多，可是由于它剪掉的分枝仅仅当时最优解，所以它的猜测才能要弱于后剪枝。
别的，在sklearn 中只提供了决议计划树的预剪枝的代码接口，需求留意
情形六：媒婆送上纸玫瑰
许媒婆：梅梅啊，名单也给你了，你觉得有什么问题没？
韩梅梅：(略略紧张)没…没没，没有问题，7 ; G | z D p许姨我再考虑考虑。
许媒婆：好，那剩余的就靠你自己了，我这有个纸玫瑰c , !{% c T i g b玫瑰}送给你，加油噢
许媒婆：看你还对决议计划树挺感兴趣的，这个给你
稍稍总结一下决t a # @ ( $ P 4 }议计划树
决议计划树的结构包含三步：特征挑选、决议计划树生成和决议计划树剪枝
特征挑选能够经过信息增益（ID3）、信息增益率（C4.5）、基尼指数（CART）三种方式进行特征的区分挑选
决议计划树生成是经过特征挑选，将每个特征特点进行组合组成一棵二叉或多叉树
决议计划树剪枝对决议计划树进行剪枝操作，以提高决议计划树模型的猜测[ : 2 R * 才能。
决议计划树算法的差异与优缺陷
ID3算法
- 依据信息增益进行特征挑选，挑选信息增益最大特点进行特征区分
- 能够生成二叉树和多叉树
- 只可对离散型数据进行分类猜测
C4.5算法
- 依据信息增益率进行特征挑9 B 9 # . Q选，在信息增益高于平均水平的特点中挑选信息增益率最大的特点进行特征区分
- 能够生成二叉树和多叉树
- 能够将接连数据离散化之后进行分类猜测
- 能够针对缺失数据进行猜测
CART算法
- 依据基] 5 $ :尼指数进行特征挑选，挑选基尼系数r ! 8 8 最小的特点进行特征区分
- 只& s C Q C能够生成二叉树
- 可猜测分类问题，% 2 {也能够猜测回归问题
终究，请收下这个吧
假如思想导图被二压了，咱们w n I ; r |能够在原文链接中获取，我猜八成会被e _ / 4 ^ s r h二压，由于这张图原图2.3M
写X – 4 l O s D在后边的话
鬼话算法系列第一篇，计划换个风格来写p Q o ( – _ *文章
算法很单调，少有人看的下去，但这又是进阶必会的技能栈
小一想着尽可能的用大白话去写，除了必要的数学公式会贴出来
尽管没有数学可能会少一些内容，很不严谨，但却能够让x M 8新手赶快入门K ] w x q a + K ?
主张咱们暗里抽时刻看看数学推导，看看延伸内容，很有I ) o z D ^ p # 3必要
算法系列文章每篇都会紧跟着一个实战项目，从数据清洗到模型优化，也算是对曾经的一切Y h s U ^ V 7 ] J文章有一个很好的总结使用
下节介绍CART算法和剪枝优化，期望你不要和韩妈妈相同一败涂地
我是小一，咱们下节见
原文链接：鬼话系列 | 决z l ` | D议计划树（上篇）
原文链接：鬼话系列 | 决议计划树（中A O S h 5篇）
原创不易，欢迎点赞噢
文章首发：大众号【知秋小一】
文章同步：6HU网，简书，csdn
欢迎三连支持小一，继续更新中
