机器学习之决策树：一、算法原理
目录
一、算法介绍
决策树(Decision tree)是一种基本的分类与回归算法，本次博客只讨论用于分类的决策树。
决策树，顾名思义，是一种基于树结构的决策选择模型，表示基于特征对实例分类的过程。它可以认为是if-then的规则集合，也可以认为是特征空间上的条件概率分布。决策树依据对某种特征的满足与否进行子集划分，整棵树的节点分为内部节点和叶子节点，内部节点对应作为划分依据的特征，叶子节点表示满足从根节点到该叶子节点路径上所有属性要求的实例的分类。
如下图所示（圆表示内部节点，方框表示叶子节点）：
规定决策树的左子树表示满足父节点的要求，右子树表示不满足。如上图所示，第一象限的点表示满足X>0为真并且满足Y>0为真，即满足从根节点到该叶子节点路径上的所有要求， 最终确定了象限分类。
二、概念介绍
2.1、信息熵
熵是由被评为20世纪最聪明的人之一的克劳德·香农提出的。作为信息论的创始人，有人这样评价他，“贝尔实验室和MIT的很多人将香农与爱因斯坦相提并论，但有些人认为这是不公平的——对香农不公平。”
熵是用来衡量信息的不确定程度的物理量，熵的值越大，信息的混乱程度就越大，熵的值越小，信息的混乱程度就越低。
设离散变量X的概率分布为：
那么随机变量X的熵定义为：
此处log的底一般为2或者自然对数e，本博客中取e作为底，熵的单位为bit，若p=0,那么认为plogp=0。
上图的信息熵为:
上图的信息熵为:
通过观察可知，第一幅图要比第二幅图X的取值种类更多，也就更混乱，经计算所得的熵也要大。
2.2、信息增益与信息增益率
在给定的数据集中，我们用频率来代替概率，所以在计算数据集的熵之前，需要统计频率。
用频率代替概率后，熵可用此公式计算：
其中Ck表示第K类出现的次数，D表示总样本数。
对数据集D的某个特征A的经验条件熵：
计算信息增益为：
信息增益率的定义为特征A对数据集D是增益与训练集D关于特征A的值的熵之比：
其中
2.3、基尼系数
对于给定的样本集D来说，基尼系数定义为：,
对于样本集D是特征A来说，
基尼系数与熵类似， 数值越小代表混乱程度越小。
三、决策树的优缺点
优点：计算复杂度不高，输出结果易于理解，容易可视化，对中间值缺失不敏感，可以处理不相关的特征数据，对特征数据的尺度差距不敏感。
缺点：可能会导致过度匹配，即过拟合，泛化能力差。
四、决策树的剪枝
决策树的剪枝分为预剪枝和后剪枝。预剪枝是指在决策树的构建过程中，一边构建一边剪枝，对于不满足阈值的父节点直接当作叶子节点。后剪枝是指决策树建立好后，根据损失函数对决策树进行剪枝。
设树T的叶节点个数为|T|，t是树的叶节点，该叶节点有Nt个样本点，其中K类样本点有Ntk个，k=1,2,3...K，Ht(T)表示叶节点t的经验熵，α为大于零的数，则决策树的损失函数为：
其中，C(T)表示模型对训练数据的预测误差，即所谓的训练误差：
其中Ht(T)为经验熵，公式为：
故损失函数的最终形式为：
当α较小时，比较注重模型与数据的拟合程度，而不注重模型的复杂度。当α较大时，比较注重模型的复杂度而不太注重模型与数据的拟合程度。α代表了对两者的权衡，这也是对训练误差与泛化能力的权衡。过于追求模型复杂度和训练误差小，会导致模型的泛化能力降低，决策树要尤其关注这一点。
五、决策树的构建算法
ID3 C4.5 CART
决策树的构建算法包括以信息增益为基准的ID3算法和以信息增益率为基准的C4.5算法和以基尼系数为基准的CART算法。其中C4.5时ID3算法的改进，因为以信息增益为基准的ID3算法更偏向于选取特征的取值多的，而C4.5将信息增益率即信息增益除以特征的熵作为基准，可以一定程度上避免。
CART算法还有一个重要的改进就是ID3和C4.5是树结构但不一定是二叉树，这取决于某一特征的取值，而CART算法构建的是严格的二叉树结构，这样可以使模型更加简单。比如特征Age的取值包括：{“young”“mid-age”“senior”},那么最终Age的分支包括三种可能：{“young，mid-age”，“senior”}、{“young”“mid-age，senior”}和{“young，senior”，"mid-age"}。最终取三种组合中基尼系数最小的二叉树分叉的决策点。
下面我们将以ID3算法为例，构建一个树模型，数据集如下：
该数据集的信息熵为：
首先求年龄的经验条件熵：
Gain(age)=0.94-0.694=0.246 bits
同理可求：
Gain(income)=0.029bits Gain(student)=0.151bits Gain(credit_rating)=0.048bits
所以根节点为年龄，接下来把按照young、mid-age、senior划分的子集作为一个新的数据集，继续进行上述过程，直到得到所有叶节点。