半結(jié)構(gòu)化數(shù)據(jù)頻繁模式挖掘相關(guān)技術(shù)研究.pdf

1、數(shù)據(jù)挖掘技術(shù)在進(jìn)步的同時(shí)，也遇到了許多挑戰(zhàn)，面對非傳統(tǒng)的數(shù)據(jù)，如含有半結(jié)構(gòu)化、非結(jié)構(gòu)化文本和超鏈接的Web頁面集、XML文檔、具有序列和三維結(jié)構(gòu)的DNA數(shù)據(jù)、時(shí)間序列測量值的氣象數(shù)據(jù)等，其結(jié)構(gòu)以及數(shù)據(jù)之間包含的許多復(fù)雜聯(lián)系，而這也正是我們挖掘模式、發(fā)現(xiàn)知識的關(guān)鍵所在，舍此別無選擇。為了挖掘這些半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)，算法就需要考慮數(shù)據(jù)間的聯(lián)系，如時(shí)間和空間的自相關(guān)性、圖的連通性、半結(jié)構(gòu)化、非結(jié)構(gòu)化文本中元素之間的聯(lián)系。樹、圖和格作為常用

2、的半結(jié)構(gòu)化數(shù)據(jù)表達(dá)方式，通過節(jié)點(diǎn)和邊表達(dá)實(shí)體、屬性，以及實(shí)體之間的聯(lián)系，因此可借助它們來描述研究對象的關(guān)系，便于半結(jié)構(gòu)化數(shù)據(jù)的處理。
　　 本文對半結(jié)構(gòu)化數(shù)據(jù)頻繁模式挖掘的若干技術(shù)進(jìn)行了研究。重點(diǎn)研究了以下幾個(gè)問題：首先源于以樹結(jié)構(gòu)描述XML文檔的簡潔性，研究樹結(jié)構(gòu)數(shù)據(jù)頻繁模式和基于約束的樹結(jié)構(gòu)數(shù)據(jù)頻繁模式的挖掘方法；然后針對具有復(fù)雜鏈接關(guān)系的XML文檔結(jié)構(gòu)數(shù)據(jù)標(biāo)記的缺失問題，研究部分標(biāo)記圖結(jié)構(gòu)數(shù)據(jù)的頻繁模式挖掘方法，以及基于支

3、持度弱化約束的圖結(jié)構(gòu)數(shù)據(jù)頻繁模式挖掘方法。本文研究內(nèi)容和創(chuàng)新工作主要包括以下五個(gè)方面：
　　 ①基于子樹編碼聚類的頻繁誘導(dǎo)子樹挖掘算法。
　　 提出頻繁誘導(dǎo)子樹挖掘算法XML Miner，將模式增長方法應(yīng)用于頻繁子樹模式挖掘算法中。采用了一種新的基于子樹編碼聚類的最小一般概化，對樹進(jìn)行關(guān)系編碼，計(jì)算其最小一般概化，找出最大公共子樹。算法直接構(gòu)造頻繁子樹，無須多次掃描樹集，利用編碼把對子樹挖掘轉(zhuǎn)移到對聚類集合的挖掘；由于避

4、免了樹匹配操作，降低了算法時(shí)間復(fù)雜度。
　　 ②基于項(xiàng)集表達(dá)的頻繁嵌入子樹挖掘算法。
　　 提出頻繁嵌入子樹挖掘算法EXML Miner。算法基于頻繁子樹編碼序列增長的方法，先將初始樹集作為項(xiàng)集，通過路徑交運(yùn)算，生成帶子樹特征的頻繁項(xiàng)，并在頻繁項(xiàng)上挖掘帶有頻繁特征的子樹，然后將頻繁子樹結(jié)構(gòu)進(jìn)行壓縮，還原成真實(shí)子樹形式并計(jì)算其支持度。算法基于最右路徑擴(kuò)展技術(shù)在有序樹中發(fā)現(xiàn)所有頻繁模式，只在樹的最右分支上增加新節(jié)點(diǎn)生成新樹，

5、同時(shí)充分利用已生成的頻繁模式信息，使得產(chǎn)生的候選模式數(shù)量較少。
　　 ③部分標(biāo)記頻繁子圖挖掘算法。
　　 提出一種模式增長的部分標(biāo)記頻繁子圖挖掘有效算法PLSM。其特點(diǎn)是：建立gIDX索引結(jié)構(gòu)，提高訪問效率。通過弱化操作，構(gòu)造部分標(biāo)記候選模式，通過計(jì)算支持度找出頻繁模式；采用深度優(yōu)先，最右模式增長的策略，挖掘任務(wù)只在部分標(biāo)記圖上進(jìn)行。
　　 ④約束條件下樹結(jié)構(gòu)數(shù)據(jù)頻繁模式挖掘算法。
　　 提出一種基于約束

6、的頻繁子樹挖掘算法CTreeMiner?；诮o出的約束定義，利用約束的簡潔性在數(shù)據(jù)預(yù)處理階段對數(shù)據(jù)進(jìn)行修剪，如基于項(xiàng)約束的原則設(shè)置權(quán)重支持度，根據(jù)權(quán)重支持度和頻繁度檢查模式項(xiàng)是否滿足約束要求。在挖掘過程中，根據(jù)約束集的要求對搜索空間進(jìn)行修剪，降低匹配測試代價(jià)；同時(shí)，為了進(jìn)一步減少生成模式的數(shù)量，將需求限制在閉模式的挖掘上。
　　 ⑤約束條件下圖結(jié)構(gòu)數(shù)據(jù)的頻繁模式挖掘。
　　 具有較高的支持度但僅包含幾個(gè)子圖的小模式與支持