下载掌阅APP，畅读海量书库
立即打开
本章概要
1．分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个if-then规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。
2．决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是NP完全问题。现实中采用启发式方法学习次优的决策树。
决策树学习算法包括3部分：特征选择、树的生成和树的剪枝。常用的算法有ID3、C4.5和CART。
3．特征选择的目的在于选取对训练数据能够分类的特征。特征选择的关键是其准则。常用的准则如下：
（1）样本集合 D 对特征 A 的信息增益（ID3）
其中， H （ D ）是数据集 D 的熵， H （ D i ）是数据集 D i 的熵， H （ D | A ）是数据集 D 对特征 A 的条件熵。 D i 是 D 中特征 A 取第 i 个值的样本子集， C k 是 D 中属于第 k 类的样本子集。 n 是特征 A 取值的个数， K 是类的个数。
（2）样本集合 D 对特征 A 的信息增益比（C4.5）
其中， g （ D , A ）是信息增益， H A （ D ）是 D 关于特征 A 的值的熵。
（3）样本集合 D 的基尼指数（CART）
特征 A 条件下集合 D 的基尼指数：
4．决策树的生成。通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根结点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。
5．决策树的剪枝。由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。