安葳鵬，程小博，劉 雨

河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作454000

1 引言

決策樹[1-2]算法在模式識(shí)別、機(jī)器學(xué)習(xí)、圖像處理和信息檢索等數(shù)據(jù)挖掘領(lǐng)域中是最有效、應(yīng)用最廣泛的技術(shù)之一。決策樹之所以成為流行的工具，不僅是因?yàn)樗哂休^高的準(zhǔn)確率和較少的參數(shù)，并且從基于特征的示例中提取的分類規(guī)則具有更好的可理解性，這在數(shù)據(jù)挖掘環(huán)境中是一個(gè)特別有吸引力的特性。決策樹算法具有直觀、精度高、生成模式簡單等優(yōu)點(diǎn)。

在決策樹算法中C4.5[3]算法使用最普遍，但算法仍存在一些不足：（1）算法在處理小規(guī)模缺失數(shù)據(jù)以及二義性數(shù)據(jù)不穩(wěn)定且效率低；（2）算法在分裂屬性時(shí)只考慮了條件屬性與決策屬性之間的關(guān)系，并沒有考慮到條件屬性與條件屬性之間的關(guān)系；（3）數(shù)據(jù)集樣本數(shù)過大時(shí)會(huì)使算法的計(jì)算量增大。

針對C4.5 算法存在的以上不足，很多學(xué)者對其進(jìn)行了深入的研究，其中Zhang 等[4]在垃圾郵件檢測中運(yùn)用C4.5 算法，引入成本矩陣，并且運(yùn)用K-fold 交叉驗(yàn)證減少樣本誤差，最后采用二進(jìn)制的PSO作為子集搜索策略。對于二義性數(shù)據(jù)得到很好的處理，但是對于缺失數(shù)據(jù)算法準(zhǔn)確率明顯下降。Wang 等[5]針對連續(xù)性數(shù)據(jù)對算法進(jìn)行改進(jìn)，給出了兩種啟發(fā)式的方法，用于分割決策樹節(jié)點(diǎn)，提高了算法的泛化能力，減小樹的大小，但是在分類精度上會(huì)明顯的降低。吳思博等[6]在決策樹ID3算法中引入斯皮爾曼等級系數(shù)，有效地解決了算法多值屬性偏向問題。姬楊蓓蓓等[7]和尹婷等[8]把貝葉斯決策樹算法分別運(yùn)用到交通事件持續(xù)時(shí)間預(yù)測和客戶流失中，可以更好地處理不一致、不完整和噪聲等干擾數(shù)據(jù)，分類的魯棒性更強(qiáng)。

本文提出了一種C4.5 算法和貝葉斯算法[9]相結(jié)合的方法，并在該基礎(chǔ)上引入Fleiss’Kappa[10]系數(shù)對算法進(jìn)行優(yōu)化。改進(jìn)后的算法解決了決策樹算法在處理小規(guī)模缺失數(shù)據(jù)以及二義性數(shù)據(jù)效率低的缺點(diǎn)，并對決策樹在處理?xiàng)l件屬性之間的關(guān)系上進(jìn)行了改進(jìn)，算法在損失一定效率的基礎(chǔ)上，大大提高其準(zhǔn)確率。

2 理論基礎(chǔ)

2.1 C4.5算法

設(shè)樣本數(shù)據(jù)集為D，N 為樣本數(shù)據(jù)集容量。設(shè)數(shù)據(jù)集D 中有M 類樣本，第k 類樣本的實(shí)例個(gè)數(shù)為Ck，則數(shù)據(jù)集D 的經(jīng)驗(yàn)熵[11]為：

設(shè)特征A 是離散的，根據(jù)特征A 的取值將數(shù)據(jù)集D 劃分為n 個(gè)子集，Ni為對應(yīng)的第i 個(gè)子集Di的個(gè)數(shù)，在集合Di中屬于第k 類樣本個(gè)數(shù)為Nik，則數(shù)據(jù)集對于特征A 的經(jīng)驗(yàn)條件熵為：

得到劃分屬性A 的信息增益為：

從而計(jì)算得到C4.5算法的信息增益率[12]為：

