决策树

什么是决策树?

定义在特征空间与类空间上的条件概率分布,决策树实际上是将特征空间划分成了互不相交的单元,每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中,哪个类别有较高的条件概率,就把该单元中的实例强行划分为该类别。

if-then的集合,该集合是所有从根节点到叶节点路径的集合。

优点?

可解释性强,速度快。

可以处理离散、连续数据。

如何学习一颗决策树?

缺点?

容易过拟合,忽略属性之间的相关性,数据不平衡时会分错。

如何学习一颗决策树?

本质上就是从训练数据集中总结出一套分类规则,具有较强的泛化能力。损失函数通常是正则化的极大似然函数,学习的策略是以损失函数为目标函数的最小化。

递归调用选择特征,将选到的特征左右切分点将数据集进行划分特征空间,构建出决策树。

递归终止条件?

所有数据基本被正确分类,或者没有了可用的特征,或者设定的特征的信息增益的阈值。

什么是剪枝?

根据训练集生成的决策树往往都比较复杂,导致泛化能力较弱。实际的决策树学习中,会将已经生成的决策树进行简化,提高泛化能力。具体就是减掉一些子树或叶节点,将根节点作为新的的叶节点。

剪枝方法?

不管是一般剪枝算法还是CART剪枝算法,都基于同一个思想,即减小决策树模型的整体损失函数。

1、一般的剪枝方法

![]()

α:权衡因子,预先给定

T:子节点的个数

C(T):预测误差

核心步骤是:假设剪枝前Cα(TB)后Cα(TA),其对应的损失函数值分别是Cα(TB)与Cα(TA),如果Cα(TB) <= Cα(TA),则进行剪枝,将父节点变为新的叶节点。递归地进行以上步骤,知道不能继续为止,得到损失函数最小的子树Tα。动态规划来实现这算法。

2、cart剪枝

优势在于不用提前设置α,在剪枝的同时能够找到最优的值。

![]()

Tt代表以内部节点t为根节点的子树。

这样计算出的值表示剪枝后整体损失函数减少的程度。

选择g(t)值最小的内部节点t进行剪枝,得到一棵新树T_g(t)。然后,对这棵新树继续上面的剪枝过程,又得到一棵新树。如此,一直到单节点树,可以得到一系列的树,它们互相嵌套。

用交叉验证法从中选出最优的子树Tg(t),它对应的α值为g(t)。

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。