基于相似度的網(wǎng)頁標(biāo)題抽取方法

李國華，昝紅英

(鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001)

1 引言

網(wǎng)頁文檔作為互聯(lián)網(wǎng)信息的一種載體，人們通過網(wǎng)頁文檔可以發(fā)布和獲取各種各樣的信息。隨著網(wǎng)絡(luò)信息量的與日俱增，互聯(lián)網(wǎng)上的海量信息在豐富了人們信息來源的同時，也給人們獲取感興趣的信息帶來了困難。面對海量的信息，如何有效地抽取網(wǎng)頁文檔中的數(shù)據(jù)，是關(guān)系到如何有效快捷地獲取目標(biāo)信息的關(guān)鍵技術(shù)之一。

本文提出了一種基于相似度計算方法的網(wǎng)頁“真實(shí)”標(biāo)題抽取方法。我們定義：與網(wǎng)頁正文內(nèi)容相關(guān)的標(biāo)題為“真實(shí)標(biāo)題”，與網(wǎng)頁正文內(nèi)容不相關(guān)的標(biāo)題為“虛假標(biāo)題”；相應(yīng)的網(wǎng)頁定義為“標(biāo)準(zhǔn)網(wǎng)頁”和“非標(biāo)準(zhǔn)網(wǎng)頁”；“單位”定義為HTML文檔抽取出的文本信息的獨(dú)立句子或段落。

網(wǎng)頁標(biāo)題是一篇網(wǎng)頁所要表達(dá)信息的最簡明扼要的概述，它對于網(wǎng)頁信息的處理及應(yīng)用(比如搜索引擎、聚類和分類)有很大的意義。大多數(shù)情況下我們可以通過HTML文檔中的標(biāo)簽準(zhǔn)確的獲得“真實(shí)標(biāo)題”，但有些時候人們卻不經(jīng)意地將“真實(shí)標(biāo)題”表達(dá)在自定義的HTML標(biāo)簽中，而在標(biāo)簽中填寫的是“虛假標(biāo)題”，如：

……

……

……

這樣會使通過網(wǎng)頁上顯示的標(biāo)題進(jìn)行查找資源的人們被迫錯失一些重要的信息。圖1中，顯示的是利用百度大學(xué)搜索工具在北京大學(xué)域下搜索“北京信息技術(shù)學(xué)院”的結(jié)果圖，搜索結(jié)果中大部分標(biāo)題都是“北京大學(xué)信息科學(xué)技術(shù)學(xué)院”，而不是各個相關(guān)網(wǎng)頁真正的“真實(shí)標(biāo)題”。

圖1 百度大學(xué)搜索“北京信息技術(shù)學(xué)院”

區(qū)別于現(xiàn)有的網(wǎng)頁標(biāo)題抽取方法，我們通過對網(wǎng)頁進(jìn)行預(yù)處理，將原始網(wǎng)頁中的文本信息表示成由多個語言“單位”組成的文檔，文檔中不包含 HTML 的任何屬性標(biāo)簽。然后比較兩兩之間的相似度，通過一系列計算步驟和方法，最終抽取出“真實(shí)”標(biāo)題。

實(shí)驗表明我們提出的方法在“標(biāo)準(zhǔn)網(wǎng)頁”和“非標(biāo)準(zhǔn)網(wǎng)頁”的數(shù)據(jù)集上都能取得較好的效果，并且可以成功地應(yīng)用于鄭州大學(xué)站內(nèi)搜索平臺[1]。

本文以下部分的組織結(jié)構(gòu)是：第2節(jié)介紹相關(guān)研究；第3節(jié)詳細(xì)介紹基于該方法的相關(guān)內(nèi)容；第4節(jié)給出了本方法實(shí)驗結(jié)果和說明；第5節(jié)給出總結(jié)及下一步的工作。

2 相關(guān)研究

Web信息抽取方法目前大多是基于規(guī)則的，一是利用自然語言處理技術(shù)的詞法、子句結(jié)構(gòu)、短語和子句間的關(guān)系建立基于語法和語義的抽取規(guī)則。典型的系統(tǒng)有SRV[2]、WHISK[3]等。該方法是將網(wǎng)頁文檔視為文本進(jìn)行處理，較適合含有大量非結(jié)構(gòu)化文本的網(wǎng)頁文檔。二是利用機(jī)器學(xué)習(xí)方法生成基于定界符的抽取規(guī)則[4-8]，規(guī)則的獲取需要訓(xùn)練手工標(biāo)注的樣本實(shí)例。典型的系統(tǒng)有Stalker、SoftMealy[9]和WIEN[10]等。與基于自然語言處理技術(shù)的方法相比較，該方法僅僅使用語義項的上下文來定位信息，沒有使用語言的語法約束。這兩種基于規(guī)則的抽取方法都需要訓(xùn)練樣本，自動化程度低[11]。

