资源描述：
《Apriori算法分析和改进,基于Markov异常检测模型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、Apriori算法分析和改进一Apriori算法介绍1.1Apriori算法思想Apriori算法的基本思想是:首先找出事务中所有的频集,这些频集出现的频繁性需要大于或等于预先设定的最小支持度。随后由频集产生强关联规则,这些规则必须大于最小支持度和最小可信度。为了生成所有频集,使用了递推的方法。1.2Apriori算法步骤1.制定最小支持度及最小置信度。2.对数据集所有事务进行扫描,对每个项出现的次数计数,删除那些出现计数值小于阈值的项集,这样就得到L1频繁项集;3.利用频繁1-项集合的结合,产生候选2-项集合C2(Candi－da
2、te2-itemset)。4.对C2中每个候选项集的支持计数,确定频繁项集2-项集的集合L2,并利用这些频繁2-项集合L2的结合,产生候选3-项集合C3。5.重复扫描数据库产生更高层次的频繁项集合,再结合产生下一级候选项集,直到穷尽数据集中的所有频繁项集。Apriori算法描述如下:(1)C1={candidate1-itemsets};(2)L1={c∈C1
3、c.count≥minsupport};(3)For(k=2,Lk-1≠Φ,k++)//直到不能再生成最大项目集为止(4)Ck=sc_candidate(Lk-1);//生成
4、含k个元素的侯选项目集(5)foralltransactionst∈D//办理处理(6)Ct=count_support(Ck,t);//包含在事务t中的侯选项目集(7)forallcandidatesc∈Ct(8)c.count=c.count+1;(9)next(10)Lk={c∈Ck
5、c.count≥minsupport};(11)next(12)resultset=resultset∪Lk其中,D表示数据库,minsupport表示给定的最小支持度,re－sultset表示所有最大项目集。1.3Apriori算法的不足在Ap
6、riori算法中候选项集是逐层产生,而产生此层的频集,必须要扫描整个数据库一次,然后再结合频集产生下一层级的候选项集合,直到频集无法结合产生候选项集。Apriori算法一定要等到扫描完整个数据库后才做结合,因为在扫描的过程中,有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度,因此在扫描这些若干个区段后,便可以找出频集,并直接结合产生下一个层级的候选物项集。基于上述原因,Apriori算法可能会存在下述问题。(1)所挖掘的规则存在大量冗余。(2)因计算项过多而造成执行能缓慢,主要的原因在于频繁项集合产生过多的候选项集
7、,尤其是候选22项集的情况最为严重。二Apriori算法的典型改进及其比较2.1FIS-ES算法FIS-ES算法对传统集合操作进行了扩展,提出了基于扩展集合操作的最大频繁项集生成法FIS-ES,算法通过从数据库中检测是否有符合最小支持度要求的频繁项,并删除该频繁项的真子集,循环操作直到读完数据库中的记录为止。该算法通过只保留最大的频繁项集,从而压缩了搜索空间、提高了数据挖掘的效率。2.2基于PCL模型的频繁项集求解算法从近几年频繁项集挖掘算法的研究趋势来看,为了提高算法的效率,提出了一系列的混合搜索策略和高效剪枝策略。在基于Apri
8、ori算法性质基础上,胡学钢等在《基于剪枝概念格模型的频繁项集表示及挖掘》一文提出了基于PCL模型的频繁项集求解算法,改善了频集挖掘算法的时空性能。2.3FP-DFS算法在文献中作者以FP-tree为基本数据结构,首先通过新的搜索策略和剪枝策略,将事务数据库D压缩为内存中的FP-tree,然后按照相反次序逐个处理项集中的项目,每次迭代得到以某个项目开头的所有频繁项集。从而提高算法的搜索效率,减少了对内存的占用,算法的空间复杂性低。2.4使用概率的方法求候选频繁项集的Apriori改进算法针对Apriori算法存在的可能产生大量的候选
9、集的缺点,该算法通过使用概率的方法估算任意数据项集同时出现的概率来求候选频繁项集。首先创建数组来记录各个属性项独立出现的概率,设定最小概率,得到m个多个频繁1项集,由m个频繁1项集的独立出现概率,估算出任意两个属性项同时出现的概率,得到候选频繁2项集,通过迭代,由候选频繁数据项集的支持度求出频繁项集。2.5基于事务地址索引表来约简事务的Apriori优化算法针对Apriori算法需要重复地扫描数据库的缺陷,基于事务地址索引表来约简事务的Apriori优化算法提出使用一个有效约简事务数据库中事务的策略对算法进行优化。该算法中给出了一个
10、有效约简事务的方法,就是通过创建事务地址索引表缩小了对事务数据库记录的搜索范围,实现了分区域的快速定位,从而减少解空间,优化了候选集的计数过程,一定程度上提高了Apriori算法的执行效率,但是该算法还是需要对事务数据库多次扫描。2.
