数据挖掘第3章 关联规则挖掘

数据挖掘与模式识别

DataMiningandPatternRecognition

三、关联规则挖掘AssociationRulesMiningOUTLINE关联规则的基本概念与基础理论1Apriori算法原理

2

Apriori算法实例分析3Apriori算法源程序分析4Apriori算法的特点及应用5OUTLINE关联规则的评价7序列模式挖掘算法8关联规则挖掘其它算法9FP-增长算法6关联规则的基本概念与基础理论关联规则挖掘（AssociationRuleMining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一，是数据挖掘的其它研究分支的基础。最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（BasketAnalysis）问题提出的，其目的是为了发现交易数据库（TransactionDatabase）中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（ParallelAssociationRuleMining）以及数量关联规则挖掘（QuantitiveAssociationRuleMining）等。关联规则的基本概念与基础理论购物篮分析实例通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。购物篮关联分析实例图CustomerbuysbreadCustomerbuysbothCustomerbuysmilk“牛奶与面包”的关联规则关联规则的基本概念与基础理论购物篮分析实例一个大的项目集，例如，超市里售卖的东西.一个大的篮子集，每个篮子都是一个小的项目集，例如，一个顾客一天买的东西.最简单的问题：找到这个篮子里经常出现的项目集.项目集I的支持度计数=含有I里所有项目的篮子数量.给定一个最小支持度计数门槛s，在>

s

个篮子里出现的项目的集合，称为频繁项集关联规则的基本概念与基础理论购物篮分析实例Items={milk,coke,pepsi,beer,juice}.Supports=3baskets. B1={m,c,b} B2={m,p,j} B3={m,b} B4={c,j} B5={m,p,b} B6={m,c,b,j} B7={c,b,j} B8={c,b}Frequentitemsets:{m},{c},{b},{j},{m,b},{c,b},{c,j}.关联规则的基本概念与基础理论购物篮分析实例真正的市场篮子：连锁店保存有关客户同时购买的海量信息。讲述了典型的客户浏览商店，让他们定位诱人的项目.建议搭配的“招数”，例如，尿布的打折销售并提高啤酒的价格.篮子数据分析，交叉营销，销售活动分析关联规则的基本概念与基础理论购物篮分析实例“市场篮子”是将任何两个概念之间的多对多关系模型化的一个抽象：“项目”和“篮子。”项目不需要被包含在篮子里.唯一不同的是，我们数与一个篮子相关的同时出现的项目，而不是相反.规模问题沃尔玛卖100,000个项目并且储存上亿个篮子.网络有超过100,000,000单词和上亿网页关联规则的基本概念与基础理论关联规则挖掘用来发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。关联规则挖掘问题两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集是关联规则发现算法的核心。什么是频繁模式分析?频繁模式:在数据集中经常出现的模式（项目集，子序列，子结构等）。在论文中最早提出频繁项集和关联规则挖掘R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.SIGMOD'93.揭示了数据集的一个内在的重要的特性形成了许多重要的数据挖掘任务的基础关联，相关和因果关系分析顺序，结构（例如，子图）模式时空，多媒体，时间序列，数据流模式分析分类：关联分类聚类分析：频繁模式聚类语义数据压缩：成簇关联规则的基本概念与基础理论基本概念1.项与项集数据库中不可分割的最小单位信息称为项（或项目），项的集合称为项集。

设I={i1,i2,…,im}为一个项目集合(SetofItems,项集)，其中i1,i2,…,im称为项目(item,项)。

在超市的交易数据仓库中，每个项ik代表一种商品的编号或名称，为计算方便假设I中的项已按字典序排序。若I中项目的个数为k，则集合I称为k-项集。关联规则的基本概念与基础理论基本概念2.事务设I={i1,i2,…,im}

是由数据库中所有项目构成的集合，事务数据库T={t1,t2,…,tn}是由一系列具有唯一标识的事务组成。每一个事务tj

(j=1,2,…,n)包含的项集都是I的子集，即tjI(j=1,2,…,n)

。

在超市等交易数据仓库中，

tj

就代表某个顾客一次购买的所有商品编号或商品名称。例题1

对下表所示的交易数据库记录，请给出项集和其中的事务。解：交易数据库涉及a,b,c,d等4个项，即项集I={a,b,c,d}且其中的项已经按字典序排序。每一个项就代表一种商品，比如a可表示面包，b表示牛奶等。交易数据库可表示为T={t1,t2,t3}，其中t1={a,b}，t2={b,c,d}，t3={b,d}，且它们都是项集I的子集，且按照字典序排序。关联规则的基本概念与基础理论基本概念3.项集的频数

包括项集的事务数称为项集的频数。4.关联规则

关联规则是形如的蕴含式，其中X，Y分别是I的真子集，并且

。其中X称为规则的前提，Y称为规则的结果。关联规则反映X中的项目出现时，Y中的项目也跟着出现的规律。关联规则的基本概念与基础理论基本概念5.关联规则的支持度（support）

关联规则的支持度是交易集中同时包含X和Y的交易数与所有交易数之比，它反映了X和Y中所含的项在事务集中同时出现的频率，记为support（），即注意：关联规则的支持度计数为同时包含X和Y的交易数。关联规则的基本概念与基础理论基本概念对于例题1的交易数据库T，若令X={b,c},Y={d}，则Support(XY)=Support({b,c}{d})=Support({b,c,d})/3=1/3