一般來說，同一個語言單位內(nèi)的網(wǎng)頁結(jié)構(gòu)基本相似，或干脆使用同一套網(wǎng)頁模板，文獻(xiàn)[5]和文獻(xiàn)[12]也考慮了同樣的策略。基于此方法，我們的鄭州大學(xué)校內(nèi)搜索引擎[1]前期版本是通過手工制定規(guī)則來獲取網(wǎng)頁的標(biāo)題，但是這種方法即使是在小范圍內(nèi)也需要耗費(fèi)很大的人力。

文獻(xiàn)[12]和文獻(xiàn)[13-15]通過將網(wǎng)頁分析為DOM樹，然后從DOM樹中提取出信息，文獻(xiàn)[13]將網(wǎng)頁分析為DOM樹，然后從中提取出含有特征屬性的單位，結(jié)合自定義的各種HTML特征的重要程度來提取標(biāo)題。文獻(xiàn)[16]也利用HTML的主要特征研究對Web信息檢索的作用。文獻(xiàn)[17]學(xué)習(xí)一種發(fā)現(xiàn)網(wǎng)頁中重要的塊的模型。文獻(xiàn)[18]通過基于網(wǎng)頁布局的相似度進(jìn)行Web論壇數(shù)據(jù)的抽取。

雖然很早便有類似的工作應(yīng)用在自動文摘研究領(lǐng)域[19-22]，但據(jù)我們所知，目前為止還沒有利用句子之間的相似度為基礎(chǔ)來進(jìn)行網(wǎng)頁標(biāo)題抽取的相關(guān)研究。

3 網(wǎng)頁標(biāo)題抽取

3.1 網(wǎng)頁文檔預(yù)處理

計算句子之間的相似度，首先需要將網(wǎng)頁文檔中含有的信息轉(zhuǎn)換為文本文檔表示，本文使用Nekohtml[23]開源工具包進(jìn)行轉(zhuǎn)換。Nekohtml是一個Java語言的HTML掃描器和標(biāo)簽補(bǔ)全器，借助Nekohtml我們可以解析網(wǎng)頁文檔并得到網(wǎng)頁文檔包含的所有純文本信息。

在轉(zhuǎn)換過程中，對于Element節(jié)點(diǎn)，我們增加“ ”為獲得該節(jié)點(diǎn)信息的結(jié)束標(biāo)志，從而在轉(zhuǎn)換完成后，可以對整個純文本信息以“ ”進(jìn)行劃分，將經(jīng)過劃分后的段落或句子等同定義為一個語言“單位”。正文中的噪聲比如廣告、導(dǎo)航信息或相關(guān)鏈接會分別以一個語言“單位”對待；網(wǎng)頁中的真實(shí)標(biāo)題也會獨(dú)立成為一個語言“單位”；正文信息則由一個或多個語言“單位”組成。

3.2 相似度的計算

考慮到標(biāo)題信息為網(wǎng)頁正文信息的高度概括，其長度與正文信息的長度相比差距較大，所以選擇利用正向迭代最細(xì)粒度切分算法分詞后的公共子詞語方式計算單位間的相似度。“正向迭代最細(xì)粒度切分算法”分詞方法：比如“鄭州大學(xué)”分詞后為：“鄭州大學(xué)”、“鄭州”、“大學(xué)”。

計算兩個單位unit_1和unit_2間的相似度方法如下：

其中set_1和set_2分別為需要計算的兩個單位unit_1和unit_2經(jīng)過迭代分詞后的詞語集合。如果集合中出現(xiàn)相同詞語，只保留一個詞語，且詞語的數(shù)值為集合中詞語出現(xiàn)的次數(shù)，set內(nèi)的數(shù)據(jù)結(jié)構(gòu)表示為，word為詞語，count為word出現(xiàn)的次數(shù)。

sameCT為set_1和set_2兩個集合的共同詞語的次數(shù)之和，和的值等于共同詞語的次數(shù)相加。size(set)表示set集合的長度，sameCT的計算公式如下：

sameCT=∑CT1(Wordi)+∑CT2(Wordi)

