资源描述
,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,数据挖掘：概念和技术,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,数据挖掘：概念和技术,*,Apriori,算法是挖掘布尔关联规则频繁项集的算法,Apriori,算法利用频繁项集性质的先验知识（,prior knowledge,），通过逐层搜索的迭代方法，即将,k-,项集用于探察,(k+1)-,项集，来穷尽数据集中的所有频繁项集。,先找到频繁,1-,项集集合,L,1,然后用,L,1,找到频繁,2-,项集集合,L,2,，接着用,L,2,找,L,3,，直到找不到频繁,k-,项集，找每个,L,k,需要一次数据库扫描。,APRIORI,算法,Apriori算法是挖掘布尔关联规则频繁项集的算法APRIO,Apriori,算法利用的是,Apriori,性质：频繁项集的所有非空子集也必须是频繁的。,模式不可能比,A,更频繁的出现,Apriori,算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。,Apriori,性质通过减少搜索空间，来提高频繁项集逐层产生的效率,Apriori算法利用的是Apriori性质：频繁项集的所有,算法应用,经典的关联规则数据挖掘算法,Apriori,算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。,Apriori,算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。,算法应用经典的关联规则数据挖掘算法Apriori 算法广泛,Apriori,算法应用于网络安全领域，比如时候入侵检测技术中。早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些,审计跟踪,的目的多是为了,性能测试,或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的,Apriori,算法削弱了,Apriori,算法的挖掘结果规则，是网络,入侵检测系统,可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。,Apriori,算法应用于高校管理中。随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的,Apriori,算法应用到贫困助学体系中，并且针对经典,Apriori,挖掘算法存在的不足进行改进，先将事务数据库映射为一个,布尔,矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求,与,运算，寻找频繁项集。实验结果表明，改进后的,Apriori,算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。,Apriori算法应用于网络安全领域，比如时候入侵检测技术中,算法思想,该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第,1,步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了,递归,的方法。,算法思想该算法的基本思想是：首先找出所有的频集，这些项集出现,算法实现,Apriori,算法利用频繁项集性质的先验知识（,prior knowledge,），通过逐层搜索的迭代方法，即将,k-,项集用于探察,(k+1)-,项集，来穷尽数据集中的所有频繁项集。,先找到频繁,1-,项集集合,L1,然后用,L1,找到频繁,2-,项集集合,L2,，接着用,L2,找,L3,，直到找不到频繁,k-,项集，找每个,Lk,需要一次数据库扫描。,算法实现Apriori算法利用频繁项集性质的先验知识（pri,Apriori,算法由,连接,和,剪枝,两个步骤组成。,连接,：为了找,L,k,，通过,L,k-1,与自己连接产生候选,k-,项集的集合，该候选,k,项集记为,C,k,。,L,k-1,中的两个元素,L1,和,L2,可以执行连接操作 的条件是,C,k,是,L,k,的超集，即它的成员可能不是频繁的，但是所有频繁的,k-,项集都在,C,k,中（为什么？）。因此可以通过扫描数据库，通过计算每个,k-,项集的支持度来得到,L,k,。,为了减少计算量，可以使用,Apriori,性质，即如果一个,k-,项集的,(k-1)-,子集不在,L,k-1,中，则该候选不可能是频繁的，可以直接从,C,k,删除。,Apriori算法由连接和剪枝两个步骤组成。,算法：,Apriori,。使用逐层迭代方法基于候选产生找出频繁项集。,输入：,D:,实物数据库；,M,in_sup:,最小支持度计数阈值。,输出：,L,：,D,中的频繁项集。,方法：,L,1,=find_frequent_1-itemsets(D);,f,or(k=2;L,k-1,!=,；,k+),C,k,=apriori_gen(L,k-1,);,For each,事务,t,D/,扫描,D,用于计数,Ct=subset(Ck,t);/,得到,t,的子集，它们是候选,for each,候选,cC;,C,.count+;,L,k,=cC|c.count=min_stp,return L=U,k,L,k,；,Apriori,伪代码,算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项,P,rocedure apriori_gen(L,k-1,:frequent(k-1)-itemsets),for each,项集,l,1,L,k-1,for each,项集,l,2,L,k-1,I,f(,l,1,1=l,2,1),(,l,1,2=l,2,2),(,l,1,k-2=l,2,k-2),(,l,1,k-1=l,2,k-1)then,c=l,1,l,2,/,连接步：产生候选,if has_infrequent_subset(c,L,k-1,)then,d,elete c;/,剪枝部；删除非频繁的候选,e,lse add c to C,k,；,r,eturn C,k,；,p,rocedure has_infrequent_subset(c:candidate k-itemset;,L,k-1,：,frequent(k-1)-itemset)/,使用先验知识,f,or each(k-1)-subset s of c,I,f s L,k-1,then,r,eturn TRUE;,r,eturn FALSE;,Procedure apriori_gen(Lk-1:fre,Database TDB,1,st,scan,C,1,L,1,L,2,C,2,C,2,2,nd,scan,C,3,L,3,3,rd,scan,Tid,Items,10,A,C,D,20,B,C,E,30,A,B,C,E,40,B,E,Itemset,sup,A,2,B,3,C,3,D,1,E,3,Itemset,sup,A,2,B,3,C,3,E,3,Itemset,A,B,A,C,A,E,B,C,B,E,C,E,Itemset,sup,A,B,1,A,C,2,A,E,1,B,C,2,B,E,3,C,E,2,Itemset,sup,A,C,2,B,C,2,B,E,3,C,E,2,Itemset,A,B,C,B,C,E,Itemset,sup,B,C,E,2,Database TDB1st scanC1L1L2C2C2,1.,连接：,C3=L2 L2=A,C,B,C,B,EC,E A,C,B,C,B,EC,E=A,B,C,A,C,E,B,C,E,2,使用,Apriori,性质剪枝：频繁项集的所有子集必须是频繁的，对候选项,C,3,，我们可以删除其子集为非频繁的选项：,A,B,C,的,2,项子集是,A,B,A,C,B,C,，其中,A,B,不是,L2,的元素，所以删除这个选项；,A,C,E,的,2,项子集是,A,C,A,E,C,E,，其中,A,E,不是,L2,的元素，所以删除这个选项；,B,C,E,的,2,项子集是,B,C,B,E,C,E,，它的所有,2,项子集都是,L2,的元素，因此保留这个选项。,3,这样，剪枝后得到,C3=B,C,E,1.连接：,从以上的算法执行过程可以看到,Apriori,算法的缺点,:,第一,:,在每一步产生侯选项目集时循环产生的组合过多，,没有排除不应该参与组合的元素,;,第二,:,每次计算项集的支持度时，都对数据库,D,中的全部,记录进行了一遍扫描比较，如果是一个大型的数据,库的话，这种扫描比较会大大增加计算机系统的,I/O,开销。而这种代价是随着数据库的记录的增加,呈现出几何级数的增加。,因此人们开始寻求一种能减少这种系统,1/O,开销的更为快捷的算法。,Apriori,算法的缺点,从以上的算法执行过程可以看到Apriori算法的缺点:Apr,改进,Apriori,算法的方法,方法,1,：基于,hash,表的项集计数,将每个项集通过相应的,hash,函数映射到,hash,表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。,方法,2,：事务压缩（压缩进一步迭代的事务数）,不包含任何,k-,项集的事务不可能包含任何,(k+1)-,项集，这种事务在下一步的计算中可以加上标记或删除。,改进Apriori算法的方法方法1：基于hash表的项集计数,方法,3,：划分,挖掘频繁项集只需要两次数据扫描,D,中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。,第一次扫描：将数据划分为多个部分并找到局部频繁项集,第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集。,方法,4,：选样（在给定数据的一个子集挖掘）,基本思想：选择原始数据的一个样本，在这个样本上用,Apriori,算法挖掘频繁模式,通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式,可以通过一次全局扫描来验证从样本中发现的模式,可以通过第二此全局扫描来找到遗漏的模式,方法,5,：动态项集计数,在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算,方法3：划分,方法,4,：选样（在给定数据的一个子集挖掘）,基本思想：选择原始数据的一个样本，在这个样本上用,Apriori,算法挖掘频繁模式,通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式,可以通过一次全局扫描来验证从样本中发现的模式,可以通过第二此全局扫描来找到遗漏的模式,方法,5,：动态项集计数,在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算,方法4：选样（在给定数据的一个子集挖掘）,一种,Apriori,的改进算法实现,在,Apriori,算法中，寻找最大项目集的基本思路是,:,第一步,:,简单统
展开阅读全文