譚正華，戴立平，文 陽，李國泰

湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭411105

1 引言

決策樹是由貪心算法發(fā)展而來，由Hunt 等人于1966 年提出的[1]。它是數(shù)據(jù)挖掘分類算法里的關(guān)鍵分支，廣泛運用于諸多領(lǐng)域。主要的決策樹算法模型有ID3、C4.5、CART等[2]。其中C4.5算法分類精度高，對于小數(shù)據(jù)集處理速度快，且分類規(guī)則易理解，是最為經(jīng)典的決策樹算法。

文獻[3]針對C4.5 算法需要多次掃描、運行效率低的問題，提出了信息增益率的對數(shù)優(yōu)化，提高了算法的運行效率；Mantas等[4]提出了一種改進的C4.5算法——Credal-C4.5算法，通過使用新的不精確信息增益率分類標準，來估計特征和類別變量的概率，有效地解決了噪聲數(shù)據(jù)分類中過度擬合的問題；Ngoc等[5]提出了利用決策樹對英文情感詞典進行分類，并在該基礎(chǔ)上擴展出新的正極性與負極性關(guān)聯(lián)規(guī)則，為決策樹與關(guān)聯(lián)規(guī)則的結(jié)合提供了新的方法；文獻[6]提出了一種新的VFC4.5 算法，通過使用算術(shù)平均值和中值來減少候選閾值分割點的數(shù)量，改進了連續(xù)值屬性分割的方式；Sergio等[7]提出了基于C4.5 分類器的進化分割點選擇多元離散化分類，使用適應(yīng)度函數(shù)來定義數(shù)據(jù)集的最佳離散化方案，提高了數(shù)據(jù)離散精度。

本文在C4.5 分類算法的基礎(chǔ)上，提出了一種新的基于約簡屬性和閾值分割優(yōu)化的決策樹構(gòu)建方法。該方法在離散化連續(xù)值特征屬性過程中優(yōu)化了最佳閾值分割點的選擇，修正了信息增益率的計算方式，解決了分類數(shù)據(jù)集中特征屬性冗余造成分類準確率降低的問題，提高了算法的運行效率與準確率。

2 C4.5算法原理

C4.5算法是對ID3算法的改進，由Quinlan[8]于1993年提出，其基本原理為：

首先采用熵值H(X,a)表示數(shù)據(jù)集分類為獲取屬性字段a 的代價，定義為：

其中，k 為屬性a 的取值個數(shù)，n 為樣本總數(shù)。然后用信息增益比表示單位代價獲取到的信息量，定義為：

其中，I(X,a)為信息增益，將每一個屬性的信息增益比作一個計算，來確定測試屬性字段。

C4.5算法與ID3算法的不同主要有：

（1）在分支屬性的選取上，C4.5 算法采用的是單位代價內(nèi)獲取到的信息量；

（2）C4.5能夠完成連續(xù)值屬性的離散化；

（3）選用常值或者均值，取代數(shù)據(jù)樣本集的未知字段，能夠完成缺省字段值的處理；

（4）對于模型優(yōu)劣程度的評估，采用了K 次迭代交叉驗證；

（5）該算法產(chǎn)生的是if-then 的規(guī)則集合，該規(guī)則集合會形成一條路徑，由根節(jié)點到葉節(jié)點的規(guī)則生成。

雖然C4.5算法相對于ID3算法有所改進，提高了識別效果，但還是沒能夠脫離信息熵的范疇，樹的分化仍舊是一個多叉樹；同時需要將數(shù)據(jù)集中的屬性做一個掃描排序，增加了時間復(fù)雜度[9]。

3 基于屬性相關(guān)性的約簡方法

如何解決決策樹屬性冗余約簡問題，采用概率論中的Pearson系數(shù)[10]來對屬性間的相關(guān)性進行度量。屬性約簡的目標為：對于決策屬性和特征屬性，兩者之間的相關(guān)性越大越好，以保證特征屬性子集中沒有其他無關(guān)屬性；對于特征屬性，每個屬性間的相關(guān)性越小越好，使得屬性子集中沒有冗余屬性[11]。

Pearson系數(shù)有如下定義：

定義1 對于隨機變量X 的概率分布為P{X=Xk}=Pk(k=1,2,…)，當絕對收斂時，則稱該級數(shù)的和為X 的數(shù)學(xué)期望E(X)：

定義2 若隨機變量X 存在E{[X-E(X)]2}，則稱其為X 的方差，用D(X)表示：

定義3 隨機變量Y 的數(shù)學(xué)期望為E(Y)，與隨機變量X 的協(xié)方差用Cov(X,Y)表示，其中：

那么隨機變量X、Y 之間的相關(guān)系數(shù)（Pearson）表示為：

在兩個任意隨機變量之間，如下等式成立：

