基于关联规则挖掘的超市货物摆放次序优化方法研究

基于关联规则挖掘的超市货物摆放次序优化方法研究李正欣，郭建胜（空军工程大学工程学院，陕西西安710038）摘要：使用关联规则挖掘算法分析超市购物清单时，会产生不止“啤酒→尿布”的单一关联规则，而将出现涉及多种商品的“纵横交错”的多条关联规则。针对这一实际问题，本文在使用关联规则挖掘的基础上，提出一种评估关联规则中两商品间相互“促销”关系的方法，实现优化超市货物摆放次序的目的。关键词：关联规则；关联规则挖掘；Apriori算法；关联规则评估中图法分类号：TP311文献标识码：AResearchonApproachforOptimizingCommodityPuttingOrderBasedonAssociationRulesMiningLiZheng-xin，GuoJian-sheng(TheAirForceEngineeringInstitute，Xi’anShanxi710038)Abstract:Whenusingapriorialgorithmtoanalysisthemarketlistings,manycomplicatedassociationrulesmaybegetted,whicharedifferentfromthesingle“beeranddiaper”associationrule;Sobasedonassociationrulesmining,amethodofevaluatingtheassociationruleoftwoitemsisprovidedtooptimizethecommodityputtingorderofmarkets.Keywords:AssociationRule；AssociationRulesMining；AprioriAlgorithm；EvaluationofAssociationRules1.引言全球最大的零售商沃尔玛(Walmart)通过对顾客购物清单的数据挖掘发现了“尿布→啤酒”的关联规则，后来沃尔玛就把尿布和啤酒摆放在一起，从而双双促进了尿布和啤酒的销量。如果我们最终挖掘出的关联规则除了尿布→啤酒外，还有啤酒→香烟、啤酒→启瓶器、香烟→打火机、打火机→刮胡刀等，由于货架空间的限制，一种商品最多只能与另外两种商品摆放在一起（左、右两边各摆放一种商品），超市的货物应该按照怎样的次序摆放能够获利最大呢？这一问题主要涉及三个方面的内容：1、挖掘出多种商品间的关联规则；2、综合评估各个关联规则涉及的两种商品间的“促销”关系；3、根据关联规则和商品间的“促销”关系，利用最优化理论，确定商品的摆放次序。2.关联规则的挖掘原理及基本算法设集合I={i1,i2,…,im}，其中的元素称为项(item)。记D为交易(transaction)T的集合，这里交易T是项的集合，并且T∈I。对应每一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如果X∈T，那么称交易T包含X。一个关联规则是形如X→Y的蕴涵式，这里X∈I,Y∈I，并且X∩Y=NULL。规则X→Y在交易数据库D中的支持度（support）是交易集中包含X和Y的交易数与所有交易数之比，记为support(X→Y)，即：support(X→Y)=|X∩Y|/|D|。规则X→Y在交易集中的置信度（confidence）是指包含X和Y的交易数与包含X的交易数之比，记为confidence(X→Y)，即：confidence(X→Y)=|X∩Y|/|X|。给定一个交易集D，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度(min_sup)和最小置信度(minconf)的关联规则。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，设计了基于频繁集理论的Apriori算法。这是一个基于两阶段频繁集思想的方法，将关联规则挖掘算法的设计分解为两个子问题：1、找到所有支持度大于最小支持度的项集（itemset），这些项集称为频繁集(frequentitemset)；2、使用第一步找到的频繁集产生期望的规则。为了生成所有频繁集，使用了递推的方法，生成所有频繁项集的Apriori算法流程如下所示：L1={large1-itemsets};For(k=2;Lk-1≤n;k++)doBeginCk=apriori_gen(Lk-1);//新的候选集Foralltransactionst∈DdoBeginCt=subset(Ck,t);//事务t中包含的候选集Forallcandidatesc∈Ctdoc.count++;EndLk={c∈Ck|c.count≥min_sup}EndAnswer=∪kLk;Procedureapriori_gen(Lk-1,min_sup)Ck=NULLForeachitemsetli∈Lk-1Foreachitemsetlj∈Lk-1If(li[1]=lj[1])∧(li[2]=lj[2])∧…∧(li[k-2]=lj[k-2])∧(li[k-1]=lj[k-1])≥min_supthenBeginc=lijoinljifhas_infrequent_subset(c,Lk-1)deletec;elseaddctoCk;EndReturnCk;Procedurehas_infrequent_subset(c,Lk-1)Foreach(k-1)-subsetsofcIfsLk-1thenReturnTURE;ReturnFALSE;首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁集做一个（k-2）连接来产生的。Ck中的项集是用来产生频繁集的候选集，最后的频繁集Lk必须是Ck的一个子集,Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk中。3.评估关联规则中商品间的“促销”关系假设超市的顾客源是稳定的，即一年内来超市消费的顾客数量是一定的。对于关联规则尿布→啤酒[S,C,Q,P]，其中S是支持度，表示100S％的顾客同时买尿布和啤酒；C是置信度，表示100C％购买尿布的顾客还会购买啤酒；Q是平均购买量，表示在所有购买啤酒的顾客中，平均每位顾客购买的啤酒数量；P是利润，表示超市每卖出一瓶啤酒的盈利(注意:Q，P只是针对关联规则的推出项)。那么，顾客总数×S可以理解为同时购买尿布和啤酒的顾客人数；顾客总数×S×C可以理解为在尿布的“促销”下，还会购买啤酒的顾客人数；顾客总数×S×C×Q×P表示受尿布“促销”啤酒模式的影响所产生的超市利润。所以对于以盈利为目的的超市而言，顾客总数×S×C×Q×P可以用来评估关联规则“尿布→啤酒”中，尿布对啤酒“促销”作用的强弱，数值越大说明尿布对啤酒的“促销”作用越强。然而超市把两种商品摆放在一起，不仅要考虑尿布对啤酒的“促销”作用，还要充分考虑啤酒对尿布的“促销”作用，这也是传统的关联规则挖掘问题中所忽视的一个细节。虽然关联规则“尿布→啤酒”的反向规则“啤酒→尿布”可能不满足已设定的最小置信度，但是通过对其反向规则“啤酒→尿布”的分析，找出啤酒对尿布的“促销”关系对全面评估啤酒和尿布摆放在一起所能够产生的价值也是有意义的。对于关联规则尿布→啤酒[S,C,Q,P]的反向规则啤酒→尿布[S’,C’,Q’,P’]，S’是支持度，表示100S’％的顾客同时买啤酒和尿布；C’是置信度，表示100C’％购买啤酒的顾客还会购买尿布；Q’是平均购买量，表示在所有购买尿布的顾客中，平均每位顾客购买的尿布数量；P’是利润，表示超市每卖出一张尿布的盈利(注意:Q’，P’只是针对反向规则的推出项)。同理可以求得，受啤酒“促销”尿布模式的影响所产生的超市利润可以表示为：顾客总数×S’×C’×Q’×P’。因此，顾客总数×S×C×Q×P+顾客总数×S’×C’×Q’×P’可以用来表示尿布与啤酒两种商品间的相互“促销”关系。由于顾客源是稳定的，可视为常数，所以引入“促销”系数W=S×C×Q×P+S’×C’×Q’×P’，来衡量两种商品间“促销”关系的强弱。W越大，说明两种商品间的促销作用越明显，把这两种商品摆放在一起能够带来更多的利润。4.商品摆放次序的优化方法设从超市购物清单中挖掘出的关联规则及其相关信息如下表所示：表1关联规则信息表关联规则支持度置信度平均购买量利润尿布→啤酒S1C1Q1P1啤酒→香烟S2C2Q2P2香烟→打火机S3C3Q3P3尿布→打火机S4C4Q4P4尿布→刮胡刀S5C5Q5P5刮胡刀→香烟S6C6Q6P6再找出以上关联规则所对应的反向关联规则的相关信息，如下表所示：表2对应反向关联规则信息表反向关联规则支持度置信度平均购买量利润啤酒→尿布S1’C1’Q1’P1’香烟→啤酒S2’C2’Q2’P2’打火机→香烟S3’C3’Q3’P3’打火机→尿布S4’C4’Q4’P4’刮胡刀→尿布S5’C5’Q5’P5’香烟→刮胡刀S6’C6’Q6’P6’最终输出的关联规则中涉及的商品组合为尿布－啤酒、啤酒－香烟、香烟－打火机、尿布－打火机、尿布－刮胡刀、刮胡刀－香烟，从购物清单中可以进一步得出商品的平均购买数量和利润等信息。由公式Wi=Si×Ci×Qi×Pi+Si’×Ci’×Qi’×Pi’，可以求出两两商品间的相互“促销”系数，如表3所示：表3商品间“促销”系数表商品关系“促销”系数尿布－啤酒W1啤酒－香烟W2香烟－打火机W3尿布－打火机W4尿布－刮胡刀W5刮胡刀－香烟W6用下面的网络图表示五种商品间的“促销”关系：图中，两商品间有边相连，说明两种商品间有着较强的“促销”关系，边上的权值Wi表示边所连接的两商品间的“促销”系数，例如W1表示把啤酒和尿布摆放在一起的“促销”系数，W2表示把啤酒和香烟摆放在一起的“促销”系数。没有边相连则说明两商品间的“促销”关系不明显，两种商品的“促销”系数很小，甚至可以忽略。由于受货架空间的限制，一种商品最多只能与另外两种商品摆放在一起（左、右两边各摆放一种商品），这时就需要找出一种链状模式“商品1－商品2－商品3－商品4－商品5”下的商品摆放次序，使得各相邻商品的“促销”系数之和最大。根据最优化理论，只要在网络图中找出一条通路，使得这条通路能够贯穿各个节点，并且使得路径的权值之和（∑Wi）最大，那么这条通路依次通过的商品便形成了最佳的商品摆放次序。5.实例分析设顾客的一次购物活动为一次事务，购物清单中包含的商品为项，用关联规则挖掘算法分析某超市的购物清单。表4以少量数据示意超市购物清单的数据，其中A,B,C,D,E,F,G,H分别代表超市中销售的八种商品,括号里的数字代表客户购买商品的数量。表4购物清单示意数据事务ID事务的项目集T1A(2),B(2),E(1),F(2)T2B(2),D(1)T3B(1),C(1)T4A(1),B(2),D(1)T5A(2),C(1)T6B(1),C(1)T7A(4),C(1),H(2)T8A(1),B(1),C(1),E(1),G(1)T9A(2),B(1),C(1)使用Apriori算法，生成所有频繁项集，其中，规定最小事务支持度为20％，可以得到如下图所示的频繁项目集。每个列表中左边为项目集，右边为该项目集的支持数，最终产生的最大频繁集为{A,B,C}和{A,B,E}。由上述图2频繁项目集L1L2L3ABCDEF67622A,BA,CC,EB,CB,DB,E442422A,B,CA,B,E22图1“促销”关系网络图W2W6W5W4W3W1尿布啤酒刮胡刀香烟打火机频繁项目集合可以生成以下规则，并且在每条规则后面给出了相应的置信度：A→B67％A→C67％B→A57％B→C57％B→D29％B→E29％C→A67％C→E33％C→B67％D→B100％E→C100％E→B100％设最小置信度为65％，则最终输出的关联规则如表5所示：表5关联规则输出表关联规则置信度支持度A→B67％40％A→C67％4