原理+代码｜深入浅出决策树算法
大家好，我是芒果，近期在工作场景中使用了决策树分类算法，对决策树算法的原理和实战又重新复习了一下，于是就有了这篇文章～
决策树也是经典的机器学习算法之一，在这里挖个坑，希望后续有机会能继续写随机森林、聚类等其他经典的机器学习算法，写不出来当我没说～
本文结构速览：
一、决策树概述
二、决策树原理
三、python实战
四、总结
一、决策树概述
决策树顾名思义是一棵可以帮人决策的树，由根节点、中间节点和叶子结点组成，其中根节点是辅助判断的第一个特征，中间节点代表判断的中间过程，叶子结点代表最后的判断结果。
（图片来源于西瓜书）
上图是一个经典的决策树例子，如何判断一个瓜是好瓜还是坏瓜？当西瓜的纹理清晰、根蒂稍蜷、色泽乌黑、触感硬挺，那么这个瓜就是好瓜。如以上这个例子，决策树的作用就是学习数据中多种特征的规律，来判断并预测西瓜的好坏（因此决策树算法也是典型的有监督学习），当你下次去买瓜，看到纹理清晰、根蒂稍蜷、色泽乌黑、触感硬挺的西瓜就知道这瓜保熟了！
那么问题来了，在进行决策树构建时，依据什么将纹理做为根节点呢，如果将其他要素作为根节点会影响最后的分类结果吗？这就涉及到决策树的原理部分的内容，请继续往下看～
二、决策树原理
2.1 如何衡量信息量的大小 -- 信息熵
我们在日常聊天时，通常会说“你这信息量太大了”，仔细回想一下，在什么情境下才会说这句话：
在王力宏事件之前，相信娱乐圈铺天盖地的“王力宏好男人，王力宏娱乐圈清流”等言论不会引起大多数人的兴趣，因为王力宏一贯以好男人、清流的形象出现在大众面前，未造成较大反差，但是当“李靓蕾锤王力宏、王力宏渣男、蕾神之锤“等言论出现在互联网时，吃瓜群众会很吃惊，才会以”信息量好大“评价整件事情。
所以，我们用信息熵来描述一个事件混乱程度的大小（一个事件我们一定知道结果，那么这个事件的混乱程度就是0，信息量也为0；一个事件充满随机性，我们猜不到或者很难猜到结果，那么他的混乱度就很大，信息量也就很大）
信息熵的计算公式如下，单位为bit
将信息熵的概念放到决策树中，一个瓜是好瓜、坏瓜的概率分别是1/2，但是当一个经验丰富的瓜农见到了特别特别多的瓜之后总结出了一个经验：70%的纹理清晰的瓜都是好瓜。在这个经验的支持下，我们在看到一个瓜时可以首先观察纹理，依据纹理可以更加确定地判断是否是好瓜；
如果瓜农还有第二条经验：80%敲声清脆的瓜都是好瓜，这条经验相比于「纹理」对于好坏瓜的判断贡献更大，在敲声的辅助下更好判断瓜的好坏，因此敲声应该作为判断瓜好坏的第一个特征，也就是根节点。
基于以上例子，我们既要关注某个特征信息熵的大小，也要关注决策前后（即瓜农经验前后）信息熵的变化量，这就是「信息增益」的概念，说人话就是：没有这个条件的情况下的信息熵与有了这个条件信息熵的差值，公式为：
这个公式看起来很复杂，其实很简单，Ent（D）就是在没有任何条件辅助下，判断好坏瓜的信息量，后者就是在敲声条件辅助下，判断好坏瓜的信息量。
2.2 决策树的三种生成方法 -- ID3、C4.5、C5.0
由于篇幅有限，这里只解释原理，感兴趣的朋友可以自行学习更详细的公式计算方法～
1、ID3算法 -- 基于信息增益
ID3算法是最传统的决策树划分方法，计算每个特征的信息增益，选择信息增益最大的节点作为根节点（老大），然后在剩余的节点中找出信息增益最大的节点（老二），依次类推，最终生成整棵树....
仍然以西瓜数据集为例，有色泽、根蒂、脐部、敲声、纹理和触感6个特征，依据数据选择最大的信息增益特征作为根节点，然后依次选择生成整棵树。
2、C4.5算法 -- 基于信息增益率
信息增益算法虽然能一定程度上帮助判断信息量的大小，但是在计算时更偏向于数量多的特征（极端假设色泽中青绿特征有10000个，乌黑和浅白特征分别只有1个，这种情况下特征选择更偏向于特征多的属性），为了解决这种问题才有了信息增益率的算法，信息增益率的计算公式为：
IV为属性a的固有值，属性a取值数目越多(V越大) ,则 IV(a) 的值通常越大。
信息增益率为该特征的信息增益除以该特征本身的信息熵，即考虑了特征本身的信息熵大小，可以有效避免ID3算法存在的问题，但是, 需要注意的是增益率准则对可取值数目较少的属性有所偏好,信息增益对可取值数目多的属性有所偏好, 折中一下可以先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
3、CART算法 -- 基于Gini指标
C4.5算法在ID3算法的基础上解决了诸多问题，但是以上两种算法均只适用于分类，而且需要一直对各个分支进行熵计算导致计算量极大，为了解决这些问题就有了基于Gini指标的算法：
基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。
三、python实战
数据来自kaggle平台，共有10个字段14999条记录。 数据主要包括影响员工离职的各种因素（员工满意度、绩效考核、参与项目数、平均每月工作时长、工作年限、是否发生过工作差错、5年内是否升职、部门、薪资）以及员工是否已经离职的对应记录，根据此数据预测员工是否会离职。字段说明如下图所示：
3.1 数据探查
3.2 数据预处理
1、数据转化
数据中的薪资水平（salary）为定序变量, 因此将其字符型转化为数值型；部门（department）为定类型变量, 需要对其进行one-hot编码处理。
2、数据量处理
因变量存在严重不均衡的情况，因此需要筛选一部分数据保持数据的均衡：
3.3 决策树建模
这里使用sklearn对数据进行建模～
1、区分X与y
2、划分训练集与测试集
3、找到合适的树深
4、建模
5、筛选重要特征
影响员工离职与否最重要的四个的特征为满意水平、最近绩效、平均每月工作时长、工作年限，再看一下这几个特征与是否离职的相关性：
其中，满意度、最近绩效与是否离职负相关（也就是说，满意度越低、最近绩效越差员工越倾向于离职），平均每月工作时长、工作年限与是否离职正相关（也就是说，每月工作时长越长、工作年限越长越倾向于在职）。
3.3 决策树可视化
这里使用的是graphviz工具对决策树可视化，感兴趣的朋友可以自行安装一下～
解释一下graphviz生成的决策树：
从根节点开始，该决策树共有6056个样本，划分为在职和离职两个类别，其中离职3217个，在职2839个样本，离职样本大于在职数，决策树认为该节点属于离职，gini系数为0.498（几乎没有排除任何干扰）；从根节点向左分支，当满意水平<=0.465且工作年限<=4.5时，离职在职的样本量分别为445和2028，决策树认为属于在职，且gini值为0.295，小于根节点的0.498，分类结果更加确定。依次类推可以对整棵树进行解释。
以上就是我对决策树的理解及代码实现，需要「员工离职数据」的朋友欢迎加我微信「follow_a_select」获取～
The e
投递蚂蚁集团等公司10个岗位 >