唐耀先　余青松

(華東師范大學(xué)計(jì)算中心　上海 200062)

0　引　言

近年來，先進(jìn)的數(shù)據(jù)存儲(chǔ)技術(shù)使人們能快速地搜集和存儲(chǔ)海量的數(shù)據(jù)信息，促進(jìn)了數(shù)據(jù)挖掘技術(shù)的飛速發(fā)展。分類是數(shù)據(jù)挖掘中的重要研究方向之一，主要的分類算法有決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡(luò)、K-近鄰、支持向量機(jī)等[1]。其中，決策樹以其預(yù)測(cè)準(zhǔn)確率高、穩(wěn)定性好、直觀易懂等特點(diǎn)得到廣泛應(yīng)用和研究[2]。應(yīng)用如文獻(xiàn)[3]利用決策樹進(jìn)行水質(zhì)建模測(cè)試；文獻(xiàn)[4]利用決策樹處理流量分類問題；文獻(xiàn)[5]利用決策樹探究人體測(cè)量。研究上如文獻(xiàn)[6]在1993年提出的C4.5算法解決了連續(xù)屬性值的處理問題和多值偏向問題；文獻(xiàn)[7]把線性分類器和決策樹結(jié)合在一起減少?zèng)Q策樹的層數(shù)提高了決策樹效率；文獻(xiàn)[8]通過控制高維數(shù)據(jù)噪聲來優(yōu)化C4.5算法。但上述算法在構(gòu)造決策樹模型的過程中，選擇分裂屬性時(shí)僅僅只是考慮了屬性對(duì)類的影響，卻忽視了屬性之間的相互影響。

在數(shù)據(jù)集的屬性中，并非所有的屬性都包含相同的信息量，有些屬性包含較多會(huì)影響分類的信息量，而另外一些屬性包含較少會(huì)影響分類的信息量[9]。同樣，在數(shù)據(jù)集中選擇一個(gè)待分裂屬性后，剩下的屬性集中，有的屬性包含較多會(huì)影響待分裂屬性取值的信息量，而另外一些屬性包含較少會(huì)影響待分裂屬性取值的信息量。例如學(xué)生有“年齡”和“年級(jí)”兩個(gè)屬性，年齡“大小”會(huì)影響到學(xué)生的年級(jí)“高低”，所以這兩個(gè)屬性之間有一定的影響，即它們有一定的依賴關(guān)系。上述例子只是一個(gè)極端的例子，本文認(rèn)為任何兩個(gè)屬性或多或少都具有一定的依賴關(guān)系，并且定義這種依賴關(guān)系為依賴度，而依賴度會(huì)成為選擇分裂屬性的影響因素之一，忽視這種影響因素會(huì)對(duì)構(gòu)造決策樹模型產(chǎn)生不良影響。

本文針對(duì)上述問題，提出一種消除屬性依賴的C4.5決策樹改進(jìn)算法，稱之為DTEAT算法。DTEAT算法通過計(jì)算屬性間的信息增益率來量化屬性間的依賴度，在構(gòu)造決策樹的過程中把待分裂屬性與其他屬性間的依賴度均值作為選擇分裂屬性時(shí)的主要度量標(biāo)準(zhǔn)之一，從而消除屬性間依賴關(guān)系對(duì)選擇分裂屬性時(shí)產(chǎn)生的影響，以達(dá)到提高最終模型分類準(zhǔn)確率的目的。

1　C4.5決策樹算法

1.1　決策樹介紹[10]

決策樹是一種類似流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)(非樹葉節(jié)點(diǎn))表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，而每個(gè)葉子節(jié)點(diǎn)存放一個(gè)類標(biāo)號(hào)。一旦建立好了決策樹，對(duì)于一組未給定類標(biāo)號(hào)的數(shù)據(jù)，跟蹤一條由根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，該葉子節(jié)點(diǎn)就存放著該數(shù)據(jù)分類的預(yù)測(cè)。決策樹的優(yōu)勢(shì)在于不需要任何領(lǐng)域知識(shí)或參數(shù)設(shè)置，適合于探測(cè)性的知識(shí)發(fā)現(xiàn)。圖1就是一棵典型的C4.5算法對(duì)數(shù)據(jù)集產(chǎn)生的決策樹。

圖1　決策樹模型圖

1.2　C4.5決策樹生成

