劉春梅，郭 巖，俞曉明，趙 嶺，劉 悅，程學(xué)旗

1.中國科學(xué)院 計算技術(shù)研究所，北京 100190

2.中國科學(xué)院大學(xué)，北京 100190

針對開源論壇網(wǎng)頁的信息抽取研究*

劉春梅1,2+，郭 巖1，俞曉明1，趙 嶺1，劉 悅1，程學(xué)旗1

1.中國科學(xué)院 計算技術(shù)研究所，北京 100190

2.中國科學(xué)院大學(xué)，北京 100190

LIU Chunmei,GUO Yan,YU Xiaoming,et al.Information extraction research aimed at open source Web pages.Journal of Frontiers of Computer Science and Technology,2017,11(1)：114-123.

互聯(lián)網(wǎng)上大量論壇使用開源軟件生成，針對這類論壇，提出了針對論壇網(wǎng)頁信息抽取的基于模板的信息抽取方法。首先給出了基于網(wǎng)頁結(jié)構(gòu)相似度的簇劃分策略，并通過實驗證明了該策略優(yōu)于直接基于軟件版本號等直觀類別的劃分策略；其次提出了基于開源軟件特征的聚類算法，能夠根據(jù)網(wǎng)頁相似度將大規(guī)模開源軟件生成的論壇網(wǎng)頁進(jìn)行有效的自動劃分，形成可標(biāo)注類別。實驗表明，該方法不僅保持了基于模板的抽取方法所具有的高準(zhǔn)確率的優(yōu)點，同時彌補了其模板配置與維護(hù)代價高的缺點。

記錄定位；網(wǎng)頁聚類；模板抽取

1 引言

論壇作為一種重要的網(wǎng)絡(luò)交流平臺，承載了豐富的互動信息，論壇網(wǎng)頁經(jīng)過信息抽取后形成的結(jié)構(gòu)化數(shù)據(jù)對于之后的分析與挖掘都具有重要的應(yīng)用價值。相對于新聞等其他類型網(wǎng)站，論壇網(wǎng)站的重要特點是：大量論壇網(wǎng)站都基于開源軟件構(gòu)建。在互聯(lián)網(wǎng)上隨機(jī)爬取了10萬個論壇網(wǎng)頁，經(jīng)統(tǒng)計發(fā)現(xiàn)其中開源軟件生成的網(wǎng)頁的比例為70%左右（見4.1.1節(jié)實驗）。由于目前針對論壇網(wǎng)頁的信息抽取技術(shù)在維護(hù)代價和準(zhǔn)確率等方面尚不能讓人滿意，本文將基于以上觀察，研究針對開源論壇網(wǎng)站的信息抽取方法。

開源論壇網(wǎng)頁具有以下特點：

（1）同種開源軟件生成的論壇網(wǎng)頁有明顯的規(guī)律特征，這些規(guī)律特征包括內(nèi)容特征和結(jié)構(gòu)特征。內(nèi)容特征是指網(wǎng)頁文本內(nèi)容的一些指紋信息，如對于discuz生成的網(wǎng)頁，在底部會有“Powered By Discuz 2.1”的字樣。結(jié)構(gòu)特征是指由相同開源論壇軟件生成的網(wǎng)頁在DOM樹的結(jié)構(gòu)特征方面具有高度相似性。

（2）開源軟件生成的論壇網(wǎng)頁在結(jié)構(gòu)上相對穩(wěn)定。因為開源軟件只有在出現(xiàn)升級版時，才會出現(xiàn)新類型網(wǎng)頁，所以從某種角度上講，由已知開源軟件生成的論壇網(wǎng)頁在結(jié)構(gòu)上也是已知且不變的。

論壇網(wǎng)頁信息抽取方法通常分為基于模板的抽取方法和全自動抽取方法兩類?；谀０宓姆椒ň哂谐槿?zhǔn)確率高的優(yōu)點，但需要大量人工進(jìn)行模板配置和維護(hù)；全自動的信息抽取方法雖然人工代價小，但準(zhǔn)確率相對較低?；诂F(xiàn)有方法特點，對開源軟件生成的論壇信息進(jìn)行信息抽取，一種自然的想法是利用開源軟件生成網(wǎng)頁的規(guī)律性，將網(wǎng)頁劃分成簇，每個簇中的網(wǎng)頁具有高度相似性，進(jìn)而使用基于模板的方法進(jìn)行高精度抽取；同時，由于簇的數(shù)量較少，模板配置和維護(hù)代價相對較小。但該方法涉及以怎樣的策略對網(wǎng)頁進(jìn)行劃分，才能更好地利用規(guī)律性的問題；同時，由于論壇信息整體規(guī)模較大，人們希望簇劃分能夠自動進(jìn)行，這需要找到自動完成簇劃分的有效方法。本文將從這兩個角度出發(fā)提出針對開源論壇軟件生成網(wǎng)頁的信息抽取方法。

（1）提出基于網(wǎng)頁結(jié)構(gòu)相似度的簇劃分策略，并通過實驗證明該策略優(yōu)于直接基于軟件版本號等直觀類別的劃分策略。

