一種基于決策樹ID3的改進(jìn)算法

王子京 劉毓

摘 要： 針對(duì)傳統(tǒng)ID3算法無法處理屬性值連續(xù)的數(shù)據(jù)集，設(shè)計(jì)了一種新的改進(jìn)算法用于連續(xù)評(píng)價(jià)數(shù)據(jù)的處理。改進(jìn)算法先用聚類算法對(duì)連續(xù)屬性值進(jìn)行離散化，再計(jì)算屬性的粗糙度作為屬性分裂的標(biāo)準(zhǔn)，最后用改進(jìn)的ID3算法生成決策樹。通過仿真驗(yàn)證了該方法的預(yù)測(cè)正確率，并探討其應(yīng)用條件。實(shí)驗(yàn)結(jié)果表明，在不降低正確率的情況下，該算法可處理屬性值連續(xù)的數(shù)據(jù)且具有更好的可讀性及更低的運(yùn)算量。

關(guān)鍵詞： 數(shù)據(jù)挖掘； 決策樹； 粗糙集； ID3算法； 大數(shù)據(jù)； 算法改進(jìn)

中圖分類號(hào)： TN911.1?34； TP181 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）15?0039?04

An improved ID3 algorithm for decision tree

WANG Zijing， LIU Yu

（School of Communications and Information Engineering， Xian University of Posts & Telecommunications， Xian 710121， China）

Abstract： The traditional ID3 algorithm can′t process the dataset with continuous attribute value. Therefore， an improved ID3 algorithm is designed to process the continuous evaluation data. The clustering algorithm is used in the improved algorithm to discrete the continuous attribute values， and then the roughness of the attribute is calculated as the divisive standard of the attribute. The improved ID3 algorithm is adopted to generate the decision tree. The prediction accuracy of the method is verified with simulation， and its application condition is discussed. The experimental result shows that the improved algorithm can process the data with continuous attribute value， and has high readability and less computational amount while maintaining the accuracy.

Keywords： data mining； decision tree； rough set； ID3 algorithm； big data； algorithm improvement

0 引 言

ID3算法是數(shù)據(jù)挖掘中一個(gè)重要的分類算法[1]，該算法用信息增益作為分裂屬性算擇的標(biāo)準(zhǔn)，生成的決策樹結(jié)構(gòu)簡(jiǎn)單，結(jié)果可讀性好。然而，ID3算法并不適用于連續(xù)數(shù)據(jù)，且傾向于選擇多值屬性分裂。文獻(xiàn)[2?4]提出基于模糊集和粗糙集的改進(jìn)方案，用條件屬性的粗糙度代替屬性的信息熵作為分裂的標(biāo)準(zhǔn)，以解決ID3算法傾向選擇多值屬性的問題。而對(duì)于ID3無法處理連續(xù)值的問題，文獻(xiàn)[5?6]提出C4.5和CART（Classification and Regression Tree）算法。C4.5算法對(duì)連續(xù)屬性進(jìn)行分割并使分割信息熵最小，采用信息增益率作為分裂屬性的標(biāo)準(zhǔn)。而CART算法在屬性值連續(xù)的情況下，使用最小剩余方差來判定回歸樹的最優(yōu)劃分，生成回歸樹。但是C4.5和CART算法的輸出結(jié)果帶有連續(xù)屬性值的具體范圍，不易于理解。因此，仍需在優(yōu)化結(jié)果的可讀性上做進(jìn)一步的工作?？陀^世界中，存在這樣一類數(shù)據(jù)，在采樣時(shí)是連續(xù)的，在決策時(shí)，需用具有較好可讀性的離散指標(biāo)代替原連續(xù)值。因此，有必要對(duì)連續(xù)量進(jìn)行離散化并深入挖掘該連續(xù)量反映的評(píng)價(jià)等級(jí)信息，如在某種對(duì)學(xué)生的評(píng)價(jià)中，需將其連續(xù)成績(jī)轉(zhuǎn)化為“優(yōu)”“良”“中”“差”的評(píng)價(jià)指標(biāo)。對(duì)于這些數(shù)據(jù)，設(shè)計(jì)一種高效、可讀性強(qiáng)的決策方法是非常必要的。文獻(xiàn)[7]提出對(duì)于決策樹中的連續(xù)屬性值用聚類算法進(jìn)行離散化的思路，但是對(duì)于這種方法的具體實(shí)施、預(yù)測(cè)正確率、應(yīng)用場(chǎng)合及局限的研究上仍有待進(jìn)一步分析探討。本文提出用K?means++算法離散化連續(xù)屬性值的思想，并且結(jié)合粗糙集的研究成果，改進(jìn)原有的ID3算法，減少傳統(tǒng)ID3算法的運(yùn)算量。本文在具體數(shù)據(jù)集中應(yīng)用改進(jìn)的ID3算法，通過實(shí)驗(yàn)仿真得出改進(jìn)ID3算法的預(yù)測(cè)正確率，最后對(duì)改進(jìn)算法的應(yīng)用場(chǎng)合以及局限作出明確探討。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)ID3算法在不降低預(yù)測(cè)正確率的情況下，具有更好的可讀性，更少的運(yùn)算量，適用于需離散化為等級(jí)指標(biāo)的連續(xù)數(shù)據(jù)。

