基于Apriori算法的超市商品销售数据的关联规则分析

基于Apriori算法的超市商品销售数据的关联规则分析郑印（华中师范大学计算机学院，湖北武汉430079）AprioriassociationrulesalgorithmbasedsupermarketmerchandisesalesdataZhengyin(ComputerCollege,CentralChinaNormalUniversity,Hubei430079,China)摘要：Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。尤其是在超市零售业中的应用更是广泛，通过对销售数据记录的分析，挖掘出商品的关联规则，有利于提高超市零售业的销售利率，增强其市场竞争力。关键词：关联规则；Apriori算法；销售利率Abstract:Apriorialgorithmiswidelyusedinbusinessandprice’sanalysisofconsumermarket,itcanquicklydeterminetheimpactofprice’srelationshipsbetweenthevariousproducts.Especiallyusinginsupermarketretailingisevenmorewidespread,throughtheanalysisofsalesdataofrecord,theassociationruleminingcommodities,helptoimprovethesupermarketretailsalesrates,andenhancetheirmarketcompetitiveness.Keywords:Associationrules;Apriorialgorithm;salesrate1.研究背景超市零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋势，对于零售商制订销售策略是至关重要的。通过关联规则的挖掘，分析客户对商品的需求状况，发现顾客的潜在需求特征，有目的性的开展广告和销售业务。通过对顾客的忠诚度分析，相应调整商品的价格和类型，改进销售服务，有利于保持现有客户，寻找潜在的客户，扩大销售的范围和规模，从而增加销售量。通过分析销售的数据记录，目前主要应用于销售预测、库存需求、零售点选择和价格分析，分析客户的购买行为和习惯，分析商场的销售商品的构成，使商品的选择与搭配更为科学。因此，对超市经营信息、数据的整理、挖掘，从中得出对经营有用的信息，增强超市的竞争能力，已经成为各家超市企业面临的一个紧迫课题，同时，Apriori算法作为关联规则挖掘的重要算法，也被各个企业所运用。2.关联规则的基本概念设I={i1，i2，…，im}是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合。每一个事务有一个标识符，称作TID。设A是一个项集，事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，并且A∩B=Φ。关联分析中还包括两个重要的参数，支持度(min_sup)和置信度(min_conf)。具体定义如下：支持度:support(AB)=P(A∪B),即A和B这两个项集在事务集D中同时出现的概率。置信度:confidence(AB)=P(B|A)，即在出现项集A的事务集D中，项集B也同时出现的概率。同时满足最小支持度(min_sup)和最小置信度(min_conf)的规则称作强规则。项的集合称为项集(itemset)，包含k个项的项集称为k－项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。如果项集的出现频率大于或等于最小支持度，则称为频繁项集频繁k－项集的集合通常记作Lk。3.Apriori算法分析关联规则(AssociationRules)的挖掘是数据挖掘中的一个重要问题。我们采用的是相关性分析的方法，采用的是Apriori算法。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。1）连接步为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li，li[1]li[2]……….li[k-1]。将Lk-1与自身连接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]l2[k-1])，那认为l1和l2是可连接。连接l1和l2产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。2）剪枝步CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。4.数据关联规则挖掘的实现过程a)数据采集数据是数据挖掘的前提，数据采集是获取数据的方法与实现。可以对数据库中的数据进行抽样筛选得到与数据挖掘所处理的相关数据。也可以利用视图对数据库中的数据进行筛选。首先从数据中抽取同一购物单上的物品组成事务，用于关联挖掘如表1-1物品一物品二物品三物品四物品五物品六手套科普牙膏电视机电视机洗衣机T恤牙刷牛奶.............................表1-1关联事务表b）数据预处理在数据采集的基础上，处理数据，使数据易于进行挖掘处理。主要进行了下面几个步骤：1）将商品信息表、销售记录表合并到一起（即数据集成），返回销售关联信息。2）去除不用的数据字段，比如，销售日期、商品数量等等对数据挖掘没有作用，在预处理阶段就把这些字段排除。c）数据挖掘Apriori算法是一种最有影响的挖掘布尔型关联规则频繁项目集的算法。算法思想的是基于先验知识，Apriori算法所采用的是逐层迭代搜索方法，K-项目集用于搜索（K+1）-项目集，首先，寻找出频繁1-项目集的集合，该集合记作L1,L1用来寻找频繁2-项目集的集合L2,再用L2寻找出L3，以此类推，直到不能找到频繁M-项目集为止。每次找出一个Lk,就需要扫描数据库一次，即如下所述：寻找频繁项目集算法的基本思路是Apriori的性质,即频繁项目的所有非空子集都必须是频繁的。利用这个性质在搜索频繁项目集时，非常有利于压缩搜索空间，从而提高频繁项目集逐层搜索的效率。在第一遍扫描中，计算单个项目的支持度，确定哪些项目是频繁项目，即它们需具有最小支持度。在后来的扫描中，均将前一次扫描得到的频繁项目作为基础项目，利用这个基础项目产生出新的频繁项目集，这样的频繁项目集称作候选项目集（CandidateItemsets），并且在扫描数据的过程中计算这些候选项目集的实际支持度计数。扫描结束后，确定哪些候选项目集才是真正的频繁项目，然后将是频繁项目的这些候选项目集作为下一次扫描用的基础项目。重复此过程直到没有新的频繁项目集产生为止。一般地，算法要对数据库进行多次扫描。由于Apriori算法要求项目集的所有非空子集都必须是频繁的，因此在数据库中D的事务中寻找频繁项目集时，需要进行连接和剪枝，才能挖掘强关联规则。如果在数据库D中的事务找出所有的频繁项目集以后，由他们产生满足最小支持度和最小的可信度的强关联规则就很容易了，可用如下式的条件概率计算出可信度，Confidence(AB)=P(A|B)=support_count(AB)/support_count(A)其中support_count(AB)是包含项目集AB的事务数，support_count(A)是包含项目集A的事务数。根据该式，关联规则的可以产生如下：1）对于每个频繁项目集L,产生L的所有非空子集。2）对于L的所有非空子集S，如果support_count(L)/support_count(S)min_confidence,则输出关联规则“SL-S”,其中min_confidence是最小可信度阈值。由于规则由频繁项目集产生，每个规则都满足大于最小支持度，频繁项目与他们的支持度可预先存放在散列表中，以加快访问速度。让我们以上例子说明关联规则的挖掘，在该事务数据库中，假定数据包含频繁项目集L={I1,I2,I5}，可以由L产生的关联规则，L的非空子集由{I1,I2}，{I1,I5}，{I2,I5}，{I1}，{I2}和{I5}，其支持度分别是4，2，2，6，7，2。得出的关联规则如下：（每个都列出其可信度）I1I2I5，Confidence=2/4=50I1I5I2，Confidence=2/2=100I2I5I1，Confidence=2/2=100I1I2I5，Confidence=2/6=33I2I1I5，Confidence=2/7=29I5I1I2，Confidence=2/2=100如果最小的可信度阈值是70，则只有第2、3和最后一个规则可以输出，因为这些产生的是强规则。d）Apriori算法实现伪代码K=1Fk={i|i∈I∧σ({i})≥N×minsup}{发现所有的频繁1－项集}RepeatK=k+1Ck=apriori－gen(Fk－1){产生候选项集}For每个事务t∈TdoCt=subset(Ck，t){识别属于t的所有候选}For(每个候选项集c∈Ctdoσ(c)=σ(c)+1{支持度计数增值}EndforEndforFk={c|c∈Ck∧σ(c)≥N×minsup}{提取频繁k－项集}UntilFk=nullResult=∪Fke）挖掘结果支持度阈值用于筛选出商品的频繁项集集合，从而算出支持度；信任度阈值用于筛选出符合要求的商品集合之间信任度集合。通过支持度阈值和信任度阈值用户可以根据实际需要来决定筛选的程度。同时购买商品的数据：设置支持度为：2信任度为：0.7则----------------频繁集----------------牛奶;衣服;:3牛肉;鸡肉;:3奶酪;鸡肉;:2牛奶;衣服;鸡肉;:3奶酪;:4衣服;鸡肉;:3奶酪;牛肉;:3牛奶;牛肉;:2牛肉;:4鸡肉;:5奶酪;牛肉;鸡肉;:2牛奶;鸡肉;:4牛奶;:4牛奶;牛肉;鸡肉;:2衣服;:3----------------关联规则----------------牛奶;衣服;-鸡肉;:1.0牛奶;-鸡肉;:1.0衣服;-鸡肉;:1.0牛肉;-奶酪;:0.75牛奶;-衣服;:0.75牛奶;-衣服;鸡肉;:0.75牛奶;牛肉;-鸡肉;:1.0奶酪;鸡肉;-牛肉;:1.0衣服;-牛奶;:1.0牛肉;-鸡肉;:0.75牛奶;鸡肉;-衣服;:0.75鸡肉;-牛奶;:0.8衣服;鸡肉;-牛奶;:1.0衣服;-牛奶;鸡肉;:1.0奶酪;-牛肉;:0.75f）结果分析从上面我们可以看到事务集中的所有频繁项集，如牛奶;衣服;:3；牛肉;鸡肉;:3；奶酪;鸡肉;:2；牛奶;衣服;鸡肉;:3等