其中：

2.2 樸素貝葉斯算法

樸素貝葉斯算法具有處理小規(guī)模缺失數(shù)據(jù)以及二異數(shù)據(jù)穩(wěn)定且效率高的特點(diǎn)。

設(shè)樣本數(shù)據(jù)集T={(x1,y1),(x2,y2),…,(xn,yn)}由P(X,Y)獨(dú)立同分產(chǎn)生，為第i 個(gè)樣本的第j 個(gè)特征，其中為第j 個(gè)特征可能取到的第l 個(gè)值，j=1,2,…,n，l=1,2,…,sj，yi∈{c1,c2,…,cK}。則樸素貝葉斯步驟如下所示。

（1）計(jì)算先驗(yàn)概率的估計(jì)值以及條件概率[13]的估計(jì)值：

（2）對于給定的實(shí)例x=(x(1),x(2),…,x(n))T，計(jì)算：

（3）計(jì)算并返回x 的分類y：

2.3 Fleiss’Kappa系數(shù)

Fleiss’Kappa 系數(shù)是檢驗(yàn)試驗(yàn)標(biāo)注結(jié)果數(shù)據(jù)一致性比較重要的參數(shù)，對于評定條件屬性與條件屬性之間的相關(guān)程度有很大幫助。設(shè)N 為被評定對象的總數(shù)，n為評定對象的總數(shù)，k 為評定的等級數(shù)，nij為第j 個(gè)評定對象對第i 個(gè)被評對象劃分的等級數(shù)。則系數(shù)的計(jì)算公式為：

其中：

Fleiss’Kappa 系數(shù)計(jì)算結(jié)果一般為-1～1 之間，但通常會(huì)落到0～1 間，一般分為5 組來表示不同等級的一致性：0～0.20（極低的一致性）、0.21～0.40（一般的一致性）、0.41～0.60（中等一致性）、0.61～0.80（高度一致性）、0.81～1（幾乎完全一致）。

2.4 等級評定法

在數(shù)據(jù)集中，有些數(shù)據(jù)是非數(shù)字化的數(shù)據(jù)（例如在4.1節(jié)實(shí)驗(yàn)1中的西瓜數(shù)據(jù)集，數(shù)據(jù)部分都是文字類型的數(shù)據(jù)），會(huì)造成Fleiss’Kappa 系數(shù)計(jì)算的不便，因此要對這些非數(shù)字化的數(shù)據(jù)用等級評定法對其進(jìn)行數(shù)字化處理[14]。

設(shè)樣本數(shù)據(jù)集為D，根據(jù)數(shù)據(jù)集中的條件屬性中的特征A將樣本數(shù)據(jù)集劃分為n 個(gè)子集D1,D2,…,Dn，Ni為對應(yīng)Di的樣本個(gè)數(shù)。假設(shè)決策屬性被劃分為K個(gè)類別Bk，k=1,2,…,K，集合Di中屬于類Bk的樣本集合為Dik，樣本個(gè)數(shù)為Nik。首先設(shè)定B1的等級數(shù)最高，則Di中屬于類B1的個(gè)數(shù)所占的比例為Pi。假設(shè)i=3 可分為3種情況：

若P1＞P2＞P3，等級可劃分為1，2，3；

若P1=P2＞P3，等級可劃分為1.5，1.5，3；

若P1＞P2=P3，等級可劃分為1，2.5，2.5。

3 算法優(yōu)化

3.1 決策樹C4.5算法優(yōu)化

在決策樹C4.5算法的基礎(chǔ)上引入Fleiss’Kappa系數(shù)，算法步驟如下：

（1）根據(jù)等級評定法，對樣本數(shù)據(jù)進(jìn)行數(shù)字化處理，進(jìn)行等級劃分；

（2）依據(jù)劃分后的結(jié)果，通過公式（10）計(jì)算相關(guān)系數(shù)T；

（3）在公式（3）的基礎(chǔ)上引入系數(shù)T，信息增益率計(jì)算公式變?yōu)椋?/p>

3.2 貝葉斯決策樹優(yōu)化