由此可知，在购物篮分析中，XY的支持度也可以表示为关联规则的基本概念与基础理论基本概念6.关联规则的置信度（confidence）

关联规则的置信度是交易集中同时包含X和Y的交易数与包含X的交易数之比，记为confidence（），置信度反映了包含X的事务中出现Y的条件概率，即

confidence（）=

=关联规则的基本概念与基础理论基本概念7.最小支持度与最小置信度

通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限值，此两个值称为最小支持度阈值(min_sup)和最小置信度阈值(min_conf)。其中，min_sup描述了关联规则的最低重要程度，min_conf规定了关联规则必须满足的最低可靠性。关联规则的基本概念与基础理论基本概念8.频繁项集

设，项目集U在数据集T上的支持度是包含U的事务在T中所占的百分比，即

式中：表示集合中元素数目。对项目集I，在事务数据库T中所有满足用户指定的最小支持度的项目集，即不小于min_sup的I的非空子集，称为频繁项目集。关联规则的基本概念与基础理论基本概念最大频繁项集

设X1,X2,…,Xr是T上关于最小支持度min_sup的所有频繁项集，若对任意p(p=1,2,…,r；pq)都有XqXp，称Xq为一个最大频繁项目集。因此，Xq为最大频繁项集的充分必要条件是，Xq不是其它任何频繁项集的子集。显然，T上的最大频繁项集通常不唯一。关联规则的基本概念与基础理论基本概念9.强关联规则(StrongAssociationRule)support（）min_sup且confidence()min_conf，则称关联规则为强关联规则，否则称为弱关联规则。通常所说的关联规则一般是指强关联规则。关联规则挖掘就是按用户指定最小支持度min_sup和最小置信度min_conf

，从给定的事务数据库T中寻找出所有强关联规则的过程。例题2

针对例题1中的交易数据库记录，（1）若最小支持度min_sup

=0.6，对项集X={b,d}，因为Support(X)=2/30.6，即X={b,d}是个频繁项集，且是频繁2-项集。（2）令X={b,c},Y={d}，试求其置信度。由于Support(XY)=Support({b,c,d})=1/3，而Support(X)=Support{b,c}=1/3，所以Confidence(XY)=Support(XY)/Support(X)=1例题3Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeerLetmin_sup=50%,min_conf=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}Associationrules:AD(60%,100%)DA(60%,75%)关联规则的基本概念与基础理论基础理论项目集性质：项目集空间理论理论的核心为：频繁项目集的子集仍是频繁项目集，非频繁项目集的超集是非频繁项目集。关联规则的基本概念与基础理论基础理论Agrawal等人在研究事务数据库关联规则挖掘的过程中，发现了关于项集的两个基本性质，并在关联规则挖掘中被广泛应用。定理3-1(频繁项集性质1)：如果X是频繁项集，则它的任何非空子集X'也是频繁项集。

即频繁项集的子集必是频繁项集。定理3-2(频繁项集性质2)：如果X是非频繁项集，那么它的所有超集都是非频繁项集。

即非频繁项集的超集也是非频繁项集。关联规则的基本概念与基础理论基础理论关联规则性质：定理3-3

（关联规则性质1）：设X为频繁项集，YX且Y’Y。若Y’(X-Y’)为强关联规则，则Y(X-Y)也必是强关联规则。

比如，令X={b,c,e}且已知{e}{b,c}是强关联规则，则由定理3-3立即得出{b,e}{c}和{c,e}{b}都是强关联规则的结论，而不需计算这两个规则的置信度。关联规则的基本概念与基础理论基础理论关联规则性质：定理3-4（关联规则性质2）：设X为频繁项集，YX且Y'Y。若Y(X-Y)不是强关联规则，则Y'(X-Y')也不是强关联规则。

比如，令X={b,c,e}且已知{b,c}{e}不是强关联规则，则由定理3-4立即得出{b}{c,e}和{c}{b,e}都不是强关联规则的结论，也无需计算它们的置信度。典型算法AIS算法（R.Agrawal等提出）Apriori算法（及变种AprioriTid和AprioriHybrid)）SETM算法（M.Houtsma等提出）DHP算法（J.Park等提出）PARTITION算法（A.Savasere等提出）Sampling算法（H.Toivonen提出）FP-growth算法（JiaweiHan提出）关联规则的基本概念与基础理论Apriori算法原理Apriori算法是Agrawal等学者提出的关联规则的经典挖掘算法，在关联规则挖掘领域具有很大影响力。算法名称源于它使用了关于项集的两个性质，即定理3-1和3-2等先验(Apriori)知识。Apriori算法基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法原理Apriori算法在具体实现时，将关联规则的挖掘过程分解为两个子问题。1、发现频繁项集

根据用户给定的最小支持度min_sup

，寻找出所有的频繁项集，即满足支持度Support不低于min_sup的所有项集。由于这些频繁项集之间有可能存在包含关系，因此，我们可以只关心所有的最大频繁项集，即那些不被其它频繁项集所包含的所有频繁项集。

2、生成关联规则

根据用户给定的最小置信度min_conf

