基于C4.5決策樹(shù)分類算法的改進(jìn)與應(yīng)用

李春生，焦海濤，劉 澎，劉小剛

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引 言

數(shù)據(jù)挖掘的過(guò)程是根據(jù)預(yù)警目標(biāo)選擇合適的數(shù)據(jù)挖掘算法，利用該數(shù)據(jù)挖掘算法挖掘出預(yù)警目標(biāo)潛在的特征規(guī)律，根據(jù)規(guī)律特征進(jìn)行目標(biāo)預(yù)警。

原始數(shù)據(jù)的純度直接關(guān)系到相關(guān)數(shù)據(jù)挖掘技術(shù)的選取，也會(huì)影響整個(gè)數(shù)據(jù)挖掘的效果。若在挖掘前的數(shù)據(jù)格式或數(shù)據(jù)類型差異很大，容易造成數(shù)據(jù)挖掘結(jié)果產(chǎn)生偏差，影響數(shù)據(jù)挖掘結(jié)果的準(zhǔn)確率，無(wú)法實(shí)現(xiàn)科學(xué)有效的預(yù)警。同樣，如果采用的數(shù)據(jù)挖掘技術(shù)不適用當(dāng)前的數(shù)據(jù)特點(diǎn)和預(yù)警目標(biāo)，容易導(dǎo)致算法無(wú)法發(fā)揮應(yīng)有的效果，挖掘出的規(guī)律也無(wú)法用于預(yù)警。

數(shù)據(jù)挖掘算法的確立必須要以大量的歷史數(shù)據(jù)和目標(biāo)為依據(jù)，針對(duì)不同的數(shù)據(jù)類型和數(shù)據(jù)特點(diǎn)，采用不同的數(shù)據(jù)挖掘算法。不同挖掘預(yù)警目標(biāo)需要與不同分析模式進(jìn)行匹配，不同預(yù)警目標(biāo)需要的規(guī)則表達(dá)方法也有差異。因此，有必要選擇與預(yù)警目的相關(guān)的、合適度較高的數(shù)據(jù)挖掘算法。

決策樹(shù)算法是數(shù)據(jù)挖掘中常用的分類與預(yù)測(cè)算法之一，其中包括ID3算法、C4.5算法、CART算法三種。文中主要針對(duì)C4.5算法，分析傳統(tǒng)C4.5算法存在的缺點(diǎn)，并對(duì)其進(jìn)行改進(jìn)。

1 決策樹(shù)方法的選定與改進(jìn)

1.1 ID3算法

ID3算法是傳統(tǒng)經(jīng)典的決策樹(shù)算法[1-3]，其在構(gòu)造決策樹(shù)時(shí)，各節(jié)點(diǎn)代表非類屬性，邊表示此時(shí)非類屬性的取值情況。根據(jù)信息熵的下降速度進(jìn)行屬性劃分，按照從根到當(dāng)前節(jié)點(diǎn)進(jìn)行路徑選擇測(cè)試屬性，不以最大信息增益作為條件屬性。ID3算法具有理論清晰易懂、使用價(jià)值強(qiáng)等優(yōu)點(diǎn)，同時(shí)也存在多值偏向等問(wèn)題，其運(yùn)算過(guò)程通常偏重于選擇屬性取值較多的條件屬性作為決策屬性，但在大多數(shù)運(yùn)算情況下，屬性值取值最多的屬性并非是最優(yōu)屬性，由于在構(gòu)建決策樹(shù)的過(guò)程中各個(gè)節(jié)點(diǎn)僅包含一個(gè)特征，也就是單變?cè)惴?，屬性間不存在強(qiáng)相關(guān)性。也可以看成，最終生成的決策樹(shù)連在一起依舊呈現(xiàn)分散現(xiàn)象。

1.2 C4.5算法

C4.5算法是基于ID3基礎(chǔ)上的改進(jìn)算法[4-7]，在一定程度上彌補(bǔ)了ID3算法的缺陷。C4.5算法具有可處理數(shù)據(jù)范圍包含連續(xù)性數(shù)值、數(shù)據(jù)的自適用性較強(qiáng)、可處理不完整數(shù)據(jù)、屬性選擇的標(biāo)準(zhǔn)較精確以及建樹(shù)完成后具有剪枝操作等優(yōu)點(diǎn)，可避免決策樹(shù)的不完整性，同時(shí)也存在生成決策樹(shù)時(shí)計(jì)算效率較慢等缺點(diǎn)，因此最終生成決策樹(shù)所表示的知識(shí)通?？刹捎肐F-THEN形式的分類規(guī)則來(lái)表示。

