基于用户领域知识优化ID3算法的研究与应用
2016-10-12赵发勇陈曙光
阜阳师范大学学报(自然科学版) 2016年2期
王 森,赵发勇,陈曙光
(阜阳师范学院 物理与电子工程学院,安徽 阜阳 236041)
基于用户领域知识优化ID3算法的研究与应用
王森,赵发勇,陈曙光
(阜阳师范学院 物理与电子工程学院,安徽 阜阳 236041)
本文在ID3算法的基础上引入属性重要度因子和均衡化函数,对ID3算法进行优化,改进了经典ID3算法要求每个属性对类别属性的贡献一样的缺点,可以适用于不同属性对类别属性的贡献不同的情况,同时也弥补ID3算法偏向多值属性的不足。最后给出具体一个实例说明其构造决策树的过程,并将优化算法与经典ID3算法构造的决策树进行了比较,从而得出优化后的算法具有更大的适应范围,且更符合用户实际情况的需要。
决策树;ID3算法;属性重要度;均衡化函数
决策树算法是经常使用的一种分类算法,经典的决策树学习算法,如ID3算法[1]、C4.5算法[2]、CART算法[3]、CHILD算法[4]等,忽略了用户领域知识,认为各属性对分类属性的影响是一样,导致构造的的决策树不符合实际决策的情况。由于这种不足,所以在使用决策树算法时,用户要优化决策树算法。经典的ID3算法由于其使用范围很广,所以国内外许多学者提出方法对ID3算法进行改进,其中以C4.5算法[2]最为著名。
ID3算法是一个递归算法[1],具体计算过程如下:
首先,计算样本集正确分类的信息熵可由公式(1)计算:

其中,训练样本集S中有s个样本在m个不同类Ci(i=1,2,…,m)中,si是类Ci中的样本数,pi常用估计。
其次,根据每个侯选属性把样本分类后的信息熵由公式(2)计算:……p>
登录APP查看全文