，在每个最大频繁项集中，寻找置信度Confidence不小于min_conf的关联规则。Apriori算法原理说明：第二个子问题相对容易些，因为它只需要在已经找出的频繁项目集的基础上列出所有可能的关联规则，同时，满足支持度和置信度阈值要求的规则被认为是有趣的关联规则。第一个子问题是挖掘关联规则的关键步骤，挖掘关联规则的总体性能由第一个步骤决定，因此，所有挖掘关联规则的算法都是着重于研究第一个子问题。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）若Lk+1≠Φ，则k=k+1，跳往步骤（4）；

否则，跳往步骤（7）；（7）根据最小置信度，由频繁项集产生强关联规则，结束。Apriori算法原理发现频繁项集如果|I|=m,则I总共有

2m-1个非空的子集。若

|T|=n，则对于每一个事务

tj都要检查它是否包含这

2m-1个子集，其时间复杂性为O(n2m)。当m很大时，关联规则挖掘的时间开销往往是巨大的。Apriori算法原理发现频繁项集发现频繁项集的过程主要分为:

连接(self-joining)和剪枝(pruning)两步。修正原则:如果有任何非频繁的项集，则它的子集就用不生成/检验。(Agrawal&Srikant@VLDB’94,Mannila,etal.@KDD’94)方法:起初，扫描事务数据库得到频繁1项集连接：从长度K的频繁项集生成长度为（K+1）的候选项集剪枝：在事务数据库中检验候选频繁项集当没有频繁或候选集生成时就终止发现频繁项集需引入以下有关概念和符号：候选频繁项集：最有可能成为频繁项集的项目集。Ck：所有候选频繁k-项集的集合；Lk：所有频繁k-项集构成的集合；I中所有k-项集的集合。

显然，C1和L1的计算比较容易，只要扫描事务数据库T很容易找出其中的所有候选1-项集,以及判断它们是否为频繁1-项集即可。Apriori算法原理发现频繁项集根据“频繁项集的子集必为频繁项集”这一性质，可利用频繁k-项集的集合Lk，来构造所有候选(k+1)-项目集的集合Ck+1，再通过扫描数据库，从Ck+1中找出频繁(k+1)-项集的集合Lk+1(k=1,2,…,m-1)。由分析可知：因此，要寻找所有频繁k-项集的集合Lk，只需计算候选频繁k-项集的集合Ck中每个项集的支持度，而不必计算I中所有k-项集的支持度，这在一定程度上减少了算法的计算量。Apriori算法原理发现频繁项集Apriori算法之频繁项集发现算法：输入：项集I，事务数据库T，最小支持数MinSptN输出：所有频繁项集构成的集合L求L1：

①通过扫描数据库T，找出所有1-项集并计算其支持数作为候选频繁1-项集C1；

②从C1中删除低于MinSptN的元素，得到所有频繁1-项集所构成的集合L1；(2)FORk=1,2,3,….(3)连接：将Lk进行自身连接生成一个候选频繁k+1项集的集合Ck+1，其连接方法如下：对任意p，qLk，若按字典序有p={p1,p2,…,pk-1,pk}，q={p1,p2,…,pk-1,qk}且满足pk<qk，则把p,q连接成k+1项集，即将pq={p1,p2,…,pk-1,pk,qk}作为候选(k+1)-项集Ck+1中的元素。(4)剪枝：删除Ck+1中明显的非频繁(k+1)-项集，即当Ck+1中一个候选(k+1)-项集的某个k-项子集不是Lk中的元素时，则将它从Ck+1中删除。(5)计算支持数：通过扫描事务数据库T，计算Ck+1中各个元素的支持数。(6)求Lk+1：剔除Ck+1中低于最小支持数MinSptN的元素，即得到所有频繁(k+1)-项集构成的集合Lk+1。(7)若Lk+1=，则转第(9)步(8)ENDFOR(9)令L=L1L2L3…Lk，并输出L。发现频繁项集候选生成的例子L3={abc,abd,acd,ace,bcd}连接步:L3*L3abcdfromabcandabdacdefromacdandace剪枝步:acdeisremovedbecauseadeisnotinL3C4={abcd}产生关联规则1、设X为一个项集，YX，则Y(XY)称为由X导出的关联规则。2、若X是频繁项集，则它导出的关联规则必满足最小支持度要求，

即Support(Y(XY))=Support(X)min_sup

因此，只需检查Confidence(Y(XY))是否满足最小置信度min_conf

，即可判断这个规则是否为强关联规则。因为频繁项集X的任一子集Y和XY都是频繁项集，且Support(Y)和Support(XY)的值在发现频繁项集的时候已经计算出来。因此当Confidence(Y(X-Y))=Support(X)/Support(Y)

min_conf

，可知Y(X-Y)为强关联规则。产生关联规则因此，我们可以得到关联规则的生成算法：(1)对于L中的每一个频繁项集X，生成X所有的非空真子集Y。(2)对X的每一个非空真子集Y，计算Confidence(Y(X-Y))

如果Confidence(Y(X-Y))min_conf

