基于关联规则挖掘的超市货物摆放次序优化方法研究李正欣，郭建胜（空军工程大学工程学院，陕西西安710038）摘要：使用关联规则挖掘算法分析超市购物清单时，会产生不止“啤酒→尿布”的单一关联规则，而将出现涉及多种商品的“纵横交错”的多条关联规则。针对这一实际问题，本文在使用关联规则挖掘的基础上，提出一种评估关联规则中两商品间相互“促销”关系的方法，实现优化超市货物摆放次序的目的。关键词：关联规则；关联规则挖掘；Apriori算法；关联规则评估中图法分类号：TP311文献标识码：AResearchonApproachforOptimizingCommodityPuttingOrderBasedonAssociationRulesMiningLiZheng-xin，Guo激an-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...