文档介绍：决策树的算法
决策树是一种基本的分类与回归方法4在本文中T利用的是分类决策树。决 麓树模型呈树状结构，表不基于特征对实际问题进行分类的过程，结构如下图所 -
7F：
图 10 决策树模型图
从上图可以看到,决策树由“树的节点”和
决策树的算法
决策树是一种基本的分类与回归方法4在本文中T利用的是分类决策树。决 麓树模型呈树状结构，表不基于特征对实际问题进行分类的过程，结构如下图所 -
7F：
图 10 决策树模型图
从上图可以看到,决策树由“树的节点”和“树枝”组成,节点有两种类型:内部结点 和叶结点,分别用圆形和矩形表示,内部结点表示一个特征或属性,叶结点表示一个 类。用决策树解决分类问题,从根结点开始,对实际问题中的某一个特征变量进行检 测判断,根据判断的结果,将某个实例分配到其相应的子结点中,按这样一直分下去,最 终到达其中的某个叶结点,说明该实例属于该节点对应的类［7］。
决策树基本过程
在建立决策树的过程中,基本上可以分为三步:特征选择、决策树的生成、决策 树的剪枝。
(1特征选择
选出对训练数据集有较好分类能力的特征。特征选择一般采用的准则是基尼系 数、信息增益或者信息增益比。
1 先给出熵的定义 ( 熵是表示随机变量不确定性的度量 :
对于一个离散的有限的随机变量 X ,概率分布为
n i p x X P i i ,...,2,1,(=== (8
则 Z=-=n
i i i p p X H 1log (叫做关于 X 的熵。由定义可知熵只依赖于分布 , 而与
X的取值无关,所以也可以把熵记为(p H。下面我们给出条件熵的概念。
Z===n
i i i x X Y H p X Y H 1|(|( (9 经验熵:由已知的数据估计得到的熵。对应的条件熵为经验条件熵。
2信息增益表示得知特征X的信息而使类Y的信息的不确定性减少的程度。
|((,(A D H D H A D g -= (10
为特征A对训练集D的信息增益。
由信息增益的定义可知,信息增益和特征的分类能力呈正比,故利用信息增益来 选择特征的步骤如下:对于训练数据集D，计算每个特征的信息增益，尽量
选取信息增益大的特征,来构建决策树。
在实际应用中，信息增益一般都是用经验熵和经验条件熵的差来近似的，其算法 如下:
设ID I表示样本容量，即样本个数;设有K个类K C ,IK C I表示属于K C的样本个 数。设特征A有n个子集n D D D ,...,,21,Ii D I为i D的样本个数。记子集i D中属 于类K C的样本的集合为ik D,同样Iik D I为ik D样本个数。所以，训练数据集D的 经验熵[8]:
Z=-=K
k k k D C D C D H 12||||log ||||( (11 而特征 A 对数据集 D 的经验条件熵 :
m===-=n i K k i ik i ik in
i i i D D D D D D D H D D A D H 1121||||log ||||||||(|||||( (12 所以信息增益:
|((|(A D H D H A D g -= (13
3 以信息增益当作划分训练数据集的特征的准则 , 存在的问题 : 该准则对于取值 较多的特征有优选考虑