基于Apriori算法的超市商品销售数据的关联规则分析
基于Apriori 算法的超市商品销售数据的关联规则分析
郑印
（华中师范大学计算机学院，湖北武汉 430079）
Apriori association rules algorithm based supermarket merchandise sales data
Zhengyin
(Computer College, Central China Normal University, Hubei 430079, China)
摘要：Apriori 算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。尤其是在超市零售业中的应用更是广泛，通过对销售数据记录的分析，挖掘出商品的关联规则，有利于提高超市零售业的销售利率，增强其市场竞争力。
关键词：关联规则；Apriori 算法；销售利率
Abstract:Apriori algorithm is widely used in business and price’s analysis of consumer market , it can quickly determine the impact of price’s relationships between the various products. Especially using in supermarket retailing is even more widespread, through the analysis of sales data of record, the association rule mining commodities, help to improve the supermarket retail sales rates, and enhance their market competitiveness.
Key words:Association rules; Apriori algorithm; sales rate
1. 研究背景
超市零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋势，对于零售商制订销售策略是至关重要的。通过关联规则的挖掘，分析客户对商品的需求状况，发现顾客的潜在需求特征，有目的性的开展广告和销售业务。通过对顾客的忠诚度分析，相应调整商品的价格和类型，改进销售服务，有利于保持现有客户，寻找潜在的客户，扩大销售的范围和规模，从而增加销售量。通过分析销售的数据记录，目前主要应用于销售预测、库存需求、零售点选择和价格分析，分析客户的购买行为和习惯，分析商场的销售商品的构成，使商品的选择与搭配更为科学。因此，对超市经营信息、数据的整理、挖掘，从中得出对经营有用的信息，增强超市的竞争能力，已经成为各家超市企业面临的一个紧迫课题，同时，Apriori 算法作为关联规则挖掘的重要算法，也被各个企业所运用。
2. 关联规则的基本概念
设 I = {i 1 ，i 2 ，„， i m }是项的集合。设任务相关的数据 D 是数据库事务的集合，其中每个事务 T 是项的集合。每一个事务有一个标识符，称作 TID 。设 A 是一个项集，事务 T 包含 A 当且仅当 AT 。关联规则是形如 A B 的蕴涵式，其中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 算法分析
关联规则(Association Rules) 的挖掘是数据挖掘中的一个重要问题。我们采用的是相关性分析的方法，采用的是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]
CK 是LK 的超集，也就是说，CK 的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK 中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck, 可以利用Apriori 性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK 中删除。
4. 数据关联规则挖掘的实现过程
数据采集
数据是数据挖掘的前提，数据采集是获取数据的方法与实现。
可以对数据库中的数据进行抽样筛选得到与数据挖掘所处理的相关数据。也可以利用视图对数据库中的数据进行筛选。
首先从数据中抽取同一购物单上的物品组成事务，用于关联挖掘如表1-1
物品一
物品二
物品三
物品四
物品五
物品六
手套
科普
牙膏
电视机
电视机
洗衣机
T 恤
牙刷
牛奶
......
.........
.......
.......
表 1-1 关联事务表
b ）数据预处理
在数据采集的基础上，处理数据，使数据易于进行挖掘处理。主要进行了下面几个步骤：1）将商品信息表、销售记录表合并到一起（即数据集成），返回销售关联信息。2）去除不用的数据字段，比如，销售日期、商品数量等等对数据挖掘没有作用，在预处理阶段就把这些字段排除。
c ）数据挖掘
Apriori 算法是一种最有影响的挖掘布尔型关联规则频繁项目集的算法。算法思想的是基于先验知识，Apriori 算法所采用的是逐层迭代搜索方法，K-项目集用于搜索（K+1）-项目集，首先，寻找出频繁1-项目集的集合，该集合记作L1, L1用来寻找频繁2-项目集的集合L2, 再用L2寻找出L3，以此类推，直到不能找到频繁M-项目集为止。每次找出一个Lk, 就需要扫描数据库一次，即如下所述：
寻找频繁项目集算法的基本思路是Apriori 的性质, 即频繁项目的所有非空子集都必须是频繁的。利用这个性质在搜索频繁项目集时，非常有利于压缩搜索空间，从而提高频繁项目集逐层搜索的效率。
在第一遍扫描中，计算单个项目的支持度，确定哪些项目是频繁项目，即它们需具有最小支持度。在后来的扫描中，均将前一次扫描得到的频繁项目作为基础项目，利用这个基础项目产生出新的频繁项目集，这样的频繁项目集称作候选项目集（Candidate Itemsets ），并且在扫描数据的过程中计算这些候选项目集的实际支持度计数。扫描结束后，确定哪些候选项目集才是真正的频繁项目，然后将是频繁项目的这些候选项目集作为下一次扫描用的基础项目。重复此过程直到没有新的频繁项目集产生为止。一般地，算法要对数据库进行多次扫描。 由于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 的事务数。根据该式，关联规则的可以产生如下：
对于每个频繁项目集L, 产生L 的所有非空子集。
对于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 =1
Fk = { i | i∈I ∧σ({i}) ≥N × minsup } {发现所有的频繁1 －项集}
Repeat
K = k +1
Ck = apriori － gen(Fk －1 ) {产生候选项集}
For 每个事务 t ∈ Tdo
Ct = subset(C k ， t) {识别属于 t 的所有候选}
For( 每个候选项集 c ∈ Ct do
σ(c) = σ(c) + 1 {支持度计数增值}
End for
End for
Fk = { c | c ∈ Ck ∧σ(c) ≥ N × minsup } {提取频繁 k －项
集}
UntilFk = null
Result = ∪Fk
e ）挖掘结果
支持度阈值用于筛选出商品的频繁项集集合，从而算出支持度；信任度阈值用于筛选出符合要求的商品集合之间信任度集合。通过支持度阈值和信任度阈值用户可以根据实际需要来决定筛选的程度。
同时购买商品的数据：
设置支持度为：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.75
f ）结果分析
从上面我们可以看到事务集中的所有频繁项集，如牛奶; 衣服; : 3；牛肉; 鸡肉; : 3；奶酪; 鸡肉; : 2；牛奶; 衣服; 鸡肉; : 3等，他们的支持度都大于2。在这些频繁集中，牛奶，衣服可以和鸡肉建立关联规则，因为他们的信任度大于所设定的最小信任度，如上面所示还有很多频繁项集可建立关联规则。
与此同时，我们还可以看出顾客的消费习惯和那些商品顾客会同时购买，超市应该根据上面的分析结果来进购商品和安排商品的摆放位置。拿鸡肉的例子简单分析下，很多顾客购买鸡肉，因为鸡肉的支持度达到了5，远远的高于设定的支持度，同时发现很多顾客在购买鸡肉的同时还购买了牛奶，所以超市应该把鸡肉和牛奶放到一起，方便顾客的购买。 参考文献
［1］陈文伟. 数据仓库与数据挖掘 . 北京: 人民邮电出版社, 2004
［2］康晓东. 数据仓库的数据挖掘技术 . 北京: 机械工业出版社, 2004
［3］Mehmed Kantardzic. 数据挖掘 . 北京: 清华大学出版社, 2003
［4］钱颂迪. 运筹学（第二版）. 北京: 清华大学出版社, 1990
成绩
评卷人
姓名
学号
华中师范大学
研究生课程论文
论文题目
完成时间
课程名称
专业 年级