决策树基本概念

77 阅读 0 评论 51 点赞

我是靠谱客的博主知性星月，最近开发中收集的这篇文章主要介绍决策树基本概念，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、决策树概念

决策树是一种机器学习的方法。决策树的生成算法有ID3, C4.5和C5.0等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。
决策树是一种十分常用的有监督学习分类方法。

决策树的生成主要分以下两步，这两步通常通过学习已知分类结果的有标签样本来实现。

节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择将这一节点分成2个子节点（如不是二叉树的情况会分成n个子节点）
阈值的确定：选择适当的阈值使得分类错误率最小（Training Error）。

决策树的构建过程是一个递归过程。函数存在三种返回状态：（1）当前节点包含的样本全部属于同一类别，无需继续划分；
（2）当前属性集为空或者所有样本在某个属性上的取值相同，无法继续划分；
（3）当前节点包含的样本集合为空，无法划分。

二、决策树分类

比较常用的决策树有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。下面介绍具体步骤。
（1）ID3
ID3: 由增熵（Entropy）原理来决定那个做父节点，那个节点需要分裂。对于一组数据，熵越小说明分类结果越好。熵定义如下：

Entropy＝- sum [p(xi) * log2(P(xi) ]，其中p(xi) 为xi出现的概率。

假如是2分类问题，当A类和B类各占50%的时候，Entropy = - （0.5log_2( 0.5)+0.5log_2( 0.5))= 1
当只有A类，或只有B类的时候，Entropy= - （1*log_2( 1）+0）=0

所以当Entropy最大为1的时候，是分类效果最差的状态，当它最小为0的时候，是完全分类的状态。因为熵等于零是理想状态，一般实际情况下，熵介于0和1之间。熵的不断最小化，实际上就是提高分类正确率的过程。决策树算法其实就是为了找到能够迅速使熵变小，直至熵为0的那条路径，这就是信息增益的那条路。

（2）C4.5
C4.5：通过对ID3的学习，可以知道ID3存在一个问题，那就是越细小的分割分类错误率越小，所以ID3会越分越细，分割太细了，训练数据的分类可以达到0错误率，但是因为新的数据和训练数据不同，所以面对新的数据分错率反倒上升了，也就形成了过拟合（Overfitting）。决策树是通过分析训练数据，得到数据的统计信息，而不是专为训练数据量身定做。

所以为了避免分割太细，C4.5对ID3进行了改进，C4.5中，优化项要除以分割太细的代价，这个比值叫做信息增益率，显然分割太细分母增加，信息增益率会降低。除此之外，其他的原理和ID3相同。

（3）CART:分类回归树
CART是一个二叉树，也是回归树，同时也是分类树，CART的构成简单明了。
CART只能将一个父节点分为2个子节点。CART用GINI指数来决定如何分裂：
GINI指数：总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）。

CART还是一个回归树，回归解析用来决定分布是否终止。理想地说每一个叶节点里都只有一个类别时分类应该停止，但是很多数据并不容易完全划分，或者完全划分需要很多次分裂，必然造成很长的运行时间，所以CART可以对每个叶节点里的数据分析其均值方差，当方差小于一定值可以终止分裂，以换取计算成本的降低。CART和ID3一样，存在偏向细小分割，即过拟合的问题。