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

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

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

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

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

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

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