颜雪松,-关联规则挖掘综述

关联规则挖掘综述

*

颜雪松,蔡之华,蒋良孝,贺󰀁毅

(中国地质大学信息工程学院,湖北武汉430074)

摘󰀁要:介绍了关联规则挖掘的一般概念,并进一步导出它的一般框架;同时对一些典型算法进行了分

析和比较,介绍了关联规则的应用;最后展望了关联规则挖掘的未来研究方向。关键词:关联规则;频繁项目集;深度优先遍历;宽度优先遍历

中图法分类号:TP301󰀂6󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁文章编号:1001󰀁3695(2002)11󰀁0001󰀁04

SurveyofAssociationRuleMining

YANXue󰀁song,CAIZhi󰀁hua,JIANGLiang󰀁xiao,HEYi

(CollegeofInformationEngineering,ChinaUniversityofGeosciences,WuhanHubei430074,China)

Abstract:Inthispaperweexplainthefundamentsofassociationruleminingandmoreoverderiveageneralframework.Atthesame

timecomparesandanalysessometypicalalgorithms,introducestheapplicationoftheassociationrules.Attheend,viewssomefuturedirectionsinassociationrulegeneration.

Keywords:AssociationRule;FrequentItemsets;DFS;BFS

1󰀁引言

面对海量的存储数据,如何从中发现有价值的信息或知识是一项非常艰巨的任务。数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智能和数据库发展相结合的产物,是目前国际上数据库和信息决策系统最前沿的研究方向之一,已引起了学术界和工业界的广泛关注。目前研究的主要目标是发展有关理论、方法和工具,以支持从大量数据中提取有价化的知识和模式。在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。它是由R.Agrawal等人首先提出的。关联规则的一个典型例子就是:󰀂90%的客户在购买面包的同时也会购买牛奶 ,其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。

Beer}=2。

TID12345

Items

Bread,Coke,MilkBeer,Bread

Beer,Coke,Diaper,MilkBeer,Bread,Diaper,MilkCoke,Diaper,Milk

图1󰀁TransactionsfromSupermarket

关联规则可描述为:!XY,X I,Y I。关联规则X!Y的支持度s定义为:󰀁(X∀Y)/|T|,置信度󰀂定义为󰀁(X∀Y)/󰀁(X)。例如,假设一条规则{Diaper,Milk}!{Beer},表示如果Diaper和Milk在一个事务中,就意味着Beer也包含在这个事务中。这条规则的支持度是:󰀁(Di󰀁aper,Milk,Beer)/5=40%。置信度为󰀁(Diaper,Milk,Beer)/󰀁(Diaper,Milk)=66%。如果一条规则的置信度很高的话,就说明这条规则很重要,因为它可以在规则中给项目关联提供精确的预测。同样的,规则的支持度也很重要,它可以暗示在事务中这条规则的出现频率有多高。支持度很低的规则通常是引不起人们的兴趣的。

[2]

这就是为什么大多数的算法忽视那些不能满足用户给定的最小支持度条件的规则的原因。这种用给定最小支持度过滤规则的方法可以减少产生的关联规则的数量,以便于管理。因为算法可能产生的规则的数量和项目集I的子集的数量是成比例的,可能达到2|I|,因此,这种过滤在实际应用中是必需的。

发现关联规则的任务就是发现所有形如X!Y的规则,规则的支持度大于或等于给定的最小支持度,规则的置信度大于或等于给定的最小置信度。发现关联规2󰀁关联规则的基本概念