，则Y(X-Y)为强关联规则，否则不是强关联规则。产生关联规则穷举法可以通过枚举频繁项集生成所有的关联规则，并通过计算关联规则的置信度来判断该规则是否为强关联规则。但当一个频繁项集包含的项很多时，就会生成大量的候选关联规则，因为一个频繁项目集X能够生成2|X|-2个（即除去与X本身之外的子集）候选关联规则。产生关联规则可以逐层生成关联规则，并利用关联规则性质2（定理3-4）进行剪枝，以减少关联规则生成的计算工作量。其基本思路是，首先产生后件只包含一个项的关联规则，然后两两合并这些关联规则的后件，生成后件包含两个项的候选关联规则，从这些候选关联规则中再找出强关联规则，以此类推。比如，设{a,b,c,d}是频繁项集，{a,c,d}{b}和{b,c,d}{a}是两个关联规则，则通过合并它们的后件生成候选规则的后件{a,b}，则候选规则的前件为{a,b,c,d}-{a,b}={c,d}，由此即得候选规则{c,d}{a,b}。产生关联规则下图显示了由频繁项集{a,b,c,d}产生关联规则的格结构。如果格中任意结点对应关联规则的置信度低于min_conf

（即下图中MinC），则根据关联规则的性质2，可以立即剪掉该结点所生成的整个子图。TheAprioriAlgorithm—AnExampleDatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2whyHow？MinSptN=2Apriori算法实例分析参考教材《数据挖掘算法原理与实现》第38-40页例3.1、例3.2Apriori算法实例分析例题3对下表所示的交易数据库，其项集I={a,b,c,d,e}，设最小支持度min_sup=0.4，最小置信度min_conf=0.6，请完成以下工作：1、找出所有的频繁项目集；2、求出最大频繁项集的集合；3、求出所有的强关联规则。解：1、找出所有的频繁项目集因支持度min_sup=0.4，事务数据库有5条记录，即最小支持数MinSptN=2。(1)求L1：扫描事务数据库，可得候选频繁1-项集及其支持数计算结果。(2)第一轮循环：对L1执行算法的(3)至(6)步。(3)连接：由L1自身连接生成候选频繁2-项集的集合C2，其结果由下表左侧第1列给出，且已按字典序排序。{a}与{b},{c},{d},{e}分别连接生成{a,b},{a,c},{a,d}和{a,e}。{b}与{c},{d},{e}分别连接生成{b,c},{b,d},{b,d}。……(4)剪枝：由于I中所有1-项集都是频繁的，因此C2无

需进行剪枝过程。(5)计算支持数：扫描数据库，计算其支持数。(6)求L2：删除支持数小于2的候选2-项集，最终得到所有的频繁2-项集。(7)L2(2)第二轮循环：对L2执行算法的(3)至(6)步获得L3。SptN({d,e})=1,{b,d,e}、{c,d,e}被剪枝(2)第三轮循环：对L3执行算法的(3)至(6)步获得L4。(2)第四轮循环：由于L4仅有一个频繁4-项集，故已不能生成候选频繁5-项集C5，因此(7)L5=，转算法(9)步。(9)

输出L=L1

L2L3L4={{a},{b},{c},{d},{e}}

{{a,b},{a,c},{a,d},{b,c},{b,d},{b,e},{c,d},{c,e}}{{a,b,c},{a,b,d},{a,c,d},{b,c,d},{b,c,e}}{{a,b,c,d}}2、求出最大频繁项集的集合因为最大频繁项集一定不是其它任何频繁项集的子集。因此，可以采用枚举法来寻找L中的最大频繁项集，一般从项最多的频繁项集开始，检查它是否包含在某个频繁项集之中。（1）因为L中只有一个频繁4-项集{a,b,c,d}，故它不可能是L中其它2-项集，3-项集的子集，所以它是一个最大频繁项集。（2）对于{b,c,e}，因为它不是{a,b,c,d}的子集，也不是L中其它3-项集的子集，更不是其它2-项集的子集，所以是最大频繁项集。（3）因为{a,b,c},{a,b,d},{a,c,d}和{b,c,d}都是{a,b,c,d}的子集，

{a,b},{a,c},{a,d},{b,c},{b,d}和{c,d}都是{a,b,c,d}的子集,

{b,e}和{c,e}都是{b,c,e}的子集，所以它们都不是最大频繁项集。故L中有2个最大频繁项集，构成Lmax={{b,c,e}，{a,b,c,d}}。3、求出所有的强关联规则从L中取出第1个2-频繁项集{a,b}，它的两个非空真子集{a}和{b}可以生成{a}{b}和{b}{a}两个关联规则。

Confidence({a}{b})=Support({a,b})/Support({a})=3/3=1Confidence({b}{a})=Support({a,b})/Support({b})=3/5=0.6因此，{a}{b}和{b}{a}都是强关联规则。同理,求出{a,c}，{a,d}，{b,c}，{b,d}，{b,e}，{c,d}，{c,e}等7个2-频繁项集的关联规则，并判断是否强关联规则。

