并行化频繁项集挖掘及其在数据流中的研究

《并行化频繁项集挖掘及其在数据流中的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州大学硕士学位论文并行化频繁项集挖掘及其在数据流中的研究姓名：何艳珊申请学位级别：硕士专业：计算机科学与技术、计算机软件与理论指导教师：陈晓云20100401兰州大学硕士学位论文并行化频繁项集挖掘及其在数据流中的研究摘要频繁模式挖掘是数据挖掘中的一项重要任务，通过挖掘频繁模式，我们可以发现隐藏在数据中的有趣的相关和关联。频繁项集的挖掘作为频繁模式挖掘中的一类，它可以广泛应用在关联规则挖掘、聚类、分类和预测、入侵检测、相关性分析等等许多种数据挖掘任务中。由于数据挖掘在开始被提出时就是面向海量数据的，庞大的搜索空间使得许多传统的数据挖掘算法的效率并不理想。高性能并行环

2、境为数据挖掘的发展开辟了一条新的路径，研究并行环境下的数据挖掘并行算法成为了数据挖掘界的热点。频繁项集挖掘也不例外，经过这些年的研究，并行化的频繁项集挖掘算法已经取得了一些成果。本文提出了一种基于分布式并行环境的频繁项集挖掘算法HPFP．Miner。HPFP．Miner算法是一种类FP—Growth算法，通过将数据库压缩到一个数据结构上进行挖掘。算法利用两次数据库扫描，在各并行结点上建立HPFP-tree和HPFP．forest。各节点只需要挖掘本地HPFP-tree，最后将挖掘结果统一到一个共享文件中。通讯集中在建树阶段，整个挖掘过程不需要节点问的同步，大大减少了

3、通讯量，提高了算法的效率。由于数据流在日常生活中的广泛应用，数据流频繁项集挖掘受到了人们的关注。数据流有着快速变化的、海量的和无限的等特点，必须建立新的数据结构和算法对其进行挖掘。本文在上述算法的基础上，提出了基于滑动窗口的并行化的数据流频繁项集挖掘算法PFIMSD算法。算法仅通过一次扫描将当前窗口的所有数据压缩到并行节点上的PSD．tree上，窗口滑动时用增量的方法在PSD—tree上添加和删除相应分支。实验证明PFIMSD算法有着很好的时间效率和扩展性。关键字：频繁模式，频繁项集挖掘，高性能，并行化，数据流兰州大学硕士学位论文并行化频繁项集挖掘及其在数据流中的研

4、究ABSTRACTFrequentpatternminingisoneofsignificanttasksindatamining．Throughminingfrequentpattern，wecanfindoutinterestedcorrelationsandassociationshidingindata．Asakindoffrequentpatternmining，miningfrequentitemsetcanbeusedinmanyotherdataminingtasks，suchasassociationrulesmining，clusteranaly

5、sis，classificationandprediction，intrusiondetection，relevanceanalysis，etc．Duetodataminingispresentedforthevastamountofdataattheverybeginning，theperformanceofmanydataminingalgorithmsareunfavorablefortheenormoussearchingspace．Highperformanceparalleledenvironmentopensupanewroadfordataminin

6、g，thedataminingresearchbasedonparallelenvironmentbecomesthehotpointindataminingfield．Frequentitemsetminingisnoexception，throughcoupleyearsstudy,manyparalleledfrequentitemsetminingalgorithmshavealreadyemerged．Inthispaper，HPFP—Miner,afrequentitemsetminingalgorithmbasedondistributedparall

7、elenvironmentispresented．HPFP—MinerisakindofFP．．Growth-·likealgorithmwhichcompressesdatabaseintoadatastructureandminethisdatastructure．TheproposedalgorithmbuildsHPFP-treeandHPFP-forestonparalleledprocessorsbytwicescanondatabase．EachprocessoronlyneedstomineitslocalHPFP—tree，andoutputt