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

1、数据挖掘与模式识别数据挖掘与模式识别Data Mining and Pattern Recognition 三、关联规则挖掘三、关联规则挖掘Association Rules MiningOUTLINE关联规则的基本概念与基础理论关联规则的基本概念与基础理论1 1Apriori算法原理算法原理 2 2 Apriori算法实例分析算法实例分析3 3 Apriori算法源程序分析算法源程序分析4 4 Apriori算法的特点及应用算法的特点及应用5 5OUTLINE关联规则的评价关联规则的评价7 7序列模式序列模式挖掘挖掘算法算法8 8关联规则挖掘其它关联规则挖掘其它算法算法9 9FP -增长算法

2、增长算法6 6关联规则的基本概念与基础理论关联规则的基本概念与基础理论 关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一，是数据挖掘的其它研究分支的基础。 最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。 关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mi

3、ning）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。关联规则的基本概念与基础理论关联规则的基本概念与基础理论购物篮分析实例购物篮分析实例 通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。购物购物篮关篮关联分联分析实析实例图例图Customer

4、buys breadCustomerbuys bothCustomerbuys milk“牛奶与牛奶与面包面包”的的关联规则关联规则关联规则的基本概念与基础理论关联规则的基本概念与基础理论购物篮分析实例购物篮分析实例 一个大的项目集，例如，超市里售卖的东西. 一个大的篮子集，每个篮子都是一个小的项目集，例如，一个顾客一天买的东西. 最简单的问题：找到这个篮子里经常出现的项目集. 项目集 I 的支持度计数= 含有 I 里所有项目的篮子数量. 给定一个最小支持度计数门槛s，在 s 个篮子里出现的项目的集合，称为频繁项集关联规则的基本概念与基础理论关联规则的基本概念与基础理论购物篮分析实例购物篮分析

5、实例 Items=milk, coke, pepsi, beer, juice. Support s= 3 baskets.B1 = m, c, b B2 = m, p, jB3 = m, b B4 = c, jB5 = m, p, b B6 = m, c, b, jB7 = c, b, j B8 = c, b Frequent itemsets: m, c, b, j, m, b, c, b, c, j.关联规则的基本概念与基础理论关联规则的基本概念与基础理论购物篮分析实例购物篮分析实例 真正的市场篮子：连锁店保存有关客户同时购买的海量信息。讲述了典型的客户浏览商店，让他们定位诱人的项目.建

6、议搭配的“招数”，例如，尿布的打折销售并提高啤酒的价格.篮子数据分析，交叉营销，销售活动分析关联规则的基本概念与基础理论关联规则的基本概念与基础理论购物篮分析实例购物篮分析实例 “市场篮子”是将任何两个概念之间的多对多关系模型化的一个抽象：“项目”和“篮子。”项目不需要被包含在篮子里. 唯一不同的是，我们数与一个篮子相关的同时出现的项目，而不是相反. 规模问题沃尔玛卖100,000个项目并且储存上亿个篮子.网络有超过100,000,000单词和上亿网页关联规则的基本概念与基础理论关联规则的基本概念与基础理论关联规则挖掘用来发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间存在关联，那

7、么其中一项的属性就可以依据其他属性值进行预测。关联规则挖掘问题两个子问题： 第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集； 第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集是关联规则发现算法的核心。什么是频繁模式分析什么是频繁模式分析? 频繁模式:在数据集中经常出现的模式（项目集，子序列，子结构等）。 在论文中最早提出频繁项集和关联规则挖掘 R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of

8、 items in large databases. SIGMOD93. 揭示了数据集的一个内在的重要的特性 形成了许多重要的数据挖掘任务的基础关联，相关和因果关系分析顺序，结构（例如，子图）模式时空，多媒体，时间序列，数据流模式分析分类：关联分类聚类分析：频繁模式聚类语义数据压缩：成簇关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念1.项与项集 数据库中不可分割的最小单位信息称为项（或项目），项的集合称为项集。 设I=i1,i2,im为一个项目集合(Set of Items, 项集)，其中i1,i2,im称为项目(item,项)。 在超市的交易数据仓库中，每个项ik代

