关联规则Apriori算法的改进
摘要：文章提出一种改进的apriori算法。该算法通过减少对数据库搜索的次数，从而减少数据挖掘过程中的i/o开销。实践证明，用此算法进行关联挖掘，其效率比传统的方法要高。
关键词：数据挖掘关联规则频繁项集 apriori算法improvement of apriori algorithm for association rules
li xiao-hui
(college of computer science and technology,changchun university,changchun 130022,china)
abstract：this paper presents an improved apriori algorithm. the new algorithm can decrease the i/o operation of the process of mining by means of decreasing the times of database searching. it is shown by the experimental result that the improved algorithm is much more efficient than the traditional algorithm in being applied to mining association rule.
neywords：data mining，association rule，frequent itemset，apriori algorithm
1、引言
随着数据库技术和计算机网络的发展,在海量数据里发现有价值
的知识和信息的工作受到了越来越多的重视。数据挖掘的一个重要方向是关联规则的挖掘，而关联规则挖掘中最经典算法是apriori
算法[1]。但在实际应用中，apriori算法还存在着很多令人不尽满意的地方。有许多文献中也针对这些缺点提出了改进的算法[2],但算法也大多较复杂。本文在这些基础上提出了一种apriori算法新的改进。
2、关联规则定义
设i={i1,i2,…,im}为项目集，d是全体事务记录的集合。i有一个子集是事务t，事务集合t∈i，每个事务记录都有一个标识符tid。关联规则实际上是一个蕴涵式，形如x=>y，其中x∈i，y∈ i 同时x∩y=。其中x是关联规则的条件，y是关联规则的结果。关联规则x=>y对d的支持度的定义是事务集合d中包含有x和y的百分比。关联规则x=>y对d的置信度的定义是事务集合d中同时包含x和y的事务占x的百分比。
3、算法的改进
3.1 改进算法的思路
第一个步骤要简单统计所有含一个元素的项目，其出现的频率，同时找出那些大于或者等于最小支持度的那些项目集，这时就产生了一维频繁项目集g1。接着开始用循环结构处理，一直到不再产生维数更高的频繁项目集为止。循环过程描述如下:在第n步骤中，用第n-1个步骤产生的n-1维频繁项目集来生成n维的候选项目集，接着再用apriori算法来检验新的n维频繁项目集中的所有n-1维项目集是否已经包含在已经计算出的n-1维频繁项目集中。再扫描数据库d中的每个事务，如果该事务中至少含有候选项目集cn中
的一项，那么保留该项事务，否则把该事务与数据库末端未作删除标记的事务进行对换，并且把那个移到数据库末端的事务加上一个删除标记，最后把整个扫描完成的数据库保存到另一个的事务数据库d’中。
3.2 改进后的算法
(1)g1={large1-itemset};
(2)t1=d;
(3)for(n=1; gn≠ ; n++);
(4)cn+1=apriori_gen(gn);
(5)for all transactions t∈tn do begin
(6)ct=subset(gn,t);
(7)t.count=|ct|; //记为t.count
(8)if(t.count;
(9)end;
(10)for all transaction t∈tn+1 do begin;
(11)ct=subset(cn+1,t);
(12)for all candidate c∈ct do begin;
(13)c.sup++;
(14)end;
(15)gn+1={c∈cn+1|c.sup≥min sup};
(16)end;
(17)answer=gn
Apriori算法改进及其实现 内容摘要 信息技术的不断推广应用，将企业带入了一个信息爆炸的时代。如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。 本文通过对参与候选集的元素计数的方法来减少产生候选集的组合和减少数据库的扫描次数来达到要求。这有利于提高挖掘的速度和减少数据库的I/O 操作时间的开销。 关键字：数据挖掘，关联规则，Apriori算法
Apriori Algorithm And Improved Apriori Algorithm Abstract：An information burst age is coming with the various application of Information technology. How to maximize the information is a very important problem for the decision-maker of the companies. Besides getting the regular information from the Database by SQL-query, people still need to mine the data relation which is unclear but really exists.Association rules is one of the data mining methods, the famous algorithm Apriori is a method, which can be used to solute those problems. This article analyzes and studies the improved algorithm Apriori based on the algorithm of mining association rules Apriori. The main idea is to decrease the number of candidate items and to decrease the times of Database scanning. The solution is available. It upgrades the speed of data mining and decreases computer's I/O operation. It's proved to be more efficient than the traditional Key words: Datamining, association rules, Apriori algorithm,
Ｖｏｌ．２９Ｎｏ．１ Ｊａｎ．２０１３ 赤峰学院学报（自然科学版）ＪｏｕｒｎａｌｏｆＣｈｉｆｅｎｇＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）第29卷第1期（下） 2013年1月关联规则挖掘算法的研究目前是数据挖掘领域的一个重要方向，其中，Ａｐｒｉｏｒｉ算法就是一个经典的挖掘关联规则算法．１９９３年，Ａｇｒａｗａｌ等提出关联规则挖掘的相关概念，随后提出经典Ａｐｒｉｏｒｉ算法，它是一个采用两阶段挖掘思想的算法，且多次扫描事务数据库，直到寻找出给定数据集中数据项之间有趣的关联规则．1关联规则基本概念 １．１ 关联规则 关联规则是形如Ａ圯Ｂ的蕴含式，在关联规则中，有两 个重要的概念：支持度和置信度．支持度是对关联规则的重要性的衡量，置信度是对关联规则的准确度的衡量，一般情况下，用户根据实际挖掘需要，预先给定最小支持度和最小置信度，通常情况下，如果规则的置信度和支持度大于用户指定的最小置信度和支持度，那么这个规则就是一条有效规则．事实上，有效规则并不一定具有实用性，还要参照关联规则的其他指标． 定义1 设Ｉ＝｛Ｉ１，Ｉ２，…，ＩＭ｝是数据项的集合，Ｄ是全体事务 的集合，一个事务Ｔ有一个唯一的标识ＴＩＤ．如果项集Ａ哿Ｔ，则称事务Ｔ支持项集Ａ，也称事务Ｔ包含项集Ａ． 定义2 关联规则是形如Ａ圯Ｂ的蕴含式，其中Ａ奂Ｉ，Ｂ奂Ｉ，且Ａ∩Ｂ＝Φ． 定义3 事务数据库Ｄ中有Ｎ条交易事务，关联规则 Ａ圯Ｂ的支持度定义为： ｓｕｐｐｏｒｔ（Ａ圯Ｂ）＝ｓｕｐｐｏｒｔ（Ａ∪Ｂ）×１００％．定义4 置信度定义为： ｃｏｎｆｉｄｅｎｃｅ（Ａ圯Ｂ）＝ｓｕｐｐｏｒｔ（Ａ∪Ｂ）×１００％． 引理1 在数据库中若有一事务Ｔ其长度小于Ｋ＋１，则 由Ｋ项频繁集生成Ｋ＋１项频繁集时，事务Ｔ是没必要扫描的．１．２ Ａｐｒｉｏｒｉ算法的基本思想 Ａｐｒｉｏｒｉ算法是发现关联规则的经典算法．该算法分两个步骤发现关联规则：第一步通过迭代，找出事务数据库中的所有频繁项集，即支持度不低于最小支持度的项集；第二步利用频繁项集构造出满足用户最小可信度的规则．2 Apriori 算法的不足之处 Ａｐｒｉｏｒｉ算法最大的优点是算法思路比较简单，它以递归统计为基础，生成频繁项集，易于实现．Ａｐｒｉｏｒｉ算法虽然能够从海量数据中挖掘出关联规则，但是算法在执行速度和效率上有一定的局限性，表现如下：２．１ Ａｐｒｉｏｒｉ算法会产生大量的候选项集．该算法是由候选 集函数Ａｐｒｉｏｒｉ－Ｇｅｎ利用Ｌｋ－１项产生候选项集Ｃｋ，所产生的Ｃｋ由Ｃｋ Ｌｋ－１ 项集组成．显然ｋ越大产生的候选项集的数目就越多． ２．２Ｉ／Ｏ负载过大．Ａｐｒｉｏｒｉ算法需要多次扫描事务数据库， 需要很大的Ｉ／Ｏ负载．对每次ｋ循环，候集Ｃｋ中的每个元素都必须扫描数据库１次来决定其是否加入Ｃｋ．例如，一个频繁大项目集包含１２个项，那么就至少扫描事务数据库１２遍．3 对Apriori 算法的改进 算法改进的思路 １．改变数据的存储结构，用二进制位存储各项目的事务集，矩阵的列代表频繁Ｋ－项集，矩阵的行代表事务，其中１表示该项目在某事务中出现，０表示该项目在某事务中没有出现． ２．生成频繁１－项集．首先扫描源数据库，生成矩阵．统计每列中包含１的数目，得到该项目的支持事务数，如果该项的支持事务数大于最小支持事务数，则该项是频繁项集，否则是非频繁项集．从矩阵中将该列删除，并根据引理１，在矩阵中删除第９行，得出频繁１－项集． ３．由频繁１－项集生成频繁２－项集．对频繁１－项集中的项两两连接得出候选２－项集，也就是对矩阵中第ｉ列所代表的项集和第ｊ列所代表的项集进行逻辑与操作．然后计 关联规则挖掘算法的研究 张 丽 （湖南文理学院 经济与管理学院，湖南 常德415000） 摘要：本文介绍了数据挖掘中的关联规则经典Ap r i or i 算法.针对Ap r i or i 算法在执行速度和效率上的缺点，提出了一种改进的Ap r i or i 算法. 关键词：Ap r i or i ；算法；关联规则中图分类号：ＴＰ３１１ 文献标识码：Ａ 文章编号：１６７３－２６０Ｘ（２０１３）０１－００２２－０２ 基金项目：湖南文理学院2010年度青年启动课题（QNQD1017） ２２－－
研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘 学院：交通运输 专业：交通运输规划与管理 年级：硕1003班 姓名：张令杰 学号：10121084 指导教师：徐维祥
摘要 (Ⅰ) 一、引言 (1) 二、关联规则的基本描述 (1) 三、经典频繁项集挖掘的Apriori算法 (3) 四、提高Apriori算法的效率 (6) 五、由频繁项集产生关联规则 (8) 六、总结 (9) 参考文献 (9)
目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。 关键词：Apriori算法；关联规则；频繁项集；候选集
一、 引言 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析[1] 。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。 最著名的关联规则发现方法是R. Agrawal 提出的Apriori 算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。 二、关联规则的基本描述 定义1. 项与项集 数据库中不可分割的最小单位信息，称为项目，用符号i 表示。项的集合称为项集。设集合{}k i i i I ,,,21 =是项集，I 中项目的个数为k ，则集合I 称为k -项集。例如，集合{啤 酒，尿布，牛奶}是一个3-项集。 定义2. 事务 设{}k i i i I ,,,21 =是由数据库中所有项目构成的集合，一次处理所含项目的集合用T 表示，{}n t t t T ,,,21 =。每一个i t 包含的的项集都是I 子集。 例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。 定义3. 项集的频数（支持度计数） 包括项集的事务数称为项集的频数（支持度计数）。 定义4. 关联规则 关联规则是形如Y X ?的蕴含式，其中X ，Y 分别是I 的真子集，并且φ=?Y X 。 X 称为规则的前提，Y 称为规则的结果。关联规则反映X 中的项目出现时，Y 中的项目也 跟着出现的规律
1 Apriori介绍 Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I 出现次数更多。因此A∩I也不是频繁的。 2连接步和剪枝步 在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1）连接步 为找出L k（所有的频繁k项集的集合），通过将L k-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作C k。设l1和l2是L k-1中的成员。记l i[j]表示l i中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集l i，l i[1] Apriori算法实验报告 1背景 关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等，其中快速挖掘与更新频繁项目集是关联规则挖掘研究的重点，也是多种数据挖掘应用中的技术关键，已用于分类规则挖掘和网络入侵检测等方面的研究。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。 2 算法描述 Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁K项L k 集用于搜索频繁(K+1)项集L k+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。 算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k 次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集L k-1和用Aprioir-gen函数产生候选项集C k。接着扫描数据库，计算C k中候选的支持度。用Hash树可以有效地确定C k中包含在一个给定的事务t中的候选。算法如下： (1) L1 = {大项目集1项目集}; (2) for (k = 2; L k-1 != 空; k++) do begin (3) C k = apriori-gen(L k-1); //新的候选集 (4) for 所有事务t ∈D do begin (5) C t = subset ( C k，t); //t中所包含的候选 (6) for 所有候选 c ∈C t do (7) c.count++; (8) end (9) L k = {c ∈C k | c.count ≥ minsupp} (10) end (11) key = ∪L k； Apriori-gen函数： Apriori候选产生函数Apriori-gen的参数L k-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把L k-1和L k-1相连接以获得候选的最终集合的一个超集C k： 关联规则挖掘算法的研究 摘要：Apriori算法是发现频繁项目集的经典算法，但是该算法需反复扫描数据库，因此效率较低。本文介绍了Apriori算法的思想，同时对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改进算法，做一个简单的叙述。 关键词数据挖掘；关联规则；Apriori算法 Keywords：data mining；relation rule；Apriori algorithm 关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、AprioriTid 等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。但实际中，遇到的情况可能是：随着时间的推移，挖掘数据库的规模可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何从数据发生变动后的数据库中高效地对已经推导出的关联规则进行更新，具有非常重要的应用价值，这就是所谓的增量式挖掘关联规则的问题。 1关联规则 问题描述：设I={i1，i2，...，i m}是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即T I，T有一个惟一的标志符TID。如果对于I中的一个子集X，有X T，我们就说一个事务T包含X。一条关联规则(association rule)就是一个形如X =>Y的蕴涵式，其中X，Y T，而X∩Y=Φ。关联规则成立的条件是：①它具有最小支持度s，即事务数据库D中至少有s%的事务包含X∪Y；②它具有最小可信度c，即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。关联规则的挖掘问题可以分解为以下两个问题： (1) 找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称为频繁项目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。 (2) 利用频繁项目集生成关联规则。对于每一个频繁项目集A，若B A，B≠Φ，且support(A)/support(B)>minconf，则有关联规则B=> (A-B)。目前大多数的研究主要集中在第一个问题上面。 2 Apriori核心算法 Agrawal等人于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法Apriori算法，其核心是基于两个阶段频繁项集思想的递推算法。算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。Apriori核心算法思想简要描述如下：该算法中有两个关键步骤连接步和剪枝步。 (1) 连接步：为找出Lk(频繁k一项集)，通过Lk-1与自身连接，产生候选k-项集，该候选项集记作Ck；其中Lk-1的元素是可连接的。 关联分析（笔记） 事物之间的关联关系包括：简单关联关系、序列关联关系。 关联关系简单关联关系 序列关联关系 简单关联规则：属于无指导学习方法，不直接用于分类预测，只揭示事物内部的结构。Spss modeler 提供了APriori、GRI、Carma等经典算法。APriori和Carma属于同类算法。 序列关联：关联具有前后顺序，通常与时间有关。 SPSS Modeler 提供了sequence算法； 数据格式如下：按照事务表存储，同事需要时间变量。 简单关联规则要分析的对象是事务 事务的储存方式有事务表和事实表两种方式。 事实表 两种表均表明，顾客1购买了AD两种物品，顾客2购买了BD两种物品，顾客三购买了AC两种物品。关联规则有效性的测度指标 1、支持度support：所有购买记录中，A、B同时被购买的比例。 2、置信度confidence：在购买A的事务中，购买B的比例。 关联规则实用性的测度指标 1、提升度lift：（在购买A的事务中，购买B的比例）/（所有事务中，购买B的比例） 2、置信差 3、置信率、正态卡方、信息差等等简单关联关系实例 例1 数据格式：事实表算法:Apriori 所有购买项目均选入前项antecedent和后项consequent。 输出结果的最低支持度是10%；本例设定的划分频繁项集的标准大于最小支持度10%。 最小置信度是80%； 前项最多项目数：5 本例中，三项以上没有超过10%的支持度，所以不能形成三项以上的频繁项集，最大的频繁项集大小是2。 结论解释： 实例：包含前项beer、cannedveg的样本有167个，在1000个样本中前项支持度为16.7%。 规则支持度：同时购买beer、cannedveg、frozenmeal三项的支持度为14.6%。 规则置信度：购买beer、cannedveg的客户中，87.425%的人有购买frozenmeal。 规则2下，购买frozenmeal的可能性比购买frozenmeal的支持度提高2.895倍。 关联规则算法Apriori的学习与实现 (2011-07-18 11:28:52) 首先我们来看，什么是规则？规则形如”如果…那么…(If…Then…)”,前者为条件，后者为结果。关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶?面包[支持度：3%，置信度：40%] 支持度3%意味3%顾客同时购买牛奶和面包。置信度40%意味购买牛奶的顾客40%也购买面包。规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联规则是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。 我们先来认识几个相关的定义： 定义1：支持度（support） 支持度s是事务数据库D中包含A U B的事务百分比，它是概率P（A U B），即support （A B）=P（A U B），它描述了A和B这两个物品集的并集在所有的事务中出现的概率。定义2：置信度（confidence） 可信度为事务数据库D中包含A的事务中同时也包含B的百分比，它是概率P（B|A），即confidence（A B）=P（B|A）。 定义3：频繁项目集 支持度不小于用户给定的最小支持度阈值（minsup）的项集称为频繁项目集（简称频集），或者大项目集。所有 的频繁1-项集记为L1。 假设有如下表的购买记录。 顾客项目 1orange juice, coke 2milk, orange juice, window cleaner 3orange juice, detergent 4orange juice, detergent, coke 5window cleaner 将上表整理一下，得到如下的一个2维表 Orange Win Cl Milk Coke Detergent Orange41122 WinCl12100 Milk11100 Coke20021 Detergent10002 上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。 置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A==>B)=P(B|A)。例如计算"如果 关联规则Apriori算法的改进 摘要：文章提出一种改进的apriori算法。该算法通过减少对数据库搜索的次数，从而减少数据挖掘过程中的i/o开销。实践证明，用此算法进行关联挖掘，其效率比传统的方法要高。 关键词：数据挖掘关联规则频繁项集 apriori算法improvement of apriori algorithm for association rules li xiao-hui (college of computer science and technology,changchun university,changchun 130022,china) abstract：this paper presents an improved apriori algorithm. the new algorithm can decrease the i/o operation of the process of mining by means of decreasing the times of database searching. it is shown by the experimental result that the improved algorithm is much more efficient than the traditional algorithm in being applied to mining association rule. neywords：data mining，association rule，frequent itemset，apriori algorithm 1、引言 随着数据库技术和计算机网络的发展,在海量数据里发现有价值 的知识和信息的工作受到了越来越多的重视。数据挖掘的一个重要方向是关联规则的挖掘，而关联规则挖掘中最经典算法是apriori 关联规则算法探讨 发表时间：2010-01-08T10:11:56.840Z 来源：《企业技术开发》2009年第10期供稿作者：梁伟（中国地质大学信息工程学院，湖北武汉430074 [导读] 本文对关联规则的发展进行了简单的介绍，分析了关联规则的经典算法 作者简介：梁伟（1976-），男，广西崇左人，硕士研究生，主要研究方向：数据库技术数据挖掘。 摘要：本文对关联规则的发展进行了简单的介绍，分析了关联规则的经典算法，介绍进了一种新的关联规则算法，并对这三种算法在挖掘关联规则的特点进行了对比分析，最后对关联规则以后的发展进行了总结。 关键词：数据挖掘；关联规则；算法；探讨 1发展历史 随着信息技术的迅猛发展,许多领域搜集、积累了大量的数据,迫切需要一种新技术从海量的数据中自动、高效地提取所需的有用知识。对这些海量数据进行研究的过程中，数据挖掘技术受到越来越多的关注。我们可以使用数据挖掘技术从海量数据中发掘其中存在的潜在规律。并将这些规律进行总结，用于今后的决策。采用关联规则在大型事务数据库中进行数据挖掘是数据挖掘领域的一个重要研究内容。从大量数据中发现项之间有趣的、隐藏的关联和相关联系正是关联规则目的。 关联规则技术在不断成熟和发展，应用范围不断扩大，由最初的购物篮分析发展到计算机入侵检测、搜索引擎、警务预警、交通事故、保险业、金融业、农业专家系统、教学评估、股票分析等领域。在理论研究方面，由最简单的单维、单层、布尔关联规则逐渐向复杂形式扩展，由频繁模式挖掘不断扩展到闭合模式挖掘、扩展型关联规则、最大模式挖掘、衍生型关联规则、关联规则隐私保护、挖掘后处理、增量挖掘、规则主观兴趣度度量、相关模式、数据流等多种类型数据上的关联规则挖掘等。 2相关概念 设项的集合I = { i l ，i 2 ，…，i m }，D为数据库事务集合，每个事务T是一个项目子集，似的T I。每个事务由事务标识符TID标识。若有X I， X T，则称T包含X；如果X有k个元素，称X为k-项集。 关联规则的逻辑蕴含式为：X Y[s,c] ，其中X I ，Y I 且 X Y= 。规则X Y在事务集D中成立，并且具有支s和置信度c。支持s是指事务集X Y含的百分比：support(X Y)=P(X Y)，置信度c是指D中包含X的事务同时也包含Y的百分比confidence(X Y)=P(Y|X)。 对于一个事务集D，挖掘关联规则的问题就是找出支持度和可信度分别大于用户给定的最小支持度阀值(minsupp)和最小置信度(minconf)阀值的关联规则，这种规则成为强关联规则。 3经典算法 基于频繁集的方法是关联规则挖掘的主要方法,Aproiri算法是基于频繁集的算法最主要算法之一，在数据挖掘中具有里程碑的作用,但是Apriori算法本身存在着一些固有的无法克服的缺陷，而后出现的基于频繁集的另外一种算法FP-gorwth算法能较好地解决APriori算法存在的一些问题。下面分别介绍两种经典的算法。 3.1产生候选频繁项集 Apriori算法是Rabesh Agrawal等人在1994年提出的，该算法采用了一种宽度优先、逐层搜索的迭代方法：首先产生所有的频繁1-项集，然后在此基础上依次产生频繁2-项集、频繁3-项集……，直到频繁k-项集为空集。在此过程中，产生每个频繁项集都需要扫描一次数据库，通过对数据库D的多趟扫描来发现所有的频繁项目集。 设Ck表示候选k-项集，Lk表示Ck中出现频率大于或等于最小支持数的k-项集，即k-频繁集或者是k-大项集。该算法的基本过程如下。 ①首先计算所有的C1； ②扫描数据库，删除其中的非频繁子集，生成L1(1-频繁项集)； ③将L1与自己连接生成C2(候选2-项集)； ④扫描数据库，删除C2中的非频繁子集，生成L2(2-频繁项集)； ⑤依此类推，通过Lk-1((k-1)-频繁项集)与自己连接生成Ck(候选k-项集)，然后扫描数据库，生成Lk(频繁k-项集)，直到不再有产生频繁项集为止。 Apriori算法虽然能较有效地产生关联规则，同时也存在着不少缺点: ①数据库太大时对候选项集的支持度计算非常繁琐，当支持度、置信度阀值设置太低会产生过多的规则，致使用户难易人为地对这些规则进行出区分和判断。 ②要对数据进行多次扫描，需要很大的I/O负载，算法的效率不高。 ③当数据库D很大时，会产生庞大的候选集，导致算法的耗时太大。 3.2不产生候选频繁项集 FP-Tree算法由 Jiawei Han提出。它的基本思路是将数据集中的重要信息压缩在一个称为频繁模式树(FP-Tree)的数据结构中，然后基于FP-Tree生成数据集中所有的频繁项集。该算法对所有频繁项集的挖掘分为以下两步：①构造频繁模式树FP-Tree。在 FP-Tree中，每个结点有4个域组成结点名称、结点计数、结点链及父结点指针。另外，为方便树遍历，创建一个频繁项头表，它由两个域组成：项目名称及结点链头，其中结点链头指向 FP-Tree中与之名称相同的第一个结点；②调用FP-Growth挖掘出所有频繁项集，具体算法描述如下。 ①生成频繁模式树，首先，扫描事务数据库 D一次，产生频繁1-项集，并把它们按降序排列，放入L表中。其次，创建 FP-Tree的根结点，以“null”标记。再一次扫描D，对于D中的每个事务按 L中的次序排序，并对每个事务创建一个分枝。 ②挖掘频繁项集，首先，从FP-tree的头表开始，按照每个频繁项集的链接遍历，列出能够到达此项的所有前缀路径，得到条件模式基。其次，用条件模式基构造对应的条件FP-tree。第三，递归挖掘条件FP-tree，直到结果FP-tree为空，或者只含有唯一的一个路径(此路径上的每个子路径对应的项集都是频繁项集)。 FP-Growth算法是一种基于模式增长的频繁模式挖掘算法，采用了“分而治之”策略，它能够在不产生候选频繁项集的情况下挖掘全部频繁项集，直接将数据库压缩成一个频繁模式树FP-tree，只需要两次扫描数据库，相对于Apriori算法效率快一个数量级。该算法虽然可以避 Apriori ['e?pr?'?:r?] Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛的应用到商业、网络安全等各个领域。 其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。 Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。 Apriori算法应用于网络安全领域，比如网络入侵检测技术中。早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。 Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求"与"运算，寻找频繁项集。实验结果表明，改进后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。 Apriori算法被广泛应用于移动通信领域。移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。随着产业的复苏，越来越多的增值业务表现出强劲的发展势头，呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这种趋势，在关联规则数据挖掘中广泛应用的Apriori 算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台，对来自移动增值业务方面的调查数据进行了相关的挖掘处理，从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息，这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。 1.关联规则概述 1.1关联规则 超市，商场的商品应该如何摆放最合适?啤酒和尿布这两类不同商品能否摆在一起?数据挖掘的经典案例——啤酒尿布告诉我们顾客的购买行为存在一定的关联，使我们不得不重视经典的购物车问题。 关联规则的挖掘就是通过一系列数据分析来挖掘某种特定的商品组合被顾客同时购买的可能。关联规则的分析有R.Agrawal于1993年最早提出，是KDD 研究的重要内容，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和置信度的多个域之间的依赖关系。关联规则的挖掘是数据挖掘的一项重要任务，其目的就是从事物数据库、关系数据库中发现项目集或属性之间的相关性，关联关系，因果关系。 1.2关联规则的概念： 关联规则是描述数据库中数据项之间存在的潜在的关系规则。问题可以描述如下： I ={i1，i2，i3….im}是所有项的集合，相当与商品的种类集合。D 是所有事务的子集，相当于数据库中的记录集合。每个事务T 由I中的若干项组成，是I的子集，用唯一的ID 标识，记为T = { t1，t2，. . . ，tn }，相当于每次交易中的商品列表。假设X，Y 是数据项集，X 中含有的项的数目为k，称为k_数据项集，是I 的子集。关联规则表示为: ( T 中包含X) ( ( T中包含Y)。意义在于一次交易中(数据库中的一条记录)存在X 项目，意味着该交易中也存在Y 项目。通常简写为X ( Y，X 称为关联规则的前项，Y称为该关联规则的后项，称为关联操作。)关联规则主要解决的两个问题：找出所有频繁项集和分析频繁项集找出关联规则。 2.关联规则算法简介 2.1宽度优先算法：Apriori 算法 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。 2.2深度优先算法：FP-Growth算法 针对Apriori算法的不足，通过减少项集的搜索空间和数据库的扫描次数，Han于2004年提出了一个无需产生候选集，只需扫描两次数据库的算FP-Growth。FP-Growth采取如下策略:首先将要挖掘的数据库压缩到一棵频繁模式树中，并在压缩的过程中保留项集的关联信息;然后，将压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库，每个关联一个频繁项)，然后分别挖掘每个条件数据库来产生频繁项集。与逐层进行的宽度优先搜索算法不同，基于深度优先搜索的FP_ Growth算法对整个搜索空间的分枝逐个进行搜索，所以，只有当某个节点上的项集属于频繁项集的时候，才会对其子节点作进一步的搜索。 FP-Growth频繁项集挖掘算法的主要步骤： 第一步，构造FP树: （1）扫描事务数据库DB，找出1-频繁项集，并根据它们的支持度计数按降序排序， 结果一记为L。 （2）创建FP树的根节点，记为“null”，并置为当前树根。 （3）扫描DB中的一个事务T:根据L选出T中的频繁项，并按L中的顺序排列， /* 这个程序是数据挖掘中的Apriori算法*/ #include 关联规则基本算法及其应用 1．关联规则挖掘 1.1 关联规则提出背景 1993年，Agrawal 等人在首先提出关联规则概念，同时给出了相应的挖掘算法AIS ，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori 算法，至今Apriori 仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。假设分店经理想更多的了解顾客的购物习惯（如下图）。特别是，想知道哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营销策略。 1.2 关联规则的基本概念 关联规则定义为：假设12{,,...}m I i i i =是项的集合，给定一个交易数据库 12D ={t ,t ,...,t }m ， 其中每个事务(Transaction)t 是I 的非空子集，即t I ∈，每一个交易都与 一个唯一的标识符TID(Transaction ID)对应。关联规则是形如X Y ?的蕴涵式， 其中X ,Y I ∈且X Y φ?=， X 和Y 分别称为关联规则的先导(antecedent 或left-hand-side, LHS)和后继(consequent 或right-hand-side, RHS)。关联规则X Y ?在D 中的支持度(support)是D 中事务包含X Y ?的百分比，即概率()P X Y ?；置信度(confidence)是包含X 的事务中同时包含Y 的百分比，即条件概率(|)P Y X 。如果满足最小支持度阈值和最小置信度阈值，则称关联规则是有趣的。这些阈值由用户或者专家设定。 Apriori算法例子 Apriori算法例子 算法integerstringeach数据库c 1 Apriori介绍 Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。 其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I 出现次数更多。因此A∩I也不是频繁的。 2 连接步和剪枝步 在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。 1）连接步 为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li， li[1]<li[2]<……….<li[k-1]。将Lk-1与自身连接，如果(l1[1]=l2[1])&&( l1[2]=l2[2])&&……..&a mp;& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接。连接l1和l2 产生的结果是 {l1[1],l1[2],……,l1[k-1],l2[k-1]}。 2）剪枝步 CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 （Tip：为什么要压缩CK呢？因为实际情况下事务记录往往是保存在外存储上，比如数据库或者其他格式的文件上，在每次计算候选计数时都需要将候选与所有事务进行比对，众所周知，访问外存的效率往往都比较低，因此Apriori加入了Apriori算法实验报告
关联规则挖掘算法研究
关联分析--SPSS例析
关联规则算法Apriori的学习与实现
关联规则Apriori算法的改进
关联规则算法探讨
Apriori算法总结
关联规则算法改进
数据挖掘中的Apriori算法(C语言版)
关联规则基本算法
Apriori算法例子
相关主题
文本预览