【摘要】：圖數(shù)據(jù)是大數(shù)據(jù)時代中十分重要的角色,其在各種場景中有著十分廣泛的應(yīng)用,如社交網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)、合作關(guān)系網(wǎng)絡(luò)等。本文主要研究的是圖數(shù)據(jù)上的模式挖掘,研究目的是實現(xiàn)從圖數(shù)據(jù)中挖掘頻繁近似子圖。目前在頻繁子圖挖掘領(lǐng)域的工作已經(jīng)有很多,然而已有的工作要么沒有考慮子圖與其出現(xiàn)的相似程度,要么在考慮相似程度時忽略了候選子圖大小對相似程度的影響。然而,根據(jù)人的感知,不同大小的圖應(yīng)具有不同程度的容錯性,類似的,子圖的大小對計算子圖與其出現(xiàn)的相似程度也會有十分重要的影響。因此,本文設(shè)計了子圖大小相關(guān)的頻繁近似子圖挖掘策略,提出了一種新的、快速的頻繁近似子圖挖掘算法。算法不僅在計算子圖的頻繁程度時考慮與子圖的近似出現(xiàn),同時在計算子圖與其出現(xiàn)的相似程度時,考慮子圖的大小對近似程度的影響。首先,對于候選頻繁近似子圖的生成,本文設(shè)計了一種不遺漏的遍歷方式,遍歷給定單圖的全部子圖。為了提高遍歷的效率,降低候選頻繁近似子圖的數(shù)量,對頻繁近似子圖的大小上限進行了估算,并利用大小上限過濾遍歷中的子圖,對遍歷過程進行剪枝。實驗證明了子圖的上限對遍歷效率具有提升效果。其次,為提高算法效率,本文歸納出對于所有的頻繁近似子圖,其支持度符合“局部反單調(diào)性”,且在文中給出了證明。并利用該性質(zhì),設(shè)計了對候選頻繁近似子圖進行剪枝的策略,降低了需要進行近似匹配的候選子圖的數(shù)量。實驗證明,該性質(zhì)對可以顯著提升算法效率。再次,對于候選頻繁近似子圖的近似子圖生成,本文設(shè)計了基于點和邊的刪除策略的近似子圖生成算法。并通過理論證明,僅通過統(tǒng)計該算法產(chǎn)生的近似子圖在給定圖中的匹配,并計算這些匹配的支持度,可以得到與統(tǒng)計候選頻繁近似子圖的所有近似匹配相同的支持度。接著,通過與已有算法的實驗對比,證明本文算法在效率上具有明顯優(yōu)勢,同時,通過簡單案例說明,本文算法能發(fā)現(xiàn)傳統(tǒng)頻繁子圖挖掘算法無法發(fā)現(xiàn)的頻繁子圖,進一步表明在挖掘頻繁子圖時考慮近似關(guān)系,與子圖大小對近似程度的影響的必要性。最后,修改本文算法,提出了針對頻繁閉合近似子圖和頻繁極大近似子圖的挖掘算法,提高了本文研究的完整性,擴展了算法應(yīng)用場景,并通過實驗證明了兩種算法的有效性。
【圖文】：

華東師范大學(xué)碩士學(xué)位論文殊性，用于表達實體間的關(guān)系十分方便，因此實體間的關(guān)系的表達通常用圖結(jié)構(gòu)表示。如圖 1-1 所示的 PPI(Protein-ProteinInteraction)[8]，其中每個點表示一種蛋白質(zhì)，每條邊表示蛋白質(zhì)之間的交互關(guān)系，從中挖掘頻繁的蛋白質(zhì)交互關(guān)系網(wǎng)絡(luò)就是頻繁子圖挖掘的一種。圖數(shù)據(jù)又分為不同的種類，如不確定圖，標(biāo)簽圖等，本文的主要研究對象為點和邊都具有標(biāo)簽的標(biāo)簽圖，其中點和邊上的標(biāo)簽表示的

為證明本文候選子圖剪枝策略的有效性，本文設(shè)計實驗，對 DP、DP-L 以-LT 三種生成算法進行對比。實驗設(shè)置頻繁程度閾值 7，近似程度閾值，結(jié)果如下：由于算法效率差距過大，，因此我們將效率對比展示在兩個圖中，圖中橫坐示給定圖數(shù)據(jù)中點的數(shù)量，縱坐標(biāo)表示算法消耗的時間，兩個圖中橫坐標(biāo)的為 250 的點表示的是算法在真實數(shù)據(jù)中的效率，圖 6-1 展示了 DP-L 算法-LT 算法的效率對比，可以看出，隨著圖規(guī)模的增大，兩種算法的效率都在，消耗的時間上升，同時，DP-L 算法與 DP-LT 算法消耗的時間差距也逐漸，表示隨著圖規(guī)模的增大，DP-L 算法時間成本上升更快。這是因為隨著圖的增大，子圖數(shù)量呈指數(shù)上升，由于 DP-LT 算法采用了基于頻繁近似子圖上限的早停機制，降低了產(chǎn)生的候選子圖的數(shù)量，同時，隨著自圖數(shù)量的上升圖 6-1 DP-L 與 DP-LT 算法效果對比
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：O157.5;TP311.13

【相似文獻】

相關(guān)期刊論文 前10條

1 苑春佼;;《吉祥多子圖》臨摹[J];大眾文藝;2018年10期

2 魯宗貴;;吉祥多子圖頁[J];中國書畫;2018年09期

