大规模数据库关联规则挖掘算法研究

《大规模数据库关联规则挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东师范大学硕士学位论文大规模数据库关联规则挖掘算法研究姓名：丁艳辉申请学位级别：硕士专业：计算机软件与理论指导教师：王洪国20070410山东师范大学硕士学位论文摘要数据挖掘是致力于数据分析和理解、揭示数据内部蕴藏知识的技术，它成为未来信息技术应用的重要目标之一。经过十几年的努力，数据挖掘领域产生了许多新概念和方法。特别是最近几年，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。像其它新技术的发展历程一样，数据挖掘技术也必须经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探

2、索阶段，迫切需要在基础理论、应用模式、系统构架以及挖掘算法和挖掘语言等方面进行创新。关联规则挖掘是数据挖掘领域中成果颇丰而且比较活跃的研究分支，留给研究者的是更深入的课题。随着数据库规模的日益增大，关联规则挖掘需要在挖掘效率、可用性、精确性等方面得到提升。因此，需要探索新的挖掘理论和模型；需要对一些传统的算法进行改进；也需要研究新的更有效的算法。鉴于目前数据挖掘技术和关联规则挖掘研究的现状和发展趋势，我们选择了这一课题开展相关工作。本文在分析、归类现有关联规则算法研究成果的基础上对大规模数据库关联规则挖掘算法进行了研究，所设计的新算法在挖掘效率和对大规模数据库挖掘的

3、可用性方面具有潜在的应用前景。主要研究工作体现在以下三个方面：l、针对经典Apfiod算法对大型交易事务数据库挖掘关联规则时的瓶颈问题，本文提出了一种新的基于矩阵的关联规则挖掘算法--BOM(BaseOnMawix)算法。该算法使用矩阵来表示基础数据，并且通过矩阵的直接运算直接得到频繁k-项集，避免了生成大量的候选项集，提高了对大型交易数据库的处理效率。该算法不同于经典的Apriori算法，对于大型交易事务数据库，具有较Apriori算法更加优越的性能。．2、扫描大规模数据库是非常耗时的，针对大多数关联规则并行挖掘算法需要扫描数据库至少两次，严重影响了算法的效率的问

4、题，我们提出了一种新的基于共享存储多处理机模型，更有效的并行算法一sO(ScanOnce)算法。SO算法仅扫描数据库一次，并且采用了不同于著名的并行算法CD算法的设计思想，理论分析表明SO算法具有较好的性能。3、现有的大部分关联规则挖掘算法对整个数据库的各个属性的数据样本采山东师范大学硕士学位论文用单一的支持度来找出符合的关联规则，导致无法高效地发现有价值的稀有数据。本文在无向项集图的基础上，结合RSAA算法，提出了一种新的关联规则挖掘算法，采用多支持度的方法来发现数据库中有价值的稀有数据。通过将该算法与RSAA算法的分析比较，证明了其在获得有价值的稀有数据的效率以

5、及得到规则的可用性方面具有更好的性能。关键词：数据挖掘；关联规则；大规模数据库；有价值的稀有数据；串行算法；并行算法分类号：TP311Ⅱ山东师范大学硕士学位论文ABSTRACTDataminingisatechniquethataimstoanalyzeandunderstandlargeSOUI'Cedataandrevealknowledgehiddeninthedata．Ithasbeenviewedasallimportantevolutionininformationprocessing．DuringthepastdecadeOl"over,theeonc

6、,eptsandteetmiquesOndatamininghavebeenpresented,andsomeofthemhavebeendiscussedinhigherlevelsforthelastfewyears．Liketheothernewtechniques．however,dataminingmustdevelopgradllallrfromconceptcreation,acceptedimportance．widediscussion,fewusageattemptstoalargeapplications．Mostcxl把rtsconsider

7、itasthephaseofwidediscussiontoday．ItstillDeedstlaeoretiestudiesandalgorithmexploring．Associationruleminingisanimportantbranchofdataminingthatithasobtainedmanyvaluableresultsbuttherestillarcadealofmoledaallengingproblemstodiscuss．Forlargedatabases,theresearchOnimprovingtheminingperfor