基于快速挖掘的增量更新aaiu算法的研究

《基于快速挖掘的增量更新aaiu算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要挖掘关联规则及规则的更新是数据挖掘领域的一个重要研究热点之一。目前已经提出了许多用于高效地发现大规模数据库中关联规则的算法，这些算法都有各自的特点。基于不同的关联规则发现算法有不同的规则增量更新算法。深入研究了挖掘关联规则的经典算法Apriori以及常用的几种增量关联规则的挖掘算法FUP、IUA，分析了它们的执行效率，指出了其效率低下的主要原因是由于多次迭代扫描、每次迭代产生数目更大的频繁集造成的。介绍了一种快速关联规则发现算法--QAIS算法，它通过对初始数据库的一次扫描就得到数据的项集，再对该项集一次扫描就可得出频繁项集，这样即大大减少了扫描数据库的

2、次数同时降低了二次扫描规模。指出了QAIS算法在项集生成方面存在不足：首先是该算法在生成项集及获取项集支持度方面效率较低；其次该算法虽然提出了整合项集的概念，但却没有明确提出使用什么样的方法去实现其功能。针对QAIS算法的不足，论文在项集生成方法上作出改进，提出了NewQAIS算法这一新的解决的方案：使用基于链表的整合项集数据结构，节约了内存空间，同时对交易非空子集生成方法进行改善，降低了项目子集生成的复杂度。相对基于QAIS的增量更新算法AIU，这里提出了基于NEWQAIS的增量算法AAIU，该算法屏弃了其他更新算法要逐一计算项集支持度来判断项集是不是属于

3、频繁集的做法，通过对原始、新增数据库的扫描得到两个整合项集，并将其分为频繁和非频繁两块，再进行匹配批处理，更高效率的实现了频繁集的发现。给出了AAIU算法，并将其与Apriori算法的进行测试比较，得出结论，从而进一步证明了该算法的高效性以及挖掘的充分性。关键词：增量数据挖掘；关联规则；AAIU算法；整合项集IABSTRACTMiningassociationrulesandtheirupdatesareoneofthemajoraspectofdataminingDomain.Recently,therehavemanyalgorithmsproposed

4、forefficientdiscoveryofassociationrulesinlargedatabase,whichallcomeintotheirown.Therearedifferentincrementalupdatingalgorithmsbasedondifferentminingassociationrules.Firstly,ThisthesisfurtherinvestigatestheclassicalalgorithmonminingthetheassociationrulesAprioriandafewincrementalupda

5、tionofassociationrulesFUP、IUA,analysestheirexecutionefficiency,pointsoutthemainreasonthatitsefficiencyislowisscanthedatabaserepeatlyandproducethefrequentitemslargerinfigure.Then,thisthesisintroducesaquickminingassociationrulealgorithm—QAIS,whichfindsitemsetsofdatabyscanningtheiniti

6、aldatabaseonce,andthengeneratesfrequentitemsetbyscanninglastitemsets.Itreducesthetimesandscaleofscanningdatabaselargely.However,therealsoexistssomedeficiencyintheitemsetsproducing:Foronething,QAIShasalowefficiencyinproducingitemsetandgettingsupportofitemset;Foranotherthing,although

7、itgivesanconceptofaggregateditemset,itdoesnotgiveanywaytopracticethefunctionexactly.InviewoftheinsufficiencyofQAIS,thispaperpointsoutanewsolution--NewQAIS,whichmakesimprovementinthewayofitemset’sproducing:Itsavesthespaceofmemorybyusingaggregateditemsetbasedonchainlistforitsdatastru

8、cture,meanwhilereducesthec