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

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

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

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

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