2022年Apriori算法的更新算法 .pdf

《2022年Apriori算法的更新算法 .pdf》由会员分享，可在线阅读，更多相关《2022年Apriori算法的更新算法 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 关联规则 Apriori 算法的更新算法邢茜 重庆理工大学计算机科学与工程学院摘要：在数据挖掘中，关联规则是一个重要的研究方向，Apriori算法是关联规则中提取的经典算法， 但是无论是在处理的数据量还是处理效率上都有许多局限性。在现阶段的研究中，主要是针对其算法在效率上的提高。本文讨论Apriori算法存在的不足以及改进的基本思想，以提高该算法的效率。关键字：数据挖掘；关联规则；频繁项集；非频繁项集；Apriori算法1 引言数据挖掘（ Data Mining ）是一门交叉学科，是从大量数据中获取有效的、新颖的、潜在有用的、 最终可理解的模式的非平凡过程。其中的事务数据库挖掘关联规则（

2、Association Rules）是数据挖掘领域中一个非常重要的研究课题。AGRAW AL1年提出了关联规则，而后又进一步提出了著名的Apriori算法2。其基本思想是重复扫描数据库， 根据一个频繁集的任意子集都是频繁集的原理，可以从长度为 -1 的频繁集迭代地产生长度为的候选集，再扫描数据库以验证其是否为频繁集。但当数据库中事务较多，项目集较大时，扫描计算量大，耗时多。针对这些缺点，近10 年来，许多学者3-8对关联规则挖掘进行了大量研究工作，深入地研究了该算法并提出了各种改进方法。较多的文献是关于候选集精减的，Apriori算法本身也是通过精减候选集来减少计算量。本文在这些研究基础之上，

3、避免对数据库中无用数据的重复扫描，从而提高算法效率。2 Apriori算法分析2.1 Apriori 算法的描述Apriori算法是基本的关联规则挖掘算法。为了减少候选数据项集的数目，Apriori 算法使用逐层搜索的方法， 通过对数据库的所有事务数据项扫描来发现所有的频繁项目集。 通过频繁项集的性质知道， 只有那些确认是频繁项的候选名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2 集所生成的项集才可能是频繁项集。所以只用频

4、繁项集生成下一趟扫描的候选集， 也就是用 Li-1生成 Ci（为频繁项集的集合， C候选项集的集合， i 为当前扫描数据库的次数） ，在每次扫描数据库时只考虑具有同数目数据项的集合。Apriori算法可以生成相对较少的候选数据项集，候选数据项集不必再反复地根据数据库中的记录产生， 而是在寻找频繁数据项集的过程中由前一次循环产生的- 频繁数据项集一次产生。此算法利用了下面这些基本概念和性质：设 I=i1，i2， in 是一组项目集， D 为事务数据库。 TI ，T 表示某事务涉及的项目集， Tid 为事务标识符，则D中的每一个事务都可以表示为Tid ，T。例如，表 1 表示一个数据库，它包含8

5、条事务。如事务 1 用 T1 表示，它包含项目 A,B,C,D,E 。其余类推。Tid Itemset Tid Itemset T1 A,B,C,D,E T5 C,D T2 A,B,D,E T6 B,C T3 B,C,E,F T7 E,F T4 F T8 A,B,C 表 1 性质 1: 一个频繁项目集的任一非空子集必定也是频繁项目集; 性质 2: 一个非频繁项目集的任一超集必定也是非频繁项目集；性质 3:k 项数据项目集是频繁项目集的必要条件是它的所有k-1 项子集均是频繁项目集；性质 4：Ck中任一项集必是Ck-1中某一项集的超集。Apriori算法描述 : 输入：事务数据库D;最小支持度值

6、 min_sup。输出： D中的频繁项集 L。方法：1） L1=find_frequent_1_itemsets(D); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 3 2） for(k=2;Lk-1；k+) 3） Ck=Apriori_gen(Lk-1,min_sup); 4） for each transaction t D /scan D for count5） Ct=subset(Ck,t); /get subse

