第3章
关联规则挖掘
3.1基本概念
关联规则挖掘是用来发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测，关联规则挖掘是数据挖掘中的一个重要课题，*近几年已被业界深入研究和广泛应用。
关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。
关联规则挖掘问题可以分为两个子问题：*步是找出事务数据库中所有大于等于用户指定的*小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的*小置信度进行取舍，*后得到强关联规则。识别或发现所有频繁项目集是关联规则发现算法的核心，关联规则的基本描述如下。
1.项与项集
数据库中不可分割的*小单位信息称为项（或项目），用符号i表示，项的集合称为项集。设集合I={i1,i2,…,ik}是项集，I中项目的个数为k，则集合I称为k项集。例如，集合{啤酒，尿布，奶粉}是一个3项集。
2.事务
设I={i1,i2,…,ik}是由数据库中所有项目构成的集合，事务数据库T={t1,t2,…,tn}是由一系列具有唯一标识的事务组成。每一个事务ti(i=1,2,…,n）包含的项集都是I的子集。例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以标识这些商品是同一顾客同一次购买的，则称该用户的本次购物活动对应一个数据库事务。
3.项集的频数（支持度计数）
包括项集的事务数称为项集的频数（支持度计数）。
4.关联规则
关联规则是形如XY的蕴含式，其中X、Y分别是I的真子集，并且X∩Y=。X称为规则的前提，Y称为规则的结果。关联规则反映X中的项目出现时，Y中的项目也跟着出现的规律。
5.关联规则的支持度（support）
关联规则的支持度是交易集中同时包含X和Y的交易数与所有交易数之比，它反映了X和Y中所含的项在事务集中同时出现的频率，记为support（XY），即
support(XY)=support(X∪Y)=P(XY)(31)
6.关联规则的置信度（confidence）
关联规则的置信度是交易集中同时包含X和Y的交易数与包含X的交易数之比，记为confidence（XY），置信度反映了包含X的事务中出现Y的条件概率。
confidence（XY）=support(X∪Y)support(X)=P(Y|X)(32)
7.*小支持度与*小置信度
通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限值，此两个值称为*小支持度阈值(min_sup)和*小置信度阈值(min_conf)。其中，min_sup描述了关联规则的*低重要程度，min_conf规定了关联规则必须满足的*低可靠性。
8.强关联规则
如果support（XY）≥min_sup且confidence(XY)≥min_conf，则称关联规则
XY为强关联规则；否则，称XY为弱关联规则。通常所说的关联规则一般是指强关联规则。
9.频繁项集
设UI，项目集U在数据集T上的支持度是包含U的事务在T中所占比例，即
support(U）=‖{t∈T|Ut}‖‖T‖（33）
式中，‖·‖表示集合中元素数目。对项目集I，在事务数据库T中所有满足用户指定的*小支持度的项目集，即不小于min_sup的I的非空子集，称为频繁项目集或大项目集。
10.项目集空间理论
Agrawal等建立了用于事务数据库挖掘的项目集空间理论，理论的核心为：频繁项目集的子集仍是频繁项目集，非频繁项目集的超集是非频繁项目集。
3.2关联规则挖掘算法——Apriori算法原理
3.2.1Apriori算法原理解析
*著名的关联规则发现方法是R.Agrawal提出的Apriori算法。
1.Apriori算法基本思想
Apriori算法基本思想是通过对数据库的多次扫描计算项集的支持度，发现所有的频繁项集，从而生成关联规则。Apriori算法对数据集进行多次扫描。*次扫描得到频繁1项集的集合L1，第k（k>1）次扫描首先利用第k-l次扫描的结果Lk-1产生候选k项集的集合Ck，然后在扫描的过程中确定Ck中元素的支持度，*后在每一次扫描结束时计算频繁k项集的集合Lk，算法当候选k项集的集合Ck为空时结束。
2.Apriori算法产生频繁项集的过程
产生频繁项集的过程主要分为连接和剪枝两步，如下所示。
（1）连接步。为了找Lk(k≥2），通过Lk-1与自身作连接产生候选k项集的集合Ck，设l1和l2是Lk-1中的项集，记li［j］表示li的第j个项。Apriori算法假定事务或项集中的项按字典次序排序，对于（k-1）项集li，对应的项排序为：li1
3.Apriori算法的主要步骤
（1）扫描全部数据，产生候选1项集的集合C1。
（2）根据*小支持度，由候选1项集的集合C1产生频繁1项集的集合L1。
（3）对k>1，重复执行步骤（4）、（5）和（6）。
（4）由Lk执行连接和剪枝操作，产生候选（k+l）项集的集合Ck+1。
（5）根据*小支持度，由候选（k+l）项集的集合Ck+1，产生频繁（k+1）项集的集合Lk+1。
（6）若L≠，则k=k+1，跳往步骤（4）；否则，跳往步骤（7）。
（7）根据*小置信度，由频繁项集产生强关联规则，结束。
4.Apriori算法描述
输入：数据库D，*小支持度阀值min_sup。
输出：D中的频繁集L。
伪代码描述：
//找出频繁1项集
L1=find_frequent_1-itemsets(D);
For(k=2;Lk-1!=null;k++){
//产生候选，并剪枝
Ck=apriori_gen(Lk-1);
//扫描D进行候选计数
Foreach事务tinD{
Ct=subset(Ck,t);//得到t的子集
Foreach候选c属于Ct
c.count++;
}
……
新书资讯