唐耀先　余青松

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

0　引　言

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

在數(shù)據(jù)集的屬性中，并非所有的屬性都包含相同的信息量，有些屬性包含較多會(huì)影響分類(lèi)的信息量，而另外一些屬性包含較少會(huì)影響分類(lèi)的信息量[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)造決策樹(shù)模型產(chǎn)生不良影響。

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

1　C4.5決策樹(shù)算法

1.1　決策樹(shù)介紹[10]

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

圖1　決策樹(shù)模型圖

1.2　C4.5決策樹(shù)生成

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

一個(gè)數(shù)據(jù)集本身有很多屬性，我們需要考慮屬性進(jìn)行判斷的順序，ID3算法引進(jìn)了信息增益來(lái)量化屬性對(duì)類(lèi)別的影響程度，并將信息增益作為屬性選擇的度量標(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使用信息增益率來(lái)量化屬性對(duì)類(lèi)別的影響程度，并將信息增益率作為屬性選擇的度量標(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)行搜索，在搜索的過(guò)程中使用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]。在搜索的過(guò)程中使用CFS評(píng)估算法，評(píng)估從初始節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的最佳路徑代價(jià)。

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

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

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

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

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

(7)

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

(8)

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

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

(9)

2.3　DTEAT的算法流程

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

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

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

輸出：一棵決策樹(shù)T。

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

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

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

步驟4對(duì)于A中的每一個(gè)屬性，利用式(9)計(jì)算屬性對(duì)類(lèi)產(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ù)最大的類(lèi)別，由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)建決策樹(shù)T，返回T。

步驟7對(duì)節(jié)點(diǎn)Nk,以Dk作為訓(xùn)練集，A-Aj為特征集，遞歸調(diào)用步驟1-步驟6，得到子樹(shù)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分類(lèi)平臺(tái)和UCI數(shù)據(jù)集。Weka是新西蘭大學(xué)提出的基于Java的開(kāi)源開(kāi)發(fā)平臺(tái)，集合了包括數(shù)據(jù)預(yù)處理、分類(lèi)、回歸、聚類(lèi)、關(guān)聯(lián)規(guī)則等大量的機(jī)器學(xué)習(xí)算法，并實(shí)現(xiàn)了交互式界面上的可視化[13]。UCI是加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫(kù)，種類(lèi)涉及生活、工程、科學(xué)各個(gè)領(lǐng)域。它已被學(xué)生、教育工作者和其他研究機(jī)器學(xué)習(xí)的研究者作為數(shù)據(jù)來(lái)源廣泛使用。本文的實(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所示。屬性選擇是直接剔除掉一部分與類(lèi)別依賴度低，但是相互之間依賴度高的屬性，而剩下的屬性之間依舊會(huì)有一定依賴度，因此在分類(lèi)算法中消除屬性間依賴度的影響還是很有必要。

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

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

圖2　ROC曲線圖

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

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

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

兩種算法在7組數(shù)據(jù)集上的分類(lèi)準(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算法通過(guò)計(jì)算屬性間的信息增益率來(lái)量化屬性間的依賴度。在構(gòu)造決策樹(shù)的過(guò)程中把待分裂屬性與其他屬性間的依賴度均值作為選擇分裂屬性時(shí)的主要度量標(biāo)準(zhǔn)之一。將屬性間依賴關(guān)系對(duì)選擇

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

4　結(jié)　語(yǔ)

本文是基于C4.5算法在選擇分裂屬性時(shí)忽視屬性間的相互影響這一不足，提出了消除屬性依賴的DTEAT算法。在構(gòu)造決策樹(shù)的過(guò)程中，通過(guò)計(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算法在消除屬性依賴后的分類(lèi)準(zhǔn)確率有了明顯提升，即DTEAT算法減少了屬性間依賴對(duì)分裂屬性的選擇產(chǎn)生的影響，從而提高了最終的分類(lèi)準(zhǔn)確率。目前，本文提出的消除屬性依賴的改進(jìn)算法每一次選擇分裂屬性時(shí)，都要多計(jì)算一次屬性間的增益率，算法效率有所降低。如何在消除屬性依賴提高分類(lèi)準(zhǔn)確率的同時(shí)兼顧算法的效率是需要進(jìn)一步研究的問(wèn)題。

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

[2] 姚亞夫,邢留濤.決策樹(shù)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決策樹(shù)的流量分類(lèi)方法[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] 馮少榮.決策樹(shù)算法的研究與改進(jìn)[J].廈門(mén)大學(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基因分類(lèi)方法[J].信息化建設(shè),2016(5):30-32.

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

[12] 楊青松.爬蟲(chóng)技術(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-均值聚類(lèi)算法[J].北京聯(lián)合大學(xué)學(xué)報(bào),2016(4):53-57.