对频繁3-项集{b,c,e}有6个非自身的非空真子集{b},{c},{e},{b,c},{b,e},{c,e}，故共可生成6个关联规则，其置信度计算结果详见下表。同理，可以计算求出其它频繁3-频繁集的强关联规则，也可以计算由{a,b,c,d}可以导出{a}{b,c,d}，{a,b}{c,d}等14个关联规则，并找出相应的强关联规则。Apriori算法源程序分析参考教材《数据挖掘算法原理与实现》第41-49页利用网络资源，获取程序代码Apriori算法的特点及应用Apriori算法是应用最广泛的关联规则挖掘算法，它有如下优点：1）Apriori算法是一个迭代算法。2）数据采用水平组织方式。3）采用Apriori优化方法。4）适合事务数据库的关联规则挖掘。5）适合稀疏数据集。Apriori算法的特点及应用特点Apriori算法有如下缺点：1）多次扫描事务数据库,需要很大的I/O负载。对每个k=1,2，…,m，为了计算候选k-项集的支持度，都需要扫描一次事务数据库，才能确定候选k-项集的支持度，其计算时间开销很大。2）可能产生庞大的候选集。例如，当事务数据库有104个频繁1-项集时，Apriori算法就需要产生多达107个候选2-项集，即对存储空间要求会影响算法的执行效率。3）候选项集支持度计算量大，尤其在频繁项目集长度变大的情况下,运算时间显著增加。Apriori算法的特点及应用特点改进的Apriori大体思路：1）减少交易数据库的扫描。2）减少候选的数量。3）提高候选频繁项支持度计算效率。Apriori算法的特点及应用特点改进的Apriori大体思路：1）减少交易数据库的扫描。2）减少候选的数量。3）提高候选频繁项支持度计算效率。Apriori算法的特点及应用应用商业网络安全领域高校管理移动通信领域FP-增长算法用FP-增长(Frequent-PatternGrowth，FP-Growth)算法来发现频繁项集。算法只需扫描事务数据库两次，其计算过程主要由以下两步构成。（1）构造FP-树

将事务数据库压缩到一棵频繁模式树(Frequent-PatternTree，简记为FP-树)之中，并让该树保留每个项的支持数和关联信息。（2）生成频繁项集

由FP-树逐步生成关于项集的条件树，并根据条件树生成频繁项集。FP-增长算法构造FP-树FP-树是事务数据库的一种压缩表示方法。

它通过逐个读入事务，并把每个事务映射为FP-树中的一条路径，且路径中的每个结点对应该事务中的一个项。

不同的事务如果有若干个相同的项，则它们在FP-树中用重叠的路径表示，用结点旁的数字标明该项的重复次数，作为项的支持数。

因此，路径相互重叠越多，使用FP-树结构表示事务数据库的压缩效果就越好。

如果FP-树足够小且能够在内存中存储，则可以从这个内存的树结构中直接提取频繁项集，而不必再重复地扫描存放在硬盘上的事务数据库。例题4某超市经营a,b,c,d,e等5种商品，即超市的项集I={a,b,c,d,e}，而下表是其交易数据库T。

下面借用这个事务数据库来介绍FP-树的构造方法，这里假设最小支持数MinS=2。FP-树的构造主要由以下两步构成。1、生成事务数据库的头表H

第一次扫描事务数据库T，确定每个项的支持数，将频繁项按照支持数递减排序，并删除非频繁项，得到T的频繁-1项集H={iv:SptNv|ivI,SptNv为项目iv的支持数}。现有文献都将H称为事务数据库的头表(Headtable)。

对于上表的事务数据库T，其头表H={(a:8),(b:7),(c:6),(d:5),(e:3)}，即T中的每个项都是频繁的。2、生成事务数据库的FP-树

第二次扫描数据集T，读出每个事务并构建根结点为null的FP-树。

开始时FP-树仅有一个结点null，然后依次读入T的第r个事务tr(r=1,2,…,|T|)。

设tr已删除了非频繁项，且已按照头表H递减排序为{a1,a2，…,}，则生成一条路径tr=null-a1-a2-,…,-，并按以下方式之一，将其添加到FP-树中，直到所有事务处理完备。如果FP-树与路径tr没有共同的前缀路径(prefixpath)，即它们没有从null开始，其余结点完全相同的一段子路径，则将tr直接添加到FP-树的null结点上，形成一条新路径，且让tr中的每个项对应一个结点，并用av:1表示。例

假设FP-树中已有两条路径null-a-b和null-c-d-e(图(1))。

设有事务t={b,c,d}，其对应的路径为t=null-b-c-d(事务和对应的路径采用同一个符号t)。因为FP-树与t没有共同的前缀路径，即从null开始没有相同的结点，因此，将t直接添加到FP-树中(图(2))。

如果FP-树中存在从根结点开始与tr完全相同的路径，即FP-树中存在从null到a1直到的路径，则将FP-树中该路径上从a1到的每个结点支持数增加1即可。例

假设FP-树中已有两条路径null-a-b-c和null-b-c-d(图(1))。

设有事务t={a,b}，其路径为t=null-a-b，则因为FP-树从根节点null开始存在与null-a-b完全相同的路径，因此，将结点a,b的支持数分别增加1即可(图(2))。如果FP-树与路径tr有相同的前缀路径，即FP-树已有从null到a1直到aj的路径，则将FP-树的结点a1到aj的支持数增加1，并将tr从aj+1开始的子路径放在aj之后生成新的路径。例

假设FP-树中已有两条路径null-a-b和null-b-c-d(图(1))。

设有事务t={b,c,e}，其对应的路径为t=null-b-c-e，则因为FP-树与t存在共同的前缀路径null-b-c，因此，将结点b,c的支持数直接增加1，并在结点c后面增加结点e(图(2))。例

