《大数据经典算法Apriori讲解.》由会员分享，可在线阅读，更多相关《大数据经典算法Apriori讲解.（20页珍藏版）》请在金锄头文库上搜索。
1、nApriori算法是挖掘布尔关联规则频繁项集的算法 nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k -项集用于探察(k+1)-项集，来穷尽数据集中的 所有频繁项集。 n先找到频繁1-项集集合L1,然后用L1找到频繁2- 项集集合L2，接着用L2找L3，直到找不到频繁k -项集，找每个Lk需要一次数据库扫描。 APRIORI算法 nApriori算法利用的是Apriori性质：频繁项集的所 有非空子集也必须是频繁的。 n模式不可能比A更频繁的出现 nApriori算法是反单调的，即一个集合如果不能 通过测试，则该集合的所有超集也
2、不能通过相 同的测试。 nApriori性质通过减少搜索空间，来提高频繁项 集逐层产生的效率 算法应用 n经典的关联规则数据挖掘算法Apriori 算法广泛应用于各 种领域，通过对数据的关联性进行了分析和挖掘，挖掘 出的这些信息在决策制定过程中具有重要的参考价值。 nApriori算法广泛应用于商业中，应用于消费市场价格分 析中，它能够很快的求出各种产品之间的价格关系和它 们之间的影响。通过数据挖掘，市场商人可以瞄准目标 客户，采用个人股票行市、最新信息、特殊的市场推广 活动或其他一些特殊的信息手段，从而极大地减少广告 预算和增加收入。百货商场、超市和一些老字型大小的 零售店也在进行数据挖掘，
3、以便猜测这些年来顾客的消 费习惯。 nApriori算法应用于网络安全领域，比如时候入侵检测技术中。早期中大 型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的 多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。 它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作 用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测 系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高 了基于关联规则的入侵检测系统的检测性。 nApriori算法应用于高校管理中。随着高校贫困生人数的不断增加，学校 管理部门资助工作难度也越加增大。针对这一现象，提
4、出一种基于数 据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系 中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据 库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进 行存储，再利用向量求“与“运算，寻找频繁项集。实验结果表明，改进 后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有 效地辅助学校管理部门有针对性的开展贫困助学工作。 算法思想 n该算法的基本思想是：首先找出所有的频集，这些 项集出现的频繁性至少和预定义的最小支持度一样 。然后由频集产生强关联规则，这些规则必须满足 最小支持度和最小可信度。然后使用第1步找到
5、的 频集产生期望的规则，产生只包含集合的项的所有 规则，其中每一条规则的右部只有一项，这里采用 的是中规则的定义。一旦这些规则被生成，那么只 有那些大于用户给定的最小可信度的规则才被留下 来。为了生成所有频集，使用了递归的方法。 算法实现 Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项 集用于探察(k+1)-项集，来穷尽数据集中的所有频 繁项集。 先找到频繁1-项集集合L1,然后用L1找到频繁2-项 集集合L2，接着用L2找L3，直到找不到频繁k-项 集，找每个Lk需要一次数据库扫描。 nApriori算法由连接和剪枝两个步骤
6、组成。 n连接：为了找Lk，通过Lk-1与自己连接产生候选k-项 集的集合，该候选k项集记为Ck。 nLk-1中的两个元素L1和L2可以执行连接操作 的条件是 nCk是Lk的超集，即它的成员可能不是频繁的，但是 所有频繁的k-项集都在Ck中（为什么？）。因此可 以通过扫描数据库，通过计算每个k-项集的支持度 来得到Lk 。 n为了减少计算量，可以使用Apriori性质，即如果 一个k-项集的(k-1)-子集不在Lk-1中，则该候选不 可能是频繁的，可以直接从Ck删除。 n算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项集。 n输入： nD:实物数据库； nMin_sup:最小支持度
7、计数阈值。 n输出：L：D中的频繁项集。 n方法： nL1=find_frequent_1-itemsets(D); nfor(k=2;Lk-1 !=；k+) nCk=apriori_gen(Lk-1); nFor each 事务 tD/扫描D用于计数 nCt=subset(Ck,t);/得到t的子集，它们是候选 nfor each候选cC; nC.count+; n nLk=cC|c.count=min_stp n nreturn L=UkLk； Apriori伪代码 nProcedure apriori_gen(Lk-1:frequent(k-1)-itemsets) nfor each项
8、集l1Lk-1 nfor each项集l2Lk-1 nIf (l11=l21) (l12=l22) (l1k-2=l2k-2) (l1k-1=l2k- 1) then nc=l1l2/连接步：产生候选 nif has_infrequent_subset(c,Lk-1)then ndelete c;/剪枝部；删除非频繁的候选 nelse add c to Ck； n nreturn Ck； nprocedure has_infrequent_subset (c:candidate k-itemset; nLk-1：frequent (k-1)-itemset)/使用先验知识 nfor each(
9、k-1)-subset s of c nIf s Lk-1then nreturn TRUE; nreturn FALSE; Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3L3 3rd scan TidItems 10A, C, D 20B, C, E 30A, B, C, E 40B, E Itemsetsup A2 B3 C3 D1 E3 Itemsetsup A2 B3 C3 E3 Itemset A, B A, C A, E B, C B, E C, E Itemsetsup A, B1 A, C2 A, E1 B, C2 B, E3
10、C, E2 Itemsetsup A, C2 B, C2 B, E3 C, E2 Itemset A,B,C B, C, E Itemsetsup B, C, E2 n1 . 连接： nC3=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 n2使用Apriori性质剪枝：频繁项集的所有子集必须是频 繁的，对候选项C3，我们可以删除其子集为非频繁的选 项： nA,B,C的2项子集是A,B,A,C,B,C，其中A,B不 是L2的元素，所以删除这个选项； nA,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以
11、删除这个选项； nB,C,E的2项子集是B,C,B,E,C,E，它的所有2 项子集都是L2的元素，因此保留这个选项。 n3这样，剪枝后得到C3=B,C,E 从以上的算法执行过程可以看到Apriori算法的缺点: 第一:在每一步产生侯选项目集时循环产生的组合过多， 没有排除不应该参与组合的元素; 第二:每次计算项集的支持度时，都对数据库D中的全部 记录进行了一遍扫描比较，如果是一个大型的数据 库的话，这种扫描比较会大大增加计算机系统的 I/O开销。而这种代价是随着数据库的记录的增加 呈现出几何级数的增加。 因此人们开始寻求一种能减少这种系统1/O开销的更 为快捷的算法。 Apriori算法的缺点
12、 改进Apriori算法的方法 n方法1：基于hash表的项集计数 n将每个项集通过相应的hash函数映射到hash表中的 不同的桶中，这样可以通过将桶中的项集技术跟最 小支持计数相比较先淘汰一部分项集。 n方法2：事务压缩（压缩进一步迭代的事务数） n不包含任何k-项集的事务不可能包含任何(k+1)-项集 ，这种事务在下一步的计算中可以加上标记或删除 。 n方法3：划分 n挖掘频繁项集只需要两次数据扫描 nD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。 n第一次扫描：将数据划分为多个部分并找到局部频繁项集 n第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁 项集。 n方
13、法4：选样（在给定数据的一个子集挖掘） n基本思想：选择原始数据的一个样本，在这个样本上用Apriori 算法挖掘频繁模式 n通过牺牲精确度来减少算法开销，为了提高效率，样本大小应 该以可以放在内存中为宜，可以适当降低最小支持度来减少遗 漏的频繁模式 n可以通过一次全局扫描来验证从样本中发现的模式 n可以通过第二此全局扫描来找到遗漏的模式 n方法5：动态项集计数 n在扫描的不同点添加候选项集，这样，如果一个候选项集已经 满足最少支持度，则在可以直接将它添加到频繁项集，而不必 在这次扫描的以后对比中继续计算 方法4：选样（在给定数据的一个子集挖掘） 基本思想：选择原始数据的一个样本，在这个样 本
14、上用Apriori算法挖掘频繁模式 通过牺牲精确度来减少算法开销，为了提高效率 ，样本大小应该以可以放在内存中为宜，可以适 当降低最小支持度来减少遗漏的频繁模式 可以通过一次全局扫描来验证从样本中发现 的模式 可以通过第二此全局扫描来找到遗漏的模式 方法5：动态项集计数 在扫描的不同点添加候选项集，这样，如果一个 候选项集已经满足最少支持度，则在可以直接将 它添加到频繁项集，而不必在这次扫描的以后对 比中继续计算 一种Apriori的改进算法实现 在Apriori算法中，寻找最大项目集的基本思路是: 第一步:简单统计所有含一个元素的项目出现的频率，并找 出那些大于或等于最小支持度的项目集，产生
15、一维频繁项 目集Lt。 第二步:循环处理直到未能再产生维数更高的频繁项目集。 循环过程是:在第k步中，根据k-1步生成的k-1维频繁 项目集来产生k维候选项目集，由于在产生k-1维频繁项目 集时，我们可以实现对该集中出现元素的个数进行计数处 理，因此对某元素而言，若它的计数个数不到k-1的话， 可以事先删除该元素，从而排除由该元素将引起的大规格 所有组合。 第三步：按Apriori算法再检验新的K 维频繁项目集的所有 k-1维项目集是否已经包含在已经求出的K-1维频繁项目集 。 若其中有一个没有包含，则也可删去该组合，这样得到 一个真正有用的K维频繁项目集选项目集。 第四步：得到了这个候选项目
16、集后，可以对数据库D的每 一个事务tid进行扫描，若该事务中至少含有候选项目集 CK中的一员，则保留该项事务，否则把该事物记录与数 据库末端没有作删除标记的事务记录对换，并对移到数 据库末端的事务记录作删除标一记，整个数据库扫描完 毕后为新的事务数据库D 中。 一种Apriori的改进算法实现 算法的图例说明 算法的评价: 我们可以看到本算法的思路基本上与Apriori算法保 持一致，但是又有不同之处。 第一，改进的算法在考虑组合Ck前，对将参与组合 的元素进行计数处理，根据计数结果决定排除一些不符 合组合条件的元素，这就降低了组合的可能性，即降低 循环判断的次数。 第二，改进的算法对数据库进行了扫描后的重新生 成，虽然会在
