关联规则挖掘基本概念和算法张令杰

研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘学 院：交通运输 专 业：交通运输规划与管理 年 级：硕1003班 姓 名：张令杰 学 号： 指导教师：徐维祥 目录摘要.一、引言.1二、关联规则的基本描述.1三、经典频繁项集挖掘的Apriori算法.3四、提高Apriori算法的效率.6五、由频繁项集产生关联规则.8六、总结.9参考文献.9摘要目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。关键词：Apriori算法 ；关联规则；频繁项集；候选集 - -一、 引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析1。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。最著名的关联规则发现方法是R. Agrawal提出的Apriori算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。二、关联规则的基本描述定义1. 项与项集数据库中不可分割的最小单位信息，称为项目，用符号表示。项的集合称为项集。设集合是项集，中项目的个数为，则集合称为-项集。例如，集合啤酒，尿布，牛奶是一个3-项集。定义2. 事务设是由数据库中所有项目构成的集合，一次处理所含项目的集合用表示，。每一个包含的的项集都是子集。例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。定义3. 项集的频数（支持度计数）包括项集的事务数称为项集的频数（支持度计数）。定义4. 关联规则关联规则是形如的蕴含式，其中，分别是的真子集，并且。称为规则的前提，称为规则的结果。关联规则反映中的项目出现时，中的项目也跟着出现的规律定义5. 关联规则的支持度（support）关联规则的支持度是交易集中同时包含的和的交易数与所有交易数之比，记为support，即Support = support=支持度反映了和中所含的项在事务集中同时出现的频率。定义6. 关联规则的置信度（confidence）关联规则的置信度是交易集中包含和的交易数与所有交易数与包含的交易数之比，记为confidence，即Confidence =置信度反映了包含的事务中，出现的条件概率。定义7. 最小支持度与最小置信度通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限，当support、confidence分别大于等于各自的阈限值时，认为是有趣的，此两个值称为最小支持度阈值(min_ sup)和最小置信度阈值(min_ conf)。其中，min_ sup描述了关联规则的最低重要程度，min_ conf规定了关联规则必须满足的最低可靠性。定义8. 频繁项集设为项目的集合，且，对于给定的最小支持度min_ sup，如果项集的支持度supportmin_ sup，则称为频繁项集，否则，为非频繁项集。定义9. 强关联规则supportmin_ sup且confidencemin_ conf，称关联规则为强关联规则，否则称为弱关联规则。性质2. 设和是数据集D中的项目集（1）若，则supportsupport（2）若，如果是非频繁项目集，则也是非频繁项目集，即任意弱项目集的超集都是弱项集。（3）若，如果是非频繁项目集，则也是非频繁项目集，即任意大项集的子集都是大项集。三、经典频繁项集挖掘的Apriori算法3（一）Apriori算法基本思想。Apriori算法基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描得到频繁1-项集的集合L1，第k（k1）次扫描首先利用第（k-l）次扫描的结果Lk来产生候选k-项集的集合Ck，然后再扫描的过程中确定Ck中元素的支持度，最后再每一次扫描结束时计算频繁k-项集的集合Lk，算法当候选k-项集的集合Ck为空时结束。（二）Apriori算法产生频繁项集的过程。产生频繁项集的过程主要分为连接和剪枝两步：连接步。为找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，跳往步骤；否则，跳往步骤；根据最小置信度，由频繁项集产生强关联规则，结束。（四）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. countmin_ 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，I5I4，I5项集 支持度数I1，I2 4I1，I3 4I1，I4 1 I1，I5 2I2，I3 4I2，I4 2I2，I5 2I3，I4 0I3，I5 1I4，I5 0项集 支持度计数I1，I2 4I1，I3 4I1，I5 2I2，I3 4I2，I4 2I2，I5 2第三次扫描：L2L2产生候选3项集的集合C3。 C3 C3 L3项集I1，I2，I3I1，I2，I5项集 支持度计数I1，I2，I3 2I1，I2，I5 2项集 支持度计数I1，I2，I3 2I1，I2，I5 2候选3项集C3的产生详细地列表如下：(a) 连接C3=L2L2=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第四次扫描：算法使用L3L3产生候选4-项集的集合C4。L3L3=I1，I2，I3，I5，根据Apriori性质，因为它的子集I2，I3，I5不是频繁的，所以这个项集被删除。这样C4= ，因此算法终止，找出了所有的频繁项集。四、提高Apriori算法的效率Apriori算法的最大的优点是算法思路比较简单，它以递归统计为基础，生成频繁项集，易于实现。Apriori算法作为经典的频繁项目集生成算法，在数据挖掘技术中占有很重要的地位。但通过上面的分析发现，为了生成Ck，在连接步骤需要大量的比较，而且由连接产生的项集即使后来由Apriori性质确定了它不是候选项集，但在确定之前仍然需要对它生成子项集，并对子项集进行确定是否都在Lk-1中。这些步骤浪费了大量的时间，如果可以保证由连接步生成的项集都是候选项集的话，那么可以省掉不必要的连接比较和剪枝步骤。下面介绍改进后的算法4。（一）、算法介绍首先对Lk-1中的每项进行扫描，记下项集 ， ， ， ， ， ，。设1个k项集=，由Apriori性质知道，如果属于Ck，那么以下的(k-1)个(k-1)项集就必须都出现在Lk-1中，所以 至少要出现(k-2)次，至少要出现(k-3)次，依次类推，至少要出现1次。设扫描得到的 出现次数为a，如果a(k-2)，则可以将Lk-1中所有以开头的(k-1)项集全部删除，如果a(k-2)，那么比较扫描得到的，出现次数b与(k-3)的大小，若b(k-3)，则删除Lk-1中所有以，开头的项集，如果b(k-3)，则继续比较下一项。通过简单的数字比较，可以大量地从Lk-1中删除项集，这样可以大大地减少不必要的连接。连接生成的k项集，也只需要比较1次就可以确定是否属于Ck。运用新的算法，从另一个先删减再连接的新视角来生成频繁项集，可以减少大量的无用连接，进而也减少了剪枝步需要判断是否为候选项集的数量，在时间上提高了效率。（二）、实例说明通过由频繁3项集生成4项候选集的例子，说明是如何通改进的算法在连接前对频繁3项集进行删减的。设L3=I1，I2，I3，I1，I2，I6，I2，I3，I4，I2，I3，I5，I2，I4，I5，I3，I4，I5，I3，I5，I6，I4，I5，I6。扫描L3，得到相关的计数。下表所示为删减L3中项集的过程。经过删减得Lk=I2，I3，I4，I2，I3，I5，Lk自连接只生成1个4项集I2，I3，I4，I5。I3，I4，I5L3，所以，得到候选项集C4=I2，I3，I4，I5。通过验证，结果是正确的。扫描项出现次数比较数操作I1I1,I2I2I2,I3I2,I4I3I3,I4I3,I5I422321211132322322323，从L3中删除所有以I1开头的项集。不再比较以I1开头的项集出现次数，从I2开头的项集出现次数开始比较。无操作33，比较I2开头的项集出现的次数。2 2，保留L3中以I2，I3开头的项集，继续下一步比较。12，删除L3中以I2,I4开头的项集，进行I3比较。23，从L3中删除所有以I3开头的项集。不再比较以I3开头的项集出现次数，从I4开头的项集出现次数开始比较。无操作无操作1 3，从L3中删除所有以I4开头的项集。结束。如果采用经典的Apriori算法，先连接生成2个4项集I1，I2，I3，I6，I2，I3，I4，I5，再进行剪枝，最坏情况下，需要扫描8个子项集是否在L3中，才能确定，I1，I2，I3，I6，I2，I3,I4，I5是否为候选项集。而采用新的算法，只连接生成1个4项集，再进行剪枝步，只需要扫描1个子项集I3，I4，I5是否在L3中。运用新的算法，从另一个先删减再连接的新视角来生成频繁项集，可以减少大量的无用连接，进而也减少了剪枝步需要判断是否为候选项集的数量，在时间上提高了效率。 五、由频繁项集产生关联规1一旦由数据库中的事务找出频繁项集，可直接由它们产生强关联规则。对于置信度，confidence = 其中support（ ）是包括项集 的事务数，而support（ ）是包括项集 的事务数。根据该式，关联规则可以产生如下：对于每个频繁项集l，产生l的所有非空子集。对于l的每个非空子集s，如果 min_ conf ，则输出关联规则“s （l-s) ”。 产生关联规则例子：上例中频繁项集l=I1,I2,I5。可以由l产生哪些关联规则？设最小置信度阈值为70%