決策樹分類算法中C4.5算法的研究與改進①

韓存鴿,葉球孫

1(武夷學院 數學與計算機學院,武夷山 354300)

2(認知計算與智能信息處理福建省高校重點實驗室,武夷山 354300)

決策樹分類算法是分類挖掘算法中較為常用的算法,是一種自頂向下的遞歸算法,常用于分類器和預測模型.1966年Hunt 等人開發研制的CLS[1]系統,為許多決策樹算法奠定了基礎.1979年Quinlan 提出ID3[2]算法,其核心思想以最大的信息增益屬性作為分裂屬性.之后的許多決策樹算法都是在ID3 算法的基礎上衍生改進的.其中C4.5[3]算法就是在 ID3 算法的基礎上發展的,采用信息增益率作為屬性選擇的度量依據,在處理連續性屬性的時,C4.5 算法將這些連續屬性“離散化”,解決了ID3 算法多值偏向性的缺點,有效避免了取值較多的屬性容易被選作分裂屬性的趨勢,增強了決策樹模型的有效性.但是當測試集屬性值缺失率高時,C4.5 算法的分類準確率會明顯下降,而且在構造樹的過程中,該算法需要多次對數據集進行順序掃描及排序,在進行計算時又頻繁地調用對數,增加了算法的時間開銷,從而導致算法低效[4].

文獻[5]調整了連續閾值懲罰項,但是并沒有解決決策樹過度擬合問題.文獻[6]提出雙重熵平均決策樹算法,采用熵值擬合的方法,提高算法運行速度,但是沒有解決空缺屬性問題.文獻[7]在連續屬性離散化方面進行了改進,但并沒有很好的解決過度擬合問題.文獻[8]適用范圍為變精度粗糙集,不適合一般數據分析.

本文在研究C4.5 算法的基礎上提出一種優化算法,通過對UCI 數據庫中 5 個數據集進行實驗,實驗結果表明,改進后的算法極大的提高了運行效率.

1 C4.5 算法理論

C4.5 算法是在ID3 的基礎上加進了對連續型屬性、屬性值空缺情況的處理,通過生成樹和樹剪枝兩個階段來建立決策樹.C4.5 算法通過計算每個屬性的信息增益率(information GainRatio),最后選出具有最高信息增益率的屬性給定集合S 的測試屬性,再根據測試屬性值建立分支,采用遞歸算法,得到初步決策樹.C4.5 算法的相關計算公式如下[9]：

(1)期望信息(也稱信息熵)設S是Si個數據樣本的集合,假定類標號屬性有m個不同值,定義m個不同類Ti(i=1,…,m).設Si是類Ti中的樣本數.對一個給定的樣本分類所需的期望值為：

(2)信息增益 由屬性A劃分成子集的信息量為：

信息增益為原來的信息需求與新的需求之間的差.

(3)信息增益率C4.5 算法中引入了信息增益率,屬性A的信息增益率的計算公式為：

C4.5 算法采用后剪枝技術對生成的決策樹進行剪枝操作,形成決策樹模型,根據建立好的模型,生成一系列IF-THEN 規則,實現對訓練集的分類.

2 改進的C4.5 算法

2.1 決策分類過程中空缺屬性值處理研究

(1)延伸貝葉斯分類算法

決策樹進行分類時,測試樣本數據中可能存在缺失某些屬性值.傳統的決策樹算法在處理缺失屬性值時,一般采用拋棄缺失屬性值的樣本,或重新賦予訓練樣本該屬性的常見值[10].C4.5 算法采用概率分布的填充法來處理缺失屬性值,具體執行過程：首先為某個未知屬性的每個可能值賦予一個概率,根據某節點上屬性不同值的出現頻率,這些概率可以再次估計[11].雖然C4.5 算法有很強的處理噪聲數據的能力,但當訓練集合屬性值的缺失率很高時,使用該算法構建的決策樹模型的結點數更多,模型更為復雜,而且分類準確率也會下降[12].鑒于樸素貝葉斯分類具有堅實的理論基礎、較小的出錯率.本文提出一種基于樸素貝葉斯定理方法[13],來處理空缺屬性值.

假設數據樣本為n維向量空間,V={V1,V2,V3,…,Vi} 若該數據樣本有C1,C2,C3,…,Cm個類別屬性取值,那么基本貝葉斯將未知類別的樣本V歸到類別Ci,當且僅當：

等價p(ci)p(v|ci)＞p(cj)p(v|cj).

若V的m個屬性互相獨立,那么

繼而推出：

故將未知類別的樣本X歸到類別Ci,當且僅當

根據上述原理可以實現對多維空缺屬性的處理：

(2)空缺屬性值處理過程

本文采用上述算法處理空缺屬性,大致流程如下：

① 讀入測試數據.

② 若數據集中沒有空缺屬性值,則把數據壓入Di集合;如果測試數據集中含有空缺屬性值,采用“樣本空缺屬性個數排序,越少越排前,反之則排后.”的原則插入到D2集合.

③ 返回第一步,直到測試數據集中所有數據都檢測結束.最后形成Di、D2兩個集合.其中Di中存放沒有空缺屬性值,D2中存放包含空缺屬性的信息.

④ 取出D2中的記錄數據,為缺失屬性賦值計入Di.

⑤ 遞歸調用上述第④步,直到D2中記錄為0.

2.2 改進思想及改進計算方式

雖然C4.5 算法具有建模速度快、準確率高、易于理解、靈活簡單等優點,但是該算法在構造樹的過程中,需要多次對數據集進行順序掃描及排序,在進行計算時又頻繁地調用對數,增加了算法的時間開銷,從而導致算法低效.針對以上缺點,本文對C4.5 算法的計算公式進行精簡優化,從減小計算時間上提出一種改進算法命名為N-C4.5 算法.公式簡化如下：

