当前课程知识点：数据挖掘 > 第7章 分类 > 7.2 决策树 > 7.2 决策树（中）
ID3算法是
J.Rose Quinlan
提出的一种决策树算法
属于传统概念学习算法
ID3算法的构建方法
和决策树的构建基本是一致的
不同的是分裂结点的特征选择的标准
该算法在分裂结点处
将信息增益作为分裂准则进行特征选择
递归地构建决策树
ID3算法的步骤如下
①输入数据
主要包括训练集的特征和类标号
②如果所有实例都属于一个类别
则决策树是一个单结点树
否则执行③
③计算训练数据中每个特征的信息增益
④从根结点开始
选择最大信息增益的特征进行分裂
依次类推
从上向下构建决策树
每次选择具有
最大信息增益的特征进行分裂
选过的特征后面
就不能继续进行选择使用了
⑤重复步骤④
直到没有特征可以选择
或者分裂后的所有元组
属于同一类别时候停止构建
⑥决策树构建完成
进行预测
例 使用ID3算法进行分类预测
如下面两个表为训练数据和测试数据
其中“患病与否”是类标记
使用ID3算法
构建决策树然后进行分类预测
解
①连续型数据的离散化
ID3算法不能直接处理连续型数据
只有通过离散化
将连续型数据转化成
离散型数据再进行处理
此例采用等宽分箱法
对连续型特征“年龄”离散化
设定区域范围（设箱子数为3
箱子宽度为（68-23）/3=15）
分箱结果为
箱1
23 25 27 30
箱2
39 41 43 45 46 47
箱3
62 63 66 66 68
对特征“年龄”进行分箱
如图所示
离散化后训练数据集此表所示
可以看到
特征“年龄”的连续型数据离散化
②根据训练数据构造ID3算法的决策树
其中Z代表训练集
A、B、C、D分别代表特征
“年龄” “吸烟史”
“有无家族病史” “体重范围”
按照每个特征计算其分裂的信息增益
选择信息增益最大特征“体重范围”
作为根结点的分裂属性
将训练集Z划分为5个子集
Zˇ1 Zˇ2
Zˇ3 Zˇ4 和Zˇ5
对应的“体重范围”取值分别为
“低” “较低”
“中” “较高” “高”
由于Zˇ2 Zˇ3
和Zˇ4只有一类数据
所以它们各自成为一个叶结点
三个结点的类标签分别为
“否” “否” “是”
③对于Zˇ1继续进行分裂
选择剩余特征中信息增益最大的
作为分裂属性
选择信息增益最大特征
作为Zˇ1结点的分裂属性
由于三个属性的信息增益相同
随机挑选一个作为分裂属性
此处选取“有无家族病史”作为分裂属性
它将数据集Zˇ1分成2个子集
Zˇ21和Zˇ22
对应的“有无家族病史”的取值
分别为“有”和“无”
在这2个子集中的数据都各自属于同一类
于是就不需要再继续分裂
④对于Zˇ5继续进行分裂
选择剩余特征中信息增益最大的
作为分裂属性
选择信息增益最大特征“有无家族病史”
作为Zˇ5结点的分裂属性
将数据集Zˇ5分成2个子集
Zˇ51和Zˇ52
对应的“有无家族病史”的取值
分别为“有”和“无”
“有”对应的Zˇ51中的数据
都属于同一类
不需要再继续分裂
“无”对应的Zˇ52中的数据
属于不同类
需要对其进行分裂
⑤对于Zˇ52继续进行分裂
选择剩余特征中信息增益最大的
作为分裂属性
由于两个属性的信息增益相同
随机挑选一个作为分裂属性
此处选取“吸烟史”
作为Zˇ52结点的分裂属性
将数据集Zˇ52分成2个子集
Zˇ521和Zˇ522
对应的“吸烟史”的取值
分别为“无”和“5年以上”
在这两个子集中的数据都各自属于同一类
于是就不需要再继续分裂
决策树构造完毕
利用ID3算法构建的决策树如图所示
当构建好决策树之后
就可以对测试数据进行预测了
分别对编号1 2 3进行预测可以得到
他们的类别分别“否” “否” “是”
正确率为100%
根据构建的决策树
可以提取分类规则如下
决策树的每一个分支
从根结点到叶结点的路径
构成一条关联规则
路径上的不同分支结点之间是与的关系
构成了关联规则的前件
叶结点构成关联规则的后件
例如第一条路径生成的关联规则为
①IF “体重范围”=“低”
AND “有无家族病史”=“有”
THEN 患病
依次可以得到如下关联规则
②IF “体重范围”=“低”
AND “有无家族病史”=“无”
THEN 没有患病
③IF “体重范围”=“较低”
THEN 没有患病
④IF “体重范围”=“中”
THEN 没有患病
⑤IF “体重范围”=“较高”
THEN 患病
⑥IF “体重范围”=“高”
AND “有无家族病史”=“有”
THEN 患病
⑦IF “体重范围”=“高”
AND “有无家族病史”=“无”
AND “吸烟史”=“无”
THEN 没有患病
⑧IF “体重范围”=“高”
AND “有无家族病史”=“无”
AND “吸烟史”=“5年以上”
THEN 患病
-1.1 数据分析与数据挖掘
-1.2 分析与挖掘的数据类型
-1.3 数据分析与数据挖掘的方法
-1.4 数据分析与数据挖掘使用的技术
-1.5 应用场景及存在的问题
-第1章 作业1
-第1章 作业2
-2.1 数据的属性
-- 2.1 数据的属性
-2.2 数据的基本统计描述
-2.3 数据的相似性和相异性
-第2章 作业1
-第2章 作业2
-3.1 数据存在的问题
--数据存在的问题
-3.2 数据清理
--3.2 数据清理
--数据清理
-3.3 数据集成
--3.3 数据集成
--数据集成
-3.4 数据归约
--3.4 数据规约
--数据归约
-3.5 数据变换与数据离散化
-第3章 作业1
-第3章 作业2
-4.1 数据仓库基本概念
--数据仓库基本概念
-4.2 数据仓库设计
--数据仓库设计
-4.3 数据仓库实现
--数据仓库实现
-4.4 联机分析处理
--联机分析处理
-4.5 元数据模型
--元数据模型
-第4章 作业1
-第4章 作业2
-5.1 回归分析的基本概念
-5.2 一元线性回归
--一元线性回归
-5.3 多元线性回归
--多元线性回归
-5.4 多项式回归
--多项式回归
-第5章 作业1
-第5章 作业2
-6.1 概述
--频繁模式概述
-6.2 Apriori算法
-6.3 FP-growth算法
-6.4 压缩频繁项集
--压缩频繁项集
-6.5 关联模式评估
--关联模式评估
-第6章 作业1
-第6章 作业2
-7.1 分类概述
--7.1 分类概述
--分类概述
-7.2 决策树
--决策树
-7.3 朴素贝叶斯分类
--朴素贝叶斯分类
-7.4 惰性学习法
-7.5 神经网络
--神经网络
-7.6 分类模型的评估
--分类模型的评估
-第7章 第一部分作业2（研究生班级）
-第7章 第二部分作业2
-第7章 第二部分作业1
-8.1 聚类概述
--8.1 聚类概述
--聚类概述
-8.2 基于划分的聚类
--基于划分的聚类
-8.3 基于层次的聚类
--基于层次的聚类
-8.4 基于密度的聚类
--基于密度的聚类
-8.5 基于网格的聚类
--基于网格的聚类
-第8章 作业1
-第8章 作业2
-9.1 离群点定义与类型
-9.2 离群点检测
--离群点检测
-第9章 作业1
-第9章 作业2