9、表一种商品的编号或名称，为计算方便假设I中的项已按字典序排序。 若I中项目的个数为k，则集合I称为 k-项集。关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念2. 事务 设 I=i1,i2,im 是由数据库中所有项目构成的集合，事务数据库 T=t1,t2,tn 是由一系列具有唯一标识的事务组成。每一个事务 tj (j=1,2,n) 包含的项集都是 I 的子集，即 tj I (j=1,2,n) 。 在超市等交易数据仓库中， tj 就代表某个顾客一次购买的所有商品编号或商品名称。例例题题1 1 对下表所示的交易数据库记录，请给出项集和其中的事务。解：交易数据库涉及a,b,c

10、,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中的项目也跟着出现的规律。XYXY关联规则的基本概念与基

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

12、篮分析中，XY的支持度也可以表示为关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念6. 关联规则的置信度（confidence） 关联规则的置信度是交易集中同时包含X和Y的交易数与包含X的交易数之比，记为confidence（ ），置信度反映了包含X的事务中出现Y的条件概率，即 confidence（ ）= = XYsupport()support()XYXXY()P Y X关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念7. 最小支持度与最小置信度 通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限值，此两个值称为最小支持度阈

13、值(min_ sup)和最小置信度阈值(min_ conf)。其中，min_ sup描述了关联规则的最低重要程度，min_ conf规定了关联规则必须满足的最低可靠性。关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念8. 频繁项集 设 ，项目集U在数据集T上的支持度是包含U的事务在T中所占的百分比，即 式中： 表示集合中元素数目。对项目集I，在事务数据库T中所有满足用户指定的最小支持度的项目集，即不小于min_sup的I的非空子集，称为频繁项目集。UITTUUtUport)(sup关联规则的基本概念与基础理论关联规则的基本概念与基础理论基本概念基本概念最大频繁项集 设X

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

15、支持度min_ sup和最小置信度min_ conf ，从给定的事务数据库T中寻找出所有强关联规则的过程。XYXYXYXY例例题题2 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)= Supportb,c=1/3，所以Confidence(XY) = Support (XY )/ Support (X)=1例例题题3 3Tr

16、ansaction-idItems bought10A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, FCustomerbuys diaperCustomerbuys bothCustomerbuys beer Let min_ sup = 50%, min_ conf = 50% Freq. Pat.: A:3, B:3, D:4, E:3, AD:3 Association rules:A D (60%, 100%)D A (60%, 75%)关联规则的基本概念与基础理论关联规则的基本概念与基础理论基础理论基础理论项目集性质：项目集空间理论理论

17、的核心为：频繁项目集的子集仍是频繁项目集，非频繁项目集的超集是非频繁项目集。关联规则的基本概念与基础理论关联规则的基本概念与基础理论基础理论基础理论Agrawal等人在研究事务数据库关联规则挖掘的过程中，发现了关于项集的两个基本性质，并在关联规则挖掘中被广泛应用。定理3-1(频繁项集性质1)：如果X是频繁项集，则它的任何非空子集X也是频繁项集。 即频繁项集的子集必是频繁项集。定理3-2(频繁项集性质2)：如果X是非频繁项集，那么它的所有超集都是非频繁项集。 即非频繁项集的超集也是非频繁项集。关联规则的基本概念与基础理论关联规则的基本概念与基础理论基础理论基础理论关联规则性质：定理3-3 （关联

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

