一種改進的靜態(tài)取證數(shù)據(jù)挖掘算法_圖文

1、計算機時代2009年第4期0引言隨著計算機信息技術(shù)的發(fā)展和普及,計算機犯罪案件的發(fā)生越來越頻繁,如何最大限度地獲取計算機犯罪相關(guān)的電子證據(jù),將犯罪分子繩之以法,有效地打擊計算機犯罪,成為了目前的研究熱點,其中涉及的技術(shù)就是計算機取證(computer forensics 技術(shù)。計算機取證是對電子證據(jù)的發(fā)現(xiàn)、獲取、傳輸、存貯、分析、提交和報告的過程,大體上可分為三個階段:電子證據(jù)信息的獲取和保存、電子證據(jù)信息的分析、犯罪證據(jù)的呈示。其中證據(jù)信息的分析是關(guān)鍵環(huán)節(jié),其主要任務(wù)是從證據(jù)信息中挖掘出強有力直接與間接犯罪證據(jù)以及各證據(jù)在時間、空間上的相互關(guān)系。根據(jù)取證時機不同,計算機取證技術(shù)可分為事后的靜

2、態(tài)取證和實時的動態(tài)取證兩種。實施靜態(tài)取證的關(guān)鍵是從海量的數(shù)據(jù)中篩選挖掘有效信息,審查判斷出與案件相關(guān)的、反映案件客觀事實的、法庭接受的電子證據(jù)。因此,對海量的電子證據(jù)數(shù)據(jù)進行篩選挖掘的算法研究,有著十分重大的理論價值和實際意義。電子證據(jù)數(shù)據(jù)一般都具有很強相關(guān)性,本文主要研究以皮爾森關(guān)聯(lián)系數(shù)為相關(guān)性度量的強相關(guān)項目對的挖掘算法。1皮爾森關(guān)聯(lián)系數(shù)以及Taper 算法從統(tǒng)計角度,相關(guān)性度量描述了變量之間關(guān)聯(lián)性的強弱。對于離散變量而言,變量之間的關(guān)聯(lián)關(guān)系可以用皮爾森關(guān)聯(lián)系數(shù)來表示。關(guān)聯(lián)系數(shù)是皮爾森關(guān)聯(lián)系數(shù)在二元變量時的一種特殊形式。假定有兩個二元變量A 和B,其取值的分布情況如表1所示。表1變量取制分

3、布圖A列和01BP (00P (00P (001P (00P (00P (00行和P (00P (00N此時,關(guān)聯(lián)系數(shù)可以按以下公式進行計算:其中,P (ij表示同時滿足A=i 和B=j 的對象的個數(shù)(i=0,1;j=0,l。此外,P (i +表示滿足A=i 的對象的個數(shù)(不必考慮B 的取值,P (+j表示滿足B=j 的對象的個數(shù)(不必考慮A 的取值。項目對A,B的關(guān)聯(lián)系數(shù)的上界upper(A,B可以最終表示為公式。此上界用來過濾掉那些不可能滿足條件的項目對,提高算法的效率。2基于1NF 的強相關(guān)項目對的挖掘算法改進的Taper+算法為了減少候選項目對的測試代價,我們利用1NF 的性質(zhì),對Ta

4、per 算法進行改進,設(shè)計了改進的Taper+算法,在挖掘過程中減少候選項目對的數(shù)目,以提高算法的效率。Taper+算法分為兩個步驟:候選項目對的產(chǎn)生和剪枝。在候選項目對產(chǎn)生過程中,利用1NF 的性質(zhì)減少候選項目對的數(shù)目:在剪枝過程,利用上界過濾掉那些不可能滿足條件的項目對,避免計算那些剪枝掉的項目對的支持度的代價。我們依據(jù)以下四個結(jié)果,說明Taper+算法的優(yōu)勢。原始的Taper算法在剪枝過程之前有 個候選項目對。因為原始的Taper 算法并未考慮關(guān)系表的特殊性,所以它生成了所有可能的組合。Taper +算法在剪枝過程之前只有個候選項目對。顯然,根據(jù)和,在第一步中(即候選項目對的產(chǎn)生,Tap

5、er+算法比原始的Taper 算法少生成 個關(guān)系數(shù)據(jù)庫上不正確的項目對,其數(shù)量隨屬性與屬性值的個數(shù)增大。而且,這些個關(guān)系數(shù)據(jù)庫上不正確的項目對在利用關(guān)聯(lián)一種改進的靜態(tài)取證數(shù)據(jù)挖掘算法徐宏斌,王燕(貴州警官職業(yè)學(xué)院,貴州貴陽550005摘要:隨著計算機犯罪案件的日益增加,采集犯罪證據(jù)的計算機取證技術(shù)已成為目前的研究熱點。計算機取證有事后的靜態(tài)取證和實時的動態(tài)取證兩種方法。靜態(tài)取證的關(guān)鍵是從海量的數(shù)據(jù)中篩選挖掘出與案件相關(guān)的、反映案件客觀事實的、有效的犯罪證據(jù)信息?；谝延徐o態(tài)取證分析方法的不足,文章提出了一種改進的靜態(tài)取證數(shù)據(jù)挖掘算法,并通過對大量數(shù)據(jù)的測試證明,該算法不但可行而且準(zhǔn)確性及效率較

6、高。關(guān)鍵詞:計算機取證;靜態(tài)取證;電子證據(jù);數(shù)據(jù)挖掘··7Computer Era No.42009系數(shù)的上界剪枝過程中一定不能被裁減掉,因此,進一步增加了計算的代價。令R1(和R2(分別是Taper算法和Taper+算法未被裁減掉的項目對的個數(shù)(給定最小相關(guān)閾值,且令R3(代表個關(guān)系數(shù)據(jù)庫上不正確的項目對中未被減掉的項目對的個數(shù),則有R1(=R2(+R3(。因此,Taper算法不光要在剪枝過程中檢查個多余的項目對,而且還要在掃描數(shù)據(jù)庫時多檢查R3(個項目對;而通過利用1NF的性質(zhì),Taper+算法至少在剪枝和掃描數(shù)據(jù)庫兩個步驟中降低了計算代價。這在大規(guī)模數(shù)據(jù)集上進行數(shù)據(jù)挖

7、掘時是非常重要的。Taper+算法使用以下公式進行剪枝:此上界用來過濾掉那些不可能滿足條件的項目對,從而避免了計算那些剪枝掉的項目對的支持度。然而,從計算公式不難看出,此上界是始終大于0的,因此,如果最小相關(guān)閾值被設(shè)定為一個非常小的值,比如0.01,被剪枝掉的候選項目對的個數(shù)會非常之少,使得基于上界的剪枝技術(shù)的效果變得很差。為此,本文利用關(guān)系表的特殊結(jié)構(gòu)來減少候選項目對的個數(shù)。其基本思想描述如下。不失一般性,設(shè)屬性A i和A j屬性值的集合分別為V i=u1, u2,u p和V j=v1,v2,v q。這兩個屬性可以產(chǎn)生p*q個項目對。然而,這p*q個項目對并不都是必須的,因為sup(u k=

8、sup (u k v1+sup(u k v2+sup(u k v q,即,sup(u k v q=sup(u k-sup(u k v1-sup(u k v2-sup(u k,v q-1。換言之,支持度sup(u k v q可以從sup(u k,sup(u k v1,sup(u k v2,sup(u k v q-1導(dǎo)出。更進一步講,不需要直接在掃描數(shù)據(jù)庫的過程中計算包含v q的項目對的支持度。因此,在掃描數(shù)據(jù)庫中只需計算(p-1*(q-1個項目對。在Taper+算法中,在不使用剪枝技術(shù)的前提下,在掃描數(shù)據(jù)庫的過程中至多需要檢查個項目對的支持度。從這個結(jié)果可以知道,在基于上界的剪枝技術(shù)效果不盡如人

9、意的時候,可以有效地減少項目對的個數(shù),這就使得Taper+算法在最小相關(guān)閾值很小的時候,仍可以進行高效的項目對挖掘。Taper+算法的流程如下。在算法的第一步,利用關(guān)系數(shù)據(jù)庫的特殊結(jié)構(gòu),生成所有符合1NF的候選項目對,同時保證沒有關(guān)系數(shù)據(jù)庫上無意義的項目對。在算法的第二步,由于在上一步己經(jīng)得到了所有的單個項目的支持度,所以可以利用上界進行剪枝,過濾掉那些不可能滿足條件的項目對,避免掃描數(shù)據(jù)庫、計算那些剪枝掉的項目對的支持度。在算法的第三步,對數(shù)據(jù)庫進行掃描。在掃描過程中對遇到的每一條記錄,查看候選項目對集合中的每一個項目對是否包含在該記錄中。如果某個候選項目對包含在該記錄中,則將此候選項目對的

10、支持度增加1。在數(shù)據(jù)庫掃描結(jié)束之后,可得到每個候選項目對的支持度。利用以下公式就可計算每個項目對的關(guān)聯(lián)系數(shù),然后輸出那些關(guān)聯(lián)系數(shù)大于最小相關(guān)閾值的項目對。Taper+算法:首先候選項目對產(chǎn)生產(chǎn)生所有的符合1NF的候選項目對候選相關(guān)項目對剪枝用上界進行候選項目對剪枝數(shù)據(jù)掃描計算最終結(jié)果3試驗結(jié)果取證證據(jù)分析中一般使用有效率和誤取率作為系統(tǒng)的性能指標(biāo)。有效率和誤取率總是緊密相關(guān)的,增加有效率常常要以誤取率的增加為代價,而誤取率偏高使取證系統(tǒng)對原本不是犯罪相關(guān)的事件產(chǎn)生了錯誤的取證,將導(dǎo)致取證的功效降低。因此,既能增加有效率又能降低誤取率是取證系統(tǒng)設(shè)計希望達到的目標(biāo)。為了驗證本算法的效果,我們首先使

11、用Java語言編程實現(xiàn)了該算法,然后從本市網(wǎng)監(jiān)支隊提供的數(shù)據(jù)中選取了10組不同檢測數(shù)據(jù)集合,每組包括2萬條記錄,其中包含了很多近似的無關(guān)數(shù)據(jù)。通過算法程序我們分別對每組記錄進行數(shù)據(jù)篩選檢測實驗,反復(fù)實驗10多次后,得到一個近似的平均結(jié)果:本算法的誤取率在3%以下時,有效率可達96%以上,與其它的數(shù)據(jù)檢測算法相比性能有極大的提高。本算法也存在一些問題,比如仍然有某些分布很特殊的證據(jù)信息記錄集聚類效果不明顯,仍存在誤報和漏報問題,還需進一步改進和完善。4結(jié)束語本文提出了一種改進的用于海量電子證據(jù)的篩選挖掘算法。測試實驗表明,此法可以較好地提高證據(jù)檢測效率和降低誤取證率,因而具有較高的可行性和實用性。下一步的工作擬將貝葉斯算法、遺傳算法等思想與數(shù)據(jù)挖掘原理相結(jié)合,以進一步提高取證系統(tǒng)的有效率和準(zhǔn)確率,改善系統(tǒng)的綜合性能。參考文獻:Closed Correlated Patterns.In:Proc.of PAKD