Wordi∈set_1或Wordi∈set_2

(2)

3.3 權(quán)值的計算

根據(jù)公式(1)計算出的兩兩單位之間的相似度，可以得到一個單位的權(quán)值計算公式：

(3)

其中unit_i為需要計算權(quán)值的單位；Sim(unit_i,unit_j)為unit_i與unit_j的相似度；N為文檔中的單位的總數(shù)目。

3.4 權(quán)值的調(diào)整

HITS算法通過兩個評價權(quán)值——內(nèi)容權(quán)威度(Authority)和鏈接權(quán)威度(Hub)來對網(wǎng)頁質(zhì)量進(jìn)行評估。

本文將其思想應(yīng)用到文本文檔中的各個單位之間，首先將文本文檔表示成圖G。圖G的各個頂點(diǎn)分別對應(yīng)各個單位；頂點(diǎn)之間的邊是否存在取決于頂點(diǎn)對應(yīng)的單位之間相似度的大小，如果相似度的值等于0，則頂點(diǎn)之間不存在邊；邊的權(quán)值大小為相似度的值，值大于0；頂點(diǎn)的初始權(quán)重為公式(3)計算出的權(quán)值大小。

根據(jù)圖G的定義，我們對公式(3)計算的權(quán)值進(jìn)行加權(quán)調(diào)整：

Weight′(unit_i)=Weight(unit_i)×linkCT(unit_i)

(4)

其中Weight(unit_i)為unit_i的初始權(quán)重，即公式(3)計算出的權(quán)值。linkCT為圖G中單位unit_i(unit_i)對應(yīng)頂點(diǎn)的度。

公式(4)表明，一個頂點(diǎn)的度越大，其對應(yīng)的單位的重要性也就越大。

3.5 標(biāo)題的選取步驟

本文將整篇文本文檔以“ ”劃分成多個語言單位，并通過計算后，表示成Collection<> sortList。以下是標(biāo)題選取的步驟：

1) 首先對sortList按照文檔中的單位unit的權(quán)值Weight′(unit)進(jìn)行升序排序；

2) 計算所有頂點(diǎn)的度數(shù)和TTCT以及權(quán)值大于等于?的頂點(diǎn)總個數(shù)PCT：

TTCT=∑linkCT(unit_i)

Weight′(unit_i)≥?

(5)

其中?為可定義的參數(shù)值，實(shí)驗測試取?值為 0.1 比較合適。

(6)

3) 計算平均度的閾值aveCT：

(7)

其中aveCT為用于控制權(quán)值過小的單位。判斷條件為：如果linkCT(unit_i)

4) 經(jīng)過步驟 1)、2)、3)計算：

第一，選取sortList中序號idx較小的兩個語言單位作為候選標(biāo)題。單位的序號idx定義為該單位在文本文檔被劃分為多個單位中相對應(yīng)的索引序號。這里選取原則為“真實(shí)標(biāo)題”往往出現(xiàn)在網(wǎng)頁的頂部區(qū)域，其索引序號較小。

第二，比較兩個候選單位的權(quán)值，選取權(quán)值較大的單位作為抽取“真實(shí)標(biāo)題”的結(jié)果。

4 實(shí)驗及分析

4.1 數(shù)據(jù)集的選取

為了驗證所提的方法的有效性，我們從鄭州大學(xué)校內(nèi)搜索引擎[1]抓取的網(wǎng)頁中選取部分網(wǎng)頁文檔。通過人工制定規(guī)則獲取真實(shí)標(biāo)題，并校對驗證真實(shí)標(biāo)題的正確性，剔除出現(xiàn)亂碼和全英文的網(wǎng)頁后，共計23 709篇“非標(biāo)準(zhǔn)網(wǎng)頁”，作為“非標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取的實(shí)驗數(shù)據(jù)。

同時，為了驗證提出的方法的泛化能力，本文從Web上的7個站點(diǎn)(北方網(wǎng)、新浪網(wǎng)、搜狐網(wǎng)、中華網(wǎng)、新民網(wǎng)、網(wǎng)易網(wǎng)、艾瑞網(wǎng))的子欄目利用爬蟲抓取了3 000篇“標(biāo)準(zhǔn)網(wǎng)頁”，并且從鄭州大學(xué)內(nèi)部網(wǎng)中抓取了250篇“標(biāo)準(zhǔn)網(wǎng)頁”，共計3 250篇“標(biāo)準(zhǔn)網(wǎng)頁”，作為“標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取的實(shí)驗數(shù)據(jù)。“標(biāo)準(zhǔn)網(wǎng)頁”實(shí)驗數(shù)據(jù)的來源及選取的網(wǎng)頁篇數(shù)見表1。

