韓存鴿,葉球?qū)O

1(武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,武夷山 354300)

2(認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室,武夷山 354300)

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

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

本文在研究C4.5 算法的基礎(chǔ)上提出一種優(yōu)化算法,通過對UCI 數(shù)據(jù)庫中 5 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法極大的提高了運(yùn)行效率.

1 C4.5 算法理論

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

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

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

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

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

C4.5 算法采用后剪枝技術(shù)對生成的決策樹進(jìn)行剪枝操作,形成決策樹模型,根據(jù)建立好的模型,生成一系列IF-THEN 規(guī)則,實(shí)現(xiàn)對訓(xùn)練集的分類.

2 改進(jìn)的C4.5 算法

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

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

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

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

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

若V的m個(gè)屬性互相獨(dú)立,那么

繼而推出：

故將未知類別的樣本X歸到類別Ci,當(dāng)且僅當(dāng)

根據(jù)上述原理可以實(shí)現(xiàn)對多維空缺屬性的處理：

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

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

① 讀入測試數(shù)據(jù).

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

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

④ 取出D2中的記錄數(shù)據(jù),為缺失屬性賦值計(jì)入Di.

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

2.2 改進(jìn)思想及改進(jìn)計(jì)算方式

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

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

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

在數(shù)據(jù)集D中計(jì)算屬性X的信息熵公式為

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

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

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

2.3 N-C4.5 算法實(shí)際應(yīng)用

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

表1 顧客購買計(jì)算機(jī)的樣本信息S

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

Step1.計(jì)算分類所需的期望信息

Step2.計(jì)算每個(gè)屬性的信息熵

Step3.計(jì)算每個(gè)屬性的信息增益

Step4.計(jì)算每個(gè)屬性的分裂信息度量

Step5.信息增益率

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

圖1 N-C4.5 算法構(gòu)造的決策樹

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

3 實(shí)驗(yàn)結(jié)果比較分析

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

表2 測試數(shù)據(jù)集基本信息

Iris 數(shù)據(jù)集是構(gòu)建決策樹挖掘中最典型的一組數(shù)據(jù),共有150 條記錄,有4 個(gè)分裂屬性,類標(biāo)記屬性為3 種,人為添加部分缺失信息,缺失屬性為sepal width,共有30 條缺失記錄,使用Iris 數(shù)據(jù)集對改進(jìn)前后的算法進(jìn)行5 次仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 Iris 數(shù)據(jù)建模時(shí)間

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

表3 建模信息表

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

4 總結(jié)

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