1.3 CART算法

CART算法是在決策樹(shù)方法基礎(chǔ)上采用的交叉決策樹(shù)算法[8-11]，具體在算法執(zhí)行的過(guò)程中，首先需要選取具有最小基尼系數(shù)的屬性，通過(guò)對(duì)當(dāng)前決策樹(shù)的節(jié)點(diǎn)進(jìn)行分裂，選取的基尼系數(shù)越小，則表示目前擁有的訓(xùn)練樣本集的純度越高，采用決策樹(shù)進(jìn)行分類效果也就越好。CART算法主要是針對(duì)高度傾斜和多態(tài)的數(shù)值數(shù)據(jù)、有序或無(wú)序的類別型屬性數(shù)據(jù)進(jìn)行快速處理。該算法存在對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行多次布爾測(cè)試的詬病，按照最終的測(cè)試結(jié)果進(jìn)行規(guī)則劃分，當(dāng)判定條件為真時(shí)判定為左分支，否則判定為右分支[12-16]。

2 C4.5決策樹(shù)算法的改進(jìn)

文中以C4.5算法思想在經(jīng)濟(jì)犯罪數(shù)據(jù)中的應(yīng)用為例進(jìn)行概述。運(yùn)用C4.5算法的主要思想是：以訓(xùn)練數(shù)據(jù)集S作為樣本集，當(dāng)樣本集S不斷分裂生成經(jīng)濟(jì)犯罪特征決策樹(shù)的同時(shí)，通過(guò)對(duì)各經(jīng)濟(jì)犯罪屬性信息增益率的計(jì)算，選取當(dāng)前數(shù)值最大的屬性作為分裂節(jié)點(diǎn)。重復(fù)按照此標(biāo)準(zhǔn)，可將樣本集S散列成n個(gè)樣本子集。若在樣本集分裂過(guò)程中，第i個(gè)樣本子集Si內(nèi)包含的元組類別相同時(shí)，當(dāng)前節(jié)點(diǎn)可看作此時(shí)分裂決策樹(shù)的葉子節(jié)點(diǎn)，分裂終止。若在決策樹(shù)分裂過(guò)程中生成不滿足上述條件的經(jīng)濟(jì)犯罪屬性子集Si，則繼續(xù)使用上述方法依次遞歸生成決策樹(shù)，直到所有經(jīng)濟(jì)犯罪屬性子集包含的元組均屬同一個(gè)類別為止。它主要基于以下原理：

定義1：類別信息熵：假設(shè)訓(xùn)練樣本集為S，S中有s個(gè)子樣本，將此訓(xùn)練集劃分為m個(gè)類別，第i類的實(shí)例個(gè)數(shù)可看作為Si，Pi為Si/S的概率，INFO(S)為類別信息熵，基于信息熵的計(jì)算公式為：

定義2：條件信息熵：假設(shè)A作為屬性劃分訓(xùn)練樣本集S，訓(xùn)練樣本集S被劃分成k個(gè)子集{S1，S2，…，Sk}，即將A的取值分為k個(gè){a1，a2，…，ak}，定義Si中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為Sij，INFOA(S)為屬性A的條件信息熵，由A劃分成子集的信息熵計(jì)算公式如下：

定義3：屬性A的信息增益計(jì)算公式為：

Gain(A,S)=INFO(S)-INFOA(S)

定義4：分裂信息熵：設(shè)劃分訓(xùn)練集的屬性A有k個(gè)不同的值，則將屬性A樣本集劃分為k個(gè)不同的子集。其中，樣本子集Sj包含樣本集S中的部分樣本，ai為它們?cè)趯傩訟上的值。若以屬性A的值為基準(zhǔn)，對(duì)樣本集進(jìn)行分割，則INFO(A)表示屬性A的分裂信息熵，其計(jì)算公式為：

定義5：劃分屬性A的信息增益率的計(jì)算公式為：

