黃宇達(dá) 范太華 王迤冉

（1.西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川綿陽(yáng)621010；2.周口職業(yè)技術(shù)學(xué)院信息工程系，河南周口466000；3.周口師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南周口466001）

摘要：首先對(duì)決策樹ID3算法基本原理及主要不足進(jìn)行了簡(jiǎn)要分析，然后針對(duì)其主要不足即分裂屬性選取過程中的多值偏向問題，通過引入一種修正函數(shù)對(duì)其加以改進(jìn)，同時(shí)又提出了一種獨(dú)立性假設(shè)。理論分析和實(shí)驗(yàn)結(jié)果表明：改進(jìn)算法在一定程度上不僅較好地彌補(bǔ)了多值偏向的最大不足，而且還大大簡(jiǎn)化了算法計(jì)算過程，在提高分類準(zhǔn)確度的同時(shí)也明顯加快了決策樹構(gòu)建速度。

關(guān)鍵詞：決策樹；ID3算法；修正函數(shù)；獨(dú)立性假設(shè)；加權(quán)獨(dú)立信息增益

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)01-0096-03

An Improved Algorithm of Decision Tree ID3 Algorithm

HUANG Yu-da1,2，F(xiàn)AN 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

近年來，數(shù)據(jù)挖掘作為一種新的數(shù)據(jù)分析方法和技術(shù)，可發(fā)現(xiàn)海量數(shù)據(jù)中一些潛在的有用信息，如今已在金融、證券、房地產(chǎn)、醫(yī)療和教育等很多行業(yè)領(lǐng)域得到廣泛應(yīng)用，同時(shí)也為人們?cè)诋?dāng)今數(shù)據(jù)海洋中更快獲取更多的潛在而有價(jià)值的信息提供了一種強(qiáng)有力手段。

分類是數(shù)據(jù)挖掘技術(shù)中最常用方法之一。決策樹分類算法與其它分類算法相比，前者以信息論為基礎(chǔ)并具有速度快、精度高、直觀易懂、無參數(shù)和生成模式簡(jiǎn)單等很多優(yōu)點(diǎn)，在如今數(shù)據(jù)挖掘領(lǐng)域中具有不可替代的作用和地位。ID3算法作為最具影響力的一種決策樹構(gòu)造算法是由QuinLan J R[1]于1986年提出，其后很多專家學(xué)者已對(duì)其進(jìn)行了深入的研究[2-6]。

本文從改進(jìn)和簡(jiǎn)化的角度對(duì)ID3算法加以一定程度的優(yōu)化，針對(duì)其最大不足即分裂屬性選取時(shí)的多值偏向問題，引入一個(gè)修正函數(shù)來修正信息增益，從而在一定程度上較好地彌補(bǔ)了該方面不足；另外又提出了一種與樸素貝葉斯算法相似的獨(dú)立性假設(shè)，通過該假設(shè)的應(yīng)用，可明顯加快分類速度并大大降低計(jì)算成本。

針對(duì)ID3算法上述主要不足，已有很多學(xué)者已對(duì)其進(jìn)行了深入研究并提出各自改進(jìn)方案。比如，文獻(xiàn)[3]在求信息熵時(shí)引入用戶興趣度參數(shù)，但需要用戶具有一定專業(yè)知識(shí)背景且要大量反復(fù)試驗(yàn)，且易受用戶主觀意識(shí)影響，導(dǎo)致往往較難反應(yīng)客觀現(xiàn)實(shí)；文獻(xiàn)[4]雖然創(chuàng)新性地利用泰勒公式和麥克勞林公式大大簡(jiǎn)化了信息熵的運(yùn)算，提高了算法運(yùn)行效率，但忽略了簡(jiǎn)化帶來的誤差；文獻(xiàn)[5]提出關(guān)聯(lián)度函數(shù)的概念，其在一定程度上也能克服ID3算法多值傾向的不足，但由于在計(jì)算時(shí)完全拋棄信息熵而導(dǎo)致不能與ID3算法的分類準(zhǔn)確率相媲美；文獻(xiàn)[6]采用灰色關(guān)聯(lián)度來取代用戶興趣度，但實(shí)際應(yīng)用中對(duì)于灰度較低和取值較多都不便界定其范圍。

4結(jié)束語(yǔ)

本文首先針對(duì)傳統(tǒng)ID3算法最大不足即多值偏向問題，通過引入一個(gè)修正函數(shù)來對(duì)信息增益加以修正，在一定程度上克服了ID3算法主要缺陷，然后利用獨(dú)立性假設(shè)對(duì)屬性信息增益值的計(jì)算過程進(jìn)行了簡(jiǎn)化，明顯提高了算法執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明：新算法與ID3算法相比無論在分類準(zhǔn)確度還是分類速度方面都是相對(duì)優(yōu)越的并具有較好的分類效果。

參考文獻(xiàn)：

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

[2]孫愛東,朱梅階,涂淑琴.基于屬性值的ID3算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(12): 3011-3012.

[3]王苗，柴瑞敏.一種改進(jìn)的決策樹分類屬性選取方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46（8）：127-129.

[4]黃愛輝，陳湘濤.決策樹ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué),2009,31(6):109-l11.

[5]韓松來，張輝，周華平.基于關(guān)聯(lián)度函數(shù)的決策樹分類算法[J].計(jì)算機(jī)應(yīng)用,2005，25（11）：2655-2657.

[6]葉明權(quán)，胡學(xué)鋼.一種基于灰色關(guān)聯(lián)度的決策樹改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,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.