一种带约束条件的购物篮分析方法
2016-02-23褚维伟张文斌陈小军黄哲学
褚维伟，张文斌，陈小军，黄哲学
(深圳大学，广东 深圳 518000)
一种带约束条件的购物篮分析方法
褚维伟，张文斌，陈小军，黄哲学
(深圳大学，广东 深圳 518000)
购物篮分析是数据挖掘技术在零售业的典型应用之一，旨在从零售记录中分析出顾客经常同时购买商品的组合，挖掘出购物篮中有价值的信息。如今购物篮分析在零售业已经有了广泛的应用，包括商品的促销、摆架、物流等。通过与零售客户的详细沟通与调研，发现传统购物篮分析并不考虑商品之间的层次关系，并且将支持度作为评估购物篮的唯一指标，在实际应用中存在缺陷。针对传统购物篮分析的不足，文中提出一种带有约束条件的购物篮分析，定义了一种新的购物篮评估方法。通过对真实数据进行一系列实验研究与分析，得到了更有实际意义的购物篮，并且在算法复杂度与运行时间方面比传统购物篮分析算法有了很大提升。
数据挖掘；购物篮分析；约束条件；频繁项集
1 概 述
在大数据时代，每时每刻都在产生着形形色色的数据。如何利用数据挖掘的知识与工具从这些海量的数据中挖掘出想要的信息，是最重要的研究内容之一。关联规则是数据中所蕴含的一类重要规律，对关联规则进行挖掘则是数据挖掘中的一项根本性任务，甚至可以说是数据库和数据挖掘领域中所发明并被广泛研究的最为重要的模型。关联规则挖掘的目标是在数据中找到所有的并发关系，也可以把这种关系称作关联。自从1993年Agrawal等第一次提出这个概念后，它已经引起了众多学者的注意，出现了许多算法、扩展以及应用[1]。
关联规则挖掘最经典的一个应用就是购物篮分析。通过发现顾客每次放入购物篮中的商品之间的联系，分析顾客的购买行为并辅助零售企业制定营销策略[2]。通常说的购物篮分析指的是通过购物篮中显示出来的交易信息来分析顾客的购买行为，顾客在购买商品的过程中通常会一次购买多件商品，从而使得这些商品之间具有很强的关联性[3-4]。因此，可以认为顾客的购买行为是一种整体行为，是否购买一件商品会影响到其他商品的购买，从而影响到每个购物篮的利润。所以，购物篮分析的目标就是找出重要而且有价值的购物篮[5]。目前关于购物篮分析的研究大多关注商品之间的关联度算法，而在实际应用方面，特别是在零售业中的应用却很少[6-7]。
在传统的购物篮分析中，得出的结果通常是一些常规商品的组合。这些组合的购物篮支持度很高，但是它们已经是被大家所认知的，对企业的价值和意义不大。此外，传统购物篮分析中一个很大的局限性在于它并不考虑商品的层次结构，通常只选择一个层次的商品来进行购物篮分析[8-9]。这样就导致得出的结果往往是同一小类产品的组合，例如不同品牌的饮料，这种购物篮满足不了企业的需求，妨碍了其在零售业中的实际应用[10]。
针对传统购物篮分析的局限性并结合企业实际应用中的需求，文中提出一种带有约束条件的购物篮分析方法。约束每个购物篮的组成中不能包含有相同父类的商品，并通过支持度和销售额的阈值来对候选购物篮进行评估、筛选。
2 传统购物篮分析
消费者日趋成熟的心理、越来越多样化的需求以及越来越激烈的市场竞争，使得充分分析并正确了解顾客已成为企业成功至关重要的因素[11]。虽然部分零售企业已经意识到这个问题并且做了很多这方面的工作，例如计算机辅助销售、顾客资料登记分析、人口统计分析等，但是很多时候效果并不明显。因此，购物篮分析的方法便应运而生，它提供了一种有效地研究顾客购买行为的方法[12]。购物篮分析作为关联规则挖掘在零售领域中的一个经典应用，通常所使用的技术也是关联规则挖掘的经典算法，文中以经典的Apriori算法为例对传统购物篮分析方法进行介绍。
2.1 基于Apriori算法的传统购物篮分析
Apriori算法是一种经典的关联规则频繁项集挖掘算法，其主要分两步进行：
(1)生成所有频繁项目集：一个频繁项目集是一个支持度高于最小支持度阈值的项集。
(2)从频繁项目集中生成所有可信关联规则：一个可信关联规则是置信度大于最小可信度阈值的规则。
把一个项集中项目的个数称为这个项集的基数，则k-项集表示一个基数是k的项集，k-频繁项集表示一个基数为k的频繁项目集[13-14]。
Apriori算法使用一种称为逐层搜索的迭代方法，即用k-项集来产生(k+1)-项集。首先找出1-项集的候选集，记为C1，然后根据最小支持度对C1进行剪枝得到频繁1-项集L1。再由L1连接产生2-项集的候选集C2，由C2产生频繁2-项集L2，循环下去，直到得到的Lk为空为止[15]。
Apriori频繁项集挖掘算法是根据支持度来进行剪枝的，其过程可以描述为：
设I=[i1,i2,…,im]是所有项目的集合，即所有商品类别的集合；D=[T1,T2,…,Tn]是所有事务的集合，即所有交易记录的集合。事务T可以表示为：T=[TID,
(1)
(2)
设P为支持度阈值，当且仅当PB≥P时，购物篮B才是有效的[16-19]。
2.2 传统购物篮分析的局限性
商场中出售的商品都有自己的类别，根据交易记录可以得到商品类别的层次结构。例如，图1是从由某超市的交易记录得出的商品层次结构树。从图中可以得到这些商品的层次信息，如白菜与胡萝卜都属于蔬菜类，雪碧与可乐都属于饮料类。
图1 商品层次结构树
在购物篮的项目组成方面，由于传统购物篮分析并不考虑商品的层次结构和所属关系，通常得出的购物篮很多是同一小类产品的组合，例如得到的购物篮B=[苹果，梨子，香蕉，葡萄，牛奶]。其中，[苹果，梨子，香蕉，葡萄]⊆[水果]，此种购物篮对企业的价值不大。同时，真正有价值的购物篮被大量重复、没有价值的购物篮所掩盖，这是影响购物篮分析在零售业应用的一个重要因素。
在购物篮选择方面，根据调研发现，企业对支持度的需求与传统购物篮分析的支持度计算方法有一定的区别。例如，购物篮B=[蔬菜，牛奶，豆腐，猪肉，水果]中含有5个品类，如果按5-项集计算支持度，可能不满足频繁集的条件，但这个购物篮对企业有用。如果放松支持度的条件，只要某笔交易含有这5个品类中的3个或者4个(用户可以自己定义)，就可以认为这笔交易记录符合购物篮。另一方面，传统的购物篮分析仅仅依据支持度来进行筛选，而支持度表征的是符合条件的交易数占总的交易数的比例，在实际应用中并不是衡量购物篮重要性的唯一属性。企业不仅希望得出的购物篮在数量上有较高的支持度，同时希望在价值上能够最大化。所以除了支持度之外，对购物篮进行评估还需增加购物篮的销售额。
3 带有约束条件的购物篮分析
基于上述传统购物篮的局限性，文中提出一种带有约束条件的购物篮分析方法。首先提出基于商品层次结构的购物篮生成算法，然后定义两种购物篮评估方法，最后对整个算法进行总结和分析。
3.1 基于约束条件的购物篮生成算法
3.1.1 约束条件定义
在购物篮分析中，通常会选择商品分类层次中的某一层。首先找出这一层商品对应的父类，形成如图1所示的商品层次结构树，并将其符号化表示。
给定一个具有商品层次分类信息的交易数据库D，商品的层次树可以用下面的方法获得：
商品的层次结构挖掘算法get_Tree()(算法1)如下所述：
输出：带有商品层次信息的项目集I。
步骤：
Tree[0]=(0，-1); //初始化根节点
point_of_insert=1;
for每笔交易记录T∈Ddo//按行读入数据库
point_of_insert++;
endfor
I=trans(Tree);//将Tree转化为I输出
3.1.2 候选购物篮生成算法
在上一节定义了基于商品层次结构的约束条件。这个约束条件保证了同一个购物篮中不会出现相同父类的商品，从而增加了购物篮的多样性，提升了购物篮的可用性。根据该条件，设计一种新的购物篮生成算法。对任意一对频繁(k-1)-项集，只有它们的前(k-2)项相同，并且(k-1)项不属于同一个父类时，才进行合并生成一个k项的购物篮。在这里，购物篮和频繁集是同一个概念，k-项集购物篮挖掘算法gen_Candidate()(算法2)如下所述：
输入：频繁(k-1)-项集Lk-1,商品层次结构树I；
输出：候选k-项集Ck。
步骤：
for任意两个A,B∈Lk-1do
令A={a1,a2,…,ak-1}，B={b1,b2,…,bk-1}
ifaj=bj(j=1,2,…,k-2) &&
H(ak-1)≠H(bk-1)then
endfor//其中函数H(x)为根据商品层次结构I找出x的父类
3.2 基于支持度和销售额的购物篮评估方法
在传统的购物篮分析中，支持度是检验购物篮的唯一指标，导致最后得到的分析结果通常都是一些最常见的商品组合，例如蔬菜、猪肉、豆腐等。这些商品虽然销售量很大，但是它们的销售额却不高，从而给企业带来的利润不高。因此文中在利用支持度对购物篮进行评估的基础上，加入了销售额的评估维度，从而保证得到的购物篮价值较高。设B为一个购物篮，则定义B的支持度为：
(3)
B的销售额占比为：
(4)
由式(3)和式(4)得出k-项集候选购物篮Ck中每个购物篮B对应的支持度PB和销售额RB，当且仅当PB和RB都大于对应的阈值时，购物篮B有效。购物篮评估算法basket_Assess()(算法3)如下所述：
输入：候选集Ck，支持度阈值min_sup，销售额阈值min_sale；
输出：频繁集Lk。
步骤：
for每个购物篮B∈Ckdo
ifPB≥min_sup &&RB≥min_salethen
Lk.Add(B) //将购物篮加入到Lk中
endfor
3.3 带约束条件的购物篮挖掘算法
综合上述商品层次树挖掘算法，约束条件和候选购物篮生成算法以及购物篮评估算法，可以得出带约束条件的购物篮挖掘算法。
(1)用算法1从交易数据库得出商品的层次结构树；
(2)用算法2生成满足约束条件的候选购物篮；
(3)根据支持度和销售额对候选购物篮进行筛选。
重复这个过程，直到候选购物篮个数为0或者购物篮数量满足给定值为止。带约束条件的购物篮挖掘算法(算法4)如下所述：
输入：交易数据库D，最小销售额阈值min_sale，最小支持度阈值min_sup，期望得到的购物篮中商品个数aim_k，期望购物篮中项目匹配个数w；
输出：aim_k项购物篮。
调用商品的层次结构挖掘算法得到商品层次结构I=get_Tree(D)
扫描D可得到C1
whileLk≠NULL &&k≤aim_kdo
Ck=gen_candidate(Lk-1,I)
k++;
end
文中提出的带约束条件的购物篮挖掘算法，一方面考虑了商品之间的层次结构和所属关系，在产生候选购物篮的过程中加入约束条件，增加了购物篮的多样性与实用性；另一方面在评估候选购物篮的过程中加入销售额的评估维度，并根据现实应用中零售企业的需求重新定义了支持度的计算方法，提高了购物篮对企业的价值和意义。
4 实验与结果分析
为了检验文中提出的带约束条件的购物篮挖掘方法在实际应用中的效果，采用真实数据对效果和性能进行验证。数据来源于大型连锁超市的实际交易记录数据，共有3 073 886条记录，532 484个交易号(TID)。观察数据可知，该超市的商品结构分为四层，从高到低依次是经营小类、商品中类、商品小类、单品。针对商品种类进行分析，使用上述数据集，对带有约束条件的购物篮挖掘算法进行了性能测试。实验使用的计算机配置：3.2GCPU和16G内存。
图2对比了不同长度的购物篮中有相同父类的购物篮占比随着支持度变化的趋势。实验采用Apriori算法来产生购物篮。
由图中可以看出，随着支持度增加，含有相同父类商品的购物篮占比明显增加，尤其是当购物篮长度较长时，这一比例始终维持在95%以上。在实际应用中，企业往往想要的是含有多个项目的购物篮，购物篮中商品的多样性尽可能最大化，而不是人们常识中已经熟悉的那些商品组合。传统购物篮分析得到的购物篮中有相同父类的购物篮的比例会很高，对企业的价值与意义不大，妨碍了购物篮分析在实际场景中的应用。新的有约束条件的购物篮分析可以有效避免这种问题。
图2 不同长度购物篮中含有相同父类
图3比较了文中提出的带有约束条件的购物篮分析算法和传统购物篮分析算法所产生的购物篮的销售额的分布情况。
图3 两种算法产生的购物篮销售额分布对比
可以看出，文中提出的算法产生的购物篮销售额明显高于传统购物篮分析算法的销售额。因此，新算法可以提升购物篮对用户的应用价值，找出了销售额较高、利润率较高的购物篮，而不再是传统购物篮分析中经常出现的蔬菜、豆腐等低利润的常规项。
Apriori算法的一个最大缺点就是产生大量的候选项集，对机器的内存大小要求很高，算法的运行时间较长。
图4对比了随着实验数据量的增加，传统的购物篮挖掘方法和文中提出的算法的运行时间变化情况。设支持度为0.1%，销售额占总销售额比例的阈值为1%，期望产生的购物篮中商品个数为5。
由图可看出，带有约束条件的购物篮分析算法运行时间明显小于基于Apriori算法的传统购物篮分析算法，大大减少了传统购物篮分析算法的时间复杂度。此外，当数据量增大时，基于Apriori算法的运行时间增加较快，而带有约束条件的购物篮分析算法的运行时间增加相对较缓。
图4 实验数据量增加时两种购物篮
图5为实验得到的购物篮分析结果示例。
图5 带有约束条件的购物篮分析实验结果示例
由图可以看出，购物篮的组成符合人们的生活常识。例如，第一个购物篮为家居生活用品，第二个购物篮为零食小吃，并且在同一个购物篮中的商品都是属于不同的父类，满足约束条件，增加了购物篮的多样性，方便企业进行交叉销售，提升购物篮的应用价值。
根据算法描述以及实验结果，可以总结出带有约束条件的购物篮分析算法的两个主要优点：
(1)约束条件和新的购物篮评估方法产生的购物篮应用价值更高。
(2)通过参数的设定，有效减少了传统购物篮分析方法的时间和空间复杂度。
5 结束语
文中详细描述了带有约束条件的购物篮挖掘方法，并提出了新的购物篮评估方法，采用实际数据进行了性能测试，并与传统的购物篮分析方法进行了对比。结果表明，带有约束条件的购物篮挖掘算法能有效避免同一购物篮中商品相似度过高和销售额较低的问题，产生企业需要的购物篮，新算法的时间和空间复杂度相对于传统购物篮分析都有显著下降。
下一步，计划结合多层次的关联规则来进行购物篮分析。对于很多的应用来说，由于数据分布的分散性，很难在数据最细节的层次上发现一些强关联规则。当引入概念层次后，就可以在较高的层次上进行挖掘。 然较高层次上得出的规则可能是更普遍的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。 所以购物篮分析应该提供这样一种在多个层次上进行分析的功能。
[1]GatziouraA,Sanchez-MarreM.Acase-basedrecommendationapproachformarketbasketdata[J].IEEEIntelligentSystems,2015,30(1):20-27.
[2]BuczakAL,GiffordCM.Fuzzyassociationruleminingforcommunitycrimepatterndiscovery[C]//ProcofISI-KDD2010.USA:ACM,2010.
[3]AguinisH,ForcumLE,JooH.Usingmarketbasketanalysisinmanagementresearch[J].JournalofManagement,2013,39(7):1799-1824.
[4]BasuchowdhuriP,ShekhawatMK.Analysisofproductpurchpatternsinaco-purchasenetwork[C]//Procoffourthinternationalconferenceofemergingapplicationsofinformationtechnology.[s.l.]:[s.n.],2014:355-360.
[5]GuptaN,YadavML.AnimplementationandanalysisofDSRusingmarketbasketanalysistoimprovethesalesofbusiness[C]//Procof5thinternationalconferenceofthenextgenerationinformationtechnologysummit.[s.l.]:[s.n.],2014:82-86.
[6]ZhouLe,LiJunjie,HuangZhexue.BalancedparallelFP-growthwithMapReduce[C]//ProcofIEEEyouthconferenceoninformationcomputingandtelecommunications.[s.l.]:IEEE,2010:243-246.
[7]KimHK,KimJK.Aproductnetworkanalysisforextendingthemarketbasketanalysis[J].ExpertSystemswithApplications,2012,39(8):7403-7410.
[8]BirtoloC,deChiaraD,LositoS,etal.SearchingoptimalproductbundlesbymeansofGA-basedengineandmarketbasketanalysis[C]//ProcofIFSAworldcongressandNAFIPSannualmeeting.Edmonton,AB:IEEE,2013:448-453.
[9]BhalodiyaD,PatelC.Anefficientwaytofindfrequentpatternwithdynamicprogrammingapproach[C]//ProcofNirmauniversityinternationalconferenceonengineering.[s.l.]:[s.n.],2014:1-5.
[10]CaviqueL.Next-itemdiscoveryinthemarketbasketanalysis[C]//Procofconferenceonartificialintelligence.[s.l.]:[s.n.],2005:198-199.
[11]TrnkaA.Marketbasketanalysiswithdataminingmethods[C]//Procofinternationalconferenceonnetworkingandinformationtechnology.[s.l.]:IEEE,2010:446-450.
[12]ChenaYL,TangK,ShenaRJ,etal.Marketbasketanalysisinamultiplestoreenvironment[J].DecisionSupportSystems,2005,40(2):339-354.
[13]SarkanMO,AkcakocaA,KucukakdagC,etal.AlarmcorrelationusingApriorialgorithm[C]//Procofsignalprocessingandcommunicationapplications.[s.l.]:[s.n.],2015:1602-1605.
[14]ZakiMJ.Scalablealgorithmsforassociationmining[J].IEEETransactionsonKnowledgeandDataEngineering,2000,12(3):372-390.
[15]HanJ,PeiH,YinY.Miningfrequentpatternswithoutcandidategeneration[C]//Procofconferenceonthemanagementofdata.NewYork,NY,USA:ACMPress,2000.
[16]AgrawalR,Imieli′nskiT,SwamiA.Miningassociationrulesbetweensetsofitemsinlargedatabases[C]//Proceedingsofthe1993ACMSIGMODinternationalconferenceonmanagementofdata.[s.l.]:ACMPress,1993:207-216.
[17]ZhangChun-Sheng,LiYan.Extensionoflocalassociationrulesminingalgorithmbasedonapriorialgorithm[C]//Procof5thIEEEinternationalconferenceonsoftwareengineeringandservicescience.[s.l.]:IEEE,2014:340-343.
[18]ChangRui,LiuZhiyi.Animprovedapriorialgorithm[C]//Procofinternationalconferenceonelectronicsandoptoelectronics.[s.l.]:[s.n.],2011:476-478.
[19]SaxenaP,PantB.Inter-transactionalpatterndiscoveryapplyingcomparativeaprioriandmodifiedreverseaprioriapproach[C]//ProcofIEEE8thinternationalconferenceonintelligentsystemsandcontrol.[s.l.]:IEEE,2014:300-305.
A Market Basket Analysis Method with Constraints
CHU Wei-wei，ZHANG Wen-bin，CHEN Xiao-jun，HUANG Zhe-xue
(Shenzhen University，Shenzhen 518000，China)
Basket analysis is a typical application of data mining technology in retail industry.It aims to analyze customers’ purchase patterns of goods from sales transactions and digs out the valuable information in the basket.Nowadays,basket analysis has been widely used in retail business,including sales promotion,pendulum shelf and logistics for goods.Through communication with retail customers,it is found that traditional basket analysis,which doesn’t consider the hierarchical relation between goods and takes the support degree as the unique index of evaluating basket,has some defects in real applications.In view of the deficiencies,a new basket analysis method with constraints is proposed and a new basket evaluation method is defined.Through a series of experiment research and analysis of real data,the basket with more practical significance is obtained,and the complexity and run time of proposed algorithm is better than the traditional one.
data mining;basket analysis;constraints;frequent itemsets
2015-11-06
2016-03-10
时间：2016-06-22
国家自然科学基金资助项目(61305059);深圳大学青年教师科研启动项目(201432)
褚维伟(1990-)，男，硕士，研究方向为数据挖掘；黄哲学，特聘教授，研究方向为数据挖掘。
http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0845.048.html
K921/927；TP393
A
1673-629X(2016)08-0069-06
10.3969/j.issn.1673-629X.2016.08.015
