《关联规则挖掘基本概念和算法--张令杰10121084》由会员分享，可在线阅读，更多相关《关联规则挖掘基本概念和算法--张令杰10121084（12页珍藏版）》请在金锄头文库上搜索。
1、研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘学 院：交通运输 专 业：交通运输规划与管理 年 级：硕1003班 姓 名：张令杰 学 号：10121084 指导教师：徐维祥 目录摘要.一、引言.1二、关联规则的基本描述.1三、经典频繁项集挖掘的Apriori算法.3四、提高Apriori算法的效率.6五、由频繁项集产生关联规则.8六、总结.9参考文献.9摘要目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并
2、分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。关键词：Apriori算法 ；关联规则；频繁项集；候选集 - -一、 引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析1。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一
3、商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。最著名的关联规则发现方法是R. Agrawal提出的Apriori算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。二、关联规则的基本描述定义1. 项与项集数据库中不可分割的最小单位信息，称为项目，用符号表示。项的集合称为项集。设集合是项集，中项目的个数为，则集合称为-项集。例如，集合啤酒，尿布
4、，牛奶是一个3-项集。定义2. 事务设是由数据库中所有项目构成的集合，一次处理所含项目的集合用表示，。每一个包含的的项集都是子集。例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。定义3. 项集的频数（支持度计数）包括项集的事务数称为项集的频数（支持度计数）。定义4. 关联规则关联规则是形如的蕴含式，其中，分别是的真子集，并且。称为规则的前提，称为规则的结果。关联规则反映中的项目出现时，中的项目也跟着出现的规律定义5. 关联规则的支持度（support）关联规则的支持度是交易集
5、中同时包含的和的交易数与所有交易数之比，记为support，即Support = support=支持度反映了和中所含的项在事务集中同时出现的频率。定义6. 关联规则的置信度（confidence）关联规则的置信度是交易集中包含和的交易数与所有交易数与包含的交易数之比，记为confidence，即Confidence =置信度反映了包含的事务中，出现的条件概率。定义7. 最小支持度与最小置信度通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限，当support、confidence分别大于等于各自的阈限值时，认为是有趣的，此两个值称为最小支持度阈值(min_ sup)和最小置
6、信度阈值(min_ conf)。其中，min_ sup描述了关联规则的最低重要程度，min_ conf规定了关联规则必须满足的最低可靠性。定义8. 频繁项集设为项目的集合，且，对于给定的最小支持度min_ sup，如果项集的支持度supportmin_ sup，则称为频繁项集，否则，为非频繁项集。定义9. 强关联规则supportmin_ sup且confidencemin_ conf，称关联规则为强关联规则，否则称为弱关联规则。性质2. 设和是数据集D中的项目集（1）若，则supportsupport（2）若，如果是非频繁项目集，则也是非频繁项目集，即任意弱项目集的超集都是弱项集。（3）若，
7、如果是非频繁项目集，则也是非频繁项目集，即任意大项集的子集都是大项集。三、经典频繁项集挖掘的Apriori算法3（一）Apriori算法基本思想。Apriori算法基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描得到频繁1-项集的集合L1，第k（k1）次扫描首先利用第（k-l）次扫描的结果Lk来产生候选k-项集的集合Ck，然后再扫描的过程中确定Ck中元素的支持度，最后再每一次扫描结束时计算频繁k-项集的集合Lk，算法当候选k-项集的集合Ck为空时结束。（二）Apriori算法产生频繁项集的过程。产生频繁项
8、集的过程主要分为连接和剪枝两步：连接步。为找Lk，通过Lk-1与自身作连接产生候选k-项集的集合Ck。设和是Lk-1中的项集。记表示的第j个项。Apriori假定事务或项集中的项按字典次序排序。对于（k-1）项集，意味将项排序，使 。如果Lk-1的元素和的前（k-2）个对应项相等，则和可连接。即，如果（=）（=）（=）（）时，和可连接。条件1，重复执行步骤、；由Lk执行连接和剪枝操作，产生候选（k+l）-项集的集合Ck+1；根据最小支持度，由候选（k+l）-项集的集合Ck+1，产生频繁（k+1）-项集的集合Lk+1；若L，则k=k+1，跳往步骤；否则，跳往步骤；根据最小置信度，由频繁项集产生强
9、关联规则，结束。（四）Apriori算法描述。输入：数据库D，最小支持度阀值min_ sup输出：D中的频繁集L（1）Begin（2）L1=1-频繁项集；（3）for（k=2；Lk-1；k+）do begin（4）Ck=Apriori_ gen（Lk-1）； 调用函数Apriori_ gen（Lk-1）通过频繁（k-1）-项集产生候选k-项集（5）for所有数据集tD do begin 扫描D用于计数（6）Ct=subset（Ck，t）；用subset找出该事务中是候选的所有子集（7）for所有候选集cCt do（8）c. count+；（9）end；（10）Lk=cCk |c. countm
10、in_ sup （11）end （12）end （13）Return L1L2LkLm 形成频繁项集的集合（五）、Apriori算法的举例1下图是一个数据库的事务列表，在数据库中有9笔交易，即|D|=9。每笔交易都用不同的TID作代表，交易中的项按字典序存放，下面描述一下Apriori算法寻找D中频繁项集的过程。事务商品ID的列表T100I1，I2I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3设最小支持度计数为2，即min_ sup=2，利用Apriori算法产生候选项集及频繁项集的过程如下所示：第一次扫描：扫描数据库D获得每个候选项的计数：项集支持度计数I16I27I36I42I52 C1 L1 项集支持度计数I16I27I36I42I52比较候选支持计数 与最小支持度计数由于最小事务支持数为2，没有删除任何项目。可以确定频繁1-项集的集合L1，它由具有最小支持度的候选1-项集组成。第二次扫描：为发现频繁2项集的集合L2，算法使用L1L1产生候选2项集的集合C2。在剪枝步没有候选从C2中删除，因为这些候选的每个子集也是频繁的。 C1 C2 L2项集I1，I2I1，I3 I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5
