基于属性值的ID3算法改进  

Improved ID3 algorithm based on attribute values

作　　者：孙爱东[1] 朱梅阶[1] 涂淑琴[1] 

机构地区：[1]华南农业大学信息学院,广东广州510642

出　　处：《计算机工程与设计》2008年第12期3011-3012,3033,共3页Computer Engineering and Design

基　　金：华南农业大学校长基金项目(2005X027)

摘　　要：I:D3算法是数据挖掘中经典的决策树分类算法。针对ID3算法所存在的属性取值偏向问题及只对较小的数据集有效的缺点提出改进。当训练样本各属性的取值个数相差较大的情况下,在计算划分标准时引入了属性取值个数N,在一定程度上克服了ID3算法易偏向于取值较多的属性这一缺陷,得到了结构更简洁的、较为理想的决策树。采用先剪枝的方法实现改进,设定一个阈值避免决策树的完全生长,在保持分类准确率的同时,大大地提高了算法的速度。实验结果表明,改进后的算法(AVID3)对许多数据集比传统ID3算法更有效。ID3 is a classical decision tree induction algorithm in data mining. It has the preference bias in selecting attributes with multiple values and is related to the number of training examples. A new approach to solving these drawbacks is given. At first, the threshold of attributes value＇s number is assigned to optimize the decision tree in calculating the entropy. At the meantime, a tree pruning method is implemented by adopting another threshold to reduce the error rate of the fully expanded tree. Experimental results demonstrated that the improved ID3 algorithm （AVID3） is more efficient than the traditional ID3 algorithm on many data sets.

关 键 词：决策树 ID3算法 剪枝 属性值 熵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]