3 印安濤;錢鋼;施歡歡;;在復(fù)雜網(wǎng)絡(luò)中查找k個有限重疊的密集子圖[J];計算機應(yīng)用與軟件;2016年12期

4 魯宗貴;;吉祥多子圖[J];文藝研究;2017年03期

5 梁瑤;;吉祥多子圖[J];美與時代(中);2017年06期

6 魯宗貴;;《吉祥多子圖》[J];老年教育(書畫藝術(shù));2016年01期

7 王苗苗;;《吉祥多子圖》[J];明日風(fēng)尚;2016年08期

8 周姍;;《吉祥多子圖》[J];參花(上);2016年06期

9 楊利民;圖K_n~k和C_n~t的理想子圖的計數(shù)[J];大理師專學(xué)報(自然科學(xué)版);1995年01期

10 陳賜平;;帶虧數(shù)的[1,n]-子圖[J];北京農(nóng)業(yè)工程大學(xué)學(xué)報;1987年03期

相關(guān)會議論文 前9條

1 劉桂珍;徐周波;;最大公共子圖問題的約束符號求解技術(shù)[A];廣西計算機學(xué)會2016年學(xué)術(shù)年會論文集[C];2016年

2 徐以凡;;層分解和子圖識別問題[A];2001年全國數(shù)學(xué)規(guī)劃及運籌研討會論文集[C];2001年

3 吳衛(wèi)江;李國和;;Apriori算法思想在頻繁子圖挖掘中應(yīng)用的研究[A];第六屆全國信息獲取與處理學(xué)術(shù)會議論文集（2）[C];2008年

4 陶劍文;丁佩芬;趙杰煜;;csgIndex:一種可擴展的對比子圖索引模型[A];第二十七屆中國控制會議論文集[C];2008年

5 陳榮斯;;非正則冠狀系統(tǒng)[A];面向21世紀(jì)的科技進步與社會經(jīng)濟發(fā)展（上冊）[C];1999年

6 吳穎華;周皓峰;袁晴晴;洪銘勝;汪衛(wèi);施伯樂;;Topology:一個快速的頻繁連通子圖的挖掘算法[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2003年

7 韓璐;王朝坤;阮文靜;歐曉平;仇萍;;基于MapReduce的不確定子圖查詢處理[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

8 周楊;王峰;;FSM——基于子圖同構(gòu)和結(jié)構(gòu)同構(gòu)的頻繁子圖挖掘算法[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2007年

9 張麗麗;殷兆麟;張愛娟;王竹曉;;以結(jié)點為中心的WordNet子圖的可視化[A];2006年全國開放式分布與并行計算學(xué)術(shù)會議論文集（二）[C];2006年

相關(guān)重要報紙文章 前1條

1 王圣立;“五子圖”罐再現(xiàn)成化風(fēng)彩[N];中國商報;2003年

相關(guān)博士學(xué)位論文 前10條

1 買吐肉孜·買司地克（Metrose Metsidik）;帶子圖及其部分對偶若干性質(zhì)的刻畫[D];廈門大學(xué);2017年

2 藺厚元;禁用子圖與圖的哈密爾頓性[D];華中師范大學(xué);2012年

3 李斌龍;重子圖條件下圖的Hamilton性及相關(guān)問題[D];西北工業(yè)大學(xué);2016年

4 毛玲;基于層次因子圖的心電圖自動診斷方法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

5 崔慶;Tutte子圖方法及其應(yīng)用[D];南開大學(xué);2009年

6 鄒磊;圖數(shù)據(jù)庫中的子圖查詢算法研究[D];華中科技大學(xué);2009年

7 崔耀祖;基于復(fù)雜網(wǎng)絡(luò)邊的密度探索社團結(jié)構(gòu)算法研究[D];大連理工大學(xué);2016年

8 吳云建;一致星因子圖與籠的連通性[D];南開大學(xué);2009年

9 馬登舉;曲面的極小禁用子圖與圖的虧格[D];華東師范大學(xué);2011年

10 石海佳;基于復(fù)雜網(wǎng)絡(luò)的產(chǎn)業(yè)生態(tài)系統(tǒng)結(jié)構(gòu)復(fù)雜性研究[D];清華大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 黃子揚;圖在點度數(shù)限制下的大導(dǎo)出子圖[D];中國科學(xué)技術(shù)大學(xué);2019年

2 竇建凱;單圖中子圖大小相關(guān)的近似頻繁子圖挖掘[D];華東師范大學(xué);2019年

3 黃睿智;不確定圖下的稠密子圖挖掘研究[D];浙江工業(yè)大學(xué);2018年

4 閆靚;穩(wěn)定頻繁子圖挖掘算法研究[D];遼寧大學(xué);2018年

5 劉鐘凌;頂點加權(quán)圖的最密集子圖算法設(shè)計與實現(xiàn)[D];廣州大學(xué);2018年

6 鄒艷梅;關(guān)于圖的Hamilton性的禁用子圖條件[D];華東師范大學(xué);2018年

7 姜麗雁;大規(guī)模動態(tài)有向標(biāo)簽圖子圖查詢方法研究[D];遼寧大學(xué);2018年

8 陳科第;基于頻繁子圖模式挖掘的群體性抗議事件檢測技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2016年

9 李新鋒;知識圖譜中子圖查詢技術(shù)研究[D];華中科技大學(xué);2017年

10 張迎;面向大圖數(shù)據(jù)的子圖相似匹配算法研究與實現(xiàn)[D];東北大學(xué);2015年

本文編號：2669184