王　森，趙發(fā)勇，陳曙光

（阜陽(yáng)師范學(xué)院 物理與電子工程學(xué)院，安徽 阜陽(yáng) 236041）

基于用戶領(lǐng)域知識(shí)優(yōu)化ID3算法的研究與應(yīng)用

王森，趙發(fā)勇，陳曙光

（阜陽(yáng)師范學(xué)院 物理與電子工程學(xué)院，安徽 阜陽(yáng) 236041）

本文在ID3算法的基礎(chǔ)上引入屬性重要度因子和均衡化函數(shù)，對(duì)ID3算法進(jìn)行優(yōu)化，改進(jìn)了經(jīng)典ID3算法要求每個(gè)屬性對(duì)類別屬性的貢獻(xiàn)一樣的缺點(diǎn)，可以適用于不同屬性對(duì)類別屬性的貢獻(xiàn)不同的情況，同時(shí)也彌補(bǔ)ID3算法偏向多值屬性的不足。最后給出具體一個(gè)實(shí)例說明其構(gòu)造決策樹的過程，并將優(yōu)化算法與經(jīng)典ID3算法構(gòu)造的決策樹進(jìn)行了比較，從而得出優(yōu)化后的算法具有更大的適應(yīng)范圍，且更符合用戶實(shí)際情況的需要。

決策樹；ID3算法；屬性重要度；均衡化函數(shù)

決策樹算法是經(jīng)常使用的一種分類算法，經(jīng)典的決策樹學(xué)習(xí)算法，如ID3算法［1］、C4.5算法［2］、CART算法［3］、CHILD算法［4］等，忽略了用戶領(lǐng)域知識(shí)，認(rèn)為各屬性對(duì)分類屬性的影響是一樣，導(dǎo)致構(gòu)造的的決策樹不符合實(shí)際決策的情況。由于這種不足，所以在使用決策樹算法時(shí)，用戶要優(yōu)化決策樹算法。經(jīng)典的ID3算法由于其使用范圍很廣，所以國(guó)內(nèi)外許多學(xué)者提出方法對(duì)ID3算法進(jìn)行改進(jìn)，其中以C4.5算法［2］最為著名。

ID3算法是一個(gè)遞歸算法［1］，具體計(jì)算過程如下：

首先，計(jì)算樣本集正確分類的信息熵可由公式（1）計(jì)算：

其中，訓(xùn)練樣本集S中有s個(gè)樣本在m個(gè)不同類Ci（i=1，2，…，m）中，si是類Ci中的樣本數(shù)，pi常用估計(jì)。

其次，根據(jù)每個(gè)侯選屬性把樣本分類后的信息熵由公式（2）計(jì)算：

其中 sij是屬于子集Sj中類別Ci的樣本個(gè)數(shù)，充當(dāng)?shù)趈個(gè)子集的權(quán)。E（A）越小，子集純度越高。

最后計(jì)算每個(gè)侯選屬性A上的信息增益由公式（3）給出：

表示知道屬性A的值而導(dǎo)致訓(xùn)練集的信息熵減小。

ID3算法計(jì)算并比較各侯選屬性的信息增益值，選取具有信息增益最高的侯選屬性作為測(cè)試屬性。據(jù)該屬性創(chuàng)建一個(gè)結(jié)點(diǎn)，并根據(jù)該屬性的每個(gè)值創(chuàng)建該結(jié)點(diǎn)的分枝且劃分樣本；對(duì)于每個(gè)劃分后的子樣本集，遞歸調(diào)用該算法。ID3算法有兩個(gè)不足，不使用領(lǐng)域知識(shí)（也是它的優(yōu)點(diǎn)）和信息增益算法有選擇多值屬性的傾向，但多值屬性未必是最優(yōu)的測(cè)試屬性；所以創(chuàng)建的決策樹有時(shí)不符合實(shí)際的決策情況且效率低下。