信息增益越大，再劃分時(shí)所需要的信息量就越小。一般情況下，存在數(shù)個(gè)條件屬性，分別計(jì)算每一個(gè)條件屬性的信息增益，選擇信息增益最大的一個(gè)屬性作為分裂節(jié)點(diǎn)。假如存在一個(gè)多值屬性，這個(gè)屬性往往會(huì)被優(yōu)先選擇作為分裂節(jié)點(diǎn)。但是取值最多的屬性有可能是在實(shí)踐中沒有意義的甚至是不相關(guān)的屬性。另外，計(jì)算各條件屬性的信息熵時(shí)，要進(jìn)行大量的對(duì)數(shù)運(yùn)算。在數(shù)據(jù)集較大的情況下，運(yùn)算量陡增。因此，有必要針對(duì)這兩個(gè)問題作出改進(jìn)。

2 基于粗糙集的ID3算法原理

對(duì)于上述運(yùn)算量大和偏向選擇多值屬性的問題，文獻(xiàn)[8?9]提出一種基于粗糙集的改進(jìn)算法。它的核心思想是用條件屬性的粗糙度作為選擇分裂屬性的標(biāo)準(zhǔn)，無需進(jìn)行對(duì)數(shù)運(yùn)算，減少了運(yùn)算量，避免了優(yōu)先選擇多值屬性。

2.1 決策系統(tǒng)

四元組[S=U，A，V，f]為一個(gè)信息系統(tǒng)。其中，[U]為所要驗(yàn)究對(duì)象的非空有限集合，為論域；[A]是屬性集合；[V=a∈AVa]是屬性[a]的值域；[f：U×A→V]是信息函數(shù)，其為論域中的每一個(gè)對(duì)象賦予屬性值。若[A=C∪D]，其中，C為條件屬性集合，D為決策屬性集合，則該信息系統(tǒng)稱為決策系統(tǒng)。

2.2 不可區(qū)分關(guān)系

對(duì)于一個(gè)決策系統(tǒng)[S=U，A，V，f]，[?B?A]是屬性集合的一個(gè)子集，稱等價(jià)關(guān)系[IndB]為[S]的不可區(qū)分關(guān)系，即：

[IndB=x，y∈U×U?a∈B，fx，a=fy，a]

它的含意是僅僅通過屬性集[B]無法區(qū)分對(duì)象[x]和對(duì)象[y]，即兩者的屬性取值相同。

2.3 上近似與下近似

對(duì)于一個(gè)決策系統(tǒng)[S=U，A，V，f]，[IndB]是等價(jià)關(guān)系，[X∈U]是一個(gè)樣例集，它是粗糙的，那么[X]的某些子集可以完全被定義，稱為下近似集；可能屬于[X]的集合稱為上近似集。數(shù)學(xué)表達(dá)式如下：