表1 “標(biāo)準(zhǔn)網(wǎng)頁”實(shí)驗據(jù)來源及篇數(shù)

4.2 標(biāo)題抽取的評測方法

本文使用準(zhǔn)確率作為標(biāo)題抽取結(jié)果的評估。準(zhǔn)確率的計算公式為：

(8)

同時，利用本方法抽取出的標(biāo)題和“真實(shí)標(biāo)題”的近似程度超過閾值β時，我們判定為抽取正確。此處近似值的計算方式為：

(9)

sameCT為抽取出來的標(biāo)題title_extracted和“真實(shí)標(biāo)題”的共同子詞語數(shù)；size(title_extracted)為抽取出來的標(biāo)題的長度；β等于0.6。

參數(shù)β的選取主要因為網(wǎng)頁的標(biāo)題中，發(fā)布人通常會在網(wǎng)頁的標(biāo)題后面加上信息來源，比如：“美國冒險家徒手登上海波3 900米高峰(組圖)—冒險—北方網(wǎng)—科技無限”。

4.3 “標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取實(shí)驗

從表2中我們可以看出，該方法對于Web網(wǎng)上的網(wǎng)頁抽取準(zhǔn)確率很高，泛化能力可以得到保證。經(jīng)過對由方法抽取的標(biāo)題與正確標(biāo)題進(jìn)行對比并觀察網(wǎng)頁發(fā)現(xiàn)，抽取錯誤的網(wǎng)頁特征主要集中表現(xiàn)為：類型一，網(wǎng)頁是鏈接導(dǎo)航型的網(wǎng)頁，即網(wǎng)站的子分類欄目或某個專題的索引頁面，網(wǎng)頁中正文信息過于分散；類型二，網(wǎng)頁新聞的標(biāo)題為使用近似語義概括的標(biāo)題，由于本方法沒有進(jìn)行同義詞擴(kuò)展，所以對于這類網(wǎng)頁，抽取出的效果也不是很好。

4.4 “非標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取實(shí)驗

從表3中我們可以看出，該方法對于較大數(shù)據(jù)集的“非標(biāo)準(zhǔn)網(wǎng)頁”處理性能仍然較好。經(jīng)過對由方法抽取的標(biāo)題與正確標(biāo)題進(jìn)行對比并觀察網(wǎng)頁發(fā)現(xiàn)，抽取錯誤的網(wǎng)頁特征除有“標(biāo)準(zhǔn)網(wǎng)頁”中出現(xiàn)的兩種類型的錯誤外，還表現(xiàn)為：類型三，網(wǎng)頁正文信息表達(dá)了多個主題，對于這種網(wǎng)頁，本方法抽取出的結(jié)果大都是其中的一個子主題的標(biāo)題；類型四，網(wǎng)頁為圖片或內(nèi)容為表格或文件下載，文字信息很少。四種錯誤類型的網(wǎng)頁的統(tǒng)計的數(shù)據(jù)見表4。

表2 “標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取結(jié)果

表3 “非標(biāo)準(zhǔn)網(wǎng)頁”標(biāo)題抽取結(jié)果

表4 標(biāo)題抽取錯誤的結(jié)果中——屬于四種錯誤類型的網(wǎng)頁所占篇數(shù)

以上對“標(biāo)準(zhǔn)網(wǎng)頁”和“非標(biāo)準(zhǔn)網(wǎng)頁”的標(biāo)題抽取實(shí)驗數(shù)據(jù)顯示，本文提出的方法對于抽取“非標(biāo)準(zhǔn)網(wǎng)頁”的“真實(shí)標(biāo)題”性能良好，同時對互聯(lián)網(wǎng)網(wǎng)頁的泛化能力較高。

5 結(jié)論與展望

本文提出了一種基于相似度的網(wǎng)頁標(biāo)題抽取方法，區(qū)別于利用HTML結(jié)構(gòu)和標(biāo)簽特征的標(biāo)題抽取方法，并取得了令人滿意的抽取效果。實(shí)驗表明本文提出的方法不僅可以滿意地實(shí)現(xiàn)對“非標(biāo)準(zhǔn)網(wǎng)頁”的抽取，而且對“標(biāo)準(zhǔn)網(wǎng)頁”有較好的泛化能力。下一步將考慮改進(jìn)相似度比較方法以及更深入的挖掘HITS模型對權(quán)值的調(diào)整等工作。

