论文部分内容阅读
[摘 要]网络日志数据量日益增大。如何从巨大的网络数据中提取有效信息是数据研究人员一直关心的问题。入侵模式挖掘系统（Intrusion Digger）结合了数据挖掘技术与入侵检测技术，旨在通过发现关联规则而对网络数据进行判别。最小支持度小于所有支持度的项集称为频繁项集，简称频集。基于划分改进的Apriori算法明显优越于原来的算法。基于划分改进的Apriori算法为入侵模式挖掘系统的设计提供了重要的理论支持。
[关键词]入侵模式挖掘系统 基于划分改进的Apriori算法 数据挖掘
[中图分类号] G642 [文献标识码] A [文章编号] 2095-3437（2013）15-0036-02
一、系统的实现原理
众所周知，网络日志数据量日益增大，从巨大的网络数据中提取有用信息是入侵模式挖掘系统所要完成的工作。在这里我们使用数据挖掘的关联分析方法，即产生频繁项集与关联规则。关联规则就是我们得到的有用信息。在得到关联规则后，我们便可以使用关联规则对测试数据进行分析，判断测试数据是正常数据还是非正常数据。对于判断的结果，我们用一个评价体系来评测判断结果的好坏。入侵模式挖掘系统结合了数据挖掘技术与入侵检测技术，旨在通过发现关联规则而对网络数据来进行判别。因此，根据以上分析，入侵模式挖掘系统的总体大致设计图如图1.1所示。
■
图1.1 入侵模式挖掘系统总体设计图
图1.1中方框内为数据或文件如原始网络日志数据、测试结果文件等，初步设计有三个大的子系统，分别是模式挖掘系统、测试系统、评价系统。箭头代表数据的流向或者结果的输出，椭圆框内为入侵模式挖掘系统的初步设计的子系统。
二、系统的设计算法分析
（一）Apriori算法
本系统采用关联分析方法中的Apriori算法作为核心算法。目前，该算法是挖掘布尔关联规则频繁项集算法中最有影响力的一种，基于两阶段频集思想的递推算法是其核心。在此，最小支持度小于所有支持度的项集称为频繁项集，简称频集。[1]在分类上该关联规则属于单层、单维和布尔关联规则，该关联规则为了生成所有频集，采用了递推的方法。
算法思路：第一步，找出所有出现的频繁性至少和预定义的最小支持度一样的频集。第二步，由频集产生必须满足最小可信度和最小支持度的强关联规则。第三步，使用第一步找到的频集产生只包含集合项的所有规则，其中每一条定义为中规则的右部只有一项的规则。第四步，大于用户给定的最小可信度的规则被留下来生成我们需要的规则。
程序算法如下：
（1）L1 = find_frequent_1_itemset（D）；
（2）for（k = 2； Lk-1≠φ； k++）{
（3） Ck = apriori_gen（Lk-1）；
（4） for each t ∈ D{
（5） Ck = subset（Ck，t）；
（6） For each c ∈ Ct c.count++； }
（7）Lk = {c∈Ck| c.count > min_sup} }
（8）retrurn L = ∪Lk
该算法中首先产生频繁1项集L1，其次产生频繁2项集L2，然后直到有一个频繁r值使得对应项集Lr为空，此时算法终止。Ck中的项集是用来产生频集的候选项集，最终的频集Lk一定是集合Ck的一个子集。在第k次循环中，算法先产生候选项k项集的集合Ck，Ck中的每一个项集属于项集Lk-1的频集来产生的下一个连接集合。Ck中的每个元素都需要在数据库中进行验证，然后才能决定该项是否能够加入频集Lk中。
Apriori算法的两个严重不足会导致挖掘的效率非常低。一个方面，该算法在每进行一次迭代的时候扫描一次数据库，多次扫描数据库带来巨大I/O开销。另一个方面，该算法在迭代过程中需要在内存中产生、处理和保存数量巨大的候选频集，这也导致算法在深度和广度上的适应性很差。
（二）基于划分改进的Apriori算法
为了提高Apriori算法的效率，需要对Apriori算法进行改进。本系统引入了一种基于划分改进的Apriori算法，该算法只需要扫描数据库两次。第一次扫描中，将产生一组潜在的频集，这组项集是最后需要确定的频集的超集，它也可能包含错误的选择，但绝对不可能漏掉正确的选择。第二次扫描中，对这些潜在的频集进一步计算它在整个数据库中的实际支持度，可以最后确定所求得的真正的频集。
算法思路：第一步，将整个数据库尽可能划分成N个子块。第二步，针对每一个子块单独产生一组潜在的频集。第三步，将上一步所有潜在的频集合并为一个全局的候选频集。第四步，在整个数据库中，计算每个候选频集的实际支持度，从而确定最后有用的频集。
程序算法如下：
（1） P=partion_database（D）
（2）n=number of partitions
（3）for i=1 to n begin
（4）read_in_partition（PiP）
（5）LPi=gen_large_itemset（Pi）
（6）end
（7）for（i=2；LPi=φ，，J=1，2，…，n； i++）do
（8）CGi=ULPi
（9）forall candidates c∈CG do begin
（10）c.count++；
（11）Lk={c∈Ck|c.count≥min_sup}
（12）end （13）answer=UkLk；
（14）Produce gen_large_itemset（Pi，min_sup）
（15）L1={Pi}；
（16）for（k=2；Lk-1≠？覫；k++）do begin
（17）Ck=apriori_gen（Lk-1，min_sup）；
（18）forall transactions∈tPi do begin
（19）Ct=subset（Ck，t）；
（20）forall candidations∈cCt do
（21）c.count++；
（22）end
（23）Lk={c= Ck|c.count≥min_sup*n}
（24）end
（25）return Lk
（26）Produce apriori_gen（Lk-1，min_sup）
（27）forall items l1∈Lk-1
（28）forall items l2∈Lk-1
（29）if（（l1[1]=l2[2]（∧…∧ l1[k-1]= l2[k-2]）∧（ l1[k-1] ？刍l2[k-2]））do begin
（30）c=l1？茌l2；
（31）if has_infrequent_itemset（c， Lk-1）
（32）delete c；
（33）else Ck=Ck∨{c}
（34）end；
（35）return Ck
（36）Produce has_infrequent_subset（c，Lk-1）
（37）forall （k-1）subset s of c
（38）if s？埸Lk-1 return true；
（39）else return false
通过对基于划分改进的Apriori算法解析，我们发现该算法有三大优点。
优点1、两种算法扫描次数相比，基于划分改进的Apriori算法扫描数据库次数少。
优点2、基于划分改进的Apriori算法第一次扫描数据库产生的一组潜在的既有需要的也有不需要的频集，它为第二次扫描数据库进行计算及确认最后挖掘出有效频集做了铺垫。
优点3、基于划分改进的Apriori算法进行数据挖掘是将数据库划分成N个子块，先对每个子块单独产生一组频集，然后再合并所有独立产生的各组频集构成一个全局的候选频集。在数据量逐渐增多的情况下，这种“以大划小，以小并行”的思想，可以使数据挖掘的效率大大提高。
综上，通过分析比较可以看出，基于划分改进的Apriori算法跟Apriori算法相比，确实有了相当不错的改进，数据挖掘的效率大大提高了。基于划分改进的Apriori算法为入侵模式挖掘系统的设计提供了重要的理论支持。
[ 参 考 文 献 ]
[1] 刘明辉，周萍.基于Web挖掘的网站优化系统的研究[J].长春大学学报（自然科学版），2009，19（3）.
[2] aul Ammann，Duminda wijesekera and Saket kaushie. Scalable，graph-based network vulnerability analysis[A]. CCS’02[C]， Washington， DC， USA，2002.18-22.
[责任编辑：戴祯杰]
[关键词]入侵模式挖掘系统 基于划分改进的Apriori算法 数据挖掘
[中图分类号] G642 [文献标识码] A [文章编号] 2095-3437（2013）15-0036-02
一、系统的实现原理
众所周知，网络日志数据量日益增大，从巨大的网络数据中提取有用信息是入侵模式挖掘系统所要完成的工作。在这里我们使用数据挖掘的关联分析方法，即产生频繁项集与关联规则。关联规则就是我们得到的有用信息。在得到关联规则后，我们便可以使用关联规则对测试数据进行分析，判断测试数据是正常数据还是非正常数据。对于判断的结果，我们用一个评价体系来评测判断结果的好坏。入侵模式挖掘系统结合了数据挖掘技术与入侵检测技术，旨在通过发现关联规则而对网络数据来进行判别。因此，根据以上分析，入侵模式挖掘系统的总体大致设计图如图1.1所示。
■
图1.1 入侵模式挖掘系统总体设计图
图1.1中方框内为数据或文件如原始网络日志数据、测试结果文件等，初步设计有三个大的子系统，分别是模式挖掘系统、测试系统、评价系统。箭头代表数据的流向或者结果的输出，椭圆框内为入侵模式挖掘系统的初步设计的子系统。
二、系统的设计算法分析
（一）Apriori算法
本系统采用关联分析方法中的Apriori算法作为核心算法。目前，该算法是挖掘布尔关联规则频繁项集算法中最有影响力的一种，基于两阶段频集思想的递推算法是其核心。在此，最小支持度小于所有支持度的项集称为频繁项集，简称频集。[1]在分类上该关联规则属于单层、单维和布尔关联规则，该关联规则为了生成所有频集，采用了递推的方法。
算法思路：第一步，找出所有出现的频繁性至少和预定义的最小支持度一样的频集。第二步，由频集产生必须满足最小可信度和最小支持度的强关联规则。第三步，使用第一步找到的频集产生只包含集合项的所有规则，其中每一条定义为中规则的右部只有一项的规则。第四步，大于用户给定的最小可信度的规则被留下来生成我们需要的规则。
程序算法如下：
（1）L1 = find_frequent_1_itemset（D）；
（2）for（k = 2； Lk-1≠φ； k++）{
（3） Ck = apriori_gen（Lk-1）；
（4） for each t ∈ D{
（5） Ck = subset（Ck，t）；
（6） For each c ∈ Ct c.count++； }
（7）Lk = {c∈Ck| c.count > min_sup} }
（8）retrurn L = ∪Lk
该算法中首先产生频繁1项集L1，其次产生频繁2项集L2，然后直到有一个频繁r值使得对应项集Lr为空，此时算法终止。Ck中的项集是用来产生频集的候选项集，最终的频集Lk一定是集合Ck的一个子集。在第k次循环中，算法先产生候选项k项集的集合Ck，Ck中的每一个项集属于项集Lk-1的频集来产生的下一个连接集合。Ck中的每个元素都需要在数据库中进行验证，然后才能决定该项是否能够加入频集Lk中。
Apriori算法的两个严重不足会导致挖掘的效率非常低。一个方面，该算法在每进行一次迭代的时候扫描一次数据库，多次扫描数据库带来巨大I/O开销。另一个方面，该算法在迭代过程中需要在内存中产生、处理和保存数量巨大的候选频集，这也导致算法在深度和广度上的适应性很差。
（二）基于划分改进的Apriori算法
为了提高Apriori算法的效率，需要对Apriori算法进行改进。本系统引入了一种基于划分改进的Apriori算法，该算法只需要扫描数据库两次。第一次扫描中，将产生一组潜在的频集，这组项集是最后需要确定的频集的超集，它也可能包含错误的选择，但绝对不可能漏掉正确的选择。第二次扫描中，对这些潜在的频集进一步计算它在整个数据库中的实际支持度，可以最后确定所求得的真正的频集。
算法思路：第一步，将整个数据库尽可能划分成N个子块。第二步，针对每一个子块单独产生一组潜在的频集。第三步，将上一步所有潜在的频集合并为一个全局的候选频集。第四步，在整个数据库中，计算每个候选频集的实际支持度，从而确定最后有用的频集。
程序算法如下：
（1） P=partion_database（D）
（2）n=number of partitions
（3）for i=1 to n begin
（4）read_in_partition（PiP）
（5）LPi=gen_large_itemset（Pi）
（6）end
（7）for（i=2；LPi=φ，，J=1，2，…，n； i++）do
（8）CGi=ULPi
（9）forall candidates c∈CG do begin
（10）c.count++；
（11）Lk={c∈Ck|c.count≥min_sup}
（12）end （13）answer=UkLk；
（14）Produce gen_large_itemset（Pi，min_sup）
（15）L1={Pi}；
（16）for（k=2；Lk-1≠？覫；k++）do begin
（17）Ck=apriori_gen（Lk-1，min_sup）；
（18）forall transactions∈tPi do begin
（19）Ct=subset（Ck，t）；
（20）forall candidations∈cCt do
（21）c.count++；
（22）end
（23）Lk={c= Ck|c.count≥min_sup*n}
（24）end
（25）return Lk
（26）Produce apriori_gen（Lk-1，min_sup）
（27）forall items l1∈Lk-1
（28）forall items l2∈Lk-1
（29）if（（l1[1]=l2[2]（∧…∧ l1[k-1]= l2[k-2]）∧（ l1[k-1] ？刍l2[k-2]））do begin
（30）c=l1？茌l2；
（31）if has_infrequent_itemset（c， Lk-1）
（32）delete c；
（33）else Ck=Ck∨{c}
（34）end；
（35）return Ck
（36）Produce has_infrequent_subset（c，Lk-1）
（37）forall （k-1）subset s of c
（38）if s？埸Lk-1 return true；
（39）else return false
通过对基于划分改进的Apriori算法解析，我们发现该算法有三大优点。
优点1、两种算法扫描次数相比，基于划分改进的Apriori算法扫描数据库次数少。
优点2、基于划分改进的Apriori算法第一次扫描数据库产生的一组潜在的既有需要的也有不需要的频集，它为第二次扫描数据库进行计算及确认最后挖掘出有效频集做了铺垫。
优点3、基于划分改进的Apriori算法进行数据挖掘是将数据库划分成N个子块，先对每个子块单独产生一组频集，然后再合并所有独立产生的各组频集构成一个全局的候选频集。在数据量逐渐增多的情况下，这种“以大划小，以小并行”的思想，可以使数据挖掘的效率大大提高。
综上，通过分析比较可以看出，基于划分改进的Apriori算法跟Apriori算法相比，确实有了相当不错的改进，数据挖掘的效率大大提高了。基于划分改进的Apriori算法为入侵模式挖掘系统的设计提供了重要的理论支持。
[ 参 考 文 献 ]
[1] 刘明辉，周萍.基于Web挖掘的网站优化系统的研究[J].长春大学学报（自然科学版），2009，19（3）.
[2] aul Ammann，Duminda wijesekera and Saket kaushie. Scalable，graph-based network vulnerability analysis[A]. CCS’02[C]， Washington， DC， USA，2002.18-22.
[责任编辑：戴祯杰]