基于鏈接路徑搜索的URL屬性集成方法

馬艷紅，胡學鋼，吳共慶

(合肥工業大學計算機與信息學院，合肥 230009)

1 概述

用于處理結構化數據的數據庫，在海量信息的檢索和數據挖掘方面已顯現出諸多的局限性。而網頁中的半結構化數據已成為人們獲取、傳播和交換信息的重要途徑。如何充分利用半結構化數據資源，并將其同傳統的結構化數據集成在一起，成為一個重要的研究課題。

例如，傳統數據庫中的數據結構相對固定，添加新的屬性列往往需要大量的人力和時間。為解決該問題，一種可行的方案是對數據庫中每個數據的相關網頁進行信息抽取，并將新的屬性填充到數據庫中。然而，由于真實數據庫信息量龐大，該方法的難點在于如何自動、高效地找到這些數據的相關網頁的URL，并得到這些網頁與數據庫的映射，為后期的信息抽取和數據挖掘等操作提供準確的信息來源。

由此可知，實現目標需進行2步，第1步是找到需填充數據庫內容的相關網頁，文獻[1]采用了決策樹和邏輯回歸分析來找到符合用戶需要的主頁，在2002 TREC Web Track[2]也有這方面的任務，目標是找到某個特定命名實體的網頁。求解的第2步是得到這些網頁和結構化數據庫之間的映射。當前有很多工作都集中在從半結構化的網頁中抽取出結構化信息[3-5]。然而，利用這些網頁來豐富結構化數據庫內容也是非常重要的。在這些半結構化網頁中存在著大量的超鏈接，而超鏈接上的核心-錨文本已經被研究多年[6-8]，其形式簡短，內容概括性強，在商業搜索引擎方面[9]起到很重要的作用。文獻[10]驗證了聚合的錨文本比鄰近鏈接更能提高查詢算法的有效性。因此，文獻[11]利用聚合的錨文本和圖的 K個最短路徑算法[12]得到相關網頁和結構化數據庫的最佳匹配。一方面，該算法可以自動地得到數據庫和相關網頁的匹配，另一方面，與只采用鄰近鏈接進行查詢相比，該算法具有更高的精度。然而，對文獻[11]的實驗數據分析可以發現，部分個人網頁的錨文本信息量不足，姓名并不在鏈接路徑錨文本包中，而網頁標題卻包含了姓名標識。因此，本文將錨文本和網頁標題結合，對鏈接路徑的相關概念重新定義，并在 W2DR算法基礎上提出一種URL屬性集成方法。

2 相關概念和問題描述

定義1(鏈接路徑) 若將網絡用有向圖表示，即每個網頁用一個頂點表示，每個超鏈接用一條有向邊表示，且每個網頁可由一個URL唯一確定，則從網頁u通過超鏈接到達網頁v的途中經過的所有頂點構成的集合為u到v的鏈接路徑。

圖1為網絡的有向圖表示示例，方框表示各個網頁，箭頭上為網頁間的錨文本，括號內是目標網頁的標題。則從源網頁u到目標網頁v1的一條鏈接路徑為:{u,x,x2,x3,v1}。

圖1 網絡的有向圖表示示例

定義2(鏈接路徑錨文本) 2個網頁間某條鏈接路徑上錨文本構成的集合。如網頁u到v1的鏈接路徑錨文本為:{People, Faculty, Primary Faculty, Web page}。

定義3 K個最短路徑PK:表示從u到v的K個最短無環路徑。用集合PK={p1,p2,…,pk}?P表示，且規定如下[12]:

其中，K是正整數；c表示權重，為方便起見，規定每條有向邊的權重為1，因此，若路徑p共經過s條有向邊，則 ()cp s= 。

定義4(鏈接路徑錨文本包) 將網頁u到v的K個最短路徑全部放在一個集合中，并對各元素賦予權重，用Au,v表示。

由圖1可知，網頁u到v1、v2、v3的鏈接路徑錨文本包分別為:

