大型数据库中的关联规则挖掘

大型数据库中的关联规则挖掘什么是关联规则挖掘？关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品（图6.1）之间联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析假定作为AllElectronics

的分店经理，你想更加了解你的顾客的购物习惯。例如，你想知道“什么商品组或集合顾客多半会在一次购物时同时购买？”为回答你的问题，你可以在你的商店顾客事务零售数据上运行购物篮分析。分析结果可以用于市场规划、广告策划、分类设计。例如，购物篮分析可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售。例如，如果顾客购买计算机也倾向于同时购买财务软件，将硬件摆放离软件陈列近一点，可能有助于增加二者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发买这些商品的顾客一路挑选其它商品。例如，在决定购买一台很贵的计算机之后，去看软件陈列，购买财务软件，路上可能看到安全系统，可能会决定也买家庭安全系统。购物篮分析也可以帮助零售商规划什么商品降价出售。如果顾客趋向于同时购买计算机和打印机，打印机降价出售可能既促使购买打印机，又促使购买计算机。购物篮分析如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示关联规则的两个兴趣度度量支持度置信度6.1.2基本概念设I={i1,i2,...,im

}是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T⊆I。每一个事务有一个标识符，称作TID。设A是一个项集，事务T包含A当且仅当A⊆T。关联规则是形如A⇒B的蕴涵式，其中A⊂I，B⊂I，并且A∩B=∅。规则A⇒B在事务集D中成立，具有支持度s，其中s是D中事务包含A∪B（即，A和B二者）的百分比。6.1.2基本概念它是概率P(A∪B)。规则A⇒B在事务集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比是c。这是条件概率P(B|A)。support(A⇒B)=P(A∪B)(6.2)confidence(A⇒B)=P(B|A)(6.3)6.1.2基本概念同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。为方便计，我们用0%和100%之间的值，而不是用0到1之间的值表示支持度和置信度。项的集合称为项集。包含k个项的项集称为k-项集。集合{computer,financial_management_software}是一个2-项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min_sup，如果项集的出现频率大于或等于min_sup

与D中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集。频繁k-项集的集合通常记作Lk。基本概念——示例项的集合I={A,B,C,D,E,F}每个事务T由事务标识符TID标识，它是项的集合比如：TID(2000)={A,B,C}任务相关数据D是数据库事务的集合D规则度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度和置信度的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)大型数据库关联规则挖掘(1)基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集大型数据库关联规则挖掘(2)大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则关联规则挖掘分类(1)关联规则有多种分类：根据规则中所处理的值类型布尔关联规则量化关联规则（规则描述的是量化的项或属性间的关联性）根据规则中涉及的数据维单维关联规则（仅涉及buys这个维）多维关联规则关联规则挖掘分类(2)根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）根据关联挖掘的各种扩充挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c’，使得每个包含c的事务也包含c’）（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则A

C，其支持度=50%置信度Apriori算法(1)Apriori算法是挖掘布尔关联规则频繁项集的算法Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。模式不可能比A更频繁的出现Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率Apriori算法(2)Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接步：为找Lk，通过Lk-1

与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1

和l2

是Lk-1

中的项集。记号li[j]表示li

的第j项（例如，l1[k-2]表示l1

的倒数第3项）。为方便计，假定事务或项集中的项按字典次序排序。执行连接；其中，Lk-1

的元素是可连接的，如果它们前(k-2)个项相同；即，Lk-1

的元素l1

和l2

是可连接的，如果(l1

[1]=l2

[1])∧(l1[2]=l2

[2])∧...∧(l1[k-2]=l2

[k-2])∧(l1

[k-1]<l2

[k-1])。条件(l1[k-1]<l2

[k-1])是简单地保证不产生重复。连接l1

和l2

产生的结果项集是l1[1]l1

[2]...l1

[k-1]l2

[k-1]。剪枝步：Ck

是Lk

的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck

中。扫描数据库，确定Ck

中每个候选的计数，从而确定Lk（即，根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck

可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori

性质：任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-1)-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck

中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例6.1让我们看一个Apriori

的具体例子。该例基于图6.2的AllElectronics

的事务数据库。数据库中有9个事务，即|D|=9。Apriori

假定事务中的项按字典次序存放。我们使用图6.3解释Apriori算法发现D中的频繁项集。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}2最小支持计数：2使用Apiori性质由L2产生C31．连接：C3=L2

L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以删除这个选项；{B,C,E}的2项子集是{B,C},{B,E},{C,E}，它的所有2－项子集都是L2的元素，因此保留这个选项。3．这样，剪枝后得到C3={{B,C,E}}由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由如下过程产生：对于每个频繁项集l，产生l的所有非空子集；对于每个非空子集s，如果 则输出规则“ ”6.2.3提高Apriori的有效性（1）基于散列的技术（散列项集计数）：一种基于散列的技术可以用于压缩候选k-项集Ck(k>1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，我们可以对每个事务产生所有的2-项集，将它们散列（即，映射）到散列表结构的不同桶中，并增加对应的桶计数（图6.6）。在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2-项集，因而应当由候选项集中删除。这种基于散列的技术可以大大压缩要考察的k-项集（特别是当k=2时）。6.2.3提高Apriori的有效性6.2.3提高Apriori的有效性（2）事务压缩（压缩进一步迭代扫描的事务数）：不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样，这种事务在其后的考虑时，可以加上标记或删除，因为为产生j-项集(j>k)，扫描数据库时不再需要它们。6.2.3提高Apriori的有效性划分（为找候选项集划分数据）：可以使用划分技术，它只需要两次数据库扫描，以挖掘频繁项集（图6.7）。它包含两遍。在第I遍，算法将D中的事务划分成n个非重叠的部分。如果D中事务的最小支持度阈值为min_sup，则每个部分的最小支持度计数为min_sup×该部分中事务数。对每一部分，找出该部分内的频繁项集。这些称作局部频繁项集。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。这使得对于k=1,2,..，找出所有的局部频繁k-项集只需要扫描一次数据库。6.2.3提高Apriori的有效性局部频繁项集可能不是整个数据库D的频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，所有的局部频繁项集作为D的候选项集。所有部分的频繁项集的集合形成D的全局候选项集。在第II遍，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。每一部分的大小和划分的数目这样确定，使得每一部分能够放入内存，这样每遍只需要读一次。6.2.3提高Apriori的有效性（4）选样（在给定数据的一个子集挖掘）：选样方法的基本思想是：选取给定数据库D的随机样本S，然后，在S而不是在D中搜索频繁项集。用这种方法，我们牺牲了一些精度换取了有效性。样本S的大小这样选取，使得可以在内存搜索S中频繁项集；这样，总共只需要扫描一次S中的事务。由于我们搜索S中而不是D中的频繁项集，我们可能丢失一些全局频繁项集。为减少这种可能性，我们使用比最小支持度低的支持度阈值来找出局部于S的频繁项集（记作LS）。6.2.3提高Apriori的有效性然后，数据库的其余部分用于计算LS中每个项集的实际频繁度。有一种机制可以用来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，只需要扫描一次D。否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须在不同的数据上运行时，选样方法特别合适。6.2.3提高Apriori的有效性（5）动态项集计数（在扫描的不同点添加候选项集）：动态项集计数技术将数据库划分为标记开始点的块。不象Apriori

仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori

少。其它变形涉及多层和多维关联规则挖掘，在本章的其余部分讨论。涉及空间数据、时间序列数据和多媒体数据的关联挖掘在第9章讨论。6.2.4不产生候选挖掘频繁项集正如我们已经看到的，在许多情况下，Apriori

的候选产生-检查方法大幅度压缩了候选项集的大小，并导致很好的性能。然而，它有两种开销可能并非微不足道的。6.2.4不产生候选挖掘频繁项集它可能需要产生大量候选项集。例如，如果有104个频繁1-项集，则Apriori

算法需要产生多达107个候选2-项集，累计并检查它们的频繁性。此外，为发现长度为100的频繁模式，如{a1,...,a100}，它必须产生多达2100≈1030

个候选。它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式尤其如此。6.2.4不产生候选挖掘频繁项集“可以设计一种方法，挖掘全部频繁项集，而不产生候选吗？”一种有趣的方法称作频繁模式增长，或简单地，FP-增长，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（或FP-树），但仍保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。让我们看一个例子。6.2.4不产生候选挖掘频繁项集例6.3使用频繁模式增长方法，我们重新考察例6.1中图6.2事务数据库D的挖掘。数据库的第一次扫描与Apriori

相同，它导出频繁项（1-项集）的集合，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或表记作L。这样，我们有L=[I2:7,I1:6,I3:6,I4:2,I5:2]。6.2.4不产生候选挖掘频繁项集然后，FP-树构造如下：首先，创建树的根结点，用“null”标记。二次扫描数据库D。每个事务中的项按L中的次序处理（即，根据递减支持度计数排序）并对每个事务创建一个分枝。例如，第一个事务“T100:I1,I2,I5”按L的次序包含三个项{I2,I1,I5}，导致构造树的第一个分枝<(I2:1),(I1:1),(I5:1)>。该分枝具有三个结点，其中，I2作为根的子女链接，I1链接到I2，I5链接到I1。6.2.4不产生候选挖掘频繁项集第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀<I2>。这样，我们将结点I2的计数增加1，并创建一个新结点(I4:1)，它作为(I2:2)的子女链接。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个结点的计数增加1，为随在前缀之后的项创建结点并链接。6.2.4不产生候选挖掘频繁项集为方便树遍历，创建一个项头表，使得每个项通过一个结点链指向它在树中的出现。扫描所有的事务之后得到的树展示在图6.8中，附上相关的结点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-树问题。6.2.4不产生候选挖掘频繁项集6.2.4不产生候选挖掘频繁项集FP-树挖掘处理如下。由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP-树中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。6.2.4不产生候选挖掘频繁项集FP-树的挖掘总结在表6.1中，让我们首先考虑I5，它是L中的最后一个项，而不是第一个。其原因随着我们解释FP-树挖掘过程就会清楚。I5出现在图6.8的FP-树的两个分枝。（I5的出现容易通过沿它的结点链找到。）这些路径由分枝<(I2I1I5:1)>和<(I2I1I3I5:1)>形成。这样，考虑I5为后缀，它的两个对应前缀路径是<(I2I1:1)>和<(I2I1I3:1)>，它们形成I5的条件模式基。它的条件FP-树只包含单个路径<(I2:2I1:2)>；不包含I3，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2I5:2,I1I5:2,I2I1I5:2。6.2.4不产生候选挖掘频繁项集6.2.4不产生候选挖掘频繁项集对于I4，它的两个前缀形成条件模式基{(I2I1:1),(I2:1)，产生一个单结点的条件FP-树<I2:2>，并导出一个频繁模式I2I4:2。注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁模式在I5的考察时已经分析过。这就是我们为什么由后面，而不是由前面开始处理的原因。6.2.4不产生候选挖掘频繁项集与以上分析类似，I3的条件模式基是{(I2I1:2),(I2:2),(I1:2)}。它的条件FP-树有两个分枝<I2:4,I1:2>和<I1:2>，如图6.9所示，它产生模式集：{I2I3:4,I1I3:2,I2I1I3:2}。最后，I1的条件模式基是{(I2,4)}，它的FP-树只包含一个结点<I2:4>，产生一个频繁模式I2I1:4。挖掘过程总结在图不产生候选挖掘频繁项集算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D；最小支持度阈值min_sup。输出：频繁模式的完全集。方法：1．按以下步骤构造FP-树：(a)扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。6.2.4不产生候选挖掘频繁项集(b)创建FP-树的根结点，以“null”标记它。对于D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为[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非空，递归地调用insert_tree(P,N)。6.2.4不产生候选挖掘频繁项集6.2.4不产生候选挖掘频繁项集FP-增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP-树是不现实的。一种有趣的替换是首先将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP-树并挖掘它。该过程可以递归地用于投影数据库，如果它的FP-树还不能放进内存。对FP-树方法的性能研究表明：对于挖掘长的和短的频繁模式，它都是有效的和可规模化的，并且大约比Apriori

算法快一个数量级。它也比树-投影算法快。树-投影算法递归地将数据库投影为投影数据库树。6.2.5冰山查询Apriori

算法可以用来提高回答冰山查询的效率。冰山查询在数据挖掘中经常用，特别是对购物篮分析。冰山查询在一个属性或属性集上计算一个聚集函数，以找出大于某个指定阈值的聚集值。给定关系R，它具有属性a_1,a_2,...,a_n

和b，一个聚集函数agg_f，冰山查询形如：6.2.5冰山查询给定大量输入数据元组，满足having子句中的阈值的输出元组数量相对很少。输出结果看作“冰山顶”，而“冰山”是输入数据集。例6.4一个冰山查询：假定给定销售数据，你想产生这样的一个顾客-商品对的列表，这些顾客购买商品的数量达到3件或更多。这可以用下面的冰山查询表示：6.2.5冰山查询SelectP.cust_ID,P.Item_ID,SUM(P.qty)FromPurchasesPgroupbyP.cust_ID,Pitem_IDHavingSUM(P.qty)>=36.2.5冰山查询“如何回答例6.4的查询？”一个常用的策略是使用散列或排序，对所有顾客-商品分组，计算聚集函数SUM的值，然后删除被给定的顾客购买的商品数量少于3的那些。相对于处理的元组总数，满足该条件的元组多半很少，为改进性能留下了空间。我们可以使用Apriori

性质的变形，裁减需要考虑的顾客-商品对。即，不是考查每个顾客购买的每种商品的数量，我们可以：6.2.5冰山查询6.2.5冰山查询由先验知识，我们可以删除许多被散列/排序方法产生的顾客-商品对：仅对cust_list

中的顾客和在item_list

中的商品产生候选顾客-商品对。对每个这样的对，维持一个计数。尽管该方法通过预先裁减许多对或分组提高了性能，所产生的顾客-商品对数量可能依然很大，不能放进内存。可以将散列和选样策略集成到该过程，帮助提高该查询回答技术的总体性能。6.2.5冰山查询6.2.5冰山查询6.2.5冰山查询多层关联规则(1)数据项中经常会形成概念分层底层的数据项，其支持度往往也较低这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTIDItemsT1{IBMD/C,Sonyb/w}T2{M.Sw.,Ms.fin.Sw.}T3{Logi.mouse,Ergowaywristpad}T4{IBMD/C,Ms.Fin.Sw.}T5{IBMD/C}Ergoway多层关联规则(2)在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的通常，事务数据库中的数据也是根据维和概念分层来进行储存的这为从事务数据库中挖掘不同层次的关联规则提供了可能。在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力挖掘多层关联规则的方法通常，多层关联规则的挖掘还是使用置信度－支持度框架，可以采用自顶向下策略请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数每一层的关联规则挖掘可以使用Apriori等多种方法例如：先找高层的关联规则：computer->printer[20%,60%]再找较低层的关联规则：laptop->colorprinter[10%,50%]多层关联——一致支持度一致支持度：对所有层都使用一致的最小支持度优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索缺点：最小支持度值设置困难太高：将丢掉出现在较低抽象层中有意义的关联规则太低：会在较高层产生太多的无兴趣的规则多层关联——递减支持度使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难递减支持度：在较低层使用递减的最小支持度每一层都有自己的一个独立的最小支持度抽象层越低，对应的最小支持度越小min_sup=5%min_sup=5%min_sup=3%多层关联——搜索策略(1)具有递减支持度的多层关联规则的搜索策略逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的（P165,图6-14）(computer)(laptopcomputer,desktopcomputer)层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的（P165,图6-15）(computer,printer)((laptopcomputer,colorprinter),(desktopcomputer,b/wprinter)…)多层关联——搜索策略(2)搜索策略比较逐层独立策略条件松，可能导致底层考察大量非频繁项层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项（图6-14)受控的层交叉单项过滤策略层交叉单项过滤策略的改进版本设置一个层传递临界值，用于向较低层传递相对频繁的项。即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生min_sup=12%level_passage_support=8%min_sup=3%检查冗余的多层关联规则挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的例如：desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中，我们说第一个规则是第二个规则的“祖先”如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。多维关联规则——概念单维关联规则：buys(X,“milk”)＝buys(X,“bread”)多维关联规则：涉及两个或多个维或谓词的关联规则维间关联规则：不包含重复的谓词age(X,”19-25”)∧occupation(X,“student”)=>buys(X,“coke”)混合维关联规则：包含某些谓词的多次出现age(X,”19-25”)∧buys(X,“popcorn”)=>buys(X,“coke”)在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。例如：{age,occupation,buys}是一个3-谓词集挖掘多维关联规则的技术数据属性可以分为分类属性和量化属性分类属性具有有限个不同值，值之间无序量化属性数值类型的值，并且值之间有一个隐含的序挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：1.量化属性的静态离散化使用预定义的概念分层对量化属性进行静态地离散化2.量化关联规则根据数据的分布，将量化属性离散化到“箱”3.基于距离的关联规则考虑数据点之间的距离，动态地离散化量化属性多维关联规则挖掘——使用量化属性的静态离散化量化属性使用预定义的概念分层，在挖掘前进行离散化数值属性的值用区间代替如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描数据立方体技术非常适合挖掘多维关联规则n-维方体的单元用于存放对应n-谓词集的计数或支持度，0-D方体用于存放任务相关数据的事务总数如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘量化关联规则(1)量化关联规则中，数值属性将根据某种挖掘标准，进行动态的离散化例如：最大化挖掘规则的置信度和紧凑性为了简化量化关联规则挖掘的讨论，我们将聚焦于类似以下形式的2-维量化关联规则：Aquan1

Aquan2Acat（两个量化属性和一个分类属性间的关联）例如：age(X,”30-39”)income(X,”42K-48K