关联规则挖掘的Apriori算法改进综述.doc

关联规则挖掘的Apriori算法改进综述1引言数据挖掘是一种半自动地从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取出隐含在其中潜在有用的信息和知识的过程。数据挖掘从数据中提取人们感兴趣的可用信息和知识，并将提取出来的信息和知识表示成概念、规则、规律和模式。数据挖掘，又称数据库中的知识发现 (Knowledge Discovery in Database, KDD)，指的是从大型数据库的数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息，换言之，数据挖掘是一个利用各种分析工具在海量数据中，发现模型和数据间关系的过程，这些模型和关系可以用来作出预测。对于数据挖掘技术的研究已引起了国际人工智能和数据库等领域专家与学者的广泛关注，这其中在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。关联规则是美国 IBM Almaden research center的Rabesh Agrawal等人于1993年首先提出的，最近几年在数据挖掘研究领域对关联规则挖掘的研究开展得比较积极和深入1。 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不停被地收集和存储，许多业界人士对于从数据库中挖掘关联规则越来越感兴趣。2 Apriori算法2.1关联规则挖掘问题的形式化描述对于经常使用的数据， 同一文件的不同版本之间的内容往往会有重复，因此数据冗余比较多，如果采用增量式压缩就可以大大节省磁盘空间。但是这样的数据是压缩的，一旦用户需要查询/恢复数据就需要解压过程， 因此这会使系统性能降低。设I=i1，i2，im是由 m个不同的项目组成的集合，给定一个事务数据库 D，其中的每一个事务 T是 I中一组项目的集合，即TI， T有一个唯一的标识符TID。若项集XI 且X T，则事务T包含项集X。一条相联规则就是形如XY的蕴涵式，其中XI，YI，xY=。相联规则XY成立的条件是: (l)它具有支持度s， 即事务数据库D中至少有s%的事务包含XY ； (2)它具有置信度c， 即在事务数据库D中包含X的事务至少有c%同时也包含Y。 关联规则的挖掘问题就是在事务数据库 D 中找出具有用户给定的最小支持度minsup和最小置信度minconf的关联规则。2.2 Apriori算法简介1994 年，Rakesh AgrawalRama 和 Krishnan Skrikant 首先提出了Apriori算法2，它是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是使用候选项集找频繁项集。Apriori算法使用一种称作逐层搜索的迭代方法k-项集用于搜索以(k+l)-项集。首先，找出频繁 1-项集的集合，该集合记作L1，L1 用于找频繁2-项集的集合L2， L2 从用于找L3.如此下去，直到不能找到频繁项集。3 Apriori算法的改进3.1 DDApriori算法3从 Apriori算法可以看出, 对每一 Ci均对数据库扫描一次,而这时有些事务已经对频繁项集的生成不产生作用, 减少数据库 D 内不起作用的事务对于算法来说是很有必要的,本算法的基本思想就基于此。该算法是在每次计算 Ci支持记数的过程中, 给不包含 Ci中的任何项集的事务打上删除标记,在以后的扫描计数中不加考虑。其实在Ci扫描过数据库后,与 Ci中某一项集相同的事务t , 如果其支持记数小于 Vmin sup, 这一事务对后面的频繁项集将不产生作用, 因此它也可以从数据库中删去。本算法通过增加这一事实,得出的算法比 3中算法更有效。随着 i 值的增大, 删除的事务也不断增大, 因而有效降低了候选项集的计数速度, 提高了整个算法的效率。算法: DDApri ori使用根据候选生成的逐行迭代找出频繁项集输入: 事务数据库 D; 最小支持记数阈值 Vmin s up输出: D中的频繁项集L方法: 10) L1= find frequent 1- itemsets( D) ;/20) for( i= 2; Li- 1 ; i + + ) 30) Ck= aproiri _gen( Li- 1, Vmin sup) ; /产生新的候选项集, 此函数同于 Apriori算法中的函数40) for each transaction t D /扫描 D并计数41) if t . delet e= 0 then do be gin50) Ct= subset( Ci , t) ; /获取 t的子集作为候选51) if Ct= then52) t . delet e= 1/打上删除标志53) els e/对每一个Ct进行计数并记录内容54) if Ct= c then t . count + + , t . t ext= c60) for each candi date c Ct .70) c. count + + ;71) end80) 81) if 0 t. count and t. text . count Vmin_sup then82) t . delete= 1/去掉已无作用的事务 t90) Li= cCi | c. c ountVmin_sup /得到满足条件的 Li100) 110) return L= iLi ;下面举例说明。设最小支持记数为 2。支持度计数简记为Sup。图示如下:C1 database L1Item Sup I1 4 I2 5 I3 5 I4 4 I5 4TID itemT100 I1 I2 I5T200 I1 I4T300 I3 I5T400 I2 I4T500 I3 I4T600 I2 I3T700 I4 I5T800 I1 I2 I3 I5T900 I1 I2 I3Item set I1 I2 I3 I4 I5 I1 4 C2 database L2Item set Sup I1 I2 3 I1 I3 2 I1 I5 2 I2 I3 3 I2 I5 2 I3 I5 2TID itemT100 I1 I2 I5T200 I1 I4T300 I3 I5T400 I2 I4T500 I3 I4T600 I2 I3T700 I4 I5T800 I1 I2 I3 I5T900 I1 I2 I3Item set I1 I2 I1 I3 I1 I4 I1 I5 I2 I3 I2 I4 I2 I5 I3 I4 I3 I5 I4 I5C3 database L3Item set Sup I1 I2 I3 2 I1 I2 I5 2TID itemT100 I1 I2 I5T300 I3 I5T600 I2 I3T800 I1 I2 I3 I5T900 I1 I2 I3Item set I1 I2 I3 I1 I2 I5 I2 I3 I5从图中可以看出, 在 C2 扫描数据库时, 数据库中的事务T200, T400, T500, T700 在 C2 中, 且它的支持记数小于 2, 因此在 C3 扫描时, 数据库 D 已经不再考虑它们,数据库已经有了很大的缩小,这对于大型数据来说是很有用处的。3.2基于矩阵的MApriori算法本算法的基本思想为, 对数据库给出一个矩阵表示。具体方法为: 对每一成员按一序排列,事务集也按一序列进行排列。成员分别表示行向量, 事务表示列向量,若第 i 个成员在第j 个事务中,则矩阵的第 i 行, 第j 列的值为 1,否则为0, 称其为数据库的布尔矩阵。上面的数据库可以用矩阵表示如下:此矩阵的行向量之和为成员出现的次数, 则一项集的支持记数可求出。对于二项集 Ii , Ij 只需扫描第 i 行与第j 行即可,他们同一列的值均为 1 的个数, 即为二项集 Ii , I j 的支持记数,依此类推。只需扫描矩阵的第 i1 , i2 , , ik 行,他们同一列的值均为 1 的个数即为 k 项集 Ii 1 , I i 2 , , I ik 的支持记数。可以看出, Ci扫描数据库时只扫描一部分, 而不是 Apriori 算法要扫描全部数据库, 这样算法效率就高。此算法中 Ci 的求法与 Apriori算法一样,算法描述如下:算法:MApri ori使用根据候选生成的逐行迭代找出频繁项集。输入: 事务数据库 D的布尔矩阵M; 最小支持记数阈值Vmin_sup.输出: D中的频繁项集L方法:10) L1 = find_frequent 1- it emsets( D) ;20) for( i= 2;Li- 1; i + ) 30) Ci= aproiri_gen(Li- 1 ,Vmin_sup) ; /产生新的候选项集40) for each transaction c Ci /扫描矩阵M 并计数50) for ( j= 1; j M_列数; j + ) if M c_1 j = 1 and M c_2 j = 1 and. . . and M c_i j = 1 then70) c. c ount + + ;80) 90) Li= cCi | c. count Vmin_sup ; 得到满足条件的Li100) 110) return L=iLi; 作为理解, 取上一例子作以简单说明。由布尔矩阵的各行和可以得出一项集的支持记数,从而求出 L1 , 进而得出 C2。对C2 中的每一项集扫描数据库的布尔矩阵, 并且记数。比如对二项集 I 1 , I 2 ,只需扫描第一行与第二行, 每一列同为 1 的记数,得出它的支持记数为 3。依次取遍 C2 , 支持记数大于或者等于Vmin_sup 的项集生成 L2 , 由L 2 生成 C3 ,在对 C3 中的每三项集扫描布尔矩阵, 这时要扫描 3 行。依此类推,直到算法终止。3.3 基于数组的改进方法4 与 Apr i or i算法有关的变种有很多,这些变体通常针对如下三个目标中的一个或者多个: 最小化扫描数据的次数;最小化必须分析的候选项集; 最小化计算每个候选集频率所需的时间。文献5提出了一种基于内存数组的算法, 该算法只扫描一次数据库,建立数据库的镜像内存数组,将对数据库的扫描转化为对内存数组的扫描, 由于内存的寻址和读写速度都远远大于磁盘的寻址和读写速度, 所以该算法大大提高了 Apriori算的运行速度。算法如下:输入: Database D; Minimum support thres hold min_sup输出: L , frequent item sets in D方法:L1 = Find Large Item 1( D, A n m , min_sup) ;L2 = Find Large Item 2( L1, A n m , min_sup );f or( k= 3 ; ; k+ + ) do begin Ck = Apriori_gen ( ) ;f or( i= 1 ; i=n*min_sup) L1= 1i; /*找出频繁1_项集*/for (k=2; 1 ；k+) /*找出候选k_项集 */for Lk-1中的每个项集for Lk-11中的每个项集if ( 1= 1)( k-2= k-2)( k-1= k-1)c= ;Ck=CkC ;for 中的每个( k-1)-项集s /*事先剪枝*/if (s Lk-1) Ck=Ck -s; for 扫描事务树中 number=k的事务 tfor t中的每个 k- 项子集 sif ( sCk ) s.sup_count=s.sup_count+1;for Ck 中的每个项集 c/*找出频繁 k-项集*/if (c.sup_count=n*min_sup) Lk = Lkc L=LLk ; for L 中的每个频繁项集 l /*求强关联规则集合*/for l 中的每个非空真子集if (l.sup_count/ .sup_count=min_conf)R_S=R_S=l-4.结束语Aprior被应用于各个方面,所以也有很多相应的改进方法,例如：Web使用挖掘中Apriori算法的改进，改进的算法BI_Apriori9采用不规则的数组来保存项集信息，这些算法的主要目的都是有效省去了扫描数据库所耗费的大量时间;同时在对Apriori算法存在的问题进行一些改进，采用新的修剪策略，利用Apriori算法的性质找出一个影响效率的因素,用来提高算法的效率，增加独立性检验，从而将该算法能利用的更加有效。参考文献:1 冯兴杰,周谆. Apriori 算法的改进J.计算机工程,2005,07(31):172-1732 李超,余昭平. 基于矩阵的 Apriori 算法改进J.计算机工程,2006,12(32):68-693马盈仓.挖掘关联规则中 Apriori算法的改进J. Computer Appl ications and Software,2004,21(11):82-834钱少华,蔡勇钱,雪忠.基于数组的Apriori算法的改进J.计算机应用与软件.2006, 23(2):111