机器学习-决策树

原文链接：https://blog.knoldus.com/2017/08/07/introduction-to-machine-learning-2/)

机器学习是计算机科学中的子领域，目的提供机器在未被编程控制的情况下具有自主学习的能力。(Arthur Samuel, 1959)

目前机器学习是科技领域很火爆的词，尤其大家认为机器人会在未来统治世界或者抢走我们的饭碗，这其实是觉得让人觉得充满挑战，感到迷惑且有着一丝恐惧的。不管我们是否承认，日常生活中智能物品可以帮助我们解决很多问题。

对于机器学习或者终结者中被我们称为天网的东西，一些人们是担心这些会变成现实，同时另外一群人对于AI纪元的新机会新挑战充满了兴趣。比如谷歌的无人驾驶，FB的人脸识别、Amazon的推荐系统、Siri或者Cortana的语音识别，Paypal的欺诈检测等。这里作者从决策树出发简单的介绍机器学习。

机器学习对话图

什么是决策树？

简而言之，决策树可以理解是，每个非叶子节点代表很多种选择，每个叶子节点代表具体的选择结果。

因为预先定义了目标变量，所以决策树是监督学习算法，该算法是可适应于类别型和连续型输入输出的分类模型，决策树是归纳推理中常用且有效的方法。决策树从已有的样本中学习和训练然后预测新样本。

机器学习的流程

决策树的树状示意图

决策树算法(ID3)

ID3是RossQuinlan提出的基于迭代的二叉决策树，它从固定样本中训练出决策树然后引用到预测中。听起来很容易吗？但是如何选择决策树的节点呢？现在下面我们提出一些选择节点的方法。

决策树的形象

熵(Entropy)

在信息论中，熵是用来衡量不确定信息的，它给出了数据集中的无序度。给定一个包含正负样本的集合S，熵的计算公式如下图，其中p+和p-分别代表正负样本。

熵计算公式

按照这个公式计算如下这种情况

如果全是正样本或者全是负样本，S的熵应该是0。

如果一半正样本一半负样本，那么S的熵是1。

所以一个集合的熵应该是[0,1]的。

熵的曲线图

信息增益(Information Gain)

IG是衡量熵的变化幅度，是挑选决策树的选择节点的策略，为了使最后的决策树深度最小，必须选择哪种使熵减少幅度最大的变量作为选择节点。

信息增益计算公式

其中

S是变量A的所有可能值的样本集合

Sv是所有值为v的样本子集合

|Sv|是值为v的样本个数

|S|是所有样本个数