赞
踩
决策树(decision tree):是一种基本的分类与回归方法,此处主要讨论分类的决策树。
在分类问题中,表示基于特征对实例进行分类的过程,可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树通常有三个步骤:特征选择、决策树的生成、决策树的修剪。
用决策树分类:从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点,此时每个子节点对应着该特征的一个取值,如此递归的对实例进行测试并分配,直到到达叶节点,最后将实例分到叶节点的类中。
下图为决策树示意图,圆点——内部节点,方框——叶节点
决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数:正则化的极大似然估计函数
决策树学习的测试:最小化损失函数
决策树学习的目标:在损失函数的意义下,选择最优决策树的问题。
特征选择 ——> 决策树的生成 ——> 决策树的剪枝
特征选择:熵、条件熵、信息增益、信息增益比、基尼指数
决策树的生成:ID3、C4.5、CART
决策树的剪枝:预剪枝、后剪枝
特征选择在于选取对训练数据具有分类能力的特征,这样可以提高决策树学习的效率。
在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。熵越大,随机变量的不确定性就越大。
设X是一个取有限个值的离散随机变量,其概率分布为
则随机变量X的熵定义为
熵只依赖于X的分布,与X的取值无关,所以也可以将X的熵记作
条件熵(conditional entropy)表示在已知随机变量X的条件下随机变量Y的不确定性,定义为X 给定条件下Y 的条件概率分布的熵对X 的数学期望:
当熵和条件熵中的概率是通过训练集得到时,所对应的熵与条件熵分别称为经验熵和经验条件熵
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
信息增益的算法:
以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题 ,所以引入了西信息增益比问题。
当特征的可取值个数较大时,较大,那么信息增益比较小,因此信息增益比倾向于选择可取值个数较小的特征,解决了采用信息增益进行特征选择时面临的过拟合问题。
对于分类任务而言,基尼指数越小,对应特征对训练样本的分类能力越强。
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。
具体办法:
从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再对子节点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止,最后得到一颗决策树。
C4.5算法与ID3算法类似,C4.5算法对ID3算法进行了改进。C4.5算法在生成的过程中,用信息增益比来选择特征。
首先剪枝(pruning)的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。
决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):
预剪枝就是在决策树生成过程中提前停止树的增长的一种剪枝算法。主要思路是在决策树结点分裂之前,计算当前结点划分能否提升模型泛化能力,如果不能,则决策树在该结点停止生长。
后剪枝就是先构造一颗完整的决策树,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。
对比预剪枝和后剪枝,能够发现,后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情形下,后剪枝决策树的欠拟合风险小,泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的,并且要自底向上的对树中的所有非叶结点进行逐一考察,因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
优点:
1、决策树算法易理解,机理解释起来简单。
2、决策树算法可以用于小数据集。
3、决策树算法的时间复杂度较小,为用于训练决策树的数据点的对数。
4、相比于其他算法智能分析一种类型变量,决策树算法可处理数字和数据的类别。
5、能够处理多输出的问题。
6、对缺失值不敏感。
7、可以处理不相关特征数据。
8、效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。
缺点:
1、对连续性的字段比较难预测。
2、容易出现过拟合。
3、当类别太多时,错误可能就会增加的比较快。
4、在处理特征关联性比较强的数据时表现得不是太好。
5、对于各类别样本数量不一致的数据,在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。