在原有決策樹結(jié)構(gòu)的基礎(chǔ)上加入新的貝葉斯節(jié)點(diǎn)，該節(jié)點(diǎn)位于決策樹的兩個(gè)測試屬性之間，能夠根據(jù)貝葉斯算法計(jì)算此節(jié)點(diǎn)，因此稱為貝葉斯決策樹。貝葉斯決策樹結(jié)構(gòu)圖如圖1所示。

圖1 貝葉斯決策樹結(jié)構(gòu)

圖中可以看出，貝葉斯決策樹中的貝葉斯節(jié)點(diǎn)可以取兩個(gè)值分別為0值和f 值。0值表示貝葉斯節(jié)點(diǎn)不做任何運(yùn)算，f 值表示該節(jié)點(diǎn)需要經(jīng)過貝葉斯算法計(jì)算得到，并在決策樹屬性分裂中起關(guān)鍵作用。

貝葉斯決策樹算法優(yōu)化過程如下：

（1）對于完整的數(shù)據(jù)以及非二異的數(shù)據(jù)，直接用改進(jìn)的決策樹C4.5 算法選取屬性，對數(shù)據(jù)進(jìn)行分類，否則，跳轉(zhuǎn)步驟（2）；

（2）對于缺失數(shù)據(jù)以及在分類時(shí)存在二義性的數(shù)據(jù)，則需要計(jì)算f 值，根據(jù)屬性的先驗(yàn)概率，利用貝葉斯公式計(jì)算出后驗(yàn)概率，選出概率最大的一類。

3.人身損害。人身損害是受害人一方的生命權(quán)、健康權(quán)、身體權(quán)遭受損害產(chǎn)生的不利后果。例如第三人干擾婚姻關(guān)系導(dǎo)致過錯(cuò)方配偶產(chǎn)生厭惡等情緒而引發(fā)家庭暴力致使對方遭受人身損害，或者無過錯(cuò)方配偶因第三人干擾婚姻關(guān)系的行為受重大打擊進(jìn)行自殘或者自殺等情形，又或者與第三人發(fā)生正面沖突引起爭執(zhí)或者斗毆導(dǎo)致無過錯(cuò)方配偶遭受人身傷害。

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

4.1 實(shí)驗(yàn)1

實(shí)驗(yàn)選取GitHub 中的西瓜數(shù)據(jù)集，數(shù)據(jù)由條件屬性色澤、根蒂、敲聲、紋理、臍部、觸感、密度、含糖率以及決策屬性的好瓜構(gòu)成。實(shí)驗(yàn)數(shù)據(jù)如表1所示。

（1）計(jì)算Fleiss’Kappa系數(shù)：

從表2 中可以看出P（青綠）>P（烏黑）>P（淺白），同理得到在根蒂屬性中P（蜷縮）>P（稍蜷）>P（硬挺），在敲聲屬性中P（濁想）>P（沉悶）>P（清脆），在紋理屬性中P（清晰）>P（稍糊）>P（模糊），在臍部屬性中P（凹陷）>P（稍凹）>P（平坦），在觸感屬性中P（硬滑）>P（軟粘）。因此，可以得到數(shù)字化處理后的樣本數(shù)據(jù)表如表3所示。

表1 西瓜樣本數(shù)據(jù)集

表2 色澤評定結(jié)果

表3 等級評定結(jié)果

根據(jù)表3的數(shù)據(jù)，可以看做為17個(gè)專家對6項(xiàng)任務(wù)進(jìn)行3級評定，可以將表3的數(shù)據(jù)修改為表4的數(shù)據(jù)結(jié)果。

表4 轉(zhuǎn)換結(jié)果

運(yùn)用公式（10）、（11）以及（12）計(jì)算出Fleiss’Kappa系數(shù)T=0.135 1，得出條件屬性具有極低的相關(guān)性。

（2）根據(jù)公式（13）計(jì)算每個(gè)條件屬性的信息增益率，得到：

Gain_ratio(D,根蒂)=0.269

Gain_ratio(D,敲聲)=0.253

Gain_ratio(D,紋理)=0.482

