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

基于关联规则挖掘的超市货物摆放次序优化方法研究
李正欣，郭建胜
（空军工程大学工程学院，陕西 西安 710038）

摘 要：使用关联规则挖掘算法分析超市购物清单时，会产生不止“啤酒→尿布”的单一关联规则，而将出现涉及多种商品的“纵横交错”的多条关联规则。针对这一实际问题，本文在使用关联规则挖掘的基础上，提出一种评估关联规则中两商品间相互“促销”关系的方法，实现优化超市货物摆放次序的目的。
关键词：关联规则；关联规则挖掘；Apriori算法；关联规则评估
中图法分类号：TP311 文献标识码：A

Research on Approach for Optimizing Commodity Putting Order Based on Association Rules Mining
Li Zheng-xin，Guo Jian-sheng
(The Air Force Engineering Institute，Xi’an Shanxi 710038)
Abstract: When using apriori algorithm to analysis the market listings, many complicated association rules may be getted, which are different from the single “beer and diaper” association rule; So based on association rules mining, a method of evaluating the association rule of two items is provided to optimize the commodity putting order of markets.
Key words: Association Rule； Association Rules Mining； Apriori Algorithm； Evaluation of Association Rules

1.引言
全球最大的零售商沃尔玛(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），这些项集称为频繁集(frequent itemset)；2、使用第一步找到的频繁集产生期望的规则。为了生成所有频繁集，使用了递推的方法，生成所有频繁项集的Apriori算法流程如下所示：
L1 = {large1-itemsets};
For (k=2; Lk-1≤n; k++) do
Begin
Ck = apriori_gen(Lk-1); //新的候选集
For all transactions t∈D do
Begin
Ct = subset(Ck,t); //事务t中包含的候选集
For all candidates c∈Ct do
c.count++;
End
Lk = { c∈Ck| c.count≥min_sup }
End
Answer = ∪kLk;

Procedure apriori_gen( Lk-1,min_sup )
Ck = NULL
For each itemset li∈Lk-1
For each itemset lj∈Lk-1
If (li[1]=lj[1])∧(li[2]=lj[2]) ∧…∧(li[k-2]=lj[k-2])∧(li[k-1]=lj[k-1])≥min_sup then
Begin
c = li join lj
if has_infrequent_subset ( c,Lk-1)
delete c;
else add c to Ck;
End
Return Ck;

Procedure has_infrequent_subset( c,Lk-1)
For each (k-1)-subset s of c
If sLk-1 then
Return TURE;
Return FALSE;
首先产生频繁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 关联规则信息表
关联规则
支持度
置信度
平均购买量
利润
尿布→啤酒
S1
C1
Q1
P1
啤酒→香烟
S2
C2
Q2
P2
香烟→打火机
S3
C3
Q3
P3
尿布→打火机
S4
C4
Q4
P4
尿布→刮胡刀
S5
C5
Q5
P5
刮胡刀→香烟
S6
C6
Q6
P6
再找出以上关联规则所对应的反向关联规则的相关信息，如下表所示：
表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
用下面的网络图表示五种商品间的“促销”关系：
图1 “促销”关系网络图
W2
W6
W5
W4
W3
W1
尿布
啤酒
刮胡刀
香烟
打火机

图中，两商品间有边相连，说明两种商品间有着较强的“促销”关系，边上的权值Wi表示边所连接的两商品间的“促销”系数，例如W1表示把啤酒和尿布摆放在一起的“促销”系数，W2表示把啤酒和香烟摆放在一起的“促销”系数。没有边相连则说明两商品间的“促销”关系不明显，两种商品的“促销”系数很小，甚至可以忽略。由于受货架空间的限制，一种商品最多只能与另外两种商品摆放在一起（左、右两边各摆放一种商品），这时就需要找出一种链状模式“商品1－商品2－商品3－商品4－商品5”下的商品摆放次序，使得各相邻商品的“促销”系数之和最大。根据最优化理论，只要在网络图中找出一条通路，使得这条通路能够贯穿各个节点，并且使得路径的权值之和（∑Wi）最大，那么这条通路依次通过的商品便形成了最佳的商品摆放次序。
5.实例分析
设顾客的一次购物活动为一次事务，购物清单中包含的商品为项，用关联规则挖掘算法分析某超市的购物清单。表4以少量数据示意超市购物清单的数据，其中A,B,C,D,E,F,G,H分别代表超市中销售的八种商品,括号里的数字代表客户购买商品的数量。
表4 购物清单示意数据
事务ID
事务的项目集
T1
A(2),B(2),E(1),F(2)
T2
B(2),D(1)
T3
B(1),C(1)
T4
A(1),B(2),D(1)
T5
A(2),C(1)
T6
B(1),C(1)
T7
A(4),C(1),H(2)
T8
A(1),B(1),C(1),E(1),G(1)
T9
A(2),B(1),C(1)
使用Apriori算法，生成所有频繁项集，其中，规定最小事务支持度为20％，可以得到如下图所示的频繁项目集。
图2 频繁项目集
L1
L2
L3
A
B
C
D
E
F
6
7
6
2
2
A,B
A,C
C,E
B,C
B,D
B,E

4
4
2
4
2
2
A,B,C
A,B,E

2
2

每个列表中左边为项目集，右边为该项目集的支持数，最终产生的最大频繁集为{A,B,C}和{A,B,E}。由上述频繁项目集合可以生成以下规则，并且在每条规则后面给出了相应的置信度：
A→B 67％ A→C 67％
B→A 57％ B→C 57％
B→D 29％ B→E 29％
C→A 67％ C→E 33％
C→B 67％ D→B 100％
E→C 100％ E→B 100％
设最小置信度为65％，则最终输出的关联规则如表5所示：
表5 关联规则输出表
关联规则
置信度
支持度
A→B
67％
40％
A→C
67％
40％
C→A
67％
40％
C→B
67％
40％
D→B
100％
20％
E→C
100％
20％
E→B
100％
20％
最终输出的关联规则中涉及的商品组合为A－B、A－C、B－C、B－D、B－E、C－E。从购物清单中可以进一步得出商品的平均购买数量和利润等信息：
表6关联规则信息表示例
关联规则
支持度
置信度
平均购买量
利润
A→B
40％
67％
1.4
1.2
A→C
40％
67％
1
0.3
C→B
40％
67％
1.4
1.2
D→B
20％
100％
1.4
1.2
E→C
20％
100％
1
0.3
E→B
20％
100％
1.4
1.2
再挖掘出以上关联规则所对应的反向关联规则的相关信息：
表7对应反向关联规则信息表示例
反向关联规则
支持度
置信度
平均购买量
利润
B→A
40％
57％
2
0.8
C→A
40％
67％
2
0.8
B→C
40％
57％
1
0.3
B→D
20％
29％
1
0.2
C→E
20％
33％
1
2
B→E
20％
29％
1
2
由公式Wi= Si×Ci×Qi×Pi+ Si’×Ci’×Qi’×Pi’，可以求出两两商品间的“促销”系数，如表8所示：
表8 商品间“促销”系数表示例
WAB
WAC
WBC
WBD
WBE
WCE
0.81504
0.5092
0.51864
0.3476
0.4520
0.1920
根据上表所示，可知商品A和B相互间的“促销”作用最明显。再用网络图表示出各商品间的“促销”关系，每条边上的数字代表这条边所连接的两商品间的“促销”系数：
图3 “促销”关系网络图示例
根据最优化理论，在网络图上可以找到两条通路把所有的商品依次连接起来：1、D—B—A—C—E，∑W=1.86384；2、D—B—E—C—A，∑W=1.5008。从中选择∑W较大的通路，所以超市中A、B、C、D、E五种热销商品的最佳摆放次序为：D—B—A—C—E。
6.结束语
优化超市货物摆放次序是一项复杂的系统工程，它涉及因素繁多，难以进行直接的量化评估。本文在关联规则挖掘算法的基础上，提出一种评估两种商品间相互“促销”关系的方法，并根据最优化理论，定性分析同定量分析相结合，为优化超市货物摆放次序提供了一种途径。

参考文献

［1］冯玉才,吕建芳. 一个销售模型的关联规则挖掘研究［J］. 计算机工程与应用, 2005, 17: 183-185.
［2］陈文伟. 数据仓库与数据挖掘 ［M］. 北京: 人民邮电出版社, 2004. 143－151.
［3］康晓东. 基于数据仓库的数据挖掘技术 ［M］. 北京: 机械工业出版社, 2004. 148－156.
［4］Mehmed Kantardzic. 数据挖掘 ［M］. 闪四清译. 北京: 清华大学出版社, 2003. 144－169.
［5］钱颂迪. 运筹学（第二版） ［M］. 北京: 清华大学出版社, 1990. 254－283.
作者简介:
李正欣(1982－),男,河南省信阳市人, 在读硕士研究生,主要研究领域为指挥自动化、管理信息系统；郭建胜(1965－),男,在读博士研究生,教授,主要研究领域为指挥自动化、管理信息系统。