经典机器学习方法(二):决策树原理解析
决策树简介
决策树,是一项十分经典的机器学习的方法,是一类通过对训练数据进行划分而得到的树结构,通过对原有训练数据划分而对现有需要预测样例进行判断预测阶段其实与if/else判断类似 举个栗子,如果我们现在得到的西瓜数据集如下:
其对应每一个样例,都有色泽,根蒂等特征,那么通过划分这些特征,我们就可以依据这个训练数据集生成对应的决策树:
那么问题来了,如何去选择对应的特征来生成对应的决策树呢?
特征选择
对于决策树特征选择来说一般都是采用贪心的方法来进行选择特征,例如如上的训练数据集在每一次划分节点时,都按照“色泽->根蒂->敲声…”的从左到右的顺序去判断对应的划分节点.
划分指标
那么既然已经定了对应的特征的选择的次序,怎么评判对应划分后的好坏呢?
ID3决策树
这里我们引入一个信息熵的概念,用这个指标也就可以对于我们划分后的数据集的纯度进行评判(也就是我们数据集中属于同一类的数据有多少).公式如下:
因此,只要求划分后我们的数据集纯度越高,则表明我们的划分特征也就越好.自然而然的,划分前有一个信息熵,划分后又有一个信息熵,为了便于比较,我们把每一次划分使得数据集纯度提升的多少,称为信息增益,公式如下:
对应的,我们还是举一个简单的栗子,还是使用原先的数据集:
首先我们先计算没有划分前的信息熵的值为多少,运用小学二年级一通运算后,我们得到如下的数值:
然后我们采用色泽先划分,因为色泽一共有三个青绿，乌黑，浅白三个特征,因此很自然的分成了三个部分,其好瓜样本占属性样本比例分别是3/6，4/6，1/5。坏瓜样本占属性样本比例分别是3/6，2/6，4/5。则根据信息熵公式得到：
然后再根据信息增益的公式可以得到:
同理,我们还需要对根蒂,敲声等特征再进行计算,最后留下对应的信息增益最大的方法.
很容易可以看到最大的就是纹理,因此我们采用纹理作为我们最后的划分特征,从而得到:
同理只要一直这样划分,就可以得到对应的最后的决策树啦,需要注意的是,之前采用过的划分特征,在其子节点的划分过程中,是不可以采用的哦.
C4.5决策树
由于权重的存在，信息增益其实对包含数目较多的属性有偏好。为了减少这种不“客观”的判定，可以选择”增益率“(C4.5)来划分属性,其实说白了也就是对信息增益除以一个属性的数目,从而减小对应的影响:
IV(a)计算的其实就是每一个划分后的数据集的大致比例.
CART决策树
当然了,你也可以采用另外指标如基尼指数来对树进行划分.具体的公式如下:
基尼指数,主要是对同一个集合中,不同样例多少,即非纯度的一个评价,跟信息熵正好相反.其他的划分过程则依旧不变.
总结来说,目前绝大多数的决策树采用的CART的决策树,而且效果一般要比ID3和C4.5的决策树要好.
决策树剪枝
由于决策树是对训练数据集直接划分得到的,因此十分容易造成过拟合的情况,所以我们还需要对决策树进行适当的剪枝来减小模型的复杂度,
预剪枝
预剪枝的思想很简单,即当我们采用的指标没有获得较大的提升,就不在往下划分树了.举一个简单的栗子,例如对于当前划分情况:
当我们计算出来对应根蒂的指标不如不划分之前的指标大小,那么我们就停止划分,进而得到对应的决策树.
后剪枝
后剪枝同预剪枝相反,其在树生成完之后再对整棵树进行剪枝.依旧举个小栗子,假如最后分的决策树如下:
然后我们通过计算得到,根蒂的划分反而降低了指标值,因此将根蒂的划分裁掉,从而得到最后的决策树:
总结
限于篇幅的原因,只是简单的介绍了决策树的大概内容,至于对应的决策树如缺失值的处理,预剪枝后剪枝的优缺点等都没有详细概要的介绍,期望大家可以自己学习一下啦.