假设T是事务的集合,在T中的每一个事务都是项目集I的子集。假设C是I的一个子集,我们定义C的支持度如下:󰀁(C)=|{t|t!T,C t}|。󰀁(C)表示包含在C中的事务的数目。例如图1所示的事务集。事务的项目集I是{Bread,Beer,Coke,Diaper,Milk}。{Diaper,Milk}的支持度是󰀁{Diaper,Milk}=3,而󰀁{Diaper,Milk,

收稿日期:2001󰀁12󰀁14;修返日期:2002󰀁04󰀁28

基金项目:湖北省自然科学基金资助项目(2001ABB006)󰀁󰀁#2#计算机应用研究2002年

则可以分为两步:一是发现所有频繁项目集;二是从频繁项目集中产生关联规则。发现频繁项目集的计算量远远大于从这些频繁项目集中发现规则,因此在关联规则挖掘过程中集中讨论的是第一步。

有项目集是由父类E∋的两个项目集联合而产生的话,那么两个节点是由一条边相连的,如图3所示。

3󰀁关联规则挖掘算法概述

实际上,一批有效的挖掘关联规则的算法在过去几年中得到了长足的发展。在这些年里,许多特殊任务算法已经取得了长足的发展。首先,有了提高关联规则自身的方法∃∃∃例如量化关联规则[24];普通关联规则[23,12]和序列模式[3,15]。此外,还有几个关于规则问题的概括[16,27]。除此之外,算法在挖掘规则集合的子集上有了长足的发展,这些子集是根据特殊项目或属性测量定义的,例如普通约[17,25][8,20][28]束、有效规则、最大频繁项目集和频繁封闭项目集[18,19];并且还有挖掘密集型数据库的算法[5],以及联机关联规则挖掘算法[10]和增量算法[26,4]。

图3󰀁TreeforI={1,2,3,4}

3󰀂1󰀁算法背景

我们需要寻找满足最小支持度(Minsupp)的所有项目集。在实际应用中,要在巨大的查找空间里寻找I的所有子集是注定要失败的。实际上,项目的直线增长依然暗示着项目集的呈指数增长。对于特殊事件I={1,2,3,4},我们把查找空间形象化为格子,如图2所示。频繁项目集位于等级较高部分,而非频繁发生的位于较低的部分。虽然我们没有明确地定义每个项目集的支持度,我们假设边界是使频繁项目集从非频繁项目集中出来的因素,对于任何一个特定的数据库D和Min󰀁supp都存在着这样一个边界。

图2󰀁LatticeforI={1,2,3,4}

普通算法的基本原理是利用这个边界有效地删减查找空间。一旦边界被找到,我们就能够自己定义在这个边界上的项目集的支持度,同时忽略位于边界之下的项目集。

示意图:I%{1,&,|I|},描述了所有项目X!I逐个到原始数目之上的示意图。现在项目通过用󰀂< 排序以后能够全部被看见。除此之外,对X I,让X.item:{1,&,|X|}%I:n%X.itemn作为描述X.itemn的元素,X.itemn表示用󰀂< 排列的项目x!X的第n个项目。一个项目集X(n∀|X|)的前缀n可以定义为:P={X.item|1∀m∀n}。类E(P)(E(P)={X I||X|=|P|

m

在这里项目集支持度向下终止属性暗示了以下内容:如果类E的父类E∋没有包含两个以上的频繁项目集的话,E一定没有包括任何频繁项目集。如果我们在树中遇到这样一个类E∋,我们应当利用边界把非频繁项目集从频繁项目集中分隔出来,要从查找空间中删减E和E∋的所有后代。后面的过程允许我们有效地研究的项目集的数目。我们简单地定义项目集的支持度,这些项目集是我们在寻找频繁项目集和非频繁项目集的边界时访问过的。最后,寻找边界的真正的策略是我们自己的选择。现在常用的方法是宽度优先搜索(BFS)和深度优先搜索(DFS)。在BFS中,所有(k󰀁1)维项目集的支持度是在计算k维项目集支持度之前定义的。相反的,DFS是随着上面定义的树形结构下降的。

下面有这样一个定义:一个项目集是潜在的频繁项目集,并且我们在搜索格子时定义它的支持度叫做候选项目集或简称候选者。一个定义项目集支持度一般的方法是直接计算它在数据库中出现的次数。为了这个目的,计算者把每个需要研究的项目集都挑选出来并初始化为零,接着扫描所有的事务,当候选者成为事务的子集而被识别时,则计数增加。这样典型子集的产生和候选者的产生看起来是组合在一起的,并且用于哈希树或相似的数据结构。简言之,并不是每个事务的所有子集都是产生出来的,只有那些包含在候选者中或者那些至少有一个候选者和前缀的子集。

另一个定义候选者支持度的方法是集合交叉。Tid是事务的惟一标志符。对于单独的项目,Tidlist是和包含这个项目的事务相一致的标志符集合。存在的一个项目集X的Tidlist可以表示为X.tidlist。候选者C=X∀Y的Tidlist可以这样得到:C.tidlist=X.tidlist(Y.TIDList。Tidlist按升序排列并且允许交叉。

通过缓冲频繁候选者作为交叉结果来表示Tidlist,我们可以加速后继候选者Tidlist的产生。最后候选者的支持度是通过定义|C.tidlist|来得到的。

3󰀂2󰀁算法描述3󰀂2󰀂1󰀁系统化

本文中提到的算法在图4中被系统化。

+1,P是X的前缀}),P I是树的节点。假如类E的所图4󰀁SystematizationoftheAlgorithm

我们描述每一种算法的特性可分为两步:(1)搜索第11期颜雪松等:关联规则挖掘综述#3󰀁#󰀁

查找空间的策略;(2)定义项目集支持度的策略。除此

之外,一种算法可能使用更有效的方法以进一步提高效率。

3󰀂2󰀂2󰀁BFS和出现频度计算

关于这种类型的最流行的算法是Apriori[2],它介绍了项目集支持度的向下终止属性。Apriori算法通过在计算支持度之前删减那些非频繁子集的事务来增加附加的属性。使这种有效的方法成为可能的原因是:BFS保证了一个事务的所有子集的支持度预先都是知道的。Apriori算法扫描整个数据库来计算所有事务的支持度。重要的步骤是查寻每一个事务中的候选者。为了这个目的,文献[2]介绍了一种叫哈希树的结构。哈希树中每一事务的项目都是下降的,不管什么时候到达它的叶子,我们将发现有一批候选者已经有了包含在事务中的普通前缀了;接着,在事务中寻找这些已经被转化为位图的候选者,如果寻找成功的话,候选者的计数增加。

[2]

AprioriTID算法是Apriori算法的扩展。除了依赖原始数据库以外,AprioriTID还通过自身的候选者来表示每一个事务。AprioriHybrid是上面两种算法的组合[2]。在一定范围内,SETM[13]是一个类似于AprioriTID的算法,它可以直接使用SQL语句。

DIC是Apriori[7]算法的进一步变种。DIC弱化了计算候选者和产生候选者之间的严格界线。当一个候选者达到了Minsupp,就算这个候选者在所有事务中不可见,DIC也将产生这个额外的候选者。前缀树的使用就是为了这个目的。和哈希树相反的是,前缀树的每一个节点、叶节点或内节点都是和代表频繁项目集的候选者相对应的。和哈希树用法相反之处在于:当到达一个节点时,我们可以确定和这个节点相关联的项目集是包含在事务中的。此外,连锁支持度定义和候选者产生减少了扫描数据库的次数。

有一个新方法叫FP󰀁growth[9]。在FP󰀁growth的预处理过程中导出了关于事务数据高度浓缩的描述,叫做FP-树。FP-树是由DFS和出现频度计算产生的。和前面的DFS方法相反,FP󰀁growth不是跟随树节点的,而是直接跟着查找空间的部分项目集下降的。在第二步,FP󰀁growth利用FP-树导出所有频繁项目集的支持度。

3󰀂2󰀂5󰀁DFS和TID󰀁List交叉

在文献[28]中,介绍了一种Eclat算法,它是DFS和Tidlist交叉的组合运用。当运用DFS,它能够保证现在研究的从根部到内存的路径的Tidlist。因此,像Partition算法那样拆分数据库就不是很必要了。

Eclat算法使用了一个叫做󰀂快速交叉 的有效方法。无论我们什么时候交叉两个Tidlist,我们只能交叉那些满足Minsupp的结果Tidlist。换句话说,我们要中断每一个不符合条件的交叉。Eclat只产生那些Size#3的频繁项目集。我们通过在它们的Tidlist中包括1󰀁维项目集来改变Eclat算法,使它适用于1󰀁维和2󰀁维项目集。

除此之外,在文献[28]中还介绍了一种开采最大频繁项目集的算法∃∃∃MaxEclat。假设对于所有频繁项目集Y,且X Y!Y=X成立,则项目集X是最大频繁项目集。我们不会仔细考虑这些算法,因为虽然它们可以直接从最大频繁项目集中导出所有的频繁项目集,但是这样的话就不能得到一致的支持度了,没有这些,我们就不能导出规则的可信度并产生关联规则了。

4󰀁关联规则的应用

关联规则可以广泛应用于各个领域,既可以检验行业内长期形成的知识模式,也能够发现隐藏的新规律。有效地发现、理解、运用关联规则,是完成数据挖掘任务的一个重要手段。关联规则的应用面很广,如识别欺诈:电子通信行业和信用卡公司在这方面是两个先行者,股票交易所和银行也有这方面的需要;推销商可以用关联规则帮助他们确定客户的主要来源,从而在不减少收入的前提下节约不必要的开支;商场根据关联规则计划进什么货、如何摆放货物;关联规则在医学上的应用也有重大意义,可以预测一次手术、药物检验、药物治疗的效果。

3󰀂2󰀂3󰀁BFS和TID󰀁List交叉

Partition算法[2]是一种类似于Apriori的算法,它利用集合交叉来定义支持度。与上面描述的Apriori算法一样,定义所有(k󰀁1)维候选者的支持度要在计算k维候选者之后。但是存在一个问题就是:Partition算法想利用频繁的(k󰀁1)维项目集的Tidlist来产生k维候选者的tidlist。显然,这些中间结果很容易超出普通机器的物理存储器的容量。为了克服此问题,Partition算法把数据库拆分为的几块,这些块的大小和主存储器相适应。在对每个数据块的频繁项目集定义以后,需要一次额外的扫描以确保局部频繁项目集是全局中的一部分。

5󰀁结束语

本文讨论了数据挖掘中产生关联规则的方法以及它的应用,在讨论关联规则挖掘算法中我们给出了算法的基本原理和不同点。关联规则挖掘还存在如下的缺点:当问题变大时,计算量增长得厉害;难以决定正确的数据;容易忽略稀有的数据。这些都是我们在以后的研究工作中应该注意的方面。参考文献:

[1]

RAgrawal,TImielinski,ASwami.MiningAssociationRulesbetweenSetsofItemsinLargeDatabases[C].InProc.oftheACMSIGMODInt)lConf.onManagementofData(ACMSIG󰀁MOD)93),Washington,USA,1993󰀂207󰀁216.3󰀂2󰀂4󰀁DFS和出现频度计算