在決策樹模型中，X、Y 表示數(shù)據(jù)集中的兩個特征屬性集合，數(shù)據(jù)樣本總數(shù)為num，其屬性值分別為X={X1,X2,…,Xm},包含了m 個屬性值；Y={Y1,Y2,…,Yn},包含了n 個屬性值。其中Xi表示特征屬性X 中的第i個值，Yj表示特征屬性Y 中的第j 個值，nai表示滿足條件X=Xi的樣本個數(shù)，用nbj表示Y=Yj的樣本個數(shù)，當存在X=Xi且Y=Yj的樣本數(shù)時，用naibj表示，其結(jié)果如圖1所示。

圖1 結(jié)果覆蓋示意圖

特征屬性X、Y 的相關(guān)系數(shù)ρxy取絕對值，由式（4）、式（8）可推導(dǎo)得出：

結(jié)合式（3）可得：

對于數(shù)據(jù)集中存在的特征屬性，兩者間的相關(guān)性越大則p 值越大，反之越小。當屬性間相關(guān)性較大時，比較屬性間的信息增益率，那么可以通過去除信息增益率較小的冗余屬性，達到約簡數(shù)據(jù)集特征屬性，提高決策樹模型準確率的目的。

一般情況下，當0.8 ≤ρxy≤1 時，表示兩個特征屬性極強相關(guān)；0.6 ≤ρxy＜0.8 時，強相關(guān)；0.4 ≤ρxy＜0.6 時，中等程度相關(guān)；0.2 ≤ρxy＜0.4 時，弱相關(guān)；0 ≤ρxy＜0.2時，極弱或者無相關(guān)。

4 基于閾值分割點的邊界判定優(yōu)化

傳統(tǒng)C4.5算法對連續(xù)值的處理如下[12]：

（1）對數(shù)據(jù)樣本子集中的變量統(tǒng)一排序，以升序的排列方式得到屬性序列{A1,A2,…,An}；

（2）根據(jù)屬性值劃分，得到n-1 個候選分割閾值點，對于第i 個分割閾值點，分割取值設(shè)置為Si=middle{Ai,Ai+1}={Ai,Ai+1}/2，將樣本集劃分為兩個子集；

（3）產(chǎn)生的候選閾值分割點共有n-1 個，并對閾值分割點的信息增益率系數(shù)進行計算，最佳的閾值分割點為計算系數(shù)最大的點。

在上述計算中，需要計算n-1 個閾值分割點的信息增益率，當數(shù)據(jù)總量較大時，容易出現(xiàn)時間復(fù)雜度較高的問題。針對以上問題，在C4.5 決策樹對連續(xù)變量分裂屬性的處理上，提出了一種優(yōu)化閾值分割點的方法，減少了分割閾值點的劃分，降低了算法的時間復(fù)雜度。當數(shù)據(jù)集樣本較大時，能夠較好地提高運行效率。

4.1 閾值分割點的邊界判定定義

定義4 邊界點：對于訓(xùn)練集T,T 中有連續(xù)字段A，當將A 字段中的連續(xù)字段屬性值按照從小到大排列后，有一個點S 將T 劃為兩個子集T1和T2，能夠使得T1＜S ＜T2，其中T1中所有的A 屬性值都小于T,T2中所有的A 字段值都會比T 大，那么就可以將T 定義為一個邊界點。

定理1 關(guān)于邊界點判定定理：定義T 為樣本數(shù)據(jù)集，A 為字段屬性，E 為在屬性A 上劃分樣本數(shù)據(jù)集T 所得到的平均類熵，S 為字段A 的閾值點。如果存在S，使得E(A,S;T)最小，則S 是一個邊界點。

通過上述判定定理，離散化閾值分割點存在邊界點中，最佳劃分點總是在邊界處，如果把同一個類分成了不同的類，那么這樣的分割點是不會有信息增益的。因此并不需要測試所有的分割閾值點，只需要測試邊界點[13]。

4.2 分割點的優(yōu)化判定方法

基于邊界點判定定理，通過邊界點的劃分，降低算法的時間復(fù)雜度，減少處理連續(xù)屬性的計算量，其步驟如下：

步驟1 對連續(xù)屬性進行升序排序，得到序列；

步驟2 劃分閾值分割點，對每個閾值分割點是否屬于邊界點進行判定；

步驟3 計算邊界點的信息增益，選擇信息增益最大的邊界點進行離散化；

步驟4 將連續(xù)屬性值離散為兩部分，構(gòu)造決策樹節(jié)點。

優(yōu)化的C4.5決策樹構(gòu)造偽代碼如下：

輸入：節(jié)點N ，訓(xùn)練樣本集S，分類屬性集A；

輸出：一棵決策樹；

算法流程如圖2所示。

圖2 閾值分割流程圖

在對最佳閾值分割點進行判定時，為避免特征屬性分化選擇偏連續(xù)值屬性，對處理連續(xù)值特征屬性的方法進行了修正[14]。其中最佳分割點為信息增益最大的點，而不是信息增益率最大的點。離散化后再計算該特征屬性的信息增益率。修正步驟為：

步驟1 將該節(jié)點上的連續(xù)屬性值進行升序排序，得到屬性序列為{A1,A2,…,An,…,Atotal}；

