王會(huì)青,陳俊杰,侯曉晶,郭 凱

(太原理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原030024)

分類是數(shù)據(jù)挖掘中一種重要的分析方法,通過學(xué)習(xí)訓(xùn)練集構(gòu)造一個(gè)分類函數(shù)或分類模型,利用分類函數(shù)或模型對測試數(shù)據(jù)集進(jìn)行分類[1]。分類可用于預(yù)測,預(yù)測的目的是從歷史數(shù)據(jù)記錄中自動(dòng)推導(dǎo)出對給定數(shù)據(jù)的趨勢描述,從而能對未來數(shù)據(jù)進(jìn)行預(yù)測。目前分類算法主要有決策樹方法、神經(jīng)網(wǎng)絡(luò)方法、統(tǒng)計(jì)方法等[2],不同方法會(huì)產(chǎn)生不同的分類器,分類器的優(yōu)劣直接影響數(shù)據(jù)挖掘的效率與準(zhǔn)確性。決策樹方法是一種經(jīng)典的分類算法,具有較好地處理缺省數(shù)據(jù)及帶有噪聲數(shù)據(jù)的能力。

ID3算法是由Quinlan提出的一種基于信息熵的決策樹學(xué)習(xí)算法[2]。該算法以信息論為基礎(chǔ),把信息熵作為選擇測試屬性標(biāo)準(zhǔn),對訓(xùn)練實(shí)例集進(jìn)行歸納分類。但是在選擇測試屬性時(shí),ID3算法往往偏向于選擇取值較多的屬性,而屬性值較多的屬性卻不一定是最優(yōu)的屬性[4]。為了克服ID3算法在選擇屬性中存在的缺點(diǎn),引入OneR算法來選擇相關(guān)屬性子集,降低無關(guān)屬性或重復(fù)屬性在分類中的影響,優(yōu)化分類結(jié)果。

1 ID3算法

在決策樹歸納方法中,通常使用信息增益方法來幫助確定生成每個(gè)結(jié)點(diǎn)時(shí)所應(yīng)選擇的合適屬性。該方法選擇具有最高信息增益的屬性作為當(dāng)前結(jié)點(diǎn)的測試屬性,使劃分后的訓(xùn)練樣本子集進(jìn)行分類時(shí)所需要信息最小,利用該屬性劃分當(dāng)前樣本集合,使得所產(chǎn)生的每個(gè)樣本子集中的“不同類別混合程度”降為最低。ID3算法的基本原理為[5]：

設(shè)樣本集S是s個(gè)數(shù)據(jù)樣本的集合,假定有m個(gè)不同類Ci(i=1,2,…,m),si是Ci類的樣本數(shù),對樣本集S所期望的信息值I(s1,s2,…,sm)為：

式中,p i是任意樣本屬于Ci的概率：si/s。

設(shè)屬性A有v個(gè)不同值{a1,a2,…,av},利用屬性A可以將樣本集S劃分為v個(gè)子集{S1,S2,…,Sv},其中,Sj包含S中屬性A上具有aj值的樣本。如果屬性A被選為測試屬性,則這些子集對應(yīng)有包含集合S的結(jié)點(diǎn)生長出來的分支。

設(shè)sij是Sj中Ci類的樣本數(shù),則由屬性 A劃分成子集的熵為：

式中,p i,jw為子集Sj中任一個(gè)樣本屬于類別Ci的概率。

根據(jù)期望信息和熵值可以得到相應(yīng)的信息增益值,因此屬性A上的分支獲得的信息增益值為：

Gain(A)=I(s1,s2,…,sm)-E(A)

ID3算法采用自頂向下的搜索可能的決策空間,以信息增益作為選取最佳屬性的度量標(biāo)準(zhǔn),實(shí)現(xiàn)對數(shù)據(jù)樣本的歸納分類。

詳細(xì)算法[6]描述如下：

輸入：訓(xùn)練樣本,各屬性均取離散數(shù)值,可共歸納的候選屬性集為：attribute_list;