（2）提出基于開源軟件特征的聚類算法，能夠根據(jù)網(wǎng)頁相似度將大規(guī)模開源軟件生成的論壇網(wǎng)頁進(jìn)行有效的自動劃分，形成可標(biāo)注類別。

使用本文提出的方法抽取開源軟件生成的論壇網(wǎng)頁，優(yōu)點在于：具有基于模板抽取方法的高準(zhǔn)確率；開源軟件生成的網(wǎng)頁結(jié)構(gòu)具有很強(qiáng)的規(guī)律性，能夠使用少量模板覆蓋大規(guī)模網(wǎng)頁，降低模板配置的代價；開源軟件生成的網(wǎng)頁結(jié)構(gòu)相對穩(wěn)定，模板失效的可能性很小，從而使得抽取模板的維護(hù)代價也很小。從應(yīng)用的角度看，由于對開源軟件論壇頁面自動識別較為容易，本文方法不僅可以單獨針對開源論壇網(wǎng)站進(jìn)行抽取，也可以用于提升論壇整體抽取的效果。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3章介紹核心算法和實現(xiàn)；第4章介紹實驗部分；最后進(jìn)行未來工作的展望。

2 相關(guān)工作

本文涉及的相關(guān)工作包括兩方面：論壇信息抽取和網(wǎng)頁聚類。

針對論壇的信息抽取方法主要是全自動信息抽取方法和基于模板的信息抽取方法。全自動論壇信息抽取算法可以分成兩類：

（1）單頁面重復(fù)結(jié)構(gòu)發(fā)現(xiàn)。這類方法大多借助網(wǎng)頁中記錄之間結(jié)構(gòu)的相似性找各條記錄所在的節(jié)點。例如經(jīng)典的MDR（mining data records）算法[1]以及其后續(xù)改進(jìn)的算法DEPTA（data extraction based on partial tree alignment）[2]提供了一種多記錄節(jié)點挖掘法。實際應(yīng)用中，網(wǎng)頁結(jié)構(gòu)有兩種特殊情況：論壇頁面只包含一樓記錄，或者主貼記錄與其他記錄有不同的結(jié)構(gòu)。由于MDR算法是利用多個相似子樹來定位多記錄節(jié)點，這使得MDR一類的算法只適用于挖掘有多個結(jié)構(gòu)相似的記錄節(jié)點，而無法處理上述兩種情況，導(dǎo)致從整體上降低了論壇信息抽取準(zhǔn)確率。本文對此有較好的處理處理方法。

（2）多頁面重復(fù)結(jié)構(gòu)規(guī)約。該類方法以Crescenzi等人的RoadRunner[3]為代表，通過對比多個同類型頁面的html串或者DOM樹的異同，規(guī)約出模板。

近年來，針對上述兩類方法只使用了結(jié)構(gòu)信息或文本信息的問題，文獻(xiàn)[2,4-5]通過加入Render& Layout過程，引入視覺信息，通過性能犧牲換取了更高的數(shù)據(jù)記錄識別準(zhǔn)確率。另外，除了充分挖掘網(wǎng)頁通用屬性信息，文獻(xiàn)[6-7]針對特定的抽取對象，引入了領(lǐng)域知識，并在特定領(lǐng)域的網(wǎng)頁內(nèi)容抽取上取得了很好的成績。

基于模板的論壇信息抽取方法可以分為兩類：包裝器歸納方法和模板自動生成方法。而自動化的方法有準(zhǔn)確率低的缺點，因此本文采用的抽取方法是包裝器歸納法。包裝器歸納方法通常由用戶在網(wǎng)頁源碼中標(biāo)記出需要抽取的信息，然后使用基于規(guī)則的機(jī)器學(xué)習(xí)等技術(shù)自動歸納出包裝器。經(jīng)典的包裝器歸納方法有SoftMealy算法[8]。SoftMealy使用有限狀態(tài)機(jī)來刻畫屬性之間的轉(zhuǎn)換關(guān)系，放松了對屬性順序的要求。因此，SoftMealy支持多對象性、缺值性、多值性和多序性，使得待抽取對象的結(jié)構(gòu)可以存在更多差異，即模板的通用性較好。包裝器歸納方法的優(yōu)點在于一旦生成了包裝器，對結(jié)構(gòu)相同或非常相似的網(wǎng)頁有很好的抽取效果。但是對于海量且異構(gòu)的網(wǎng)頁來說，包裝器的人工維護(hù)代價過大。本文使用SoftMealy對開源論壇軟件生成網(wǎng)頁進(jìn)行抽取。但在抽取之前，首先使用聚類技術(shù)對網(wǎng)頁按照結(jié)構(gòu)相似程度劃分，然后針對每簇預(yù)先配置模板，從而在保持SoftMealy算法本身具有的抽取準(zhǔn)確率高，包裝器通用性好等優(yōu)點的同時，大幅度降低Soft-Mealy包裝器的配置與維護(hù)代價。

