基于多頭絨泡菌仿生模型的圖挖掘研究.pdf

1、圖作為一種重要的數(shù)據(jù)結(jié)構(gòu)，常用于刻畫(huà)自然界或社會(huì)中事物間的復(fù)雜關(guān)系。隨著信息技術(shù)的發(fā)展，圖模型逐漸覆蓋生活各個(gè)方面，相關(guān)數(shù)據(jù)迅速增加，如社交、交通、蛋白質(zhì)之間相互作用等都可以用圖模型進(jìn)行刻畫(huà)。挖掘圖中信息可以幫助人們優(yōu)化推薦系統(tǒng)、設(shè)計(jì)高效網(wǎng)絡(luò)、預(yù)測(cè)蛋白質(zhì)功能等。如何高效的進(jìn)行圖挖掘已經(jīng)成為一個(gè)研究熱點(diǎn)。
　　隨著圖數(shù)據(jù)增加，求解圖挖掘問(wèn)題的算法近年來(lái)也得到了長(zhǎng)足發(fā)展。根據(jù)求解基本策略不同主要分為優(yōu)化算法和啟發(fā)式算法。但優(yōu)化算法面對(duì)

2、大規(guī)模問(wèn)題時(shí)仍然存在搜索效率低的問(wèn)題，啟發(fā)式算法也面臨易陷入局部最優(yōu)解等問(wèn)題。無(wú)論基于優(yōu)化的算法還是啟發(fā)式算法，如何提高算法效率，高效進(jìn)行圖挖掘問(wèn)題求解是當(dāng)前亟待解決的問(wèn)題。生物啟發(fā)一直都是推動(dòng)算法發(fā)展的重要?jiǎng)恿?。最近研究中，一種名為多頭絨泡菌的粘菌在覓食過(guò)程中展現(xiàn)出自組織、自優(yōu)化等智能特性引起廣泛關(guān)注。利用多頭絨泡菌仿生模型，本文對(duì)現(xiàn)有圖挖掘算法進(jìn)行優(yōu)化，以期提高算法效率。
　　本文著眼于圖挖掘中子圖挖掘問(wèn)題和圖聚類(lèi)問(wèn)題進(jìn)行研究

3、。首先對(duì)多頭絨泡菌仿生模型的圖挖掘能力進(jìn)行進(jìn)一步探究，擴(kuò)展其求解問(wèn)題范圍。然后利用多頭絨泡菌仿生模型的特性，對(duì)代表性的圖挖掘問(wèn)題設(shè)計(jì)了針對(duì)性的算子和算法，對(duì)當(dāng)前圖挖掘算法進(jìn)行優(yōu)化。本文的主要貢獻(xiàn)包括以下兩個(gè)方面：
　　1）針對(duì)子圖挖掘中典型的組播樹(shù)問(wèn)題，本文提出了基于多頭絨泡菌仿生模型的遺傳交叉算子，以提高遺傳算法的局部搜索能力。首先對(duì)多頭絨泡菌仿生模型進(jìn)行了修改，使得模型可以求解最短路徑樹(shù)問(wèn)題。之后針對(duì)多頭絨泡菌最短路徑樹(shù)模型計(jì)

4、算復(fù)雜度較高的問(wèn)題，優(yōu)化了模型中的迭代過(guò)程。最后基于優(yōu)化后的多頭絨泡菌最短路徑樹(shù)模型，本文提出了一種新的遺傳交叉算子（PMcrossover），并將PMcrossover嵌入到三種典型的遺傳算法中。通過(guò)和原算法在四個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比，說(shuō)明基于多頭絨泡菌的交叉算子可以有效的提高算法的搜索效率和魯棒性，驗(yàn)證了PMcrossover的有效性。
　　2）針對(duì)圖聚類(lèi)中典型的社團(tuán)挖掘問(wèn)題，本文從優(yōu)化算法中的進(jìn)化算法和啟發(fā)式算法中的馬爾可夫聚類(lèi)

5、算法兩個(gè)方面進(jìn)行求解。進(jìn)化算法以遺傳算法和蟻群算法為代表。為了探究多頭絨泡菌仿生模型在圖聚類(lèi)問(wèn)題上的潛力，本文對(duì)多頭絨泡菌網(wǎng)絡(luò)模型進(jìn)行修改，使得其可以一定程度上區(qū)分社團(tuán)間和社團(tuán)內(nèi)的邊。之后將多頭絨泡菌仿生模型對(duì)邊的識(shí)別作為先驗(yàn)知識(shí)整合到了遺傳算法的初始化過(guò)程和蟻群算法的啟發(fā)式因子中，提出了進(jìn)化算法優(yōu)化策略。對(duì)于啟發(fā)式算法，本文以馬爾可夫聚類(lèi)算法為代表。通過(guò)進(jìn)一步研究發(fā)現(xiàn)，多頭絨泡菌模型中的正反饋系統(tǒng)和馬爾可夫聚類(lèi)算法中的動(dòng)態(tài)系統(tǒng)基于類(lèi)似

6、的基本假設(shè)。根據(jù)這個(gè)特點(diǎn)，模仿多頭絨泡菌仿生模型中的正反饋關(guān)系，在馬爾可夫聚類(lèi)算法中建立了新的反饋流。同時(shí)，本文對(duì)典型馬爾可夫聚類(lèi)算法中主要算子進(jìn)行優(yōu)化，提出多頭絨泡菌啟發(fā)的馬爾可夫聚類(lèi)算法。最后在12個(gè)數(shù)據(jù)集上，從準(zhǔn)確率、魯棒性、時(shí)間復(fù)雜度等方面驗(yàn)證了提出方法的效果。
　　綜上，本文在對(duì)多頭絨泡菌仿生模型進(jìn)行研究的基礎(chǔ)上，充分挖掘其圖挖掘潛力，并對(duì)現(xiàn)有進(jìn)化算法和馬爾可夫聚類(lèi)算法進(jìn)行優(yōu)化，對(duì)典型的子圖挖掘問(wèn)題和圖聚類(lèi)問(wèn)題進(jìn)行求解。