对右表所示的事务数据库T，假设最小支持数MinS=2，试构造它的FP-树。生成频繁项集

由于每一个事务都被映射为FP-树中的一条路径，且结点代表项和项的支持数，因此通过直接考察包含特定结点(例如e)的路径，就可以发现以特定结点(比如e)结尾的频繁项集。

由FP-树生成频繁项集的算法以自底向上的方式搜索FP-树，并产生指定项集的条件树，再利用条件树生成频繁项集。

对于前面所得的FP-树，算法从头表H={(a:8),(b:7),(c:6),(d:5),(e:3)}的最后，即支持数最小的项开始，依次选择一个项并构造该项的条件FP-树(conditionFP-tree)，即首先生成以e结尾的前缀路径，更新其结点的支持数后获得e的条件FP-树，并由此生成频繁项集{e}。

在{e}频繁的条件下，需要进一步发现以de、ce、be和ae结尾的频繁项集等子问题，直至获得以e结尾的所有频繁项集，即包括e的所有频繁项集。

观察头表H可知，包括e的项集共有{e},{d,e},{c,e},{b,e},{a,e},{c,d,e},{b,d,e},{b,c,e},{a,d,e},{a,c,e},{a,b,e},{a,c,d,e}等。

在e的条件FP-树产生过程中，算法会不断地删除非频繁项集保留频繁项集，而不是枚举地检验以上每个项集是否为频繁的，因而提高了搜索效率。从de的条件FP-树可得以de结尾的频繁项集{a,d,e}，{d,e}。

当包括e的所有频繁项集生成以后，接下来再按照头表H，并依次寻找包括d，c，b或a的所有频繁项集，即依次构造以d，c，b或a结尾的前缀路径和条件FP-树，并获得以它们结尾的所有频繁项集。根据与前面类似的计算过程，最终可得事务数据库T的所有频繁项集(如下表)关联规则的评价1、主观标准

以决策者的主观知识或领域专家的先验知识等建立的评价标准，称为主观兴趣度。(1)关联规则{黄油}{面包}有很高的支持度和置信度，但是它表示的联系连超市普通员工都觉得显而易见，因此不是有趣的。(2)关联规则{尿布}{啤酒}确实是有趣的，因为这种联系十分出人意料，并且可能为零售商提供新的交叉销售机会。关联规则的评价2、客观标准

以统计理论为依据建立的客观评价标准，称为客观兴趣度。(1)客观兴趣度以数据本身推导出的统计量来确定规则是否是有趣的。(2)支持度，置信度，提升度(马上介绍)等都是客观兴趣度，也就是客观标准。支持度和置信度的不足为了说明支持度和置信度在关联规则检测中存在的不足，可用基于2个项集A和B（也称二元变量A，B）的相依表来计算说明。

下表中的记号

表示项集A没有在事务中出现，nij为支持数，即n11表示同时包含项集A和B的事务个数；n01表示包含B但不包含A的事务个数；n10表示包含A但不包含B的事务个数；n00表示既不包含A也不包含B的事务个数；n1+表示A的支持数，n+1表示B的支持数，而N为事务数据库的事务总数。例题5一个误导的“强”关联规则。若MinS=0.3，MinC=0.60，则因Support(AB)=4000/10000=0.4>MinS，Confidence(AB)=4000/6000=0.66>MinS得出AB是一个强关联规则的结论。实际上，AB这个强关联规则却是一个虚假的规则，如果商家使用这个规则将是一个错误，因为购买录像的概率是75%比60%高。

此外，计算机游戏和录像机是负相关的，因为买其中一种商品实际上降低了买另一种商品的可能性。如果不能完全理解这种现象，容易根据规则AB做出不明智的商业决策。相关性分析提升度(lift)是一种简单的相关性度量。

对于项集A和B，如果概率P(AB)=P(A)P(B)，则A和B是相互独立的，否则它们就存在某种依赖关系。Lift(A,B)=P(AB)/(P(A)P(B))=(P(AB)/P(A))/P(B)Lift(A,B)=Confidence(AB)/Support(B)

如果Lift(A,B)的值大于1，表示二者存在正相关，而小于1表示二者存在负相关。若其值等于1，则表示二者没有任何相关性。对于二元变量，提升度等价于被称为兴趣因子(Interestfactor)的客观度量，其定义如下Lift(A,B)=I(A,B)=Support(AB)/(Support(A)Support(B))=Nn11/(n1+n+1)例题6

对于例题5中的表所示的相依表，试计算其提升度或兴趣因子。解：P(AB)=4000/100000=0.4；P(A)=6000/1000=0.6；P(B)=7500/10000=0.75Lift(A,B)=P(AB)/(P(A)P(B))=0.4/(0.60.75)=0.4/0.45=0.89

关联规则AB，也就是{计算机游戏}{录像机}的提升度Lift(A,B)小于1，即前件A与后件B存在负相关关系，若推广“计算机游戏”不但不会提升“录像机”的购买人数，反而会减少。

项集之间的相关性也可以用相关系数来度量。对于二元变量A,B，相关系数r定义为

若相关系数r等于0，表示二者不相关，大于0表示正相关，小于0表示负相关。例题7