輸出：決策樹。

處理流程：

1)創(chuàng)建一個(gè)結(jié)點(diǎn)N;

2)若該結(jié)點(diǎn)中的所有樣本均為同一類別C,則返回N作為一個(gè)葉結(jié)點(diǎn)并標(biāo)志為類別C;

3)若attribute_list為空,則返回N作為一個(gè)葉結(jié)點(diǎn)并標(biāo)記為該結(jié)點(diǎn)所含樣本中類別個(gè)數(shù)最多的類別;

4)從attribute_list選擇一個(gè)信息增益最大的屬性test_attribute;

5)并將結(jié)點(diǎn)N標(biāo)記為test_attribute;

6)對于test_attribute中每一個(gè)已知取值ai,準(zhǔn)備劃分結(jié)點(diǎn)N所包含的樣本集;

7)根據(jù)test_attribute=ai條件,從結(jié)點(diǎn)N產(chǎn)生相應(yīng)的一個(gè)分支,以表示該測試條件;

8)設(shè)si為test_attribute=ai條件所獲得的樣本集合;

9)若si為空,則將相應(yīng)葉結(jié)點(diǎn)標(biāo)記為該結(jié)點(diǎn)所含樣本中類別個(gè)數(shù)最多的類別;

10)否則將相應(yīng)的葉結(jié)點(diǎn)標(biāo)記為Generate_decision_tree(si,attribute_list,test_attribute)返回值。

2 屬性選擇

由于ID3算法要處理多個(gè)屬性,其中部分屬性是無關(guān)或者重復(fù)屬性,因此需要進(jìn)行屬性選擇,忽略無關(guān)或者重復(fù)屬性,提高ID3算法的分類性能。本文在ID3算法中引入OneR算法,使生成決策樹時(shí)屬性值較少的屬性不會(huì)被屬性值較多且并不重要的屬性淹沒,最終使決策樹減少了對取值較多屬性的依賴性,從而盡可能地減少大數(shù)據(jù)掩蓋小數(shù)據(jù)的現(xiàn)象發(fā)生,解決ID3算法偏向于取值較多屬性的偏置問題。

OneR算法是一個(gè)簡單分類算法,其基本思想是對數(shù)據(jù)集中的每個(gè)屬性創(chuàng)建一個(gè)單層的分類器,然后比較每個(gè)屬性在訓(xùn)練集上所有分類器的錯(cuò)誤率,最終選擇分類效果最好的分類器作為分類策略,其處理流程[7]為：

For每一個(gè)屬性A

For屬性的每個(gè)取值VA,按如下方式產(chǎn)生規(guī)則：計(jì)算屬性的每個(gè)取值在每一類中的樣本數(shù)找出每個(gè)取值中樣本數(shù)最多的類別Cmax

產(chǎn)生規(guī)則：if A=VA,類別=Cmax.

End For

計(jì)算所有規(guī)則的錯(cuò)誤率,

End For

選擇錯(cuò)誤率最小的規(guī)則。

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)以開源的數(shù)據(jù)挖掘平臺(tái)Weka中分類平臺(tái)和UCI數(shù)據(jù)集為基礎(chǔ)。Weka是基于JAVA的工作平臺(tái),集合了大量能承擔(dān)數(shù)據(jù)挖掘任務(wù)的機(jī)器學(xué)習(xí)算法,包括對數(shù)據(jù)進(jìn)行預(yù)處理、分類、回歸、聚類、關(guān)聯(lián)規(guī)則以及在新的交互式界面上的可視化。在決策樹算法中,決策樹的復(fù)雜度和分類精度是需要考慮的兩個(gè)最重要因素。常用的評價(jià)指標(biāo)有：模型準(zhǔn)確性和預(yù)測準(zhǔn)確性,描述分類模型準(zhǔn)確預(yù)測新的或未知的數(shù)據(jù)類的能力。

實(shí)驗(yàn)1 采用氣候訓(xùn)練集[8],如表1所示。

表1 氣候數(shù)據(jù)集

