研究生课程论文关联规则挖掘基本概念和算法课程名称：数据仓库与数据挖掘学院：交通运输专业：交通运输规划与管理年级：硕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 中的项目也跟着出现的规律定义5. 关联规则的支持度（support ）关联规则的支持度是交易集中同时包含的X 和Y 的交易数与所有交易数之比，记为support ()Y X ⇒，即Support ()Y X ⇒= support Y X ⋃=()XY P支持度反映了X 和Y 中所含的项在事务集中同时出现的频率。

定义6. 关联规则的置信度（confidence ）关联规则的置信度是交易集中包含X 和Y 的交易数与所有交易数与包含X 的交易数之比，记为confidence ()Y X ⇒，即Confidence ()Y X ⇒=()()()X Y P X port Y X port =⋃sup sup 置信度反映了包含X 的事务中，出现Y 的条件概率。

定义7. 最小支持度与最小置信度通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限，当support ()Y X ⇒、confidence ()Y X ⇒分别大于等于各自的阈限值时，认为Y X ⇒是有趣的，此两个值称为最小支持度阈值(min_ sup)和最小置信度阈值(min_ conf)。

其中，min_ sup 描述了关联规则的最低重要程度，min_ conf 规定了关联规则必须满足的最低可靠性。

定义8. 频繁项集设{}n u u u U ,,,21 =为项目的集合，且I U ⊆，Φ≠U ，对于给定的最小支持度min_ sup ，如果项集U 的支持度support ()U ≥min_ sup ，则称U 为频繁项集，否则，U 为非频繁项集。

定义9. 强关联规则support ()Y X ⇒≥min_ sup 且confidence ()Y X ⇒≥min_ conf ，称关联规则Y X ⇒为强关联规则，否则称Y X ⇒为弱关联规则。

性质[2]. 设X 和Y 是数据集D 中的项目集（1）若Y X ⊆，则support ()X ≥support ()Y（2）若Y X ⊆，如果X 是非频繁项目集，则Y 也是非频繁项目集，即任意弱项目集的超集都是弱项集。

（3）若Y X ⊆，如果Y 是非频繁项目集，则X 也是非频繁项目集，即任意大项集的子集都是大项集。

三、经典频繁项集挖掘的Apriori 算法[3]（一）Apriori 算法基本思想。

Apriori 算法基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。

Apriori 算法对数据集进行多次扫描。

第一次扫描得到频繁1-项集的集合L 1，第k （k>1）次扫描首先利用第（k-l ）次扫描的结果L k 来产生候选k-项集的集合C k ，然后再扫描的过程中确定C k 中元素的支持度，最后再每一次扫描结束时计算频繁k-项集的集合L k ，算法当候选k-项集的集合C k 为空时结束。

（二）Apriori 算法产生频繁项集的过程。

产生频繁项集的过程主要分为连接和剪枝两步：①连接步。

为找L k ，通过L k-1与自身作连接产生候选k-项集的集合C k 。

设1l 和2l 是L k-1中的项集。

记[]j l i 表示i l 的第j 个项。

Apriori 假定事务或项集中的项按字典次序排序。

对于（k-1）项集i l ，意味将项排序，使[]1i l < []2i l <…<[]1-k l i 。

如果Lk-1的元素1l 和2l 的前（k-2）个对应项相等，则1l 和2l 可连接。

即，如果（[]11l =[]12l ）∩（[]21l =[]22l ）∩…∩（[]21-k l =[]22-k l ）∩（[]11-k l <[]12-k l ）时，1l 和2l 可连接。

条件[]11-k l <[]12-k l 仅仅是保证不重复。

连接1l 和2l 产生的结果项集为（[]11l ，[]21l ，…，[]11-k l ，[]12-k l ）。

②剪枝步。

Apriori 算法的性质可知，频繁k-项集的任何子集必须是频繁项集。

由连接生成的集合Ck 需要进行验证，去除不满足支持度的非频繁k-项集。

（三）Apriori 算法的主要步骤①扫描全部数据，产生候选1-项集的集合C 1；②根据最小支持度，由候选1-项集的集合C 1产生频繁1-项集的集合L 1；③对k>1，重复执行步骤④、⑤、⑥；④由L k 执行连接和剪枝操作，产生候选（k+l ）-项集的集合C k+1；⑤根据最小支持度，由候选（k+l ）-项集的集合C k+1，产生频繁（k+1）-项集的集合L k+1； ⑥若L ≠Φ，则k=k+1，跳往步骤④；否则，跳往步骤⑦；⑦根据最小置信度，由频繁项集产生强关联规则，结束。

（四）Apriori 算法描述。

输入：数据库D ，最小支持度阀值min_ sup输出：D中的频繁集L（1）Begin（2）L1=1-频繁项集；（3）for（k=2；L k-1≠Φ；k++）do begin（4）C k=Apriori_ gen（L k-1）；{调用函数Apriori_ gen（L k-1）通过频繁（k-1）-项集产生候选k-项集}（5）for所有数据集t∈D do begin {扫描D用于计数}（6）C t=subset（C k，t）；{用subset找出该事务中是候选的所有子集}（7）for所有候选集c∈C t do（8）c. count++；（9）end；（10）L k={c∈C k |c. count≥min_ sup}（11）end（12）end（13）Return L1∪L2∪L k…∪L m{形成频繁项集的集合}（五）、Apriori算法的举例[1]下图是一个数据库的事务列表，在数据库中有9笔交易，即|D|=9。

每笔交易都用不同的TID作代表，交易中的项按字典序存放，下面描述一下Apriori算法寻找D中频繁项集的过程。

设最小支持度计数为2，即min_ sup=2，利用Apriori算法产生候选项集及频繁项集的过程如下所示：第一次扫描：扫描数据库D 获得每个候选项的计数：C 1 L 1由于最小事务支持数为2，没有删除任何项目。

可以确定频繁1-项集的集合L1，它由具有最小支持度的候选1-项集组成。

第二次扫描：为发现频繁2项集的集合L 2，算法使用L 1∞L 1产生候选2项集的集合C 2。

在剪枝步没有候选从C 2中删除，因为这些候选的每个子集也是频繁的。

C 1 C 2 L 2第三次扫描：L 2∞L 2产生候选3项集的集合C 3。

C3 C3 L3候选3项集C3的产生详细地列表如下：(a) 连接C3=L2∞L2={{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} ∞{{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}}={{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}(b) 使用Apriori性质剪枝：频繁项集的所有非空子集也必须是频繁的。

例{I1，I3，I5}的2项子集是{I1，I3}，{I1，I5}和{I3，I5}。

{I3，I5}不是L2的元素，因而不是频繁的。

因此，从C3中删除{I1，I3，I5}(c) 这样，剪枝C3={{I1，I2，I3}，{I1，I2，I5}}第四次扫描：算法使用L3∞L3产生候选4-项集的集合C4。

L3∞L3={{I1，I2，I3，I5}}，根据Apriori 性质，因为它的子集{I2，I3，I5}不是频繁的，所以这个项集被删除。

这样C4= Φ，因此算法终止，找出了所有的频繁项集。