对例题5所示的相依表，试计算相关因子。解：相关系数r的分子等于4000500-35002000=20000007000000=-5000000，故相关系数r小于0，故购买“计算机游戏”与购买“录像机”两个事件是负相关的。

此外，相关性还可以用余弦值来度量，即

相关性度量可以提高关联规则的可用性，但仍然存在局限性，还需要研究，并引入其它客观度量。序列模式挖掘算法关联规则刻画了交易数据库在同一事务中，各个项目(Items)之间存在的横向联系(购买A的同时还买了B)，但没有考虑事务中的项目在时间维度上存在的纵向联系(购买了A一段时间后，再来购买B)，后者就是一种时间序列模式，简称序列模式。序列模式的概念定义3-1设I={i1,i2,…,im}为项集，称S=<(s1,h1),(s2,h2),…,(sn,hn)>为一个时间事务序列，如果siI，hi为si发生的时间且hi<hi+1(i=1,2,…,n-1)。

如果在时间事务序列问题的分析时，只要求hi<hi+1且不计hi=hi+1-hi的大小(i=1,2,…,n-1)，即不关心前后两个事务发生的时间跨度，则时间事务序列可简记为S=<s1,s2,…,sn)>，并称为一个序列(Sequence)。其中项集si称为序列S的元素。定义3-2

若序列S中包含k个项，则称S为k-序列或长度为k的序列。序列模式的概念例题8

顾客购买商品的序列

若仅关心顾客购买商品的时间顺序而不关心购买商品的具体时间，则S=<{笔记本电脑,鼠标},{移动硬盘,摄像头},{刻录机,刻录光盘),{激光打印机,打印纸}>就是某个顾客一段时间内购买商品的序列，它有4个元素，8个项目，其长度为8。序列模式的概念定义3-3

称S=<s1,s2,…,sr)>为序列

的子序列(Subsequence)，记作SS’，若存在正整数,使例题9

对于序列S‘=<{7},{3,8},{9},{4,5,6},{8}>，则S=<{3},{4,5},{8}>是S’的一个子序列，因为S的元素{3}{3,8}，S的元素{4,5}{4,5,6}，S的元素{8}{8}，即S是S'的一个子序列。例题10

对于下表所示的交易数据库，其中商品用长度为2的数字编码表示。试给出每个顾客的购物序列。解：对于包含时间信息的交易数据库，可以按照顾客id和交易日期升序排序，并把每位顾客每一次购买的商品集合作为该顾客购物序列中的一个元素，最后按照交易日期先后顺序将其组成一个购物序列，生成如下表所示的序列数据库S。序列模式的概念

类似于关联规则中的支持度概念，我们可以将序列S在序列数据库TS中的支持数定义为该数据库中包含S的元组数，即SptN(S)=|{(Cid,S')|(Cid,S')TSSS')}|因此，S在序列数据库TS中的支持度可定义为Support(S)=|{(Cid,S')|(Cid,S')TSSS')}|/|TS|=SptN(S)/|TS|定义3-4

给定一个最小支持度阈值MinS，如果Support(S)≥MinS，则称序列S是频繁的。如果序列S是频繁的，则称S为一个频繁序列(FrequentSequence)或序列模式（SequencePattern）。

序列模式的概念例题11对于例题10所得的序列数据库TS，给定最小支持度阈值MinS=25%，试找出其中的两个频繁序列模式。解：因为MinS=25%，而序列数据库TS有5条记录，所以支持数等于1.25，即频繁序列至少应包含在2个元组之中。容易判断序列<{30},{90}>和<{30},{40,70}>都是频繁的，因为元组C2和C4包含序列<{30},{90}>，而元组C2和C4包含序列<{30}{40,70}>。故<{30},{90}>和<{30},{40,70}>都是序列模式。序列模式的概念

对于项集XI，如果存在序列S的元素si使得Xsi，则称元组(Cid,S)包含项集X。因此，类似于关联规则中的频繁项集概念，可以将X在序列数据库TS中的支持数定义为该数据库中包含X的元组数SptN(X)=|{(Cid,S)|(Cid,S)TSsi(Xsi)}|同理，X在序列数据库TS中的支持度可定义为Support(X)=|{(Cid,S)|(Cid,S)TSsi(Xsi)}|/|TS|=SptN(X)/|TS|定义3-5

设XI,MinS为最小支持度阈值，如果Support(X)≥MinS，则称X为序列数据库TS的频繁项集。序列模式的类Apriori算法序列模式的发现可以采用穷举法来枚举所有可能的序列，并统计它们的支持度。但这种方法的计算复杂性非常高。容易证明，在长度为n的序列中，一个具有n个项的序列总共包含2n-1个不同的子序列。因此必要寻找其它更高效的算法来发现序列模式，而下面介绍的定理3-5(序列模式的性质)，就可以在序列模式的搜索空间中剪裁掉那些明显的非频繁序列，从而提高序列模式挖掘的效率。

定理3-5

(序列模式性质)：如果S’是频繁序列，则其任何非空子序列S也是频繁序列。序列模式的类Apriori算法类Apriori（AprioriBased）算法是一种基于Apriori原理的序列模式挖掘算法，利用序列模式的性质（定理3-5）来对候选序列模式集进行剪枝，从而减少了算法的计算工作量。其挖掘过程又可分解为事务数据库排序、频繁项集生成、事务转换映射、频繁序列挖掘等几个步骤，下面通过例子予以详细说明。（1）事务数据库排序

