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

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

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

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

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

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

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

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