文獻(xiàn)［5-8］引進(jìn)用戶興趣度對(duì)ID3算法作了改進(jìn)，增加對(duì)用戶感興趣屬性的重要性，把計(jì)算信息熵時(shí)加權(quán)和轉(zhuǎn)換為權(quán)加用戶興趣度的和。某屬性的信息熵E（A）改為并對(duì)用戶興趣度α的選取提出很好的建議，由決策者根據(jù)先驗(yàn)知識(shí)或領(lǐng)域知識(shí)測(cè)試后給出其大小，一般在［0，1］范圍內(nèi)。

1　基于用戶領(lǐng)域知識(shí)決策樹的理論基礎(chǔ)

訓(xùn)練樣本的每個(gè)屬性對(duì)決策結(jié)果影響的重要性可能不同。在此情況下，若把它們同樣的對(duì)待，并根據(jù)ID3算法得到的決策樹，可能無法反映真實(shí)的決策情況。例如在學(xué)期末，學(xué)生課程的綜合成績(jī)，期末考試成績(jī)的重要性要比平時(shí)上課出席情況、作業(yè)情況要高，而ID3算法把屬性看為同等重要，構(gòu)建的決策樹不符合實(shí)際的決策過程；再比如，對(duì)于同一個(gè)數(shù)據(jù)集不同的用戶可能有不同的要求：在買汽車時(shí)有的用戶可能更注意汽車的安全性，對(duì)安全性有特殊的要求，而注重環(huán)保的用戶，可能對(duì)節(jié)能或新能源有特殊的要求；在選擇籃球運(yùn)動(dòng)員時(shí)，在同等的條件下，更注重身高的要求；在評(píng)價(jià)學(xué)生論文的成績(jī)時(shí)更關(guān)注論文的有無創(chuàng)新性等，這樣的例子在日常生活和工作中很常見；因此為了體現(xiàn)不同侯選屬性對(duì)類別屬性重要性的不同，筆者在計(jì)算各侯選屬性的信息增益時(shí)，根據(jù)用戶的先驗(yàn)知識(shí)，將候選屬性對(duì)分類屬性的重要性進(jìn)行量化，引入了屬性重要度參數(shù)α，不同的候選屬性可以根據(jù)實(shí)際決策時(shí)該屬性的重要性來設(shè)置，可以按比例對(duì)各屬性進(jìn)行設(shè)置，也可根據(jù)經(jīng)驗(yàn)設(shè)置其中某個(gè)或某些屬性的重要性。屬性重要性α體現(xiàn)的是分類屬性依賴候選屬性的重要性，屬性越關(guān)鍵越重要，α取值越大；反之，則屬性重要性越小，α取值越小；若為0，則按照ID3算法考慮該屬性。

另一方面，經(jīng)典的ID3算法在選擇測(cè)試屬性時(shí)有選取多值屬性傾向，而這些屬性在實(shí)際情況下并不一定是最優(yōu)測(cè)試屬性，反而取值少的屬性有可能為分類提供更有用的信息。因此，為了有效地解決偏向于取值較多的屬性問題，引入了信息均衡化函數(shù) f（N），它與屬性值的個(gè)數(shù)N有相同的變化趨勢(shì)，即隨著N的增加而增加。當(dāng)然 f（N）選擇的好壞對(duì)結(jié)果也有很大的影響，已有學(xué)者證明C4.5算法中，就隨著 N值的增加而增加。

在參考前人研究成果的基礎(chǔ)上，結(jié)合自己實(shí)際研究工作，利用領(lǐng)域知識(shí)引入屬性重要度或?qū)傩载暙I(xiàn)度和信息增益均衡化處理［9-11］，從而，增加用戶對(duì)特別屬性重要性的要求和降低ID3算法偏向多值屬性的影響，在計(jì)算信息增益時(shí)，采用具體公式如下：

gain（屬性）=（I（分類屬性）-（1-α）E（屬性）/f（N）（4）

公式（4）說明：

α是屬性重要度，是表示該屬性的重要性，越重要值越大，常常根據(jù)領(lǐng)域知識(shí)實(shí)驗(yàn)得到，其范圍在0和1之間，即：0≤α≤1；

f（N）為信息增益均衡化函數(shù)，它與屬性值的個(gè)數(shù)N有相同的變化趨勢(shì)，即隨著N值的增加，函數(shù)值也增加，最簡(jiǎn)單的取該屬性的值的個(gè)數(shù)N；另外C4.5的spliti（A）函數(shù)就具有這種性質(zhì)。