設(shè)有數(shù)據(jù)集D，|D|為D的樣本總數(shù)。設(shè)類別C有m個(gè)不同的取值{C1,C2,…,Ci,…,Cm}，|Ci|為D中屬于類Ci的樣本總數(shù)。設(shè)有n個(gè)不同的屬性{Aj1,Aj2,…,Ajk,…,Ajt}，屬性Aj有t個(gè)不同的取值{aj1,aj2,…,ajk,…,ajt}，|Djk|為D中屬性Aj取值為ajk的子集Djk的樣本總數(shù)，|Dijk|為在Djk中屬于類Ci的樣本總數(shù)。

一個(gè)數(shù)據(jù)集本身有很多屬性，我們需要考慮屬性進(jìn)行判斷的順序，ID3算法引進(jìn)了信息增益來量化屬性對(duì)類別的影響程度，并將信息增益作為屬性選擇的度量標(biāo)準(zhǔn)[11]。在給定Aj的條件下，C在D中的信息增益計(jì)算公式為：

Gain(C,D|Aj)=Info(C,D)-Info(C,D|Aj)

(1)

式中：Info(C,D)為C在D中的信息熵，Info(C,D|Aj)為給定屬性Aj的條件下，C在D中的信息熵：

(2)

(3)

則信息增益最終的計(jì)算公式為：

(4)

C4.5使用信息增益率來量化屬性對(duì)類別的影響程度，并將信息增益率作為屬性選擇的度量標(biāo)準(zhǔn)，計(jì)算公式為：

(5)

式中：Info(Aj,D)為屬性Aj在D中的信息熵：

(6)

2　DTEAT算法

2.1　最優(yōu)屬性選擇

屬性選擇使用BFS(Best First Search)算法對(duì)屬性集進(jìn)行搜索，在搜索的過程中使用CFS(Correlation-base Feature Selector)算法對(duì)屬性進(jìn)行評(píng)估選擇。

BFS是寬度優(yōu)先搜索的擴(kuò)展，基本思想是將節(jié)點(diǎn)表按據(jù)目標(biāo)的距離進(jìn)行排序，再以節(jié)點(diǎn)的估計(jì)距離為標(biāo)準(zhǔn)選擇待擴(kuò)展的節(jié)點(diǎn)[12]。在搜索的過程中使用CFS評(píng)估算法，評(píng)估從初始節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的最佳路徑代價(jià)。

CFS評(píng)估算法評(píng)估每個(gè)屬性的預(yù)測(cè)能力以及相互之間的依賴度，傾向于選擇與類別依賴度高，但是相互之間依賴度低的屬性。

通過屬性選擇，先剔除掉與類別依賴度低或者相互之間依賴度高的屬性，提高算法的效率，并且完成一次屬性依賴的消除。

2.2　DTEAT的改進(jìn)思想

信息增益率表示的是在給定一個(gè)屬性條件下，類不確定性相對(duì)于沒有屬性限定條件時(shí)的減少量，即類對(duì)該屬性的依賴度。同理在給定屬性Ax的條件下，另一個(gè)屬性Aj在D中的信息增益率即可表示屬性Aj對(duì)屬性Ax依賴度。

根據(jù)式(5)，屬性Aj對(duì)屬性Ax依賴度公式為：

(7)

則屬性Ax與其他所有屬性的平均依賴度公式為：

(8)

式中：E為不包含Aj的屬性子集，|E|為集合E的屬性總數(shù)。

在選擇分裂屬性的時(shí)候不僅要考慮該屬性給類帶來最大的信息增益率，也必須考慮該屬性和其他屬性有最小的信息增益率，即該屬性與其他屬性有最小的平均依賴度。本文提出新的選擇分裂屬性的信息增益率公式：

(9)

2.3　DTEAT的算法流程

假設(shè)D代表當(dāng)前樣本集，當(dāng)前候選屬性集用A表示，則DTEAT算法見算法1。

算法1使用訓(xùn)練數(shù)據(jù)集構(gòu)建決策樹

輸入：訓(xùn)練樣本D；候選屬性的集合A。

輸出：一棵決策樹T。

步驟1創(chuàng)建節(jié)點(diǎn)N。

步驟2如果D中的所有實(shí)例都屬于同一類別Ci，則將N標(biāo)記為Ci類葉節(jié)點(diǎn)，構(gòu)建T為只包含N的單節(jié)點(diǎn)樹，返回決策樹T。

步驟3如果A為空，或者D中所有實(shí)例在A上取值相同，則將N標(biāo)記葉節(jié)點(diǎn)，其類別標(biāo)記D中實(shí)例數(shù)最大的類，置T為只包含N的單節(jié)點(diǎn)樹，返回決策樹T。

步驟4對(duì)于A中的每一個(gè)屬性，利用式(9)計(jì)算屬性對(duì)類產(chǎn)生的信息增益率GainRatioNew(C,D|Aj)，選擇具有最高信息增益率的屬性Aj作為節(jié)點(diǎn)N的待分裂屬性。