在C4.5算法構(gòu)建特征決策樹(shù)的過(guò)程中，選擇適合分裂經(jīng)濟(jì)犯罪特征屬性時(shí)，需要計(jì)算每個(gè)經(jīng)濟(jì)犯罪條件屬性的信息增益率，選定信息增益率最大的條件屬性作為分裂屬性。由于經(jīng)濟(jì)犯罪涉案人特征數(shù)據(jù)量較大，需要不斷計(jì)算屬性的信息增益率，涉及到多次的對(duì)數(shù)運(yùn)算，需要頻繁調(diào)用庫(kù)函數(shù)，因此增加了經(jīng)濟(jì)犯罪特征模式挖掘的計(jì)算量，容易產(chǎn)生建樹(shù)效率過(guò)慢的問(wèn)題。

針對(duì)上述問(wèn)題，文中通過(guò)對(duì)信息增益率的計(jì)算公式進(jìn)行改進(jìn)，深入了解數(shù)學(xué)統(tǒng)計(jì)思想的泰勒公式和麥克勞林公式[17]，將二者的公式思想融入到C4.5算法的信息增益率公式計(jì)算中，從而實(shí)現(xiàn)信息增益率計(jì)算速度下降的目的。

由于lnx在x=0時(shí)導(dǎo)數(shù)無(wú)意義，且在信息增益率計(jì)算公式中常定義的概率取值范圍為[0,1]，因此，選用ln(x+1)的麥克勞林公式改進(jìn)傳統(tǒng)C4.5中信息增益率的計(jì)算公式，如下所示：

于是有：

通過(guò)對(duì)以上公式進(jìn)行近似簡(jiǎn)化，完全能夠?qū)?duì)數(shù)運(yùn)算轉(zhuǎn)換成非對(duì)數(shù)運(yùn)算，同時(shí)利用上述轉(zhuǎn)化特點(diǎn)實(shí)現(xiàn)消除信息增益率公式中復(fù)雜的對(duì)數(shù)運(yùn)算，從而達(dá)到簡(jiǎn)化計(jì)算過(guò)程、提升建樹(shù)效率的目的。

類別信息熵的轉(zhuǎn)化過(guò)程如下：

INFO(S)=

同理，條件信息熵和分裂信息熵的轉(zhuǎn)化可表示為：

INFO(S)=

INFO(A)=

因此，轉(zhuǎn)化后的信息增益率計(jì)算公式為：

對(duì)上述改進(jìn)后的計(jì)算公式分析可得出結(jié)論，利用類別信息熵來(lái)計(jì)算條件屬性信息增益率時(shí)每次的時(shí)間值相似度較高，由于上述公式在簡(jiǎn)化的過(guò)程中各部分均可省去-1/ln2S。為了有效地保證算法的分類精度，文中在計(jì)算類條件熵時(shí)采用改進(jìn)的計(jì)算公式，實(shí)現(xiàn)不改變各個(gè)條件屬性的信息增益率的排列順序，同時(shí)又不影響分類精度。

改進(jìn)后的C4.5算法與常規(guī)C4.5算法通過(guò)調(diào)用函數(shù)來(lái)進(jìn)行大量的對(duì)數(shù)函數(shù)運(yùn)算的不同之處在于，改進(jìn)算法只需利用簡(jiǎn)單的四則混合運(yùn)算，便能實(shí)現(xiàn)信息增益率計(jì)算公式的運(yùn)算，無(wú)需多次對(duì)數(shù)運(yùn)算，從而大幅提高了系統(tǒng)的運(yùn)算速度。因此，簡(jiǎn)化后的計(jì)算公式以信息熵理論和知識(shí)為依據(jù)，在一定程度上可保留分類的精準(zhǔn)度。

算法的主要步驟如下所示：

輸入：經(jīng)濟(jì)犯罪數(shù)據(jù)訓(xùn)練樣本集S，經(jīng)濟(jì)犯罪涉案特征屬性集合list，決策屬性d；

輸出：決策樹(shù)。

(1)以經(jīng)濟(jì)犯罪數(shù)據(jù)訓(xùn)練樣本集合S作為根節(jié)點(diǎn)N，創(chuàng)建特征決策樹(shù)；

(2)如果經(jīng)濟(jì)犯罪數(shù)據(jù)訓(xùn)練樣本集S中的所有樣本屬于同一類別，則記節(jié)點(diǎn)N為葉子節(jié)點(diǎn)，并標(biāo)記為類別C，否則轉(zhuǎn)入步驟(3)；

(3)如果經(jīng)濟(jì)犯罪涉案特征屬性集合list為空，記節(jié)點(diǎn)N為訓(xùn)練樣本集合S中含樣本數(shù)量最多的類C，否則轉(zhuǎn)入步驟(4)；

