網(wǎng)絡信息自動化高效抽取技術研究.pdf

1、隨著互聯(lián)網(wǎng)爆炸式的發(fā)展和普及,網(wǎng)絡信息已經(jīng)成為了一種寶貴的信息數(shù)據(jù)資源。海量的網(wǎng)絡數(shù)據(jù)使得數(shù)據(jù)分析與挖掘系統(tǒng)進入了一個新時代,越來越多的網(wǎng)絡應用系統(tǒng)需要對來自不同數(shù)據(jù)源的結構化數(shù)據(jù)進行抽取、挖掘和整合。然而,由于網(wǎng)頁文檔的半結構化性質,網(wǎng)頁上呈現(xiàn)的數(shù)據(jù)往往不能被機器自動地抽取和理解,因此,網(wǎng)絡信息抽取的研究目標在于提取網(wǎng)頁的結構化數(shù)據(jù)?；ヂ?lián)網(wǎng)數(shù)據(jù)的海量規(guī)模與高度異構的特征,為網(wǎng)絡信息抽取工作帶來了巨大的挑戰(zhàn)。
　　本文圍繞網(wǎng)絡信息

2、的海量規(guī)模與高度異構的特征,分數(shù)據(jù)記錄抽取和數(shù)據(jù)單元抽取兩個層次,對自動化、高效抽取網(wǎng)絡信息的技術展開了相關研究,研究內容包括以下四個方面:
　　1.針對網(wǎng)絡信息高度異構的特點,提出新的自動化的基于錨點樹的數(shù)據(jù)記錄的抽取方法(Mining data records Basedon Anchor Trees,MiBAT)。首先分析了當數(shù)據(jù)記錄含有一定的不規(guī)則內容時(例如用戶原創(chuàng)內容)時,現(xiàn)有的基于相似度檢測的自動化方法并不能取得理想

3、的抽取效果。本文提出錨點的概念,對應數(shù)據(jù)記錄中的某些關鍵的數(shù)據(jù)單元。例如,每個用戶創(chuàng)建、發(fā)表的帖子記錄(例如在線論壇帖子、用戶評論等)都含有發(fā)帖時間這個關鍵的數(shù)據(jù)單元,可以作為由領域約束獲得的錨點。本文提出MiBAT方法,利用領域約束檢測出錨點,然后圍繞包含錨點的DOM(Document Object Model)子樹,完成數(shù)據(jù)記錄的自動化抽取工作。實驗表明,與以往的自動化的數(shù)據(jù)記錄抽取方法相比,MiBAT方法可以較好的克服數(shù)據(jù)記錄的不

4、規(guī)則性,具有較高的抽取準確度。
　　2.針對數(shù)據(jù)記錄層次的網(wǎng)絡信息的海量規(guī)模的特點,提出快速高效的錨點樹的尋找算法。傳統(tǒng)的網(wǎng)絡信息挖掘算法采用自上而下的枚舉DOM子樹的方式,按照這種方式設計錨點樹尋找算法,MiBAT的時間復雜度為O(n2),其中n是輸入網(wǎng)頁的DOM樹的結點的數(shù)量。本文提出一個新的基于標簽路徑自底向上聚集的錨點樹尋找算法,使得MiBAT的時間復雜度降到O(nlogn)。實驗表明,新的錨點樹尋找算法極大地提高了MiB

5、AT方法的運行效率,同時保持較高的抽取準確度。
　　3.針對網(wǎng)絡信息的跨領域異構的特點,提出不依賴領域約束的通用錨點的檢測方法。錨點的概念最初由領域約束而來,對應于領域相關的數(shù)據(jù)單元。在實際應用時,對不同的領域,需要預先指定相應的領域約束,這在某種程度上限制了MiBAT方法的自動化應用。本文對此進行擴展,提出通用錨點的概念及其檢測和應用方法。實驗表明,應用通用錨點時,MiBAT方法可以應用于不同的領域的信息抽取任務,具有較高的準確

6、度,不需要人為指定領域約束。
　　4.針對數(shù)據(jù)單元層次的網(wǎng)絡信息的海量規(guī)模的特點,研究快速高效的DOM樹匹配算法,應用在數(shù)據(jù)單元抽取對齊任務中?，F(xiàn)有的廣泛應用的樹匹配方法的復雜度是O(n2),并不適合海量規(guī)模的網(wǎng)絡信息抽取任務。本文提出一個新的基于標簽路徑序列的最長公共子列(Longest Common Subsequence,LCS)的方法。利用LCS問題的稀疏性質,算法復雜度可以達到O(rlogn),其中r等于兩棵樹上具有相同