頻繁子結(jié)構(gòu)挖掘算法研究與應(yīng)用.pdf

1、在新興的化學(xué)信息學(xué)、生物信息學(xué)，網(wǎng)絡(luò)分析、XML 數(shù)據(jù)等領(lǐng)域，需要用樹(shù)或圖這樣的結(jié)構(gòu)化數(shù)據(jù)類型來(lái)表示數(shù)據(jù)。在這些結(jié)構(gòu)化數(shù)據(jù)類型中進(jìn)行數(shù)據(jù)挖掘，將有助于我們獲取新的信息和知識(shí)。在結(jié)構(gòu)化類型的數(shù)據(jù)集合中，頻繁項(xiàng)的挖掘是一種最基本的數(shù)據(jù)挖掘方式，如何高效地挖掘頻繁子結(jié)構(gòu)模式，是一個(gè)挑戰(zhàn)性的問(wèn)題。
　　 已有的高效頻繁子結(jié)構(gòu)挖掘算法的核心思想可以大致分為基于Apriori 原則的連接方法和基于模式增長(zhǎng)的擴(kuò)展方法，但前者難以直接生成規(guī)范化

2、的候選模式，后者又容易產(chǎn)生候選模式的數(shù)目過(guò)大。通過(guò)分析這兩類方法的特點(diǎn)，提出了混合型PJE 方法，該方法是研究頻繁有根無(wú)序樹(shù)挖掘、頻繁自由樹(shù)挖掘和頻繁子圖挖掘的基礎(chǔ)。
　　 在頻繁有根無(wú)序樹(shù)的挖掘中，采用最小深度序列作為規(guī)范化標(biāo)記形式，并且基于前綴結(jié)點(diǎn)進(jìn)行擴(kuò)展，在常數(shù)時(shí)間內(nèi)得到新的規(guī)范化形式的候選模式樹(shù)。采用深度擴(kuò)展和廣度連接的混合方式列舉候選模式樹(shù)，利用Apriori 原則減少候選模式樹(shù)的數(shù)目。
　　 對(duì)列舉生成的候選

3、模式樹(shù)，利用Apriori 原則進(jìn)行剪枝，進(jìn)一步減少需要進(jìn)行頻度統(tǒng)計(jì)的候選模式樹(shù)數(shù)目。用規(guī)范化的嵌入出現(xiàn)列表表示模式樹(shù)在數(shù)據(jù)庫(kù)中的出現(xiàn)，在此基礎(chǔ)上進(jìn)行出現(xiàn)頻度統(tǒng)計(jì)，不僅避免完整的子圖同構(gòu)判斷問(wèn)題，而且比使用完整出現(xiàn)列表節(jié)約了大量空間。綜合以上技術(shù)，給出了頻繁有根無(wú)序樹(shù)挖掘算法Root-PJE，并且在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行性能測(cè)試，驗(yàn)證了性能比現(xiàn)有算法有較大提高。
　　 在頻繁自由樹(shù)的挖掘中，定義自由樹(shù)的中心結(jié)點(diǎn)或雙中心結(jié)點(diǎn)

4、，將自由樹(shù)轉(zhuǎn)換為以中心結(jié)點(diǎn)為根的有根無(wú)序樹(shù)。基于自由樹(shù)的脊柱路徑和最小脊柱串，定義自由樹(shù)的脊柱串優(yōu)先最小深度序列，在此基礎(chǔ)上運(yùn)用前綴結(jié)點(diǎn)進(jìn)行深度擴(kuò)展和廣度連接，在常數(shù)時(shí)間內(nèi)得到新的候選模式自由樹(shù)。對(duì)候選模式自由樹(shù)采用Apriori 原理進(jìn)行剪枝，并采用規(guī)范化嵌入出現(xiàn)列表進(jìn)行頻度統(tǒng)計(jì)。綜合以上方法，給出頻繁自由樹(shù)挖掘算法Free-PJE，并且在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行性能測(cè)試，驗(yàn)證了性能比現(xiàn)有算法有較大提高。
　　 在頻繁子圖

5、的挖掘中，將圖分解為不包含葉結(jié)點(diǎn)的圖核部分和不包含環(huán)的分支森林部分，定義分支森林在圖核上的連接向量。由此定義最小“圖核-分支-連接向量”
　　 三元組作為圖的規(guī)范化標(biāo)記形式。以擴(kuò)展方法得到頻繁模式圖核，對(duì)一個(gè)圖核由列舉得到所有最小連接向量，由此將圖看做是虛擬有根無(wú)序樹(shù)，在此虛擬樹(shù)上進(jìn)行基于前綴結(jié)點(diǎn)的深度擴(kuò)展和廣度連接，從而在常數(shù)時(shí)間內(nèi)得到新的候選模式圖。采用基于Apriori 原理的剪枝和基于規(guī)范化嵌入出現(xiàn)列表的出現(xiàn)頻度統(tǒng)計(jì)?；?/p>

6、于以上方法，給出頻繁子圖挖掘算法Graph-PJE。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了性能測(cè)試，驗(yàn)證了性能比現(xiàn)有算法有較大提高。
　　 為了提高圖查詢的效率，需要在圖數(shù)據(jù)庫(kù)中建立圖索引。利用圖數(shù)據(jù)庫(kù)中的特征子圖和其事務(wù)出現(xiàn)列表建立圖索引。查詢時(shí)，首先利用圖索引得到查詢圖的候選查詢結(jié)果集，然后驗(yàn)證每個(gè)候選結(jié)果圖是否完整包含查詢圖。使用頻繁子圖挖掘結(jié)果作為圖索引，可以保證候選查詢結(jié)果集不大于頻繁挖掘中的最小支持度。使用共享前綴樹(shù)保存索

7、引特征子圖，只需保存有效事務(wù)出現(xiàn)列表，可以減小圖索引的大小。在真實(shí)的分子結(jié)構(gòu)圖數(shù)據(jù)庫(kù)中，將6 邊環(huán)和5邊環(huán)看做虛擬原子，對(duì)分子結(jié)構(gòu)圖進(jìn)行重構(gòu)后建立圖索引，可以大幅減小圖索引的大小。利用真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試，驗(yàn)證了頻繁子圖索引的高效。
　　 利用新提出的頻繁子結(jié)構(gòu)索引和查詢方法，以達(dá)夢(mèng)關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)為平臺(tái)，設(shè)計(jì)并實(shí)現(xiàn)了化學(xué)數(shù)據(jù)庫(kù)系統(tǒng)的原型。在該數(shù)據(jù)庫(kù)中，利用關(guān)系表存儲(chǔ)化學(xué)結(jié)構(gòu)數(shù)據(jù)和化學(xué)結(jié)構(gòu)索引，利用外部存儲(chǔ)過(guò)程，實(shí)現(xiàn)了化學(xué)結(jié)構(gòu)數(shù)