1、第第3章关联规则挖掘章关联规则挖掘 数据挖掘原理、算法及应用第3章 关联规则挖掘第第3章关联规则挖掘章关联规则挖掘 3.1基基 本本 概概 念念 交易数据库又称为事务数据库，尽管它们的英文名词一样，但是事务数据库更具有普遍性。例如，病人的看病记录、基因符号等用事务数据库更贴切。因此，下面的叙述更多使用事务数据库这一名词，而不用交易数据库这个名词。第第3章关联规则挖掘章关联规则挖掘 一个事务数据库中的关联规则挖掘可以描述如下：设I=i1,i2,im 是一个项目集合，事务数据库D=t1,t2,tn 是由一系列具有惟一标识的TID事务组成。每一个事务ti(i=1,2,n)都对应I上的一个子集。定义3
2、.1设I1 I，项目集(Itemsets)I1在数据集D上的支持度(Support)是包含I1的事务在D中所占的百分比，即式中：|表示集合中元素数目。(3.1)第第3章关联规则挖掘章关联规则挖掘 定义3.2对项目集I，在事务数据库D中所有满足用户指定的最小支持度(Minsupport)的项目集，即不小于Minsupport的I的非空子集，称为频繁项目集(Frequent Itemsets)或大项目集(Larg Itemsets)。定义3.3一个定义在I和D上，形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来定义的。所谓规则的可信度，是指包含I1和I2的事务数
3、与包含I1的事务数之比，即)(support)(support)(confidence12121IIIII(3.2)第第3章关联规则挖掘章关联规则挖掘 定义定义3.4D在I上满足最小支持度和最小置信度(Minconfidence)的关联规则称为强关联规则(Strong Association Rules)。通常所说的关联规则一般是指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。第第3章关联规则挖掘章关联规则挖掘(1)发现频繁项目集：通过用户给定的最小支持度，寻找所有频繁项目集，即满足支
4、持度Support不小于Minsupport的所有项目子集。发现所有的频繁项目集是形成关联规则的基础。(2)生成关联规则：通过用户给定的最小可信度，在每个最大频繁项目集中，寻找置信度不小于Minconfidence的关联规则。第第3章关联规则挖掘章关联规则挖掘 3.2关联规则挖掘算法关联规则挖掘算法 3.2.1项目集空间理论项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集空间理论。理论的核心为：频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。这个理论一直作为经典的数据挖掘理论被应用。第第3章关联规则挖掘章关联规则挖掘 定理定理3.1如果项目集X是频繁项目集，那
5、么它的所有非空子集都是频繁项目集。证明证明设X是一个项目集，事务数据库D中支持X的元组(记录)数为S。设X的任一非空子集YX，事务数据库D中支持Y的元组(记录)数为S1。根据项目集支持度的定义，很容易知道支持X的元组一定支持Y，所以S1S，即support(Y)support(X)按假设，项目集X是频繁项目集，即support(X)minsupport所以support(Y)support(X)minsupport，因此Y是频繁项目集。第第3章关联规则挖掘章关联规则挖掘 定理定理3.2如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明证明设事务数据库D中支持X的元组数为S。设X
6、的任一超集Z X，事务数据库D中支持Z的元组数为S2。根据项目集支持度的定义，很容易知道支持Z的元组一定支持X，所以S2S，即support(Z)support(X)第第3章关联规则挖掘章关联规则挖掘 按假设，项目集X是非频繁项目集，即support(X)minsupport所以support(Z)support(X)minsupport，因此Z不是频繁项目集。1993年，Agrawal等人在提出关联规则概念的同时，给出了相应的挖掘算法AIS，但性能较差。1994年，他们依据上述两个定理，提出了著名的Apriori算法，Apriori算法至今仍然作为关联规则挖掘的经典算法，其他算法均是在此基础
7、上进行改进的。第第3章关联规则挖掘章关联规则挖掘 3.2.2经典的发现频繁项目集算法经典的发现频繁项目集算法Apriori算法是R.Agrawal和R.Strikant于1994年提出的布尔关联规则挖掘频繁项集的原创性算法。算法的基本思想：基于频繁项目集性质的先验知识，使用由下到上逐层搜索的迭代方法，k项集用于搜索k+1项集。首先，扫描数据库，统计每一个项发生的数目，找出满足最小值支持度的项，找出频繁1项集，计作L1；然后，基于L1找出频繁2项集的集合L2，基于L2找出频繁3项集的集合L3，如此下去，直到不能找到频繁k项集Lk。找每一个Lk需要一次数据库全扫描。第第3章关联规则挖掘章关联规则挖
8、掘 Apriori算法的核心由连接步和剪枝步组成。(1)连接步：为找频繁项集Lk(k2)，先通过将Lk-1与自身连接产生候选K项集的集合Ck。设l1和l2是Lk-1中的项集，即l1Lk-1，l2Lk-1。Apriori算法假定事务或项集中的项按照字典顺序排列，设lij表示li中的第j项。对于k-1项集li，对应的项排序为：li1li2lik-1。Lk-1与自身连接使用Lk-1Lk-1来表示。第第3章关联规则挖掘章关联规则挖掘 如果l1Lk-1，l2Lk-1中的前k-2个元素相同，则称l1、l2是可连接的，即l11=l21l12=l22l1k-1l2k-1。条件l1k-1l2k-1可以保证不产生
9、重复，而按照L1，L2，Lk-1，Lk，Ln次序寻找频繁项集可以避免对事务数据库中不可能发生的项集所进行的搜索和统计的工作。连接l1、l2的结果项集是l11、l12、l1k-1、l2k-1。第第3章关联规则挖掘章关联规则挖掘(2)剪枝步：由候选K项集的集合Ck产生频繁K项集Lk。Ck是Lk的超集，也就是说Ck的成员可以不是频繁的，但所有的频繁项集Lk都包含在Ck中。扫描数据库D，统计Ck中每一个候选项集的计数，从而确定Lk。然而Ck集合中元素数目可能很大，这样所涉及的计算量就很大。为压缩Ck，可以利用频繁项目集性质的先验知识：任何非频繁的(k-1)项集都不是频繁k项集的子集。第第3章关联规则挖
10、掘章关联规则挖掘 因此，如果候选k项集Ck的(k-1)项子集不在Lk-1中，则该候选不可能是频繁的，从而可以从Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例如，如果2项目集C2=AB,AD,AC,BD，而对于新产生3项目集中的元素ABC不需要加入到C3中，因为它的2项子集BC不在C2中。而对于新产生的元素ABD应该加入到C3中，因为它的所有2项子集都在C2中。第第3章关联规则挖掘章关联规则挖掘【例3.1】表3-1为某一超市销售事务数据库D，使用Apriori算法发现D中频繁项目集。问题分析：事务数据库D中有9个事务，即|D|=9。超市中有5件商品可供顾客选择，即I=I1,I2
11、,I3,I4,I5，且|I|=5。设最小支持数minsup_count=2，则对应的最小支持度为2/92.2%。第第3章关联规则挖掘章关联规则挖掘 表表3-1某一超市销售事务数据库某一超市销售事务数据库D 第第3章关联规则挖掘章关联规则挖掘 事务数据库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中，选取支持数不小于最小支持
12、数minsup_count=2的候选1项目集作为频繁1项目集L1,L1=I1,I2,I3,I4,I5。第第3章关联规则挖掘章关联规则挖掘 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算法使用连接L1L1产生候选项目集C2。L1L1连接运算要求两个连接的项集共享0个项，LkLk运算中要求两个连接的项集共享k-1个项。对候选项目
13、集C2中的每一个2候选项目集，在数据库D进行扫描，统计它们的支持数。第第3章关联规则挖掘章关联规则挖掘 4)2频繁项目集L2的生成在2候选项目集C2中，选取支持数不小于最小支持数minsup_count=2的候选项目集作为2频繁项目集L2。第第3章关联规则挖掘章关联规则挖掘 5)3候选项目集C3的生成由2频繁项目集L2生成3候选项目集C3。首先按照连接步定义计算C3=L2L2=I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I2,I3,I5,I2,I4,I5；然后按照剪枝步的方法，频繁项集的所有子集也必须是频繁的，可以确定后4个候选不可能是频繁的，从而可以把它们从C3中
14、删除，这样扫描数据库D时，不必再统计它们的数目。第第3章关联规则挖掘章关联规则挖掘 由于Apriori算法采用由下到上、逐层搜索技术，当给定候选k项集，只须检查它们的k-1项子集是否频繁。对候选项目集C3中的每一个3候选项目集，在数据库D进行扫描，统计它们的支持数。第第3章关联规则挖掘章关联规则挖掘 6)3频繁项目集L3的生成在3候选项目集C3中，选取支持数不小于最小支持数minsup_count=2的候选项目集作为3频繁项目集L3。7)4候选项目集C4的生成计算C4=L3L3=I1,I2,I3,I5，因为它的子集I2,I3,I5不是频繁的，应该从C4中删除。这样C4，算法终止，找出了所有的频
15、繁项集。这样一个寻找所有频繁项集的过程如图3-1所示。第第3章关联规则挖掘章关联规则挖掘 图3-1搜索候选项集和频繁项集过程第第3章关联规则挖掘章关联规则挖掘 以下为Apriori算法和它的相关过程的伪代码。算法算法3.1Apriori(发现频繁项目集)。输入：数据集D、最小支持数minsup_count。输出：频繁项目集L。(1)L1=large 1-itemsets;/所有支持数不小于minsup_count的1项目集(2)FOR(k=2；Lk-1；k+)(3)Ck=apriori-gen(Lk-1);/Ck是包含k个元素的候选项目集第第3章关联规则挖掘章关联规则挖掘(4)FOR all
16、transactions tD/扫描数据集D用于计数(5)Ct=subset(Ck,t);/Ct是所有t中包含Ck的候选项目集(6)FOR all candidates cCt c.count+;/计数(7)(8)Lk=cCkc.countminsup_count(9)(10)RETURN L=Lk；第第3章关联规则挖掘章关联规则挖掘 Apriori算法中步骤(1)找出频繁1项集的集合L1；步骤(2)(9)实现由Lk-1生成Ck，再找出Lk；步骤(3)调用了apriori-gen(Lk-1)函数，是为了通过(k-1)频繁项目集产生k候选集，并删除包含非频繁子集的k候选集；步骤(4)对所有的候选
17、扫描数据集D用于计数；步骤(5)对每一个事务使用subset函数找出事务中是候选的所有子集；步骤(6)对这样的候选累加计数；步骤(8)找出满足最小支持度的候选；步骤(10)形成频繁项集的集合L。第第3章关联规则挖掘章关联规则挖掘 算法算法3.2apriori-gen(Lk-1)(候选集产生)。输入：(k-1)频繁项目集Lk-1。输出：k侯选项目集Ck。(1)FOR all itemset l1Lk-1(2)FOR all itemset l2Lk-1(3)IF(l11=l21l12=l22l1k-12)THEN generateRules(lkL,xm-1X,minConfidence);(7
18、)第第3章关联规则挖掘章关联规则挖掘 利用频繁项目集生成关联规则就是逐一测试在所有频繁项集中可能生成的关联规则、对应的支持度、置信度参数。算法3.5实际上采用深度优先搜索方法来递归生成关联规则，当然，同样也可以使用广度优先搜索方法来递归生成关联规则，读者可以自己尝试来完成。第第3章关联规则挖掘章关联规则挖掘【例3.2】对于例3.1事务数据库D，假定发现的频繁项集l=I1,I2,I5，试找出由l产生的所有关联规则。频繁项集l=I1,I2,I5的所有非空子集为I1,I2、I1,I5、I2,I5、I1、I2、I5则其对应的关联规则和置信度如下：(1)I1I2 I5，confidence=2/4=50
19、%;(2)I1I5 I2，confidence=2/2=100%;(3)I2I5 I1，confidence=2/2=100%;第第3章关联规则挖掘章关联规则挖掘(4)I1 I2I5，confidence=2/6=33%;(5)I2 I1I5，confidence=2/7=29%;(6)I5 I1I2，confidence=2/2=100%。如果最小置信度阈值为70，则只有(2)、(3)和(6)为强关联规则。由频繁项目集生成关联规则的优化问题主要集中在减少不必要的规则生成尝试方面。第第3章关联规则挖掘章关联规则挖掘 定理定理3.3设有频繁项目集l，项目集X l，X1为X的一个子集，即X1X。如
20、果关联规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章关联规则挖掘章关联规则挖掘 由于X(l-X)不是强关联规则，即confidence(X(l-X)minConfidence所以 confidence(X1(l-X1)confidence(X(l-X)
21、2&confidence(xm-1 (l-xm-1)minConfidence)作为递归结束的判断条件，读者可以自己尝试来完成。第第3章关联规则挖掘章关联规则挖掘 定理定理3.4 设有项目集X，X1是X的一个子集，即X1X，如果规则Y X是强规则，那么规则Y X1一定是强规则。证明证明由支持度定义可知，一个项目集的子集的支持度一定大于等于它的支持度，即support(X1Y)support(XY)所以confidence(YX)=support(XY)/support(Y)support(X1Y)/support(Y)=support(X1Y)第第3章关联规则挖掘章关联规则挖掘 由于YX是强规
22、则，即confidence(Y X)minConfidence所以corfidence(X1Y)confidence(YX)minConfidence因此，“YX1”也是强规则。由定理3.4可知，在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定是强规则的尝试。这个定理也保证把测试的注意点放在判断最大频繁项目集的合理性上。实际上，只要从所有最大频繁项目集出发去测试可能的关联规则即可，因为其他频繁项目集生成的规则的右项一定包含在对应的最大频繁项目集生成的关联规则右项中。第第3章关联规则挖掘章关联规则挖掘 3.3Apriori改进算法改进算法 3.3.1Apriori算法的瓶颈算法的瓶颈
23、Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。但是随着研究的深入，它的缺点也暴露出来。Apriori算法有两个致命的性能瓶颈。(1)多次扫描事务数据库，需要很大的IO负载。对每次k循环，候选集Ck中的每个元素都必须通过扫描一次数据库来验证其是否加入Lk。假如一个频繁大项目集包含10个项，那么就至少需要扫描事务数据库10遍。第第3章关联规则挖掘章关联规则挖掘(2)可能产生庞大的候选集。由Lk-1产生k候选集Ck是呈指数增长的，例如104个1频繁项目集,Apriori算法能产生多达107个2候选集。如此大的候选集对时间和主存空间都是一种挑战。因此，包括Agrawal在内
24、的许多学者提出了Apriori算法的改进方法。第第3章关联规则挖掘章关联规则挖掘 3.3.2改进算法改进算法1.基于散列的技术基于散列的技术(散列项集到对应的桶中散列项集到对应的桶中)一种基于散列的技术可以用于压缩候选k项集Ck(k1)。例如，当扫描数据库中的每个事务，由C1中的候选1项集产生频繁1项集L1时，可以对每个事务产生所有的2项集，将它们散列(即映射)到散列表结构的不同桶中，并增加对应的桶计数(如图3-2所示)。在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁的，因而应当从候选项集中删除。这种基于散列的技术可以显著压缩要考察的候选k项集。第第3章关联规则挖掘章关联规则挖掘 图
25、3-2候选2项集的散列表第第3章关联规则挖掘章关联规则挖掘 2.事务压缩事务压缩不包含任何频繁k项集的事务不可能包含任何频繁(k+1)项集。因此，这种事务在其后考虑中，可以加上标记或删除，因为产生j(jk)项集的数据库扫描不再需要它们。第第3章关联规则挖掘章关联规则挖掘 3.划分划分使用划分技术只需要两次数据库扫描，以挖掘频繁项集(如图3-3所示)。它包含两个阶段。在阶段，算法将D中的事务分成n个非重叠的划分。如果D中事务的最小支持度阈值为min_sup，则一个划分的最小支持度计数为min_sup乘以该划分中的事务数。对每个划分，找出该划分内的所有频繁项集。这些称做局部频繁项集(Local F
26、requent Itemset)。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。对于k=1，2，n 找出所有的局部频繁项集只需要扫描一次数据库。第第3章关联规则挖掘章关联规则挖掘 图3-3通过划分数据进行挖掘第第3章关联规则挖掘章关联规则挖掘 局部频繁项集可能是也可能不是整个数据库D的频繁项集。D的任何频繁项必须作为局部频繁项集至少出现在一个划分中。这样，所有的局部频繁项集是D的候选项集。所有划分的频繁项集的集合形成D的全局候选项集。在阶段，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。划分的大小和划分的数目以每个划分能够放入内存为原则来确定，这样每
27、阶段只需要读一次。第第3章关联规则挖掘章关联规则挖掘 4.抽样抽样抽样方法的基本思想：选取给定数据D的随机样本S，然后在S中搜索频繁项集。用这种方法，虽然牺牲了一些精度但换取了有效性。样本S的大小选取使得可以在内存中搜索S的频繁项集。这样，总共只需要扫描一次S中的事务。由于搜索S中而不是D中的频繁项集，可能丢失一些全局频繁项集。为减少这种可能性，使用比最小支持度低的支持度阈值来找出S中局部的频繁项集(记作LS)。然后，数据库的其余部分用于计算LS中每个项集的实际频率。使用一种机制来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，则只需要扫描一次D。否则，可以做第二次
28、扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须频繁运行时，抽样方法特别合适。第第3章关联规则挖掘章关联规则挖掘 5.动态项集计数动态项集计数动态项集计数技术将数据库划分为用开始点标记的块。不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已计数的所有项集的支持度，如果一个项集的所有子集已确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。第第3章关联规则挖掘章关联规则挖掘 3.4不候选产生挖掘频繁项集不候选产生挖掘频繁项集 频繁模式增长(FrequentPat
29、tern Growth)，或简称FP增长，试图设计一种方法，挖掘全部频繁项集而不产生候选。它采取如下分治策略：首先，将提供频繁项的数据库压缩到一棵频繁模式树(或FP树)，但仍保留项集关联信息。然后，将压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库)，每个与一个频繁项或“模式段”关联，并分别挖掘每个条件数据库。第第3章关联规则挖掘章关联规则挖掘【例3.3】FP增长(发现频繁项集而不产生候选)。使用频繁模式增长方法，重新考察例3.1中表3-1的事务数据库D的挖掘。数据库的第一次扫描与Apriori相同，它导出频繁项(1项集)的集合和支持度计数(频率)。设最小支持度计数为2。频繁项的集
30、合按支持度计数的递减序排序。结果集或列表记作L，L=I2:7,I1:6,I3:6,I4:2,I5:2。第第3章关联规则挖掘章关联规则挖掘 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链接到根，I
31、4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀I2。这样，将节点I2的计数增加1，并创建一个新节点I4:1作为I2:2的子女链接。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数增加1，为在前缀之后的项创建节点和链接。第第3章关联规则挖掘章关联规则挖掘 为方便树遍历，创建一个项头表，使每项通过一个节点链指向它在树中的位置。扫描所有的事务之后得到的树如图3-4所示，带有相关的节点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP树问题。第第3章关联规则挖掘章关联规则挖掘 图3-4存放压缩的频繁模式信息的FP树第第3章关联规则挖掘章关联规则挖掘 FP树的挖掘过程：由每
32、个长度为1的频繁模式(初始后缀模式)开始，构造它的条件模式基(一个“子数据库”由FP树中与后缀模式一起出现的前缀路径集组成)，然后，构造它的条件FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。第第3章关联规则挖掘章关联规则挖掘 该FP树的挖掘总结在表3-2中，细节如下。首先考虑I5，它是L中的最后一项，而不是第一个。从表的后端开始的原因随着解释FP树挖掘过程就会清楚。I5出现在图3-3的FP树的两个分枝(I5的出现沿它的节点链容易找到)。这些分枝形成的路径是I2,I1,I5:1和I2,I1,I3,I5：1。因此，考虑I5为后缀，它的两个对应前缀路径是I2
33、,I1:1和I2,I1,I3:1，形成I5的条件模式基。它的条件FP树只包含单个路径I2:2,I1:2；不包含I3，因为它支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2,I5:2,I1,I5:2,I2,I1,I5:2。第第3章关联规则挖掘章关联规则挖掘 表表3-2通过创建条件子模式基挖掘通过创建条件子模式基挖掘FP树树 第第3章关联规则挖掘章关联规则挖掘 I4的两个前缀路径形成条件模式基I2 I1:1,I2:1,产生单节点的条件FP树I2:2，并导出一个频繁模式I2,I4:2。注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁
34、模式在考察I5时已经分析过。第第3章关联规则挖掘章关联规则挖掘 与以上分析类似，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中。第第3章关联规则挖掘章关联规则挖掘 图3-5具有条件节点I3的条件FP树第第3章关联规则挖掘章关联规则挖掘 算法算法3.6FP增长。使用FP树，通过模式段增长挖掘频繁模式。输入：事务数据库D；最小
35、支持度计数阈值min_sup。输出：频繁模式的完全集。方法：(1)按以下步骤构造FP树：扫描事务数据库D一次。收集频繁项的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。创建FP树的根节点，以“null”标记它。对于D中每个事务Trans，执行：第第3章关联规则挖掘章关联规则挖掘 选择Trans中的频繁项，并按L中的次序排序。设排序后的Trans中频繁项列表为p|P，其中p是第一个元素，而P是剩余元素的列表。调用insert_tree(p|P,T)。该过程执行情况如下：如果T有一个子女N使得N.item-name=p.item-name，则N的计数增加1，否则创建一个新
36、节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同item-name的节点。如果P非空，递归地调用insert tree(P,N)。第第3章关联规则挖掘章关联规则挖掘(2)FP树的挖掘通过调用FP_growth(FP-tree，null)实现。该过程实现如下：procedure FP_growth(Tree，)IF Tree含单个路径P then FOR each路径P中节点的每个组合(记作)产生模式，其支持度计support_count等于中节点的最小支持度计数；ELSE FOR Tree的头表中的每个i 第第3章关联规则挖掘章关联规则挖掘 产生模式=i，其支
37、持度计数support_count=i.support_count;构造的条件模式基，然后构造的条件FP树Tree，IF Tree then 调用FP-growth(Tree,)；第第3章关联规则挖掘章关联规则挖掘 FP增长方法将发现长频繁模式的问题转换成递归地搜索一些较短模式，然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP树有时是不现实的。一种有趣的可选方案是首先将数据库划分成投影数据库的集合，然后在每个投影数据库构造FP树并挖掘它。如果投影数据库的FP树还不能放进内存，该过程可以递归地用于投影数据库。第第3章关联规则挖
38、掘章关联规则挖掘 对FP增长方法的性能研究表明：对于挖掘长和短的频繁模式，它都是有效的和可规模化的，并且比Apriori算法快约一个数量级。它也比树一投影算法快。树一投影算法递归地将数据库投影到投影数据库树。第第3章关联规则挖掘章关联规则挖掘 3.5使用垂直数据格式挖掘频繁项集使用垂直数据格式挖掘频繁项集 Apriori和FP增长方法都从TID项集格式(即TID:itemset)的事务集挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品集。这种数据格式称做水平数据格式(horizontal data format)。另处，数据也可以用项TID集格式(即item:TI
39、D_set)表示，其中item是项的名称，而TID_set是包含item的事务的标识符的集合。这种格式称做垂直数据格式(vertical data format)。第第3章关联规则挖掘章关联规则挖掘【例3.4】使用垂直数据格式挖掘频繁项集。考虑例3.1中表3-1的事务数据库D的水平数据格式。扫描一次该数据集可以将它转换成表3-3所示的垂直数据格式。通过取每对频繁单个项的TID集的交，可以对该数据集进行挖掘。最小支持度计数为2。由于表3-3的每个项都是频繁的，总共进行10次交运算，导致8个非空2项集，如表3-4所示。注意，项集I1,I4和I3,I5)各只包含一个事务，因此它们都不属于频繁2项集的
40、集合。第第3章关联规则挖掘章关联规则挖掘 根据Apriori性质，一个给定的3项集是候选3项集，仅当它的每一个2项集子集都是频繁的。通过取这些候选3项集任意两个对应的2项集的TID集的交，得到表3-5，其中只有两个频繁3项集I1,I2,I3:2和I1,I2,I5:2。第第3章关联规则挖掘章关联规则挖掘 表表3-3表表3-1的事务数据库的事务数据库D的垂直数据格的垂直数据格 第第3章关联规则挖掘章关联规则挖掘 表表3-4垂直数据格式的垂直数据格式的2项集项集 第第3章关联规则挖掘章关联规则挖掘 表表3-5垂直数据格式的垂直数据格式的3项集项集 第第3章关联规则挖掘章关联规则挖掘 例3.4解释了通
41、过探查垂直数据格式挖掘频繁项集的过程。首先，通过扫描一次数据集将水平格式的数据转换成垂直格式。项集的支持度计数直接是项集的TID集的长度。从k=1开始，根据Apriori性质，使用频繁k项集来构造候选(k+1)项集。通过取频繁k项集的TID集的交计算对应的(k+1)项集的TID集。重复该过程，每次k增值1，直到不能再找到频繁项集或候选项集。第第3章关联规则挖掘章关联规则挖掘 除了由频繁k项集产生候选(k+1)项集时利用Apriori性质之外，这种方法的另一优点是不需要扫描数据库来确定(k+1)项集(对于k1)的支持度。这是因为每个k项集的TID集携带了计算该支持度所需的完整信息。然而，TID集
42、可能很大，需要大量空间，同时求大集合的交也需要大量计算时间。第第3章关联规则挖掘章关联规则挖掘 为了进一步降低存储长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。实验表明，在某些
43、情况下，如当数据集包含许多稠密和长模式时，该技术可以显著地降低频繁项集垂直格式挖掘的总开销。第第3章关联规则挖掘章关联规则挖掘 3.6挖掘闭频繁项集挖掘闭频繁项集 频繁项集挖掘可能产生大量频繁项集，特别是当最小支持度阈值min_sup设置较低或数据集中存在长模式时尤其如此。闭频繁项集可以显著减少频繁项集挖掘所产生的模式数量，而且保持关于频繁项集的完整信息。也就是说，从闭频繁项集的集合可以很容易地推出频繁项集的集合和它们的支持度。这样，在许多实践中，更希望挖掘闭频繁项集的集合，而不是所有频繁项集的集合。第第3章关联规则挖掘章关联规则挖掘 1999年，Pasquier等人提出闭合项目集挖掘理论，并
44、给出了基于这种理论的Close算法。他们给出了闭合项目集的概念，并讨论了这个闭合项目集格空间上的基本操作算子。定义定义3.5设I=i1,i2,im 是一个项目集合，项集X I、Y I。如果项集X是项集Y的真子集，亦X Y，则称项集Y是项集X的真超项集。换而言之，X的每一项集包含在Y中，但是Y至少有一个项不在X中。第第3章关联规则挖掘章关联规则挖掘 定义定义3.6设S为一事务数据集，如果项集X不存在真超集Y使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。如果项集X在数据集S中是闭的和频繁的，则项集X是数据集S中的闭频繁集。定义定义3.7如果X是频繁的，并且不存在超项集YX在S中
45、是频繁的，项集X是数据集S中的极大频繁项集(极大项集)。第第3章关联规则挖掘章关联规则挖掘 设C是数据集S中满足最小支持度阈值min_sup的闭频繁项集的集合，令M是S中满足min_sup的极大频繁项集的集合。假定有C和M中的每个项集的支持度计数。注意，C和它的计数信息可以用来导出频繁项集的完整集合。因此，称C包含了关于频繁项集的完整信息。另一方面，M只存储了极大项集的支持度信息。通常，它并不包含其对应的频繁项集的完整的支持度信息。用下面的例子解释这些概念。第第3章关联规则挖掘章关联规则挖掘【例3.5】假定事务数据库只有两个事务：a1,a2,a100;a1,a2,a50。设最小支持度计数阈值m
46、in_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章关联规则挖掘章关联规则挖掘 闭频繁项集的集合包含了频繁项集的完整信息。例如，可以从C推出：(1)a2,a45:2，因为 a2,a45是a1,a2,a50的子集；(2)a8,a55:1，因为a8,a55不是a1,a2,a50的子集，而是a1,a2,a100的子集。然而，从极
47、大频繁项集只能断言两个项集(a2,a45和a8,a55)是频繁的，但是不能断言它们的实际支持度计数。第第3章关联规则挖掘章关联规则挖掘 挖掘闭频繁项集的一种朴素方法是首先挖掘频繁项集的完全集，然后删除这样的频繁项集，即每个与现有的频繁项集有相同支持度的真子集。然而，这种方法的开销太大，如例3.5所示，为了得到一个长度为100的频繁项集，在开始删除冗余项集之前，这种方法首先必须导出2100-1个频繁项集。这是不能容忍的高开销。事实上，例3.5的数据集中的闭频繁项集的数量非常少。挖掘闭频繁项集(Close)算法的描述：第第3章关联规则挖掘章关联规则挖掘(1)generators inFCCl=(1
48、-itemsets)；/候选频繁闭合1项目集(2)FOR(i=1；FCCi.generators=；i+)(3)doswres in FCCi=;(4)supports in FCCi=0;(5)FCCi=Gen_Closure(FCCi)；/计算FCC的闭合(6)FOR all candidate closed itemsets cFCCi D0 BEGIN(7)IF(c.supportminsupport)THEN FCi=FCiC；/修剪小于最小支持度的项第第3章关联规则挖掘章关联规则挖掘(8)FCGi+1=Gen_enerator(FCi)；/连接生成FCGi+1(9)(10)FC=F
49、Ci(FCi.closure，FCi.support)；/返回FC(11)Deriving frequent itemsets(FC，L)；第第3章关联规则挖掘章关联规则挖掘 在Close算法中，使用了迭代的方法：利用频繁闭合i项目集记为FCi，生成频繁闭合(i+1)项目集，记为FCi+1(i1)。首先找出候选1项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1中，再将它与自身连接，以得到候选频繁闭合2项目集FCC2，再经过修剪得出FC2，再用FC2推出FC3，如此继续下去
50、，直到有某个值r使得候选频繁闭合r项目集FCCr为空，这时算法结束。第第3章关联规则挖掘章关联规则挖掘 在Close算法中调用了三个关键函数：Gen_Closure(FCCi)，Gen_Generator(FCi)和Deriving frequent itemsets，它们分别描述如下：Gen_Closure(FCCi)函数(1)FOR all transactions tD(2)Go=Subset(FCCi.generator，t)；(3)FOR all generators pGo(4)IF(P.closure=)THEN P.closure=t；第第3章关联规则挖掘章关联规则挖掘(5)E