針對于網(wǎng)頁聚類，特征選取至關(guān)重要。文獻(xiàn)[9-10]的聚類特征除了考慮網(wǎng)頁結(jié)構(gòu)特征外，還考慮了網(wǎng)頁的內(nèi)容特征。文獻(xiàn)[9]的聚類算法的特征是基于網(wǎng)頁分塊信息的，對每個分塊除考慮網(wǎng)頁結(jié)構(gòu)特征外，還有錨文本、URL等內(nèi)容特征；文獻(xiàn)[10]的聚類算法的結(jié)構(gòu)特征考慮的是DOM樹的分層特征，內(nèi)容特征包括URL、關(guān)鍵詞、錨文本等。另外一些聚類算法如文獻(xiàn)[11-14]選取的特征純粹是基于網(wǎng)頁結(jié)構(gòu)的，文獻(xiàn)[11]的聚類算法利用局部標(biāo)簽樹的編輯距離，而文獻(xiàn)[12]的聚類算法利用全局XPath作為網(wǎng)頁的特征。本文提出的聚類算法充分利用論壇開源軟件生成網(wǎng)頁的規(guī)律性特征，例如基于記錄節(jié)點的局部XPath等特征，并選擇層次聚類和K中心點算法相融合的H-K算法進(jìn)行聚類[15]。

3 針對開源軟件的信息抽取方法

論壇網(wǎng)頁中的帖子列表頁面和帖子詳情頁面包含了豐富且價值很高的信息，本文的研究重點在于解決帖子列表頁面和帖子詳情頁面的抽取問題。如前文所述，開源論壇軟件生成的網(wǎng)頁有明顯的規(guī)律特征，這些規(guī)律特征包括內(nèi)容特征和結(jié)構(gòu)特征，而且開源軟件生成的論壇網(wǎng)頁在結(jié)構(gòu)上相對穩(wěn)定?？紤]到上述規(guī)律，將這些開源軟件生成的論壇網(wǎng)頁劃分成多個簇，保證每個簇中的網(wǎng)頁具有足夠的相似性，從而可以用同一個模板進(jìn)行抽取。這樣做的目的是在抽取時，為每一個簇配置一個模板即可，既可以獲得較高的抽取準(zhǔn)確率，又可以大幅度降低模板的配置與維護(hù)代價。因此，本章將首先研究簇劃分策略，然后提出簇的自動劃分方法，最后給出完整的抽取方法。

3.1 簇劃分策略

論壇軟件本身有軟件和版本之分，例如discuz X2.5，因此最自然的簇劃分策略是將同一個軟件和版本的開源軟件生成的論壇網(wǎng)頁劃分為一個簇，并為它配置一個模板完成抽取，即按照軟件版本對網(wǎng)頁進(jìn)行劃分。4.1.2節(jié)對論壇軟件版本和同一版本所需抽取模板數(shù)量進(jìn)行了統(tǒng)計分析發(fā)現(xiàn)，相同版本號的開源軟件生成的網(wǎng)頁在結(jié)構(gòu)方面依然存在一定差異，無法使用一個模板完成抽取；同時，進(jìn)一步分析發(fā)現(xiàn)有些不同版本號的開源軟件的網(wǎng)頁在結(jié)構(gòu)特征方面反而相似度很高。因此利用版本號對網(wǎng)頁進(jìn)行劃分的方法難以很好地利用開源軟件生成論壇網(wǎng)頁間的相似性，不是有效的簇劃分策略。

基于模板的抽取方法對網(wǎng)頁的DOM樹特征非常敏感，因此本文根據(jù)DOM樹的結(jié)構(gòu)特征對開源論壇網(wǎng)頁做更精確的劃分，最終選擇了基于DOM樹結(jié)構(gòu)特征的聚類算法。

4.2節(jié)實驗結(jié)果表明，和按照軟件版本對網(wǎng)頁進(jìn)行劃分相比較，按照聚類結(jié)果對網(wǎng)頁的劃分能夠保證相同簇中的網(wǎng)頁在結(jié)構(gòu)上具有更強(qiáng)的相似性，使得每一簇網(wǎng)頁可以共用一個信息抽取模板，而且只需對簇的中心頁面配置模板即可。由于開源論壇軟件生成的網(wǎng)頁結(jié)構(gòu)相對穩(wěn)定，使得人們預(yù)先得到的聚類結(jié)果，以及對每一個簇配置的抽取模板都相對穩(wěn)定。這些特點都大幅度降低了生產(chǎn)環(huán)境中對抽取模板的失效檢測與維護(hù)的代價。

3.2 基于聚類的劃分方法

為了描述本文提出的基于聚類的劃分方法，給出以下定義：

（1）記錄節(jié)點和記錄統(tǒng)領(lǐng)節(jié)點。網(wǎng)頁的DOM樹中，每條數(shù)據(jù)記錄中承載的子樹的根節(jié)點稱為記錄節(jié)點，在圖1中是div[class,bm_c]以及它的右兄弟div節(jié)點。記錄統(tǒng)領(lǐng)節(jié)點就是所有記錄節(jié)點的父節(jié)點，在圖1中是div[class,vt]節(jié)點。

（2）主貼節(jié)點。主貼記錄也是一種特殊的數(shù)據(jù)記錄，在網(wǎng)頁中，它與其他數(shù)據(jù)記錄在格式上有很大的不同，為了區(qū)別其他數(shù)據(jù)記錄，將主貼記錄子樹的根節(jié)點成為主貼節(jié)點。