[1] 鄭州大學(xué)校內(nèi)搜索引擎. http://search.ha.edu.cn/zzu/[CP/OL].

[2] Freitag D. Machine Learning for Information Extraction in Informal Domains[J]. Machine Learning, 2000,39(2-3):169-202.

[3] Soderland S. Learning Information Extraction Rules for Semi-structured and Free Text[J]. Machine Learning, 1999,34(1-3):233-272.

[4] Yipu Wu, Xuejie Zhang, Qing Li, Jing Chen. Title Extraction from Loosely Structured Data Records[C]//Proceedings of the Seventh International Conference on Machine Learning and Cybernetics, 2008.

[5] Crescenzi, V., Mecca, G. and Merialdo, P. Roadrunner: Towards Automatic Data Extraction from Large Web Sites[C]//Proceedings of the Twenty-seventh International Conference on Very Large Databases(VLDB2001), 2002.

[6] Chidlovskii, B.,Ragetli, J., and de Rijke, M. Wrapper Generation via Grammar Induction[C]//Proceedings of the Eleventh European Conference on Machine Learning(ECML2000), 2000.

[7] Crescenzi, V., Mecca, G. and Merialdo, P. Wrapping-Oriented Classification of Web pages[C]//Procceedings of the 2002 ACM Symposium on Applied Computing(SAC-2002), 2002:1108-1112.

[8] Craven, T.C. HTML Tags as Extraction Cues for Web Page Description Construction[J]. Informing Science Journal, 2003,6:1-12.

[9] 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.

[10] Kushmerick N, Weld D S. Doorenbos R. Wrapper Induction for Information Extraction[J]. 15th International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, 1997:729-737.

[11] 李猛. 基于DOM的Web信息抽取技術(shù)的研究與實(shí)現(xiàn)[D].大連理工大學(xué)， 2008：5-6.

[12] Kosala, R., Bruynooghe, M., Bussche, J.V. and Blockeel, H. Information Extraction from Web Documents Based on Local Unranked Tree Automaton Inference[C]//Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence(IJCAI-2003), 2003.

[13] Yunhua Hu, Guomao Xin, Ruihua Song, Guoping Hu, Shuming Shi, Yunbo Cao, and Hang li. Title Extraction from Bodies of HTML Documents and its application to Web Page Retrieval[C]//Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval,2005: 250-257.

[14] Breuel, T.M Information Extraction from HTML Documents by Structural Matching[C]//Proceedings of the Second International Workshop on Web Document Analysis(WDA2003), 2003.

[15] Reis, D., Golgher, P., Silva, A. and Laender, A. Automatic Web News Extraction Using Tree Edit Distance[C]//Proceedings of International WWW Conference(WWW-2004),2004.

[16] Zhang, M., Song, R. and Ma, S. DF or IDF? On the use of HTML primary feature fields for Web IR[C]//Proceedings of the Twelfth International World Web Conference(WWW2003), 2003.

[17] Song, R., Liu, H., Wen, J.-R. and Ma, W.Y. Learning Block Importance Models for Web Pages[C]//Proceedings of International WWW Conference(WWW-2004), 2004.

[18] 王允, 李弼程, 林琛. 基于網(wǎng)頁布局相似度的Web論壇數(shù)據(jù)抽取[J]. 中文信息學(xué)報，2010, 24 (2)： 68-75.

[19] G.Salton, A. Singhai, M. Mitra, C.Buckly. Automatic text structuring and summarization [C]//In advances in Automatic Text Summarization, Eds. I. Mani and M.T.Maybury. The MIT Press,1999:62-70.

[20] Jae-Hoon Kim, JoonHong Kim, Dosam Hwang, 2000. Korean Text Summarization Using an Aggregate Similarity [C]//The 5th International Workshop on Information Retrieval with Asian Languages. Hong Kong, September 30 to October 3, 2000.

[21] 張奇, 黃萱菁, 吳立德. 一種新的句子相似度度量及其在文本自動摘要中的應(yīng)用[J]. 中文信息學(xué)報，2005，19(2)：93-98.

[22] Rada Mihalcea. Graph-based Ranking Algorithms for Sentence Extraction, Applied to Text Summarization[C]//Proceedings of the Conference and Workshops of ACL-2004. Barcelona.

[23] Nekohtml. http://nekohtml.sourceforge.net/[CP/OL].