基于文本分類的維吾爾文數(shù)字取證研究

如先姑力·阿布都熱西提，賀一峰，亞森·艾則孜（新疆警察學(xué)院信息安全工程系，新疆烏魯木齊　830013）

?

基于文本分類的維吾爾文數(shù)字取證研究

如先姑力·阿布都熱西提，賀一峰，亞森·艾則孜
（新疆警察學(xué)院信息安全工程系，新疆烏魯木齊830013）

摘要：針對(duì)維吾爾文書寫的數(shù)字文本的犯罪取證，提出一種基于文本分類的維吾爾文數(shù)字取證方案。首先，對(duì)維吾爾文文本進(jìn)行預(yù)處理，濾除文本中非維吾爾文字符和停用詞；然后，提出一種多特征空間正則化互信息（M?FNMI）算法，使用輸入特征組合與類之間的互信息（MI）來代替單個(gè)特征與類之間的MI，從而提取出更準(zhǔn)確的特征詞；最后，利用支持向量機(jī)（SVM）算法來對(duì)特征進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明，該方案具有較高的分類精度，能夠?yàn)榉缸锶∽C提供判斷依據(jù)。

關(guān)鍵詞：數(shù)字取證；文本分類；維吾爾文；互信息；支持向量機(jī)

0　引　言

由于信息和存儲(chǔ)技術(shù)的飛速發(fā)展，公安信息系統(tǒng)中存儲(chǔ)了大量的案件信息。為了能夠更好地預(yù)防、打擊和控制犯罪，則需要應(yīng)用數(shù)字取證技術(shù)，對(duì)存儲(chǔ)數(shù)據(jù)進(jìn)行深度分析，發(fā)現(xiàn)各類案例信息的規(guī)律和關(guān)系[1]。在數(shù)字取證過程中，面對(duì)大量的電子文檔，如何快速地將電子文檔進(jìn)行分類，準(zhǔn)確地辨析案件類型，以及從中提取出有用的信息是取證人員需要解決的一個(gè)主要問題，而數(shù)據(jù)挖掘中的文本分類技術(shù)是解決這種問題的一種有效方法[2]。

隨著國家對(duì)新疆地區(qū)的大力投入，使其信息化建設(shè)得到快速發(fā)展，維吾爾文等少數(shù)民族語種的大量文字信息開始以數(shù)字化形式呈現(xiàn)。對(duì)維吾爾文書寫的大量文本數(shù)據(jù)進(jìn)行文本分類，從而進(jìn)行電子取證，能夠?yàn)樾陆貐^(qū)的計(jì)算機(jī)犯罪提供有力證據(jù)，具有重要的意義[3]。

目前，對(duì)于英文和中文等大語種的文本分類技術(shù)已經(jīng)得到大量研究，并趨于成熟。然而，對(duì)于維吾爾文表述的數(shù)字文本的文本分類，相關(guān)方面的研究還處于起步階段。維吾爾語是一種黏著性語言，具有比較復(fù)雜的時(shí)態(tài)變化和豐富的形態(tài)結(jié)構(gòu)[4]。為此，文獻(xiàn)[4]提出一種基于語義詞特征提取的維吾爾文文本的分類方法，用一種組合統(tǒng)計(jì)量（DME）來度量文本中相鄰單詞之間的關(guān)聯(lián)程度，以此來提取特征詞。文獻(xiàn)[5]利用χ2統(tǒng)計(jì)量來提取詞干，并利用支持向量機(jī)（Support Vector Machine，SVM）算法來構(gòu)造了維吾爾文文本分類器。文獻(xiàn)[6]提出一種新的統(tǒng)計(jì)量（CHIMI），將χ2統(tǒng)計(jì)量和互信息（Mutual Information，MI）進(jìn)行結(jié)合組成CHIMI，抽取Bigram作為文本特征，并采用SVM算法對(duì)維吾爾文文本進(jìn)行分類。