I（分類屬性）是計(jì)算該數(shù)據(jù)樣本集分類所需的期望信息；

E（屬性）是該候選屬性的信息熵；

gain（屬性）是該候選屬性的信息增益；

在計(jì)算并比較每個(gè)屬性的信息增益后，選擇信息增益最大的屬性為測(cè)試屬性，據(jù)此對(duì)樣本空間進(jìn)行劃分。

對(duì)公式（4）的分析說明：

(ⅰ)屬性對(duì)分類貢獻(xiàn)越大，即重要性越大，α越大，最大值為1，即指定按照該屬性進(jìn)行分裂，反之，屬性對(duì)分類貢獻(xiàn)越小，即重要性越小，α越小，最小值為0，即與標(biāo)準(zhǔn)的ID3算法一樣同等的考慮該屬性；

( ⅱ)當(dāng)α=0，f（N）=1時(shí)，該公式退化為標(biāo)準(zhǔn)ID3計(jì)算信息增益的公式；

(ⅳ)可以根據(jù)用戶的要求任意指定某個(gè)或某些屬性的的重要性α，而不必全部指定（當(dāng)然也可以全部指定）。

此外為了加快構(gòu)建決策樹，在構(gòu)建決策樹時(shí)，可以根據(jù)用戶指定的閾值采用先剪枝方法，使用統(tǒng)計(jì)度量，若要分裂的樣本中有閾值以上樣本屬于同一個(gè)類時(shí)停止結(jié)點(diǎn)的分裂，構(gòu)建葉子結(jié)點(diǎn)，并用多數(shù)表決來決定該結(jié)點(diǎn)的類別。

2　基于用戶領(lǐng)域知識(shí)決策樹算法

構(gòu)建一個(gè)基于用戶領(lǐng)域知識(shí)決策樹算法如下：

算法名及參數(shù)說明：Gen_User_Dec_Tree（S，A，A_Importance）其中S是訓(xùn)練數(shù)據(jù)集，A是候選屬性集，A_Importance是候選屬性對(duì)應(yīng)的重要性因子的集合。

算法功能：由要訓(xùn)練、學(xué)習(xí)的數(shù)據(jù)集產(chǎn)生一棵用戶決策樹。

輸入：由離散屬性表示訓(xùn)練數(shù)據(jù)集S；用于決策候選屬性的集合A；每個(gè)用于決策候選屬性對(duì)應(yīng)的重要性因子的集合A_Importance。

輸出：一棵用戶決策樹。

方法：

(ⅰ)由訓(xùn)練數(shù)據(jù)集S，創(chuàng)建節(jié)點(diǎn)N，該結(jié)點(diǎn)包含所有的訓(xùn)練數(shù)據(jù)集中所有數(shù)據(jù)樣本；

( ⅱ)if S都在同一個(gè)類C，則返回N，并把該結(jié)點(diǎn)作為葉子節(jié)點(diǎn)，使用類C標(biāo)記。

(ⅲ)else if A為空then返回N作為葉子節(jié)點(diǎn)，并以S中大多數(shù)樣本所在的類別標(biāo)記它或給出類分布。

(ⅳ)else統(tǒng)計(jì)侯選屬性集合A中每個(gè)屬性取值個(gè)數(shù)，即均衡化因子f（N）取為屬性值個(gè)數(shù)n，并和A_Importance一起利用公式：

gain（屬性）=（I（分類屬性）-（1-α）E（屬性）/f（N）其中α是該屬性重要度，f（N）是均衡化因子，其中f （N）=n，n表示每個(gè)屬性取值個(gè)數(shù)。計(jì)算侯選屬性集合A中每個(gè)侯選屬性的信息增益，把信息增益最大的屬性選出作為測(cè)試屬性Test_A。

■使用屬性Test_A標(biāo)記N；并根據(jù)屬性Test_A中每個(gè)屬性值ai，劃分訓(xùn)練數(shù)據(jù)集S；相應(yīng)的，由結(jié)點(diǎn)N生長(zhǎng)一個(gè)條件為Test_A=ai的分枝；

