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

馬艷紅，胡學(xué)鋼，吳共慶

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 230009)

1 概述

用于處理結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)庫(kù)，在海量信息的檢索和數(shù)據(jù)挖掘方面已顯現(xiàn)出諸多的局限性。而網(wǎng)頁(yè)中的半結(jié)構(gòu)化數(shù)據(jù)已成為人們獲取、傳播和交換信息的重要途徑。如何充分利用半結(jié)構(gòu)化數(shù)據(jù)資源，并將其同傳統(tǒng)的結(jié)構(gòu)化數(shù)據(jù)集成在一起，成為一個(gè)重要的研究課題。

例如，傳統(tǒng)數(shù)據(jù)庫(kù)中的數(shù)據(jù)結(jié)構(gòu)相對(duì)固定，添加新的屬性列往往需要大量的人力和時(shí)間。為解決該問(wèn)題，一種可行的方案是對(duì)數(shù)據(jù)庫(kù)中每個(gè)數(shù)據(jù)的相關(guān)網(wǎng)頁(yè)進(jìn)行信息抽取，并將新的屬性填充到數(shù)據(jù)庫(kù)中。然而，由于真實(shí)數(shù)據(jù)庫(kù)信息量龐大，該方法的難點(diǎn)在于如何自動(dòng)、高效地找到這些數(shù)據(jù)的相關(guān)網(wǎng)頁(yè)的URL，并得到這些網(wǎng)頁(yè)與數(shù)據(jù)庫(kù)的映射，為后期的信息抽取和數(shù)據(jù)挖掘等操作提供準(zhǔn)確的信息來(lái)源。

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

2 相關(guān)概念和問(wèn)題描述

定義1(鏈接路徑) 若將網(wǎng)絡(luò)用有向圖表示，即每個(gè)網(wǎng)頁(yè)用一個(gè)頂點(diǎn)表示，每個(gè)超鏈接用一條有向邊表示，且每個(gè)網(wǎng)頁(yè)可由一個(gè)URL唯一確定，則從網(wǎng)頁(yè)u通過(guò)超鏈接到達(dá)網(wǎng)頁(yè)v的途中經(jīng)過(guò)的所有頂點(diǎn)構(gòu)成的集合為u到v的鏈接路徑。

圖1為網(wǎng)絡(luò)的有向圖表示示例，方框表示各個(gè)網(wǎng)頁(yè)，箭頭上為網(wǎng)頁(yè)間的錨文本，括號(hào)內(nèi)是目標(biāo)網(wǎng)頁(yè)的標(biāo)題。則從源網(wǎng)頁(yè)u到目標(biāo)網(wǎng)頁(yè)v1的一條鏈接路徑為:{u,x,x2,x3,v1}。

圖1 網(wǎng)絡(luò)的有向圖表示示例

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

定義3 K個(gè)最短路徑PK:表示從u到v的K個(gè)最短無(wú)環(huán)路徑。用集合PK={p1,p2,…,pk}?P表示，且規(guī)定如下[12]:

其中，K是正整數(shù)；c表示權(quán)重，為方便起見(jiàn)，規(guī)定每條有向邊的權(quán)重為1，因此，若路徑p共經(jīng)過(guò)s條有向邊，則 ()cp s= 。

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

由圖1可知，網(wǎng)頁(yè)u到v1、v2、v3的鏈接路徑錨文本包分別為:

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

定義 6(擴(kuò)展鏈接路徑錨文本包) 在網(wǎng)絡(luò)構(gòu)成的有向圖中，u為源網(wǎng)頁(yè)，將網(wǎng)頁(yè)v的擴(kuò)展鏈接路徑錨文本中各元素的權(quán)重進(jìn)行標(biāo)準(zhǔn)化，且按照權(quán)重降序排序，用EAu,v表示，且標(biāo)準(zhǔn)化公式如下:

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

定義7(h-可達(dá)網(wǎng)頁(yè)集) 給定源網(wǎng)頁(yè)u，從 u根據(jù)網(wǎng)頁(yè)中的超鏈接進(jìn)行h層的廣度優(yōu)先遍歷爬蟲(chóng)，得到的網(wǎng)頁(yè)URL集合，稱為網(wǎng)頁(yè)u的h-可達(dá)網(wǎng)頁(yè)集，用h-URLs(u)表示。

URL屬性求解問(wèn)題描述:給定網(wǎng)頁(yè)u、u的h-可達(dá)網(wǎng)頁(yè)集 h-URLs(u)以及結(jié)構(gòu)化數(shù)據(jù)表 R中的列 c、行 r，計(jì)算是否存在 url∈h-URLs(u)，使得 URL(r(c))=url，其中，URL(r(c))表示第r行第c列的元素對(duì)應(yīng)的實(shí)際URL值。

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

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

IULP算法具體描述如下:

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

分析填充結(jié)構(gòu)化數(shù)據(jù)庫(kù)算法的時(shí)間性能，假設(shè)可達(dá)網(wǎng)頁(yè)集總數(shù)為N，擴(kuò)展鏈接路徑錨文本包的元素個(gè)數(shù)為m，結(jié)構(gòu)化數(shù)據(jù)表的行數(shù)為k。所以，在不考慮匹配值計(jì)算的前提下，其最壞的時(shí)間復(fù)雜度是O(Nmk）。經(jīng)分析，在擴(kuò)展鏈接路徑錨文本包中，元素排名越靠前，找到最終匹配的概率越大，且當(dāng)元素排名超過(guò)4時(shí)就很少有正確的匹配，因此，實(shí)際中最壞的情況很少出現(xiàn)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)集介紹

