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

(東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318)

0 引 言

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

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

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

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

1 決策樹方法的選定與改進

1.1 ID3算法

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

1.2 C4.5算法

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

1.3 CART算法

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

2 C4.5決策樹算法的改進

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

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

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

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

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

定義4：分裂信息熵：設劃分訓練集的屬性A有k個不同的值，則將屬性A樣本集劃分為k個不同的子集。其中，樣本子集Sj包含樣本集S中的部分樣本，ai為它們在屬性A上的值。若以屬性A的值為基準，對樣本集進行分割，則INFO(A)表示屬性A的分裂信息熵，其計算公式為：

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

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

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

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

于是有：

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

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

INFO(S)=

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

INFO(S)=

INFO(A)=

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

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

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

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

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

輸出：決策樹。

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

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

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

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

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

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

算法流程如圖1所示。

3 實驗結果分析

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

圖1 算法流程

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

續(xù)表1

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

圖2 算法分類精度對比

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

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

4 結束語

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