基于約簡屬性和閾值分割的決策樹構建方法

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

湘潭大學 信息工程學院，湖南 湘潭411105

1 引言

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

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

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

2 C4.5算法原理

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

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

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

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

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

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

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

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

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

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

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

3 基于屬性相關性的約簡方法

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

Pearson系數有如下定義：

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

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

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

那么隨機變量X、Y 之間的相關系數（Pearson）表示為：

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

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

圖1 結果覆蓋示意圖

特征屬性X、Y 的相關系數ρxy取絕對值，由式（4）、式（8）可推導得出：

結合式（3）可得：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：一棵決策樹；

算法流程如圖2所示。

圖2 閾值分割流程圖

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

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

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

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

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

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

5 實驗結果及分析

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

本文采用的數據集共三個，具體內容參見表1。

表1 數據集具體內容

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

5.1 數據集處理

計算數據集中特征屬性間的相關系數ρ，結果如表2、表3、表4所示。

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

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

表2 iris數據集特征屬性相關系數

表3 wine數據集特征屬性相關系數

表4 abalone數據集特征屬性相關系數

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

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

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

5.2 實驗結果

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

表8 iris數據集實驗結果

表9 wine數據集實驗結果

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

表10 abalone數據集實驗結果

圖3 CPU耗時對比圖

圖4 準確率對比圖

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

6 結束語

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