计算出现频度要假设候选集合的大小。对于每一个候选集都要扫描数据库,如Apriori算法依赖于BFS扫描数据库一遍来寻找大小为k的候选者。当利用DFS时,候选集是由文中树的节点表示的项目集构成的。显然扫描数据库中的每一个结果节点的花销是巨大的。DFS和出现频度计算简单地组合没有什么实际的关联关系[11]。󰀁󰀁#4#

[2]

计算机应用研究2002年

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]RAgrawaletal.FastAlgorithmsforMiningAssociationRules

[C].InProc.ofthe20thInt)lConf.onVeryLargeDatabases(VLDB)94),Santiago,Chile,1994.487󰀁499.

RAgrawal,RSrikant.MiningSequentialPatterns[C].InProc.oftheInt)lConf.onDataEngineering(ICDE),Taipei,Tai󰀁wan,1995.3󰀁14.

NFAyan,AUTansel,etal.Arkun.AnEfficientAlgorithmtoUpdateLargeItemsetswithEarlyPruning[C].InProc.ofthe5thInt)lConf.onKnowledgeDiscoveryandDataMining(KDD)99),SanDiego,California,USA,1999.439󰀁450.RJBayardoJr,etal.Constraint󰀁basedRuleMininginLarge,DenseDatabases[C].InProc.ofthe15thInt)lConf.onDataEngineering,Sydney,Australia,1999.85󰀁93.

