大型超市购物篮问题.docx
《大型超市购物篮问题.docx》由会员分享，可在线阅读，更多相关《大型超市购物篮问题.docx（29页珍藏版）》请在冰点文库上搜索。
大型超市购物篮问题
模式识别期中作业
--挖掘布尔关联规则频繁项集的算法——Apriori算法
一、问题重述
作为超市的经理，经常关心的问题是顾客的购物习惯。
他们想知道：
“什么商品组或集合顾客多半会在一次购物时同时购买？
”。
现在假设你们是某超市的市场分析员，已经掌握了该超市近一个星期的所有顾客购买物品的清单和相应商品的价格，需要你们给超市经理一个合理的“购物篮”分析报告，并提供一个促销计划的初步方案。
问题一：
附件1中的表格数据显示了该超市在一个星期内的4717个顾客对999种商品的购买记录，对数据进行分析，试建立一种数学模型，使该模型能定量表达超市中多种商品间的关联关系的密切程度。
问题二：
根据问题1建立的模型，通过一种快速有效的方法从附件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
促销系数
四、问题分析
本题是关于大型超市“购物篮”的分析问题，涉及到数据挖掘、关联规则等相关问题。
本题的三个问题是层层递进的关系，要求通过对商品购买数据的分析，找到关联程度较高且购买次数较高的商品，最后设计出合理的超市促销方案。
问题一，由于购物篮分析是关联规则挖掘的一个典型案例，因此我们采用一种最有影响的挖掘布尔关联规则
频繁项集的算法——Apriori算法
。
利用其基本思想，进行了商品两种之间的支持度和置信度计算，在定义最小支持度和最小置信度后，进行筛选得到关联规则集。
为定量地表达超市中多种商品间的关联关系的密切程度，本文引入一个关联密切系数进行衡量分别对12个组合求解平均置信度,进而得到该组的关联密切系数。
由此认为，关联密切系数越大的商品组合，其关联关系密切程度较高。
问题二，在得到商品两种关联数据的基础上，仅考虑商品支持度的大小，求得在一定最小支持度下被频繁地同时购买的商品组合。
同时为使商品数量尽量多，我们在两种组合的情况下延伸至三种组合，四种组合……以此得到尽可能多的商品被频繁同时购买的信息，尽量靠近最频繁被同时购买且商品数量越多的双重目标。
问题三，在结合商品利润的条件下，考虑两种组合中各商品的利润、支持度和置信度，分别计算出三者的乘积再求和，记为促销系数H，并以此作为衡量此组合商品是否进行促销的标准。
当结果较高时，我们就采取就近摆放、打折促销、消费送礼等捆绑销售方式式得到一种促销方案，在方便顾客的购买的同时，增加消费者对该超市的有好感和信任度，最终使得超市的效益进一步增大。
五、模型的建立和求解
模型一：
基于Apriori算法的关联规则挖掘
模型
1.模型的准备
设:
I={i1,i2......,im}是所有项目的集合.D是所有事务的集合（即数据库）,每个事务T是一些项目的集合,T包含在D中,每个事务可以用唯一的标识符TID来标识.设X为某些项目的集合,如果X包含在T中,则称事务T包含X,关联规则则表示为如下形式（X包含在T）=>（Y包含在T）的蕴涵式,这里X包含在I中,Y包含在I中,并且X∧Y=Φ.其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现（为简单化,将（X包含在T）=>（Y包含在T）表示为X=>Y,这里,‘=>’称为‘关联’操作，X称为关联规则的先决条件,Y称为关联规则的结果）.
事务数据库D中的规则X=>Y是由支持度s（support）和置信度c（confidence）约束,置信度表示规则的强度,支持度表示在规则中出现的频度。
数据项集X的支持度s（X）是D中包含X的事务数量与D的总事务数量之比,但为下文便于叙述,数据项集X的支持度是用数据库D中包含X的数量来表示;
规则X=>Y的支持度s定义为:
在D中包含X∪Y的事务所占比例为s%,表示同时包含X和Y的事务数量与D的总事务量之比。
用该项集出现的次数除以TID总数即可得到，用如下公式表示：
Support（X）=Count（X）/Count（TID）
规则X=>Y的置信度c定义为:
在D中,c%的事务包含X的同时也包含Y,表示D中包含X的事务中有多大可能性包含Y.依据所求的频繁项集，及所求得的支持度，运用如下公式求解：
Confidence（X=>Y）=Support（X∪Y）/Support（X）
最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性.最小置信度阈值mincontinence表示规则的最低可靠性.如果数据项集X满足X.support>=minsupport,则X是大数据项集.一般由用户给定最小置信度阈值和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则,反之称为弱关联规则.发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则.
基于上述概念，我们可以很容易得到一些基本结论:
（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的K-1.维子项集的个数小于K，则存在XK的K-1维子项集不是频繁数据项集，由结论
（2）知K维数据项集本身也不是高频繁数据项集。
2、模型的建立
（1）求关联规则集
第一步：
从事务数据库D中找出所有支持度不小于指定的最小支持度阈值的频繁项集。
第二步：
使用频繁项集产生所期望的关联规则，产生关联规则的基本原则是其置信度不小于指定的最小置信度阈值。
第一步的任务是迅速高效地找出D中全部的频繁项集，这是关联规则挖掘的核心问题，是衡量关联规则挖掘算法的标准。
对此，我们运用Matlab进行编程得出计算结果。
第二步的求解比较容易和直接，先分别计算出不小于最小支持度的商品组合对应的置信度，降序后进行筛选。
最后只留下支持度和置信度都较高的商品组合。
此建模过程可以表示为：
图1关联规则挖掘模型示意图
（2）关联关系的密切程度表示
对商品组合数据的挖掘结果进行整理，得到关联规则表格，再利用表格中各商品组合对应的支持度和平均置信度表示组合的关联关系。
例如：
在组合i中，有两个编号分别为
、
的两个商品，其支持度为
，平均置信度为
，则该组合的关联关系可以表示为（
）.
为定量表达超市中多种商品间的关联关系的密切程度，我们引入一个关联密切系数
来衡量，我们认为当支持度和置信度分别大于距离最低支持度和最低置信度时，其距离越远，关联程度越高，于是得到其公式为：
其中，
为组合i的支持度，
为该组合的平均置信度,
和
分别为该类组合的最小支持度和最小置信度。
用图表示为：
图2关联密切系数示意图
将12组商品组合的支持度和平均置信度带入关联密切系数的公式中进行计算，将所得数据列表降序排列，关联系数越大的商品组合的关联关系的密切程度越大。
3、模型的求解
对于问题1：
（1）将最小支持度设定为5%，从4717个原始数据项中得到个数为17的频繁项集。
按支持度降序排列后，依次编号，整理得到表1：
表1两种组合频繁项集表
组合i
编号A
编号B
支持度
1
368
529
0.070792709
2
368
829
0.06634167
3
217
368
0.061678677
4
368
489
0.061678677
5
368
682
0.061254769
6
368
419
0.057015685
7
368
937
0.055532005
8
368
692
0.055320051
9
368
510
0.055108097
10
368
914
0.054896142
11
529
692
0.054472234
12
529
829
0.054048326
13
368
720
0.0527766
14
438
529
0.051716829
15
217
529
0.051292921
16
692
829
0.051080967
17
419
829
0.05023315
对由上表得到的数据，分别计算各个组合相互的置信度，并将最小置信度设定为20%，剔除部分数据后得到关联规则集。
再对数据列表的s（A=>B）进行降序处理，重新编号后得到表2：
表2关联规则表
组合i
编号A
编号B
支持度s
置信度c（A=>B）
置信度c（B=>A）
1
217
368
0.061678677
0.311229947
0.217488789
2
692
829
0.051080967
0.296068796
0.218495014
3
438
529
0.051716829
0.286721504
0.22405877
4
217
529
0.051292921
0.258823529
0.222222222
5
419
829
0.05023315
0.251325557
0.21486854
6
368
529
0.070792709
0.249626308
0.306703398
7
529
692
0.054472234
0.235996327
0.315724816
8
529
829
0.054048326
0.23415978
0.23118767
9
368
829
0.06634167
0.233931241
0.283771532
10
368
489
0.061678677
0.217488789
0.328442438
11
368
682
0.061254769
0.215994021
0.352869353
12
368
419
0.057015685
0.201046338
0.285259809
最后留下的12个支持度和置信度都较高的商品组合即为关联规则集。
（3）为定量地表达超市中多种商品间的关联关系的密切程度，分别对12个组合求解平均置信度,进而得到该组的关联密切系数。
如表3所示：
表3关联密切评定表
组合i
编号A
编号B
支持度
平均置信度
关联密切系数
1
217
368
0.061678677
0.264359368
0.065410395
2
692
829
0.051080967
0.257281905
0.057292103
3
438
529
0.051716829
0.255390137
0.055416737
4
217
529
0.051292921
0.240522876
0.040543497
5
419
829
0.05023315
0.233097049
0.03309787
6
368
529
0.070792709
0.278164853
0.080883131
7
529
692
0.054472234
0.275860571
0.075992284
8
529
829
0.054048326
0.232673725
0.032923567
9
368
829
0.06634167
0.258851386
0.061078113
10
368
489
0.061678677
0.272965614
0.073894332
11
368
682
0.061254769
0.284431687
0.085178516
12
368
419
0.057015685
0.243153073
0.043719648
对于问题2：
本题要求最频繁被同时购买、商品数量越多越好的商品组合。
由支持度的定义可知，某商品组合的支持度越高，表示该组合越频繁被同时购买。
我们采用问题一中的数据，将所筛选出的商品种类选出，与上述两种商品的组合进行匹配，去掉重复项，得到三种商品组合，挑选出满足支持度support的组合。
同样进行满足支持度的四种商品、五种商品、六种商品的选择……依次循环直到没有符合最低支持度的组合程序结束。
以此进行matlab编程，见附录。
（1）我们设定support为2.12%，得到1391种组合，在问题一中我们列出了其中一些组合。
（2）对于三种商品组合符合support为2.12%的组合数为40个，由于版面限制，以下列出频繁项集为最高的15种组合：
表4三种组合频繁项集表
组合i
编号A
编号B
编号C
次数
支持度
1
368
489
682
124
0.026287895
2
413
538
956
122
0.025863897
3
424
572
797
116
0.024591902
4
413
538
797
115
0.024379902
5
413
572
956
114
0.024167903
6
413
797
956
114
0.024167903
7
538
797
956
114
0.024167903
8
413
424
956
113
0.023955904
9
413
826
956
112
0.023743905
10
424
572
956
112
0.023743905
11
538
797
826
111
0.023531906
12
538
826
956
111
0.023531906
13
572
797
956
111
0.023531906
14
797
826
956
111
0.023531906
15
413
572
797
110
0.023319907
（3）四种商品组合有35种，以下频繁项集为前15种：
表5四种组合频繁项集表
组合i
编号A
编号B
编号C
编号D
次数
支持度
1
413
424
572
956
107
0.022683909
2
413
572
797
956
107
0.022683909
3
424
572
797
956
107
0.022683909
4
413
424
797
956
106
0.022471910
5
413
538
797
826
106
0.022471910
6
413
538
797
956
106
0.022471910
7
413
797
826
956
106
0.022471910
8
413
424
538
797
105
0.022259911
9
413
424
572
797
105
0.022259911
10
413
424
797
826
105
0.022259911
11
413
538
572
956
105
0.022259911
12
413
538
826
956
105
0.022259911
13
413
572
826
956
105
0.022259911
14
424
538
572
797
105
0.022259911
15
538
797
826
956
105
0.022259911
（5）由编程得出的结果中，五种商品组合的结果只有一个。
编号分别为413、424、538、572、797，重复次数为102，支持度为2.12%。
六种商品组合没有符合的结果。
从五种组合的数据来看，我们有理由认为表5中所列出的四种商品组合和编号分别为413、424、538、572、797的五种组合即为所求的最频繁被同时购买、商品数量多的商品组合。
在实际应用中，对于不同的超市，其要求的支持度support不同，可自行设置。
模型二：
效益最大化模型
1、模型的建立
为使超市的效益尽可能增大，必须同时考虑两个因素：
（1）频繁被同时购买的商品组合；
（2）对应商品组合的利润是否最高。
由第一个基于Apriori算法的关联规则挖掘模型可以得到，频繁被同时购买的两种商品组合数据。
为衡量这些组合的效益，本文引入了促销系数：
其中，
为组合i中商品的利润之和。
对于问题3：
第一步：
利益最大化模型
只考虑两种组合的情形，分别计算表1中17个组合的促销系数，并将得到的结果进行降序排列，得到表6：
表6两种组合促销系数表
组合
编号A
编号B
支持度
置信度A=>B
置信度B=>A
利润和
促销系数H
1
368
529
0.070792709
0.249626308
0.306703398
575.95
22.6832649
2
529
692
0.054472234
0.235996327
0.315724816
557.56
16.7566201
3
368
829
0.06634167
0.233931241
0.283771532
479.64
16.47336364
4
368
419
0.057015685
0.201046338
0.285259809
587.93
16.30158102
5
438
529
0.051716829
0.286721504
0.22405877
559.82
14.78816934
6
692
829
0.051080967
0.296068796
0.218495014
461.25
12.12368734
7
529
829
0.054048326
0.23415978
0.23118767
473.77
11.91590804
8
419
829
0.05023315
0.251325557
0.21486854
485.75
11.37548683
9
368
682
0.061254769
0.215994021
0.352869353
315.259
10.9853873
10
368
489
0.061678677
0.217488789
0.328442438
296.1188
9.971005752
11
217
368
0.061678677
0.311229947
0.217488789
296.1188
9.656633102
12
217
529
0.051292921
0.258823529
0.222222222
290.2488
7.161669045
由上表可以得出，编号为529的商品可以和368,692,428,829,217摆放在一起，368可以和529,892，419,682,489,217摆放在一起。
为了更好的说明商品的摆放顺序，作图2，其中方框中的数字表示商品编码，直线上的数字表示该直线两端商品组合的促销系数。
图2促销关系网络示意图
由图2可直观看出，编号为368的商品应优先考虑和529摆放一起，再考虑和829一起。
编号为529的商品再和692一起……在实际情况中，即可操作为，将829,368,529,692放在同一货架上，其他的放在临近货架，并根据实际情况进行调整。
第二步：
打折促销
由第一步可以获得利润高又频繁被同时购买的商品组合，为方便顾客选购同时提高超市的利润值，我们决定将这些商品组合摆放在相同或相近货架上，采取“捆绑”销售的理念，进行打折促销。
首先找出符合以下要求的组合：
若一个商品组合中有一个利润较大，我们可以对此商品进行打折，其他商品价格不变。
经过多次进行市场实践调查，得到当打折为f（i）的时候可以得到最大的利润
，那么f（i）就是我们需要的打折数据。
以表格X中组合（X,Y）为例，在促销过程中，我们可以对利润较高的编号为X商品打折f（i），保持Y商品价格不变。
第三步：
提高最低消费
为降低部分顾客只购买打折商品的发生几率，超市可以先统计出该购物群体绝大多数的消费水平，将其上调部分后，配合同时期的打折活动推出购满上调后金额赠送小礼品的活动。
例如该购物群体每次消费在60~80元之间占绝大多数，基于此信息采取购满88元返券、满88元加1元赠送抽纸一包的促销措施来提高销售量；基于大多数人贪小便宜的消费心理，很多消费者会选择购满88元。
这些措施不仅使得顾客的交叉消费大为提高，还能提升顾客对超市的满意度，增加再次光临选购的几率。
七、模型评价
对于问题一的数据挖掘问题，通过分析每个数据，从大量数据中寻找其规律的技术，我们采用Apriori算法的思想，经过一定程度的改进，进行了运用。
优点：
（1）作为一个迭代算法，使用Apriori性质来生成候选项集的方法，得到所有大于等于最小支持度的频繁项目集，大大压缩了频繁集的大小，取得了很好的性能。
最终得到的程序解决所给问题只需40s，而且可以表示出满足条件的商品个数及其种类。
有助于超市经理进行“购物篮”分析并做出相应的促销方案。
（2）Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，改进后的Apriori算法更适用于适合事务数据库的关联规则挖掘。
（3）该算法结构简单,易于理解,没有复杂的推导。
缺点：
（1）对数据库的扫描次数过多。
该算法需要在每进行一次迭代的时候扫描一次数据库,一般挖掘出的最大频繁项集的长度为N时,需要扫描N次数据库,而在实际应用中经常需要挖掘很长的模式,多次扫描数据库带来巨大开销，且效率较低。
（2）Apriori算法可能产生大量的侯选项集。
Apriori算法在迭代过程中要在内存中产生,处理和保存候选频繁项集,这个数量有时候是非常巨大的,导致算法在广度和深度上的适应性很差。
（3）程序不利于非编程人员的直接调用和使用。
改进：
可以将程序进行打包，增加其可视化的方面，利于非编程人员的直接使用
对于问题一中关联密切程度系数公式的引入，我们认为它的优点是能够反映支持度越高、置信度越高，则关联密切程度越高。
缺点是该公式缺乏一些实践检验。
对于问题三的促销方案，我们引入的促销系数综合权衡了置信度、支
升级会员 