本文在改進(jìn)傳統(tǒng)MI提取特征的基礎(chǔ)上，提出一種基于文本分類的維吾爾文數(shù)字取證方案，用于犯罪文本取證。利用改進(jìn)型正則化互信息算法對(duì)維吾爾文進(jìn)行特征提取，利用SVM進(jìn)行文本分類，從而取證出與犯罪相關(guān)的文本信息。

1　本文方案

本文提出一種基于文本分類的維吾爾文數(shù)字取證方案，其主要包括3個(gè)部分：維吾爾文文本預(yù)處理；特征提取；文本分類。

其中，在特征提取階段，本文針對(duì)傳統(tǒng)MI特征提取中只考慮單個(gè)特征和類別的MI，而沒有考慮上下文特征關(guān)聯(lián)性的缺陷，對(duì)其進(jìn)行改進(jìn)，將輸入特征的組合與類別之間的MI代替單一特征與類別的MI。

1.1文本預(yù)處理

維吾爾文文本預(yù)處理主要包括兩個(gè)部分：文本過濾和詞干提取。其中，文本過濾用于過濾掉文本中非維吾爾文文字和停用詞；詞干提取是用來提取文本中具有真正含義的詞匯。經(jīng)過文本預(yù)處理，可將文本原始特征維度降低約一半。文本去噪過程中，首先對(duì)文本進(jìn)行過濾，獲得維吾爾文單詞集。然后，通過和事先準(zhǔn)備好的停用詞表進(jìn)行比對(duì)，過濾掉停用詞。停用詞為對(duì)文本主題沒有貢獻(xiàn)，不包含文章類別信息的詞，例如介詞、副詞、代詞等。去掉停留詞能夠?qū)崿F(xiàn)特征降維，提高分類精度[7]。詞干提取過程中，首先，根據(jù)維吾爾文單詞與單詞之間的空格符來進(jìn)行分詞。由于維吾爾文單詞是由字母拼寫而成的，通過將不同的詞綴粘貼到單詞的頭部來實(shí)現(xiàn)語法功能，所以，提取文本中能夠代表真實(shí)含義的詞匯是困難的。維吾爾文中，同一詞干可以演變?yōu)楹芏嗖煌x的詞語，雖然這些詞語的詞形不同，但詞義卻不會(huì)有很大區(qū)別[8]。其中一個(gè)典型例子如表1所示。為了提取單詞的詞義，并考慮特征的數(shù)量，本文以詞干（學(xué)校）作為特征項(xiàng)，以此從文本中提取出詞干集。

表1　維吾爾詞語變體

1.2特征提取

目前，主流的特征提取方法有文檔頻率（DF）、信息增益（IG）、χ2統(tǒng)計(jì)量（CHI）和互信息（MI）等[9]。這些特征選擇方法基本思想都是基于一種評(píng)估函數(shù)，評(píng)估每個(gè)特征詞的價(jià)值，然后根據(jù)價(jià)值將特征詞從高到低進(jìn)行排序，根據(jù)設(shè)定的特征數(shù)量，從高到低提取特征詞作為特征集合，以此獲得具有高區(qū)別能力的特征集并降低特征維數(shù)。本文采用基于MI的特征提取方法，MI根據(jù)特征和類別共同出現(xiàn)的概率，度量特征和類別的相關(guān)性。將預(yù)處理得到的詞干集作為初始特征集，根據(jù)每個(gè)詞干和每個(gè)類別之間的MI值來選擇具有較高類別區(qū)分能力的詞干作為最終特征，進(jìn)一步降低特征維數(shù)[10]。然而，傳統(tǒng)MI特征提取只計(jì)算單個(gè)特征和目標(biāo)類之間的相關(guān)性，沒有考慮文本的上下文特征。

為此，本文對(duì)傳統(tǒng)MI特征提取方案進(jìn)行改進(jìn)，提出利用輸入特征的組合與類別之間的MI代替單一特征與類別的MI，并應(yīng)用前向選擇特征空間MI理論，增強(qiáng)特征選擇算法的選擇能力。

1.2.1傳統(tǒng)MI特征提取算法

