改進的C4.5算法的研究與應用?

趙建民 黃 珊 王 梅 劉 澎

（東北石油大學計算機與信息技術學院 大慶 163318）

數據挖掘是對大數據集的探索過程，并揭示出其中的隱含規律，它融合了眾多的技術，是計算機科學的一個重要分支。其中分類分析是數據挖掘中重要的分析技術之一，分類分析是根據己有數據樣本集的特點發現分類規則，構造分類函數或分類器，從而對未知類別的樣本賦予類別，以更好地輔助決策。

目前對涉案人的預警主要運用犯罪專業理論和統計學方法，這些方法大多需要預測人員具備專業的涉案人犯罪經驗和領域內的先驗知識。同時，對采用較新數據挖掘技術進行涉案人預測挖掘的研究較少［1～3］。數據挖掘中的決策樹方法具有可以生成易理解的規則、清晰顯示重要字段、計算量較小等優點。應用此方法不要求預測人員具有太多專業領域內的先驗知識。

基于決策樹的預測方法有很多種類［4］，ID3算法和C4.5算法為最主要的兩大算法。其中C4.5算法通過采用信息增益率等方式對ID3算法進行了較好的改進，解決了ID3算法不能處理連續屬性和容易選擇屬性取值較多的值作為分裂標準的弊端，從而使之具有更好的適應性。在應用過程中，由于C4.5算法是按照貪心策略以局部最優的方式構造決策樹，此方法下的決策樹不一定是全局最優。與此同時，涉案人不同的特征屬性的影響程度不同，且不同時間及地點涉案人的特征規律不盡一致，使得運用C4.5算法的分類預測效果并不理想。針對C4.5算法目前存在的問題，相關研究人員提出了使用劃分相似度為標準進行C4.5決策樹最優特征選?。?］，通過選取多次抽樣訓練的分類規則進而形成最優規則，在提高該算法準確度的同時還提高了算法的精度，但此方法的使用范圍僅限于部分數據集。

本文以C4.5算法的改進作為研究目標，針對涉案人特征挖掘這一問題，提出一種改進的C4.5算法。在C4.5算法中加入加權參數W，即C4.5-W算法。通過對涉案人犯罪數據進行訓練得到先驗知識-加權參數W，采用C4.5算法對進行預測。

2 改進的C4.5算法概述

將加權參數W與屬性選擇相結合，降低強關聯屬性的信息熵，提高某些弱關聯屬性的信息熵，構造新的決策樹模型，提高決策樹預測的準確性，為涉案人特征挖掘奠定基礎。

2.1 劃分信息熵

利用屬性V劃分樣本集S中的數據，計算V對S劃分熵值定義為Entropy（S）。屬性V分為離散型和連續性兩種。

1）V為離散型

取N個不同的值，則屬性V依據N的不同值將S劃分為N個子集｛S1，S2…，Sm｝。引入參數W后，屬性V劃分S的信息熵定義為

Si和S中包含的樣本個數分別是|Si|和|S|。

2）V為連續型時

利用屬性V的取值遞增排序，假設S中屬性V有N個不同的取值，則排好序的取值序列為a1、a2、…、am，按順序逐一將兩個相鄰的值的平均值作為分割點，分割點將S劃分為SL和SR兩個子集，SL為屬性V取值小于平均值的子集，SR為屬性V取值大于平均值的子集，對每個可能的分割點計算信息熵為

通過計算并比較屬性V所有分割點的信息增益率，選取最大信息增益率作為屬性V的信息增益率。

2.2 計算信息增益率

假設劃分樣本集S為C個類的熵為Entyopy（S），其取值與具體的條件屬性無關。則信息增益率計算公示如下：

通過對原有C4.5算法中增益率的計算，推理出新的C4.5算法中信息增益率計算公式如下：

其中，SplitE（V）為按屬性V分組的分裂信息，計算方法與C4.5算法相同［6～10］。

2.3 參數W與信息增益率的關系

設樣本數據集為Q，包含屬性集S。在任意屬性V中，設屬性V的第i個取值為Vi，則Vi對應的信息熵為Entropy（Si），記為X，即

X≥0易在信息熵中得到，且X的取值可以是任意值的非負整數，即x屬于［0，+00），按照式（1）和式（2）調整信息熵的取值范圍，定義一個帶加權參數W的加權信息熵，記為X′，具體定義如下：

其中，k的取值范圍為［-1，0］。

設y=GainRatio（V），f（V）=Split（V），y可用如下公式表示：

式（3）中的Entropy（S）取值與屬性無關，可取值為常數Z，Z為非負數。定義g（Z）公式如下所示：

其中，C為任意實數。

經過進一步推理，y的表達式可以進一步如下表示：

