1
模式识别——基于 ID3 算法的三次改进
191132 詹才韬 2016 年 7 月 7 日
Abstract
ID3 算法是决策树的鼻祖,最早于 1986 年由 Quinlan
提出,全称是 Iterative Dichotomiser 3 [1]。在这篇课
程报告中,我将对经典的 ID3 做出三次改进:1.把
改进为 ;2. 把简单投票的过
程改进为朴素贝叶斯的方法;3. 将许多颗 ID3 决策
树打造成随机森林。本人将在 Weka 平台进行二次开
发,并且用 Weka-Experiment 做大量实验,和 其它著
名的算法进行比较,最后做出综述。项目的源代码开
源在本人的 GitHub 主页上。
Improvement One
经典 ID3 算法构造一棵树的过程如下:
1. 构造根节点:输入数据集 data,找出
最大的属性 attribute,用属性 attribute 对数据集
data 划分成若干子节点。子节点中的数据集 data’
是其父节点中数据集 data 的一个子集
2. 如果子节点的 等于 0,则子节点成为
叶节点,停止生长树
3. 如果子节点的不等于 0,则以该子节
点为”根节点”,继续长树,即回到步骤 1
这里可以改进的地方在于, 在 ID3 中,
[2]。其中,
为 划 分 样 本 集 S 为 c 个 类 的 熵 ,
为属性 A 划分样本集 S 导致的期望熵。
当 data 越“纯”,entropy 就越小,子节点的 entropy
之和就 越 小 ,这样就 越 大 。 我 们 希 望
越大越好。
问题来了,现在输入一个数据集,有一个属性是这样
的:有很多的取值,甚至每一个实例的该属性上的值
都不一样。比如在 Weaher.nominal 数据集中增加一
个名为 IDcode 的属性,那么 ID3 算法构造的树如图-
1。为了解决这个问题,提出了如下改进[3]:
引入
图-1:训练集=Weather.nominal.IDcode, 算法=ID3。算
法选择了 IDcode 这个属性对数据集进行划分。然而
这样是无法对新来的实例进行预测的,因为每一个
实例的 ID code 都不一样。
其中,
这样一来,使用 来替代,可以
抵消部分某属性的取值过多的不利因素,如图-2
图-2:训练集=Weather.nominal, 算法=ID3_gain-ratio。
IDcode 的例子,其 IDcode 的 ,是第
大二 0.246 的接近 5 倍。它的 ,
只是第二大的 0.156 的 1.5 倍多一点。
评论2