决策树
一、决策树原理
（参考文献：周志华《机器学习》清华大学出版社）
决策树使用类似流程图是树形结构对样本进行分类。一般地，一颗决策树包含一个根节点、若干内部节点和若干叶子节点。非叶子节点对应于一个属性的测试，叶子节点对应于决策结果。从树的根节点（包含样本全集）开始，从属性集中选择一个属性测试，然后按照给定实例的属性值确定对应的分支，根据属性测试的结果将样本分到对应的子结点中，使用过的属性从属性集中去掉。不断重复该过程，直到满足以下3种情况结束递归返回结果：①当前结点包含的样本属于同一类，无需继续划分，将该结点标记为叶子节点；②属性集为空，或者样本在属性集的所有属性上取值一样，无法继续划分；将当前结点设为叶子结点，类别设定投票进行（那个类别的样本最多就设为那个类别）；③当前结点包含样本数为0；将当前结点标记为叶子结点，类别设定由其父节点投票决定（父节点那个类别的样本最多就将该节点设为那个类别）。
算法关键之一：如何选择最优的划分属性，下面介绍几种常见的算法。
二、ID3算法
（该部分转载自：https://www.cnblogs.com/starfire86/p/5749328.html）
ID3算法，即Iterative Dichotomiser 3，迭代二叉树3代，是J R Quinlan提出的一种决策树算法。特点是引入信息论中互信息的概念，他将之称为信息增益（information gain），以它作为属性选择的标准。
在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。在认识信息增益之前，先来看看信息熵的定义熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
假如一个随机变量的取值为
，每一种取到的概率分别是
，那么
的熵定义为
对于分类系统来说，类别是变量，它的取值是
，而每一个类别出现的概率分别是
而这里的就是类别的总数，此时分类系统的熵就可以表示为
下面介绍信息增益。信息增益是针对一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。
接下来以天气预报的例子来说明。下面是描述天气数据表，学习目标是play或者not play。
可以看出，一共14个样例，包括9个正例和5个负例。那么当前信息的熵计算如下：
在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用属性Outlook来分类，那么如下图：
划分后，数据被分为三部分了，其中各个分支的信息熵计算如下：
那么划分后的信息熵为：
表示系统在特征属性
的条件下样本的条件熵。那么最终得到特征属性
带来的信息增益为：
于是我们可以总结信息增益的计算公式如下：
其中为全部样本集合，
是属性
所有取值的集合，
是
的其中一个属性值，
是
中属性
的值为
的样例集合，
为
中所含样例数。
在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性。以上就是ID3算法的核心思想。
ID3算法信息增益的缺点选择属性时偏向于选择取值多的属性。比如，假设在上面列子中加入一个日期属性（如，3月1号），则ID3算法会选择该属性，并一步到位将所有样本划分好，但是这没有意义。C4.5算法对此进行了改进，下面介绍该算法。
C4.5算法
首先，我们介绍“分裂信息”(split information)的概念。
属性A的“分裂信息”(split information)：
其中，训练数据集S通过属性A的属性值划分为m个子节点，|Sj|表示第j个子节点中样本数量，|S|表示划分之前数据集中样本总数量
例如，本文例子中“outlook”的分裂信息为：
SplitInfo(S) = - 5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.5774
|S分裂之后样本集的信息增益率：
通过属性A分裂之后样本集的信息增益率：
则，本文例子中“outlook” 的信息增益率为：
InfoGainRation(S,A) = Entropy(S) / SplitInfo(S) = 0.24675 / 1.5774 = 0.1564
。