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

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

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

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

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

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

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