半結構化數(shù)據(jù)頻繁模式挖掘相關技術研究.pdf

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

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

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

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

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

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