基于頻繁子模式的圖形相似性搜索研究.pdf

1、自從上世紀(jì)后期，數(shù)據(jù)挖掘就作為一種新興且有效的信息提取手段，不斷受到越來(lái)越多科學(xué)研究人員的重視和研究。圖形挖掘作為數(shù)據(jù)挖掘?qū)W科的一個(gè)新興的交叉領(lǐng)域是在2000年開(kāi)始被一些專(zhuān)家學(xué)者提出并研究。圖形挖掘本質(zhì)上就是將數(shù)據(jù)挖掘技術(shù)推廣到利用圖形對(duì)領(lǐng)域和科研信息進(jìn)行建模的科學(xué)研究中，并在此基礎(chǔ)上研究出適合各個(gè)領(lǐng)域的新的圖形挖掘技術(shù)，從而推動(dòng)科研生產(chǎn)的發(fā)展。
　　 圖形挖掘主要的應(yīng)用領(lǐng)域，即化學(xué)和生物信息科學(xué)。在這些領(lǐng)域中利用圖形對(duì)一些領(lǐng)域

2、信息如分子，蛋白質(zhì)鏈等進(jìn)行建模，然后通過(guò)在相應(yīng)的圖形數(shù)據(jù)集中挖掘出一些對(duì)各種科學(xué)研究有價(jià)值的模式信息，來(lái)為科學(xué)研究服務(wù)。頻繁子圖挖掘和圖形相似性搜索是圖形挖掘中兩個(gè)重要的研究領(lǐng)域。
　　 頻繁子圖挖掘，即從給定圖形數(shù)據(jù)集中挖掘頻繁出現(xiàn)的一些子圖或圖(也叫子結(jié)構(gòu)或模式)。而這些頻繁子圖(模式)實(shí)質(zhì)上就表示相關(guān)領(lǐng)域的一些重要的信息。
　　 圖形相似性搜索，即在給定的基于領(lǐng)域信息建模的圖形數(shù)據(jù)集中查詢滿足某種相似性條件的圖形，

3、是在2004年才由Yan等人提出。這種搜索廣泛應(yīng)用于各種科學(xué)研究中，如新藥物的研制，化合物毒性的預(yù)測(cè)等。
　　 近似圖包含搜索作為一種圖形相似性搜索最早是在2007年Chen等人的關(guān)于圖包含搜索的論文中被提出，但并沒(méi)有研究。這之前的研究只局限與精確搜索和傳統(tǒng)子結(jié)構(gòu)相似性搜索。傳統(tǒng)子結(jié)構(gòu)相似性搜索，即查詢給定數(shù)據(jù)集中包含或近似包含給定查詢圖的模型圖。近似圖包含則是搜索被查詢圖包含或近似包含的模型圖。由于包含關(guān)系截然相反，因此以前的

4、針對(duì)傳統(tǒng)子結(jié)構(gòu)相似性搜索的索引構(gòu)造策略對(duì)近似圖包含搜索不再適用，并且，在此之前，還沒(méi)有針對(duì)近似圖包含搜索的索引構(gòu)造算法提出。
　　 本文在對(duì)一些典型的關(guān)于頻繁子圖挖掘和圖形相似性搜索的索引構(gòu)造算法進(jìn)行充分研究的基礎(chǔ)上，提出了一種基于覆蓋率和支持度的針對(duì)近似圖包搜索的索引構(gòu)造算法csIndex(coverage and support based Index)，csIndex的主要思想是首先對(duì)從給定模型圖集合中挖掘出的頻繁子結(jié)構(gòu)的