頻繁模式挖掘的目標(biāo)是在數(shù)據(jù)中找出所有頻繁出現(xiàn)的模式,進(jìn)而發(fā)現(xiàn)蘊(yùn)含在數(shù)據(jù)中的潛在知識(shí),根據(jù)所挖掘數(shù)據(jù)對(duì)象的種類,可以把模式分為事務(wù)、序列、項(xiàng)集和圖等。在圖數(shù)據(jù)中挖掘頻繁的圖模式稱為頻繁圖模式挖掘,頻繁圖模式挖掘的目標(biāo)是在數(shù)據(jù)圖中找出所有出現(xiàn)次數(shù)大于給定最小支持度閾值的圖模式。頻繁圖模式挖掘具有非常重要的理論與應(yīng)用價(jià)值,眾多學(xué)者也致力于研究新的更高效的頻繁圖模式挖掘算法。圖模式匹配是頻繁圖模式挖掘算法中的重要操作,在頻繁圖模式挖掘算法中,通過圖模式匹配可以得到當(dāng)前候選圖模式在數(shù)據(jù)圖中的匹配結(jié)果,進(jìn)而判斷該圖模式是否頻繁。按照對(duì)匹配結(jié)果結(jié)構(gòu)要求是否嚴(yán)格,可以把圖模式匹配概念分為精確匹配和模擬匹配兩類。當(dāng)前許多在圖數(shù)據(jù)上進(jìn)行的頻繁圖模式挖掘工作都是基于子圖同構(gòu)來實(shí)現(xiàn)候選圖模式與數(shù)據(jù)圖的精確匹配。子圖同構(gòu)對(duì)匹配結(jié)果結(jié)構(gòu)約束太過嚴(yán)格,在某些應(yīng)用中進(jìn)行挖掘會(huì)丟失一些有意義的頻繁圖模式。模擬匹配允許候選圖模式與數(shù)據(jù)圖中的匹配結(jié)果存在一定拓?fù)浣Y(jié)構(gòu)差異,作為一種新興的匹配概念,在路網(wǎng)監(jiān)測和社交網(wǎng)絡(luò)分析等應(yīng)用中發(fā)揮著重要作用。現(xiàn)有的模擬匹配概念,例如圖模擬和雙向模擬。在頻繁圖模式挖掘領(lǐng)域,現(xiàn)有的模擬匹配概念... 

【文章來源】： 華冠齊 山東大學(xué)

【文章頁數(shù)】：75 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１－１數(shù)據(jù)圖與圖模式??

ｍａｓｔｅｒ－ｓｌａｖｅ?ｍｏｄｅｌ），在主計(jì)算節(jié)點(diǎn)上執(zhí)行??ＪｏｂＴｒａｃｋｅｒ，工作節(jié)點(diǎn)上執(zhí)行Ｔａｓｋｔｒａｃｋｅｒ。ｊｏｂＴｒａｃｋｅｒ負(fù)責(zé)分配計(jì)算任務(wù)給工作節(jié)??點(diǎn)，并與Ｔａｓｋｔｒａｃｋｅｒ進(jìn)行通信以收集計(jì)算結(jié)果，Ｔａｓｋｔｒａｃｋｅｒ負(fù)責(zé)執(zhí)行ｊｏｂＴｒａｃｋｅｒ??分配的計(jì)算任務(wù)，并將計(jì)算結(jié)果返回。??／?Ｍａｓｔｅｒ?）??Ｍａｐ任羅／?＼Ｒｅｄｕｃｅ任務(wù)??－｜?＼?ＪＭＡ／ｏｒｋｅｒｌ＾?■■?？?Ｍａｐ結(jié)果?｜?Ｉ?｜?Ｉ??子酬１?｜響咖結(jié)果??子數(shù)據(jù)圖２??Ｍａｐ結(jié)果ｊ?｜?Ｊ??子數(shù)據(jù)圖３?￣＾?｜??＾?數(shù)據(jù)?Ｒｅｄｕｃｅ結(jié)果??——￣?Ｍａｐ結(jié)果＇?ｊ?Ｉ?＾＾?Ｉ????圖２－１?ＭａｐＲｅｄｕｃｅ計(jì)算模型??ＭａｐＲｅｄｕｃｅ核心步驟可以分為兩個(gè)用戶自行編寫的函數(shù)：映射函數(shù)（Ｍａｐ）??與規(guī)約函數(shù)（Ｒｅｄｕｃｅ），二者均采用ｋｅｙ－ｖａｌｕｅ鍵值對(duì)作為數(shù)據(jù)處理單元。??１１??

