1、基本概念与解决方法 经典的频繁项目集生成算法分析 Apriori算法的性能瓶颈问题Apriori的改进算法对项目集格空间理论的发展关联规则挖掘中的一些更深入的问题第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法 关联规则挖掘（关联规则挖掘（Association Rule Mining）是数据挖掘）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。中研究较早而且至今仍活跃的研究方法之一。最早是由最早是由Agrawal等人提出的（等人提出的（1993）。最初提出的动机是）。最初提出的动机是针对购物篮分析（针对购物篮分析（Basket Analysis）问题提出的，其目的是）问题提出的，
2、其目的是为了发现交易数据库（为了发现交易数据库（Transaction Database）中不同商品之）中不同商品之间的联系规则。间的联系规则。关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（挖掘（Parallel Association Rule Mining）以及数量关联规）以及数量关联规则挖掘（则挖掘（Quantitive Association Rule Mining）等。）等。关联规则挖掘是数据挖掘的其他研究分支的基础。关联规则
3、挖掘是数据挖掘的其他研究分支的基础。设设I=i1，i2，im 是一个项目是一个项目(Item)集合，事务数据库集合，事务数据库D=t1，t2，tn 是由一系列具有唯一标识是由一系列具有唯一标识TID(事务号事务号)的事务组成，每个事务的事务组成，每个事务ti（i=1，2，n）都对应）都对应 I 上的一上的一个子集。个子集。一个事务数据库可以用来刻画：一个事务数据库可以用来刻画：购物记录：购物记录：I是全部物品集合，是全部物品集合，D是购物清单，每个元是购物清单，每个元组组 ti 是一次购买物品的集合（它当然是是一次购买物品的集合（它当然是 I 的一个子集）。的一个子集）。如如I=物品物品1，物
4、品物品2，物品物品m;事务数据库事务数据库D=t1，t2，tn 是是 t1物品物品2物品物品6物品物品9 t2物品物品3物品物品8物品物品16 tn物品物品1物品物品12物品物品34 l定义（项目集的支持度）定义（项目集的支持度）给定一个全局项目集给定一个全局项目集I和数据库和数据库D，一个项目集，一个项目集 I1 I 在在D上的上的支持度（支持度（Support）是包含是包含 I1 的事务在的事务在D中所占的百分比：中所占的百分比：support（I1）=|t D|I1 t|/|D|l定义（频繁项目集）定义（频繁项目集）给定全局项目集给定全局项目集I和数据库和数据库D，D中中所有满足用户指定
5、的最小支持度（所有满足用户指定的最小支持度（Minsupport）的项目集，）的项目集，即大于或等于最小支持度的即大于或等于最小支持度的 I 的非空子集，称为的非空子集，称为频繁项目频繁项目集（集（Frequent Itemsets）。在频繁项目集中挑选出所有不。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为被其他元素包含的频繁项目集称为最大频繁项目集最大频繁项目集（Maximum Frequent Itemsets）。l定义（规则的可信度）定义（规则的可信度）一个定义在一个定义在I和和D上的形如上的形如 I1I2 的关联规则通过满足一定的的关联规则通过满足一定的可信度可信度(Con
6、fidence)来给出。来给出。所谓规则的可信度是指包含所谓规则的可信度是指包含 I1 和和I2的事务与包含的事务与包含 I1 的事务的事务之比：之比：Confidence(I1I2)=|Support(I1I2)/Support(I1)其中其中I1,I2 I;I1I2=定义（强关联规则）。定义（强关联规则）。D 在在 I 上满足最小支持度和最小可上满足最小支持度和最小可信度的关联规则称为强关联规则。信度的关联规则称为强关联规则。通常所说的关联规则一般指上面定义的强关联规则。通常所说的关联规则一般指上面定义的强关联规则。关联规则挖掘问题就是根据用户指定的关联规则挖掘问题就是根据用户指定的最小支
7、持度最小支持度和最小可信度来寻找强关联规则。和最小可信度来寻找强关联规则。关联规则挖掘问题可以划分成两个子问题：关联规则挖掘问题可以划分成两个子问题：1.1.发现频繁项目集发现频繁项目集:通过用户给定通过用户给定最小支持度最小支持度，寻找所有频，寻找所有频繁项目集或者最大频繁项目集。繁项目集或者最大频繁项目集。2.2.生成关联规则生成关联规则:通过用户给定通过用户给定最小可信度最小可信度，在频繁项目集，在频繁项目集中，寻找关联规则。中，寻找关联规则。第第1 1个子问题是近年来关联规则挖掘算法研究的重点。个子问题是近年来关联规则挖掘算法研究的重点。Agrawal等人建立了用于事务数据库挖掘的项目
8、集格空间理等人建立了用于事务数据库挖掘的项目集格空间理论（论（1993,Appriori 属性）。属性）。其理论核心的原理是：其理论核心的原理是：频繁项目集的所有非空子集都是频繁项目集频繁项目集的所有非空子集都是频繁项目集非频繁项目集的所有超集都是非频繁项目集非频繁项目集的所有超集都是非频繁项目集（相关定理及其证明略。）（相关定理及其证明略。）Apriori算法是通过项目集元素数目不断增长来完成频繁项目算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生集发现的。首先产生1_频繁项目集频繁项目集L1，然后产生，然后产生2_频繁项频繁项目集目集L2，直到不能再扩展频繁项目集的元素数目
9、为止。，直到不能再扩展频繁项目集的元素数目为止。下面给出一个样本事务数据库，并对它实施下面给出一个样本事务数据库，并对它实施Apriori算法。算法。TIDItemset1001，3，42002，3，53001，2，3，54002，5 1994年，年，Agrawal 等人提出了著名的等人提出了著名的Apriori 算法。算法。TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4 C1：1-候选集候选集 L1：1-频繁项目集频繁项目集C2：2-候选
10、集候选集 L2：2-频繁项目集频繁项目集C3：3-候选集候选集 L3：3-频繁项目集频繁项目集C4：4-候选集候选集 L4：4-频繁项目集频繁项目集L3是最大频繁项目集是最大频繁项目集Apriori算法（发现频繁项目集）算法（发现频繁项目集）（1）L1=large 1-itemsets;/所有所有1-项目频集项目频集（2）FOR（k=2;Lk-1;k+）DO BEGIN（3）Ck=apriori-gen（Lk-1）;/Ck是是k-候选集候选集（4）FOR all transactions t D DO BEGIN（5）Ct=subset（Ck，t）;/Ct是所有是所有t包含的候选集元素包含的候
11、选集元素（6）FOR all candidates c Ct DO（7）c.count+;（8）END（9）Lk=c Ck|c.count minsup_count（10）END（11）L=Lk;算法算法Apriori中调用了中调用了Apriori-gen(Lk-1)，是为了通过，是为了通过(k-1)-频频集产生集产生K-侯选集。侯选集。has_infrequent_subset（c，Lk-1），判断），判断c是否加入到是否加入到k-侯选集侯选集中。中。（1）FOR all itemset p Lk-1 DO（2）FOR all itemset q Lk-1 DO（3）IF p.item1=q
12、.item1，p.itemk-2=q.itemk-2，p.itemk-1 1）THEN/generate rules with subsets of xm-1 as antecedents（7）genrules（lk，xm-1）;（8）END（9）END；Minconfidence=80%序号序号lkxm-1ConfidenceSupport规则（是否是强规则）规则（是否是强规则）1235267%50%235（否）（否）2235367%50%325（否）（否）3235567%50%523（否）（否）423523100%50%235（是）（是）52352567%50%253（否）（否）62353
13、5100%50%352（是）（是）包含包含2,35的事务与包含的事务与包含2的事务的比值的事务的比值,即即2:3同时满足支持同时满足支持度和可信度度和可信度 Apriori作为经典的频繁项目集生成算法，在数据作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈算法有两个致命的性能瓶颈:1多次扫描事务数据库，需要很大的多次扫描事务数据库，需要很大的I/O负载负载 对每次对每次k k循环，侯选集循环，侯选集C Ck k中的每个元素都必须通过扫描数据库中的每个元素都必须通过扫描数据库一次来验证其是否加入一次来验证其是否加入L Lk
14、 k。假如有一个频繁大项目集包含。假如有一个频繁大项目集包含1010个个项的话，那么就至少需要扫描事务数据库项的话，那么就至少需要扫描事务数据库1010遍。遍。2可能产生庞大的侯选集可能产生庞大的侯选集 由由L Lk k-1-1产生产生k k-侯选集侯选集C Ck k是指数增长的，例如是指数增长的，例如10104 4个个1-1-频繁项目集频繁项目集就有可能产生接近就有可能产生接近10107 7个元素的个元素的2-2-侯选集。如此大的侯选集对侯选集。如此大的侯选集对时间和主存空间都是一种挑战。时间和主存空间都是一种挑战。一些算法虽然仍然遵循一些算法虽然仍然遵循Apriori 属性，但由于引入了相
15、属性，但由于引入了相关技术，在一定程度上改善了关技术，在一定程度上改善了Apriori算法适应性和效率。算法适应性和效率。主要的改进方法有：主要的改进方法有：基于数据分割（基于数据分割（Partition）的方法：基本原理是）的方法：基本原理是“在一在一个划分中的支持度小于最小支持度的个划分中的支持度小于最小支持度的k-项集不可能是全项集不可能是全局频繁的局频繁的”。基于散列（基于散列（Hash）的方法：基本原理是）的方法：基本原理是“在一个在一个hash桶桶内支持度小于最小支持度的内支持度小于最小支持度的k-项集不可能是全局频繁的项集不可能是全局频繁的”。基于采样（基于采样（Sampling
16、）的方法：基本原理是）的方法：基本原理是“通过采样通过采样技术，评估被采样的子集中，并依次来估计技术，评估被采样的子集中，并依次来估计k-项集的全项集的全局频度局频度”。其它方法，如动态删除没有用的事务：其它方法，如动态删除没有用的事务：“不包含任何不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删的事务对未来的扫描结果不会产生影响，因而可以删除除”。Apriori算法在执行过程中是先生成候选集再剪枝，可是生算法在执行过程中是先生成候选集再剪枝，可是生成的候选集并不都是有效的。候选集的产生需要花费很大的成的候选集并不都是有效的。候选集的产生需要花费很大的代价。把数据分割技术应用到关联
17、规则挖掘中，可以改善关代价。把数据分割技术应用到关联规则挖掘中，可以改善关联规则挖掘在大数据集中的适应性。联规则挖掘在大数据集中的适应性。其基本思想：首先将大数据集从逻辑上分成互不相交的块，其基本思想：首先将大数据集从逻辑上分成互不相交的块，每块应用挖掘算法（如每块应用挖掘算法（如Apriori算法）生成局部的频繁项目算法）生成局部的频繁项目集，然后将这些局部的频繁项目集作为全局候选频繁项目集，集，然后将这些局部的频繁项目集作为全局候选频繁项目集，通过测试他们的支持度来得到最终的全局频繁项目集。通过测试他们的支持度来得到最终的全局频繁项目集。其可在以下两方面改善其可在以下两方面改善Aprior
18、i关联规则挖掘算法的性能：关联规则挖掘算法的性能：1合理利用主存空间：数据分割将大数据集分成小的块，为块内数合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。据一次性导入主存提供机会。2支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。因此提供了开发并行数据挖掘算法的良好机制。定理定理 设数据集设数据集D被分割成分块被分割成分块D1，D2，Dn，全局最小，全局最小支持度为支持度为minsupport，假设对应的全局最小支持数为，假设对应的全局最小支持数为min
19、sup_count。如果一个数据分块。如果一个数据分块Di 的局部最小支持数的局部最小支持数记为记为minsup_counti(i=1，2，n)，则局部最小支持数，则局部最小支持数minsup_counti按照如下方法生成：按照如下方法生成：minsup_counti=minsup_count*|Di|/|D|可以保证所有的局部频繁项目集涵盖全局频繁项目集。可以保证所有的局部频繁项目集涵盖全局频繁项目集。1995，Park等发现寻找频繁项目集的主要计算是在生成等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，频繁项目集上。因此，Park等利用了这个性质引入等利用了这个性质引入散列散
20、列技技术来改进产生术来改进产生2-频繁项目集的方法。频繁项目集的方法。例：桶地址例：桶地址=（10 x+y）mod 7；minsupport_count=3 TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3L2=(I2，I3)，(I1，I2)，(I1，I3)桶地址桶地址 0 1 2 3 4 5 6桶计数桶计数 2 2 4 2 2 4 4桶桶 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 内内 I3，I5 I1，I5 I2，I3 I2
21、，I4 I2，I5 I1，I2 I1，I3容容 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 随着数据库容量的增大，重复访问数据库（外存）随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。成为近年来关联规则挖掘研究的热点之一。两个典型的方法：两个典型的方法：Close算法算法 FP-tree算法算法 一个频繁闭合项目集的所有闭合子集一定是频繁一个频繁闭合项目集的所有闭合子
22、集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。是非频繁的。什么是一个闭合的项目集？什么是一个闭合的项目集？一个项目集一个项目集C是闭合的，当且仅当对于在是闭合的，当且仅当对于在C中中的任何元素，不可能在的任何元素，不可能在C中存在小于或等于它中存在小于或等于它的支持度的子集。的支持度的子集。例如，例如，C1=AB3，ABC2是闭合的；是闭合的；C2=AB2，ABC2不是闭合的；不是闭合的；CLOSS算法的基本思路：利用频繁闭合算法的基本思路：利用频繁闭合i_项目集项目集FCi，生，生成频繁闭合成频繁闭合i+1 _项目集项目集FCi+
23、1（i1）。）。首先找出候选频繁闭合首先找出候选频繁闭合1_项目集项目集FCC1，通过扫描数据，通过扫描数据库得到库得到候选闭合候选闭合项目集，再经修剪得到项目集，再经修剪得到频繁闭合项目集频繁闭合项目集FC1项目集。用项目集。用FC1产生产生候选频繁闭合候选频繁闭合2_项目集项目集FCC2，再，再经修剪得到经修剪得到频繁闭合项目集频繁闭合项目集FC2项目集。在用项目集。在用FC2推出推出FC3，如此继续直到某个如此继续直到某个FCCr 为空时停止。为空时停止。扫描数据库得到扫描数据库得到:FCC1=(A,3),(B,5),(C,4),(D,3),(E,3)；相应闭合项目集为相应闭合项目集为:
24、FCl(A)=ABC,3(计算计算A的闭合过程的闭合过程:第一项包含第一项包含A,首先得到首先得到A的闭合的闭合为为ABCD,第三项也包含第三项也包含A,故取故取ABCD与第三项的交与第三项的交ABC作为作为A的闭合，第五项也包含的闭合，第五项也包含A,故取故取ABC与第五项的交与第五项的交ABC作为作为A的闭的闭合合,这时到了最后一项这时到了最后一项,计算完毕计算完毕)。同理，。同理，FCl(B)=B,5，FCl(C)=BC,4，FCl(D)=BD,3，FCl(E)=BE,3；FCC2=(AB,3),(AC,3),(BC,4),(BD,3),(BE,3)；相应闭合项目集为相应闭合项目集为:F
25、C2(AB)=ABC,3,FC2(AC)=ABC,3；L3，L4，L5不用测，于是频繁大项集为不用测，于是频繁大项集为ABC。下面是下面是Close算法作用到右表数据集的算法作用到右表数据集的执行过程（假如执行过程（假如minsup_count=3）：）：TIDItemset1A，B，C，D2B，C，E3A，B，C，E4B，D，E5A，B，C，D样本数据库样本数据库 2000年年Han等提出了一个称为等提出了一个称为FP-Tree（频繁模频繁模式树）的算法，该算法只进行式树）的算法，该算法只进行 2 次数据库扫描，不次数据库扫描，不使用侯选集，直接压缩数据库成一个使用侯选集，直接压缩数据库成一
26、个FP-Tree，然后，然后通过该树生成关联规则。构造通过该树生成关联规则。构造FP-Tree的过程如下的过程如下：按按Apriori算法，扫描数据库一次生成算法，扫描数据库一次生成1-频繁项频繁项目集，并按频度降序排序，放入目集，并按频度降序排序，放入L列表中；列表中；创建根结点，标志为创建根结点，标志为null，扫描数据库一次，扫描数据库一次，当得到数据库的一个项目（元组）时，就把其当得到数据库的一个项目（元组）时，就把其中的元素按中的元素按L表中的次序排列，然后通过递归表中的次序排列，然后通过递归实现实现FP-Tree的增长；的增长；样本数据库样本数据库下面看一个例子来说明下面看一个例子
27、来说明FP-Tree的增长过程的增长过程,最小支持度阈值为最小支持度阈值为3。TIDItemset1f,a,c,d,g,i,m,p2a,b,c,f,l,m,o3b,f,h,j,o4b,c,k,s,p5a,f,c,e,l,m,p,nItemfrequencyf4c4a3b3m3p3L扫描数据库一次生成扫描数据库一次生成1-频繁项目集（在数据库中出现频繁项目集（在数据库中出现3次或次或3次以上的），并按频次以上的），并按频度降序排序，放入度降序排序，放入L列表中；列表中；TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,p(1-频繁项目集频繁项目集)
28、样本数据库样本数据库TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,pItem(fre)f4c4a3b3m3p3LT1T2T3T4扫描数据库扫描数据库,依次增依次增长长FP-tree，并改变并改变支持数支持数f:1c:1a:1m:1NULLp:1f:2c:2a:2m:1NULLb:1p:1m:1f:3c:2a:2m:1NULLb:1p:1m:1b:1f:3c:2a:2m:1NULLb:1p:1m:1b:1c:1b:1p:1f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5Item(fre)f4c4a3b3m3p3L建
29、立索引建立索引f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5 用用FP-Tree挖掘频繁集的基本思想是分而制之，挖掘频繁集的基本思想是分而制之，即使用即使用FP-Tree 递归增长频繁集的方法：递归增长频繁集的方法：对每个项，生成其条件模式库，然后生成其条件对每个项，生成其条件模式库，然后生成其条件FP-Tree；对每个新生成的条件对每个新生成的条件FP-Tree，重复此步骤；重复此步骤；直到结果直到结果FP-Tree为空，或只含唯一的一个路径，此路为空，或只含唯一的一个路径，此路径的每个子路径对应的项目集都是频繁集。径的每个子路径对应的项目集都是频繁集。对应的
30、条件模式库对应的条件模式库Item条件模式库条件模式库cf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1FP-treeItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5m-条件条件模式库模式库Item条件模式库条件模式库cf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1f:3c:3a:3NULLItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5Item条件模式库
31、条件模式库p(fcam:2),(cb:1)(c:3)|pm(fca:2),(fcab:1)(f:3,c:3,a:3)|mb(fca:1),(f:1),(c:1)Emptyafc:3(f:3,c:3)|acf:3(f:3|cfEmptyEmptyc:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLNULLc:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLNULL根据规则中涉及到的层次，多层次关联规则可以分为：根据规则中涉及到的层次，多层次关联规则可以分为：同层关联规则：如果一个关联规则对应的项目是同一个同层关联规则：如果一个关联规则对
32、应的项目是同一个粒度层次，那么它是同层关联规则。如粒度层次，那么它是同层关联规则。如“牛奶牛奶面包面包”和和“羽羽绒服绒服酸奶酸奶”都是同层关联规则都是同层关联规则;日用品服装食品夏季服装冬季服装面包牛奶羽绒服大衣品牌1品牌2鲜奶酸奶品牌3品牌4层间关联规则：如果层间关联规则：如果在不同的粒度层次上考在不同的粒度层次上考虑问题，那么可能得到虑问题，那么可能得到的是层间关联规则。的是层间关联规则。如如“夏季服装夏季服装酸奶酸奶”都是都是层间关联规则层间关联规则;多层次关联规则挖掘的度量方法可以沿用多层次关联规则挖掘的度量方法可以沿用“支持度支持度-可信度可信度”的框架。不过，多层次关联规则挖掘有
33、两种基本的设置支持的框架。不过，多层次关联规则挖掘有两种基本的设置支持度的策略：度的策略：统一的最小支持度：算法实现容易，而且很容易支持统一的最小支持度：算法实现容易，而且很容易支持层间的关联规则生成。但是弊端也是显然的：层间的关联规则生成。但是弊端也是显然的：不同层次可能考虑问题的精度不同、面向的用户群不同层次可能考虑问题的精度不同、面向的用户群不同不同 对于一些用户，可能觉得支持度太小，产生了过多对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。而对于另外的用户来说，又认为不感兴趣的规则。而对于另外的用户来说，又认为支持度太大，有用信息丢失过多。支持度太大，有用信息丢失过多。不同
34、层次使用不同的最小支持度：每个层次都有自己不同层次使用不同的最小支持度：每个层次都有自己的最小支持度。较低层次的最小支持度相对较小，而的最小支持度。较低层次的最小支持度相对较小，而较高层次的最小支持度相对较大。这种方法增加了挖较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是，也留下了许多相关问题需要解决：掘的灵活性。但是，也留下了许多相关问题需要解决：首先，不同层次间的支持度应该有所关联，只有正首先，不同层次间的支持度应该有所关联，只有正确地刻画这种联系或找到转换方法，才能使生成的确地刻画这种联系或找到转换方法，才能使生成的关联规则相对客观。关联规则相对客观。其次，由于具有不同的
35、支持度，层间的关联规则挖其次，由于具有不同的支持度，层间的关联规则挖掘也是必须解决的问题。例如，有人提出层间关联掘也是必须解决的问题。例如，有人提出层间关联规则应该根据较低层次的最小支持度来定。规则应该根据较低层次的最小支持度来定。对于多层关联规则挖掘的策略，可灵活掌握：对于多层关联规则挖掘的策略，可灵活掌握：自上而下方法：先找高层规则，如自上而下方法：先找高层规则，如“冬季服装冬季服装牛牛奶奶”，再找其下层规则，如，再找其下层规则，如“羽绒服羽绒服鲜奶鲜奶”。如此。如此逐层逐层自上而下自上而下挖掘。挖掘。不同层次的支持度可以一样，不同层次的支持度可以一样，也可以根据上层的支持度动态生成下层的
36、支持度。也可以根据上层的支持度动态生成下层的支持度。自下而上方法：先找低层规则，再找其上层规则，自下而上方法：先找低层规则，再找其上层规则，如如“羽绒服羽绒服鲜奶鲜奶”。不同层次的支持度可以动态生不同层次的支持度可以动态生成。成。在同一固定层次上挖掘：用户可根据情况，在一个在同一固定层次上挖掘：用户可根据情况，在一个固定层次上挖掘，如果需要查看其他层次的数据，固定层次上挖掘，如果需要查看其他层次的数据，可通过上钻和下钻等操作来获得相应数据。可通过上钻和下钻等操作来获得相应数据。多维关联规则可以有：多维关联规则可以有：维内的关联规则：例如，维内的关联规则：例如，“年龄（年龄（X，2030）职业职
37、业（X，学生），学生）购买（购买（X，笔记本电脑），笔记本电脑）”。这里我们。这里我们就涉及到三个维：年龄、职业、购买。就涉及到三个维：年龄、职业、购买。混合维关联规则：这类规则允许同一个维重复出现。混合维关联规则：这类规则允许同一个维重复出现。例如，例如，“年龄（年龄（X，2030）购买（购买（X，笔记本电脑），笔记本电脑）购买（购买（X，打印机），打印机）”。由于同一个维。由于同一个维“购买购买”在在规则中重复出现，因此为挖掘带来难度。但是，这类规则中重复出现，因此为挖掘带来难度。但是，这类规则更具有普遍性，具有更好的应用价值，因此近年规则更具有普遍性，具有更好的应用价值，因此近年来得到普
38、遍关注。来得到普遍关注。主要解决连续的数值型数据挖掘问题，它与布尔关联规则挖主要解决连续的数值型数据挖掘问题，它与布尔关联规则挖掘不同。主要涉及的关键问题有：掘不同。主要涉及的关键问题有：连续数值属性的处理，一般有连续数值属性的处理，一般有 对数值属性进行离散化处理，包括：对数值属性进行离散化处理，包括：数值属性的静态离散化；数值属性的静态离散化；数值属性的动态离散化；数值属性的动态离散化；基于特定的技术进行离散化。基于特定的技术进行离散化。不直接对数值属性离散化，而是采用统计或模糊方不直接对数值属性离散化，而是采用统计或模糊方法进行处理。法进行处理。规则的优化规则的优化对关系数据库而言，不加限制会产生大量冗余规则，对关系数据库而言，不加限制会产生大量冗余规则，这些规则对于理解和使用都是新的瓶颈。需对其进行这些规则对于理解和使用都是新的瓶颈。需对其进行优化以找出用户真正感兴趣的规则集。优化以找出用户真正感兴趣的规则集。提高挖掘效率提高挖掘效率 数量关联规则挖掘是效率很关键，需要在连续属性的数量关联规则挖掘是效率很关键，需要在连续属性的离散化、频繁集发现、规则产生及规则优化等诸多方离散化、频繁集发现、规则产生及规则优化等诸多方面开展工作。面开展工作。
