趙建民 黃 珊 王 梅 劉 澎

（東北石油大學(xué)計算機(jī)與信息技術(shù)學(xué)院 大慶 163318）

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

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

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

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

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

將加權(quán)參數(shù)W與屬性選擇相結(jié)合，降低強(qiáng)關(guān)聯(lián)屬性的信息熵，提高某些弱關(guān)聯(lián)屬性的信息熵，構(gòu)造新的決策樹模型，提高決策樹預(yù)測的準(zhǔn)確性，為涉案人特征挖掘奠定基礎(chǔ)。

2.1 劃分信息熵

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

1）V為離散型

取N個不同的值，則屬性V依據(jù)N的不同值將S劃分為N個子集｛S1，S2…，Sm｝。引入?yún)?shù)W后，屬性V劃分S的信息熵定義為

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

2）V為連續(xù)型時

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

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

2.2 計算信息增益率

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

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

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

2.3 參數(shù)W與信息增益率的關(guān)系

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

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

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

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

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

其中，C為任意實數(shù)。

經(jīng)過進(jìn)一步推理，y的表達(dá)式可以進(jìn)一步如下表示：

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

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

當(dāng)生成決策樹模型誤差率大于指定閾值時，可通過調(diào)整W的取值進(jìn)行反復(fù)實驗使得決策樹模型和樣本實際數(shù)據(jù)接近一致，降低訓(xùn)練誤差率，提高預(yù)測準(zhǔn)確性。

3 實驗分析

將涉案人相關(guān)數(shù)據(jù)為例進(jìn)行訓(xùn)練建模驗證C4.5算法的準(zhǔn)確性和有效性。涉案人屬性主要包括姓名、性別、聯(lián)系方式、戶籍、曾用名、職業(yè)、年齡、涉案金額、涉案時間、涉案地點(diǎn)、涉案人是否有過犯罪經(jīng)歷、涉案類別等屬性。

3.1 數(shù)據(jù)預(yù)處理

為了方便接下來算法的正常使用，對數(shù)據(jù)進(jìn)行預(yù)處理，主要方式如下：

1）數(shù)據(jù)清洗

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

2）數(shù)據(jù)變換

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

3.2 訓(xùn)練數(shù)據(jù)及W值的選定

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

表1 訓(xùn)練數(shù)據(jù)集

根據(jù)2.3節(jié)相關(guān)理論，在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構(gòu)造出不同W值下的決策樹模型，再通過實際中已經(jīng)偵破案件中的數(shù)據(jù)分析訓(xùn)練誤差。兩者比較結(jié)果如圖1、圖2、圖3、圖4所示。

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

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

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

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

圖4 W=-0.9，-1

3.3 實驗結(jié)果與分析

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

同樣，從圖6的預(yù)測結(jié)果可以看出，C4.5-W算法的預(yù)測曲線中預(yù)測值與實際值曲線重合度比原始C4.5算法預(yù)測曲線重合度高。因此，在C4.5算法中引入?yún)?shù)W可大幅提升算法的準(zhǔn)確率。

圖5 C4.5算法預(yù)測能力

圖6 C4.5-W算法預(yù)測結(jié)果

4 結(jié)語

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