[BX=xi∈UBxi?X] （5）

[BX=xi∈UBxi∩X≠?] （6）

式中：[BX]為[X]的下近似集；[BX]為[X]的上近似集；[Bxi]為等價(jià)關(guān)系[IndB]下包含[xi]的等價(jià)類。

2.4 屬性重要性

設(shè)[P，Q∈R]，其中[R]是論域中等價(jià)關(guān)系的集合。那么[γPQ]表示[P]的分類能力：

[γPQ=cardPXcardX] （7）

式中：card是求模運(yùn)算；[X]是屬于等價(jià)關(guān)系[Q]下的等價(jià)類非空集合。對(duì)于[P]下的屬性[a]，分別計(jì)算[a]加入[P]與未加入[P]時(shí)的[γPQ]，可以得出屬性[a]的重要性。表達(dá)式如下：

[SGAa，P，Q=γPQ-γP-{a}Q] （8）

3 K?means算法及改進(jìn)

K?means是一種聚類算法，流程如下：在數(shù)據(jù)集中隨機(jī)選擇k個(gè)不同的值作為聚類中心。計(jì)算數(shù)據(jù)集中每一個(gè)樣本與k個(gè)分類中心的距離，并將其歸入最臨近的一個(gè)中心所在的一類。得到一個(gè)聚類結(jié)果后，再次計(jì)算各分類結(jié)果的中心，計(jì)算樣本與中心之間的距離，反復(fù)迭代，以至得到一個(gè)聚類誤差收斂的結(jié)果或根據(jù)實(shí)際情況設(shè)定迭代次數(shù)。

K?means聚類的結(jié)果以及迭代次數(shù)與初始值選擇有很大關(guān)系。為了提高效率、改善聚類結(jié)果，必須優(yōu)化初始值的選擇。文獻(xiàn)[10]提出K?Means++算法，它的思想是在選擇初始值時(shí)盡可能地使各初始值的距離最大，可減少迭代的次數(shù)，提高聚類效率。

4 改進(jìn)的ID3算法原理

改進(jìn)算法的主要思想是首先將數(shù)據(jù)集中連續(xù)的屬性取值應(yīng)用K?means++算法進(jìn)行離散化，然后計(jì)算各條件屬性的重要性[SGAa，P，Q]，選擇重要性大的屬性作為分裂節(jié)點(diǎn)。反復(fù)迭代，直至所有條件屬性均被用作分裂節(jié)點(diǎn)。最后剪枝生成決策樹。

改進(jìn)的ID3算法主要步驟如下：

1） 數(shù)據(jù)初始化。

2） 判斷屬性值是否離散。若離散，則執(zhí)行步驟3）。否則，確定離散化后取值的個(gè)數(shù)，應(yīng)用K?means++算法離散化，并用離散值代替原連續(xù)值。

3） 計(jì)算活躍的條件屬性的重要性，即根據(jù)式（8）計(jì)算[SGAa，P，Q]的值。

4） 分割樣本集，選擇重要性最大的條件屬性作為分裂節(jié)點(diǎn)。

5） 繼續(xù)分割樣本集，重復(fù)步驟3）和步驟4）選擇剩余的條件屬性分割樣本集，直至所有條件屬性均被用作分裂結(jié)點(diǎn)。

6） 剪枝，生成決策樹。

5 實(shí)驗(yàn)以及結(jié)果分析

