面向不確定圖數(shù)據(jù)的子圖模式挖掘算法的研究與實(shí)現(xiàn).pdf

1、圖作為一種重要的數(shù)據(jù)結(jié)構(gòu)，已經(jīng)在多個(gè)領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用。例如研究人員在對(duì)化合物、社交網(wǎng)絡(luò)等數(shù)據(jù)進(jìn)行分析時(shí)，均采用圖這種結(jié)構(gòu)來(lái)進(jìn)行建模，得到的是確定圖數(shù)據(jù)。然而，在現(xiàn)實(shí)生活中，由于采集、傳輸?shù)燃夹g(shù)的條件限制，數(shù)據(jù)通常是含有噪音的、不完全的和不精確的。因此，將其建模為不確定圖數(shù)據(jù)更為合適。
　　隨著不確定圖數(shù)據(jù)量的急劇增加，研究如何高效地從其中蘊(yùn)含的豐富結(jié)構(gòu)及語(yǔ)義信息中挖掘出有用的知識(shí)，是數(shù)據(jù)庫(kù)及數(shù)據(jù)挖掘研究領(lǐng)域的熱點(diǎn)之一，有

2、著重要的理論研究和應(yīng)用價(jià)值。由于不確定性的引入，傳統(tǒng)的圖數(shù)據(jù)挖掘算法不能直接用于不確定圖數(shù)據(jù)。基于此，本文圍繞不確定圖數(shù)據(jù)中的子圖模式挖掘問(wèn)題展開(kāi)了研究，具體工作如下：
　　首先，學(xué)習(xí)不確定圖數(shù)據(jù)挖掘領(lǐng)域的相關(guān)知識(shí)，掌握已有挖掘算法的核心思想，并分析每種算法的適用場(chǎng)景及優(yōu)劣。
　　其次，針對(duì)不確定圖數(shù)據(jù)中的頻繁子圖模式挖掘問(wèn)題，提出了遵循“候選產(chǎn)生——候選判定”框架的算法FSMWT(Frequent Subgraph Pat

3、tern Mining With less Test)。算法采用著名的DFS編碼枚舉框架并對(duì)其進(jìn)行了改進(jìn)，為枚舉框架中的每個(gè)節(jié)點(diǎn)創(chuàng)建了相應(yīng)的GEindex數(shù)據(jù)結(jié)構(gòu)。在候選產(chǎn)生階段，通過(guò)GEindex實(shí)現(xiàn)了只在包含該子圖的圖中進(jìn)行子圖擴(kuò)展而不必掃描整個(gè)數(shù)據(jù)庫(kù)。在候選判定階段，利用GEindex實(shí)現(xiàn)了期望支持度的直接計(jì)算而無(wú)需進(jìn)行子圖同構(gòu)操作。此外，文中還提出了確定性剪枝和概率性剪枝技術(shù)，從而進(jìn)一步提高了算法的效率。實(shí)驗(yàn)表明，F(xiàn)SMWT比其

4、他算法具有更高的效率。
　　最后，針對(duì)從不確定圖數(shù)據(jù)中挖掘k-truss緊密子圖模式的問(wèn)題提出了MTKUG(Mining Top-K k-truss from Uncertain Graph Data)算法。文中形式化定義了從不確定圖數(shù)據(jù)中挖掘k值最大的前K個(gè)k-truss緊密子圖的問(wèn)題，并給出了期望支持度的概念。算法中提出了期望支持度的計(jì)算方法，并利用并行計(jì)算系統(tǒng)提高了計(jì)算效率。另外，文中還提出了剪枝策略以進(jìn)一步提高算法效率。通