山東大學(xué)碩士學(xué)位論文??ＭａｐＲｅｄｕｃｅ計(jì)算模型如圖２－１所示。在計(jì)算任務(wù)開始時(shí)，Ｍａｓｔｅｒ節(jié)點(diǎn)將映射任務(wù)??分配給各個(gè)Ｗｏｒｋｅｒ節(jié)點(diǎn)，Ｗｏｒｋｅｒ?qū)?dāng)前數(shù)據(jù)通過一定規(guī)則映射為另外的數(shù)據(jù)，??再將映射后的數(shù)據(jù)進(jìn)行排序分組（Ｓｈｕｆｆｌｅ）處理，分配給其他Ｗｏｒｋｅｒ，其他Ｗｏｒｋｅｒ??接到Ｍａｓｔｅｒ的規(guī)約任務(wù)和處理后的數(shù)據(jù)，按照規(guī)約函數(shù)對(duì)數(shù)據(jù)進(jìn)行規(guī)約，得到??最終的運(yùn)算結(jié)果，輸出結(jié)果也采用鍵值對(duì)格式。??２）?Ｐｒｅｇｅｉ大規(guī)模分布式圖計(jì)算平臺(tái)??Ｇｏｏｇｌｅ在２０１０年發(fā)布的Ｐｒｅｇｅｌ并行圖處理系統(tǒng)＾＾是一個(gè)可擴(kuò)展的，容錯(cuò)性??良好的分布式圖計(jì)算系統(tǒng)。Ｐｒｅｇｅｌ也遵循主從架構(gòu)和整體同步并行計(jì)算模型（Ｂｕｌｋ??Ｓｙｎｃｈｒｏｎｏｕｓ?Ｐａｒａｌｌｅｌ?Ｃｏｍｐｕｔｉｎｇ?Ｍｏｄｅｌ），Ｐｒｅｇｅｌ?由一個(gè)唯一的主計(jì)算節(jié)點(diǎn)和若干??工作節(jié)點(diǎn)組成，主計(jì)算節(jié)點(diǎn)本身不保存整個(gè)數(shù)據(jù)圖，也不負(fù)責(zé)復(fù)雜的圖計(jì)算任務(wù)，??而是將整張數(shù)據(jù)圖按照“切邊法”切成規(guī)模較小的子圖，分發(fā)給各個(gè)工作節(jié)點(diǎn)保??存，工作節(jié)點(diǎn)只需要維護(hù)自身保存數(shù)據(jù)圖的結(jié)構(gòu)。Ｐｒｅｇｅｌ計(jì)算模型以結(jié)點(diǎn)為中心，??以超步（Ｓｕｐｅｒｓｔｅｐ）為計(jì)算單位進(jìn)行計(jì)算，一次計(jì)算流程包括若干超步的迭代計(jì)??算。在每個(gè)超步執(zhí)行過程中，計(jì)算節(jié)點(diǎn)執(zhí)行用戶自定義的任務(wù)，同時(shí)處理上個(gè)超??步中接收到的其他節(jié)點(diǎn)發(fā)來的消息，實(shí)現(xiàn)整體同步各個(gè)節(jié)點(diǎn)并行計(jì)算，在分布式??計(jì)算領(lǐng)域得到了較為廣泛的應(yīng)用。??超步１?｜超步２?｜超步３?…?｜超步Ｎ??〇?ＫＩ）?Ｊ〇?？〇??０＼?ｘｒＯ??、、ｃ??ｃｒ?ｏ??圖２－２?Ｐｒｅｇｅｌ計(jì)算模型??圖２－２展示了?Ｐｒｅｇｅｌ以


本文編號(hào)：2969450