步驟5如果待分裂屬性Aj為連續(xù)型，則找到Aj的分割閾值。

步驟6對(duì)于屬性Aj的每一個(gè)屬性值ajk，從節(jié)點(diǎn)N生成對(duì)應(yīng)的子節(jié)點(diǎn)，并從D中劃分出對(duì)應(yīng)的子集Dk。如果Dk非空，構(gòu)建子節(jié)點(diǎn)Nk，將其標(biāo)記為Dk中實(shí)例數(shù)最大的類別，由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)建決策樹T，返回T。

步驟7對(duì)節(jié)點(diǎn)Nk,以Dk作為訓(xùn)練集，A-Aj為特征集，遞歸調(diào)用步驟1-步驟6，得到子樹Tk,返回Tk。

步驟8對(duì)T進(jìn)行剪枝處理。

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

3.1　實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集介紹

實(shí)驗(yàn)使用Weka分類平臺(tái)和UCI數(shù)據(jù)集。Weka是新西蘭大學(xué)提出的基于Java的開源開發(fā)平臺(tái)，集合了包括數(shù)據(jù)預(yù)處理、分類、回歸、聚類、關(guān)聯(lián)規(guī)則等大量的機(jī)器學(xué)習(xí)算法，并實(shí)現(xiàn)了交互式界面上的可視化[13]。UCI是加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫，種類涉及生活、工程、科學(xué)各個(gè)領(lǐng)域。它已被學(xué)生、教育工作者和其他研究機(jī)器學(xué)習(xí)的研究者作為數(shù)據(jù)來源廣泛使用。本文的實(shí)驗(yàn)環(huán)境如表1所示。

表1　實(shí)驗(yàn)環(huán)境

本文使用UCI官方提供的Audiology、Heart-c、heart-h、Labor、Soybean、Splice、Vehicle等7組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，各個(gè)數(shù)據(jù)的樣本總數(shù)和屬性總數(shù)如表2所示。

表2　數(shù)據(jù)集樣本數(shù)和屬性總數(shù)

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

實(shí)驗(yàn)一：對(duì)上述7組數(shù)據(jù)集進(jìn)行屬性選擇。首先使用BFS算法進(jìn)行屬性搜索，然后使用CFS算法進(jìn)行屬性評(píng)估，選擇最優(yōu)的訓(xùn)練屬性集。各組數(shù)據(jù)集剩余的最優(yōu)屬性總數(shù)如表3所示。屬性選擇是直接剔除掉一部分與類別依賴度低，但是相互之間依賴度高的屬性，而剩下的屬性之間依舊會(huì)有一定依賴度，因此在分類算法中消除屬性間依賴度的影響還是很有必要。

表3　屬性選擇之后的數(shù)據(jù)集

實(shí)驗(yàn)二：數(shù)據(jù)集Labor具有57個(gè)樣本，屬性選擇后具有7個(gè)最優(yōu)屬性，是一個(gè)二分類的經(jīng)典數(shù)據(jù)集，只包含good和bad兩種類別。本實(shí)驗(yàn)分別使用C4.5算法和DTEAT算法對(duì)屬性選擇后的該數(shù)據(jù)集進(jìn)行分類，通過設(shè)置不同的閾值得到真正例率TP Rate和假正例率FP Rate，分別繪制C4.5和DTEAT兩種分類模型的ROC平滑曲線圖，如圖2所示。

圖2　ROC曲線圖

ROC曲線即接受者操作特征曲線，表明了假正例率與真正例率之間的關(guān)系。ROC曲線可以用來判斷分類方法的性能，ROC曲線下方包圍的面積(AUC)越大，分類效果越好。本次實(shí)驗(yàn)計(jì)算出利用C4.5算法模型進(jìn)行分類時(shí)，AUC的值為0.733 1，而利用DTEAT算法模型進(jìn)行分類，AUC的值為0.812 9。DTEAT算法模型的AUC值明顯大于C4.5算法模型的AUC值，由此可知DTEAT算法的分類效果比C4.5算法的分類效果好。

實(shí)驗(yàn)三：分別使用傳統(tǒng)C4.5決策樹算法和消除屬性依賴的DTEAT算法在進(jìn)行屬性選擇后的7組數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，然后通過十字交叉驗(yàn)證法計(jì)算分類準(zhǔn)確率，最后對(duì)比兩種算法的分類準(zhǔn)確率，如表4所示。

表4　C4.5算法改進(jìn)前后的準(zhǔn)確率　　　%