通過OneR算法對氣候數(shù)據(jù)集的各個(gè)屬性進(jìn)行篩選后,得到的評估參數(shù)如表2所示。

表2 評估參數(shù)

通過比較可知,風(fēng)力和氣溫的錯(cuò)誤率高于天氣和濕度的錯(cuò)誤率,需要降低風(fēng)力和氣溫屬性在分類中的重要性,相對地提高天氣和濕度屬性在分類中的作用。通過反復(fù)測試,經(jīng)OneR算法選擇天氣、濕度和風(fēng)力屬性作為ID3算法的分類屬性。

從ID3分類算法的模型準(zhǔn)確率、未知率和運(yùn)行時(shí)間方面,ID3算法和優(yōu)化后ID3算法得到的分類結(jié)果如表3所示。

表3 分類結(jié)果比較

從表3中可以直觀地看出,優(yōu)化后的ID3算法降低了氣溫屬性在分類中的重要性,有效地提高了算法的分類準(zhǔn)確率。

實(shí)驗(yàn)2 從樣本個(gè)數(shù)、屬性個(gè)數(shù)、類的個(gè)數(shù),類的取值分布四個(gè)方面,在UCI數(shù)據(jù)庫中選取5個(gè)數(shù)據(jù)集,包括 mushroom,lymphography,splice,promoters和zoo,作為測試數(shù)據(jù),UCI數(shù)據(jù)集描述如表4所示。

表4 UCI數(shù)據(jù)集

采用10次交叉驗(yàn)證的方法,在5個(gè)UCI數(shù)據(jù)集上分別采用ID3算法和優(yōu)化后的ID3算法進(jìn)行分類,分類結(jié)果如表5所示。

表5 分類結(jié)果比較

根據(jù)表5的實(shí)驗(yàn)結(jié)果,與ID3算法相比,優(yōu)化后的ID3算法在分類準(zhǔn)確率上都有所提高,除數(shù)據(jù)集lymphography外,其他四個(gè)數(shù)據(jù)集的分類未知率都有所降低,且運(yùn)行時(shí)間基本上降低了50%以上,一定程度上降低了無關(guān)屬性或者重復(fù)屬性對分類的影響,克服了ID3算法取值偏置的缺陷,提高了ID3算法的性能和效率。

4 結(jié)束語

ID3算法是決策樹生成算法中提出最早最經(jīng)典的算法,為了避免噪聲和干擾屬性對數(shù)據(jù)分類的影響,在建立決策樹之前應(yīng)先進(jìn)行屬性選擇。針對ID3算法中存在的不足,引入OneR算法用于測試屬性的選擇,減少了ID3算法中對取值較多的屬性的依賴性,改善分類結(jié)果。實(shí)驗(yàn)結(jié)果表明,與ID3算法相比改進(jìn)后的方案有較高的準(zhǔn)確率,克服了ID3算法取值偏置問題,優(yōu)化了分類結(jié)果。但是,ID3算法只能對靜態(tài)數(shù)據(jù)集提取靜態(tài)的分類規(guī)則,如何解決變化的數(shù)據(jù)集及規(guī)則提取問題是未來研究的重點(diǎn)。

[1] 羅可,林睦綱,郗東妹.數(shù)據(jù)挖掘中分類算法綜述[J].計(jì)算機(jī)工程,2005,31(1)：3-6.

[2] 欒麗華,吉根林.決策樹分類技術(shù)研究[J].計(jì)算機(jī)工程,2004,30(9)：94-96.

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

[4] 毛國君,段立娟,王實(shí),等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社,2007：123-123.

[5] 朱明.數(shù)據(jù)挖掘[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社,2002：67-68.

[6] HOLTE RC.Very simple classification rules perform well on most commonly used datasets[J].Machine learning,1993,l1(1)：63-91.

[7] 陳文偉,黃金才,趙新昱.數(shù)據(jù)挖掘技術(shù)[M].北京：北京工業(yè)大學(xué)出版社,2002：20-20.