XML非完全結構查詢處理中若干關鍵技術的研究.pdf

1、隨著Internet的發(fā)展和異構信息源集成技術以及存儲技術的進步，網(wǎng)絡中涌現(xiàn)出大量半結構化數(shù)據(jù)資源。XML由于其所具有的自描述性、靈活的數(shù)據(jù)結構以及豐富的數(shù)據(jù)表示能力等特點，逐漸成為數(shù)據(jù)表示、存儲和交換標準之一。近年來，XML非完全結構查詢處理技術作為有效管理XML文檔的關鍵技術之一，引起越來越多研究人員的關注。 XML非完全結構查詢(Non-fullyStructuredQuery,NFSQuery)是指滿足用戶在缺乏完整的X

2、ML文檔結構信息情況下的查詢需求。NFS查詢是近兩年出現(xiàn)的XML查詢技術，其主要面向缺少完整的結構信息說明以及異構環(huán)境下的查詢需求。在實際中，特別是在Internet和Intranet上，大部分XML文檔缺少結構說明或存在異構現(xiàn)象，這使得NFS查詢有著廣泛的應用前景。本文就XML非完全結構查詢處理技術中的有意義的NFS查詢結果判斷技術和基于內容的查詢結果聚類技術進行了深入研究。 有意義的NFS查詢結果判斷是NFS查詢處理中非常重

3、要的一環(huán)，現(xiàn)有的判斷方法，如XSEarch中的InterconnectionRelationship和Timber中MLCA，都是從一個特定的角度來設計判斷標準，缺乏一個準確和全面的定義，這使得它們只能適用于特定的XML文檔。另外，現(xiàn)有方法無法適應于大規(guī)模XML文檔，如XSEarch的索引建立時間和Timber的查詢時間在大規(guī)模XML文檔下遠遠超出用戶的容忍程度。 本文提出了一種基于模式和實體概念的有意義的NFS查詢結果判斷模型

4、—PE模型。PE模型從系統(tǒng)角度出發(fā)定義了一種用戶普遍接受的判斷方法，與具體的等價模式和等價查詢項的判斷方法無關，具有可擴展性。基于PE判斷模型，提出一種具體的基于結構相似性的等價模式判斷方法，并給出了一個判斷規(guī)則。為了提高NFS查詢的執(zhí)行效率，設計了模式索引PE和增強的倒排索引I2P，提出一種高效的NFS查詢算法，它們不僅可以支持高效的路徑查詢和關鍵字查詢，而且可以有效地支持本文提出PE模型，并有效地利用了現(xiàn)有XML數(shù)據(jù)庫系統(tǒng)中的索引資

5、源，適用于大部分XML編碼方案。實驗表明，本文方法的效率和準確率要遠遠高于XSEarch和Timber系統(tǒng)，適用于大規(guī)模XML文檔。 NFS查詢?yōu)榉蔷_查詢，在XML文檔規(guī)模較大的情況下，NFS查詢往往返回大量結果。而以文檔為中心的XML文檔節(jié)點包含了大量的文本信息，為了方便用戶快速定位所需信息，通常需要對結果按照內容進行聚類。文檔聚類是實現(xiàn)這一目的的有效技術之一。基于概率模型的聚類方法具有高維數(shù)據(jù)適用性和簇可解釋性特點，被廣泛

6、用于文檔聚類。但當數(shù)據(jù)特征超過100維時，基于模型的聚類極容易產(chǎn)生聚類偏斜。目前的研究主要通過設定平衡約束條件，并將聚類問題看作約束優(yōu)化問題來防止聚類偏斜。這種解決方法的局限性是：它們均假設數(shù)據(jù)分布是均衡的,并且通過直接設定各個簇在數(shù)據(jù)集合中的比例來改進分配階段的數(shù)據(jù)分配策略，僅適用于可以事先獲得平衡約束條件的應用中。在實際應用中，這種假設在大多數(shù)情況下是無法成立的，而且很難事先設定約束條件。 本文認為聚類偏斜產(chǎn)生原因主要有以下

7、三點：簇模型的初始值選擇、簇模型對文檔特性的擬合性以及估計樣本分散化與簇模型估計泛化的互作用?；诖朔治?，提出一種克服聚類偏斜的文檔聚類方法MMPClust，它采用基于內容特性的混合模型作為簇模型，以期更準確地反映各簇基于內容的分布特征，提高分配階段的準確率，防止分配階段樣本分散化。在模型重估計階段，MMPClust自動選取模型估計樣本,降低估計樣本的分散化，有效地防止在估計階段的模型泛化。同基于約束的方法相比，MMPClust不需要事

8、先設定各個簇所占的比例作為約束條件，因而具有更好的應用性。另外，為了適應不同的應用環(huán)境，本文提出了兩種具體的聚類算法MMPClust-Ⅰ和MMPClust-Ⅱ，MMPClust-Ⅰ算法著重于聚類質量，而MMPClust-Ⅱ算法是MMPClust-Ⅰ算法的簡化，其聚類質量略有降低，但聚類效率大大高于前者。實驗結果顯示，MMPClust在很大程度上抑制了聚類偏斜的產(chǎn)生，其Macro-F1評價指標優(yōu)于現(xiàn)有的模型聚類算法。 基于概念的文

9、檔特征降維是有效提高文檔聚類質量的手段之一。然而現(xiàn)有的基于概念的特征降維技術沒有全面地反映詞、概念、文檔與主題之間的關系，并存在如何選取概念的問題。通過潛在概念變量和主題變量的引入，以及詞、潛在概念、文檔和主題之間關系的概率表示，本文的模型更全面地反映了詞與潛在概念、文檔與主題和潛在概念與主題之間的模糊關系。根據(jù)信息論中熵壓縮編碼理論，定義了求解潛在概念和文檔聚類的全局目標函數(shù)，并給出一個類似于確定性退火算法的求解算法ECTC，用以獲得

10、概念層次樹以及在不同層次的概念上文檔題聚類結果，是一種雙向軟聚類方法。提出一種基于最短描述長度原則的概念選擇方法，用以最終確定概念數(shù)目以及對應的文檔聚類結果。盡管該方法只是得到MDL的局部最優(yōu)解，但實驗表明更為泛化的概念可以取得很好的聚類結果，并且可以獲得更低維的概念空間。 總之，本文提出的基于模式和實體概念的有意義的NFS查詢結果判斷模型，及其實現(xiàn)方法大大提高了NFS查詢處理的質量和效率，而兩種文檔聚類方法不僅提高了聚類質量，