19、信度。 典型算法AIS 算法（R. Agrawal等提出）Apriori算法（及变种AprioriTid和AprioriHybrid)） SETM 算法（M. Houtsma等提出）DHP 算法（J. Park等提出）PARTITION 算法（A.Savasere等提出）Sampling 算法（H.Toivonen提出）FP-growth 算法（Jiawei Han提出）关联规则的基本概念与基础理论关联规则的基本概念与基础理论Apriori算法原理算法原理Apriori算法是Agrawal等学者提出的关联规则的经典挖掘算法，在关联规则挖掘领域具有很大影响力。算法名称源于它使用了关于项集的两个性

20、质，即定理3-1和3-2等先验(Apriori)知识。Apriori算法基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法原理算法原理Apriori算法在具体实现时，将关联规则的挖掘过程分解为两个子问题。1、发现频繁项集 根据用户给定的最小支持度min_ sup ，寻找出所有的频繁项集，即满足支持度Support不低于min_ sup的所有项集。由于这些频繁项集之间有可能存在包含关系，因此，我们可以只关心所有的最大频繁项集，即那些不被其它频繁项集所包含的所有频繁项集。 2、生成关联规则 根据用户给定的最小置信度min_ conf ，在每个

21、最大频繁项集中，寻找置信度Confidence不小于min_ conf的关联规则。Apriori算法原理算法原理说明： 第二个子问题相对容易些，因为它只需要在已经找出的频繁项目集的基础上列出所有可能的关联规则，同时，满足支持度和置信度阈值要求的规则被认为是有趣的关联规则。 第一个子问题是挖掘关联规则的关键步骤，挖掘关联规则的总体性能由第一个步骤决定，因此，所有挖掘关联规则的算法都是着重于研究第一个子问题。Apriori算法的主要步骤算法的主要步骤（1）扫描全部数据，产生候选1-项集的集合C1；（2）根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L1；（3）对k1，重复执行步骤（

22、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很大时，关联规则挖掘的时间开销往往是巨大的。Apri

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

24、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-项集的支持度，这在

25、一定程度上减少了算法的计算量。Apriori算法原理算法原理发现频繁项集发现频繁项集Apriori算法之频繁项集发现算法：输入：输入：项集I，事务数据库T，最小支持数MinSptN输出：输出：所有频繁项集构成的集合L(1)求L1： 通过扫描数据库T，找出所有1-项集并计算其支持数作为候选频繁1-项集C1； 从C1中删除低于MinSptN的元素，得到所有频繁1-项集所构成的集合L1；(2) FOR k=1, 2, 3, . (3) 连接：将Lk进行自身连接生成一个候选频繁k+1项集的集合Ck+1，其连接方法如下：对任意p，qLk，若按字典序有 p=p1, p2, pk-1, pk ，q=p1,

