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

【文章來源】： 華冠齊 山東大學

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

【學位級別】：碩士

【部分圖文】：

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

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

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


本文編號：2969450