一种改进的静态取证数据挖掘算法_图文

1、计算机时代2009年第4期0引言随着计算机信息技术的发展和普及,计算机犯罪案件的发生越来越频繁,如何最大限度地获取计算机犯罪相关的电子证据,将犯罪分子绳之以法,有效地打击计算机犯罪,成为了目前的研究热点,其中涉及的技术就是计算机取证(computer forensics 技术。计算机取证是对电子证据的发现、获取、传输、存贮、分析、提交和报告的过程,大体上可分为三个阶段:电子证据信息的获取和保存、电子证据信息的分析、犯罪证据的呈示。其中证据信息的分析是关键环节,其主要任务是从证据信息中挖掘出强有力直接与间接犯罪证据以及各证据在时间、空间上的相互关系。根据取证时机不同,计算机取证技术可分为事后的静

2、态取证和实时的动态取证两种。实施静态取证的关键是从海量的数据中筛选挖掘有效信息,审查判断出与案件相关的、反映案件客观事实的、法庭接受的电子证据。因此,对海量的电子证据数据进行筛选挖掘的算法研究,有着十分重大的理论价值和实际意义。电子证据数据一般都具有很强相关性,本文主要研究以皮尔森关联系数为相关性度量的强相关项目对的挖掘算法。1皮尔森关联系数以及Taper 算法从统计角度,相关性度量描述了变量之间关联性的强弱。对于离散变量而言,变量之间的关联关系可以用皮尔森关联系数来表示。关联系数是皮尔森关联系数在二元变量时的一种特殊形式。假定有两个二元变量A 和B,其取值的分布情况如表1所示。表1变量取制分

3、布图A列和01BP (00P (00P (001P (00P (00P (00行和P (00P (00N此时,关联系数可以按以下公式进行计算:其中,P (ij表示同时满足A=i 和B=j 的对象的个数(i=0,1;j=0,l。此外,P (i +表示满足A=i 的对象的个数(不必考虑B 的取值,P (+j表示满足B=j 的对象的个数(不必考虑A 的取值。项目对A,B的关联系数的上界upper(A,B可以最终表示为公式。此上界用来过滤掉那些不可能满足条件的项目对,提高算法的效率。2基于1NF 的强相关项目对的挖掘算法改进的Taper+算法为了减少候选项目对的测试代价,我们利用1NF 的性质,对Ta

4、per 算法进行改进,设计了改进的Taper+算法,在挖掘过程中减少候选项目对的数目,以提高算法的效率。Taper+算法分为两个步骤:候选项目对的产生和剪枝。在候选项目对产生过程中,利用1NF 的性质减少候选项目对的数目:在剪枝过程,利用上界过滤掉那些不可能满足条件的项目对,避免计算那些剪枝掉的项目对的支持度的代价。我们依据以下四个结果,说明Taper+算法的优势。原始的Taper算法在剪枝过程之前有 个候选项目对。因为原始的Taper 算法并未考虑关系表的特殊性,所以它生成了所有可能的组合。Taper +算法在剪枝过程之前只有个候选项目对。显然,根据和,在第一步中(即候选项目对的产生,Tap

5、er+算法比原始的Taper 算法少生成 个关系数据库上不正确的项目对,其数量随属性与属性值的个数增大。而且,这些个关系数据库上不正确的项目对在利用关联一种改进的静态取证数据挖掘算法徐宏斌,王燕(贵州警官职业学院,贵州贵阳550005摘要:随着计算机犯罪案件的日益增加,采集犯罪证据的计算机取证技术已成为目前的研究热点。计算机取证有事后的静态取证和实时的动态取证两种方法。静态取证的关键是从海量的数据中筛选挖掘出与案件相关的、反映案件客观事实的、有效的犯罪证据信息。基于已有静态取证分析方法的不足,文章提出了一种改进的静态取证数据挖掘算法,并通过对大量数据的测试证明,该算法不但可行而且准确性及效率较

6、高。关键词:计算机取证;静态取证;电子证据;数据挖掘··7Computer Era No.42009系数的上界剪枝过程中一定不能被裁减掉,因此,进一步增加了计算的代价。令R1(和R2(分别是Taper算法和Taper+算法未被裁减掉的项目对的个数(给定最小相关阈值,且令R3(代表个关系数据库上不正确的项目对中未被减掉的项目对的个数,则有R1(=R2(+R3(。因此,Taper算法不光要在剪枝过程中检查个多余的项目对,而且还要在扫描数据库时多检查R3(个项目对;而通过利用1NF的性质,Taper+算法至少在剪枝和扫描数据库两个步骤中降低了计算代价。这在大规模数据集上进行数据挖

7、掘时是非常重要的。Taper+算法使用以下公式进行剪枝:此上界用来过滤掉那些不可能满足条件的项目对,从而避免了计算那些剪枝掉的项目对的支持度。然而,从计算公式不难看出,此上界是始终大于0的,因此,如果最小相关阈值被设定为一个非常小的值,比如0.01,被剪枝掉的候选项目对的个数会非常之少,使得基于上界的剪枝技术的效果变得很差。为此,本文利用关系表的特殊结构来减少候选项目对的个数。其基本思想描述如下。不失一般性,设属性A i和A j属性值的集合分别为V i=u1, u2,u p和V j=v1,v2,v q。这两个属性可以产生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导出。更进一步讲,不需要直接在扫描数据库的过程中计算包含v q的项目对的支持度。因此,在扫描数据库中只需计算(p-1*(q-1个项目对。在Taper+算法中,在不使用剪枝技术的前提下,在扫描数据库的过程中至多需要检查个项目对的支持度。从这个结果可以知道,在基于上界的剪枝技术效果不尽如人

9、意的时候,可以有效地减少项目对的个数,这就使得Taper+算法在最小相关阈值很小的时候,仍可以进行高效的项目对挖掘。Taper+算法的流程如下。在算法的第一步,利用关系数据库的特殊结构,生成所有符合1NF的候选项目对,同时保证没有关系数据库上无意义的项目对。在算法的第二步,由于在上一步己经得到了所有的单个项目的支持度,所以可以利用上界进行剪枝,过滤掉那些不可能满足条件的项目对,避免扫描数据库、计算那些剪枝掉的项目对的支持度。在算法的第三步,对数据库进行扫描。在扫描过程中对遇到的每一条记录,查看候选项目对集合中的每一个项目对是否包含在该记录中。如果某个候选项目对包含在该记录中,则将此候选项目对的

10、支持度增加1。在数据库扫描结束之后,可得到每个候选项目对的支持度。利用以下公式就可计算每个项目对的关联系数,然后输出那些关联系数大于最小相关阈值的项目对。Taper+算法:首先候选项目对产生产生所有的符合1NF的候选项目对候选相关项目对剪枝用上界进行候选项目对剪枝数据扫描计算最终结果3试验结果取证证据分析中一般使用有效率和误取率作为系统的性能指标。有效率和误取率总是紧密相关的,增加有效率常常要以误取率的增加为代价,而误取率偏高使取证系统对原本不是犯罪相关的事件产生了错误的取证,将导致取证的功效降低。因此,既能增加有效率又能降低误取率是取证系统设计希望达到的目标。为了验证本算法的效果,我们首先使

11、用Java语言编程实现了该算法,然后从本市网监支队提供的数据中选取了10组不同检测数据集合,每组包括2万条记录,其中包含了很多近似的无关数据。通过算法程序我们分别对每组记录进行数据筛选检测实验,反复实验10多次后,得到一个近似的平均结果:本算法的误取率在3%以下时,有效率可达96%以上,与其它的数据检测算法相比性能有极大的提高。本算法也存在一些问题,比如仍然有某些分布很特殊的证据信息记录集聚类效果不明显,仍存在误报和漏报问题,还需进一步改进和完善。4结束语本文提出了一种改进的用于海量电子证据的筛选挖掘算法。测试实验表明,此法可以较好地提高证据检测效率和降低误取证率,因而具有较高的可行性和实用性。下一步的工作拟将贝叶斯算法、遗传算法等思想与数据挖掘原理相结合,以进一步提高取证系统的有效率和准确率,改善系统的综合性能。参考文献:Closed Correlated Patterns.In:Proc.of PAKD