试论增量式关联规则更新算法研究

《试论增量式关联规则更新算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文增量式关联规则更新算法研究姓名：左向科申请学位级别：硕士专业：计算机软件与理论指导教师：邢永康20090602重庆大学硕士学位论文中文摘要摘要在关联规则挖掘的实际应用中，用于挖掘的数据常发生增加、减少和修改等数据更新，并且，用户为了得到感兴趣的关联规则也常调整最小支持度和最小置信度这两个阈值。此时，传统的做法是用新的数据集和阈值按原来的挖掘算法重新再做一次计算，这样，上一次的计算结果就白白浪费了。因此，关联规则的增量更新问题成为关联规则挖掘中的一个重要问题，它关心的是当原始数据库中的数据或者最小支持度、最小置信度发生变化时，如何充分利

2、用以前的挖掘结果来高效的获得理想的关联规则。所以如果关联规则挖掘算法能充分利用前次挖掘结果来加速本次挖掘过程，而不是简单地将关联规则算法重新作用于整个事务数据库。那整个挖掘过程的效率可得到大幅度的提高，尤其对给定大型数据库中的海量数据，更可取的是增量式更新数据挖掘。应用增量式更新挖掘算法渐增地进行知识更新，修正和加强先前已经发现的知识可以说是一个诱人的目标。因此，研究增量式关联规则更新挖掘算法具有很重要的实用意义。本文就是针对增量式关联规则挖掘更新算法展开研究，其主要工作可以概括为：①综合前人的工作，根据相关的文献，综述了关联规则挖掘算法。重点研究了基本

3、类型的经典关联规则挖掘算法，分析各自的优缺点；分析算法中频繁项集的搜索策略；总结了基于经典算法的各种改进优化策略。②分析了一种增量更新算法--NewQAIS算法，举例说明了该算法的使用。并把它与Apriori算法进行了分析比较。③针对NewQAIS算法的缺点，提出了改进优化策略。在此基础上提出了一种改进算法--OFIUA(OrderedForstIncrementalUpdatingAlgorithm)。OFIUA算法引入了矩阵思想，通过一次扫描事务数据库将其转化为0．1矩阵，用向量的内积运算计算项集的支持数，大大提高了运算效率。分析NewQAIS算法中

4、项集的构成特点，指出了算法中在生成项集和查找方面的不足，OFIUA算法引入了有序森林的数据结构。有序森林里的有序树相互独立，提高了利用Apriori算法的apriori．gen函数生成候选项集的速度。该算法适用于事务数据库事务增加或支持度阈值变化而引起的关联规则的更新。关键词：关联规则，Apriori算法，频繁项集，增量，更新重庆大学硕士学位论文英文摘要ABSTRACTInthepracticalapplicationofassociationrulesmining，themineddataalwaysincreases，decreasesandrevi

5、ses．Inordertoobtaintheexpectedassociationrules，usersusuallyadjustthethresholdsofminimumsupportandminimumconfidence．，nlctraditionalmethodtodeal、析tllthiskindofproblemistocomputeitagainwiththereviseddataandthreshold，whichcarlnotmakeuseoftheformercomputation．Asanimportantproblemofass

6、ociationrulesmining，theincrementalupdatingofassociationrulesfocusesonhowtoobtaintheidealassociationrulesfrommakinguseoftheformercomputationwhentheoriginaldatabaseortherelevantthresholdchanges．TheefficiencyofminingprocesswillbegreatlyimprovedifthealgorithmofassociationrulesCanfull

7、ymakesuseoftheformercomputation,insteadofapplyingthenewalgorithmtothewholetransactiondatabase．Itisespeciallyimportantforthelarge—scaledatabasetoupdatethedatadynamicallyinsteadofminingfromtheupdateddatabaseagainandagain．Theincrementalupdatingalgorithmcanupdatedatastepbystep，whichC

8、anreviseandenhancethedatawhichhasbeenpro