并行化頻繁項集挖掘及其在數(shù)據(jù)流中的研究

《并行化頻繁項集挖掘及其在數(shù)據(jù)流中的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、蘭州大學碩士學位論文并行化頻繁項集挖掘及其在數(shù)據(jù)流中的研究姓名：何艷珊申請學位級別：碩士專業(yè)：計算機科學與技術(shù)、計算機軟件與理論指導(dǎo)教師：陳曉云20100401蘭州大學碩士學位論文并行化頻繁項集挖掘及其在數(shù)據(jù)流中的研究摘要頻繁模式挖掘是數(shù)據(jù)挖掘中的一項重要任務(wù)，通過挖掘頻繁模式，我們可以發(fā)現(xiàn)隱藏在數(shù)據(jù)中的有趣的相關(guān)和關(guān)聯(lián)。頻繁項集的挖掘作為頻繁模式挖掘中的一類，它可以廣泛應(yīng)用在關(guān)聯(lián)規(guī)則挖掘、聚類、分類和預(yù)測、入侵檢測、相關(guān)性分析等等許多種數(shù)據(jù)挖掘任務(wù)中。由于數(shù)據(jù)挖掘在開始被提出時就是面向海量數(shù)據(jù)的，龐大的搜索空間使得許多傳統(tǒng)的數(shù)據(jù)挖掘算法的效率并不理想。高性能并行環(huán)

2、境為數(shù)據(jù)挖掘的發(fā)展開辟了一條新的路徑，研究并行環(huán)境下的數(shù)據(jù)挖掘并行算法成為了數(shù)據(jù)挖掘界的熱點。頻繁項集挖掘也不例外，經(jīng)過這些年的研究，并行化的頻繁項集挖掘算法已經(jīng)取得了一些成果。本文提出了一種基于分布式并行環(huán)境的頻繁項集挖掘算法HPFP．Miner。HPFP．Miner算法是一種類FP—Growth算法，通過將數(shù)據(jù)庫壓縮到一個數(shù)據(jù)結(jié)構(gòu)上進行挖掘。算法利用兩次數(shù)據(jù)庫掃描，在各并行結(jié)點上建立HPFP-tree和HPFP．forest。各節(jié)點只需要挖掘本地HPFP-tree，最后將挖掘結(jié)果統(tǒng)一到一個共享文件中。通訊集中在建樹階段，整個挖掘過程不需要節(jié)點問的同步，大大減少了

3、通訊量，提高了算法的效率。由于數(shù)據(jù)流在日常生活中的廣泛應(yīng)用，數(shù)據(jù)流頻繁項集挖掘受到了人們的關(guān)注。數(shù)據(jù)流有著快速變化的、海量的和無限的等特點，必須建立新的數(shù)據(jù)結(jié)構(gòu)和算法對其進行挖掘。本文在上述算法的基礎(chǔ)上，提出了基于滑動窗口的并行化的數(shù)據(jù)流頻繁項集挖掘算法PFIMSD算法。算法僅通過一次掃描將當前窗口的所有數(shù)據(jù)壓縮到并行節(jié)點上的PSD．tree上，窗口滑動時用增量的方法在PSD—tree上添加和刪除相應(yīng)分支。實驗證明PFIMSD算法有著很好的時間效率和擴展性。關(guān)鍵字：頻繁模式，頻繁項集挖掘，高性能，并行化，數(shù)據(jù)流蘭州大學碩士學位論文并行化頻繁項集挖掘及其在數(shù)據(jù)流中的研

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