MI通常用來測量特征與類別之間的相關(guān)性，MI值越大表明相關(guān)性越大。定義維吾爾文本兩個(gè)特征變量U =(u1，u2，…，uk)和V =(v1，v2，…，vd)之間的互信息為：

式中：(u1，u2，…，uk)和(v1，v2，…，vd)分別為變量U和V的離散值；p(U，V)為一個(gè)聯(lián)合密度函數(shù)；p(U)和p(V)都為邊緣密度函數(shù)。

式（1）中，特征變量V =(v1，v2，…，vd)和類C =(c1，c2，…，ck)之間的MI可表示為：

特征變量v1在類c1中出現(xiàn)的概率越高，則互信息I(c1，v1)就越大，則相關(guān)性越大。

1.2.2改進(jìn)型MI特征提取算法

針對(duì)傳統(tǒng)MI的缺陷，本文提出一種改進(jìn)算法，利用具有多個(gè)特征的特征空間來正則化用于特征選擇的MI，稱為多特征空間正則化互信息（Multi?feature Space Nor?malized Mutual Information，M?FNMI）。使用輸入特征組合與類之間的MI來代替?zhèn)鹘y(tǒng)MI算法中單個(gè)特征與類之間的MI，并融入貪心選擇策略，本文改進(jìn)算法如下：

（1）初始化：設(shè)置F←n個(gè)特征的初始集，F(xiàn) ={f1，f2，…，fn}，初始選擇特征集S←{ }。

（2）根據(jù)式（2），計(jì)算每個(gè)輸入特征?fi∈F與輸出類C之間的MI：I(Cfi)（式（2）中fi= V）。

（3）選擇第一個(gè)特征：找出最大I(Cfi)所對(duì)應(yīng)的特征fi，設(shè)置F←F{fi}，S←{fi}，其中F{fi}表示從F中刪除fi。

（4）貪心選擇：重復(fù)下述過程，直至選擇出期望的特征數(shù)目：

①計(jì)算特征之間的MI：

對(duì)所有的特征( fi，fs)，其中fi∈F，fs∈S，計(jì)算I( fi，fs)。

②選擇下一個(gè)特征：

選擇特征fi∈F，最大化：

接下來，求解特征空間F的信息概率空間。假設(shè)每個(gè)個(gè)體特征fi有ni個(gè)離散值(v1，v2，...，)，每個(gè)離散值vj對(duì)應(yīng)的概率為。每個(gè)個(gè)體特征fi的信息概率空間為：

對(duì)所有個(gè)體特征中選擇出的離散值進(jìn)行組合，形成特征空間F的值，特征空間F的信息概率空間可表示為。其中：()表示特征空間F的值；表示特征空間F的值所對(duì)應(yīng)的概率值。例如，數(shù)據(jù)集A包含兩個(gè)特征f1和f2，值為(v1，v2)=(0，1)，數(shù)據(jù)集A為：，則特征f的信息1概率空間為，特征f的信息概率空2間為，由此可以計(jì)算出特征空間F = f1?f2={f1，f2}的信息概率空間為，其中，第一行的二進(jìn)制數(shù)“00”表示特征f1和f2都有一個(gè)值為0；“01”表示f1有一個(gè)值為0，f2有一個(gè)值為1。另外，特征空間F ={f1，f2}中的特征不需要都是獨(dú)立的，例如：

上述算法中，特征空間只考慮包含兩個(gè)特征，但可以擴(kuò)展到包含兩個(gè)以上特征。

1.3文本分類

