本文介绍了 ID3,C4.5,CART三种基本的决策树模型。首先介绍了决策树的特征选择,包括信息增益,信息增益率、基尼指数、最小均方差分别对应分类树ID3、C4.5、CART、回归树CART。然后介绍了决策树建树的一般流程、对比分类树和回归树建树的区别。最后介绍了树模型中避免过拟合问题的剪枝方法,包括前剪枝和后剪枝。
作者 | 文杰
编辑 | yuquanle
决策树是一种基本的分类和回归方法,用于分类主要是借助每一个叶子节点对应一种属性判定,通过不断的判定导出最终的决策;用于回归则是用均值函数进行多次二分,用子树中数据的均值进行回归。
决策树算法中,主要的步骤有:特征选择,建树,剪枝。接下来将介绍三种典型的决策树算法:ID3,C4.5,CART。
优点:
缺点:
对于决策树而言,每一个非叶子节点都是在进行一次属性的分裂,选择最佳的属性,把不同属性值的样本划分到不同的子树中,不断循环直到叶子节点。其中,如何选择最佳的属性是建树的关键,决策树的一个特征选择的指导思想是熵减思想。
常见的选择方式有ID3的信息增益,C4.5的信息增益率,CART的基尼指数,最小均方差。这里分别介绍这ID3,C4.5,CART决策树的特征选择标准
为了更清楚的理解信息增益这个概念,我们需要先来了解下信息论中的信息熵,以及条件熵的概念。
熵是一种对随机变量不确定性的度量,不确定性越大,熵越大。
假设离散随机变量的概率分布为,则其熵为:
其中熵满足不等式。
在进行特征选择时尽可能的选择在属性确定的条件下,使得分裂后的子集的不确定性越小越好(各个子集的信息熵和最小),即的条件熵最小。
其中是表示属性取值为构成的子集。
信息增益表示的就是在特征已知的条件下使得类别的不确定性减少的程度。即为特征对训练数据集的信息增益为:
用信息增益来进行特征选择,的确可以选择出那些对于类别敏感的特征。
值得注意的是,信息增益没有考虑属性取值的个数的问题。因为划分的越细,不确定性会大概率越小,因此信息增益倾向于选择取值较多的特征。
如对于数据表中主键这样的属性,用信息增益进行属性选择,那么必然会导致信息增益率最大,因为主键与样本是一一对应关系,而这样做分类是无意义的,即信息增益不考虑分裂后子集的数目问题。
信息增益偏向于选择特征值取值较多的特征,而信息增益比通过将训练集关于特征的信息熵作为分母来限制这种倾向。
信息增益比定义为信息增益比上特征的信息熵:
其中。
基尼指数特征选择准则是CART分类树用于连续值特征选择,其在进行特征选择的同时会决定该特征的最优二分阈值。基尼指数是直接定义在概率上的不确定性度量:
可以看出,基尼指数与信息熵的定义极为一致。
最小均方差应用于回归树,回归问题一般采用最小均方差作为损失。在特征选择的同时会测试不同的二分阈值的最小均方误差,选择最有的特征和阈值:
其中是第个模型的回归值。
特征选择准则对比:
由于回归树不存在剩余样本属于一类或者特征用完的情况,所以回归树没有分类树建树前面两步。
分类树和回归树建树区别:
决策树生成算法递归生成的决策树,按照建树的过程直到结束。这样产生的决策树往往对训练集的分类很准确,但是对未知数据却没有那么准确,容易出现过拟合现象。因此,决策树需要借助验证集来进行剪枝处理,防止决策树过拟合。
预剪枝是在构造决策树的过程中,对比属性划分前后决策树在验证集上是否由精度上的提高。由于非叶子节点中的样本往往不属于同一类,采用多数样本标记为该节点的类别进行决策。若划分后的决策树在精度上有提高,则正常分裂,否则进行剪枝。其过程是一个贪心过程,即每一次划分都必须使得决策精度有所提高。
当然也可以对建树进行约束,比如信息增益小于一定阈值的情况或者建树之后其中一个子集的样本数小于一定数量进行预剪枝,统计学习方法书中采用熵加叶子节点树作为损失函数来控制预剪枝。
后剪枝是在决策树建立后以后,自底向上的对决策树在验证集上对每一个非叶子节点判断剪枝前和剪枝后的验证精度,若剪枝后对验证精度有所提高,则进行剪枝。
不同于预剪枝的是,预剪枝是对划分前后的精度进行比较,而后剪枝是对剪枝前和剪枝后的验证精度进行比较,相对于预剪枝,后剪枝决策树的欠拟合风险小,泛化能力优于预剪枝,但时间开销大。
决策树总结
double calcShannonEntOrGini(const DataStr &data, const string &type)
{
unsigned int i;
map<string,double> label_value;//每一类样本的个数统计
double prob=0;
double shannoEnt=0;
double Gini=1;
string label;
for(i=0; i<data.size(); i++)
{
label=data[i][data[0].size()-1];
if(label_value.count(label))
label_value[label]+=1;//如果类别已初始化则在之前的基础上加1
else
label_value[label]=1;//如果类别未初始化,则把当前类别下样本数初始化为1
}
//统计该子数据集上的所有样本的决策属性以及不同决策属性上样本数
for(map<string,double>::iterator it=label_value.begin();it!=label_value.end();it++)
{
prob=it->second/data.size();
shannoEnt-=prob*log(prob);
Gini-=prob*prob;
}
//cout<<"shannoEnt="<<shannoEnt<<endl; //检测信息熵计算是否正确
if(type=="Gini")
return Gini;
if(type=="Ent")
return shannoEnt;
return shannoEnt;
}
完整代码见【https://github.com/myazi/myLearn】