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

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

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

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

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