本文通過分析督導(dǎo)專家對(duì)授課教師的聽課評(píng)價(jià)記錄，應(yīng)用改進(jìn)的ID3算法生成評(píng)判授課教師教學(xué)水平高低的決策規(guī)則。目前本文提出的算法已應(yīng)用于西安郵電大學(xué)的本科教學(xué)評(píng)估實(shí)踐中。

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文的數(shù)據(jù)為近年西安郵電大學(xué)督導(dǎo)專家對(duì)本校教師的聽課評(píng)價(jià)記錄，該數(shù)據(jù)可在西安郵電大學(xué)官網(wǎng)下載。數(shù)據(jù)集的結(jié)構(gòu)如表1所示，樣本的數(shù)量為325個(gè)。樣本中包含4個(gè)條件屬性和1個(gè)決策屬性。決策屬性是連續(xù)的；而條件屬性即教師的教學(xué)態(tài)度、教學(xué)內(nèi)容、教學(xué)能力和教學(xué)效果，是離散的。所有條件屬性下的取值均為“一般”和“良好”兩個(gè)評(píng)價(jià)等級(jí)。改進(jìn)算法對(duì)連續(xù)的決策屬性值進(jìn)行離散化。在離散化過程中，需根據(jù)評(píng)價(jià)體系的不同，確定相應(yīng)的聚類中心個(gè)數(shù)。一般而言，二值評(píng)價(jià)和三值評(píng)價(jià)體系較為常見。本文采用二值評(píng)價(jià)體系，將待評(píng)教師分為“良好”和“一般”兩類。

5.2 實(shí)驗(yàn)過程

將樣本分為4等份，前3份用作訓(xùn)練數(shù)據(jù)，最后1份用作測(cè)試集。所有仿真均在Matlab 2012軟件中完成。本文在二值評(píng)價(jià)體系中應(yīng)用改進(jìn)算法，生成的決策樹如圖1所示。本文也應(yīng)用了CART算法分析數(shù)據(jù)集，作為參照對(duì)象。最后分別測(cè)試生成的決策樹的準(zhǔn)確性。測(cè)試結(jié)果及決策樹復(fù)雜度如表2所示，其中CART算法的準(zhǔn)確率是指在預(yù)測(cè)值的區(qū)間[-0.5，0.5]之內(nèi)的實(shí)際值與所有實(shí)際值的比例。

5.3 實(shí)驗(yàn)結(jié)果分析

二值評(píng)價(jià)體系下改進(jìn)算法生成的決策樹更為簡(jiǎn)潔。改進(jìn)算法的葉子節(jié)點(diǎn)已經(jīng)是教師的評(píng)價(jià)結(jié)果，可讀性更好。這是因?yàn)镃ART算法在用條件屬性分割樣本集后，僅僅對(duì)樣本作回歸分析，并未對(duì)樣本所反映的評(píng)價(jià)等級(jí)信息進(jìn)行深入挖掘。而改進(jìn)算法通過對(duì)樣本集作聚類，充分挖掘了隱藏的評(píng)價(jià)等級(jí)信息，得出的決策樹的可讀性更好。另外，改進(jìn)算法只計(jì)算條件屬性的重要性，而CART算法生成回歸樹時(shí)，需要對(duì)樣本實(shí)施分割并進(jìn)行回歸分析。因此，改進(jìn)的ID3算法的計(jì)算量比CART算法小，運(yùn)行時(shí)間更短。綜上所述，改進(jìn)的ID3算法適用于本文的教學(xué)督導(dǎo)評(píng)價(jià)數(shù)據(jù)，具有良好的可讀性以及較少的計(jì)算量。

6 結(jié) 語

ID3算法是數(shù)據(jù)挖掘中的一種重要算法。針對(duì)具體的關(guān)于評(píng)價(jià)體系的數(shù)據(jù)，本文提出的改進(jìn)ID3算法用K?means離散連續(xù)屬性值，通過計(jì)算屬性的重要性選擇分裂節(jié)點(diǎn)，生成決策樹。實(shí)驗(yàn)證明具有更好的可讀性及較低的計(jì)算量。然而，本文只在二值評(píng)價(jià)體系下應(yīng)用了改進(jìn)算法，對(duì)于其他評(píng)價(jià)體系下的應(yīng)用仍需做進(jìn)一步研究。另外，本文提出的改進(jìn)ID3算法在其他類型數(shù)據(jù)的應(yīng)用上也有必要做進(jìn)一步探討。

