Apriori算法分析和改进,基于Markov异常检测模型.doc

Apriori算法分析和改进一 Apriori算法介绍1.1 Apriori 算法思想 Apriori 算法的基本思想是:首先找出事务中所有的频集,这些频集出现的频繁性需要大于或等于预先设定的最小支持度。随后由频集产生强关联规则, 这些规则必须大于最小支持度和最小可信度。为了生成所有频集,使用了递推的方法。1.2 Apriori 算法步骤1.制定最小支持度及最小置信度。2.对数据集所有事务进行扫描,对每个项出现的次数计数,删除那些出现计数值小于阈值的项集,这样就得到 L1频繁项集;3.利用频繁 1-项集合的结合,产生候选 2-项集合 C2(Candidate2-itemset)。4.对 C2中每个候选项集的支持计数,确定频繁项集 2-项集的集合 L2,并利用这些频繁 2-项集合 L2的结合,产生候选 3-项集合 C3。5.重复扫描数据库产生更高层次的频繁项集合,再结合产生下一级候选项集,直到穷尽数据集中的所有频繁项集。Apriori 算法描述如下:(1) C1=candidate1-itemsets;(2) L1=cC1|c.countminsupport;(3) For(k=2,Lk-1,k+)/直到不能再生成最大项目集为止(4) Ck=sc_candidate(Lk-1);/生成含 k 个元素的侯选项目集(5) for all transactions tD/办理处理(6) Ct=count_support (Ck,t);/包含在事务 t 中的侯选项目集(7) for all candidates cCt(8) c.count=c.count+1;(9)next(10) Lk=cCk|c.countminsupport;(11) next(12) resultset=resultsetLk其中,D 表示数据库,minsupport 表示给定的最小支持度,resultset 表示所有最大项目集。1.3 Apriori 算法的不足 在Apriori 算法中候选项集是逐层产生, 而产生此层的频集, 必须要扫描整个数据库一次, 然后再结合频集产生下一层级的候选项集合, 直到频集无法结合产生候选项集。Apriori 算法一定要等到扫描完整个数据库后才做结合, 因为在扫描的过程中, 有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度, 因此在扫描这些若干个区段后, 便可以找出频集, 并直接结合产生下一个层级的候选物项集。基于上述原因,Apriori算法可能会存在下述问题。(1) 所挖掘的规则存在大量冗余。(2) 因计算项过多而造成执行能缓慢, 主要的原因在于频繁项集合产生过多的候选项集, 尤其是候选22项集的情况最为严重。二 Apriori 算法的典型改进及其比较2.1 FIS-ES 算法 FIS-ES 算法对传统集合操作进行了扩展,提出了基于扩展集合操作的最大频繁项集生成法 FIS-ES,算法通过从数据库中检测是否有符合最小支持度要求的频繁项, 并删除该频繁项的真子集,循环操作直到读完数据库中的记录为止。该算法通过只保留最大的频繁项集,从而压缩了搜索空间、提高了数据挖掘的效率。2.2 基于 PCL 模型的频繁项集求解算法 从近几年频繁项集挖掘算法的研究趋势来看, 为了提高算法的效率,提出了一系列的混合搜索策略和高效剪枝策略。在基于 Apriori 算法性质基础上,胡学钢等在基于剪枝概念格模型的频繁项集表示及挖掘一文提出了基于 PCL 模型的频繁项集求解算法,改善了频集挖掘算法的时空性能。2.3 FP-DFS 算法 在文献中作者以 FP-tree 为基本数据结构, 首先通过新的搜索策略和剪枝策略, 将事务数据库 D 压缩为内存中的 FP-tree,然后按照相反次序逐个处理项集中的项目,每次迭代得到以某个项目开头的所有频繁项集。从而提高算法的搜索效率,减少了对内存的占用,算法的空间复杂性低。2.4 使用概率的方法求候选频繁项集的 Apriori 改进算法 针对 Apriori 算法存在的可能产生大量的候选集的缺点,该算法通过使用概率的方法估算任意数据项集同时出现的概率来求候选频繁项集。首先创建数组来记录各个属性项独立出现的概率,设定最小概率,得到 m 个多个频繁 1 项集,由 m 个频繁1 项集的独立出现概率, 估算出任意两个属性项同时出现的概率,得到候选频繁 2 项集,通过迭代,由候选频繁数据项集的支持度求出频繁项集。2.5 基于事务地址索引表来约简事务的 Apriori 优化算法 针对 Apriori 算法需要重复地扫描数据库的缺陷,基于事务地址索引表来约简事务的 Apriori 优化算法提出使用一个有效约简事务数据库中事务的策略对算法进行优化。该算法中给出了一个有效约简事务的方法, 就是通过创建事务地址索引表缩小了对事务数据库记录的搜索范围,实现了分区域的快速定位,从而减少解空间,优化了候选集的计数过程,一定程度上提高了Apriori 算法的执行效率, 但是该算法还是需要对事务数据库多次扫描。2.6 适用于数字资源访问日志数据库的关联规则挖掘改进算法 文献提出了一种适用于数字资源访问日志数据库的关联规则挖掘改进算法,通过事务压缩和项目压缩相结合,生成候选项目集的同时, 剔除事务数据库中不支持频繁项集的事务及事务中的项目, 在每条事务压缩后通过联接产生候选项目集及计算支持度,候选项目集采用关键字识别,省去了 Apriori 算法中的剪枝和字符串模式匹配步骤,提高了产生频繁模式集的速度。但是该算法存在应用范围较窄的缺陷。2.7 S_Apriori 算法 S_Apriori 算法在 Apriori 算法的基础上作了改进,采用新的数据结构, 使得只需要扫描一次数据库和连接时无须重复判断即可快速找到更高阶的频繁项目集,算法的效率也得到了提高。 总之,国内外众多学者从不同的角度提出了各种优化算法,尽管这些算法各具优点且挖掘的性能和效率均明显高于传统的算法,但总的来说,各自还是有些缺点,算法仍较复杂。 FIS-ES 算法与 Apriori 算法的不同之处就在于 FIS-ES 只需扫描一次数据库,而 Apriori 算法的每一次频繁项集的产生都需要扫描一次数据库。所以该算法比 Apriori 算法具有更快的挖掘速度、更少的空间占用等优点,但也存在一些不足:算法的时间和空间占用随项目长度的增加呈指数增长, 这种情况在最小支持度较大时表现得尤为突出;事务数据量比较大时,对内存的要求会比较高。基于 PCL 模型的频繁项集求解算法应用过程中构造剪枝概念格需要花费一定时间, 另外基于概念格及其分布式关联规则挖掘算法及其在实际应用需要进行大量的研究,尤其是分布式概念的关联规则挖掘算法等都需要进一步深入研究解决。 通过使用概率的方法估算任意数据项集同时出现的概率来求候选频繁项集的方法,该算法与 Apriori 算法比较产生的候选项集大小和扫描数据库次数都有了改进, 将关联规则挖掘的运行速度提高了一个数量级,这种算法非常适合挖掘数据库大、长模式的关联规则, 但是算法中参数 a、b 的设定需要额外的时间,同时算法采用概率估算求候选频繁项集,如果参数设定不合适, 有可能会遗漏一些用户感兴趣的关联规则。FP-DFS 算法、基于事务地址索引表来约简事务的 Apriori 优化算法等其他算法与 Apriori 算法比较提高了搜索效率,但也存在应用范围较窄等问题。基于Markov异常检测模型一 引言 入侵检测系统(IDS，IntrusionDetectionSystem)作为对常规安全措施(如用户认证、信息加密)和安全产品(如防火墙)的补充，已被越来越多的人所认识。入侵检测系统从检测技术上可分为特征检测、统计分析和专家系统三种技术。Markov过程模型作为一种统计分析技术在语音识别、信息抽取和一些分类领域得到成功应用，但将其应用于网络安全中的异常检测，研究得并不多。异常检测是事先定义一组系统”正常”情况的数值，如CPU利用率、内存利用率、文件校验和等(这些数据可以人为定义，也可以通过观察系统利用统计的办法得出)，然后将系统运行时的数值与定义的”正常”情况比较，得出是否有被攻击的迹象。异常检测的困难在于如何定义所谓的“正常”情况，它需要对系统安全有足够的背景知识。如何在领域知识匮乏的情况下，识别系统的异常行为，对于异常检测的实际应用有着十分重要的意义。下面介绍从单步、多步Markov链和基于多步Markov链的序列预测三个方面，较为全面地研究了Markov链模型在异常检测上的应用。二 Markov链模型应用于异常检测 Markov链是Markov随机过程的特殊情况,它是状态和时间参数都离散的Markov过程.随机序列Xu,在任一时刻t,可以处在状态1,T,且它在m+k时刻所处的状态的概率,只与它在m时刻的状态有关,而与它在m时刻以前所处状态无关,则称Xu为Markov链.实际中,Markov链的每一状态对应于一个可以观测到的物理事件,所有状态之间的转移用状态转移概率矩阵表示.状态转移概率矩阵和状态的初始概率分布,二者结合可完整描Markov链. 大部分攻击过程都包含了一系列前后相关的行为,其特征与正常系统过程有着明显的差别,Markov链模型在异常检测中的应用就是利用这种差别,使用Markov链建立正常系统行为的统计模型,并以此来检测系统行为的异常.状态对应于每种类型的系统事件,用状态转移矩阵来表示状态间的变化,当一个事件发生时,如果状态转移矩阵确认该转移的概率较小则可能是异常事件.2.1建立Markov链模型 首先,通过统计方法计算一步转移概率矩阵P,元素Pij表示系统在t时刻处于状态i,在t+1时刻处于状态j的概率,计算公式为: Pij= Nij/Ni (1)其中,Nij表示系统调用i和系统调用j相邻出现的次数;Ni表示系统调用i出现的次数.此外,设系统的初始状态概率矢量= (1,n),其中, i= P(i=i) =NiN,1in (2)其中,Ni表示系统调用i出现的次数;N表示总的系统调用数.显然有:0i1并且ii=1另外,单步Markov链模型存在两条基本假设: 1)t+1时刻系统状态的概率分布只与t时刻的状态有关,与t时刻以前的状态无关.2)从t时刻到t+1时刻的转移概率与t的值无关.这两条假设对系统调用序列并不严格成立,要考虑某一状态的前几个状态对该状态的影响.例如,在序列(S1,S2,St-1,St)中,不仅St-1对St有影响,此前的若干系统调用也可能影响到St.为此要计算多步的状态转移概率.由Markov多步转移概率的性质P(t+s)=P(t)P(s),可以使用一步转移概率矩阵来计算得到多步的转移概率矩阵.2.2Markov链分析检测数据2.2.1滑动窗口序列首先利用滑动窗口对长的序列进行分割,形成小的序列集合.窗口分割一般有时间窗分割和数量窗分割两种.时间窗分割是用一定长度的时间间隔(譬如2 s)划分序列.本方法是以一定长度的系统调用序列为基本单位,使用数量窗来分割序列.例如,对系统调用序列(S1,S2,St,St+1,St+s),使用长为t的滑动窗口划分,可得s+1个长为t的序列集合:(S1,S2,St);(S2,S3,St+1)(Ss+1,Ss+2,St+s);2.2.2分析方法在建立了正常系统调用行为的Markov链模型之后,利用该模型对待检测的序列进行分析,分析的方法有以下几种:(1) 单步Markov链计算序列支持度. 对长度为t的系统调用序列(S1,S2,St),计算正常系统模式对其支持度:P(S1,S2,St)=S1PS1S2PSt-1St.(3)若此支持度小于某一阈值,则此序列为异常序列,否则为正常序列,并统计所有异常序列所占的比率.(2)多步Markov方法.由于单步Markov链存在的前提假设在实际应用中不能严格成立,为此采用多步的Markov链分析方法.对长度为t的系统调用序列(S1,S2,St),计算在正常系统模式下下一系统调用St+1出现的概率P(St+1S1,St).这里取序列(S1,S2,St)中所有时刻的状态Si(1it)到St+1的转移概率的加权平均值,计算公式为: 其中:PSiSt+1是i时刻系统调用为Si,t+1时刻系统调用为St+1的概率,由t+1-i步状态转移概率矩阵得到.Wi是状态Si到St+1的转移概率权值,体现的是与St+1距离为t+1-i的Si对St+1的影响,距离越小影响越大,所以随着i增加,权值