常用数据挖掘算法从入门到精通 第六章 决策树分类算法概述

在接下来的几章，作者主要给大家讲一讲决策树分类算法，包括ID3算法，C4.5算法和CART算法。

为了感谢大家的支持，其中有一些内容都是作者在外面做培训的内容，希望对大家的理解有所帮助。

决策树分类模型简介

• 决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘出有用的规则，用于对新集进行预测

• 决策树算法是一种非参数学习算法。对每个输入使用由该区域的训练数据计算得到的对应的局部模型

• 决策树归纳的基本算法是贪婪算法，自顶向下以递归的方式构造决策树

• 在其生成过程中，分割时属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性

决策树算法的工作过程

决策树的结构

决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。

决策树的结构

决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？ (年龄)；母亲：26。

女儿：长的帅不帅？ (长相)；母亲：挺帅的。

女儿：收入高不？ (收入情况)；母亲：不算很高，中等情况。

女儿：是公务员不？ (是否公务员)；母亲：是，在税务局上班呢。

======>>>女儿：那好，我去见见。

找对象的决策树分类模型

• 由决策树的根结点到叶结点的每一条路径构建一条规则

• 路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论

• If-then规则集合的一重要性质：互斥并且完备

决策树分类模型学习

• 学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类

• 一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力

• 决策树学习本质：从训练数据集中归纳出一组分类规则

• 决策树学习的损失函数：通常是正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题

• 现实中决策树学习通常采用启发式方法，即局部最优

• 具体做法：每次选择Feature时，都挑选择当前条件下最优的那个Feature作为划分规则，即局部最优的Feature

• 停止条件：一个节点上的数据都是属于同一个类别或没有属性可以再用于对数据进行分割，学习停止

分类特征选择

• 特征选择在于选取对训练数据具有局部最优分类能力的特征

• 选择特征的准则不同形成不同的分类算法

• 信息增益—ID3算法

• 信息增益比—C4.5算法

• 基尼指数—CART算法

决策树的剪枝

• 决策树生成算法对于训练集是很准确的，但是会造成过拟合，所以需要通过剪枝来提高泛化能力

• 剪枝思路：就是在决策树对训练数据的预测误差和树复杂度之间找到一个权衡