手把手教你推导决策树算法
最后更新：2020-06-09 10:06:16 手机定位技术交流文章
作者:阿伦·莫汉
翻译:杨怡园
校对:王琦
这篇文章的长度是2000字，建议阅读5分钟。
本文介绍了决策树算法和机器学习中常用的相关术语，并基于天气数据集手工推导了决策树算法(ID3，CART算法)的实现过程。
标签:机器学习
决策树是最重要的机器学习算法之一，可用于分类和回归问题。在本文中，我们将介绍分类部分。
什么是决策树？
决策树是一种具有树形结构的分类和预测工具，其中每个内部节点代表属性测试，每个分支代表测试结果，每个叶节点(终端节点)有一个类别标签。
上图是一棵小决策树。决策树的一个重要优势是它的高度可解释性。在上图中，如果身高大于180厘米或小于180厘米，体重大于80公斤，则为男性，否则为女性。你有没有想过我们如何得到一个类似于上面显示的决策树？我将使用天气数据集来解释这一点。
在此之前，我将解释一些相关的术语。
熵在机器学习中，熵是对正在处理的信息的随机性的度量。熵值越高，就越难从这些信息中得出结论。
信息增益信息增益可以被定义为通过观察另一个随机变量由随机变量或信号获得的信息量，它可以被认为是父节点的熵和子节点的加权平均熵之差。
基尼纯度基尼纯度是一种测量方法。如果数据是根据标签在子集中的分布随机标记的，基尼系数用于衡量从集合中随机选择的错误标记数据的频率。
基尼系数的下限是0。如果数据集只包含一个类别，那么基尼系数为0。
有许多算法可以构建决策树。它们是:
1.Cart(分类回归树):基尼系数作为衡量标准；
2.ID3(迭代二分法3):熵和信息增益被用作测量标准。
本文将介绍ID3算法。一旦您理解了ID3，您就可以轻松地使用CART来实现相同的功能。
用ID3算法分类
接下来，我们将根据天气数据集决定是否踢足球。
这里，自变量将决定因变量。其中，自变量为天气预报(展望)、温度、湿度和风，因变量为是否踢足球(是/否)。
首先，我们必须找到决策树的父节点。为此，有以下步骤:
1.计算类别变量(即因变量)的熵。
E(S) = -
2.现在我们需要计算加权平均熵，即我们为每个特征计算的权重之和乘以概率。
E(S，展望)= (5/14)*E(3，2) + (4/14)*E(4，0) + (5/14)*E(2，3) = (5/14)(-(3/5)日志(3/5)-(2/5)日志(2/5))+ (4/14)(0) + (5/14)((2/5)日志(2/5)-(3/5)日志(3/5)) = 0.693
下一步是计算信息增益，即父节点的熵和我们上面计算的加权平均熵之间的差值。
IG(S，前景)= 0.94 - 0.693 = 0.247
类似地，计算温度、湿度和风的信息增益。
IG(S，温度)= 0.940 - 0.911 = 0.029
IG(S，湿度)= 0.940 - 0.788 = 0.152
风力= 0.940 - 0.8932 = 0.048
现在选择熵增益最大的特征。天气预报(outlook)以最大熵增益为特征，因此它形成决策树的第一个节点(根节点)。
现在我们的数据如下:
因为当天气预报(展望)以阴天为特征时，因变量的结果只有“是”的类别，所以我们可以将其设置为“是”。这意味着如果天气预报(展望)的特点是多云，我们可以踢足球。现在我们的决策树如下。
接下来，在决策树中找到下一个节点。在晴天我们会找到一个节点。我们需要确定谁在温度、湿度或风力方面拥有更高的信息增益。
计算父节点的熵E(晴天):
e(晴天)= (-(3/5)对数(3/5)-(2/5)对数(2/5)) = 0.971
计算温度的信息增益ig(晴天，温度):
E(晴天，温度)= (2/5)*E(0，2) + (2/5)*E(1，1) + (1/5)*E(1，0)=2/5=0.4
现在计算信息增益:
IG(晴天，温度)= 0.971–0.4 = 0.571
同样，我们可以得到:
IG(晴天，湿度)= 0.971
IG(晴天，刮风)= 0.020
这里是最大值。因此，湿度是晴天的一个子节点。
对于上表中的湿度，如果湿度正常，因变量为“是”；如果湿度高，因变量为“否”。类似于上面的方法，我们可以找到雨的子节点。
注意:熵大于0的分支需要进一步拆分。
最后，我们可以得到以下决策树:
CART算法用于分类
使用CART的分类过程类似于ID3算法，但是它使用基尼杂质而不是熵作为测量标准。
1.第一步，我们需要找到决策树的根节点，所以我们需要计算因变量的基尼系数。
基尼系数(S) = 1 -
基尼系数(S，前景)= (5/14)基尼系数(3，2)+(4/14)*基尼系数(4，0)+(5/14)*基尼系数(2，3)=(5/14)((3/5)-(2/5))+(4/14)* 0+(5/14)((2/5)-(3/5))= 0.171+0.171 = 0.342
基尼系数增量(S，前景)= 0.459 - 0.342 = 0.117
基尼系数(S，温度)= 0.459 - 0.4405 = 0.0185
基尼系数增益(S，湿度)= 0.459 - 0.3674 = 0.0916
基尼系数增益(S，风)= 0.459 - 0.4286 = 0.0304
我们需要选择基尼系数增益最高的特征，而outlook的基尼系数增益最高，因此我们可以选择它作为我们的根节点。
现在，您应该知道如何进行下一个操作，即重复ID3算法中的相同步骤。
决策树的优缺点
优势:
决策树是高度可解释的；几乎不需要数据预处理；适合低延迟应用。缺点:
噪声数据可能拟合过度。决策树越深，噪声导致过度拟合的可能性就越大。一个解决方案是修剪决策树。参考:
1.https://www.saedsayad.com/decision_tree.htm
2.应用人工智能课程
原始标题:
实例操作的决策树算法
原始链接:
https://medium . com/data drivininvestor/决策树-算法-实践-示例-e6c2afb40d38
艺术经纬:黄
校对:林一林
译者简介
杨一元毕业于清华大学自动化系，毕业于华中科技大学实验班，主修工业过程测试中的人工智能算法。我对“人工智能+”特别感兴趣，因为我喜欢唱歌和接触新事物。作为简历和数据挖掘的初学者，我希望接触到更多不属于我研究领域的东西，拓宽我的知识面。
-完毕-
为了在数据科学领域获得更多相关发展，我们诚挚邀请您关注清华-青岛数据科学研究所官方微信公众平台“数据派THU”。
本文由 在线网速测试 整理编辑，转载请注明出处。
