关联规则挖掘课件

第3章关联规则挖掘

3.1基本概念3.2关联规则挖掘算法3.3Apriori改进算法3.4不候选产生挖掘频繁项集3.5使用垂直数据格式挖掘频繁项集3.6挖掘闭频繁项集3.7挖掘各种类型的关联规则3.8相关分析3.9基于约束的关联规则3.10矢量空间数据库中关联规则的挖掘第3章关联规则挖掘

3.1基本概念3.1基本概念

交易数据库又称为事务数据库，尽管它们的英文名词一样，但是事务数据库更具有普遍性。例如，病人的看病记录、基因符号等用事务数据库更贴切。因此，下面的叙述更多使用事务数据库这一名词，而不用交易数据库这个名词。3.1基本概念交易数据库又称为事务数据库，一个事务数据库中的关联规则挖掘可以描述如下：设I={i1,i2,…,im}是一个项目集合，事务数据库D={t1,t2,…,tn}是由一系列具有惟一标识的TID事务组成。每一个事务ti(i=1,2,…,n)都对应I上的一个子集。定义3.1设I1

I，项目集(Itemsets)I1在数据集D上的支持度(Support)是包含I1的事务在D中所占的百分比，即式中：||·||表示集合中元素数目。(3.1)一个事务数据库中的关联规则挖掘可以描述如下：式中定义3.2对项目集I，在事务数据库D中所有满足用户指定的最小支持度(Minsupport)的项目集，即不小于Minsupport的I的非空子集，称为频繁项目集(FrequentItemsets)或大项目集(LargItemsets)。定义3.3一个定义在I和D上，形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来定义的。所谓规则的可信度，是指包含I1和I2的事务数与包含I1的事务数之比，即(3.2)定义3.2对项目集I，在事务数据库D中所有满足用户指定

定义3.4D在I上满足最小支持度和最小置信度(Minconfidence)的关联规则称为强关联规则(StrongAssociationRules)。通常所说的关联规则一般是指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。定义3.4D在I上满足最小支持度和最小置信度(Minc(1)发现频繁项目集：通过用户给定的最小支持度，寻找所有频繁项目集，即满足支持度Support不小于Minsupport的所有项目子集。发现所有的频繁项目集是形成关联规则的基础。(2)生成关联规则：通过用户给定的最小可信度，在每个最大频繁项目集中，寻找置信度不小于Minconfidence的关联规则。(1)发现频繁项目集：通过用户给定的最小支持度，寻找3.2关联规则挖掘算法

3.2.1项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集空间理论。理论的核心为：频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。这个理论一直作为经典的数据挖掘理论被应用。3.2关联规则挖掘算法3.2.1项目集空间理论定理3.1如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。证明设X是一个项目集，事务数据库D中支持X的元组(记录)数为S。设X的任一非空子集YX，事务数据库D中支持Y的元组(记录)数为S1。根据项目集支持度的定义，很容易知道支持X的元组一定支持Y，所以S1≥S，即support(Y)≥support(X)按假设，项目集X是频繁项目集，即support(X)≥minsupport所以support(Y)≥support(X)≥minsupport，因此Y是频繁项目集。定理3.1如果项目集X是频繁项目集，那么它的所有非空子定理3.2如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明设事务数据库D中支持X的元组数为S。设X的任一超集Z

X，事务数据库D中支持Z的元组数为S2。根据项目集支持度的定义，很容易知道支持Z的元组一定支持X，所以S2≤S，即support(Z)≤support(X)定理3.2如果项目集X是非频繁项目集，那么它的所有超集按假设，项目集X是非频繁项目集，即support(X)<minsupport所以support(Z)≤support(X)<minsupport，因此Z不是频繁项目集。1993年，Agrawal等人在提出关联规则概念的同时，给出了相应的挖掘算法AIS，但性能较差。1994年，他们依据上述两个定理，提出了著名的Apriori算法，Apriori算法至今仍然作为关联规则挖掘的经典算法，其他算法均是在此基础上进行改进的。按假设，项目集X是非频繁项目集，即3.2.2经典的发现频繁项目集算法Apriori算法是R.Agrawal和R.Strikant于1994年提出的布尔关联规则挖掘频繁项集的原创性算法。算法的基本思想：基于频繁项目集性质的先验知识，使用由下到上逐层搜索的迭代方法，k项集用于搜索k+1项集。首先，扫描数据库，统计每一个项发生的数目，找出满足最小值支持度的项，找出频繁1项集，计作L1；然后，基于L1找出频繁2项集的集合L2，基于L2找出频繁3项集的集合L3，如此下去，直到不能找到频繁k项集Lk。找每一个Lk需要一次数据库全扫描。3.2.2经典的发现频繁项目集算法Apriori算法的核心由连接步和剪枝步组成。(1)连接步：为找频繁项集Lk(k≥2)，先通过将Lk-1与自身连接产生候选K项集的集合Ck。设l1和l2是Lk-1中的项集，即l1∈Lk-1，l2∈Lk-1。Apriori算法假定事务或项集中的项按照字典顺序排列，设li［j］表示li中的第j项。对于k-1项集li，对应的项排序为：li［1］＜li［2］＜…＜li［k-1］。Lk-1与自身连接使用Lk-1∞Lk-1来表示。Apriori算法的核心由连接步和剪枝步组成。如果l1∈Lk-1，l2∈Lk-1中的前k-2个元素相同，则称l1、l2是可连接的，即l1［1］=l2［1］∧l1［2］=l2［2］∧…∧l1［k-1］<l2［k-1］。条件l1［k-1］<l2［k-1］可以保证不产生重复，而按照L1，L2，…，Lk-1，Lk，…，Ln次序寻找频繁项集可以避免对事务数据库中不可能发生的项集所进行的搜索和统计的工作。连接l1、l2的结果项集是l1［1］、l1［2］、…、l1［k-1］、l2［k-1］。如果l1∈Lk-1，l2∈Lk-1中的前k-2个元素相同(2)剪枝步：由候选K项集的集合Ck产生频繁K项集Lk。Ck是Lk的超集，也就是说Ck的成员可以不是频繁的，但所有的频繁项集Lk都包含在Ck中。扫描数据库D，统计Ck中每一个候选项集的计数，从而确定Lk。然而Ck集合中元素数目可能很大，这样所涉及的计算量就很大。为压缩Ck，可以利用频繁项目集性质的先验知识：任何非频繁的(k-1)项集都不是频繁k项集的子集。(2)剪枝步：由候选K项集的集合Ck产生频繁K项集Lk。因此，如果候选k项集Ck的(k-1)项子集不在Lk-1中，则该候选不可能是频繁的，从而可以从Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例如，如果2项目集C2={AB,AD,AC,BD}，而对于新产生3项目集中的元素ABC不需要加入到C3中，因为它的2项子集BC不在C2中。而对于新产生的元素ABD应该加入到C3中，因为它的所有2项子集都在C2中。因此，如果候选k项集Ck的(k-1)项子集不在Lk-1中【例3.1】表3-1为某一超市销售事务数据库D，使用Apriori算法发现D中频繁项目集。问题分析：事务数据库D中有9个事务，即||D||=9。超市中有5件商品可供顾客选择，即I=｛I1,I2,I3,I4,I5｝，且||I||=5。设最小支持数minsup_count=2，则对应的最小支持度为2/9＝2.2%。【例3.1】表3-1为某一超市销售事务数据库D，使用表3-1某一超市销售事务数据库D

表3-1某一超市销售事务数据库D事务数据库D中候选项目集、频繁项目集生成过程如下：1)候选1项目集C1的生成

