基于演化算法的連通子圖挖掘方法研究.pdf

1、隨著數(shù)據(jù)挖掘研究的深入，越來越多的問題呈現(xiàn)在我們面前，也提出了更高的要求。當前，復雜類型數(shù)據(jù)的挖掘需求上升，專家學者開始關注這方面的新應用和理論研究，并試圖利用結構化數(shù)據(jù)挖掘方面的經(jīng)驗和方法論來幫助解決新問題。而連通子圖挖掘問題就是本文所致力研究的問題。 本文主要研究了N連通子圖挖掘問題和多信息連通子圖挖掘問題。N連通子圖發(fā)現(xiàn)問題是在一個很大的圖中尋找一個較小的子圖來表現(xiàn)幾個給定節(jié)點在圖中的關系的問題。多信息連通子圖挖掘問題是在

2、一個邊有多種類型的圖中尋找連通幾個特定結點的，能夠滿足問題約束的連通子圖的問題。本文的主要工作和特色如下： 1．本文提出了一個新的解決N-連通子圖挖掘問題的方法。首先分析了問題并定義了一個評價函數(shù)來評價一個子圖表現(xiàn)N個給定節(jié)點之間關系的好壞。同時設計了一個特殊的UTM編碼來表示一個確定結點數(shù)的圖的拓撲結構。使用UTM編碼能夠避免在進化過程中多余的編碼步驟，能夠減小算法的時間和空間消耗。在UTM編碼和評價函數(shù)的基礎上，設計了一個演

3、化算法來對圖的拓撲結構進行優(yōu)化。實驗結果顯示該算法能夠有效地在不同類型的網(wǎng)絡上發(fā)現(xiàn)連通子圖。 2．在N連通子圖挖掘問題之后，本文針對多信息連通子圖發(fā)現(xiàn)問題的特點，提出了一個通用的進化算法。設計了一種表示多信息子圖拓撲結構的特殊編碼——多信息子圖編碼MSC。使用MSC編碼能夠很好的表示多信息連通子圖，這個編碼能夠在進化過程中能夠減少時間和空間的消耗。同時在真實數(shù)據(jù)上的實驗結果顯示該算法是有效的。 3．在前面兩個算法的基礎上