（3）子樹特征。子樹特征是從該子樹的根節(jié)點到所有結(jié)束節(jié)點的XPath特征的集合。

每個XPath特征是一個字符串，由途經(jīng)的標(biāo)簽名稱和class屬性構(gòu)成。如果class屬性中有數(shù)字，則一律轉(zhuǎn)換成d+的正則表達(dá)式形式。如圖1中DIV [class,bm_c]節(jié)點的特征集合為：

Fig.1 DOM tree圖1 DOM樹舉例

根據(jù)特征的功能，本文將記錄節(jié)點的特征分為兩類：

（1）聚類特征。網(wǎng)頁中每個記錄節(jié)點下的子樹特征是記錄節(jié)點的聚類特征。

（2）定位特征。記錄節(jié)點所在的位置特征，以及記錄節(jié)點的格式特征統(tǒng)稱為記錄節(jié)點的定位特征，進(jìn)而提取聚類特征。

本文提出的基于聚類的劃分方法需要解決的關(guān)鍵問題如下：

（1）定位特征庫的構(gòu)建。在進(jìn)行聚類之前，為了減少網(wǎng)頁中導(dǎo)航、廣告等造成的噪音特征，首先需要利用定位特征定位到網(wǎng)頁中所有的記錄節(jié)點。為了能夠增量地利用這些具有共性的定位特征，使用大量開源軟件生成的網(wǎng)頁進(jìn)行離線訓(xùn)練，利用相似子樹聚類等技術(shù)自動學(xué)習(xí)出記錄節(jié)點的定位特征，并將其存儲到定位特征庫中。

（2）結(jié)構(gòu)相似網(wǎng)頁的聚類。在聚類過程中，首先利用定位特征庫中的特征找到網(wǎng)頁中所有的記錄節(jié)點，然后在每個記錄節(jié)點下抽取局部XPath作為聚類特征進(jìn)行聚類，最后為每個聚類的中心頁面配置模板。為了得到聚類的中心頁面，本文采用的聚類算法是基于層次聚類和K中心聚類的融合算法H-K算法。

3.2.1 定位特征庫的構(gòu)建

通過分析，將記錄節(jié)點和主貼節(jié)點分別在論壇列表頁面和帖子頁面中的位置情況分為圖2的4種類型。

Fig.2 Four cases of page structures圖2 論壇網(wǎng)頁結(jié)構(gòu)的4種情況

對于前兩種情況，需要查找到重復(fù)子樹集合，集合中每個重復(fù)子樹的根節(jié)點即記錄節(jié)點。后兩種情況分別表示含主貼節(jié)點的情況?；谝陨嫌^察，構(gòu)建定位特征庫主要有以下3步：

步驟1記錄節(jié)點定位

后序遍歷網(wǎng)頁的DOM樹，保證在遍歷到某個節(jié)點時，其孩子節(jié)點的特征已經(jīng)提取完畢。在遍歷過程中，對當(dāng)前遍歷的節(jié)點做以下3個操作：

（1）判斷候選記錄統(tǒng)領(lǐng)節(jié)點

因為記錄統(tǒng)領(lǐng)節(jié)點具有這樣的特性：它的重復(fù)子樹數(shù)目大于1，所以需要進(jìn)行重復(fù)子樹的查找，利用聚類的方法，將重復(fù)子樹聚到一個簇中。有的簇中重復(fù)子樹個數(shù)大于1，則認(rèn)為當(dāng)前遍歷節(jié)點有可能是記錄統(tǒng)領(lǐng)節(jié)點，記為候選統(tǒng)領(lǐng)節(jié)點。

（2）判斷候選記錄節(jié)點

一個數(shù)據(jù)記錄的子樹可能存在于多個簇中，如圖2的第二種情況所示，因此需要將屬于一條數(shù)據(jù)記錄的簇進(jìn)行合并，合并的條件是：一個簇中按順序存儲著每個子樹的位置索引，如果簇的子樹數(shù)目相等，且簇間子樹的位置索引間隔依次相等，則可將這些簇進(jìn)行合并。最后得到的所有重復(fù)子樹個數(shù)大于1的簇，這些簇中的子樹節(jié)點都是候選記錄節(jié)點。

（3）篩選記錄節(jié)點

為了保證記錄節(jié)點定位的準(zhǔn)確性，需要使用一些約束條件從候選記錄節(jié)點中篩選出真正的記錄節(jié)點。約束條件有如下5點：

①一般記錄統(tǒng)領(lǐng)節(jié)點和記錄節(jié)點的標(biāo)簽為div、table。

②每一條數(shù)據(jù)記錄中都需要有時間序列，如2014-12-26 12:14，前天14:24。

③如果記錄節(jié)點含有Id的屬性，那么它的Id為數(shù)字且長度大于3。

④記錄統(tǒng)領(lǐng)節(jié)點的深度一般不超過11。

⑤滿足上述條件的節(jié)點中，深度最大的節(jié)點作為統(tǒng)領(lǐng)節(jié)點。

對于單記錄頁面或者噪聲頁面，使用以上約束條件篩選后，將不會抽出任何記錄節(jié)點。

