频繁项目集挖掘算法研究

《频繁项目集挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、辽宁师范大学硕士学位论文频繁项目集挖掘算法研究姓名：张亮申请学位级别：硕士专业：课程与教学论指导教师：任永功20090501摘要数据挖掘是从数据中析取、识别和发现潜在正确和有用、前所未知的、最终可理解的知识的过程。它是当今人工智能和数据库研究方面最富活力的领域之一。关联规则挖掘则是数据挖掘的一个重要研究内容，而频繁项目集挖掘又是关联规则挖掘的核心问题。在实际问题中，频繁项目集存在着较多的冗余信息，因此诸多学者采用各种方法试图减少频繁模式中的冗余。目前，主要采用的有频繁闭项目集(FCI)和最大频繁项目集(呱I)

2、两种，它们包含所有频繁项目集的信息，但数量要比频繁项目集的数量小几个数量级。本文首先对频繁闭项目集和最大频繁项目集挖掘中一些经典的算法进行了系统的分析和总结，然后在此基础上提出了新的解决相应问题的挖掘算法：首先，提出了频繁闭项目集挖掘算法Max-FCIA，该算法利用哈希表映射事务数据库，通过对哈希表进行操作从而得到所有频繁项目集的支持度，进而生成包含所有频繁项目的有序树。经过剪枝处理的有序树就是包含所有最小频繁闭项目集的FC—tree，最后用最小频繁闭项目集生成频繁闭项目集。实验结果表明，该算法通过映射事务数

3、据库，减少了扫描数据库所浪费的时间，提高程序执行效率。另外，运用有效的剪枝策略，避免了不必要候选项目集的生成，节省了存储空间，实验证明该算法是有效的。其次，提出了最大频繁项目集挖掘算法FP-MFIA，该算法利用频繁模式树对最大频繁项目集进行检索，通过位图建树的方法有效的减少了扫描数据库的次数。除此以外，此算法运用独特的最大频繁项目集搜索策略，同时运用投影技术进行超集检测，提高了遍历的效率，实验证明FP-MFIA算法是比较有效的最大频繁项目集搜索算法。另外，本文给出了频繁闭项目集和最大频繁项目集挖掘算法的一些新

4、的、有效的改进措施：第一，提出了FC—tree的概念，将所有频繁项目都存储在FC-tree中，明显减少了事务数据库的扫描次数。而且，FC-tree是一棵有序树，在项目集的搜索方面，根据项目集的有序性，采用了二分法查找的方法，可以大大节省系统在项目集搜索方面的时间。第二，提出了一种判断最大频繁项目集的新方法，大大地提高了频繁项目集发现算法的时间效率。关键字频繁项目集，频繁闭项目集，最小频繁闭项目集，最大频繁项目集，频繁模式树lAbstractDataminingistheprocessofextracting，

5、identifyinganddiscoveringpotentiallyvalid，useful，preyiOUSlYunknown，andultimatelYunderstandableknowledge．DataMiningisoneofthemostactireresearehfieIds，especialinthefieldsofartificialintelleginceanddatabasereaseareh．TheasSOCiationruleminingisamainresearchaspec

6、tofdatamining．AndthediscoveryofthefrequentitemsetsisflkeyproblemoftheasSOCiationrulemining．Inpracticalproblems，frequentitemsetshavemoreredundantinformation，somanyresearcherstriedtousevariOUSmethodstoconstric,ttheredundantfrequentpattern．Atpresent，frequentcl

7、oseditemsets(FCI)andmaximalfrequentitemsets(MFI)ismainlYused．Theycontaina11thefrequentitemsets，butthenumberissmallerthanthenumberoffrequentitemsets．Inthethesis，weanalyseandsummarizesomeusefulalgorithmspresentedaboutfrequentcloseditemsetsandmaximalfrequentit

8、emsetsatfirst，andthenwepresentedtwonewalgorithmsforsolvingsomerelativeproblemsindataminingasfollows：Firstly，wepresentanalgorithm，Max—FCIA，forminingfrequentcloseditemsets．Thisalgorithmmapsthetransaction