定義5(擴展鏈接路徑錨文本) 將網頁v的標題作為新的元素添加到集合Au,v中，若Au,v中已存在該元素，則相應權重加一，否則，將其加入集合，并賦予權重 1。則 u到 v1、v2、v3的擴展鏈接路徑錨文本分別為:

定義 6(擴展鏈接路徑錨文本包) 在網絡構成的有向圖中，u為源網頁，將網頁v的擴展鏈接路徑錨文本中各元素的權重進行標準化，且按照權重降序排序，用EAu,v表示，且標準化公式如下:

其中，f(a ∈Au,vi)是元素a在Au,vi中的權重，則u到v1、v2、v3的擴展鏈接路徑錨文本包分別為:

定義7(h-可達網頁集) 給定源網頁u，從 u根據網頁中的超鏈接進行h層的廣度優先遍歷爬蟲，得到的網頁URL集合，稱為網頁u的h-可達網頁集，用h-URLs(u)表示。

URL屬性求解問題描述:給定網頁u、u的h-可達網頁集 h-URLs(u)以及結構化數據表 R中的列 c、行 r，計算是否存在 url∈h-URLs(u)，使得 URL(r(c))=url，其中，URL(r(c))表示第r行第c列的元素對應的實際URL值。

3 基于鏈接路徑搜索的URL屬性集成方法

URL屬性集成方法基本思想:已知源網頁u、結構化數據表 R中的已選列 c。首先得到 h-URLs(u)，其中，v∈h-URLs(u)。利用EAu,v和c列中元素尋找v的最終匹配，最后將u的h-可達網頁集的URL集成到R中。

IULP算法具體描述如下:

其中，第1步是得到源網頁u的h-可達網頁集；第2步～第21步是對這些網頁進行循環操作。在循環中，第 3步是得到 u到 v的 K個最短路徑 PK，第 4步得到擴展鏈接路徑錨文本包 EAu,v，第 6步～第 21步是尋找 v與 r最終匹配的過程，當算法中2個集合的元素相同時，即找到匹配，并將此時v的url插入到第rn行的URL屬性列中。