■設(shè)Si是訓(xùn)練數(shù)據(jù)集S中屬性Test=ai的樣本數(shù)據(jù)的集合；如果Si為空則去掉該分枝或用S中大多數(shù)數(shù)據(jù)所在的類別標(biāo)記；else加上一個(gè)由Gen_User_Dec_Tree（Si，A-Test_A，A_Importance-Test_A_Importance）返回的子樹或結(jié)點(diǎn)。

3　基于用戶領(lǐng)域知識(shí)決策樹算法一個(gè)實(shí)際應(yīng)用

由于本科畢業(yè)設(shè)計(jì)（論文）成績(jī)一般從三方面考慮：①指導(dǎo)教師對(duì)學(xué)生的評(píng)價(jià)的有關(guān)數(shù)據(jù)并建議成績(jī)等級(jí)。主要從完成“畢業(yè)論文任務(wù)”規(guī)定工作情況、學(xué)習(xí)態(tài)度、創(chuàng)新性評(píng)價(jià)、寫作的規(guī)范性程度、存在的問題等方面。②評(píng)閱教師對(duì)設(shè)計(jì)（論文）評(píng)閱的情況并建議成績(jī)等級(jí)，主要從論文選題的價(jià)值與意義、創(chuàng)新性評(píng)價(jià)、工作量的大小、寫作規(guī)范化程度等各方面。③答辯小組對(duì)答辯情況的簡(jiǎn)述并建議成績(jī)等級(jí)，主要從答辯態(tài)度、知識(shí)面、邏輯思維能力、口頭表達(dá)能力、回答問題是否正確、語(yǔ)言是否流暢、對(duì)論文不足的認(rèn)識(shí)、有關(guān)軟件和硬件的演示情況的各方面考慮；三部分成績(jī)組成學(xué)生的最終成績(jī)。但不同單位，三部分成績(jī)的比例不同，各種各樣。

由于本科畢業(yè)論文成績(jī)是由答辯小組決定的，為此筆者設(shè)計(jì)一個(gè)調(diào)查問卷，在畢業(yè)論文答辯時(shí)發(fā)給每個(gè)答辯小組，在答辯時(shí)要求答辯老師給予填寫。調(diào)查表有關(guān)屬性如下：學(xué)號(hào)、姓名、論文題目、論文格式（符合、基本符合、不符合）、論文有無創(chuàng)新（有、無）、論文的工作量（大、適中、?。?、論文的實(shí)用價(jià)值（很大、一般）、答辯情況（好、一般、差）、論文的最終成績(jī)（優(yōu)、良、中、及格）。

從2014電子信息本科1班抽查若干名畢業(yè)設(shè)計(jì)答辯情況調(diào)查表和最終成績(jī)，并綜合考慮，經(jīng)過屬性相關(guān)性分析（去除不相關(guān)和弱相關(guān)的屬性如學(xué)號(hào)、姓名、論文題目）、數(shù)據(jù)預(yù)處理（由于論文的格式由論文指導(dǎo)老師已經(jīng)按要求對(duì)學(xué)生的論文進(jìn)行嚴(yán)格把握，論文格式都基本符合論文要求，在此刪除；對(duì)有關(guān)空缺值，根據(jù)畢業(yè)論文指導(dǎo)手冊(cè)對(duì)有關(guān)數(shù)據(jù)進(jìn)行補(bǔ)充或刪除數(shù)據(jù)差別較大的數(shù)據(jù)值），數(shù)據(jù)轉(zhuǎn)換后得到如下20名學(xué)生畢業(yè)設(shè)計(jì)答辯情況調(diào)查表和論文的最終成績(jī)，并整理如表1。

表1　從2014電子信息本科1班畢業(yè)設(shè)計(jì)中抽查20名畢業(yè)設(shè)計(jì)情況調(diào)查表和最終成績(jī)

其中分類屬性為論文的最終成績(jī)，其中優(yōu)秀4個(gè)，良好6個(gè)，中等7個(gè)，及格3個(gè)。

首先，樣本分類所需的期望信息為：

