文档介绍：决策树ID3算法的一种改进算法
黄宇达 范太华 王迤冉 (,四川绵阳621010;,河南周口466000;,河南周口46600has 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]提出关联