Gain_ratio(D,臍部)=0.372

Gain_ratio(D,觸感)=0.154

根據(jù)Gain_ratio（D，紋理）>Gain_ratio（D，臍部）>Gain_ratio（D，根蒂）>Gain_ratio（D，敲聲）>Gain_ratio（D，色澤）>Gain_ratio（D，觸感），選擇紋理作為決策樹的根節(jié)點(diǎn)。

（3）在構(gòu)建決策樹過程中，對于條件屬性中的敲聲、紋理很難給出明確的判斷。因此在屬性敲聲、紋理加入到?jīng)Q策樹前，需要計(jì)算f 值，并根據(jù)屬性的先驗(yàn)概率，兩者結(jié)合得到屬性的后驗(yàn)概率，再根據(jù)計(jì)算得到的后驗(yàn)概率把其歸為某一類。

通過與原C4.5 算法比較，樣本數(shù)據(jù)集中的二異性數(shù)據(jù)，并在引入Fleiss’Kappa系數(shù)的基礎(chǔ)上，在計(jì)算各個(gè)屬性的信息增益率時(shí)，數(shù)據(jù)劃分的更明顯，得到的結(jié)果更加準(zhǔn)確。

4.2 實(shí)驗(yàn)2

為了充分驗(yàn)證改進(jìn)后算法的準(zhǔn)確性，實(shí)驗(yàn)引用了UCI[15]中的Abalon、Iris、Soybean以及Zoo數(shù)據(jù)集。實(shí)驗(yàn)隨機(jī)抽取部分?jǐn)?shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩余部分?jǐn)?shù)據(jù)集作為測試數(shù)據(jù)，分別運(yùn)用本文改進(jìn)的T_C4.5算法，文獻(xiàn)[3]算法，文獻(xiàn)[7]算法以及原C4.5 算法對這些數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析。4 種算法實(shí)驗(yàn)準(zhǔn)確率對比如表5，實(shí)驗(yàn)時(shí)間對比如表6所示。

表5 準(zhǔn)確率對比

表6 實(shí)驗(yàn)時(shí)間對比 s

從表5看出，針對UCI中的4個(gè)數(shù)據(jù)集，本文提出的T_C4.5算法在準(zhǔn)確率方面明顯高于文獻(xiàn)[3]和文獻(xiàn)[7]的兩個(gè)算法，并且會(huì)遠(yuǎn)遠(yuǎn)大于原C4.5 算法的準(zhǔn)確率。針對不同大小的數(shù)據(jù)集，4種算法的準(zhǔn)確率表現(xiàn)的也不一樣，對于較大的數(shù)據(jù)集，準(zhǔn)確率明顯會(huì)有所降低。

從表6看出，本文提出的T_C4.5算法在運(yùn)行時(shí)間上與其他3種算法相比會(huì)有所提高，這是因?yàn)樗惴ㄔ谶\(yùn)行時(shí)需要判斷時(shí)候計(jì)算貝葉斯決策樹中的0或者f 的值，以及在計(jì)算Fleiss’Kappa 系數(shù)時(shí)，需要對數(shù)據(jù)進(jìn)行各種處理。但是，運(yùn)行時(shí)間的增加幅度在可允許范圍內(nèi)。

5 結(jié)束語

本文在已有工作的基礎(chǔ)上，提出了貝葉斯決策樹算法，并在此基礎(chǔ)上引入Fleiss’Kappa 系數(shù)。在GitHub中的西瓜數(shù)據(jù)集上對算法的改進(jìn)進(jìn)行了詳細(xì)的說明，并在UCI 中的4 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，與文獻(xiàn)[3]和文獻(xiàn)[7]以及原C4.5 算法進(jìn)行對比，實(shí)驗(yàn)表明該算法在一定程度上犧牲了運(yùn)行時(shí)間，但在準(zhǔn)確率方面得到明顯提高。本文所提到的算法存在后續(xù)的研究空間，例如在算法的執(zhí)行效率方面比其他算法算法低，在以后的工作中將會(huì)致力于解決執(zhí)行效率的問題，以提高算法的高效性。