1、引言
ID3算法是用来干什么的?主要用来解决类似于这样的问题:今天天气晴朗、气温适中、湿度高且无风,我应该去打高尔夫球吗?
ID3算法是一种贪心算法,,用来构造决策树。ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美分类训练样例。
2、背景知识
ID3算法最早是由罗斯昆(J. Ross Quinlan)于1975年在悉尼大学提出的一种分类预测算法,算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益,认为信息增益高的是好属性,每次划分选取信息增益最高的属性为划分标准,重复这个过程,直至生成一个能完美分类训练样例的决策树。
决策树是对数据进行分类,以此达到预测的目的。该决策树方法先根据训练集数据形成决策树,如果该树不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。
3、以一个实例来讲解ID3算法
题目:表1中给出了一个关于配眼镜的一个决策分类所需要的数据。数据集包含5属性。
(1)age:{young,pre-presbyopic,presbyopic};
(2)astigmatism:{no,yes};
(3)spectacle-prescrip:{myope,hypermetrope};
(4)tear-prod-rate:{reduced,normal};
(5) contact-lenses: {soft,none,hard};
contact-lenses是决策属性,通过手动模拟ID3算法来实现决策过程。
表1训练数据集
解:
4、Word下载
(1)
作者:Joe Chael
原文地址:
思想如钻子,必须集中在一点钻下去才有力量