基于大数据挖掘的关联规则挖掘

关联规则最初是针对购物篮分析问题提出的。假设分店经理想更多地了解顾客的购物习惯，特别是想知道哪些商品顾客可能会在一次购物时同时购买。为回答该问题，可以对商店的顾客购物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。

除了购物篮分析，关联规则还被广泛应用在通信、金融、交通、健康医疗和Web用户行为分析等领域。例如，在健康医疗领域，可以通过分析病人的历史诊疗记录，发现不同诊疗手段之间的关系；在交通领域，可以通过发现不同路段的拥堵关系来优化道路设计和交通管理^[6]；在司法行政领域，一些强制隔离戒毒所尝试采用食疗的模式对吸毒人员进行矫治，为此，可利用关联规则挖掘，发现食谱和戒毒效果的关系；在监狱和强制隔离戒毒所，可以发现矫治人员的日常行为与他们的危险性的关系。

1993年，Agrawal等人在首先提出关联规则概念的同时也给出了相应的挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，后来诸多的研究人员对关联规则的挖掘问题进行了大量的研究。

关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。那么，如何从大量的数据中发现关联规则呢？为此，我们需要了解关联规则的相关概念。

定义一：项和项集

设I＝{i1，i2，…，im}是m个不同的项目的集合，每个ik（1≤k≤m）称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度，长度为k的项集称为k-项集。例如：项集I＝{面包，啤酒，蛋糕，冰淇淋，牛奶，茶叶}的长度为6。

定义二：项集的频数和支持度

设I＝{i1，i2，…，im}是由数据库中所有项目（商品）构成的集合，事务数据库T＝{t1，t2，…，tn}，其中每一个事务ti（i＝1，2，…，n）包含的项集都是I的子集。例如，某顾客在某个商店里一次购买了多种商品，这些购买信息在事务数据库中会生产一个唯一的标识ti，用于表示该用户在本次的购买活动，也即一个事务。事务数据库中包含的某个项集的事务数称为该项集的频数，项集的频数占所有交易数之比为该项集的支持度。

定义三：关联规则

关联规则就是有关联的规则，关联规则是一个蕴含式：

其中，X⊂I，Y⊂I，并且有X∩Y＝ф，X为规则的前提，Y为规则的结果。关联规则反映了项集X在某一交易中出现时，Y以某一概率出现的规律。关联规则可以用支持度（Support）和自信度（Confidence）来衡量。

定义四：关联规则的支持度

关联规则R的支持度是交易集中同时包含X和Y的交易数占所有交易数之比，即为：

其中，count（X∩Y）表示同时包含X和Y的交易事务数，D为交易数据库D，｜D｜表示D中所有的交易事务数。支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁项集的支持度。例如：某超市2016年有100万笔销售，顾客既购买可乐又购买薯片有20万笔，顾客既购买可乐又购买面包有10万笔，那可乐和薯片的关联规则的支持度是20%，可乐和面包的支持度是10%。

定义五：关联规则的置信度（Con fidence）

关联规则R的置信度是指包含X和Y的交易数与包含X的交易数之比。即：

置信度反映了如果交易中包含X，则交易包含Y的概率。例如：某超市2016年可乐购买次数40万笔，购买可乐又购买了薯片是30万笔，顾客购买可乐又购买面包有10万笔，则购买可乐又购买薯片的置信度是75%，购买可乐又购买面包的置信度是25%，这说明买可乐也会买薯片的关联性比面包强，营销上可以做一些组合策略销售。(www.xing528.com)

一般来说，只有支持度和置信度较高的关联规则才是用户感兴趣的。

定义六：最小支持度和最小置信度

用户通常为了达到一定的要求，需要制定关联规则必须满足的支持度和置信度阈值。设定关联规则R的最小支持度和最小可信度为min_sup和min_conf，前者表示关联规则的最低重要程度，后者表示关联规则必须满足的最低可靠性。

定义七：频繁项集

支持度不小于min_sup的项集称为频繁项集，长度为k的频繁项集称为k-频繁项集。

定义八：强关联规则

规则R的支持度和置信度均不小于min_sup和min_conf，即：

Support（X⇒Y）≥min_sup且Confidence（X⇒Y）≥min_conf

则称关联规则X⇒Y为强关联规则。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。例如：表5-1为顾客购买记录数据库D，包含6个事务。项集I＝{网球，网球拍，运动鞋，羽毛球}。考虑关联规则：网球拍⇒网球，事务1、2、3、4、6包含网球拍，事务1、2、6包含网球拍和网球，则有：Support（网球拍⇒网球）＝3/6＝0.5，Confidence（网球拍⇒网球）＝3/5＝0.6。若给定min_sup＝0.5，min_conf＝0.5，则关联规则：网球拍⇒网球是强关联规则。

定义九：关联规则的提升度（Lift）

提升度表示先购买X对购买Y的概率的提升作用，用来判断规则是否有实际价值，即：

Lift＝Support（X∩Y）/Support（X）*Support（Y）

使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效，小于1则无效。例如：可乐和薯片的关联规则的支持度是20%，购买可乐的支持度是3%，购买薯片的支持度是5%，则提升度是：0.2/（0.3*0.5）＝1.33＞1，X⇒Y规则对于商品Y有提升效果。

这九个定义包含了与关联规则相关的几个重要基本概念，关联规则挖掘主要有两个问题：

（1）找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。

（2）利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度筛选出强关联规则。

其中，问题（1）是关联规则挖掘算法的难点，下文介绍的Apriori算法和FP-growth算法，都是解决问题（1）的算法。

表5-1　客户购买体育用品记录数据库