文本分類是一種學(xué)習(xí)過程，其利用一個(gè)已被明確分類過的訓(xùn)練文檔集，找出文本特征與文本類別之間的關(guān)系，然后對(duì)此進(jìn)行學(xué)習(xí)，獲得一個(gè)關(guān)系模型，從而對(duì)新的文本進(jìn)行分類[11]。目前，主流的文本分類算法有基于質(zhì)心的分類、樸素貝葉斯分類（NB）、K近鄰分類（KNN）、決策樹分類、神經(jīng)網(wǎng)絡(luò)（NN）分類以及支持向量機(jī)（SVM）分類算法等[12]。文獻(xiàn)[13]通過文本分類實(shí)驗(yàn)，將SVM與其他多種分類算法進(jìn)行比較，發(fā)現(xiàn)SVM的文本分類性能最好，所以本文采用SVM分類器。SVM算法基本思想是尋找出一個(gè)最優(yōu)分類面，最優(yōu)分類面不但能將兩類樣本點(diǎn)正確地分開，而且使兩類的分類間隔最大[14]。SVM中，線性判別函數(shù)為g(x)= wTx + b，分類面函數(shù)為wTx + b = 0。為了使最優(yōu)分類面能準(zhǔn)確分類所有樣本，則需要滿足以下條件：

能夠使式（5）中等于0成立的那些樣本成為支持向量。兩類樣本的分類間隔為：

因此，可利用以下約束優(yōu)化問題來表示最優(yōu)分類面問題，即在約束條件式（5）下，求式（7）的最小值：

為此，可以定義拉格朗日（Lagrange）函數(shù)：

式中，αi≥0為拉格朗日系數(shù)，為了對(duì)w和b求拉格朗日函數(shù)的最小值，將式（8）分別對(duì)w，b，α求偏微分，并令它們等于0，得：

根據(jù)式（9）～式（11），則可將原問題轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問題：

式（12）為一個(gè)求解二次函數(shù)極值問題，存在惟一的最優(yōu)解，若為最優(yōu)解，則：

式中，sgn（·）為符號(hào)函數(shù)。

2　實(shí)驗(yàn)及分析

2.1實(shí)驗(yàn)環(huán)境

為了評(píng)估本文方案的性能，構(gòu)建一個(gè)計(jì)算平臺(tái)，以Intel酷睿i5作為CPU，主頻為2.4 GHz，應(yīng)用Windows 7系統(tǒng)環(huán)境，利用Matlab 2011進(jìn)行實(shí)驗(yàn)。

對(duì)于維吾爾文的文本分類應(yīng)用，目前還沒有可使用的標(biāo)準(zhǔn)文本集。由于本文方案是應(yīng)用于犯罪數(shù)字取證領(lǐng)域，所以本文從新疆公安犯罪數(shù)據(jù)庫中的案情、新疆公安網(wǎng)公布的治安新聞以及人民網(wǎng)維吾爾文版的新聞上收集了2 500篇文本，通過人工方式將其分為7類犯罪：危害國家安全；危害公共安全；侵犯公民人身權(quán)利；破壞市場經(jīng)濟(jì)秩序；妨害社會(huì)管理秩序；侵犯財(cái)產(chǎn)；貪污賄賂。其中，1 600篇文本作為訓(xùn)練集，900篇作為測試集。各類的訓(xùn)練和測試樣本數(shù)如表2所示。

表2　分類文本庫

2.2性能指標(biāo)

本文采用分類中常用的性能指標(biāo)F1值來評(píng)估方案性能，其由準(zhǔn)確率（P）和召回率（R）計(jì)算獲得：

式中：a表示正確分類的文本數(shù)；b表示分類為該類，但不屬于該類的文本數(shù)；c表示屬于該類，但未被分類到該類的文本數(shù)。通常將準(zhǔn)確率和召回率進(jìn)行綜合，得到評(píng)估文本分類質(zhì)量的F1值，表達(dá)式如下：

通常情況下，方案的F1值越高，則分類效果越好。實(shí)驗(yàn)中，本文將各個(gè)類別的F1值求平均，得到最終性能指標(biāo)，即F1平均值。

2.3分類實(shí)驗(yàn)