I=｛I1,I2,I3,I4,I5｝中每一项都是候选1项目集合C1的成员，对候选1项目集C1=｛I1,I2,I3,I4,I5｝中的每一个1候选项目集，在数据库D进行扫描，统计它们的支持数。2)频繁1项目集L1的生成在候选1项目集C1=｛I1,I2,I3,I4,I5｝中，选取支持数不小于最小支持数minsup_count=2的候选1项目集作为频繁1项目集L1,L1=｛I1,I2,I3,I4,I5｝。事务数据库D中候选项目集、频繁项目集生成过程如下：3)候选2项目集C2的生成由频繁1项目集L1=｛I1,I2,I3,I4,I5｝生成候选2项目集C2。由数学中组合知识和2候选项目集定义可知，2候选项目集C2是1频繁项目集L1=｛I1,I2,I3,I4,I5｝的全组合，共有C2

|L1|种组合，也就是说,2候选项目集C2中共有C2|L1|个元素。为了提高算法效率，Apriori算法使用连接L1∞L1产生候选项目集C2。L1∞L1连接运算要求两个连接的项集共享0个项，Lk∞Lk运算中要求两个连接的项集共享k-1个项。对候选项目集C2中的每一个2候选项目集，在数据库D进行扫描，统计它们的支持数。3)候选2项目集C2的生成4)2频繁项目集L2的生成在2候选项目集C2中，选取支持数不小于最小支持数minsup_count=2的候选项目集作为2频繁项目集L2。

4)2频繁项目集L2的生成5)3候选项目集C3的生成由2频繁项目集L2生成3候选项目集C3。首先按照连接步定义计算C3=L2∞L2={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}；然后按照剪枝步的方法，频繁项集的所有子集也必须是频繁的，可以确定后4个候选不可能是频繁的，从而可以把它们从C3中删除，这样扫描数据库D时，不必再统计它们的数目。5)3候选项目集C3的生成由于Apriori算法采用由下到上、逐层搜索技术，当给定候选k项集，只须检查它们的k-1项子集是否频繁。对候选项目集C3中的每一个3候选项目集，在数据库D进行扫描，统计它们的支持数。由于Apriori算法采用由下到上、逐层搜索技术，当给定6)3频繁项目集L3的生成在3候选项目集C3中，选取支持数不小于最小支持数minsup_count=2的候选项目集作为3频繁项目集L3。7)4候选项目集C4的生成计算C4=L3∞L3={{I1,I2,I3,I5}}，因为它的子集{I2,I3,I5}不是频繁的，应该从C4中删除。这样C4＝Ф，算法终止，找出了所有的频繁项集。这样一个寻找所有频繁项集的过程如图3-1所示。6)3频繁项目集L3的生成图3-1搜索候选项集和频繁项集过程图3-1搜索候选项集和频繁项集过程以下为Apriori算法和它的相关过程的伪代码。算法3.1Apriori(发现频繁项目集)。输入：数据集D、最小支持数minsup_count。输出：频繁项目集L。(1)L1={large1-itemsets};//所有支持数不小于minsup_count的1项目集(2)FOR(k=2；Lk-1≠Φ；k++)｛(3)Ck=apriori-gen(Lk-1);//Ck是包含k个元素的候选项目集以下为Apriori算法和它的相关过程的伪代码。(4)FORalltransactionst∈D｛//扫描数据集D用于计数(5)Ct=subset(Ck,t);//Ct是所有t中包含Ck的候选项目集(6)FORallcandidatesc∈Ctc.count++;//计数(7)｝(8)Lk={c∈Ck︱c.count≥minsup_count}(9)｝(10)RETURNL=∪Lk；(4)FORalltransactionst∈Apriori算法中步骤(1)找出频繁1项集的集合L1；步骤(2)～(9)实现由Lk-1生成Ck，再找出Lk；步骤(3)调用了apriori-gen(Lk-1)函数，是为了通过(k-1)频繁项目集产生k候选集，并删除包含非频繁子集的k候选集；步骤(4)对所有的候选扫描数据集D用于计数；步骤(5)对每一个事务使用subset函数找出事务中是候选的所有子集；步骤(6)对这样的候选累加计数；步骤(8)找出满足最小支持度的候选；步骤(10)形成频繁项集的集合L。Apriori算法中步骤(1)找出频繁1项集的集合L1；

