《数据挖掘2-ID3算法》由会员分享，可在线阅读，更多相关《数据挖掘2-ID3算法（16页珍藏版）》请在金锄头文库上搜索。
1、ID3 算法,ID3算法是一个众所周之的决策树算法，该算法是澳大利亚悉尼大学的Ross Quinlan于1986年提出，也是国际上最早、最有影响力的决策树算法，其他的许多算法如C4.5、CART算法等都是在ID3算法基础上的改进。,在ID3算法中，决策节点属性的选择运用了信息论中的熵概念作为启发式函数。 在这种属性选择方法中，选择具有最大信息增益（information gain）的属性作为当前划分节点。 通过这种方式选择的节点属性可以保证决策树具有最小的分枝数量，使得到的决策树冗余最小。,公式1,设数据划分D为类标记的元组的训练集。 假定类标号属性具有M个不同值，定义m个不同的类Ci（I1，
2、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、投掷硬币？ 2、投掷均匀正六面体的骰子？,