兩種算法在7組數(shù)據(jù)集上的分類準(zhǔn)確率對(duì)比如圖3所示。

圖3　C4.5算法改進(jìn)前后準(zhǔn)確率對(duì)比

根據(jù)圖3的實(shí)驗(yàn)結(jié)果，可以看出DTEAT算法相對(duì)于C4.5算法準(zhǔn)確率有了明顯的提升，準(zhǔn)確率最高提升了7.15個(gè)百分點(diǎn)，最少也提升了3.02個(gè)百分點(diǎn)，平均提升了4.43個(gè)百分點(diǎn)，即使是對(duì)于原算法準(zhǔn)確率高達(dá)94.49%的數(shù)據(jù)集Splice仍然有3個(gè)百分點(diǎn)的提升。由此可知DTEAT算法通過計(jì)算屬性間的信息增益率來量化屬性間的依賴度。在構(gòu)造決策樹的過程中把待分裂屬性與其他屬性間的依賴度均值作為選擇分裂屬性時(shí)的主要度量標(biāo)準(zhǔn)之一。將屬性間依賴關(guān)系對(duì)選擇

分裂屬性時(shí)產(chǎn)生的影響進(jìn)行消除之后，有效地提升了分類的準(zhǔn)確率。

4　結(jié)　語

本文是基于C4.5算法在選擇分裂屬性時(shí)忽視屬性間的相互影響這一不足，提出了消除屬性依賴的DTEAT算法。在構(gòu)造決策樹的過程中，通過計(jì)算待分裂屬性與其他屬性間的信息增益率量化屬性間的依賴度，并且將屬性間依賴度均值作為選擇分裂屬性時(shí)的主要度量標(biāo)準(zhǔn)之一。在Weka實(shí)驗(yàn)平臺(tái)上對(duì)7組UCI官方數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)表明DTEAT算法在消除屬性依賴后的分類準(zhǔn)確率有了明顯提升，即DTEAT算法減少了屬性間依賴對(duì)分裂屬性的選擇產(chǎn)生的影響，從而提高了最終的分類準(zhǔn)確率。目前，本文提出的消除屬性依賴的改進(jìn)算法每一次選擇分裂屬性時(shí)，都要多計(jì)算一次屬性間的增益率，算法效率有所降低。如何在消除屬性依賴提高分類準(zhǔn)確率的同時(shí)兼顧算法的效率是需要進(jìn)一步研究的問題。

[1] 周美琴.單位代價(jià)收益敏感決策樹分類算法及其剪枝算法的研究[D].桂林:廣西師范大學(xué),2016.

[2] 姚亞夫,邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,42(12):3772-3776.

[3] Everaert G,Bennetsen E,Goethals P L M.An applicability index for reliable and applicable decision trees in water quality modelling[J].Ecological Informatics,2016,32:1-6.

[4] 徐鵬,林森.基于C4.5決策樹的流量分類方法[J].軟件學(xué)報(bào),2009,20(10):2692-2704.

[5] Savall F,Faruch-Bilfeld M,Dedouit F,et al.Metric sex determination of the human coxal bone on a virtual sample using decision trees[J].Journal of Forensic Sciences,2015,60(6):1395-1400.

[6] Quinlan J R.C4.5:programs for machine learning[M].Morgan Kaufmann Publishers Inc.1993.

[7] 馮少榮.決策樹算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)(自然版),2007,46(4):496-500.

[8] 王偉,李磊,張志鴻.具有容噪特性的C4.5算法改進(jìn)[J].計(jì)算機(jī)科學(xué),2015,42(12):268-271.

[9] 王培,金聰,葛賀賀.面向軟件缺陷預(yù)測(cè)的互信息屬性選擇方法[J].計(jì)算機(jī)應(yīng)用,2012,32(6):1738-1740.

[10] 王凱華,蔣逸恒,李迪.基于WEKA平臺(tái)的C4.5基因分類方法[J].信息化建設(shè),2016(5):30-32.

[11] 董躍華,劉力.結(jié)合矯正函數(shù)的決策樹優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(1):300-306.

[12] 楊青松.爬蟲技術(shù)在互聯(lián)網(wǎng)領(lǐng)域的應(yīng)用探索[J].電腦知識(shí)與技術(shù):學(xué)術(shù)交流,2016,12(15):62-64.

[13] 劉彩霞,方建軍,劉艷霞,等.Weka平臺(tái)上距離指數(shù)自動(dòng)尋優(yōu)的模糊C-均值聚類算法[J].北京聯(lián)合大學(xué)學(xué)報(bào),2016(4):53-57.