算法3.2apriori-gen(Lk-1)(候选集产生)。输入：(k-1)频繁项目集Lk-1。输出：k侯选项目集Ck。(1)FORallitemsetl1Lk-1{(2)FORallitemsetl2Lk-1{(3)IF(l1［1］=l2［1］∧l1［2］=l2［2］∧…∧l1［k-1］<l2［k-1］)THEN{;(4)C=l1∞l2;//连接步，把l2［k-1］连接在l1［k-1］后算法3.2apriori-gen(Lk-1)(候选集(5)IFhas_infrequent_subset(C,Lk-1)THEN(6)deleteC;//删除含有非频繁项目子集的候选项目集C(7)ELSE(8)Ck=Ck∪C(9)}(10)}(11)}(12)RETURNCk;(5)IFhas_infrequent_subset

算法3.2中调用函数has_infrequent_subset(C,Lk-1)是为了判断C是否要加入到k侯选项目集Ck中。

算法3.3has_infrequent_subset(C,Lk-1)。输入：候选项目集C，(k-1)频繁项目集Lk-1。输出：是否删除候选项目集C。(1)FORall(k-1)-subsetSofC(2)IFSLk-1THENRETURNTRUE(3)RETURNFALSE算法3.2中调用函数has_infrequent_su3.2.3由频繁项集产生关联规则由数据库D中的事务找出频繁项集，可按照下面的步骤生成关联规则。(1)对于每一个频繁项集l，生成其所有的非空子集。(2)对于每一个非空子集xl，计算confidence(x(l-x))。如果confidence(x(l-x))≥minConfidence，那么规则x(l-x)为一个强关联规则。3.2.3由频繁项集产生关联规则

算法3.4从给定的频繁项目集中生成强关联规则。输入：频繁项目集L、最小信任度minConfidence。输出：强关联规则。Rule－generate(L,minConfidence)(1)FORearchfrequentitemsetlk∈L(2)generateRules(lk∈L,lk∈L,minConfidence);算法3.4的核心是函数generateRules的递归过程，它实现一个频繁项目集中所有强关联规则的生成。算法3.4从给定的频繁项目集中生成强关联规则。

算法3.5通过递归寻找一个频繁项目集中的所有强关联规则。generateRules(lk：frequentk-itenset，lm：frequentm-itenset,minConfidence)(1)X={(m-1)-itensetxm-1｜xm-1xm};(2)FOReachxm-1∈X{(3)confidence(xm-1)=support(lk)/support(lm-1);算法3.5通过递归寻找一个频繁项目集中的所有强关联规则(4)IF(confidence(xm-1)≥minConfidence)THEN(5)printtherule“xm-1(lk-xm-1)，withsuppot(lk),andconfidence(xm-1)”(6)IF(m>2)THENgenerateRules(lk∈L,xm-1∈X,minConfidence);(7)}(4)IF(confidence(xm-1)≥min利用频繁项目集生成关联规则就是逐一测试在所有频繁项集中可能生成的关联规则、对应的支持度、置信度参数。算法3.5实际上采用深度优先搜索方法来递归生成关联规则，当然，同样也可以使用广度优先搜索方法来递归生成关联规则，读者可以自己尝试来完成。利用频繁项目集生成关联规则就是逐一测试在所有频繁项集中可【例3.2】对于例3.1事务数据库D，假定发现的频繁项集l={I1,I2,I5}，试找出由l产生的所有关联规则。频繁项集l={I1,I2,I5}的所有非空子集为{I1,I2}、{I1,I5}、{I2,I5}、{I1}、{I2}、{I5}则其对应的关联规则和置信度如下：(1)I1∧I2I5，confidence=2/4=50%;(2)I1∧I5I2，confidence=2/2=100%;(3)I2∧I5I1，confidence=2/2=100%;【例3.2】对于例3.1事务数据库D，假定发现的频繁项(4)I1I2∧I5，confidence=2/6=33%;(5)I2I1∧I5，confidence=2/7=29%;(6)I5I1∧I2，confidence=2/2=100%。如果最小置信度阈值为70％，则只有(2)、(3)和(6)为强关联规则。由频繁项目集生成关联规则的优化问题主要集中在减少不必要的规则生成尝试方面。(4)I1I2∧I5，confidence=2/6定理3.3设有频繁项目集l，项目集Xl，X1为X的一个子集，即X1X。如果关联规X(l-X)不是强关联规则，那么X1(l-X1)一定不是强关联规则。

证明由支持度的定义可知，X1的支持度support(X1)一定大于X的支持度support(X)，即support(X1)≥support(X)所以confidence(X1(l-X1))=support(l)/support(X1)≤confidence(X(l-X))=support(l)/support(X)定理3.3设有频繁项目集l，项目集Xl，X1为X的由于X(l-X)不是强关联规则，即confidence(X(l-X))<minConfidence所以confidence(X1(l-X1))≤confidence(X(l-X))<minConfidence因此，X1(l-X1)不是强关联规则。由于X(l-X)不是强关联规则，即由定理3.2可知，在由频繁项目集生成关联规则的过程中，可以利用已有的关联规则结果来有效避免一些不必要的搜索，从而提高算法效率。在算法3.5的步骤(6)中可以加入这一条件：以(m>2&confidence(xm-1(l-xm-1))≥minConfidence)作为递归结束的判断条件，读者可以自己尝试来完成。由定理3.2可知，在由频繁项目集生成关联规则的过程中，可定理3.4设有项目集X，X1是X的一个子集，即X1X，如果规则YX是强规则，那么规则YX1一定是强规则。

证明由支持度定义可知，一个项目集的子集的支持度一定大于等于它的支持度，即support(X1∪Y)≥support(X∪Y)所以confidence(YX)=support(X∪Y)/support(Y)≤support(X1∪Y)/support(Y)=support(X1∪Y)定理3.4设有项目集X，X1是X的一个子集，即X1由于YX是强规则，即confidence(YX)≥minConfidence所以corfidence(X1∪Y)≥confidence(YX)≥minConfidence因此，“YX1”也是强规则。由定理3.4可知，在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定是强规则的尝试。这个定理也保证把测试的注意点放在判断最大频繁项目集的合理性上。实际上，只要从所有最大频繁项目集出发去测试可能的关联规则即可，因为其他频繁项目集生成的规则的右项一定包含在对应的最大频繁项目集生成的关联规则右项中。由于YX是强规则，即3.3Apriori改进算法

3.3.1Apriori算法的瓶颈Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。但是随着研究的深入，它的缺点也暴露出来。Apriori算法有两个致命的性能瓶颈。(1)多次扫描事务数据库，需要很大的I／O负载。对每次k循环，候选集Ck中的每个元素都必须通过扫描一次数据库来验证其是否加入Lk。假如一个频繁大项目集包含10个项，那么就至少需要扫描事务数据库10遍。3.3Apriori改进算法3.3.1Apriori(2)可能产生庞大的候选集。由Lk-1产生k候选集Ck是呈指数增长的，例如104个1频繁项目集,Apriori算法能产生多达107个2候选集。如此大的候选集对时间和主存空间都是一种挑战。因此，包括Agrawal在内的许多学者提出了Apriori算法的改进方法。(2)可能产生庞大的候选集。3.3.2改进算法1.基于散列的技术(散列项集到对应的桶中)一种基于散列的技术可以用于压缩候选k项集Ck(k>1)。例如，当扫描数据库中的每个事务，由C1中的候选1项集产生频繁1项集L1时，可以对每个事务产生所有的2项集，将它们散列(即映射)到散列表结构的不同桶中，并增加对应的桶计数(如图3-2所示)。在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁的，因而应当从候选项集中删除。这种基于散列的技术可以显著压缩要考察的候选k项集。3.3.2改进算法图3-2候选2项集的散列表图3-2候选2项集的散列表2.事务压缩不包含任何频繁k项集的事务不可能包含任何频繁(k+1)项集。因此，这种事务在其后考虑中，可以加上标记或删除，因为产生j(j>k)项集的数据库扫描不再需要它们。2.事务压缩3.划分使用划分技术只需要两次数据库扫描，以挖掘频繁项集(如图3-3所示)。它包含两个阶段。在阶段Ⅰ，算法将D中的事务分成n个非重叠的划分。如果D中事务的最小支持度阈值为min_sup，则一个划分的最小支持度计数为min_sup乘以该划分中的事务数。对每个划分，找出该划分内的所有频繁项集。这些称做局部频繁项集(LocalFrequentItemset)。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。对于k=1，2，…，n找出所有的局部频繁项集只需要扫描一次数据库。3.划分图3-3通过划分数据进行挖掘图3-3通过划分数据进行挖掘局部频繁项集可能是也可能不是整个数据库D的频繁项集。D的任何频繁项必须作为局部频繁项集至少出现在一个划分中。这样，所有的局部频繁项集是D的候选项集。所有划分的频繁项集的集合形成D的全局候选项集。在阶段Ⅱ，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。划分的大小和划分的数目以每个划分能够放入内存为原则来确定，这样每阶段只需要读一次。局部频繁项集可能是也可能不是整个数据库D的频繁项集。D的4.抽样抽样方法的基本思想：选取给定数据D的随机样本S，然后在S中搜索频繁项集。用这种方法，虽然牺牲了一些精度但换取了有效性。样本S的大小选取使得可以在内存中搜索S的频繁项集。这样，总共只需要扫描一次S中的事务。由于搜索S中而不是D中的频繁项集，可能丢失一些全局频繁项集。为减少这种可能性，使用比最小支持度低的支持度阈值来找出S中局部的频繁项集(记作LS)。然后，数据库的其余部分用于计算LS中每个项集的实际频率。使用一种机制来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，则只需要扫描一次D。否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须频繁运行时，抽样方法特别合适。4.抽样5.动态项集计数动态项集计数技术将数据库划分为用开始点标记的块。不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已计数的所有项集的支持度，如果一个项集的所有子集已确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。5.动态项集计数3.4不候选产生挖掘频繁项集

频繁模式增长(FrequentPatternGrowth)，或简称FP增长，试图设计一种方法，挖掘全部频繁项集而不产生候选。它采取如下分治策略：首先，将提供频繁项的数据库压缩到一棵频繁模式树(或FP树)，但仍保留项集关联信息。然后，将压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库)，每个与一个频繁项或“模式段”关联，并分别挖掘每个条件数据库。3.4不候选产生挖掘频繁项集频繁模式增长(Frequ【例3.3】FP增长(发现频繁项集而不产生候选)。使用频繁模式增长方法，重新考察例3.1中表3-1的事务数据库D的挖掘。数据库的第一次扫描与Apriori相同，它导出频繁项(1项集)的集合和支持度计数(频率)。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或列表记作L，L=［I2:7,I1:6,I3:6,I4:2,I5:2］。【例3.3】FP增长(发现频繁项集而不产生候选)。使用频FP树构造：首先，创建树的根节点，用“null”标记。第二次扫描数据库D。每个事务中的项按L中的次序处理(即按递减支持度计数排序),并对每个事务创建一个分枝。例如，扫描第一个事务“T100:I1,I2,I5”包含三项(按L的次序I2，I1，15)，导致构造树包含这三个节点的第一个分枝〈I2:1〉,〈I1:1〉,〈I5:1〉，其中，I2作为根的子女链接到根，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀I2。这样，将节点I2的计数增加1，并创建一个新节点〈I4:1〉作为〈I2:2〉的子女链接。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数增加1，为在前缀之后的项创建节点和链接。FP树构造：首先，创建树的根节点，用“null”标记。为方便树遍历，创建一个项头表，使每项通过一个节点链指向它在树中的位置。扫描所有的事务之后得到的树如图3-4所示，带有相关的节点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP树问题。为方便树遍历，创建一个项头表，使每项通过一个节点链指向它图3-4存放压缩的频繁模式信息的FP树图3-4存放压缩的频繁模式信息的FP树FP树的挖掘过程：由每个长度为1的频繁模式(初始后缀模式)开始，构造它的条件模式基(一个“子数据库”由FP树中与后缀模式一起出现的前缀路径集组成)，然后，构造它的条件FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。FP树的挖掘过程：由每个长度为1的频繁模式(初始后缀模式该FP树的挖掘总结在表3-2中，细节如下。首先考虑I5，它是L中的最后一项，而不是第一个。从表的后端开始的原因随着解释FP树挖掘过程就会清楚。I5出现在图3-3的FP树的两个分枝(I5的出现沿它的节点链容易找到)。这些分枝形成的路径是〈I2,I1,I5:1〉和〈I2,I1,I3,I5：1〉。因此，考虑I5为后缀，它的两个对应前缀路径是〈I2,I1:1〉和〈I2,I1,I3:1〉，形成I5的条件模式基。它的条件FP树只包含单个路径〈I2:2,I1:2〉；不包含I3，因为它支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}。该FP树的挖掘总结在表3-2中，细节如下。首先考虑I5，表3-2通过创建条件子模式基挖掘FP树

表3-2通过创建条件子模式基挖掘FP树

I4的两个前缀路径形成条件模式基{I2

I1:1},{I2:1},产生单节点的条件FP树〈I2:2〉，并导出一个频繁模式{I2,I4:2}。注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁模式在考察I5时已经分析过。I4的两个前缀路径形成条件模式基{I2I1:1},{与以上分析类似，I3的条件模式基是{(I2

I1:2)，(I2:2)，(I1:2)}。它的条件FP树有两个分枝〈I2:4,I1:2〉和〈I1:2〉，如图3-5所示，它产生模式集：{I2

I3:4,I1I3:4,I2I1I3:2}。最后，I1的条件模式基是{(I2:4)}，它的FP树只包含一个节点〈I2:4〉，产生一个模式{I2I1:4}。挖掘过程总结在算法3.6中。与以上分析类似，I3的条件模式基是{(I2I1:2)，图3-5具有条件节点I3的条件FP树图3-5具有条件节点I3的条件FP树算法3.6FP增长。使用FP树，通过模式段增长挖掘频繁模式。输入：事务数据库D；最小支持度计数阈值min_sup。输出：频繁模式的完全集。方法：(1)按以下步骤构造FP树：①扫描事务数据库D一次。收集频繁项的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。②创建FP树的根节点，以“null”标记它。对于D中每个事务Trans，执行：算法3.6FP增长。使用FP树，通过模式段增长挖掘频繁选择Trans中的频繁项，并按L中的次序排序。设排序后的Trans中频繁项列表为［p|P］，其中p是第一个元素，而P是剩余元素的列表。调用insert_tree(［p|P］,T)。该过程执行情况如下：如果T有一个子女N使得N.item-name=p.item-name，则N的计数增加1，否则创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同item-name的节点。如果P非空，递归地调用inserttree(P,N)。选择Trans中的频繁项，并按L中的次序排序。设排序后的(2)FP树的挖掘通过调用FP_growth(FP-tree，null)实现。该过程实现如下：procedureFP_growth(Tree，α)①IFTree含单个路径Pthen②FOReach路径P中节点的每个组合(记作β)③产生模式β∪α，其支持度计support_count等于β中节点的最小支持度计数；④ELSE⑤FORTree的头表中的每个αi{(2)FP树的挖掘通过调用FP_growth(FP-t⑥产生模式β=αi∪α，其支持度计数support_count=αi.support_count;⑦构造β的条件模式基，然后构造β的条件FP树Treeβ，⑧IFTreeβ≠Φthen⑨调用FP-growth(Treeβ,β)；⑩ }⑥产生模式β=αi∪α，其支持度计数support_cFP增长方法将发现长频繁模式的问题转换成递归地搜索一些较短模式，然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP树有时是不现实的。一种有趣的可选方案是首先将数据库划分成投影数据库的集合，然后在每个投影数据库构造FP树并挖掘它。如果投影数据库的FP树还不能放进内存，该过程可以递归地用于投影数据库。FP增长方法将发现长频繁模式的问题转换成递归地搜索一些较对FP增长方法的性能研究表明：对于挖掘长和短的频繁模式，它都是有效的和可规模化的，并且比Apriori算法快约一个数量级。它也比树一投影算法快。树一投影算法递归地将数据库投影到投影数据库树。对FP增长方法的性能研究表明：对于挖掘长和短的频繁模式，3.5使用垂直数据格式挖掘频繁项集

Apriori和FP增长方法都从TID项集格式(即{TID:itemset})的事务集挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品集。这种数据格式称做水平数据格式(horizontaldataformat)。另处，数据也可以用项TID集格式(即{item:TID_set})表示，其中item是项的名称，而TID_set是包含item的事务的标识符的集合。这种格式称做垂直数据格式(verticaldataformat)。3.5使用垂直数据格式挖掘频繁项集Apriori和【例3.4】使用垂直数据格式挖掘频繁项集。考虑例3.1中表3-1的事务数据库D的水平数据格式。扫描一次该数据集可以将它转换成表3-3所示的垂直数据格式。通过取每对频繁单个项的TID集的交，可以对该数据集进行挖掘。最小支持度计数为2。由于表3-3的每个项都是频繁的，总共进行10次交运算，导致8个非空2项集，如表3-4所示。注意，项集{I1,I4}和{I3,I5)各只包含一个事务，因此它们都不属于频繁2项集的集合。【例3.4】使用垂直数据格式挖掘频繁项集。考虑例3.1中根据Apriori性质，一个给定的3项集是候选3项集，仅当它的每一个2项集子集都是频繁的。通过取这些候选3项集任意两个对应的2项集的TID集的交，得到表3-5，其中只有两个频繁3项集{I1,I2,I3:2}和{I1,I2,I5:2}。根据Apriori性质，一个给定的3项集是候选3项集，仅表3-3表3-1的事务数据库D的垂直数据格

表3-3表3-1的事务数据库D的垂直数据格表3-4垂直数据格式的2项集

表3-4垂直数据格式的2项集表3-5垂直数据格式的3项集

表3-5垂直数据格式的3项集例3.4解释了通过探查垂直数据格式挖掘频繁项集的过程。首先，通过扫描一次数据集将水平格式的数据转换成垂直格式。项集的支持度计数直接是项集的TID集的长度。从k=1开始，根据Apriori性质，使用频繁k项集来构造候选(k+1)项集。通过取频繁k项集的TID集的交计算对应的(k+1)项集的TID集。重复该过程，每次k增值1，直到不能再找到频繁项集或候选项集。例3.4解释了通过探查垂直数据格式挖掘频繁项集的过程。除了由频繁k项集产生候选(k+1)项集时利用Apriori性质之外，这种方法的另一优点是不需要扫描数据库来确定(k+1)项集(对于k≥1)的支持度。这是因为每个k项集的TID集携带了计算该支持度所需的完整信息。然而，TID集可能很大，需要大量空间，同时求大集合的交也需要大量计算时间。除了由频繁k项集产生候选(k+1)项集时利用Aprior为了进一步降低存储长TID集合的开销以及求交的计算开销，可以使用一种称做差集(diffset)的技术。该技术仅记录(k+1)项集的TID集与一个对应的k项集的TID集之差。例如，在例3.4中，有{I1}={T100,T400,T500,T700,T800,T900)和{I1,I2}={T100,T400,T800,T900}。二者的差集为diffset({I1,I2},{I1})={T500,T700}。这样，不必记录构成{I1}和{I2)交集的4个TID，可以使用差集仅记录代表{I1}和{I1,I2)差的两个TID。实验表明，在某些情况下，如当数据集包含许多稠密和长模式时，该技术可以显著地降低频繁项集垂直格式挖掘的总开销。为了进一步降低存储长TID集合的开销以及求交的计算开销，3.6挖掘闭频繁项集

频繁项集挖掘可能产生大量频繁项集，特别是当最小支持度阈值min_sup设置较低或数据集中存在长模式时尤其如此。闭频繁项集可以显著减少频繁项集挖掘所产生的模式数量，而且保持关于频繁项集的完整信息。也就是说，从闭频繁项集的集合可以很容易地推出频繁项集的集合和它们的支持度。这样，在许多实践中，更希望挖掘闭频繁项集的集合，而不是所有频繁项集的集合。

3.6挖掘闭频繁项集频繁项集挖掘可能产生大量频繁项1999年，Pasquier等人提出闭合项目集挖掘理论，并给出了基于这种理论的Close算法。他们给出了闭合项目集的概念，并讨论了这个闭合项目集格空间上的基本操作算子。

定义3.5设I={i1,i2,…,im}是一个项目集合，项集XI、YI。如果项集X是项集Y的真子集，亦XY，则称项集Y是项集X的真超项集。换而言之，X的每一项集包含在Y中，但是Y至少有一个项不在X中。1999年，Pasquier等人提出闭合项目集挖掘理论，定义3.6设S为一事务数据集，如果项集X不存在真超集Y使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。如果项集X在数据集S中是闭的和频繁的，则项集X是数据集S中的闭频繁集。

定义3.7如果X是频繁的，并且不存在超项集YX在S中是频繁的，项集X是数据集S中的极大频繁项集(极大项集)。定义3.6设S为一事务数据集，如果项集X不存在真超集Y设C是数据集S中满足最小支持度阈值min_sup的闭频繁项集的集合，令M是S中满足min_sup的极大频繁项集的集合。假定有C和M中的每个项集的支持度计数。注意，C和它的计数信息可以用来导出频繁项集的完整集合。因此，称C包含了关于频繁项集的完整信息。另一方面，M只存储了极大项集的支持度信息。通常，它并不包含其对应的频繁项集的完整的支持度信息。用下面的例子解释这些概念。设C是数据集S中满足最小支持度阈值min_sup的闭频繁【例3.5】假定事务数据库只有两个事务：{〈a1,a2,…,a100〉;〈a1,a2,…,a50〉}。设最小支持度计数阈值min_sup=1。发现两个闭频繁项集和它们的支持度，即C={{a1,a2,…,a100}:1;{a1,a2,…,a50}:2}。只有一个极大频繁项集：M={{a1,a2,…,a100}:1}。({a1,a2,…,a50}不能包含在极大频繁项集中，因为它有一个频繁超集{a1,a2,…,a100})，与上面相比，那里确定了2100-1个频繁项集，数量太大，根本无法枚举!【例3.5】假定事务数据库只有两个事务：{〈a1,a2闭频繁项集的集合包含了频繁项集的完整信息。例如，可以从C推出：(1){a2,a45:2}，因为{a2,a45}是{a1,a2,…,a50}的子集；(2){a8,a55:1}，因为{a8,a55}不是{a1,a2,…,a50}的子集，而是{a1,a2,…,a100}的子集。然而，从极大频繁项集只能断言两个项集({a2,a45}和{a8,a55})是频繁的，但是不能断言它们的实际支持度计数。闭频繁项集的集合包含了频繁项集的完整信息。例如，可以从C挖掘闭频繁项集的一种朴素方法是首先挖掘频繁项集的完全集，然后删除这样的频繁项集，即每个与现有的频繁项集有相同支持度的真子集。然而，这种方法的开销太大，如例3.5所示，为了得到一个长度为100的频繁项集，在开始删除冗余项集之前，这种方法首先必须导出2100-1个频繁项集。这是不能容忍的高开销。事实上，例3.5的数据集中的闭频繁项集的数量非常少。挖掘闭频繁项集(Close)算法的描述：挖掘闭频繁项集的一种朴素方法是首先挖掘频繁项集的完全集，(1)generatorsinFCCl=(1-itemsets)；//候选频繁闭合1项目集(2)FOR(i=1；FCCi.generators=Φ；i++){(3)doswresinFCCi=Φ;(4)supportsinFCCi=0;(5)FCCi=Gen_Closure(FCCi)；//计算FCC的闭合(6)FORallcandidatecloseditemsetsc∈FCCiD0BEGIN(7)IF(c.support≥minsupport)THENFCi=FCi∪{C}；//修剪小于最小支持度的项(1)generatorsinFCCl=(1-ite(8)FCGi+1=Gen_enerator(FCi)；//连接生成FCGi+1(9)}(10)FC=∪FCi(FCi.closure，FCi.support)；//返回FC(11)Derivingfrequentitemsets(FC，L)；(8)FCGi+1=Gen_enerator(FCi)在Close算法中，使用了迭代的方法：利用频繁闭合i项目集记为FCi，生成频繁闭合(i+1)项目集，记为FCi+1(i≥1)。首先找出候选1项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1中，再将它与自身连接，以得到候选频繁闭合2项目集FCC2，再经过修剪得出FC2，再用FC2推出FC3，如此继续下去，直到有某个值r使得候选频繁闭合r项目集FCCr为空，这时算法结束。在Close算法中，使用了迭代的方法：利用频繁闭合i项目在Close算法中调用了三个关键函数：Gen_Closure(FCCi)，Gen_Generator(FCi)和Derivingfrequentitemsets，它们分别描述如下：Gen_Closure(FCCi)函数(1)FORalltransactionst∈D{(2)Go=Subset(FCCi.generator，t)；(3)FORallgeneratorsp∈Go{(4)IF(P.closure=Φ)THENP.closure=t；在Close算法中调用了三个关键函数：Gen_Closu(5)ELESP.closure=P.closure∩t；(6)P.support++；(7)}(8)}(9)Answer=∪{c∈FCCi|C.closure≠Φ}；(5)ELESP.closure=P.closure∩函数Gen_Closure(FCCi)产生候选的闭合项目集，以用于频繁项目集的生成。设要查找FCCi的闭合，查找闭合的方法是：取出数据库的一项，记为t。如果FCCi的某一项对应的产生式p是t的子集而且它的闭合为空，则把t的闭合记为p的闭合。如果不为空，则把它的闭合与t的交集作为它的闭合。在此过程中也计算了产生式的支持度。最后将闭合为空的产生式从FCCk中删除。函数Gen_Closure(FCCi)产生候选的闭合项例如，数据库的某一项t={ABCD}，又有FCC2的某个产生式为{AC}，此时如果{AC}的闭合为空，则由于{AC}是{ABCD}的子集，则{AC}的闭合就是{ABCD}。再如，数据库中的一项t={ABC}。由于{AC}也是{ABC}的子集，而且已经知道{AC}的闭合为{ABCD}，所以计算出{ABC}就是{AC}的闭合(因为{ABCD}与{ABC}的交集为{ABC})。如果还存在其他数据库中的项，{AC}是它的子集，则继续计算交集，直到数据库的最后一项。例如，数据库的某一项t={ABCD}，又有FCC2的某个Gen_Generator函数(1)FORallgeneratorsp∈FCCi+1{(2)Sp=Subset(FCi.generator，p)；//取得p的所有i项子集(3)FORalls∈Sp(4)IF(p∈s.closure)THEN//如果p是它的i项子集闭合的子集(5)deletepfromFCCi+1.generator；//将它删除(6)}(7)Answer=∪{c∈FCCi+1}；Gen_Generator函数在该算法中，也使用了Apriori算法的两个重要步骤：连接和修剪。在由FCCi生成FCCi+1时，前面的连接和删除非频繁子集与Apriori算法虽然是相同的，但是它增加了一个新步骤，就是对于FCCi+1的每个产生式p，将FCi的产生式中是p的子集的产生式放到Sp中(因为这时已经进行了非频繁子集的修剪，所以p的所有i项子集都存在于FCi中)。对于Sp的每一项s，如果p是s的闭合的子集，则p的闭合就等于s的闭合，此时需要把它从FCCi+1中删除。在该算法中，也使用了Apriori算法的两个重要步骤：例如，FCC2的某一个产生式为{AB}，若将FC2的产生式中{AB}的子集挑选出来，记为Sp，则Sp={{A}{B}}。如果{AB}既不在A的闭合集中，也不在B的闭合集中，就应该保留，否则就应该从FCCi+1中删除。Derivingfrequentitemsets(FC，L)函数例如，FCC2的某一个产生式为{AB}，若将FC2的产生(1)k=０；(2)FORallfrequentcloseditemsetsc∈FC{(3)L‖c‖=L‖c‖∪{c}；//按项的个数归类(4)IF(k<‖c‖)THENk=‖c‖；//记下项目集包含的最多的个数(5)}(6)FOR(i=k；i>l；i--)(7)FORallitemsetsc∈Li

(8)FORall(i-1)subsetssofc//分解所有(i-1)项目集(9)IF(sLi-1)THEN{//不包含在Li-1中(10)s.support=c.support；//支持度不变(11)Li-1=Li-1∪{s}；//添加到Li-1中(12)}(13)L=∪Li；//返回所有的Li(1)k=０；Close算法最终需要通过频繁闭合项目集得到频繁项目集。首先对FC中的每个闭合项目集计算它的项目个数，把所有项目个数相同的归入相应的Li中。例如，闭合项目集{AB}，它的个数为2，则把它加入L2中。依此类推，将所有闭合项目集分配到相应的Li中，同时得到最大的个数记为k。然后从k开始，对每个Li中的所有项目集进行分解，找到它的所有的(i-1)项子集。对于每个子集，如果它不属于Li-1，则把它加入Li-1，直到i=2，就找到了所有的频繁项目集。为了能直观地了解Close算法的思想和具体技术，下面给出一个应用的实例。Close算法最终需要通过频繁闭合项目集得到频繁项目集。【例3.6】示例数据库如表3-6所示，然后跟踪算法的执行过程(其中最小支持度为2)。(1)计算FCC1各个产生式的闭合集和支持度。首先得到FCC1的产生式：FCC1的产生式为{A}、{B}、{C}、{D)、{E}。然后计算闭合集。【例3.6】示例数据库如表3-6所示，然后跟踪算法的执行例如，计算{A}的闭合。数据库中第一项{ABE}包含{A}，这时{A}的闭合首先得到{ABE}；第四项{ABD}包含{A}，所以取{ABD}和{ABE}的交集{AB}作为{A}的闭合集；第五项{AC}包含{A}，则取{AB}和{AC}的交集得到{A}作为{A}的闭合集；第7项是{AC}，交集为{A}；第8项{ABCE}与{A}的交集是{A}；第9项{ABC}与{A}的交集是{A}。这时到了最后一项，计算完成，得到{A}的闭合是{A}，并同时计算出{A}的支持度为6(可通过对出现的A的超集进行计数得到)。同样可以得到FCC1所有的闭合集与支持度(见表3-7)。例如，计算{A}的闭合。数据库中第一项{ABE}包含{A表3-6用于Close算法的示例数据库TIDItemsetTIDItemset1ABC6BC2BD7AC3BC8ABCE4ABD9ABC5AC表3-6用于Close算法的示例数据库TIDItemse表3-7示例数据库中FCC1所有的闭合集与支持数

GeneratorClosureSupport{A}{A}6{B}{B}7{C}{C}6{D}{BD}2{E}{ABE}2表3-7示例数据库中FCC1所有的闭合集与支持数Gene(2)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC1。本例得到的FC1与FCC1相同。(3)利用FCl的Generator生成FCC2。先用Apriori相同的方法生成2项目集。然后将FC1中是FCC2中的某个候选项的子集的项选出来，记为Sp。如果FCC2的这一项是Sp的项的闭合的子集则删除，得到FCC2。对于本例，FC1自身连接后得到候选项为：{AB}、{AC}、{AD}、{AE}、{BC}、{BD}、{BE}、{CD}、{CE}和{DE}，均不含有非频繁子集。再利用FC1筛选：由于{AE}是子集{E}的闭合{ABE}的子集，{BE}是子集{E}的闭合{ABE}的子集，所以将这两项删除，得到的候选项FCC2={{AB},{AC},AD}，{BC},{BD}，{CD},{CE},{DE}}。(2)进行修剪。(4)计算各产生式的闭合集和支持度。由于FCC2非空，{CD}和{DE}的闭合为空，所以将它们从FCC2中删除，且得到各产生式的支持度。表3-8给出了所有非空2项目集对应的闭合和支持数。(4)计算各产生式的闭合集和支持度。表3-8所有非空2项集的闭合与支持数GeneratorClosureSupport{AB}{AB}4{AC}{AC}4{AD}{ABD}1{BC}{BC}4{BD}{BD}2{CE}{ABCE}1表3-8所有非空2项集的闭合与支持数GeneratorC(5)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC2，这时{AD}和{CE}的支持度为1，被删除。FC2={{AB},{AC},{BC},{BD}}。(6)利用FC2的Generator生成FCC3，并进行裁减。FC2连接后得到：{{ABC},{BCD}}，其中的{BCD}有非频繁子集{CD}，所以将这项删除，剩下为{ABC}，得到的候选项FCC3={ABC}。(7)FCC3不为空，计算各产生式的闭合集和支持度。

ABC的闭合为{ABC}，支持度为2。(8)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC3。对于本例，FCC3只有一项，支持度为2，保留。(5)进行修剪。(9)利用FC3生成FCC4。

FCC4为空，算法结束。将所有的不重复的闭合加入到FC中，得到FC={{A},{B},{ABE},{BD},{C},{AB},{AC},{BC},{ABC}}。以下步骤为生成频繁项目集。(10)统计项目集元素数。将所有的闭合项目集按元素个数统计，得到L3={{ABC},{ABE}}；L2={{AB},{AC},{BC},{BD}}；L1={{A}，{B}，{C}}。最大个数为3。(9)利用FC3生成FCC4。(11)将L3的频繁项分解。先分解{ABC}的所有2项子集为{AB}、{AC}和{BC}。这三项均在L2中；再分解{ABE}的所有2项子集为{AB}、{AE}和{BE}，后两项不存在，将它们加入到L2中，它们的支持度等于{ABE}的支持度。最后得L2={{BD},{AB},{AC},{BC},{AE},{BE}}。(12)将L2的频繁项分解。方法同上，得L1={{A},{B},{C},{D},{E}}。(11)将L3的频繁项分解。3.7挖掘各种类型的关联规则

3.7.1挖掘多层关联规则对于许多应用，由于数据的稀疏性，在低层或原始抽象层的数据项之间很难找出强关联规则；在较高的抽象层发现的强关联规则可能提供常识知识，而且，对一个用户代表常识的知识，对另一个用户可能是新颖的。因此，数据挖掘系统应当提供一种能力，能在多个抽象层挖掘关联规则，并有足够的灵活性，易于在不同的抽象空间转换。3.7挖掘各种类型的关联规则3.7.1挖掘多层关联规则【例3.7】挖掘多层关联规则。假定给定表3-9事务数据的任务相关集合，它是AllElectronics商店的销售数据，每个事务给出了购买的商品。商品的概念分层在图3[CD*2]6中给出。概念分层定义了由低层概念集到高层更一般概念的映射序列，可以通过将数据中的低层概念用概念分层中的高层概念(或祖先)替换，对数据进行泛化。图3-6的概念分层有5层，分别指层0～层4，从根节点all为层0(最一般的抽象层)开始。这里，层1包括computer、soft