本文實(shí)驗(yàn)采用2個(gè)數(shù)據(jù)集。第1個(gè)數(shù)據(jù)集是計(jì)算機(jī)研究生院教師的個(gè)人網(wǎng)頁(yè)。它是將在全美排名前25(根據(jù)US News 2010獲得)的計(jì)算機(jī)研究生院的網(wǎng)站首頁(yè)作為源網(wǎng)頁(yè)，并通過(guò)4層的廣度優(yōu)先遍歷爬蟲(chóng)獲得，統(tǒng)計(jì)總數(shù)為106、974。然后利用啟發(fā)式和主頁(yè)查找算法進(jìn)行篩選，最終得到1129個(gè)教師個(gè)人網(wǎng)頁(yè)。本數(shù)據(jù)集采用的數(shù)據(jù)庫(kù)是DBLP。

DBLP是計(jì)算機(jī)領(lǐng)域科學(xué)文獻(xiàn)的數(shù)據(jù)庫(kù)。其數(shù)據(jù)是從“http://www.informatik.uni-trier.de/～ley/db/indices/a-tree/prolific/index.html”網(wǎng)站獲得，并對(duì)其進(jìn)行分析處理。

第 2個(gè)數(shù)據(jù)集是電影的官方網(wǎng)頁(yè)。它是將“http://www.movieweb.com/”和“http://trailers.apple.com”分別作為源網(wǎng)頁(yè)進(jìn)行廣度優(yōu)先遍歷的爬蟲(chóng)，直到爬蟲(chóng)停止為止，共得到 98397個(gè)網(wǎng)頁(yè)，然后采用啟發(fā)式和主頁(yè)查找算法進(jìn)行篩選得到官方的電影網(wǎng)頁(yè)，共301個(gè)。本文數(shù)據(jù)集采用的數(shù)據(jù)庫(kù)是IMDB。

IMDB是電影方面的權(quán)威數(shù)據(jù)庫(kù)。其數(shù)據(jù)是從“ftp://ftp.funet.fi/pub/mirrors/ftp.imdb.com/pub/”網(wǎng)站上下載“aka-titles.list”文件獲得。

4.2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

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

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

對(duì)表1的結(jié)果分析后發(fā)現(xiàn)，本文算法在保證較高準(zhǔn)確率的同時(shí)，實(shí)驗(yàn)的召回率也有所提高，且平均F值提高了13.91%。

對(duì)于 UPENN和 UMASS，部分網(wǎng)頁(yè)的錨文本中沒(méi)有教師姓名，如UPENN網(wǎng)站中個(gè)人網(wǎng)頁(yè)的錨文本是“Web page”，而UCLA在未結(jié)合標(biāo)題屬性前，部分教師的鏈接路徑錨文本包中存在他人姓名且排名靠前，均導(dǎo)致召回率較低，在結(jié)合網(wǎng)頁(yè)標(biāo)題后，情況得到改善。

為了進(jìn)一步驗(yàn)證算法的性能，采用官方的電影網(wǎng)站數(shù)據(jù)集做實(shí)驗(yàn)。表 2是將 2種方法在 Apple和Movieweb網(wǎng)站上進(jìn)行實(shí)驗(yàn)的結(jié)果。

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

由表 2可知，與 W2DR算法對(duì)比，本文算法在這 2個(gè)網(wǎng)站的 F值分別提高了 3.27%和 8.15%。而Apple網(wǎng)站的召回率仍然較低，主要是因?yàn)槠渚W(wǎng)站中很多電影網(wǎng)頁(yè)的標(biāo)題是電影名字的縮寫(xiě)，所以會(huì)影響本文算法的實(shí)驗(yàn)效果。

5 結(jié)束語(yǔ)

本文將錨文本和網(wǎng)頁(yè)標(biāo)題信息結(jié)合，設(shè)計(jì)一種基于鏈接路徑包的 URL屬性集成方法。通過(guò)對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，IULP在URL屬性集成性能上優(yōu)于W2DR算法。該工作有效地構(gòu)建了半結(jié)構(gòu)化數(shù)據(jù)和結(jié)構(gòu)化數(shù)據(jù)的橋梁，為 Web信息抽取和信息檢索等研究奠定了基礎(chǔ)。下一步將結(jié)合信息抽取技術(shù)，將網(wǎng)頁(yè)中的其他重要信息集成到結(jié)構(gòu)化數(shù)據(jù)庫(kù)中，進(jìn)一步豐富數(shù)據(jù)庫(kù)的內(nèi)容。

[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文檔中構(gòu)造半結(jié)構(gòu)化信息的抽取器[J].軟件學(xué)報(bào), 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].現(xiàn)代圖書(shū)情報(bào)技術(shù), 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].軟件學(xué)報(bào), 2011, 22(8):1714-1724.

[8]王鐘斐, 王 彪.基于錨文本相似度的 PageRank改進(jìn)算法[J].計(jì)算機(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.