分析填充結構化數據庫算法的時間性能，假設可達網頁集總數為N，擴展鏈接路徑錨文本包的元素個數為m，結構化數據表的行數為k。所以，在不考慮匹配值計算的前提下，其最壞的時間復雜度是O(Nmk）。經分析，在擴展鏈接路徑錨文本包中，元素排名越靠前，找到最終匹配的概率越大，且當元素排名超過4時就很少有正確的匹配，因此，實際中最壞的情況很少出現。

4 實驗結果與分析

4.1 數據集介紹

本文實驗采用2個數據集。第1個數據集是計算機研究生院教師的個人網頁。它是將在全美排名前25(根據US News 2010獲得)的計算機研究生院的網站首頁作為源網頁，并通過4層的廣度優先遍歷爬蟲獲得，統計總數為106、974。然后利用啟發式和主頁查找算法進行篩選，最終得到1129個教師個人網頁。本數據集采用的數據庫是DBLP。

DBLP是計算機領域科學文獻的數據庫。其數據是從“http://www.informatik.uni-trier.de/～ley/db/indices/a-tree/prolific/index.html”網站獲得，并對其進行分析處理。

第 2個數據集是電影的官方網頁。它是將“http://www.movieweb.com/”和“http://trailers.apple.com”分別作為源網頁進行廣度優先遍歷的爬蟲，直到爬蟲停止為止，共得到 98397個網頁，然后采用啟發式和主頁查找算法進行篩選得到官方的電影網頁，共301個。本文數據集采用的數據庫是IMDB。

IMDB是電影方面的權威數據庫。其數據是從“ftp://ftp.funet.fi/pub/mirrors/ftp.imdb.com/pub/”網站上下載“aka-titles.list”文件獲得。

4.2 實驗結果統計

為驗證本文提出的IULP算法的有效性，表1將文獻[11]提到的W2DR算法和本文方法做對比，并采用準確率、召回率和F值作為算法的評價指標。其中，準確率:P=算法匹配到的正確的網頁數/所有匹配到的網頁數；召回率:R=算法匹配到的正確的網頁數/所有應該匹配到的網頁數；F值:F=2× P×R/(P+R)，且設定2個實驗中 K的值均為10。另外，為了更好地測試算法的性能，對25個研究生院網站分開實驗，并將統計結果按照召回率的降序排序，Top7為召回率排名在前 7的平均值，Middle15為排名在中間的15個結果的平均值，Mean為所有結果的平均值，單列出來的是結果最差的3個，以便對算法進行分析和改進。

表1 算法性能比較1 (%)

對表1的結果分析后發現，本文算法在保證較高準確率的同時，實驗的召回率也有所提高，且平均F值提高了13.91%。

對于 UPENN和 UMASS，部分網頁的錨文本中沒有教師姓名，如UPENN網站中個人網頁的錨文本是“Web page”，而UCLA在未結合標題屬性前，部分教師的鏈接路徑錨文本包中存在他人姓名且排名靠前，均導致召回率較低，在結合網頁標題后，情況得到改善。

為了進一步驗證算法的性能，采用官方的電影網站數據集做實驗。表 2是將 2種方法在 Apple和Movieweb網站上進行實驗的結果。

表2 算法性能比較2 (%)

由表 2可知，與 W2DR算法對比，本文算法在這 2個網站的 F值分別提高了 3.27%和 8.15%。而Apple網站的召回率仍然較低，主要是因為其網站中很多電影網頁的標題是電影名字的縮寫，所以會影響本文算法的實驗效果。

5 結束語

本文將錨文本和網頁標題信息結合，設計一種基于鏈接路徑包的 URL屬性集成方法。通過對比實驗發現，IULP在URL屬性集成性能上優于W2DR算法。該工作有效地構建了半結構化數據和結構化數據的橋梁，為 Web信息抽取和信息檢索等研究奠定了基礎。下一步將結合信息抽取技術，將網頁中的其他重要信息集成到結構化數據庫中，進一步豐富數據庫的內容。

[1]Xi Wensi, Edward F, Roy T, et al.Machine Learning Approach for Homepage Fnding Task[C]//Proc.of the 9th International Symposium on String Processing and Information Retrieval.London, UK:Springer-Verlag,2002.

[2]Craswell N, Hawking D.Overview of the Trec-2002 Web Track[C]//Proc.of the 11th Text Retrieval Conference.Gaithersburg, USA:[s.n.], 2003.

[3]黃豫清, 戚廣志, 張福炎.從Web文檔中構造半結構化信息的抽取器[J].軟件學報, 2000, 11(11):73-78.

[4]Zhai Yanhong, Liu Bing.Structured Data Extraction from the Web Based on Partial Tree Alignment[J].IEEE Transactions on Knowledge and Data Engineering, 2006,18(12):1614-1628.

[5]趙 洪, 肖 洪, 薛德軍, 等.Web表格信息抽取研究綜述[J].現代圖書情報技術, 2008, (3):24-31.

[6]Craswell N, Hawking D, Robertson S.Effective Site Finding Using Link Anchor Information[C]//Proc.of SIGIR’01.New York, USA:ACM Press, 2001.

[7]周 博, 劉奕群, 張 敏, 等.錨文本檢索有效性分析[J].軟件學報, 2011, 22(8):1714-1724.

[8]王鐘斐, 王 彪.基于錨文本相似度的 PageRank改進算法[J].計算機工程, 2010, 36(24):258-260.

[9]Kraft R, Zien J.Mining Anchor Text for Query Refinement[C]//Proc.of the 13th International Conference on World Wide Web.New York, USA:ACM Press, 2004.

[10]Metzler D, Novak J, Cui Hang, et al.Building Enriched Document Representations Using Aggregated Anchor Text[C]//Proc.of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval.New York, USA:ACM Press, 2009.

[11]Weninger T, Fumarola F, Han Jiawei.Mapping Web Pages to Database Records via Link Paths[C]//Proc.of the 19th ACM International Conference on Information and Knowledge Management.New York, USA:ACM Press,2010.

[12]Yen J.Finding the K Shortest Loopless Paths in a Network[J].Management Science, 1971, 17(1):712-716.