《大型超市购物篮问题》由会员分享，可在线阅读，更多相关《大型超市购物篮问题（20页珍藏版）》请在金锄头文库上搜索。
1、模式识别期中作业 -挖掘布尔关联规则频繁项集的算法Apriori算法一、问题重述作为超市的经理，经常关心的问题是顾客的购物习惯。他们想知道：“什么商品组或集合顾客多半会在一次购物时同时购买？”。现在假设你们是某超市的市场分析员，已经掌握了该超市近一个星期的所有顾客购买物品的清单和相应商品的价格，需要你们给超市经理一个合理的“购物篮”分析报告，并提供一个促销计划的初步方案。问题一： 附件1中的表格数据显示了该超市在一个星期内的4717个顾客对999种商品的购买记录，对数据进行分析，试建立一种数学模型，使该模型能定量表达超市中多种商品间的关联关系的密切程度。问题二：根据问题1建立的模型，通过一种快
2、速有效的方法从附件1中的购买记录中分析出哪些商品是最频繁被同时购买的，找到的最频繁被同时购买的商品数量越多越好。问题三：附件2给出了这999中商品的对应的利润，根据在问题1、问题2中建立的模型，设定一种初步的促销方案，使超市的效益进一步增大。二、模型的假设1、假设各个商品的利润保持不变。2、假设表格中的数据能真实地反映当地消费者的购物情况。3、假设短时间内商品的销售情况维持稳定，不会出现大幅波动。三、符号说明符号解释说明si组合i的支持度c(A=B)规则A=B的置信度c(B=A)规则B=A的置信度ci 组合i的平均置信度smin最小支持度cmin最小置信度关联密切系数H促销系数四、问题分析本题
3、是关于大型超市“购物篮”的分析问题，涉及到数据挖掘、关联规则等相关问题。本题的三个问题是层层递进的关系，要求通过对商品购买数据的分析，找到关联程度较高且购买次数较高的商品，最后设计出合理的超市促销方案。问题一，由于购物篮分析是关联规则挖掘的一个典型案例，因此我们采用一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori算法。利用其基本思想，进行了商品两种之间的支持度和置信度计算，在定义最小支持度和最小置信度后，进行筛选得到关联规则集。为定量地表达超市中多种商品间的关联关系的密切程度，本文引入一个关联密切系数进行衡量分别对12个组合求解平均置信度,进而得到该组的关联密切系数。由此认为，关联密
4、切系数越大的商品组合，其关联关系密切程度较高。问题二，在得到商品两种关联数据的基础上，仅考虑商品支持度的大小，求得在一定最小支持度下被频繁地同时购买的商品组合。同时为使商品数量尽量多，我们在两种组合的情况下延伸至三种组合，四种组合以此得到尽可能多的商品被频繁同时购买的信息，尽量靠近最频繁被同时购买且商品数量越多的双重目标。问题三，在结合商品利润的条件下，考虑两种组合中各商品的利润、支持度和置信度，分别计算出三者的乘积再求和，记为促销系数H，并以此作为衡量此组合商品是否进行促销的标准。当结果较高时，我们就采取就近摆放、打折促销、消费送礼等捆绑销售方式式得到一种促销方案，在方便顾客的购买的同时，增
5、加消费者对该超市的有好感和信任度，最终使得超市的效益进一步增大。五、模型的建立和求解模型一：基于Apriori算法的关联规则挖掘模型1. 模型的准备 设: I= i1,i2.,im 是所有项目的集合. D是所有事务的集合(即数据库), 每个事务T是一些项目的集合, T包含在D中, 每个事务可以用唯一的标识符TID来标识.设X为某些项目的集合,如果X包含在T中,则称事务T包含X,关联规则则表示为如下形式(X包含在T)=(Y包含在T)的蕴涵式,这里X包含在I中, Y包含在I中,并且XY=.其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现(为简单化,将(X包含在T)=(Y包含在T
6、)表示为X=Y,这里,= 称为关联操作，X称为关联规则的先决条件,Y称为关联规则的结果). 事务数据库D中的规则X=Y是由支持度s（support）和置信度c(confidence)约束,置信度表示规则的强度, 支持度表示在规则中出现的频度。数据项集X的支持度s(X)是D中包含X的事务数量与D的总事务数量之比, 但为下文便于叙述, 数据项集X的支持度是用数据库D中包含X的数量来表示; 规则X=Y的支持度s定义为: 在D中包含XY的事务所占比例为s%, 表示同时包含X和Y的事务数量与D的总事务量之比。用该项集出现的次数除以TID总数即可得到，用如下公式表示：Support(X)=Count(X)
7、/Count(TID) 规则X=Y的置信度c定义为: 在D中,c%的事务包含X的同时也包含Y, 表示D中包含X的事务中有多大可能性包含Y. 依据所求的频繁项集，及所求得的支持度，运用如下公式求解：Confidence(X=Y)=Support(XY)/Support(X) 最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性. 最小置信度阈值mincontinence表示规则的最低可靠性. 如果数据项集X满足X.support=minsupport, 则X是大数据项集. 一般由用户给定最小置信度阈值和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱
8、关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则. 基于上述概念，我们可以很容易得到一些基本结论: (1) K维数据项集XK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为XK-1（2） 如果K维数据项集XK的任意一个K-1维子集XK-1，不是频繁项集，则K维数据项集XK本身也不是最大数据项集。 (3) XK是K维频繁项集，如果所有K-1维频繁项集集合XK-1中包含XK的K-1维子项集的个数小于K，则XK不可能是K维最大频繁数据项集。 证明: 很明显，数据项集XK-1:的K-1维子项集的个数为K-1。如果高频繁数据项集XK-1，中包含XK的
9、K-1.维子项集的个数小于K，则存在XK的K-1维子项集不是频繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。 2、 模型的建立（1）求关联规则集第一步：从事务数据库D中找出所有支持度不小于指定的最小支持度阈值的频繁项集。第二步：使用频繁项集产生所期望的关联规则，产生关联规则的基本原则是其置信度不小于指定的最小置信度阈值。第一步的任务是迅速高效地找出D中全部的频繁项集，这是关联规则挖掘的核心问题，是衡量关联规则挖掘算法的标准。对此，我们运用Matlab进行编程得出计算结果。第二步的求解比较容易和直接，先分别计算出不小于最小支持度的商品组合对应的置信度，降序后进行筛选。最后只留下
10、支持度和置信度都较高的商品组合。此建模过程可以表示为：图1 关联规则挖掘模型示意图（2） 关联关系的密切程度表示 对商品组合数据的挖掘结果进行整理，得到关联规则表格，再利用表格中各商品组合对应的支持度和平均置信度表示组合的关联关系。例如：在组合i中，有两个编号分别为、的两个商品，其支持度为，平均置信度为，则该组合的关联关系可以表示为（）.为定量表达超市中多种商品间的关联关系的密切程度，我们引入一个关联密切系数来衡量，我们认为当支持度和置信度分别大于距离最低支持度和最低置信度时，其距离越远，关联程度越高，于是得到其公式为：其中，为组合i的支持度，为该组合的平均置信度,和分别为该类组合的最小支持度
11、和最小置信度。用图表示为：图2 关联密切系数示意图将12组商品组合的支持度和平均置信度带入关联密切系数的公式中进行计算，将所得数据列表降序排列，关联系数越大的商品组合的关联关系的密切程度越大。3、 模型的求解对于问题1：（1） 将最小支持度设定为5%，从4717个原始数据项中得到个数为17的频繁项集。按支持度降序排列后，依次编号，整理得到表1：表1 两种组合频繁项集表组合i编号A编号B支持度13685290.07079270923688290.0663416732173680.06167867743684890.06167867753686820.06125476963684190.05701
12、568573689370.05553200583686920.05532005193685100.055108097103689140.054896142115296920.054472234125298290.054048326133687200.0527766144385290.051716829152175290.051292921166928290.051080967174198290.05023315对由上表得到的数据，分别计算各个组合相互的置信度，并将最小置信度设定为20%，剔除部分数据后得到关联规则集。再对数据列表的s(A=B)进行降序处理，重新编号后得到表2： 表2 关联规则表
13、组合i编号A编号B支持度s置信度c(A=B)置信度c(B=A)12173680.0616786770.3112299470.21748878926928290.0510809670.2960687960.21849501434385290.0517168290.2867215040.2240587742175290.0512929210.2588235290.22222222254198290.050233150.2513255570.2148685463685290.0707927090.2496263080.30670339875296920.0544722340.2359963270.3
14、1572481685298290.0540483260.234159780.2311876793688290.066341670.2339312410.283771532103684890.0616786770.2174887890.328442438113686820.0612547690.2159940210.352869353123684190.0570156850.2010463380.285259809 最后留下的12个支持度和置信度都较高的商品组合即为关联规则集。（3） 为定量地表达超市中多种商品间的关联关系的密切程度，分别对12个组合求解平均置信度,进而得到该组的关联密切系数。如表3所示：表3 关联密切评定表组合i编号A编号B支持度平均置信度关联密切系数12173680.0616786770.2643593680.06541039526928290.0510809670.25728190