步驟2主貼節(jié)點的發(fā)現(xiàn)

研究發(fā)現(xiàn)主貼節(jié)點具有以下特征：

（1）主貼節(jié)點是第一個記錄節(jié)點的左兄弟或者統(tǒng)領(lǐng)節(jié)點的左兄弟。

（2）主貼節(jié)點中含有時間序列信息且文本內(nèi)容滿足一定的長度。

因此，在找到記錄節(jié)點后，根據(jù)以上特征繼續(xù)發(fā)現(xiàn)主貼節(jié)點。

步驟3定位特征存儲

找到記錄節(jié)點和主貼節(jié)點后，需要從中提取定位特征。提取過程如下：

（1）因為標(biāo)簽節(jié)點的ID屬性在整個網(wǎng)頁中有唯一性，所以如果最后查找的記錄節(jié)點有ID的屬性，則將該ID換成正則表達(dá)式形式并作為定位特征存儲，如post_123456的ID轉(zhuǎn)換成post_d+形式。

（2）如果不含有ID屬性，則將該節(jié)點以及其3個前驅(qū)節(jié)點的XPath特征作為記錄節(jié)點的定位特征存儲。

因為每個定位特征都是一個字符串，所以在使用定位特征庫進(jìn)行記錄節(jié)點的定位時，可以將定位特征庫以哈希表的形式存在內(nèi)存中，從而加快檢索效率。

3.2.2 網(wǎng)頁聚類

在聚類過程中，首先遍歷DOM樹，查找所有滿足定位特征的節(jié)點，然后提取出該節(jié)點下的子樹特征作為網(wǎng)頁的聚類特征。

本文的聚類算法采用層次聚類和K中心點融合的H-K算法。K中心算法的初始K值和初始聚類中心的選擇由基于閾值的層次聚類得到。經(jīng)過多次實驗，發(fā)現(xiàn)當(dāng)閾值設(shè)為2時可以很好地劃分結(jié)構(gòu)相似的網(wǎng)頁。將距離小于閾值的網(wǎng)頁放到一個初始簇中。

網(wǎng)頁i和網(wǎng)頁j間的距離定義如下：

其中，leni表示網(wǎng)頁i中特征的個數(shù)；lenj表示網(wǎng)頁j中特征的個數(shù)；overlap表示兩個網(wǎng)頁相同的特征的個數(shù)。

得到初始簇分布后，利用K中心算法進(jìn)行迭代，當(dāng)簇分布在兩次迭代中完全一樣時，迭代停止，得到最終的簇分布結(jié)果。

3.3 開源論壇網(wǎng)頁的信息抽取方法

在實際應(yīng)用中，針對每個簇的中心頁面，使用SoftMealy算法配置模板。信息抽取的流程如圖3所示。其中虛線框中的過程即是上文提到的兩個技術(shù)關(guān)鍵點。

Fig.3 Extraction flow圖3 抽取流程圖

4 實驗

實驗數(shù)據(jù)集是作者利用爬蟲在互聯(lián)網(wǎng)上隨機(jī)爬取的10萬個論壇網(wǎng)頁，來源于2 455個網(wǎng)站。其中帖子列表頁面有40 000個，帖子詳情頁面有60 000個。

4.1 開源軟件網(wǎng)頁統(tǒng)計

4.1.1 開源論壇網(wǎng)頁的比例

本文利用開源論壇網(wǎng)頁的內(nèi)容特征，對數(shù)據(jù)集中的開源論壇網(wǎng)頁所占比例以及各個開源軟件比例進(jìn)行統(tǒng)計，得到如圖4的統(tǒng)計結(jié)果。

Fig.4 Proportion of open source Web pages and software圖4 開源論壇網(wǎng)頁以及軟件的比例

由圖4可見，數(shù)據(jù)集中的開源論壇網(wǎng)頁所占比例為70%，約7萬個。這些網(wǎng)頁也是下面實驗主要的訓(xùn)練集。

4.1.2 開源軟件的版本

本文利用開源軟件生成的網(wǎng)頁的內(nèi)容特征，獲知每個網(wǎng)頁在開源軟件中的具體版本。對4.1.1節(jié)中統(tǒng)計得到的4個常見的開源軟件，繼續(xù)統(tǒng)計每個開源軟件有多少種版本，得到的統(tǒng)計結(jié)果如表1所示。

Table 1 Versions of open source softwares表1 開源軟件版本統(tǒng)計

4.1.3 相同版本的模板數(shù)目

相同版本號的網(wǎng)頁的結(jié)構(gòu)應(yīng)該是有一些共性的，為了驗證相同版本號的網(wǎng)頁是否可以用一個模板進(jìn)行配置，本文選擇了比例最大的discuz軟件中一些常見的版本號，對于每個版本號在數(shù)據(jù)集中隨機(jī)選擇了200個網(wǎng)頁，進(jìn)行模板數(shù)目的統(tǒng)計，得到如表2所示的結(jié)果。

Table 2 Versions and templates statistics表2 版本號與模板數(shù)量統(tǒng)計

