传感器的选用：介绍关联规则

关联规则挖掘是数据挖掘中最活跃的研究方法之一，它旨在使用一些有趣的方法来识别在数据库中发现的规则[5]。基于强规则的概念，Rakesh Agrawal、TomaszImieliński和Arun Swami[6]引入了关联规则，用于发现超市中通过销售系统记录的大规模交易数据中产品之间的规律性。

这里有一则沃尔玛超市的趣闻。沃尔玛曾经对数据仓库中一年多的原始交易数据进行了详细的分析，发现与尿布一起被购买最多的商品竟然是啤酒。借助数据仓库和关联规则，发现了这个隐藏在背后的事实:美国的妇女经常会嘱咐丈夫下班后为孩子买尿布，而30%～40%的丈夫在买完尿布之后又要顺便购买自己爱喝的啤酒。根据这个发现，沃尔玛调整了货架的位置，把尿布和啤酒放在一起销售，大大增加了销量。

这里借用一个引例来介绍关联规则挖掘[7]，以表11－2为例说明。

表11－2　某超市的交易数据库

1.基本概念

定义一　设I＝{i1，i2，…，im}是m个不同项目的集合，每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度，长度为k的项集称为k－项集。示例中每个商品就是一个项目，项集为

I＝{面包，啤酒，蛋糕，奶油，牛奶，茶}，I的长度为6

定义二　每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号，记为TID。交易全体构成了交易数据库D，｜D｜等于D中交易的个数。引例中包含10笔交易，因此｜D｜＝10。

定义三　对于项集X，设定count(X⊆T)为交易集D中包含X的交易的数量，则项集X的支持度为

引例中X＝{面包，牛奶}出现在T1、T2、T5、T9和T10中，所以支持度为0.5。

定义四　最小支持度是项集的最小支持阈值，记为SUPmin，代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin的项集称为频繁集，长度为k的频繁集称为k－频繁集。如果设定SUPmin为0.3，引例中{面包，牛奶}的支持度是0.5，所以是2－频繁集。

定义五　关联规则是一个蕴含式:(www.xing528.com)

R:X⇒Y

其中X⊂I，Y⊂I，并且X∩Y＝∅。表示项集X在某一交易中出现，则导致Y也会以某一概率出现。用户关心的关联规则，可以用两个标准来衡量:支持度和可信度。

定义六　关联规则R的支持度是交易集同时包含X和Y的交易数与｜D｜之比，即

支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。

定义七　对于关联规则R，可信度是指包含X和Y的交易数与包含X的交易数之比，即

可信度反映了如果交易中包含X，则交易包含Y的概率。一般来说，只有支持度和可信度较高的关联规则才是用户感兴趣的。

定义八　设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin，则称为强关联规则。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。

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

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

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

其中，问题(1)是关联规则挖掘算法的难点，下面介绍的Apriori算法和FP－growth算法都是解决问题(1)的算法。