SBrin,RMotwani,CSilverstein.BeyondMarketBaskets:Gen󰀁eralizingAssociationRulestoCorrelations[C].InProc.oftheACMSIGMODInt)lConf.onManagementofData(ACMSIG󰀁MOD)97),1997.265󰀁276.

SBrin,etal.DynamicItemsetCountingandImplicationRulesforMarketBasketData[C].InProc.oftheACMSIGMODInt)lConf.onManagementofData,1997.123󰀁140.

TFukuda,Y.Morimoto,etal.MiningOptimizedAssociationRulesforNumericAttributes[C].InProc.ofthe15thACMSIGACT󰀁SIGMOD󰀁SIGARTSymp.onPrinciplesofDatabaseSystems(PODS)96),Montreal,Canada,1996.23󰀁32.

JHan,JPei,YYin.MiningFrequentPatternsWithoutCan󰀁didateGeneration[C].InProc.ofthe2000ACM󰀁SIGMODInt)lConf.onManagementofData,Dallas,Texas,USA,2000.1󰀁12.

CHidber.OnlineAssociationRuleMining[C].InProc.ofthe1999ACMSIGMODConf.onManagementofData,1999.106󰀁115.

JHipp,UGiintzer,etal.MiningAssociationRules:DerivingASuperiorAlgorithmbyAnalyzingToday)sApproaches[C].InProc.ofthe4thEuropenConf.onPrinciplesandPracticeofKnowledgeDiscovery,Lyon,France,2000.420󰀁431.