以上實驗也表明了相同版本號的網(wǎng)頁并不能全部用一個模板進(jìn)行抽取。

4.2 記錄節(jié)點定位

因為記錄節(jié)點定位需要人工判斷正確性，所以本部分實驗在數(shù)據(jù)集中隨機(jī)選擇200個開源論壇網(wǎng)頁，這200個網(wǎng)頁來自200個不同的網(wǎng)站，其中版面頁面以及帖子詳情頁面各占一半。

4.2.1 評價指標(biāo)

根據(jù)抽取的結(jié)果，可將抽取結(jié)果分為5種情況：

A，多記錄頁面，抽取出正確的記錄節(jié)點；

B，多記錄頁面，抽取出錯誤的記錄節(jié)點；

C，多記錄頁面，沒抽取出記錄節(jié)點；

D，對于單記錄頁面，沒有抽取出結(jié)果；

E，對于單記錄頁面，抽取出結(jié)果。

可以看出，如果A+D所占的比例越大，實驗效果越好。

4.2.2 實驗結(jié)果及分析

本部分實驗主要是與文獻(xiàn)[1]提到的多記錄挖掘算法MDR進(jìn)行對比。比較結(jié)果表3所示。

Table 3 Record mining algorithms comparison表3 記錄挖掘算法比較

本文算法旨在降低B和E的兩種情況。因為這兩種情況可能會產(chǎn)生比較壞的后果，會造成對網(wǎng)頁記錄產(chǎn)生錯誤定位，從而提取出錯誤的特征；而對于C這種情況，在訓(xùn)練數(shù)據(jù)量大的情況下，一個網(wǎng)頁的數(shù)據(jù)記錄由于一些原因無法抽取，卻可以通過別的網(wǎng)頁來抽取，最終影響較小。

最終特征庫生成的訓(xùn)練集是數(shù)據(jù)集中7萬個開源論壇網(wǎng)頁，共生成了77條記錄特征。

4.3 網(wǎng)頁聚類

為驗證3.2.2節(jié)網(wǎng)頁聚類的效果，本部分實驗利用之前生成的定位特征庫，隨機(jī)選擇200個開源論壇網(wǎng)頁作為訓(xùn)練集。聚類結(jié)果以是否能用一個模板抽取為評價標(biāo)準(zhǔn)，人工構(gòu)建了標(biāo)準(zhǔn)答案集。

4.3.1 評價指標(biāo)

利用準(zhǔn)確率、召回率以及F1值對聚類結(jié)果進(jìn)行評價。設(shè)整個網(wǎng)頁數(shù)目為N，則兩兩構(gòu)成一對，則該數(shù)據(jù)集中的網(wǎng)頁對為N(N-1)/2個。網(wǎng)頁聚類結(jié)果有如下4種情況：

TP，同一類的網(wǎng)頁被分到同一個簇；

TN，不同類的網(wǎng)頁被分到不同簇；

FP，不同類的網(wǎng)頁被分到同一個簇；

FN，同一類的網(wǎng)頁被分到不同簇。

4.3.2 實驗結(jié)果及分析

選擇聚類算法FPC[10]進(jìn)行對比實驗。FPC聚類算法的特征選取了DOM樹的分層信息作為聚類特征。結(jié)果如表4所示。

Table 4 Comparison of cluster algorithms表4 聚類算法比較

因為最終需要按照是否能共用一個模板來劃分簇，所以對每一個網(wǎng)頁的結(jié)構(gòu)非常敏感。通過表2可以看到，對于論壇網(wǎng)頁的聚類，F(xiàn)PC算法效果遠(yuǎn)不如本文算法。原因如下：一是FPC算法采用的是KMeans算法，KMeans算法對噪聲比較敏感，聚類效果不如本文改進(jìn)的H-K算法；二是FPC算法采用的特征是DOM樹的分層特征，相比之下，本文算法的附帶class屬性的XPath特征對DOM樹的結(jié)構(gòu)有更好的表示。

4.4 抽取測試

最終的聚類和標(biāo)注的訓(xùn)練集是數(shù)據(jù)集中7萬個開源論壇網(wǎng)頁，測試數(shù)據(jù)來源于鳳凰網(wǎng)發(fā)布的論壇排行榜中的14個開源論壇的網(wǎng)站，這14個網(wǎng)站沒有在訓(xùn)練集中出現(xiàn)過。最終共配置了60個模板。對于每一個網(wǎng)站各自抽取了10個帖子詳情頁面以及10個帖子列表頁面，測試結(jié)果抽取準(zhǔn)確率可達(dá)到100%，具體結(jié)果如表5所示。

5 小結(jié)

本文針對開源論壇網(wǎng)頁規(guī)律性強(qiáng)，所占比重大的特點，先利用大量訓(xùn)練網(wǎng)頁構(gòu)建定位特征庫，然后利用定位特征定位記錄節(jié)點，獲取節(jié)點下的XPath特征作為聚類特征，最后將這些網(wǎng)頁進(jìn)行聚類，為每一個聚類的中心頁面人工配置模板。實驗表明，這些模板很大程度上覆蓋了開源軟件生成的網(wǎng)頁，在降低人工標(biāo)注代價的前提下，大幅度提高了抽取的準(zhǔn)確率。