步驟2 按照升序序列產(chǎn)生total-1 個閾值分割點，其中第n 個分割點的取值為(An+An+1)/2，將樣本數(shù)據(jù)集分成兩個子集，通過邊界點優(yōu)化方法劃分邊界點，減少閾值分割點的計算；

步驟3 計算邊界點的信息增益，選擇信息增益最大的邊界點作為該特征屬性的最佳分割點；

步驟4 離散化該連續(xù)值特征屬性，計算該最佳邊界分割點的信息增益率，并對其減去lb(N-1)/||D 進行修正，修正方法為：

其中，N 為連續(xù)特征的取值個數(shù)，D 為訓(xùn)練數(shù)據(jù)集data_set 的樣本量，GainRatioX為該節(jié)點屬性X 離散化后的信息增益率。

5 實驗結(jié)果及分析

本文實驗在Pycharm 平臺上進行，算法實現(xiàn)采用python 語言。實驗環(huán)境如下：Windows10、CPU-Intel?CoreTMi5-4200U@1.60 GHz，8 GB RAM。實驗分為兩部分：（1）采用傳統(tǒng)的C4.5算法；（2）采用改進的C4.5算法。首先對數(shù)據(jù)集特征屬性進行約簡，去掉冗余屬性，然后對連續(xù)值特征屬性離散化進行優(yōu)化處理，并對信息增益率計算進行修正。本文采用的數(shù)據(jù)集來自于UCI機器學(xué)習平臺，實驗以CPU 運行時長和準確率作為衡量算法時間復(fù)雜度和準確率高低的評判標準，測試案例為生成分類決策樹。

本文采用的數(shù)據(jù)集共三個，具體內(nèi)容參見表1。

表1 數(shù)據(jù)集具體內(nèi)容

上述數(shù)據(jù)集中，iris數(shù)據(jù)集樣本量較少，屬性較少且特征屬性全為連續(xù)值屬性；wine數(shù)據(jù)集屬性較多且特征屬性全為連續(xù)值屬性；abalone數(shù)據(jù)集樣本量較多，特征屬性包含了連續(xù)值屬性和離散值屬性。

5.1 數(shù)據(jù)集處理

計算數(shù)據(jù)集中特征屬性間的相關(guān)系數(shù)ρ，結(jié)果如表2、表3、表4所示。

iris、wine、abalone數(shù)據(jù)集每個特征屬性的信息增益率如表5、表6、表7所示。

當特征屬性個數(shù)numfeature＜10，選取ρ ≥0.9 的特征屬性；當numfeature≥10 時，選取ρ ≥0.85 的特征屬性。通過比較特征屬性的信息增益率，三個數(shù)據(jù)集的冗余屬性分別為iris{Petal.Length}、wine{Totalphenols}、abalone{Length,Wholeweight,Visceraweight,Shellweight},去除該數(shù)據(jù)集中的冗余屬性，新數(shù)據(jù)集用于改進的C4.5算法。

表2 iris數(shù)據(jù)集特征屬性相關(guān)系數(shù)

表3 wine數(shù)據(jù)集特征屬性相關(guān)系數(shù)

表4 abalone數(shù)據(jù)集特征屬性相關(guān)系數(shù)

表5 iris特征屬性的信息增益率

表6 wine特征屬性的信息增益率

表7 abalone特征屬性的信息增益率

5.2 實驗結(jié)果

實驗采用多次驗證的方法[15]，從數(shù)據(jù)集隨機抽取70%作為訓(xùn)練集，30%作為測試集，進行10次實驗，取實驗的平均值作為實驗結(jié)果。實驗結(jié)果如表8、表9、表10所示。

表8 iris數(shù)據(jù)集實驗結(jié)果

表9 wine數(shù)據(jù)集實驗結(jié)果

傳統(tǒng)C4.5算法和改進C4.5算法的實驗結(jié)果如圖3、圖4所示。

表10 abalone數(shù)據(jù)集實驗結(jié)果

圖3 CPU耗時對比圖

圖4 準確率對比圖

實驗結(jié)果表明：改進的C4.5 算法在時間運行效率和模型準確率上有了一定的提高。利用基于閾值分割點的邊界判定優(yōu)化可以減少連續(xù)值屬性離散化的計算量，有效提高決策樹的生成效率。當樣本數(shù)據(jù)量較少時，運行效率約提升了50%，隨著樣本數(shù)量的增加，運行效率提升更為明顯。同時針對數(shù)據(jù)集中冗余屬性的約簡和信息增益率的修正，有效地提高了模型分類的準確率。

6 結(jié)束語

本文采用約簡屬性和閾值分割優(yōu)化方法，可以有效地提高決策樹模型的生成效率和準確率。該方法在具有多個連續(xù)值屬性的數(shù)據(jù)集中效果較為明顯，如本文中小樣本數(shù)據(jù)集iris和wine，改進前后的差別明顯，具有較好的應(yīng)用前景和價值。本文主要針對多特征屬性和多連續(xù)值屬性的數(shù)據(jù)樣本進行改進。當數(shù)據(jù)樣本量較大時，如abalone 樣本集，運行時間較長且模型準確率較低，這是C4.5算法本身的缺陷，也是下一步研究和改進的方向。