数据挖掘2-ID3算法_第1页
数据挖掘2-ID3算法_第2页
数据挖掘2-ID3算法_第3页
数据挖掘2-ID3算法_第4页
数据挖掘2-ID3算法_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、ID3 算法,2020/7/21,ID3算法是一个众所周之的决策树算法，该算法是澳大利亚悉尼大学的Ross Quinlan于1986年提出，也是国际上最早、最有影响力的决策树算法，其他的许多算法如C4.5、CART算法等都是在ID3算法基础上的改进。,在ID3算法中，决策节点属性的选择运用了信息论中的熵概念作为启发式函数。 在这种属性选择方法中，选择具有最大信息增益（information gain）的属性作为当前划分节点。 通过这种方式选择的节点属性可以保证决策树具有最小的分枝数量，使得到的决策树冗余最小。,公式1,设数据划分D为类标记的元组的训练集。 假定类标号属性具有M个不同值，定义m个

2、不同的类Ci（I1，2，m），Ci,D是Ci类的元组的集合。 D和 Ci,，D 分别表示D和Ci,D中元组的个数。 对D中的元组分类所需的期望信息由下式给出：,公式2,假设属性A具有v个不同的离散属性值，可使用属性A把数据集D划分成v个子集D1, D2，Dv。设子集Dj中全部的记录数在A上具有相同的值aj。基于按A划分对D的元组分类所需要的期望信息由下式给出：,公式3,信息增益定义为原来的信息需求（基于类比例）与新的信息需求（对A划分之后得到的）之间的差，即 Gain(A)=Info（D）-InfoA（D）,实例 1.xls,假如你是一个网球爱好者，天气状况（天气、温度、湿度、风力）是你决定是

3、否去打球的重要因素，利用ID3算法构筑决策树。,实例 1.xls,以往部分打球数据库类标记的训练元组统计如表2-2所示。,类标号打球有两个取值（即是，否），因此有两个不同的类，即m=2，设C1类对应与是，C2类对应于否。C1有9个元组，C2有5个元组。我们根据公式1可以计算D中元组分类所需要的期望信息：,如果根据天气属性划分，根据公式2则对D的元组进行分类所需要的期望信息为：,根据公式3这种划分的信息增益是,Gain（天气）=info（D）-info天气（D）=0.940-0.694=0.246位,类似地，可以计算 Gain(温度) = 0.029 Gain(湿度)=0.151 Gain(风力)=0.048,由于天气在属性中具有最高信息增益，它被选作测试属性。创建一个节点，用天气标记，并根据每个属性值，引出一个分枝。注意，落在分区天气= 多云”的样本都属于同一类，根据算法，要在该分支的端点创建一个树叶，并用“是”标记。同理，在“晴朗”和“雨天” 这两个分支上，分别对“温度”、“湿度”、“风力”属性计算其信息增益，分别选取一

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论