假設S是n維有窮離散數據集,S中只有正反兩種情形,分別表示為YS 、NS,其中正例YS 的記錄數為m,反例NS 的記錄數為n,根據式(1)數據集S分類所需的期望值為：

假設決策樹的根為A屬性,A屬性的取值為{A1,A2,…,Ai},利用屬性A將數據集S分為{S1,S2,…,Si}個子集,其中Si為S中屬性A取Ai值的樣本實例數據,那么由屬性A劃分成子集的信息量為

在數據集D中計算屬性X的信息熵公式為

根據無窮小原理l n(1+x)≈x,那么：

信息增益：Gain(A)=Info(S)-In foA(S).

改進后的計算公式使用四則混合運算代替原來的對數運算,可以使計算效率得到提升.原C4.5 算法的時間復雜度為O(n2logn2),改進后的算法時間復雜度為O(n2),新算法去掉了對數運算,優化了時間復雜度.

2.3 N-C4.5 算法實際應用

為了驗證算法正確性,這里以顧客購買計算機的樣本信息S為例,具體樣本記錄如表1所示.使用改進后的算法構建決策樹,命名為N-C4.5 算法.該數據集S 有age、income、student、credit_rating、buy 5 個屬性,其中buy 為類標號屬性,有兩個取值{yes,no},S數據集的前4 個屬性為分裂屬性,并且每個屬性都是離散化的.這里根據每個人的age、income、student、credit_rating 來進行分類,判斷顧客是否購買計算機.

表1 顧客購買計算機的樣本信息S

對客戶購買計算機的樣本信息按照改進以后的算法構建決策樹,利用改進后的公式計算信息熵、信息增益、分裂信息量、以及信息增益率,同時選擇最大信息增益率作為分裂結點,采用遞歸算法構建決策樹.在數據集S中屬于類別“yes”的有9 個,屬于類別“no”的有5 個,根據改進后的公式計算過程分如下五步.

Step1.計算分類所需的期望信息

Step2.計算每個屬性的信息熵

Step3.計算每個屬性的信息增益

Step4.計算每個屬性的分裂信息度量

Step5.信息增益率

由計算結果可知,age 屬性的信息增益率最大,所以選擇age 作為分裂屬性,將原數據集分為youth、middle、senior 三個子集,采用遞歸算法計算每個屬性的信息熵、信息增益、分裂信息量、信息增益率,對于youth 子集,經計算得出student 信息增益率最大,選擇student 作為測試屬性;對于middle 子集全部歸為yes 類,所以不需要進行分類;而對于senior 子集,通過計算得知,credit_rating 信息增益率最大,因此選擇credit_rating 作為測試屬性,根據所有結點,可以得出購買計算機數據集采用N-C4.5 算法構造的決策樹如圖1.

圖1 N-C4.5 算法構造的決策樹

由圖1可以看出采用N-C4.5 算法構造的決策樹與使用原C4.5 算法得到的決策樹結構完全相同,但C4.5 算在計算的過程中調用了大量的對數,而NC4.5 算法卻只需要采用簡單的混合運算即可,因此運算效率大幅度提高.

3 實驗結果比較分析

為了驗證N-C4.5 算法的性能,本實驗選擇UCI 數據庫中 5 個數據集進行仿真實驗,實驗數據的基本信息見表2,實驗硬件配置：內存 4 GB,CPU 2.50 GHz ,使用Window7 操作系統,采用Java 語言在WEKA 平臺中進行仿真實驗.仿真實驗時,首先利用延伸的貝葉斯分類算法填充多維空缺屬性,該方法會生成空缺屬性的各種可能取值組合,接著遍歷各種組合,按公式計算值并記錄最大值即可;然后利用改進后的公式計算信息熵、信息增益、分裂信息量、以及信息增益率,最后選擇最大信息增益率作為分裂結點,采用遞歸算法構建決策樹.

表2 測試數據集基本信息

Iris 數據集是構建決策樹挖掘中最典型的一組數據,共有150 條記錄,有4 個分裂屬性,類標記屬性為3 種,人為添加部分缺失信息,缺失屬性為sepal width,共有30 條缺失記錄,使用Iris 數據集對改進前后的算法進行5 次仿真實驗,實驗結果如圖2所示.

圖2 Iris 數據建模時間

由圖2可以看出,對于Iris 數據,N-C4.5 算法的運行時間短,優化效果明顯.為了驗證N-C4.5 算法算法的效率,對于其他4 組數據集,同樣都分別使用改進后的N-C4.5 算法與C4.5 算法進行仿真實驗,測試時每個數據集都運行5 次,建模時間取5 次的平均值,建模時間如表3所示.

表3 建模信息表

由表中可以看出,數據樣本的大小會影響算法的運行時間,一般情況下,測試數據樣本數據量越大,需要運行的時間越長.算法改進前后的比率都大于1,正確率的提升都是正值,可以得出結論：N-C4.5 算法的建模時間明顯優于C4.5 算法,分類準確率也高于原C4.5 算法.

4 總結

雖然C4.5 算法具有建模速度快、準確率高、易于理解、靈活簡單、以及處理噪聲數據的能力強等優點,但當屬性值缺失率高時,分類準確率會明顯下降;在構建決策樹時,需要多次掃描、排序數據集、以及頻繁調用對數等缺點.本文提出一種改進的決策樹分類算法.采用一種基于樸素貝葉斯定理方法,來處理空缺屬性值,提高分類準確率.通過優化計算公式,改進后的N-C4.5 算法使用四則混合運算代替原來的對數運算,減少構建決策樹模型的運行時間,使計算效率得到提升.