决策树
简单理解决策树
决策树是一类常见的机器学习方法，和我们人类在进行问题决策时一样，决策树基于树的结构进行决策。例如对于西瓜来说，我们要对“这是好瓜吗”进行决策，通常我们会先进行一些判断：西瓜颜色、根蒂形态、敲打声音等等，最终得到决策后的结果：好瓜or坏瓜。
如下图简单展示关于西瓜分类问题的一颗决策树：
很显然，决策的最终过程也就对应着我们最终想要得到的结果，
决策树的概念
通常情况下我们用到的决策树都是在分类模型中，本文中我们也只讨论一下分类分类问题。
决策树的定义：分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点和有向边组成，节点有两种类型：内部节点和叶子结点，内部结点表示一个特征或属性，叶结点表示一个类，一般的一棵决策树包含一个根节点（最顶部的内部结点）若干个内部结点和若干个叶子结点。
简单的用if-then来说一下，决策树可以看作是一个if-then规则的集合，if用来表示属性（特征），then用来表示分类结果，简单的结构图如下所示：
决策树的划分
我们了解了决策树的结构却不知道具体的一颗决策树是怎样去生长，怎样去选择根结点和每一个内部结点的，下面再让我们来了解一下决策树的划分方式。
信息增益
在构造决策树之前，根据树形结构我们考虑在进行分类的时候哪个特征起到了更重要的作用，这样的特征我们是不是应该把它放在更重要的位置呢，又要怎样去确定一个特征是否重要呢？这个时候信息增益就起到了很大的作用。
让我们先从熵说起。
熵
熵通常出现在信息论和概率统计中，通常用来度量随机变量的不确定性。
设X是一个取有限个值的离散型随机变量，其概率分布为：
则随机变量X的熵为：
根据上式我们可以看到式子中并没有涉及到X的取值，而是涉及到了X的分布，所以我们可以认为熵只和X的分布有关，是和X的取值无关的，所以我们也可以把熵的式子定义成：
对于伯努利分布来说，H ( p ) 随概率P的变化如下图所示：
根据图像可以知道，当P=0和P=1时，H ( p ) = 0 ，随机变量完全没有不确定性，而当P=0.5时，H ( p ) = 1 ,随机变量的不确定性最大。举个例子来说就是当我们抛一个两面都一样的硬币时，可以得到的结果是确定的，而抛正常的硬币时，是完全随机的，也就是不确定性很大，此时熵也是最大的。
条件熵
条件熵H(Y|X)表示的是在已知随机变量X的情况下，随机变量Y的不确定性，条件熵的定义如下：
信息增益
信息增益表示的是得知X的信息而使得类Y的信息不确定性减少的程度。
定义：特征A对训练数据集D的信息增益Gain(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
通常情况下我们把熵和条件熵的差称作为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。
当我们进行特征选择的时候对训练数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。
决策树生成（ID3算法）
ID3算法就是在信息增益的基础上使用信息增益来选择特征，递归的来构建决策树。
主要方法
从根节点开始，对节点计算所有可能特征的信息增益，选择信息增益最大的特征作为节点的特征，并且由该特征取不同的值来建立子节点，再对子节点递归调用上述方法来构建决策树，知道所有的信息增益都变得很小或者没有特征可以选择的时候，得到最终的决策树。
算法步骤
输入：训练数据集D，特征集A，阈值ε；
输出：决策树T.
ID3示例
光看概念和步骤难免会有些抽象，让我们通过一个例子来看一下ID3的具体计算和树的生成过程。
下表是西瓜书中的西瓜数据集2.0，该数据集中包含17个训练样例，用来学习预测一个没切开的瓜是不是好瓜。很显然这是一个二分类问题。
在决策树开始构建之前，我们先看一下正例和反例所占的比例：
然后我们需要计算出当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每一个属性的信息增益。
以属性“色泽”为例，他有三个取值：{青绿、乌黑、浅白}，若使用该属性对D进行划分，则可得到三个子集，分别记为D1（色泽=青绿），D2（色泽=乌黑），D3（色泽=浅白）。根据上表我们可以得到如下的信息：
数据集D1：{1、4、6、10、13、17}，正例p1=3/6，反例p2=3/6
数据集D2：{2、3、7、8、9、15}，正例p1=4/6，反例p2=2/6
数据集D3：{5、11、12、14、16}，正例p1=1/5，反例p2=4/5
我们可以计算他们对应的信息增益如下：
对应的对于属性“色泽”的信息增益有：
类似的我们可以算出其他属性的信息增益如下：
很显然，纹理的信息增益最大，那么我们就选择它为划分属性，得到的结果如下：
对于每一个结点，我们又可以计算其余特征的信息增益进行划分，如此递归可以得到最终的决策树如下：
###信息增益率
根据信息增益的概念我们会发现，随着数据量的增大，信息增益会偏向取值较多的特征，使用信息增益率可以对这一问题进行校正。
定义：特征A对训练数据集D的信息增益比GainRatio(D,A)定义为其信息增益Gain(D,A)与训练数据集D的经验熵H(D)之比，即：
这里的Gain也就是我们的信息增益了，而H(D)也就是对应的熵了。
基于信息增益率我们有对应的算法叫做C4.5算法，需要注意的是，增益率可以对取值数目较少的属性，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式（先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的）
