Page 79 - 高中 信息技术 选择性必修4 人工智能初步
P. 79
3.4 决策树
驻留于内存的数据集。在实现过程中，C4.5算法在结构与递归上与ID3完全相同，区别只
在于选取决策特征时的决策依据不同，二者都有“贪心”性质，即通过局部最优构造全局
最优。
（3）CART算法。
CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生
成的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。
3 . 4 . 2 决策树的生成
广东教育出版社
从数据产生决策树的机器学习技术叫作决策树学习。每棵决策树都表述了一种树型结
构，由它的分支来对该类型的对象依靠属性进行分类。决策树学习包含特征选择、决策树
的生成与剪枝过程。决策树学习算法通常采用递归法选择最优特征，并用最优特征对数据
集进行分割。决策树生成时，首先构建根节点，选择最优特征，该特征有几种不同取值就
分割为几个子集，每个子集分别递归调用此方法，返回的就是上一层的子节点。直到所有
特征都已经用完，或者数据集只有一维特征为止。决策树的生成是一个递归的过程，在决
策树生成过程中，有三种情况会导致递归返回：
（1）当前节点包含的样本属于同一类别，无须划分。
（2）当前样本属性集为空，或者所有样本在所有属性上的取值相同，无法划分。
（3）当前节点包含的样本集合为空，不能划分。
1. 特征选择
决策树算法的关键在于如何选择最优划分属性，随着划分的不断进行，应使决策树的
分支节点所包含的样本尽可能属于同一类别。特征选择问题希望选取对训练数据具有良好
分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与
随机分类的结果没有很大差别，则称这个特征没有分类能力。
拓 展
认识信息熵
为了解决特征选择问题，找出最优特征，我们先要认识信息熵。
熵的概念首先在热力学中引入，用于表述热力学第二定律，度量一个热力学系统的
无序程度。信息熵（Information Entropy）是信息论中的一个重要的指标，是由香农（C.
Shannon，1916—2001）在1948年提出的，香农借用了热力学中熵的概念来描述信息的不
确定性。
（1）信息熵。
信息熵是用来衡量一元模型中信息不确定性的指标，信息的不确定性越大，熵的值也
71 71
21Y3228.indd 71 2019/10/10 14:23:59