JHipp,etal.ANewAlgorithmforFasterMiningofGeneralizedAssociationRules[C].InProc.ofthe2ndEuropeanSymposiumonPrinciplesofDataMiningandKnowledgeDiscovery(PKDD)98),Nantes,France,1998.1󰀁5.

MHoutsma,ASwami.Set󰀁orientedMiningforAssociationRulesinRelationalDatabases[R].TechnicalReportRJ9567,IBMAlmadenResearchCenter,SanJose,California,1993.25󰀁33.MKlemettinen,etatl.FindingInterestingRulesfromLargeSetsofDiscoveredAssociationRules[C].InProc.ofthe3rdInt)lConf.onInformationandKnowledgeManagement,Gaithers󰀁burg,Maryland,Dez1994.40󰀁49.

HMannila,HToivonen,IVerkamo.DiscoveryofFrequentEp󰀁isodesinEventSequences[J].DataMiningandKnowledgeDiscovery,1997,1(3):41󰀁55.

RMotwani,ECohen,FindingInterestingAssociationsWithoutSupportPruning[C].InProc.ofthe16thInt)lConf.onDataEngineering(ICDE).IEEE,2000.122󰀁133.

RNg,LSLakshmanan,etal.ExploratoryMiningandPruningOptimizationsofConstrainedAssociationsRules[C].InProc.of1998ACMSIGMODInt)lConf.onManagementofData,Seattle,Washington,USA,1998.80󰀁86.

NPasquier,etal.DiscoveringFrequentClosedItemsetsforAs󰀁th