其次，在構(gòu)建判定樹時(shí)，特別給畢業(yè)設(shè)計(jì)中屬性有無創(chuàng)新，增加一定的屬性重要性因子α，說明在計(jì)算信息增益時(shí)強(qiáng)調(diào)其重要性，為了避免信息增益度量有傾斜具有許多值的屬性，在計(jì)算信息增益時(shí)增加屬性均衡化函數(shù) f（N）=N，即除以該屬性的值的個(gè)數(shù)N，從而降低多值屬性對(duì)分類的影響。使用公式如下計(jì)算每個(gè)屬性的信息熵：

gain（屬性）=（I（分類屬性）-（1-α）E（屬性））/N，其中α是屬性重要度因子，N是均值化函數(shù)，簡(jiǎn)單取為該屬性的不同值的個(gè)數(shù)。

在下面的計(jì)算時(shí)，除了創(chuàng)新有無屬性設(shè)α= 0.5之外，其余屬性無屬性重要度要求，另外，為了快速構(gòu)建決策樹和去除噪聲，設(shè)用戶的閾值為85%（即在要分類樣本中，若有某一類的樣本數(shù)占全部樣本數(shù)的85%則停止該子樹的構(gòu)建）。

根據(jù)候選屬性論文內(nèi)容有無創(chuàng)新。統(tǒng)計(jì)屬性論文內(nèi)容有無創(chuàng)新的每個(gè)樣本值：有創(chuàng)新和無創(chuàng)新，分別計(jì)算期望信息。

對(duì)于論文中有創(chuàng)新：優(yōu)秀的有2個(gè)，良好的有4個(gè)，沒有中等和及格的，則有：

對(duì)于論文中無創(chuàng)新的：成績(jī)優(yōu)秀的有2個(gè)，良好的有2個(gè)，中等的有7個(gè)，及格的有3個(gè)，則有：

則如果樣本按論文有無創(chuàng)新劃分，對(duì)此分類所需的期望信息為：

因此，由于創(chuàng)新屬性的重要性設(shè)為0.5，故這種劃分的信息增益是

Gain（創(chuàng)新）=（I（s1，s2，s3.s4）-（1-0.5）E（創(chuàng)新）/2=0.582 9。

同理，由于其余屬性的重要性看為同等重要都設(shè)為0，使用ID3算法計(jì)算其信息增益，可得：

Gain（實(shí)用價(jià)值）=（I（s1，s2，s3.s4）-E（實(shí)用價(jià)值）/2=0.123 4；

Gain（工作量）=（I（s1，s2，s3.s4）-E（工作量）/3=0.106 4；

Gain（答辯情況）=（I（s1，s2，s3.s4）-E（答辯情況）/3=0.212 4。

比較上面四種屬性的信息增益，創(chuàng)新性屬性的信息增益最大，因此按設(shè)計(jì)有無創(chuàng)新屬性劃分實(shí)例樣本，并對(duì)每一個(gè)劃分后的樣本空間，使用上面同樣的方法，構(gòu)件判定樹的各分枝，最終構(gòu)建判定樹如圖1?；趥鹘y(tǒng)ID3構(gòu)建的決策數(shù)如圖2。

圖1　基于強(qiáng)調(diào)創(chuàng)新屬性α=0.5構(gòu)建的畢業(yè)設(shè)計(jì)（論文）成績(jī)決策樹

圖2　基于傳統(tǒng)ID3算法構(gòu)建的決策樹

比較圖1和圖2：圖1的創(chuàng)新結(jié)點(diǎn)提升到根結(jié)點(diǎn)，而具有多值屬性的論文答辯情況下降為第二層，說明圖1更強(qiáng)調(diào)創(chuàng)新在畢業(yè)論文成績(jī)中的作用，同時(shí)它也避免了多值屬性對(duì)決策樹的影響，更符合當(dāng)今強(qiáng)調(diào)創(chuàng)新精神社會(huì)中對(duì)大學(xué)生的要求，比較符合現(xiàn)今高校評(píng)價(jià)學(xué)生畢業(yè)論文的標(biāo)準(zhǔn)。