參考文獻(xiàn)

[1] 李泓波，白勁波，楊高明，等.決策樹技術(shù)研究綜述[J].電腦知識(shí)與技術(shù)，2015，11（24）：1?4.

LI Hongbo， BAI Jinbo， YANG Gaoming， et al. Review on decision tree technology research [J]. Computer knowledge and technology， 2015， 11（24）： 1?4.

[2] 翟俊海，翟夢(mèng)堯，李勝杰.基于相容粗糙集技術(shù)的連續(xù)值屬性決策樹歸納[J].計(jì)算機(jī)科學(xué)，2012，39（11）：183?186.

ZHAI Junhai， ZHAI Mengyao， LI Shengjie. Induction of decision tree for continuous?valued attributes based on tolerance rough sets technique [J]. Computer science， 2012， 39（11）： 183?186.

[3] 朱付保，霍曉齊，徐顯景.基于粗糙集的ID3決策樹算法改進(jìn)[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2015，30（1）：50?54.

ZHU Fubao， HUO Xiaoqi， XU Xianjing. Improved ID3 decision tree algorithm based on rough set [J]. Journal of Zhengzhou University of Light Industry （natural science）， 2015， 30（1）： 50?54.

[4] 翟俊海，王華超，張素芳.一種基于模糊熵的模糊分類算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（20）：176?180.

ZHAI Junhai， WANG Huachao， ZHANG Sufang. Fuzzy classification algorithm based on fuzzy entropy [J]. Computer engineering and applications， 2010， 46（20）： 176?180.

[5] 鞏固，呂俊懷，黃永青，等.有效改進(jìn)C5.0算法的方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（22）：5197?5199.

GONG Gu， L? Junhuai， HUANG Yongqing， et al. Effective method of improving C5.0 algorithm [J]. Computer engineering and design， 2009， 30（22）： 5197?5199.

[6] 張亮，寧芊.CART決策樹的兩種改進(jìn)及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（5）：1209?1213.

ZHANG Liang， NING Qian. Two improvements on CART decision tree and its application [J]. Computer engineering and design， 2015， 36（5）： 1209?1213.

[7] 王小巍，蔣玉明.決策樹ID3 算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（9）：3069?3072.

WANG Xiaowei， JIANG Yuming. Analysis and improvement of ID3 decision tree algorithm [J]. Computer engineering and design， 2011， 32（9）： 3069?3072.

[8] LIU X W， WANG D H， JIANG L X. A novel method for inducing ID3 decision trees based on variable precision rough set [C]// 2011 the Seventh International Conference on Natural Computation. Shanghai， China： IEEE， 2011： 494?497.

[9] 翟俊海，侯少星，王熙照.粗糙模糊決策樹歸納算法[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，52（2）：306?312.

ZHAI Junhai， HOU Shaoxing， WANG Xizhao. Induction of rough fuzzy decision tree [J]. Journal of Nanjing University （natural sciences）， 2016， 52（2）： 306?312.

[10] 周潤(rùn)物，李智勇，陳少淼，等.面向大數(shù)據(jù)處理的并行優(yōu)化抽樣聚類K?means算法[J].計(jì)算機(jī)應(yīng)用，2016，36（2）：311?315.

ZHOU Runwu， LI Zhiyong， CHEN Shaomiao， et al. Parallel optimization sampling clustering K?means algorithm for big data processing [J]. Journal of computer applications， 2016， 36（2）： 311?315.

[11] 李曉瑜，俞麗穎，雷航，等.一種K?means改進(jìn)算法的并行化實(shí)現(xiàn)與應(yīng)用[J].電子科技大學(xué)學(xué)報(bào)，2017，46（1）：61?68.

LI Xiaoyu， YU Liying， LEI Hang， et al. The parallel implementation and application of an improved K?means algorithm [J]. Journal of University of Electronic Science and Technology of China， 2017， 46（1）： 61?68.