7、ts of that are candidates 6） for each candidate cCt7） c.count+; 8） 9） L k=cCk |c.count=min_sup 10） 11）return L=k Lk; procedure apriori_gen(Lk-1;frequent(k-1)-items;min_sup:support) 1)for each itemset 11Lk-12)for each itemset 12Lk-13)if(111=121 (11k-2=12k-2 ) (11k-1=2） ，因此， T4 在以后统计更高阶频繁项集时不再用到，为了提高扫

8、描速度，删去T4，从而的到表 3。Tid A B C D E F T1 1 1 1 1 1 0 T2 1 1 0 1 1 0 T3 0 1 1 0 1 1 T5 0 0 1 1 0 0 T6 0 1 1 0 0 0 T7 0 0 0 0 1 1 T8 1 1 1 0 0 0 表 3 作链接构成候选 2- 项集，然后扫描计数，求出2-项集的支持计数，结果放名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 6 在表 4 的最后一行。

9、Tid AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF T1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 T2 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 T3 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 T5 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 T6 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 T7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 T8 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 3 2 2 2 0 4 2 3 0 2

10、1 0 2 0 2 表 4 约简事务：由表4 求出频繁2-项集，表中支持计数少于2 的项集分别为AF,BF,CE,CF,DF,因此删除这些非频繁项集，另外，在表4 中我们观察到事务 T5,T6,T7, 分别只含有一个频繁2- 项集，因此在以后的3-项集或者更高项集的链接中将不再用到这些事务，将其删除，得到表5。继续作链接，生成3-项集，扫描计数，结果放在最后一行，如表6。约简事务：由表 6 可以看出 3-项集ACD,ACE,BCD 的支持计数少于2，因此删除这些非频繁3- 项集，观察事务 T3,T8 分别只含有一个频繁3-项集，因此在以后的 3-项集或者更高项集的链接中将不会用到，将其删除，得

11、到表7。Tid AB AC AD AE BC BD BE CD DE EF T1 1 1 1 1 1 1 1 1 1 0 T2 1 0 1 1 0 1 1 0 1 0 T3 0 0 0 0 1 0 1 0 0 1 T8 1 1 0 0 1 0 0 0 0 0 表 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 7 Tid ABC ABD ABE ACD ACE ADE BCD BCE BDE T1 1 1 1 1 1 1

12、1 1 1 T2 0 1 1 0 0 1 0 1 1 T3 0 0 0 0 0 0 0 1 0 T8 1 0 0 0 0 0 0 0 0 2 2 2 1 1 2 1 3 2 表 6 Tid ABC ABD ABE ADE BCE BDE T1 1 1 1 1 1 1 T2 0 1 1 1 1 1 表 7 继续链接 4- 项集，扫描数据库，得到表8，将支持计数放在最后一行。Tid ABCD ABCE ABDE T1 1 1 1 T2 0 0 1 1 1 2 表 8 约简事务，由表 8 得出 4- 项集ABCD,ABCE支持计数少于 2，因此删除这两个非频繁项集，最终得到4- 频繁项集 ABDE

13、。4 算法思想由上述改进算法的描述可以得出其基本思想以及结构，构造n 维数组M 算法思想：1. 对 n 维数组 M 的每一列进行求和， 如果求和的结果超过给定的最小支持度阈值，则该列为频繁项集，否则为非频繁项集。2. 剔除所有非频繁项集所在列，剔除后的n 维数组中，若某行的元素的值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 8 为 1，则删除该行；3. 在约简后的 n 维数组的每一列做如下处理：1）两列合并： 设数组中每列

14、的标识项都已按字母顺序排列，如果数组中的某两列各自的标识项中只有最后一个不相同，则两个标识项可以合并成新的项。新标识项的长度比原来多1，其前面的公共部分不变，后面的两项分别取自原来两个标识项中的各自的最后一个。如：原来的两个标识项为 ABC，ABG ，则合并成 ABCG 。2）新标识项的列元素为原来两个对应的列作逻辑与运算得到，形成新的列。3）继续找下一对进行合并，直到找不到为止。每个标识项的长度为原来加1。4. 重复步骤 1步 3，直到 n 维数组中为空或只含有一列。为实现上述算法，定义以下数据结构： #define MAX_ARRAY_DIM 8 /假设数组维数的最大值为8 Typedef

15、 struct ElemType *base； /数组元素基址 int dim； /数组维数 int col_itemsn； / 数组的列标识， n 为项目总数 int *bounds； /数组维界基址 int *constants； /数组映像函数常量基址 Array 根据以上算法思想，设计具体算法如下：输入：初始 n 维数组 M ，最小支持度 输出：频繁模式Martrix.dim=事务总数；Martrix.col_size=I中所含项总数；初始化 Martrix.M ；初始化 Martrix.col_items；freq_len=0 ； /全局变量，用于记录当前要求的频繁项集的长度，即频繁

16、集中含的频繁项个数； count=0 ；/ 频繁项集计数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 9 freq_len+； ctemp=0；for k=1 to Martrix.col_size do for j=1 to Martrix.dim do ctempk=ctempk+MatrixMjk if ctempk=*Matrix.col_size then count+; 输出第 k 列所含的项标识集以及支持度ct

17、empk ； else for j=k+1 to Maatrix col_size do/删除第 k 列 MatrixMj-1=MatrixMj; Martrix col_size-； for k=1 to Matrix dim do nonzero=0; for j=1 to Matrix col_size do if MatrixMkj!=0 then nonzero+； if nonzero2 then /删除第 k 行 for j=k+1 to Maatrix dim do MatrixMj-1=MatrixMj； Matrix dim-； T_M.dim=new MATRIX； T_

18、M.dim=Matrix dim； T_M.col_size=0； for k=1 to Matrix col_size do for j=k+1 to Matrix col_size do if Matrix col_itemskfreq_len-1!= Matrix col_items名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 10 jfreq_len-1 then /第 k 列与第 j 列频繁集的最后一个频繁项不同

19、for i=freq_len-2 down to 0 do if Matrix col_itemski!= Matrix col_itemsji then break； if i0 then / 第 k 列与第 j 列频繁项集的除最后一个频繁项不同外，其余所含项目相同 T_M.col_size+； for i=1 to T_M.dim do/对第 k 列与第 j 列对应元素进行逻辑与运算 T_M.Mcol_sizei=MatrixMkj&MatrixMji； T_M.col_itemscol_size0freq_len-1=Matrix col_itemsk 0freq_len-1； T_M.

20、col_itemscol_sizefreq_len=Matrix col_itemsjfreq_len-1 ； Matrix=T_M； 5 小结本文讨论了 Apriori的改进算法，并举例说明了计算的全过程。从实例的计算过程来看，由于数据动态地减少，提高了计算效率。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 11 参考文献1 AGRAW AL R，MIELMSKIT，SWAMIA.Mining association r

21、ules between sets of items in large databasesC/Proceedings of the ACM SIGMOD Conference on Management of data Washington DC， 1993：207216. 2 Jiawei Han ，DATA MINING Concepts and techniquesM. 高等教育出版社3 陈江平，傅仲良，徐志红。一种 Apriori 的改进算法 J.武汉大学学报 （信息科学版） ， 2003，28（1):9499. 4 杨晓平，关联规则Apriori 算法的改进 J.浙江海洋学报（自然科

22、学版），25（ 2） ：176195. 5 刘培奇，李增智，王云岚等。基于数据库约简的关联规则挖掘算法J.西安交通大学学报.2003，37（8） ：836 839. 6 李云峰，陈建文，程代杰。关联规则挖掘的研究及对Apriori算法的改进 J.计算机工程与科学 .2002，24(6):6568. 7 章兢，张小刚等。数据挖掘算法及其工程应用M. 北京：机械工业出版社，2006. 8 李绪成， 王保保。 挖掘关联规则中Apriori 算法的一种改进J.计算机工程 .2002 28(7):104105：134. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -