关联规则挖掘综述_5.docx

《关联规则挖掘综述_5.docx》由会员分享，可在线阅读，更多相关《关联规则挖掘综述_5.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关联规则挖掘综述关联规则挖掘综述本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算法进行了分析和评价，指出传统关联规则衡量标准的缺乏，归纳出关联规则的价值衡量方法，瞻望了关联规则挖蔡伟杰张晓辉朱建秋朱扬勇2复旦大学计算机科学系上海200433摘要：本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算法进行了分析和评1价，指出传统关联规则衡量标准的缺乏，归纳出关联规则的价值衡量方法，瞻望了关联规则挖掘的将来研究方向。关键词：数据挖掘，关联规则，频集，OLAP1引言数据挖掘DataMining，又称数据库中的知识发现KnowledgeDiscoveryin

2、Database，在近期几年里已被数据库界所广泛研究，其中关联规则AssociationRules的挖掘是一个重要的问题。关联规则是发现交易数据库中不同商品项之间的联络，这些规则找出顾客购买行为形式，如购买了某一商品对购买其他商品的影响。发现这样的规则能够应用于商品货架设计、货存安排以及根据购买形式对用户进行分类。Agrawal等于1993年1首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后众多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。近期也有独立于Agrawal

3、的频集方法的工作18,19，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。同时随着OLAP技术的成熟和应用，将OLAP和关联规则结合20,21也成了一个重要的方向。也有一些工作6注重于对挖掘到的形式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。本文第二部分是对关联规则基本概念的介绍，提出了关联规则的分类方法；第三部分是对挖掘算法的介绍，从经典的apriori开场，然后描绘了对该算法的优化拓展，接着讲述脱离apriori算法的方法，最后是多层、多维的关联规则挖掘；第四部分归纳出关联规则价值衡量方法，主要从两个方面进行考虑：系统客观层面和用户主观层面；最后瞻望了关联规则挖掘的将

4、来研究方向。2关联规则的基本概念2.1基本概念和问题描绘设I=i1,i2,im是二进制文字的集合，其中的元素称为项(item)。记D为交易(transaction)T的集合，这里交易T是项的集合，并且TI。对应每一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，假如XT，那么称交易T包含X。一个关联规则是形如XTY的蕴涵式，这里XI,YI，并且XY=F。规则XTY在交易数据库D中的支持度support是交易集中包含X和Y的交易数与所有交易数之比，记为support(XTY)，即support(XTY)=|T:XYT，TD|/|D|规则XTY在交易集中的可信度confidenc

5、e是指包含X和Y的交易数与包含X的交易数之比，记为confidence(XTY)，即confidence(XTY)=|T:XYT，TD|/|T:XT，TD|给定一个交易集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。2.2关联规则的种类我们将关联规则按不同的情况进行分类：1.基于规则中处理的变量的类别，关联规则能够分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则能够和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原

6、始的数据进行处理，当然数值型关联规则中可以以包含种类变量。例如：性别=“女=职业=“秘书，是布尔型关联规则；性别=“女=avg收入=2300，涉及的收入是数值类型，所以是一个数值型关联规则。2.基于规则中数据的抽象层次，能够分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=Sony打印机，是一个细节数据上的单层关联规则；台式机=Sony打印机，是一个较高层次和细节层次之间的多层关联规则。3.基于规则中涉及到的数据的维数，关联规则能够分为单维的和多维的。在单维的

7、关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=尿布，这条规则只涉及到用户的购买的物品；性别=“女=职业=“秘书，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。给出了关联规则的分类之后，在下面的分析经过中，我们就能够考虑某个详细的方法适用于哪一类规则的挖掘，某类规则又能够用哪些不同的方法进行处理。3关联规则挖掘的算法3.1经典频集方法Agrawal等于1993年1首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核

8、心方法是基于频集理论的递推方法。以后众多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。3.1.1核心算法Agrawal等1在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计能够分解为两个子问题：1.找到所有支持度大于最小支持度的项集Itemset，这些项集称为频集FrequentItemset)。2.使用第1步找到的频集产生期望的规则。这里的第2步相对简单一

9、点。如给定了一个频集Y=I1I2.Ik，k32，IjI，产生只包含集合I1，I2，.，Ik中的项的所有规则(最多k条)，其中每一条规则的右部只要一项，(即形如Y-IiTIi，1ik)，这里采用的是4中规则的定义。一旦这些规则被生成，那么只要那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则，在其以后的工作中进行了研究，本文后面考虑的是这种情况。为了生成所有频集，使用了递推的方法。其核心思想如下：1.L1=large1-itemsets;2.for(k=2;Lk-11F;k+)dobegin3.Ck=apriori-gen(Lk-1);/新的候选集4.foralltra

10、nsactionstDdobegin5.Ct=subset(Ck,t);/事务t中包含的候选集6.forallcandidatescCtdo7.c.count+;8.end9.Lk=cCk|c.count3minsup10.end11.Answer=kLk;首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，经过先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只要一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中

11、进行验证来决定其能否参加Lk，这里的验证经过是算法性能的一个瓶颈。这个方法要求屡次扫描可能很大的交易数据库，即假如频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。在论文6中，Agrawal等引入了修剪技术Pruning来减小候选集Ck的大小，由此能够显著地改良生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，假如Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集能够被修剪掉不再被考虑，这个修剪经过能够降低计算所有的候选集的支持度的代价。文6中，还引入杂凑树HashTree方法来有效地计算

12、每个项集的支持度。3.1.2频集算法的几种优化方法固然Apriori算法本身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。1.基于划分的方法。Savasere等14设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块能够被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是能够高度并行的

13、，能够把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信经过是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间分享一个杂凑树来产生频集。更多的关于生成频集的并行化方法能够在2,11,17中找到。2.基于hash的方法。一个高效地产生频集的基于杂凑(hash)的算法由Park等10提出来。通过实验我们能够发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改良产生频繁2-项集的方法。3.基于采样的方法。基于前一遍扫描得到

14、的信息，对此仔细地作组合分析，能够得到一个改良的算法，Mannila等8先考虑了这一点，他们以为采样是发现规则的一个有效途径。随后又由Toivonen16进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不准确，即存在所谓的数据扭曲(dataskew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中形式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在7中讨论了反扭

15、曲(Anti-skew)算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来采集有关数据的次数来减少扫描遍数。Brin等4提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改良了算法在低层的效率。详细的考虑是，在计算k-项集时，一旦我们以为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则CorrelationRules的一个新方法，这是基于他们的3工作基础上的。4.减少交易的个数。减少用于将来

16、扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。进而我们就能够将这些事务移去，这样在下一遍的扫描中就能够要进行扫描的事务集的个数。这个就是AprioriTid的基本思想。3.2其他的频集挖掘方法上面我们介绍的都是基于Apriori的频集方法。即便进行了优化，但是Apriori方法一些固有的缺陷还是无法克制：1.可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集个数将会超过10M。还有就是假如要生成一个很长的规则的时候，要产生的中间元素也是宏大量的。2.无法对稀有信息进行分析。由于频集使用了参数minsup，所以

17、就无法对小于minsup的事件进行分析；而假如将minsup设成一个很低的值，那么算法的效率就成了一个很难处理的问题。下面将介绍两种方法，分别用于解决以上两个问题。在18中提到了解决问题1的一种方法。采用了一种FP-growth的方法。他们采用了分而治之的策略：在经过了第一次的扫描之后，把数据库中的频集压缩进一棵频繁形式树FP-tree，同时仍然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，可以以结合划分的方法,使得一个FP-tree能够放入主存中。实验表明，FP-growth对不同长度的

18、规则都有很好的适应性，同时在效率上较之apriori算法有宏大的提高。第二个问题是基于这个的一个想法：apriori算法得出的关系都是频繁出现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即便这些元素不是频繁出现的。在apriori算法中，起决定作用的是支持度，而我们如今将把可信度放在第一位，挖掘一些具有非常高可信度的规则。在19中介绍了对于这个问题的一个解决方法。整个算法基本上分成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有两类：Min_Ha

19、shing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分类，使得类似的列在一起的可能性更大，不类似的列在一起的可能性较小。我们再对这两个方法比拟一下。MH的遗漏率为零，错误率能够由k严格控制，但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视详细的情况而定。最后的实验数据也讲明这种方法确实能产生一些有用的规则。3.3

20、多层和多维关联规则的挖掘随着数据仓库和OLAP技术研究的深化，能够预见大量的数据将经过整合、预处理，进而存入数据仓库之中。在当前，大多数的数据仓库的应用都是进行统计、建立多维以及OLAP的分析工作。随着数据挖掘研究的深化，已经有了OLAP和数据挖掘相结合的方法20,21。首先一个有效的数据挖掘方法应该能够进行探索性的数据分析。用户往往希望能在数据库中穿行，选择各种相关的数据，在不同的细节层次上进行分析，以各种不同的形式呈现知识。基于OLAP的挖掘就能够提供在不同数据集、不同的细节上的挖掘，能够进行切片、切块、展开、过滤等各种对规则的操作。然后再加上一些可视化的工具，就能大大的提高数据挖掘的灵敏

21、性和能力。接着，我们来看一下多层和多维关联规则的定义。多层关联规则：对于很多的应用来讲，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就能够在较高的层次上进行挖掘。固然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来讲是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。多层关联规则的分类：根据规则中涉及到的层次，多层关联规则能够分为同层关联规则和层间关联规则。多层关联规则的挖掘基本上能够沿用“支持度-可信度的框架。不过，在支持度设置的问题上有一些要考虑的东西。同层关联规则能够采用两种支持度策略：

22、1.统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来讲都比拟的容易，但是弊端也是显然的。2.递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还能够利用上层挖掘得到的信息进行一些过滤的工作。层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。多维关联规则：以上我们研究的基本上都是同一个字段的值之间的关系，比方用户购买的物品。用多维数据库的语言就是单维或者叫维内的关联规则，这些规则一般都是在交易数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关联规则。例如：年龄X，“20.30职业X,“学生=购买(X，“笔记

23、本电脑)在这里我们就涉及到三个维上的数据：年龄、职业、购买。根据能否允许同一个维重复出现，能够又细分为维间的关联规则不允许维重复出现和混合维关联规则允许维在规则的左右同时出现。年龄X，“20.30购买(X，“笔记本电脑)=购买(X，“打印机)这个规则就是混合维关联规则。在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都能够处理。而对于数值型的字段，需要进行一定的处理之后才能够进行。处理数值型字段的方法基本上有下面几种：1.数值字段被分成一些预定义的层次构造。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。2.数值字段

24、根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联规则。3.数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。得出的规则叫基于距离的关联规则。4.直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比拟进而得出一些有用的规则。得出的规则叫多层数量关联规则。在OLAP中挖掘多层、多维的关联规则是一个很自然的经过。由于OLAP本身的基础就是一个多层多维分析的工具，只是在没有使用数据挖掘技术之前，OLAP只能做一些简单的统

25、计，而不能发现其中一些深层次的有关系的规则。当我们将OLAP和DataMining技术结合在一起就构成了一个新的体系OLAMOn-LineAnalyticalMining20。4关联规则价值衡量的方法当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统怎样知道哪些规则对于用户来讲是有用的、有价值的？这里有两个层面：用户主观的层面和系统客观的层面。4.1系统客观层面：很多的算法都使用“支持度-可信度的框架。这样的构造有时会产生一些错误的结果。看如下的一个例子：假设一个提供早餐的零售商调查了4000名学生在早晨进行什么运动，得到的结果是2200名学生打篮球，2750名学生晨跑，1800名学生打篮

26、球、晨跑。那么假如设minsup为40%，minconf为60%，我们能够得到如下的关联规则：打篮球T晨跑1这条规则其实是错误的，由于晨跑的学生的比例是68%，甚至大于60%。然而打篮球和晨跑可能能否定关联的，即当我们考虑如下的关联时：打篮球T不晨跑2固然这条规则的支持度和可信度都比那条蕴涵正向关联的规则1低，但是它更准确。然而，假如我们把支持度和可信度设得足够低，那么我们将得到两条矛盾的规则。但另一方面，假如我们把那些参数设得足够高，我们只能得到不准确的规则。总之，没有一对支持度和可信度的组合能够产生完全正确的关联。于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉的关联规则。一般一

27、条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之比，然而在很多应用中已发现，只要人们仍把支持度作为最初的项集产生的主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的规则，或者冒丢失一些重要规则的风险；对前一种情形计算效率是个问题，而后一种情形则有可能丢失从用户观点来看是有意义的规则的问题。在12中作者给出了感兴趣的规则的定义R-interesting，在13中他们又对此作了改良。在10中把事件依靠性的统计定义扩展到兴趣度的定义上来；15定义了否认关联规则的兴趣度。除了把兴趣度作为修剪无价值规则的工具，如今已有很多其他的工作来重新认识项集，如Brin等3考虑的相关规则

28、。在4中讨论了蕴涵规则(implicationrule)，规则的蕴涵强度在0,￥之间变化，其中蕴涵强度为1表示完全无关的规则，￥表示完备的规则，假如蕴涵强度大于1则表示更大的期望存在性。另一个度量值“采集强度(collectivestrength)在22中被定义，他们设想使用“大于期望值来发现有意义的关联规则。项集的“采集强度是0,￥之间的一个数值，其中0表示完备的否认相关性，而值￥表示完备的正相关性。具体的讨论能够在10中找到。4.2用户主观层面：上面的讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于用户的感觉。只要用户能够决定规则的有效性、可行性。所以我们应该将用户的需求和系统

29、愈加严密的结合起来。能够采用一种基于约束(consraint-based)21的挖掘。详细约束的内容能够有：1.数据约束。用户能够指定对哪些数据进行挖掘，而不一定是全部的数据。2.指定挖掘的维和层次。用户能够指定对数据哪些维以及这些维上的哪些层次进行挖掘。3.规则约束。能够指定哪些类型的规则是我们所需要的。引入一个模板template的概念，用户使用它来确定哪些规则是令人感兴趣的而哪些则不然：假如一条规则匹配一个包含的模板inclusivetemplate，则是令人感兴趣的，然而假如一条规则匹配一个限制的模板rextrictivetemplate，则被以为是缺乏兴趣的。其中有些条件能够和算法严

30、密的结合，进而即提高了效率，又使挖掘的目的愈加的明确化了。其他的方法还有：Kleinberg等人的工作是希望建立一套理论来判定所得形式的价值，他们以为这个问题仅能在微观经济学框架里被解决，他们的模型提出了一个能够发展的方向。他们引入并研究了一个新的优化问题分段(Segmentation)问题，这个框架包含了一些标准的组合分类问题。这个模型根据基本的目的函数，对“被挖掘的数据的价值提供一个特殊的算法的视角，显示了从这方面导出的详细的优化问题的广泛的应用领域。在5中Korn等就利用猜想误差(这里他们使用“均方根来定义)来作为一些从给定的数据集所发现的规则的“好处(goodness)的度量，他们所定

31、义的比例规则就是如下的规则：顾客大多数分别花费1:2:5的钱在“面包:“牛奶:“奶油上通过确定未知的(等价的，被隐藏的，丢失的)值，比例规则能够用来作决策支持。假如数据点线性地相关的话，那么比例规则能到达更紧凑的描绘，即关联规则更好地描绘了相关性。5.结论与瞻望本文讨论了数据挖掘中产生关联规则的方法以及它的应用，这方面一些研究成果已获得很大的成绩，并已被集成在一些系统中，如IBM的Quest项目，SimonFarse大学的DBMiner等。详细的内容有经典频集算法，对频集算法的优化，扩展。然后讨论了在OLAP下进行数据挖掘的一些内容。接着是对规则价值的一些评价方法。对于关联规则的发展，我们觉得

32、能够在下面一些方向上进行近一步的深化研究。在处理极大量的数据时，怎样提高算法效率的问题；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的经过中，提供一种与用户进行交互的方法，将用户的领域知识结合在其中；对于数值型字段在关联规则中的处理问题；生成结果的可视化方面等等。参考文献1R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.ProceedingsoftheACMSIGMODConferenceonManagementofdata,pp.207-216,199

33、3.2R.Agrawal,andJ.Shafer.Parallelminingofassociationrules:Design,Implementation,andExperience.TechnicalReportFJ10004,IBMAlmadenResearchCenter,SanJose,CA95120,Jan.1996.3S.Brin,R.Motwani,andC.Silverstein.Beyondmarketbaskets:generlizingassociationrulestocorrelations.ProceedingsoftheACMSIGMOD,1996.pages

34、255-276.4S.Brin,R.Motwani,J.D.Ullman,andS.Tsur.DynamicItemsetcountingandimplicationrulesformarketbasketdata.InACMSIGMODInternationalConferenceOntheManagementofData.1997.5F.Korn,A.Labrinidis,Y.Kotidis,andC.Faloutsos.Ratiorules:Anewparadigmforfast,quantifiabledatamining.6J.Kleinberg,C.Papadimitriou,an

35、dP.Raghavan.Segmentationproblems.Proceedingsofthe30thAnnualSymposiumonTheoryofComputing,ACM.1998.7J.L.Lin,andM.H.Dunham.Miningassociationrules:Anti-skewalgorithms.ProceedingsoftheInternationalConferenceonDataEngingeering,Orlando,Florida,February1998.8H.Mannila,H.Toivonen,andA.Verkamo.Efficientalgori

36、thmfordiscoveringassociationrules.AAAIWorkshoponKnowledgeDiscoveryinDatabases,1994,pp.181-192.9R.Ng,L.V.S.Lakshmanan,J.Han,andA.Pang.Exploratoryminingandpruningoptimizationsofconstrainedassociationsrules.ProceedingsofACMSIGMODInternationalConferenceonManagementofData,pates13-24,Seattle,Washington,Ju

37、ne1998.10J.S.Park,M.S.Chen,andP.S.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.ProceedingsofACMSIGMODInternationalConferenceonManagementofData,pages175-186,SanJose,CA,May1995.11J.S.Park,M.S.Chen,andP.S.Yu.Efficientparalleldataminingofassociationrules.4thInternationalConferenceonInforma

38、tionandKnowledgeManagement,Baltimore,Maryland,Novermber1995.12R.Srikant,andR.Agrawal.Mininggeneralizedassociationrules.Proceedingsofthe21stInternationalConferenceonVeryLargeDatabase,1995,pp.407-419.13R.Srikant,andR.Agrawal.Miningquantitativeassociationrulesinlargerelationaltables.ProceedingsoftheACM

39、SIGMODConferenceonManagementofData,1996.pp.1-12.14A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationrulesinlargedatabases.Proceedingsofthe21stInternationalConferenceonVerylargeDatabase,1995.15A.Savasere,E.Omiecinski,andS.Navathe.Miningforstrongnegativeassociationsinalarged

40、atabaseofcostomertransactions.ProceedingsoftheInternationalConferenceonDataEngineering,February1998.16H.Toivonen.Samplinglargedatabasesforassociationrules.Proceedingsofthe22ndInternationalConferenceonVeryLargeDatabase,Bombay,India,September1996.17M.J.Zaki,S.Parthasarathy,andW.Li.Alocalizedalgorithmfor