[1]Liu Bing,Grossman R,Zhai Yanhong.Mining data records in Web pages[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27,2003.New York:ACM, 2003:601-606.

[2]Zhai Yanhong,Liu Bing.Web data extraction based on partial tree alignment[C]//Proceedings of the 14th International Conference on World Wide Web,Chiba,Japan,May 10-14, 2005.New York:ACM,2005:76-85.

[3]Crescenzi V,Mecca G,Merialdo P.RoadRunner:towards automatic data extraction from large Web sites[C]//Proceedings of the 27th International Conference on Very Large Data Bases,Roma,Italy,Sep 11-14,2001.San Francisco, USA:Morgan Kaufmann Publishers Inc,2001:109-118.

[4]Grigalis T.Towards Web-scale structured Web data extrac-tion[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining,Rome,Italy,Feb 6-8,2013.New York:ACM,2013:753-758.

[5]Huang Wuguan,Zhu Ming,Yin Wenke.Web information automatic extraction based on DOM tree and visual feature[J]. Computer Engineering,2013,39(10):309-312.

[6]Alvarez M,Pan A,Raposo J,et al.Extracting lists of data records from semi-structured Web pages[J].Data&Knowledge Engineering,2008,64(2):491-509.

[7]Yang Zhou,Zhuo Lin,Zhao Pengpeng,et al.Automatic extraction method for product data records[J].Computer Engineering,2010,36(23):262-265.

[8]Hsu C-N,Dung M-T.Generating finite-state transducers for semi-structured data extraction from the web[J].Information Systems,1998,23(8):521-538.

[9]Fan Yixing,Guo Yan,Li Xipeng,et al.A multi-level page clustering method based on page segmentation[J].Journal of Shandong University:Natural Science,2015,50(7):1-8.

[10]Yu Jun,Guo Yan,Zhang Kai,et al.FPC:fast increment clustering for large scale Web pages[J].Journal of Chinese Information Processing,2016,30(2):182-188.

[11]Liu Yunfeng.A text information extraction algorithm based on tag XPath clustering[J].ComputerApplications and Software,2010,27(11):199-202.

[12]Li Rui,Zeng Junyu,Zhou Siwang.Improved Web page clustering algorithm based on partial tag tree matching[J]. Journal of ComputerApplications,2010,30(3):818-820.

[13]Han Pu,Wang Ze.Information extraction for Web forum based on repeated pattern[J].Journal of Nanjing Normal University: Engineering and Technology Edition,2010,10(3):74-77.

[14]Chen Ting,Liu Jiayong,Xia Tian,et al.Information extraction research based on panel-structured Web BBS[J].Journal of Chengdu University of Information Technology,2009,24 (1):1-4.

[15]Zhang Hongyun,Li Pingping.AK-means clustering algorithm based on hierarchy[J].Software Time,2010,26(4): 228-229.

附中文參考文獻(xiàn)：

[5]黃武冠,朱明,尹文科.基于DOM樹和視覺特征的網(wǎng)頁信息自動抽取[J].計算機(jī)工程，2013,39(10):309-312.

[7]楊舟,卓林,趙朋朋,等.一種針對商品數(shù)據(jù)記錄的自動抽取方法[J].計算機(jī)工程,2010,36(23):262-265.

[9]范意興,郭巖,李希鵬,等.一種基于網(wǎng)頁塊特征的多級網(wǎng)頁聚類方法[J].山東大學(xué)學(xué)報:理學(xué)版,2015,50(7):1-8.

[10]余鈞,郭巖,張凱,等.FPC:大規(guī)模網(wǎng)頁的快速增量聚類[J].中文信息學(xué)報,2016,30(2):182-188.

[11]劉云峰.一種基于標(biāo)簽路徑聚類的文本信息抽取算法[J].計算機(jī)應(yīng)用與軟件,2010,27(11):199-202.

[12]李睿,曾俊瑀,周四望.基于局部標(biāo)簽樹匹配的改進(jìn)網(wǎng)頁聚類算法[J].計算機(jī)應(yīng)用,2010,30(3):818-820.

[13]韓普,王澤.基于重復(fù)模式的論壇信息抽取研究[J].南京師范大學(xué)學(xué)報:工程技術(shù)版,2010,10(3):74-77.

[14]陳挺,劉嘉勇,夏天,等.基于平板型Web論壇的信息抽取研究[J].成都信息工程學(xué)院學(xué)報,2009,24(1):1-4.

[15]張紅云,李萍萍.一種基于層次聚類的K均值算法研究[J].軟件時空,2010,26(4):228-229.

LIU Chunmei was born in 1991.She is an M.S.candidate at Institute of Computing Technology,Chinese Academy of Sciences.Her research interests include information extraction and data mining,etc.

劉春梅（1991—），女，河北邯鄲人，中國科學(xué)院計算技術(shù)研究所碩士研究生，主要研究領(lǐng)域為信息抽取，網(wǎng)頁數(shù)據(jù)挖掘等。

GUO Yan was born in 1974.She received the Ph.D.degree in network information processing from Institute of computing technology,Chinese Academy of Sciences in 2004.Now she is an associate researcher at Institute of Computing Technology,ChineseAcademy of Sciences.Her research interest is Web information processing.

郭巖（1974—），女，陜西西安人，2004年于中國科學(xué)院計算技術(shù)研究所獲得博士學(xué)位，現(xiàn)為中國科學(xué)院計算技術(shù)研究所高級工程師，主要研究領(lǐng)域為網(wǎng)絡(luò)信息處理。

YU Xiaoming was born in 1977.He received the Ph.D.degree in computer system architecture from University of Chinese Academy of Sciences in 2008.Now he is an associate professor at Institute of Computing Technology,ChineseAcademy of Sciences.His research interests include Internet search and mining,etc.

俞曉明（1977—），男，山東青島人，2008年于中國科學(xué)院大學(xué)獲得博士學(xué)位，現(xiàn)為中國科學(xué)院計算技術(shù)研究所高級工程師，主要研究領(lǐng)域為互聯(lián)網(wǎng)搜索與挖掘等。

ZHAO Ling was born in 1987.She received the M.S.degree in human-computer interaction from Institute of Software,Chinese Academy of Sciences in 2012.Now she is an engineer at Key Laboratory of Network Data Science and Technology,Institute of Computing Technology,Chinese Academy of Sciences.Her research interests include Web crawling and structured data extraction,etc.

趙嶺（1987—），女，河南南陽人，2012年于中國科學(xué)院軟件研究所人機(jī)交互與智能信息處理實驗室獲取碩士學(xué)位，現(xiàn)為中國科學(xué)院計算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室工程師，主要研究領(lǐng)域為Web信息采集，結(jié)構(gòu)化文本抽取等。

LIU Yue was born in 1971.She is an associate professor at Institute of Computing Technology,Chinese Academy of Sciences.Her research interests include information retrieval,data mining,complex network analysis and social computing,etc.

劉悅（1971—），女，博士，中國科學(xué)院計算技術(shù)研究所副研究員，主要研究領(lǐng)域為信息檢索，數(shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析，社會計算等。

CHENG Xueqi was born in 1971.He received the Ph.D.degree in computer science from Institute of Computing Technology,Chinese Academy of Sciences in 2006.Now he is a professor and Ph.D.supervisor at Institute of Computing Technology,Chinese Academy of Sciences.His research interests include Web information retrieval,social media analytics and network data science,etc.

程學(xué)旗（1971—），男，安徽安慶人，2006年于中國科學(xué)院計算技術(shù)研究所獲得博士學(xué)位，現(xiàn)為中國科學(xué)院計算技術(shù)研究所研究員、博士生導(dǎo)師，中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室主任，主要研究領(lǐng)域為網(wǎng)絡(luò)信息檢索，社會媒體分析，網(wǎng)絡(luò)數(shù)據(jù)科學(xué)等。發(fā)表學(xué)術(shù)論文100余篇，主持10余項國家自然科學(xué)基金、973計劃、863計劃等重要科研項目，2014年獲國家杰出青年科學(xué)基金資助。

Information Extraction ResearchAimed at Open Source Web Pages*

LIU Chunmei1,2+,GUO Yan1,YU Xiaoming1,ZHAO Ling1,LIU Yue1,CHENG Xueqi1
1.Institute of Computing Technology,ChineseAcademy of Sciences,Beijing 100190,China
2.University of ChineseAcademy of Sciences,Beijing 100190,China
+Corresponding author:E-mail:liucm1005@163.com

There is a large proportion of forum Web pages generated by open source software.This paper proposes an information extraction method aimed at open source Web pages based on templates.Firstly,a clustering strategy based on the similarity of Web page structure is proposed.The experiment results show that the strategy is superior to the direct classification based on software version.Secondly,a clustering algorithm based on open source software features is proposed.It can cluster large-scale open source forum Web pages based on similarity automatically, and form a marked category.This method not only sharply decreases manual cost on annotation templates,but also increases the accuracy of information extraction.

A

：TP181

10.3778/j.issn.1673-9418.1510016

*The National Basic Research Program of China under Grant Nos.2012CB316303,2013CB329602(國家重點基礎(chǔ)研究發(fā)展計劃(973計劃));the National High Technology Research and Development Program of China under Grant Nos.2015AA015803,2014AA015204 (國家高技術(shù)研究發(fā)展計劃(863計劃);the National Natural Science Foundation of China under Grant Nos.61232010,61173064,61173008 (國家自然科學(xué)基金);the National Key Technology Support Program of China under Grant No.2012BAH46B04(國家科技支撐計劃);the Technology Innovation and Transformation Program of Shandong Province under Grant No.2014CGZH1103(山東省自主創(chuàng)新及成果轉(zhuǎn)化專項);the Medical Imaging Program of Chinese Academy of Sciences under Grant No.KGZD-EW-T03-2(中科院醫(yī)學(xué)影像項目);the 7th Technology Framework Program of European Union under Grant No.PIRSES-GA-2012-318939(歐盟第七科技框架計劃(FP7)項目).

Received 2015-10,Accepted 2016-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-01-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160107.1540.006.html

Key words:record locating;Web page clustering;template extraction