(4)計(jì)算經(jīng)濟(jì)犯罪涉案特征屬性集合list里每個(gè)條件屬性的信息增益率，將具有最大的信息增益率的節(jié)點(diǎn)屬性作為當(dāng)前節(jié)點(diǎn)的分割屬性，標(biāo)記節(jié)點(diǎn)N為A；

(5)根據(jù)分割屬性的值確定訓(xùn)練樣本子集，并建立相應(yīng)的分支；

(6)對(duì)劃分出的訓(xùn)練樣本子集重復(fù)步驟(2)～(5)，生成新的經(jīng)濟(jì)犯罪涉案特征決策分支，直到將所有的樣本子集劃分完為止。

算法流程如圖1所示。

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

以知識(shí)產(chǎn)權(quán)類經(jīng)濟(jì)犯罪案件作為預(yù)警目標(biāo)對(duì)預(yù)警模型進(jìn)行實(shí)例分析。文中采用的是數(shù)據(jù)庫(kù)中的13個(gè)知識(shí)產(chǎn)權(quán)類經(jīng)濟(jì)犯罪數(shù)據(jù)集來(lái)進(jìn)行數(shù)據(jù)分析，將各實(shí)驗(yàn)數(shù)據(jù)集分成兩組，驗(yàn)證實(shí)驗(yàn)結(jié)果。將數(shù)據(jù)集分成兩類，即訓(xùn)練樣本集和測(cè)試樣本集，將數(shù)據(jù)中的90%作為訓(xùn)練樣本，10%作為測(cè)試樣本。將改進(jìn)后的C4.5算法命名為K-C4.5算法，文中在實(shí)驗(yàn)數(shù)據(jù)相同的情況下，分別對(duì)傳統(tǒng)的C4.5算法和改進(jìn)的K-C4.5算法進(jìn)行對(duì)比分析，驗(yàn)證了改進(jìn)后算法的真實(shí)有效性。在實(shí)驗(yàn)分析過(guò)程中，分別對(duì)傳統(tǒng)的C4.5算法和改進(jìn)后的K-C4.5算法進(jìn)行準(zhǔn)確率和時(shí)間的記錄，如表1所示。

圖1 算法流程

表1 算法效率統(tǒng)計(jì)

續(xù)表1

為了直觀地展示算法實(shí)驗(yàn)結(jié)果，采用圖表表示法對(duì)部分?jǐn)?shù)據(jù)測(cè)試結(jié)果進(jìn)行直觀顯示，對(duì)比分析原始的C4.5算法和改進(jìn)后的K-C4.5算法的準(zhǔn)確率和執(zhí)行速度。圖2是傳統(tǒng)的C4.5算法和改進(jìn)后的K-C4.5算法在分類精度上的對(duì)比，圖3傳統(tǒng)的C4.5算法和改進(jìn)后的K-C4.5算法在運(yùn)行時(shí)間上的對(duì)比。

圖2 算法分類精度對(duì)比

圖3 算法執(zhí)行時(shí)間對(duì)比

根據(jù)圖2、圖3的實(shí)驗(yàn)結(jié)果分析可得，相對(duì)于傳統(tǒng)的C4.5算法，改進(jìn)后的K-C4.5算法在進(jìn)行分類時(shí)花費(fèi)時(shí)間較少，同時(shí)算法時(shí)間效率提高沒(méi)有影響分類的準(zhǔn)確度，準(zhǔn)確度與原始的C4.5算法一致性強(qiáng)。通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的分析，驗(yàn)證了改進(jìn)后的K-C4.5算法能夠提升算法的執(zhí)行效率，縮短算法執(zhí)行時(shí)間，同時(shí)算法執(zhí)行效率的提升保證了算法的準(zhǔn)確率。

4 結(jié)束語(yǔ)

主要介紹了決策樹(shù)算法中的C4.5算法的改進(jìn)方法。在研究和比較了多種常見(jiàn)的決策樹(shù)方法的基礎(chǔ)上，分析C4.5算法在執(zhí)行過(guò)程中可能存在的問(wèn)題，對(duì)C4.5算法信息增益率的計(jì)算公式進(jìn)行改進(jìn)，通過(guò)實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比分析，驗(yàn)證了算法的準(zhǔn)確性和效率性。