基于链接路径搜索的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.