对原始的事务数据库T（表8-13），以顾客id为主键，交易时间为次键进行排序，并将其转换成以顾客id和购物序列S组成的序列数据库TS（表8-14）。（2）频繁项集生成

找出所有的频繁项集，并分别用一个正整数表示。在表8-14所示的序列数据库TS中，{30},{40},{70),{40,70}和{90}都是频繁项集。为方便计算机处理，频繁项集通常被映射为一个连续正整数的集合(表8-15)。（3）序列转换映射

将序列数据库TS中每个顾客购物序列的每一个元素用它所包含的频繁项集的集合来表示，再将购物序列中的每个商品编号用表8-15的正整数代替，得到转换映射后的序列数据库TN(表8-16)。

值得注意的是，元素{40,60,70}所包含的频繁项集为{40},{70}和{40,70}，因此，它就被转换为一个频繁项集的集合{{40},{70},{40,70}}。（4）频繁序列挖掘

在映射后的序列数据库TN中挖掘出所有序列模式：首先得到候选频繁1-序列模式集CS1，扫描序列数据库TN，从CS1中删除支持度低于最小支持MinS的序列，得到频繁1-序列模式集FS1。

然后循环由频繁k-序列集FSk，生成候选频繁(k+1)-序列集CSk+1，再利用定理8-5对CSk+1进行剪枝，并从CSk+1中删除支持度低于最小支持度MinS的序列，得到频繁(k+1)-序列集FSk+1，直到FSk+1=为止。例题12

设有频繁3-序列集FS3={<{1},{2},{3}>,<{1},{2},{4}>,<{1},{3},{4}>,<{1},{3},{5}>,<{2},{3},{4}>}解：先利用频繁3-序列集FS3连接生成候选4-序列集，即

将序列<{1},{2},{3}>和<{1},{2},{4}>连接生成<{1},{2},{3},{4}>和<{1},{2},{4},{3}>，

将序列<{1},{3},{4}>和<{1},{3},{5}>连接生成<{1},{3},{4},{5}>和<{1},{3},{5},{4}>因此，得到候选4-序列集CS4={<{1},{2},{3},{4}>，<{1},{2},{4},{3}>，<{1},{3},{4},{5}>，<{1},{3},{5},{4}>}根据频繁序列的性质（定理3-5），对C4进行剪枝操作。首先将4-序列<{1},{2},{4},{3}>从C4中删除，因为它存在一个3-序列<{2},{4},{3}>不在FS3之中，即它不会是频繁4-序列。类似地可以将<{1},{3},{4},{5}>，<{1},{3},{5},{4}>从CS4中删除。因此，得到最终的候选频繁4-序列集CS4={<{1},{2},{3},{4}>}。例题13

设最小支持数为2，对于表8-16转换映射后的序列数据库TN挖掘出所有的序列模式。解：在序列数据库的转换和映射过程中已得到频繁1-序列FS1={<{l}>，<{2}>，<{3}>，<{4}>，<{5}>}。利用频繁1-序列集FS1生成候选频繁2-序列集CS2={<{1},{2}>,<{2},{1}>,<{1},{3}>,<{3},{1}>,<{1},{4}>,<{4},{1}>,<{1},{5}>,<{5},{1}>,<{2},{3}>,<{3},{2}>,<{2},{4}>,<{4},{2}>,<{2},{5}>,<{5},{2}>,<{3},{4}>,<{4},{3}>,<{3},{5}>,<{5},{3}>,<{4},{5}>,<{5},{4}>}。

共有20个候选频繁2-序列。

扫描序列数据库TN并对候选频繁2-序列计算支持数，如<{1},{2}>的支持数为2，<{2},{1}>的支持数为0，<{1},{5}>支持数为3等，取支持数不低于2的序列组成频繁2-序列集FS2={<{1},{2}>，<{1},{3}>，<{1},{4}>，<{1},{5}>，<{2},{3}>，<{2},{4}>，<{2},{5}>，<{3},{4}>，<{3},{5}>，<{4},{5}>}

对频繁2-序列集FS2进行自身连接并剪枝后得到候选3-序列集CS3={<{1},{2},{3}>，<{1},{2},{4}>，<{1},{2},{5}>，<{1},{3},{4}>，<{1},{3},{5}>，<{1},{4},{5}>，<{2},{3},{4}>，<{2},{3},{5}>，<{2},{4},{5}>，<{3},{4},{5}>}

说明：频繁2-序列连接生成20个候选频繁3-序列，其中10个候选频繁3-序列被剪枝，如<{1},{3},{2}>被剪枝是因其子序列<{3},{2}>不是频繁2-序列。

对候选频繁3-序列集CS3中每个序列计算支持数，保留支持数不小于2的序列形成频繁3-序列集FS3={<{1},{2},{5}>，<{1},{3},{5}>，<{1},{4},{5}>}。

由于FS3不能再产生候选频繁4-序列，故最后得到频繁序列模式集FS=FS2FS3={<{1},{2}>，<{1},{3}>