發(fā)布時(shí)間：2020-05-17 21:09

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

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

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

【相似文獻(xiàn)】

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

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

2 魯宗貴;;吉祥多子圖頁(yè)[J];中國(guó)書(shū)畫(huà);2018年09期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8 吳云建;一致星因子圖與籠的連通性[D];南開(kāi)大學(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 黃子揚(yáng);圖在點(diǎn)度數(shù)限制下的大導(dǎo)出子圖[D];中國(guó)科學(xué)技術(shù)大學(xué);2019年

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

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

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

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

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

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

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

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

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

本文編號(hào)：2669184