實(shí)驗(yàn)中，首先對(duì)維吾爾文文本集進(jìn)行預(yù)處理，為了方便后續(xù)處理，把文本轉(zhuǎn)換成UTF?8二進(jìn)制編碼格式。然后，過濾掉文本中的非維吾爾文字符和停用詞。預(yù)處理結(jié)束后，獲得一個(gè)具有24 420個(gè)特征的初始特征集。然后進(jìn)行詞干提取，將同一詞根演變而來的特征進(jìn)行聚合，使初始特征項(xiàng)降維到13 826個(gè)。然后通過本文提出的M?FNMI特征提取算法，提取出和類別具有高互信息（高區(qū)分度）的詞干作為最終特征。設(shè)定每個(gè)類別提取500～2 500個(gè)特征詞。表3描述了危害國家安全類別和侵犯公民人身權(quán)利類別中前5名的特征詞，這些特征詞具有最強(qiáng)的區(qū)別能力。

表3　類別的前5名高區(qū)分度的特征詞

由于本文分類算法采用傳統(tǒng)的SVM算法，而特征提取算法采用提出的新算法。所以，為了更好地證明本文方案對(duì)維吾爾文文本分類的性能，將本文特征提取算法與傳統(tǒng)MI、文獻(xiàn)[5]、文獻(xiàn)[6]中的特征提取算法進(jìn)行比較。為了實(shí)現(xiàn)更好地比較，設(shè)定各種方法都采用同樣的分類算法，即SVM。在各類別特征集大小為500，1 000，1 500，2 000和2 500情況下分別進(jìn)行分類實(shí)驗(yàn)，并計(jì)算分類性能指標(biāo)F1。圖1為本文方案在不同特征集大小下，各類別分類的F1值。圖2為本文方案和傳統(tǒng)MI、文獻(xiàn)[5]、文獻(xiàn)[6]方案的比較，其中性能指標(biāo)為各類別分類的F1平均值。

圖1　不同特征集大小下，本文方案中各類別分類的F1值

從圖1可以看出，在不同特征集大小下，各個(gè)類別的分類精度不等，其中“侵犯公民人身權(quán)利”類別分類精度最高。從圖2可以看出，隨著特征集大小的增加，各種方法的分類精度都隨之增加，然后趨向穩(wěn)定或有所下降。這是因?yàn)樘卣骷^大時(shí)，選入了有些不重要的“噪聲”特征，影響了分類效率。當(dāng)特征集大小為2 000時(shí)，各種方案都獲得了最高性能，其中本文方案獲得的F1值為0.91，分別比傳統(tǒng)MI、文獻(xiàn)[5]、文獻(xiàn)[6]高出約23%，11%和6%。

圖2　不同特征提取方案中分類的F1平均值

3　結(jié)　語

本文針對(duì)維吾爾文表述的數(shù)字文本取證應(yīng)用，提出一種基于文本分類的取證方案，利用提出的多特征空間正則化互信息（M?FNMI）對(duì)維吾爾文文本進(jìn)行特征提取，利用SVM算法對(duì)特征進(jìn)行分類。實(shí)驗(yàn)中，設(shè)定7類犯罪類型，將本文方案與現(xiàn)有方案進(jìn)行比較，結(jié)果表明，本文方案具有較高的分類性能，能夠?yàn)樾陆膊块T進(jìn)行數(shù)字取證提供有力依據(jù)。

注：本文通訊作者為亞森·艾則孜。

參考文獻(xiàn)