sociationRules[C].InProc.ofthe7Int)lConf.onDatabaseTheory(ICDT)99),Jerusalem,Israel,1999.412󰀁421.

JPei,JHan,RMao.AnEfficientAlgorithmforMiningFre󰀁quentClosedItemsets[C].InProc.ofthe2000ACM󰀁SIGMODInt)lConf.onManagementofData,Dallas,Texas,USA,2000.11󰀁20.

RRastogi,KShim.MiningOptimizedSupportRulesforNu󰀁[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

mericAttributes[C].InProc.ofthe15thInt)lConf.onDataEngineering,Sydney,Australia,1999.13󰀁25.

ADavasers,EOmiecinski,SNavathe.AnEfficientAlgorithmforMiningAssociationRulesinLargeDatabases[C].InProc.ofthe21stConf.onVeryLargeDatabases(VLDB)95),Zurich,Switzerland,1995.105󰀁112.

CSilverstein,SBrin,RMotwani,etal.ScalableTechniquesforMiningCausalStructures[C].InProc.of1998ACMSIGMODInt)lConf.onManagementofData,Seattle,Washington,USA,1998.343󰀁353.

RSrikant,RAgrawal.MiningGeneralizedAssociationRules[C].InProc.ofthe21stConf.onVeryLargeDatabases(VLDB)95),Zurich,Switzerland,1995.407󰀁419.

RSrikant,RAgrawal.MiningQuantitativeAssociationRulesinLargeRelationalTables[C].InProc.ofth1996ACMSIG󰀁MODConf.onManagementofData,Montreal,Canada,1996.1󰀁12.

JHipp,UGuntzeretal.AlgorithmsforAssociationRuleMi󰀁ning󰀁AgeneralSurveyandComparison[C].InProc.of2000ACMSIGMODInt)lConf.onManagementofData,Seattle,Washington,USA,2000.88󰀁98.

RSrikant,etal.MiningAssociationRuleswithItemConstraints

rd

[C].InProc.ofthe3Int)lConf.onKDDandDataMining(KDD)97),NewportBeach,California,1997󰀂67󰀁73.

DTsur,JDUllman,SAbitboul,etal.QueryFlocks:AGen󰀁eralizationofAssociation󰀁ruleMining[C].InProc.of1998ACMSIGMODInt)lConf.onManagementofData,Seattle,Washington,USA,1998󰀂1󰀁12.

SThomas,etal.AnEfficientAlgorithmfortheIncrementalUp󰀁dationofAssociationRulesinLargeDatabases[C].InProc.ofthe3rdInt)lConf.onKDDandDataMining(KDD)97),New󰀁portBeach,California,1997󰀂134󰀁145.

MJZaki,etal.NewAlgorithmforFastDiscoveryofAssociationRules[C].InProc.ofthe3rdInt)lConf.onKDDandDataMining(KDD)97),NewportBeach,California,1997.283󰀁286.

蔡之华,颜雪松,李晖󰀂挖掘关联规则的并行算法研究[J].计算机应用研究,2002,19(2):9󰀁11.

作者简介:

颜雪松,男,硕士研究生,研究方向为知识发现和数据挖掘;蔡之华,副教授,主要从事知识发现与数据挖掘、并行算法、计算机图像处理方面的研究和教学工作。

下期要目󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁国防信息基础设施综述金融信息交换协议FIX从日语格语法表示生成汉语的难点分析基于XML的角色访问控制(RBAC)基于软构件的Web信息发布生成器的研究与实现基于时序数据的延迟关联规则的挖掘VPN自动发现的研究基于Java技术面向移动计算的可移动Agent的研究可生存性分析方法研究基于Internet的土地利用管理信息系统关键技术研究基于可信度构架的关联规则挖掘算法的研究面向对象软件度量技术研究基于串行分类器的字符识别基于VRML的模具PDM图形系统的研究与应用基于DEM的GIS地形分析的实现方法研究三维地形飞行浏览的研究与实现