关联规则挖掘技术在零售业中的应用

[摘 要] 简要地介绍数据挖掘和关联规则的概念,关联规则的基本理论,讨论了Apriori算法的核心内容,同时针对Apriori算法的不足,提出了解决方法,描述了几种优化算法。最后分析了关联规则挖掘在零售业中的应用。

[关键词] 关联规则 数据挖掘 Apriori 算法

数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。人工智能领域习惯称知识发现,而数据库领域习惯称数据挖掘。

由于条形码技术的发展,零售部门可以利用前端收款机收集交易数据,并把这些数据存储在后台海量数据库中。如果对这些历史数据进行分析,从中获得顾客购买行为特征,对商家来说是极有价值的信息。这些信息有助于规划市场、合理安排货架等。Agrawal针对大型超市的销售数据库建立了关联规则模型和数据挖掘算法。

一、关联规则的基本理论

设I={i1,i2,…,im}为所有项目的集合,D为事务数据库,事务 T是一个项目子集(TT)。每一个事务具有惟一的事务标识Tid。设A是一个由项目构成的集合,称为项集。事务T包含项集A,当且仅当AT。如果项集A中包含k个项目,则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是频繁项集(或大项集)。

关联规则是形如XY的逻辑蕴含式,其中XI,YI,且X⌒Y=φ。如果事务数据库D中有要s%的事务包含XY,则称关联规则XY的支持度为s%,实际上,支持度是一个概率值。若项集X的支持度记为sup port(X),规则的信任度为sup port(XY)/sup port(X)。这是一个条件概率P(Y/Y)。也就是:

sup port(XY)=P(XY)

confidence(XY)=P(Y/Y)

关联规则就是支持度和信任度分别满足用户给定阈值的规则。发现关联规则需要经历如下两个步骤:

1.找出所有频繁项集。

2.由频繁项集生成满足最小信任度阈值的规则。

二、关联规则的挖掘算法

1.Apriori算法

Apriori算法在发现关联规则领域具有很大影响力。算法命名源于算法使用了频繁项集性质的先验(Prior)知识。在具体实现时,Apriori算法将发现关联规则的过程分为两个步骤:第一步通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;第二步利用频繁项集构造出满足用户最小信任度的规则。其中,挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。

由m个项目形成的不同项集的数目可以达到2m-1个,尤其在海量数据库D中,这是一个NP难度的问题。为了避免计算所有项集的支持度(实际上频繁项集只占很少一部分),Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck,频繁k项集的集合记为Lk,m个项目构成的k项集的集合为Ckm,则三者之间满足关系LkCkCkm。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。

通过已知的频繁项集构成长度更大的项集,并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度,而不必计算所有不同项集的支持度,因此在一定程度上减少了计算量。具体的实现过程为:

(1)通过单趟扫描数据库D计算出各个1项集的支持度,从而得到频繁1项集构成的集合L1。

(2)连接步:为了产生频繁k项集构成的集合Lk,预先生成一个潜在频繁k项集的集合Ck。潜在频繁项集的集合由JOIN运算得到。若p,q∈Lk-1,P{p1,p2,…,pk-2,pk-1},q={q1,q2,…,pk-2,pk-1,qk-1},并且当1≤i≤k-1时,pi=qi,当i=k-1时,pk-1≠qk-1,则pq={p1,p2,…,pk-2,pk-1,qk-1}是潜在频繁k项集的集合Ck中的元素。这里的潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。

(3)剪枝步:由于Ck是Lk的超集,可能有些元素不是频繁的。Ck很庞大时会带来巨大的计算量,为减少Ck的规模,Apriori遵从下列性质:任何非频繁的(k-1)项集必定不是频繁k项集的子集。所以,当潜在k项集的某个(k-1)子集不是Lk-1中的成员时,则该潜在频繁项集不可能是频繁的,可以从Ck中移去,这就是Apriori剪枝思想。

(4)通过单趟扫描数据库D,计算Ck中各个项集的支持度。

(5)将Ck中不满足最小支持度的项集剔除,形成由频繁k项集构成的集合Lk。

通过迭代循环,重复上述步骤(2)～(5),直到不能产生新的频繁项集的集合(非空集合)时为止,Apriori 算法求出所有满足最小支持度的频繁项集。

2.Apriori 算法的优化

虽然Apriori算法本身已经进行了一定的优化,但是一方面由于对海量数据库的多趟扫描,另一方面用JOIN产生潜在频繁项集。仍存在一些不足。目前许多专家学者通过大量的研究工作,提出了一些优化的算法以提高Apriori的效率。

(1)基于哈希表技术

Park等人提出把哈希表结构用于关联规则挖掘,在扫描数据库中的事务用以生成频繁k项集的同时,可以从事务中生成所有的(k+1)项集,并将其用Hash函数映射到哈希表结构中,同时增加相应的桶计数。该趟扫描结束时,将桶计数低于支持度阈值的项集从潜在频繁项集中删除。实质上是在生成潜在频繁项集时完成剪枝工作。算法核心是通过改变数据结构来增加关联规则的发现效率。

(2)事务压缩技术

