关联规则挖掘的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中一组项目的集合，即T?I， T有一个唯一的标识符TID。若项集X?I 且X? T，则事务T包含项集X。一条相联规则就是形如X?Y的蕴涵式，其中X?I，Y?I，x∩Y=Φ。相联规则X?Y成立的条件是: (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 gin 50)




Ct= subset( Ci , t) ;
//获取 t的子集作为候选 51)