把圖1決策樹生成的分類規(guī)則，應(yīng)用到其它畢業(yè)設(shè)計(jì)（論文）的成績(jī)中進(jìn)行準(zhǔn)確評(píng)估，準(zhǔn)確率達(dá)95%以上，當(dāng)然對(duì)于與實(shí)際成績(jī)不一致，也可以提供修改參考，分析其中的原由，并適當(dāng)?shù)倪M(jìn)行調(diào)整，從而更客觀的評(píng)定學(xué)生畢業(yè)設(shè)計(jì)（論文）成績(jī)。

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

本文對(duì)ID3算法進(jìn)行優(yōu)化，增加屬性重要性因子和屬性均衡化函數(shù)，增加重要屬性對(duì)分類的影響，同時(shí)也降低了多值屬性對(duì)分類的影響，并構(gòu)建自己的改進(jìn)算法，且利用該算法對(duì)我校畢業(yè)生畢業(yè)設(shè)計(jì)（論文）成績(jī)進(jìn)行深入的挖掘，構(gòu)建出對(duì)應(yīng)的決策樹，并提取出相應(yīng)的分類規(guī)則且把它應(yīng)用于實(shí)踐，取得很好的效果，符合我校的實(shí)際情況。對(duì)現(xiàn)實(shí)中提取的數(shù)據(jù)集，應(yīng)用這種增加屬性重要性因子和屬性均衡化函數(shù)改進(jìn)方法，更符合客觀現(xiàn)實(shí)情況的決策，準(zhǔn)確率也較高。

［1］ Han J W，Kamber M.數(shù)據(jù)挖掘（概念與技術(shù)）［M］.北京：機(jī)械工業(yè)出版社，2006.

［2］ K.P.Soman Shyam Diwakar V.Ajay.數(shù)據(jù)挖掘基礎(chǔ)教程［M］.北京：機(jī)械工業(yè)出版社，2011.

［3］ Breiman L，F(xiàn)riedman J H，Olshen R A，and Stone C J.Classification and Regression Trees［J］.Wadsworth，Belmont，1984.

［4］ Mehta M，Agrawal R.SLIQ：A fast scalable classifier for data mining［J］.int.conf.EDBT'96 28.

［5］ 魯為，王樅.決策樹的優(yōu)化及比較.計(jì)算機(jī)工程，2007，33（16）：

［6］ 張琳，陳燕，李桃迎，等.決策樹分類算法研究［J］.計(jì)算機(jī)工程，2011，37（13）：66-67，70.

［7］ 李道國(guó)，苗奪謙，俞冰.決策樹剪枝算法的研究與改進(jìn)［J］.計(jì)算機(jī)工程，2005，31（8）：19-21.

［8］ 謝妞妞，劉於勛.決策樹屬性選擇標(biāo)準(zhǔn)的改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（34）：115-118，139.

［9］ 喻金平，黃細(xì)妹，李康順.基于一種新的屬性選擇標(biāo)準(zhǔn)的ID3改進(jìn)算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29 （8）：2895-2898，2908.

［10］孫淮寧，胡學(xué)鋼.一種基于屬性貢獻(xiàn)度的決策樹學(xué)習(xí)算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，32 （8）：1137-1141.

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

Study and application on the ID3 algorithm optimization based on user field knowledge

WANG Sen，ZHAO Fa-yong，CHEN Shu-guang

（School of Physics and Electonic Engineering，F(xiàn)uyang Normal University，F(xiàn)uyang Anhui 236041，China）

This paper introduces attribute importance factor and equalization function in ID3 algorithm，to optimize the ID3 algorithm.Improves on the classical decision tree algorithm requires that shortcomings of each attribute to the class attribute with the same importance，can be used in different attributes to the class attribute，but also make up for the disadvantages that the ID3 algorithm tends to multi valued attributes.At last，the process of constructing the decision tree is given，and the decision tree constructed by the classical ID3 algorithm is compared with the decision tree in the new method，which proved that there are more application fields and the more suited to the needs of users.

decision tree；ID3Algorithm；attribute importance；function of equilibrium；

中文分類號(hào)：TP391.6A

1004-4329（2016）02-065-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）02-065-05

2015-10-25

安徽省科技攻關(guān)項(xiàng)目（12010302080）資助。

王森（1973－），男，碩士，講師，研究方向：數(shù)據(jù)挖掘、軟件工程。