Fleiss’Kappa系數(shù)在貝葉斯決策樹算法中的應用

安葳鵬，程小博，劉 雨

河南理工大學 計算機科學與技術學院，河南 焦作454000

1 引言

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

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

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

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

2 理論基礎

2.1 C4.5算法

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

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

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

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

其中：

2.2 樸素貝葉斯算法

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

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

（1）計算先驗概率的估計值以及條件概率[13]的估計值：

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

（3）計算并返回x 的分類y：

2.3 Fleiss’Kappa系數(shù)

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

其中：

Fleiss’Kappa 系數(shù)計算結果一般為-1～1 之間，但通常會落到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é)實驗1中的西瓜數(shù)據(jù)集，數(shù)據(jù)部分都是文字類型的數(shù)據(jù)），會造成Fleiss’Kappa 系數(shù)計算的不便，因此要對這些非數(shù)字化的數(shù)據(jù)用等級評定法對其進行數(shù)字化處理[14]。

設樣本數(shù)據(jù)集為D，根據(jù)數(shù)據(jù)集中的條件屬性中的特征A將樣本數(shù)據(jù)集劃分為n 個子集D1,D2,…,Dn，Ni為對應Di的樣本個數(shù)。假設決策屬性被劃分為K個類別Bk，k=1,2,…,K，集合Di中屬于類Bk的樣本集合為Dik，樣本個數(shù)為Nik。首先設定B1的等級數(shù)最高，則Di中屬于類B1的個數(shù)所占的比例為Pi。假設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算法的基礎上引入Fleiss’Kappa系數(shù)，算法步驟如下：

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

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

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

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

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

圖1 貝葉斯決策樹結構

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

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

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

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

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

4 實驗結果與分析

4.1 實驗1

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

（1）計算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 色澤評定結果

表3 等級評定結果

根據(jù)表3的數(shù)據(jù)，可以看做為17個專家對6項任務進行3級評定，可以將表3的數(shù)據(jù)修改為表4的數(shù)據(jù)結果。

表4 轉換結果

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

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

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é)點。

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

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

4.2 實驗2

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

表5 準確率對比

表6 實驗時間對比 s

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

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

5 結束語

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