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

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

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

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

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

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

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

7、掘時(shí)是非常重要的。Taper+算法使用以下公式進(jìn)行剪枝:此上界用來過濾掉那些不可能滿足條件的項(xiàng)目對,從而避免了計(jì)算那些剪枝掉的項(xiàng)目對的支持度。然而,從計(jì)算公式不難看出,此上界是始終大于0的,因此,如果最小相關(guān)閾值被設(shè)定為一個(gè)非常小的值,比如0.01,被剪枝掉的候選項(xiàng)目對的個(gè)數(shù)會(huì)非常之少,使得基于上界的剪枝技術(shù)的效果變得很差。為此,本文利用關(guān)系表的特殊結(jié)構(gòu)來減少候選項(xiàng)目對的個(gè)數(shù)。其基本思想描述如下。不失一般性,設(shè)屬性A i和A j屬性值的集合分別為V i=u1, u2,u p和V j=v1,v2,v q。這兩個(gè)屬性可以產(chǎn)生p*q個(gè)項(xiàng)目對。然而,這p*q個(gè)項(xiàng)目對并不都是必須的,因?yàn)閟up(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)出。更進(jìn)一步講,不需要直接在掃描數(shù)據(jù)庫的過程中計(jì)算包含v q的項(xiàng)目對的支持度。因此,在掃描數(shù)據(jù)庫中只需計(jì)算(p-1*(q-1個(gè)項(xiàng)目對。在Taper+算法中,在不使用剪枝技術(shù)的前提下,在掃描數(shù)據(jù)庫的過程中至多需要檢查個(gè)項(xiàng)目對的支持度。從這個(gè)結(jié)果可以知道,在基于上界的剪枝技術(shù)效果不盡如人

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

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

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