决策树ID3算法的一种改进算法

黄宇达 范太华 王迤冉

（1.西南科技大学计算机科学与技术学院，四川绵阳621010；2.周口职业技术学院信息工程系，河南周口466000；3.周口师范学院计算机科学与技术学院，河南周口466001）

摘要：首先对决策树ID3算法基本原理及主要不足进行了简要分析，然后针对其主要不足即分裂属性选取过程中的多值偏向问题，通过引入一种修正函数对其加以改进，同时又提出了一种独立性假设。理论分析和实验结果表明：改进算法在一定程度上不仅较好地弥补了多值偏向的最大不足，而且还大大简化了算法计算过程，在提高分类准确度的同时也明显加快了决策树构建速度。

关键词：决策树；ID3算法；修正函数；独立性假设；加权独立信息增益

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)01-0096-03

An Improved Algorithm of Decision Tree ID3 Algorithm

HUANG Yu-da1,2，FAN Tai-hua1，WANG Yi-ran3

(1.Southwest University of Science and Technology，College of Computer Science and Technology，MianYang 621010，China；2.ZhouK? ou Vocational and Technical College，Information and Engineering Department，Zhoukou 466000，China；3.Zhoukou Normal University，College of Computer Science and Technology，Zhoukou 466000，China)

Abstract: First,ID3 algorithms basic principles and major shortcomings have been analyzed simply, and then for the main shortcoming of ID3 algorithm that tends to select a attribute which has many values in the course of selecting split-properties,and then the ID3 algorithm has been improved by introducing a correction function and Proposing a hypothesis of independence. Theoretical analysis and experimen? tal results show that the improved algorithm , to some extent, not only better compensate for the lack of multi-valued bias of the largest, but also greatly simplifies the algorithm process, improve the classification accuracy significantly and accelerate the speed of decision tree construction.

Key words: decision tree; ID3 algorithm; correction function; the assumption of independence; weighted independent information gain

近年来，数据挖掘作为一种新的数据分析方法和技术，可发现海量数据中一些潜在的有用信息，如今已在金融、证券、房地产、医疗和教育等很多行业领域得到广泛应用，同时也为人们在当今数据海洋中更快获取更多的潜在而有价值的信息提供了一种强有力手段。

分类是数据挖掘技术中最常用方法之一。决策树分类算法与其它分类算法相比，前者以信息论为基础并具有速度快、精度高、直观易懂、无参数和生成模式简单等很多优点，在如今数据挖掘领域中具有不可替代的作用和地位。ID3算法作为最具影响力的一种决策树构造算法是由QuinLan J R[1]于1986年提出，其后很多专家学者已对其进行了深入的研究[2-6]。

本文从改进和简化的角度对ID3算法加以一定程度的优化，针对其最大不足即分裂属性选取时的多值偏向问题，引入一个修正函数来修正信息增益，从而在一定程度上较好地弥补了该方面不足；另外又提出了一种与朴素贝叶斯算法相似的独立性假设，通过该假设的应用，可明显加快分类速度并大大降低计算成本。

针对ID3算法上述主要不足，已有很多学者已对其进行了深入研究并提出各自改进方案。比如，文献[3]在求信息熵时引入用户兴趣度参数，但需要用户具有一定专业知识背景且要大量反复试验，且易受用户主观意识影响，导致往往较难反应客观现实；文献[4]虽然创新性地利用泰勒公式和麦克劳林公式大大简化了信息熵的运算，提高了算法运行效率，但忽略了简化带来的误差；文献[5]提出关联度函数的概念，其在一定程度上也能克服ID3算法多值倾向的不足，但由于在计算时完全抛弃信息熵而导致不能与ID3算法的分类准确率相媲美；文献[6]采用灰色关联度来取代用户兴趣度，但实际应用中对于灰度较低和取值较多都不便界定其范围。

4结束语

本文首先针对传统ID3算法最大不足即多值偏向问题，通过引入一个修正函数来对信息增益加以修正，在一定程度上克服了ID3算法主要缺陷，然后利用独立性假设对属性信息增益值的计算过程进行了简化，明显提高了算法执行效率。实验结果表明：新算法与ID3算法相比无论在分类准确度还是分类速度方面都是相对优越的并具有较好的分类效果。

参考文献：

[1] Quinlan J R.Induction of Decision Tree [J].Machine Learn-ing,1986(2):81-106.

[2]孙爱东,朱梅阶,涂淑琴.基于属性值的ID3算法改进[J].计算机工程与设计,2008,29(12): 3011-3012.

[3]王苗，柴瑞敏.一种改进的决策树分类属性选取方法[J].计算机工程与应用,2010,46（8）：127-129.

[4]黄爱辉，陈湘涛.决策树ID3算法的改进[J].计算机工程与科学,2009,31(6):109-l11.

[5]韩松来，张辉，周华平.基于关联度函数的决策树分类算法[J].计算机应用,2005，25（11）：2655-2657.

[6]叶明权，胡学钢.一种基于灰色关联度的决策树改进算法[J].计算机工程与应用,2007,43(32):171-173.

[7] Hu X, Cercone N. Data mining via generalization,discrimination and rough set feature selection [J].International Journal of Knowledge and Information System.1999,1(1):21-27.