26、p2, pk-1, qk且满足pkMinS，Confidence(AB)= 4000/6000 = 0.66MinS得出AB是一个强关联规则的结论。 实际上，AB这个强关联规则却是一个虚假的规则，如果商家使用这个规则将是一个错误，因为购买录像的概率是75%比60%高。 此外，计算机游戏和录像机是负相关的，因为买其中一种商品实际上降低了买另一种商品的可能性。如果不能完全理解这种现象，容易根据规则AB做出不明智的商业决策。相关性分析相关性分析提升度(lift)是一种简单的相关性度量。 对于项集A和B，如果概率P(AB)=P(A)P(B)，则A和B是相互独立的，否则它们就存在某种依赖关系。Lift(

27、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，则表示二者没有任何相关性。对于二元变量，提升度等价于被称为兴趣因子(Interest factor)的客观度量，其定义如下Lift(A,B)= I(A,B) = Support(AB)/(Support(A)Support(B) = Nn11/(n1+n+1) )例例题题6 对于例题5中的表所示的相依表，试计算其提升度或兴趣因子。解： P(AB) =40

28、00/100000=0.4；P(A)=6000/1000=0.6； P(B)=7500/10000=0.75 Lift(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所示的相依表，试计算相关因子。解：相关系

29、数r的分子等于4000500-35002000=20000007000000=-5000000，故相关系数r小于0，故购买“计算机游戏”与购买“录像机”两个事件是负相关的。 此外，相关性还可以用余弦值来度量，即 相关性度量可以提高关联规则的可用性，但仍然存在局限性，还需要研究，并引入其它客观度量。序列模式序列模式挖掘挖掘算法算法关联规则刻画了交易数据库在同一事务中，各个项目(Items)之间存在的横向联系(购买A的同时还买了B)，但没有考虑事务中的项目在时间维度上存在的纵向联系(购买了A一段时间后，再来购买B) ，后者就是一种时间序列模式，简称序列模式。序列模式的概念序列模式的概念定义定义3-

30、1 3-1 设I=i1,i2,im为项集，称S= 为一个时间事务序列，如果siI，hi为si发生的时间且hihi+1 (i=1,2,n-1)。 如果在时间事务序列问题的分析时，只要求hihi+1且不计hi=hi+1-hi的大小(i=1,2,n-1)，即不关心前后两个事务发生的时间跨度，则时间事务序列可简记为S=，并称为一个序列(Sequence)。其中项集si称为序列S的元素。定义定义3-23-2 若序列S中包含k个项，则称S为k-序列或长度为k的序列。序列模式的概念序列模式的概念例例题题8 8 顾客购买商品的序列 若仅关心顾客购买商品的时间顺序而不关心购买商品的具体时间，则S=S=就是某个顾

31、客一段时间内购买商品的序列，它有4个元素，8个项目，其长度为8。序列模式的概念序列模式的概念定义定义3-33-3 称S=为序列 的子序列(Subsequence)，记作SS，若存在正整数 ,使例例题题9 9 对于序列S=，则S=是S的一个子序列，因为S的元素33,8，S的元素4,54,5,6，S的元素88，即S是S的一个子序列。例例题题1010 对于下表所示的交易数据库，其中商品用长度为2的数字编码表示。试给出每个顾客的购物序列。解：解：对于包含时间信息的交易数据库，可以按照顾客id和交易日期升序排序，并把每位顾客每一次购买的商品集合作为该顾客购物序列中的一个元素，最后按照交易日期先后顺序将其

32、组成一个购物序列，生成如下表所示的序列数据库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-43-4 给定一个最小支持度阈值MinS，如果Support(S)MinS，则称序列S是频繁的。如果序列S是频繁的，则称S为一个频繁序列(Frequent S

33、equence)或序列模式（Sequence Pattern）。 序列模式的概念序列模式的概念例例题题11 11 对于例题10所得的序列数据库TS，给定最小支持度阈值MinS=25%，试找出其中的两个频繁序列模式。解：解：因为MinS=25%，而序列数据库TS有5条记录，所以支持数等于1.25，即频繁序列至少应包含在2个元组之中。容易判断序列和都是频繁的，因为元组C2和C4包含序列，而元组C2和C4包含序列。故和都是序列模式。序列模式的概念序列模式的概念 对于项集XI，如果存在序列S的元素si使得Xsi，则称元组(Cid, S)包含项集X。因此，类似于关联规则中的频繁项集概念，可以将X在序列数

34、据库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-53-5 设XI, MinS为最小支持度阈值，如果Support(X)MinS，则称X为序列数据库TS的频繁项集。序列模式的类序列模式的类Apriori算法算法序列模式的发现可以采用穷举法来枚举所有可能的序列，并统计它们的支持度。但这种方法的计算复杂性非常高。容易证明，在长度为n的序列

35、中，一个具有n个项的序列总共包含2n-1 个不同的子序列。因此必要寻找其它更高效的算法来发现序列模式，而下面介绍的定理3-5(序列模式的性质)，就可以在序列模式的搜索空间中剪裁掉那些明显的非频繁序列，从而提高序列模式挖掘的效率。 定理定理3-53-5 (序列模式性质)：如果S是频繁序列，则其任何非空子序列S也是频繁序列。序列模式的类序列模式的类Apriori算法算法类Apriori（Apriori Based）算法是一种基于Apriori原理的序列模式挖掘算法，利用序列模式的性质（定理3-5）来对候选序列模式集进行剪枝，从而减少了算法的计算工作量。其挖掘过程又可分解为事务数据库排序、频繁项集生

36、成、事务转换映射、频繁序列挖掘等几个步骤，下面通过例子予以详细说明。（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-1

37、5的正整数代替，得到转换映射后的序列数据库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)-序列集F

38、Sk+1，直到FSk+1=为止。例例题题1212 设有频繁3-序列集FS3=, ,解：解：先利用频繁3-序列集FS3连接生成候选4-序列集，即 将序列和连接生成 和， 将序列和连接生成 和因此，得到候选4-序列集CS4=， ，根据频繁序列的性质（定理3-5），对C4进行剪枝操作。首先将4-序列从C4中删除，因为它存在一个3-序列不在FS3之中，即它不会是频繁4-序列。类似地可以将，从CS4中删除。因此，得到最终的候选频繁4-序列集CS4=。例例题题1313 设最小支持数为2，对于表8-16转换映射后的序列数据库TN挖掘出所有的序列模式。解：解：在序列数据库的转换和映射过程中已得到频繁1-序列

39、FS1= ，。利用频繁1-序列集FS1生成候选频繁2-序列集 CS2=,2, 1, , , ,。 共有20个候选频繁2-序列。 扫描序列数据库TN并对候选频繁2-序列计算支持数，如的支持数为2，的支持数为0，支持数为3等，取支持数不低于2的序列组成频繁2-序列集 FS2=， 对频繁2-序列集FS2进行自身连接并剪枝后得到候选3-序列集 CS3=， ， 说明：频繁2-序列连接生成20个候选频繁3-序列，其中10个候选频繁3-序列被剪枝，如被剪枝是因其子序列不是频繁2-序列。 对候选频繁3-序列集CS3中每个序列计算支持数，保留支持数不小于2的序列形成频繁3-序列集 FS3=，。 由于FS3不能再

40、产生候选频繁4-序列，故最后得到频繁序列模式集 FS=FS2FS3=， ， 根据需要，将FS中的序列模式转换为真实商品编号的序列模式。比如序列模式对应于， 对应于， 而对应于等。 此外，类似强关联规则的概念，还可以引进强序列关联规则的概念。例如 3040； 30(40,7040,70,90)， 40,7040,7090关联规则挖掘其它关联规则挖掘其它算法算法频繁项集算法优化频繁项集算法优化(1) 基于划分的方法，把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的局部频繁项集。然后合并各个块的局部频繁项集，通过测试它们的支持度来生成全局频繁项集。(2) 基于hash的方法

41、，先构造一个hash函数，然后将扫描到的项目映射到不同的hash桶中，每一个2-项集最多只能放在一个特定的桶中，这样可以对每个桶中的项目进行计数，减少了候选集生成的计算时间。(3) 基于抽样的方法，使用数据库的抽样(随机抽取的部分)数据得到一些可能成立的关联规则，然后利用数据库的剩余部分验证这些关联规则是否正确。从而减少数据的分析量，提高算法效率。由于抽样方法有简单随机抽样、系统抽样、分层抽样、整群抽样、多段抽样等多种方法，因此，为了保证抽样数据对全部数据具有充分的代表性，选择恰当的抽样方法很重要。基于抽样的方法最大的优点是能够显著降低扫描数据库所付出的I/0代价，但如果抽样数据选取不当，就有可能引起结果的巨大偏差。CLOSE算法算法 CLOSE算法是一种基于概念格(concept lattice)的关联规则挖掘算法。Pasquier等人于1999年利用概念格中概念连接的闭合性，创造性地建立了闭合项集格(closed itemset lattice)理论，并提出挖掘频繁闭合项集(frequent closed itemset)的A-close算法。此后