Agrawal等提出压缩进一步迭代扫描的事务数据的方法。因为不包含任何k项集的事务,不可能包含任何(k+1)项集,可对这些事务加上删除标志,扫描数据库时不再考虑。若一个事物不包含任何k项集,则该事物包含的项数必定小于k,同时必小于(k+1),则该事物不会包含在任何(k+2)项集中。由此在扫描事务数据库产生I项集之前,先把该事物删除以提高扫描效率,在以后的操作中则不需要该事物。

(3)杂凑技术

一个高效地产生频集的基于杂凑的算法由Park等提出。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上,Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。

(4)划分技术

Savasere等设计了一个基于划分的算法,这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。

(5)抽样技术

基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息,仔细地组合分析,可以得到一个改进的算法,Mannila等先考虑了这一点,他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想,先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则,然后对数据库的剩余部分验证这个结果。

(6)动态项集计数

Brin等人采用动态项集计数方法求解频繁项集。首先把数据库分成若干个块,并在每个块的起始点加上标记。然后用到目前标记为止的计数信息动态地估计所有项集的支持度,如果所有子集均估计为频繁的,则将该项集加入潜在频繁项集中,从而形成与Apriori算法不同的生成潜在频繁项集的方法。

三、关联规则挖掘的应用

在零售业,数据挖掘可有助于识别顾客购买行为,发现顾客购买模式和趋势,改进服务质量,取得更好的顾客保持力和满意程度,提高货品销量比率,设计更好的货品运输与分销策略,减少商业成本。

下面给出一个某超市顾客购买商品的事务数据库中的数据,说明关联规则对商品销售数据的挖掘过程,通过挖掘发现顾客的购买习惯和偏好。

某超市对一定时期内顾客购买商品的数据收集如下:

数据挖掘过程如下:

第一步,计算出表中每种商品的关联规则支持度,根据定义,计算出

Support(棉衣)=2/5=0.4=40%

Support(帽子)=3/5=0.6=60%

Support(围巾)=3/5=0.6=60%

Support(手套)=3/5=0.6=60%

Support(毛巾)=1/5=0.2=20%

Support(毛毯)=1/5=0.2=20%

第二步,根据设定的最小支持度阀值,将大于或等于最小支持度阀值的商品挑选出来,设最小支持度阀值为0.3,可挑选出商品棉衣、帽子、围巾和手套。

第三步,计算商品的关联规则信任度。

根据定义,计算出棉衣、帽子、围巾和手套四种商品的信任度。

Confidence(棉衣=>帽子)= Support(棉衣=>帽子)/ Support(棉衣)=20%/40%=0.5;

Confidence(棉衣=>围巾)=Support(棉衣=>围巾) / Support(棉衣)= 20%/40%=0.5;

Confidence(棉衣=>手套)=Support(棉衣=>手套) / Support(棉衣)= 40%/40%=1,说明该规则有100%的情况是成立的。

为了简便,其余数据通过X=>Y的信任度表表示如下

第四步,根据设定的最小信任度阀值,设最小信任度阀值为0.6,得到如下规则:

第五步,根据上述关联规则,可以发现超市顾客的购买习惯和偏好,销售管理人员可采取如下措施:一是调整货架,将商品帽子、围巾统一放置在一起,便于顾客选购,甚至可考虑将商品帽子、围巾和手套,商品棉衣和手套捆绑销售;二是在进货或仓储方面,可考虑将关联商品统购统存;三是印发关联商品的促销广告,提高商品的支持度和信任度;四是在企业网络销售中,应将关联商品放在同一页面或增加关联商品间的链接。在采取以上措施后,超市可以扩大销售额,提高了服务水平,顾客可以扩大交叉购买,增加消费。

通常关联规则挖掘普遍使用“支持度——信任度”度量机制,但需要注意的是,在实际应用中,不加额外的限制条件会产生大量的规则。这些规则并不是对用户都是有用的或感兴趣的。衡量关联规则挖掘结果的有效性应该从多种综合角度来考虑。一是准确性:挖掘出的规则必须反映数据的实际情况。尽管规则不可能是100%适用。二是实用性:挖掘出的规则必须是简洁可用的,而且是针对挖掘目标的。不能是有100条规则,其中50条与商业目标无关,30条用户无法理解。三是新颖性:挖掘出的规则可以为用户提供新的有价值信息。但如果它们是用户事先知道的,那么这样的规则即使再正确也是毫无价值的。

上述销售管理的数据挖掘,可应用于商品批零业和大型超市等商业企业中。为更好地满足客户需求,通过对商品数据的挖掘,发现商品之间的关联特征,在有效利用企业有限资源的基础上,采取相应的销售策略,既能够提高企业的服务水平,提高客户满意度,又能够节约企业资源,利用最小的投入,获得到较大的收益。在信息时代,对提高企业的竞争力,更好地应对机遇和挑战具有重要作用和意义。

参考文献:

[1]李雄飞 李 军:数据挖掘与知识发现[M].北京:高等教育出版社,2003

[2]安淑芝等:数据仓库与数据挖掘[M].北京:清华大学出版社,2005 .6