二叉树剪枝_决策树,生成剪枝,CART算法

决策树

1.

原理

1.1

模型简介

决策树是一种基本的回归和分类算法。在分类问题中，可以认为是一系列

if-then

规则的几何。决策树学通常包括三个步骤：特征选择，决策树的生成，

决策树的修剪。

定义：决策树由结点和有向边组成，内部节点表示一个特征和属性，叶子

结点表示一个类。

性质：决策树路径(或者对应的

if-then

规则)具有互斥且完备性：每一个

实例都被一条路径或规则所覆盖，而且只被这条路径或规则所覆盖。

决策树学习：能够正确对数据集进行分类的决策树可能有多个，也可能一

个也没有，我们的目的是找到一个与训练数据集矛盾较小的，同时具有很好泛

化能力的决策树。

特征选择：一种是在决策树学习开始的时候，对特征进行选择，只留下对

训练数据有足够分类能力的特征，一种是在学习过程中对训练数据分割成自己

的时候，选择最优的特征进行分割。

决策树生成：一般这是一个递归的规程。

决策树的剪枝：提高决策树的泛化能力。

1.2

特征选择

特征选择的准则一般是：信息增益和信息增益比

1.2.1

信息增益

a.

信息增益：

信息增益大的特征具有更强的分类能力，

即选择信息增益值大的特

征作为最优特征。

b.

信息熵：表示变量的不确定性(在得知特征

X

的信息时，使得

Y

的信息不确

定性减少的程度)

，熵越大，变量的不确定性越大。设

X

是一个取有限值的离散型

随机变量，其概率分布为：

(

)

i

i

p

X

x

p





则随机变量

X

的熵定义为：

总结

以上是生活随笔为你收集整理的二叉树剪枝_决策树,生成剪枝,CART算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。