[1]程春惠，何欽銘.面向不均衡類別樸素貝葉斯犯罪案件文本分類[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（35）：126?128.

[2]劉露，彭濤，左萬利，等.一種基于聚類的PU主動(dòng)文本分類方法[J].軟件學(xué)報(bào)，2013，24（11）：2571?2583.

[3]熱依萊木·帕爾哈提，孟祥濤，艾斯卡爾·艾木都拉.基于區(qū)分性關(guān)鍵詞模型的維吾爾文本情感分類[J].計(jì)算機(jī)工程，2014，40（10）：132?136.

[4]吐爾地·托合提，艾克白爾·帕塔爾，艾斯卡爾·艾木都拉.語義詞特征提取及其在維吾爾文文本分類中的應(yīng)用[J].中文信息學(xué)報(bào)，2014，28（4）：140?144.

[5]阿力木江·艾沙，吐爾根·依布拉音，庫爾班·吾布力.基于SVM的維吾爾文文本分類研究[J].計(jì)算機(jī)工程與科學(xué)，2012，34 （12）：150?154.

[6]阿力木江·艾沙，庫爾班·吾布力，吐爾根·依布拉音.維吾爾文Bi?gram文本特征提取[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（3）：216?221.

[7]UYSAL A K，GUNAL S. The impact of preprocessing on text classification [J]. Information processing &management，2014，50（7）：104?112.

[8]陳卿，袁保社，李曉，等.基于模板匹配的印刷維吾爾文字符識(shí)別研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（4）：119?122.

[9]DENG H，RUNGER G，TUV E，et al. A time series forest for classification and feature extraction [J]. Information sciences，2013，239（4）：142?153.

[10]OVEISI F，OVEISI S，ERFANIAN A，et al. Tree?structured feature extraction using mutual information [J]. IEEE transac?tions on neural networks & learning systems，2012，23（1）：127?137.

[11]劉露，彭濤，左萬利，等.一種基于聚類的PU主動(dòng)文本分類方法[J].軟件學(xué)報(bào)，2013，24（11）：2571?2583.

[12]趙輝，劉懷亮，張倩.一種基于復(fù)雜網(wǎng)絡(luò)的中文文本分類算法[J].情報(bào)學(xué)報(bào)，2012，31（11）：1179?1186.

[13]LIU Zhijie，LYU Xueqiang，LIU Kun，et al. Study on SVM compared with the other text classification methods[C]// Interna?tional Workshop on Education Technology & Computer Science. Wuhan，Hubei，China：[s.n.]，2010：219?222.

[14]CAO J F，CHEN J J. An improved web text classification al?gorithm based on SVM?KNN [J]. Applied mechanics & materials，2013，27（8）：1305?1308.

[15]胡文軍，王士同.隱私保護(hù)的SVM快速分類方法[J].電子學(xué)報(bào)，2012，40（2）：280?286.

Research on Uyghur digital forensics based on text categorization

RUXIANGULI Abudurexiti，HE Yifeng，YASEN Aizezi
（Department of Information Security & Engineering，Xinjiang Police College，Urumqi 830013，China）

Abstract：For the crime forensics of digital texts written in Uighur，a Uyghur digital forensic scheme based on text categori?zation is proposed. The Uyghur texts are preprocessed to filter the non Uyghur characters and stop words. A multi?feature space normalized mutual information（M?FNMI）algorithm is proposed. The mutual information（MI）between input feature combina?tion and class is used to replace the MI between the single feature and class，so as to extract more accurate feature words. The support vector machine（SVM）algorithm is used to classify those features. Experimental results show that the proposed scheme has higher classification accuracy，and can provide a basis for criminal evidence collection.

Keywords：digital forensic；text categorization；Uyghur；mutual information；support vector machine

中圖分類號(hào)：TN911?34；TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004?373X（2016）10?0009?05

doi：10.16652/j.issn.1004?373x.2016.10.003

收稿日期：2015?09?24

基金項(xiàng)目：國家社會(huì)科學(xué)基金科研項(xiàng)目（13CFX055）；新疆維吾爾自治區(qū)自然科學(xué)基金科研項(xiàng)目（2015211A016）；新疆維吾爾自治區(qū)高?？蒲杏?jì)劃科學(xué)研究重點(diǎn)項(xiàng)目（XJEDU2013I34）

作者簡介：如先姑力·阿布都熱西提（1976—），女，新疆喀什人，講師，碩士。研究方向?yàn)樾畔踩?、?shù)字取證等。賀一峰（1978—），男，新疆烏魯木齊人，講師，碩士。研究方向?yàn)樾畔踩?、?shù)字取證等。亞森·艾則孜（1975—），男，新疆庫車人，教授，碩士，國家電子數(shù)據(jù)司法鑒定員。研究方向?yàn)樾畔踩?、自然語言處理等。