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

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

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

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

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

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

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