在上述公式的推導過程中可知，C4.5-W算法的信息增益率的取值受x、f（V）、K三個因素的影響。其中，X、f（V）與屬性V有關，可通過樣本數據計算得出；而W的值與樣本的歷史數據相關，是一個與具體應用領域有關的先驗值或先驗知識，需要通過不斷訓練歷史數據進而構建決策樹模型得出。

在決策樹構建過程中，C4.5-W算法首先需要取初始W值，并判斷值的屬性為離散型還是連續型，如果為離散型屬性，按照式（1）得到信息熵；如果為連續型屬性，對數據進行排序后，通過式（2）進行信息熵計算，利用C4.5算法計算信息增益，再采用式（3）計算信息增益率，通過對比不同屬性計算的信息增益率值的大小，確定優先分裂的屬性。

當生成決策樹模型誤差率大于指定閾值時，可通過調整W的取值進行反復實驗使得決策樹模型和樣本實際數據接近一致，降低訓練誤差率，提高預測準確性。

3 實驗分析

將涉案人相關數據為例進行訓練建模驗證C4.5算法的準確性和有效性。涉案人屬性主要包括姓名、性別、聯系方式、戶籍、曾用名、職業、年齡、涉案金額、涉案時間、涉案地點、涉案人是否有過犯罪經歷、涉案類別等屬性。

3.1 數據預處理

為了方便接下來算法的正常使用，對數據進行預處理，主要方式如下：

1）數據清洗

針對屬性下的空缺數據，采用填補該屬性下最常見的數值方法，將數據填補完整，針對屬性下的噪聲數據采用刪除的方法［11～13］。由于涉案人中的聯系方式、戶籍、曾用名等屬性對于特征挖掘暫無參考價值，故刪除。最后保留下的屬性有姓名、涉案金額、涉案時間、涉案地點、涉案人是否有過犯罪經歷、涉案類別屬性。將此部分屬性保留，便于挖掘出各類案件涉案人群在不同時間段下的，不同涉案金額下的，不同年齡段下等的涉案人群特征。

2）數據變換

數據變換是對數據的合并、清理和整合過程［14～17］。以涉案金額為例，將涉案金額換分為各個金額區間，將每個涉案區間用特征數值進行表示，如涉案金額在0～500之間的用數值1進行表示，如果涉案金額區間段劃分較多，可在數值1前加入0，即001，將數值位數補全，再將每個區間段用特定的數值表示。

3.2 訓練數據及W值的選定

為了選擇較適合對歷史數據挖掘的W值，以高峰涉案時間段2014年1月1日至2014年3月1日的數據作為訓練數據集，經過預處理后的訓練數據集如表1所示。

表1 訓練數據集

根據2.3節相關理論，在W的取值范圍［-1，0］之間，依次取0、-0.1、-0.2、-0.3、-0.4、-0.5、-0.6、-0.7、-0.8、-0.9、-1共11個W值。將W值代入公式（1）～（3），采用Weka API構造出不同W值下的決策樹模型，再通過實際中已經偵破案件中的數據分析訓練誤差。兩者比較結果如圖1、圖2、圖3、圖4所示。

根據圖1～4可以看出K取值為0、-0.1、-0.2、-0.3、-0.4、-0.5、-0.6時，預測數據與實際數據不符的情況較多。

綜上所述，W取值在-0.7或-0.8時模型的誤差率最低。因此，將W=-0.7對涉案特征進行預測分析對比。

圖1 W=0，-0.1，-0.2，-0.3

圖2 W=-0.4，-0.5，-0.6

圖4 W=-0.9，-1

3.3 實驗結果與分析

為了比較C4.5算法和C4.5-W算法的預測能力，以下通過選取2015年12月歷史數據生成模型，兩種算法得到的模型分別如圖5（a）和圖5（b）所示。在決策樹圖中將涉案金額用Money替換，將性別用Sex替換，將年齡用age替換，對比兩個圖中的屬性劃分，可以發現改進后的算法通過引入參數W，使得年齡屬性重要程度大于性別屬性的重要程度。

同樣，從圖6的預測結果可以看出，C4.5-W算法的預測曲線中預測值與實際值曲線重合度比原始C4.5算法預測曲線重合度高。因此，在C4.5算法中引入參數W可大幅提升算法的準確率。

圖5 C4.5算法預測能力

圖6 C4.5-W算法預測結果

4 結語

基于涉案人的特征和數據挖掘相關理論，本文通過實驗與比較，研究出了一種適合涉案人特征挖掘的決策樹算法：C4.5-W算法。通過實驗結果表明，C4.5-W算法在預測準確率方面較為精準，能夠作為數據挖掘涉案人特征的適用方法。但是也存在一些不足，如沒有深入考慮噪聲數據等。