第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 基于非内容信息的网络关键资源有效定位 刘奕群，张敏，马少平 (清华大学智能技术与系统国家重点实验室，北京100084) 摘要：网络信息的爆炸式增长，使得当前任何搜索引擎都只可能索引到wb上一小部分数据，而其中又充斥着大 量的低质量信息.如何在用户查询无关的条件下找到Wb上高质量的关键资源，是Web信息检索面临的挑战.基于 大规模网页统计的方法发现，多种网页非内容特征可以用于关键资源页面的定位，利用决策树学习方法对这些特征 进行综合，即可以实现用户查询无关的关键资源页面定位.在文本信息检索会议(T℉EC)标准评测平台上进行的超 过19G文本数据规模的实验表明，这种定位方法能够利用20%左右的页面覆盖超过70%的Wb关键信息；在仅为 全部页面24%的关键资源集合上的检索结果，比在整个页面集合上的检索有超过60%的性能提高.这说明使用较少 的索引量获取较高的检索性能是完全可能的 关键词：网络信息检索；关键资源页面：主题过滤：机器学习 中图分类号：TP181,TP391.3文献标识码：A文章编号：16734785(2007)01-004508 Web key resource page selection based on non-content information LIU Yi-qun,ZHAN G Min,MA Shao-ping (State Key Lab of Intelligent Technology and Systems,Tsinghua University,Beijing 100084,China) Abstract:Information growth makes it impossible for search engines to crawl and index all pages on the Web.Meanwhile indexed page set is filled with low quality information and spam.It is quite a challenge to select high quality Web pages(key resource pages)query-independently.With analysis in nomcontent fea- tures of key resources,a pre-selection method was introduced in topic distillation research.A decision tree was constructed to locate key resource pages using query-independent nomcontent features including inde- gree,document length,URL-type and two novel proposed features involving site's self-link structure a- nalysis.Although the result page set contained only about 20 pages of the whole collection,it covered more than 70%of key resources.Furthermore,information retrieval on this page set made more than 60% improvement with respect to that on all pages.It shows an effective way to get better performance in topic distillation with a smaller data set. Key words:web information retrieval;key resource page;topic distillation;link structure analysis 当前网络信息检索技术面临的最大挑战来自网静态页面数目也将超过200亿.容易想象，在未来很 络信息环境本身.由于网络数据的大量膨胀，目前己 长的时间里，随着网络技术在更多国家中得到发展」 经没有任何搜索引擎能够索引到Web上的所有网 Web数据将继续其增长趋势，这对数据收集、索引 页.根据Sullivan等的评测)，2003年2月时， 的建立更新及检索都带来几乎无法逾越的障碍」 Google是世界上索引量最大的搜索引擎（索引到33 然而，Web信息的一大特点是其内容质量参差 亿Web页面).但即使是按照加州大学伯克利分校 不齐.Google公司的Henzinger等人指出1：大量 How Much Info计划II的保守估计，当时的Web仅 冗余信息、低质量信息与Web中的有用信息鱼龙混 杂，给现代搜索引擎的发展带来了极大的问题.一方 收稿日期：200604-23. 面，由于网络数据的极大丰富，无法索引到所有的有 基金项目：国家重点基础研究(973)资助项目(2004CB318108);国家 自然科学基金资助项目(60223004,60321002,60303005， 用页面，另一方面，占用宝贵收集时间和存储空间的 60503064):教育部科学技术研究重点资助项目(104236). 数据却有许多是低质量的.因此Henzinger等人将 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 基于非内容信息的网络关键资源有效定位 刘奕群 ,张 敏 ,马少平 (清华大学 智能技术与系统国家重点实验室 ,北京 100084) 摘 要 :网络信息的爆炸式增长 ,使得当前任何搜索引擎都只可能索引到 Web 上一小部分数据 ,而其中又充斥着大 量的低质量信息. 如何在用户查询无关的条件下找到 Web 上高质量的关键资源 ,是 Web 信息检索面临的挑战. 基于 大规模网页统计的方法发现 ,多种网页非内容特征可以用于关键资源页面的定位 ,利用决策树学习方法对这些特征 进行综合 ,即可以实现用户查询无关的关键资源页面定位. 在文本信息检索会议( TREC) 标准评测平台上进行的超 过 19 G文本数据规模的实验表明 ,这种定位方法能够利用 20 %左右的页面覆盖超过 70 %的 Web 关键信息 ;在仅为 全部页面 24 %的关键资源集合上的检索结果 ,比在整个页面集合上的检索有超过 60 %的性能提高. 这说明使用较少 的索引量获取较高的检索性能是完全可能的. 关键词 :网络信息检索 ;关键资源页面 ;主题过滤 ;机器学习 中图分类号 : TP181 ,TP391. 3 文献标识码 :A 文章编号 :167324785 (2007) 0120045208 Web key resource page selection based on non2content information L IU Yi2qun ,ZHAN G Min ,MA Shao2ping (State Key Lab of Intelligent Technology and Systems , Tsinghua University , Beijing 100084 , China) Abstract :Information growt h makes it impo ssible for search engines to crawl and index all pages on t he Web. Meanwhile indexed page set is filled with low quality information and spam. It is quite a challenge to select high quality Web pages (key resource pages) query2independently. Wit h analysis in non2content fea2 t ures of key resources , a pre2selection met hod was introduced in topic distillation research. A decision tree was constructed to locate key resource pages using query2independent non2content feat ures including in2de2 gree , document lengt h , URL2type and two novel proposed features involving site’s self2link struct ure a2 nalysis. Although t he result page set contained only about 20 % pages of the whole collection , it covered more t han 70 % of key resources. Furt hermore , information retrieval on this page set made more t han 60 % improvement with respect to t hat on all pages. It shows an effective way to get better performance in topic distillation wit h a smaller data set. Keywords :web information retrieval ; key resource page ; topic distillation ; link struct ure analysis 收稿日期 :2006204223. 基金项目 :国家重点基础研究(973) 资助项目(2004CB318108) ;国家 自然科学基金资助项目(60223004 , 60321002 , 60303005 , 60503064) ;教育部科学技术研究重点资助项目(104236) . 当前网络信息检索技术面临的最大挑战来自网 络信息环境本身. 由于网络数据的大量膨胀 ,目前已 经没有任何搜索引擎能够索引到 Web 上的所有网 页. 根 据 Sullivan 等 的 评 测[1 ] , 2003 年 2 月 时 , Google 是世界上索引量最大的搜索引擎(索引到 33 亿 Web 页面) . 但即使是按照加州大学伯克利分校 How Much Info 计划[2 ]的保守估计 ,当时的 Web 仅 静态页面数目也将超过 200 亿. 容易想象 ,在未来很 长的时间里 ,随着网络技术在更多国家中得到发展 , Web 数据将继续其增长趋势 ,这对数据收集、索引 的建立更新及检索都带来几乎无法逾越的障碍. 然而 ,Web 信息的一大特点是其内容质量参差 不齐. Google 公司的 Henzinger 等人指出[3 ] :大量 冗余信息、低质量信息与 Web 中的有用信息鱼龙混 杂 ,给现代搜索引擎的发展带来了极大的问题. 一方 面 ,由于网络数据的极大丰富 ,无法索引到所有的有 用页面 ;另一方面 ,占用宝贵收集时间和存储空间的 数据却有许多是低质量的. 因此 Henzinger 等人将
·46 智能系统学报 第2卷 寻找主题无关的判断页面质量的方法作为搜索引擎 根据TREC网络信息检索部分的较权威的定 技术发展的最大挑战之一 义51，关键资源页面应当是某个关键站点的入口页 己有的网络信息检索研究，对用户笼统概念上 面，此站点需要提供关于某个主题的可靠信息 的“高质量页面”给出了较科学明确的定义能够为 需要特别指出的是，这里所提到的入口页面不 某个主题提供高质量信息或者链接的少部分页面被 一定是通常意义上的“主页”，它可能是大规模站点 称为这个主题的关键资源页面，而寻找关键资源页 的接入页面，也有可能是某个子站点或者某一类页 面的任务称为主题过滤(topic distillation).反映国 面集合的接入页面.如http:/www.nida.nih.govW 际信息检索研究最高水平的SIGIR(International drugpages/marijuana.html是美国药物滥用治疗研 ACM SIGIR Conference on Research and Develop- 究所(NDA)关于大麻方面信息的关键资源页面， ment in Information Retrieval)会议上.，主题过滤技 但它并不是一个通常意义上的“主页”，这个页面只 术无论从论文数目还是质量来看，一直都是近年讨 是为用户提供一个NDA站点内部相关信息页面 论的热点.作为信息检索领域权威评测会议的 的访问索引」 TREC,也从2002年开始，在其Web信息检索部 从定义中可以看出，关键资源页面之所以“关 分，使用主题过滤任务代替了传统的相关资源查找 键”，是因为它提供给用户一个关于某个主题的可靠 任务1.查找关键资源，是当前网络信息检索的发 信息的入口.用户通过关键资源页面，可以比较快捷 展热点，也已经获得了一些卓有成效的理论研究和 的查找到所需要的信息.同时，某个主题的关键资源 实验结果4，！但总的来说，主题过滤研究的发展还 页面数要比其相关页面数少得多（相关页面动辄成 停留在一个比较低的水平上，作为评价标准的前10 百上千，而关键资源页面往往只有几个到十几个)， 位结果检索精度(Precision at 10 documents, 这也方便用户将注意力集中到少数一些与自己的查 P@10)一直在20%左右徘徊4.s),而表现网络数据 询主题最贴切的页面上 不同于普通数据的许多非文本内容特征也没有得到 关于所有可能的主题的关键资源页面的总和 充分的考察 就构成了网络环境中的关键资源页面集合.可见这 文中对关键资源页面的若干非内容特征进行了 个页面集合只占网络页面全集的小部分，其余大部 考察，这些特征包括已有一定研究9·山，但尚未对 分页面则是信息量较少的页面，以及包含错误和冗 关键资源页面进行专门考察的UL分级特征、网 余信息的页面这说明，定位关键资源页面集合，可 页文本长度特征、入链接个数特征，也包括了根据关 以起到在网络信息环境中去粗取精的作用.这也就 键资源定义提出的新特征：站点自身出链接特征.关 是文中关注关键资源页面判定，希望能够通过非内 键资源页面在这些特征上的分布与普通网络页面有 容特征进行用户查询主题无关的定位关键资源页面 着明显的差异，从而使查询主题无关的判定关键资 的原因 源页面成为可能.综合利用非内容特征进行决策树 1.2Web页面非内容特征研究的已有成果 学习，使得人们能够从大规模测试页面全集中提取 文中考察Web页面非内容特征的目的，是试图 出一个关键资源页面集合.在关键资源页面集合上 利用这些特征进行主题无关的关键资源定位.尽管 进行的检索证明：可以使用较少的页面索引量获得 对于站点主页非内容特征的考察，已经有一定的基 较高的检索质量 础，但是站点主页与关键资源页面的巨大差异，使文 中的工作很少能够借鉴一些现有的研究结论.对于 1相关研究工作概述 关键资源页面非内容特征的考察，只能是从头起步 1.1主题过滤与关键资源页面 当前关于网页非内容特征的研究成果，大多是 主题过滤(topic distillation)技术以查找关键资 在主页查找工作的推动下得到的.主页查找即站点 源页面为目的，与查找相关页面的传统检索技术不 查找或导航类查找，按照Broder的统计]，此类查 同，它强调检索结果页面应当是用户获取信息的重 找在网络搜索引擎的日常查询中占有约20%的份 要途径而非唯一来源.用户可以通过访问结果页面 额.由于主页有明显的非内容特征如UL特征、链接 以及与其相链接的其他页面来获得完整的信息，而 特征等，在主页查找中使用这些特征也成为了必然 不是从有限的页面内资源中获取知识.主题过滤技 链接特征一直是人们考察非内容特征的重点， 术的提出，是为了用更有限的页面提供给用户更多 经典的链接分析方法，如PageRank和HITS算法，分 的关键信息 别作为Google和IBM CLEVER的核心算法，在促进网 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
寻找主题无关的判断页面质量的方法作为搜索引擎 技术发展的最大挑战之一. 已有的网络信息检索研究 ,对用户笼统概念上 的“高质量页面”给出了较科学明确的定义. 能够为 某个主题提供高质量信息或者链接的少部分页面被 称为这个主题的关键资源页面 ,而寻找关键资源页 面的任务称为主题过滤 (topic distillation) . 反映国 际信息检索研究最高水平的 SIGIR ( International ACM SIGIR Conference on Research and Develop2 ment in Information Retrieval) 会议上 ,主题过滤技 术无论从论文数目还是质量来看 ,一直都是近年讨 论的热点. 作为信息检索领域权威评测会议的 TREC ,也从 2002 年开始 ,在其 Web 信息检索部 分 ,使用主题过滤任务代替了传统的相关资源查找 任务[ 4 - 6 ] . 查找关键资源 ,是当前网络信息检索的发 展热点 ,也已经获得了一些卓有成效的理论研究和 实验结果[4 - 8 ] . 但总的来说 ,主题过滤研究的发展还 停留在一个比较低的水平上 ,作为评价标准的前 10 位 结 果 检 索 精 度 ( Precision at 10 documents , P @10) 一直在 20 %左右徘徊[4 - 5 ] ,而表现网络数据 不同于普通数据的许多非文本内容特征也没有得到 充分的考察. 文中对关键资源页面的若干非内容特征进行了 考察 ,这些特征包括已有一定研究[ 9 - 11 ] ,但尚未对 关键资源页面进行专门考察的 URL 分级特征、网 页文本长度特征、入链接个数特征 ,也包括了根据关 键资源定义提出的新特征 :站点自身出链接特征. 关 键资源页面在这些特征上的分布与普通网络页面有 着明显的差异 ,从而使查询主题无关的判定关键资 源页面成为可能. 综合利用非内容特征进行决策树 学习 ,使得人们能够从大规模测试页面全集中提取 出一个关键资源页面集合. 在关键资源页面集合上 进行的检索证明 :可以使用较少的页面索引量获得 较高的检索质量. 1 相关研究工作概述 1. 1 主题过滤与关键资源页面 主题过滤(topic distillation) 技术以查找关键资 源页面为目的 ,与查找相关页面的传统检索技术不 同 ,它强调检索结果页面应当是用户获取信息的重 要途径而非唯一来源. 用户可以通过访问结果页面 以及与其相链接的其他页面来获得完整的信息 ,而 不是从有限的页面内资源中获取知识. 主题过滤技 术的提出 ,是为了用更有限的页面提供给用户更多 的关键信息. 根据 TREC 网络信息检索部分的较权威的定 义[5 ] ,关键资源页面应当是某个关键站点的入口页 面 ,此站点需要提供关于某个主题的可靠信息. 需要特别指出的是 ,这里所提到的入口页面不 一定是通常意义上的“主页”,它可能是大规模站点 的接入页面 ,也有可能是某个子站点或者某一类页 面集合的接入页面. 如 http :/ / www. nida. nih. gov/ drugpages/ marijuana. html 是美国药物滥用治疗研 究所(NIDA) 关于大麻方面信息的关键资源页面 , 但它并不是一个通常意义上的“主页”,这个页面只 是为用户提供一个 NIDA 站点内部相关信息页面 的访问索引. 从定义中可以看出 ,关键资源页面之所以“关 键”,是因为它提供给用户一个关于某个主题的可靠 信息的入口. 用户通过关键资源页面 ,可以比较快捷 的查找到所需要的信息. 同时 ,某个主题的关键资源 页面数要比其相关页面数少得多 (相关页面动辄成 百上千 ,而关键资源页面往往只有几个到十几个) , 这也方便用户将注意力集中到少数一些与自己的查 询主题最贴切的页面上. 关于所有可能的主题的关键资源页面的总和 , 就构成了网络环境中的关键资源页面集合. 可见这 个页面集合只占网络页面全集的小部分 ,其余大部 分页面则是信息量较少的页面 ,以及包含错误和冗 余信息的页面. 这说明 ,定位关键资源页面集合 ,可 以起到在网络信息环境中去粗取精的作用. 这也就 是文中关注关键资源页面判定 ,希望能够通过非内 容特征进行用户查询主题无关的定位关键资源页面 的原因. 1. 2 Web 页面非内容特征研究的已有成果 文中考察 Web 页面非内容特征的目的 ,是试图 利用这些特征进行主题无关的关键资源定位. 尽管 对于站点主页非内容特征的考察 ,已经有一定的基 础 ,但是站点主页与关键资源页面的巨大差异 ,使文 中的工作很少能够借鉴一些现有的研究结论. 对于 关键资源页面非内容特征的考察 ,只能是从头起步. 当前关于网页非内容特征的研究成果 ,大多是 在主页查找工作的推动下得到的. 主页查找即站点 查找或导航类查找 ,按照 Broder 的统计[12 ] ,此类查 找在网络搜索引擎的日常查询中占有约 20 %的份 额.由于主页有明显的非内容特征如 URL 特征、链接 特征等 ,在主页查找中使用这些特征也成为了必然. 链接特征一直是人们考察非内容特征的重点 , 经典的链接分析方法 ,如 PageRank 和 HITS 算法 ,分 别作为 Google 和 IBM CLEVER 的核心算法 ,在促进网 · 64 · 智 能 系 统 学 报 第 2 卷
第1期 刘奕群，等：基于非内容信息的网络关键资源有效定位创 ·47· 络信息检索工具的发展方面取得了极大的成功， 引用的度量 除链接特征之外，非内容特征还有多种形式： 3)URL分级特征是表示页面URL种类的一 Westerveld等人在2000年提出了URL分级特 个非内容特征，由Kraaij等人在文献[l1]中提出 征，，这种特征比较之前通常使用的URL长度特 页面的URL划分为ROOT,SUBROOT,PATH 征更为合理，其核心思想是将页面的UL分为 FLE4类，其中ROOT类的UL只包括域名，而从 Root,Subroot,Path和File4级.由于统计结果发 ROOT类到FLE类其URL中的“/"逐渐增多 现，绝大部分的站点主页不属于Fle类，因此对非 文中着重考察的是这些特征在网络页面全集与 F1le类页面进行加权就可以提升主页查找的性能， Westerveld与其同事Kraaij等在次年总结了包括 关键资源集合上的差异，经过对.GOV和关键资源 URL分类特征在内的多种非内容特征，并在SIGIR 训练集合的统计，这种差异是确实存在的，如表1和 2001上发表：而Craswell等人则于2003年对各 表2所示 类主题无关的非内容特征包括页面长度特征、入度 表1.①V与关键资源训练集合在非内容特征值的分布差异 (入链接个数)特征、URL分级特征和PageRank数 Table 1 Differences bet ween GOV corpus and key resource 值特征在主页查找中的应用进行了系统总结，，他 set in several nomcontent features % 指出：入度特征和URL分级特征对于主页查找是 特征 GOV 关键资源训练集 有效的，而PageRank数值和文档长度特征的功能 则不太明显 页面长度≤ 16.08 1.17 关键资源页面与站点主页有一定的关联，但二 1000 入度习0 10.78 51.03 者发挥的功能具有很大的差异.一部分关键资源页 URL分级≠ 面是站点主页，但关键资源页面又远不是所在站点 12.61 57.27 FLE 的主页.这就决定了对关键资源页面非内容特征的 考察，一方面要对站点主页查找中常用的非内容特 表2.G0V与关键资源训练集合的非内容特征平均值差异 征针对关键资源页面进行分析和筛选，另一方面则 Table 2 Differences bet ween.GOV corpus and key resource 需要发现关键资源页面特有的非内容特征 set noncontent feature in mean values 2关键资源页面的非内容特征分析 特征 GOV 关键资源训练集 文中采用基于大规模网页数据统计的方法考察 页面长度 7037.43 9008.02 入度 9.94 153.12 关键资源页面的非内容特征，以便实现主题无关的 URL分级 / / 关键资源页面判定，从而将关键资源页面从普通页 面中区别开来.将要讨论的非内容特征除了上文提 由统计数据可以看出： 到的一些常用特征外，还包括根据关键资源的特性， 1)关键资源训练集的平均页面长度与普通页面 提出的一种新特征站点自身出链接特征 比较接近.但是表1的实验结果说明，2个页面集合 作为基于统计方法的基础，本节使用的大规模 语料库是.GOV网页数据库·，而用于统计关键资 上的页面长度分布还是有差异，主要表现在关键资 源页面特征的“关键资源训练集合”则是指在TREC 源页面是长度较短(1000词)页面的可能性很 2002主题过滤任务的标准答案基础上，用手工标出 小，这个特征有助于去除冗余页面 关键资源的方式加以筛选，而得到的符合关键资源 2)表2显示，关键资源页面的平均入度比普通 定义的页面 页面要大得多，这可以使用反映网页链接关系的内 2.1常用网页非内容特征在关键资源页面集合上 容推荐假设s](recommendation assumption)解释： 的考察 一个页面被其他页面所引用，反映这个页面的内容 常用于网络信息检索的网页非内容特征主要包 被其他页面的作者所推荐.拥有较多入度的页面，是 括：页面长度特征、入度特征和URL分级特征. 内容质量比较高的页面，它成为关键资源页面的可 1)页面长度是指经过过滤无用字符等预处理之 能性也就比较大 后的页面包含的单词数 3)根据表1的统计结果，FLE类型的网页在 2)入度特征是指某页面被多少个外部页面链接 GOV语料库中占了大多数：但在关键资源训练集 ·,G0V是由超过120万个网页、近20G数据组成的实验性网络语 中，FLE与非FLE类型的页面数基本相等，非 料库，它是由CSIRO(澳大利亚联邦工业研究组织)在2002年初基 于真实网络环境抓取到的.可以认为它是一个真实网络环境的采 FLE类型的页面反而更多一些.这说明关键资源 样，详细信息参见http:/es.csro.au/TRECWeb/govinfo.html 页面的URL更倾向属于非FLE类型 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
络信息检索工具的发展方面取得了极大的成功. 除链接特征之外 ,非内容特征还有多种形式 : Westerveld 等人在 2000 年提出了 URL 分级特 征[10 ] ,这种特征比较之前通常使用的 URL 长度特 征更为合理 ,其核心思想是将页面的 U RL 分为 Root , Subroot , Path 和 File4 级. 由于统计结果发 现 ,绝大部分的站点主页不属于 File 类 ,因此对非 File 类页面进行加权就可以提升主页查找的性能. Westerveld 与其同事 Kraaij 等在次年总结了包括 URL 分类特征在内的多种非内容特征 ,并在 SIGIR 2001 上发表[11 ] ;而 Craswell 等人则于 2003 年对各 类主题无关的非内容特征包括页面长度特征、入度 (入链接个数) 特征、U RL 分级特征和 PageRank 数 值特征在主页查找中的应用进行了系统总结[ 9 ] ,他 指出 :入度特征和 URL 分级特征对于主页查找是 有效的 ,而 PageRank 数值和文档长度特征的功能 则不太明显. 3 . GOV 是由超过 120 万个网页、近 20 G数据组成的实验性网络语 料库 ,它是由 CSIRO (澳大利亚联邦工业研究组织) 在 2002 年初基 于真实网络环境抓取到的. 可以认为它是一个真实网络环境的采 样 ,详细信息参见 http :/ / es. csiro. au/ TRECWeb/ govinfo. html 关键资源页面与站点主页有一定的关联 ,但二 者发挥的功能具有很大的差异. 一部分关键资源页 面是站点主页 ,但关键资源页面又远不是所在站点 的主页. 这就决定了对关键资源页面非内容特征的 考察 ,一方面要对站点主页查找中常用的非内容特 征针对关键资源页面进行分析和筛选 ,另一方面则 需要发现关键资源页面特有的非内容特征. 2 关键资源页面的非内容特征分析 文中采用基于大规模网页数据统计的方法考察 关键资源页面的非内容特征 ,以便实现主题无关的 关键资源页面判定 ,从而将关键资源页面从普通页 面中区别开来. 将要讨论的非内容特征除了上文提 到的一些常用特征外 ,还包括根据关键资源的特性 , 提出的一种新特征 ———站点自身出链接特征. 作为基于统计方法的基础 ,本节使用的大规模 语料库是. GOV 网页数据库3 ,而用于统计关键资 源页面特征的“关键资源训练集合”则是指在 TREC 2002 主题过滤任务的标准答案基础上 ,用手工标出 关键资源的方式加以筛选 ,而得到的符合关键资源 定义的页面. 2. 1 常用网页非内容特征在关键资源页面集合上 的考察 常用于网络信息检索的网页非内容特征主要包 括 :页面长度特征、入度特征和 U RL 分级特征. 1) 页面长度是指经过过滤无用字符等预处理之 后的页面包含的单词数. 2) 入度特征是指某页面被多少个外部页面链接 引用的度量. 3) URL 分级特征是表示页面 URL 种类的一 个非内容特征 ,由 Kraaij 等人在文献[ 11 ]中提出 , 页面的 URL 划分为 ROO T ,SUBROO T , PA T H , FIL E4 类 ,其中 ROO T 类的 U RL 只包括域名 ,而从 ROO T 类到 FIL E 类其 U RL 中的“/ ”逐渐增多. 文中着重考察的是这些特征在网络页面全集与 关键资源集合上的差异 ,经过对. GOV 和关键资源 训练集合的统计 ,这种差异是确实存在的 ,如表 1 和 表 2 所示. 表 1 . GOV与关键资源训练集合在非内容特征值的分布差异 Table 1 Differences between . GOV corpus and key resource set in several non2content features % 特征 . GOV 关键资源训练集 页面长度 ≤ 1 000 16. 08 1. 17 入度 ≥10 10. 78 51. 03 URL 分级 ≠ FIL E 12. 61 57. 27 表 2 . GOV与关键资源训练集合的非内容特征平均值差异 Table 2 Differences between . GOV corpus and key resource set non2content feature in mean values 特征 . GOV 关键资源训练集 页面长度 7 037. 43 9 008. 02 入度 9. 94 153. 12 URL 分级 / / 由统计数据可以看出 : 1) 关键资源训练集的平均页面长度与普通页面 比较接近. 但是表 1 的实验结果说明 ,2 个页面集合 上的页面长度分布还是有差异 ,主要表现在关键资 源页面是长度较短 ( ≤1 000 词) 页面的可能性很 小 ,这个特征有助于去除冗余页面. 2) 表 2 显示 ,关键资源页面的平均入度比普通 页面要大得多. 这可以使用反映网页链接关系的内 容推荐假设[13 ] (recommendation assumption) 解释 : 一个页面被其他页面所引用 ,反映这个页面的内容 被其他页面的作者所推荐. 拥有较多入度的页面 ,是 内容质量比较高的页面 ,它成为关键资源页面的可 能性也就比较大. 3) 根据表 1 的统计结果 ,FIL E 类型的网页在. GOV 语料库中占了大多数 ;但在关键资源训练集 中 ,FIL E 与非 FIL E 类型的页面数基本相等 ,非 FIL E 类型的页面反而更多一些. 这说明关键资源 页面的 URL 更倾向属于非 FIL E 类型. 第 1 期 刘奕群 ,等 :基于非内容信息的网络关键资源有效定位创 · 74 ·
·48 智能系统学报 第2卷 总之，这些常用的非内容特征在关键资源页面 接数目较大(>20)时，关键资源训练集上的分布百 上有不同于.G0V页面的分布，这种分布差异可以 分比明显高于.GOV语料库」 被用于关键资源页面的主题无关定位. % 2.2关键资源页面集合的站点自身出链接特征 60 50 ☆GOV语料库 关键资源页面是为用户提供高质量信息接入点 (关键资源训练集 40 的页面，这决定了它最重要的不是自身提供信息，而 30 是作为关键站点内容的代表提供链向站点内其他高 质量页面的链接.例如美国药物滥用治疗研究所 (NDA)关于大麻滥用方面信息的关键资源页面 10 2030400无流 http://www.nida.nih.gov/drugpages/marijuana. 站点自身出链接个数/个 html,它基本没有除去链接之外的文字内容，但这个 图1 站点自身出链接个数在关键资源训练集合和.GOV 页面提供了链向子站点内部其他与大麻信息相关的 语料库上的不同分布 页面链接，这些链接对浏览者获取大麻滥用方面的 Fig.I Site self link number of key resource training 信息是大有帮助的」 set and.GOV 由于关键资源页面是关键资源站点的代表和用 在统计平均值上，关键资源训练集合的站点自 户访问的接口，因此它应当具有能够直接链接到本 身出链接个数是37，而.G0V中的平均数目是18. 站点/子站点内的大多数页面，也即必须具有Cra 这也说明了站点自身出链接数目较小的页面更可能 swell等人在文献[l3]中提出的“导航功能”(navi 是普通页面，而这个数目较大的页面比较可能是关 gational function).为了更清楚的表述关键资源页 键资源页面 面的这个链接特征，把页面出链接划分为指向站点 2)站点自身出链接文本比率(site self link an- 内部的出链接和指向站点外部的出链接2类.由于 chor rate) 关键资源页面首先是站点内部高质量页面的代表， 关键资源页面的站点自身出链接文本可以认为 因此指向站点内部的出链接是我们考察的重点，这 是整个关键资源站点内容的概括.这是由链接文本 种出链接数目的多少和质量的好坏，直接影响到关 的特性所决定的，Craswell在文献[I3]中指出：对某 键资源页面本身的质量高低.为区别一般出链接，在 个确定的页面A而言，指向它的链接文本可以看作 下文中称之为“站点自身出链接” 是对此页面A的概括客观（通常来自其他作者）的 理想情况下，关键资源页面的站点自身出链接 描述.因此对关键资源页面而言，它的站点自身出链 接文本可以看作此页面作者对站点内其他页面的一 应当个数多，质量高.具体到内容无关信息而言，无 个简要介绍，这些文本的集合，也就可以作为整个站 法考察这种出链接描述文本于某个主题是否相关， 点内页面的一个综述」 但链接描述文本的长度是可知的，通过长度标准，评 站点自身出链接文本比率的定义为 判链接文本是否包含了足够的其他页面描述信息也 site self link rate=WordCount(site self link anchor) 是可行的.因此，站点自身出链接个数的多少，以及 Word Count (full text) 站点自身出链接描述文字的长短是否可以作为考察 (1) 关键资源页面质量的标准呢？下面将把站点自身出 对于关键资源页面而言，站点自身出链接文本 链接特征细化成此2个标准分别加以考查： 比率与站点自身出链接个数是类似的非内容特征，2 I)站点自身出链接个数(site self link number) 者的不同在于，站点自身出链接文本比率一定程度 关键资源页面作为关键资源站点的入口页面和 上反映了站点自身出链接质量的高低.仅仅列出导 代表，应当拥有较多的站点自身出链接.也就是说， 航信息的站点自身出链接，与给出子页面简要介绍 关键资源页面的站点自身出链接个数从总体上讲应 的站点自身出链接，其质量是显然不同的.站点自身 出链接文本比率较高的页面，可以认为其出链接质 当比普通页面更多.图1的统计数据中，横坐标表示 量较高。 站点自身出链接的个数，而纵坐标表示.GOV语料 关键资源页面一般都是关键资源站点的入口页 库和关键资源训练集合上的不同分布百分比.由统 面，其对应的站点自身出链接担负着引导用户访问 计数据可以看出，大部分（超过55%）.G0V语料库 的任务，因此链接质量较高，这类页面也相应的拥有 中的页面站点自身出链接个数小于10，而关键资源 较大的出链接文本比率 训练集中的这个比例在20%左右；而站点自身出链 对于关键资源页面而言，站点自身出链接文本 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
总之 ,这些常用的非内容特征在关键资源页面 上有不同于. GOV 页面的分布 ,这种分布差异可以 被用于关键资源页面的主题无关定位. 2. 2 关键资源页面集合的站点自身出链接特征 关键资源页面是为用户提供高质量信息接入点 的页面 ,这决定了它最重要的不是自身提供信息 ,而 是作为关键站点内容的代表提供链向站点内其他高 质量页面的链接. 例如美国药物滥用治疗研究所 (N IDA) 关于大麻滥用方面信息的关键资源页面 http :/ / www. nida. nih. gov/ drugpages/ marijuana. html ,它基本没有除去链接之外的文字内容 ,但这个 页面提供了链向子站点内部其他与大麻信息相关的 页面链接 ,这些链接对浏览者获取大麻滥用方面的 信息是大有帮助的. 由于关键资源页面是关键资源站点的代表和用 户访问的接口 ,因此它应当具有能够直接链接到本 站点/ 子站点内的大多数页面 ,也即必须具有 Cra2 swell 等人在文献[ 13 ]中提出的“导航功能”( navi2 gational f unction) . 为了更清楚的表述关键资源页 面的这个链接特征 ,把页面出链接划分为指向站点 内部的出链接和指向站点外部的出链接 2 类. 由于 关键资源页面首先是站点内部高质量页面的代表 , 因此指向站点内部的出链接是我们考察的重点 ,这 种出链接数目的多少和质量的好坏 ,直接影响到关 键资源页面本身的质量高低. 为区别一般出链接 ,在 下文中称之为“站点自身出链接”. 理想情况下 ,关键资源页面的站点自身出链接 应当个数多 ,质量高. 具体到内容无关信息而言 ,无 法考察这种出链接描述文本于某个主题是否相关 , 但链接描述文本的长度是可知的 ,通过长度标准 ,评 判链接文本是否包含了足够的其他页面描述信息也 是可行的. 因此 ,站点自身出链接个数的多少 ,以及 站点自身出链接描述文字的长短是否可以作为考察 关键资源页面质量的标准呢 ? 下面将把站点自身出 链接特征细化成此 2 个标准分别加以考查: 1) 站点自身出链接个数(site self link number) 关键资源页面作为关键资源站点的入口页面和 代表 ,应当拥有较多的站点自身出链接. 也就是说 , 关键资源页面的站点自身出链接个数从总体上讲应 当比普通页面更多. 图 1 的统计数据中 ,横坐标表示 站点自身出链接的个数 ,而纵坐标表示. GOV 语料 库和关键资源训练集合上的不同分布百分比. 由统 计数据可以看出 ,大部分 (超过 55 %) . GOV 语料库 中的页面站点自身出链接个数小于 10 ,而关键资源 训练集中的这个比例在 20 %左右 ;而站点自身出链 接数目较大( > 20) 时 ,关键资源训练集上的分布百 分比明显高于. GOV 语料库. 图 1 站点自身出链接个数在关键资源训练集合和. GOV 语料库上的不同分布 Fig. 1 Site self link number of key resource training set and . GOV 在统计平均值上 ,关键资源训练集合的站点自 身出链接个数是 37 ,而. GOV 中的平均数目是 18. 这也说明了站点自身出链接数目较小的页面更可能 是普通页面 ,而这个数目较大的页面比较可能是关 键资源页面. 2) 站点自身出链接文本比率 (site self link an2 chor rate) 关键资源页面的站点自身出链接文本可以认为 是整个关键资源站点内容的概括. 这是由链接文本 的特性所决定的 ,Craswell 在文献[13 ]中指出 :对某 个确定的页面 A 而言 ,指向它的链接文本可以看作 是对此页面 A 的概括客观 (通常来自其他作者) 的 描述. 因此对关键资源页面而言 ,它的站点自身出链 接文本可以看作此页面作者对站点内其他页面的一 个简要介绍 ,这些文本的集合 ,也就可以作为整个站 点内页面的一个综述. 站点自身出链接文本比率的定义为 site self link rate = WordCount (site self link anchor) Word Count (full text) . (1) 对于关键资源页面而言 ,站点自身出链接文本 比率与站点自身出链接个数是类似的非内容特征 ,2 者的不同在于 ,站点自身出链接文本比率一定程度 上反映了站点自身出链接质量的高低. 仅仅列出导 航信息的站点自身出链接 ,与给出子页面简要介绍 的站点自身出链接 ,其质量是显然不同的. 站点自身 出链接文本比率较高的页面 ,可以认为其出链接质 量较高. 关键资源页面一般都是关键资源站点的入口页 面 ,其对应的站点自身出链接担负着引导用户访问 的任务 ,因此链接质量较高 ,这类页面也相应的拥有 较大的出链接文本比率. 对于关键资源页面而言 ,站点自身出链接文本 · 84 · 智 能 系 统 学 报 第 2 卷
第1期 刘奕群，等：基于非内容信息的网络关键资源有效定位创 ·49· 比率与站点自身出链接个数是类似的非内容特征，2 和“1”2类.离散化属性取值的目的，是为了适应 者的不同在于，站点自身出链接文本比率一定程度 D3算法处理的要求，将取值类别局限在布尔变量 上反映了站点自身出链接质量的高低.仅仅列出导 上，则是出于减少算法复杂度的需要.离散化的具体 航信息的站点自身出链接，与给出子页面简要介绍 方式是选取特征阈值，比阈值大的样例特征取值为 的站点自身出链接，其质量是显然不同的.站点自身 1,否则取值为0.阈值的选取总体遵循保证信息增 出链接文本比率较高的页面，可以认为其出链接质 益最大的原则，但也可以作调整以得到满足不同需 量较高 要的决策树 关键资源页面一般都是关键资源站点的入口页 取值离散化后，根据D3算法的要求，信息增 面，其对应的站点自身出链接担负着引导用户访问 益最大的非内容特征（页面入度特征）选作决策树的 的任务，因此链接质量较高，这类页面也相应的拥有 根节点.训练样例集在根节点被分类后，每个子集重 较大的出链接文本比率.如图2所示 复计算信息增益的过程，并选取信息增益最大的非 内容特征作为这个子集对应的决策树节点的分类特 601 50 女.GOV语料库 征.当满足下列条件之一时算法结束： 40 兴关键资源练集 1)所有样例都具有近似相同的分类结果； 30 2)所有属性都已在每条从根节点到叶子节点的 20* 路径上被测试. 10 由上述步骤生成的决策树如图3所示，利用此 0 0.050.100.150.200.250.300.350.40othe 决策树，判定任意web页面是否可以归入关键资源 站点自身出链接比率 页面的范畴就成为可能，如果对全体web页面施行 图2站点自身出链接比率在关键资源训练集合和.GOV 决策树判定算法，就可以得到一个web页面全集的 语料库上的不同分布 子集一关键资源页面集合 Fig.2 Site self link anchor text rate of key resource 页面入度 training set and.GOV ≤0 >10 图中横坐标表示站点自身出链接文本比率的大 URL分极 小，而纵坐标表示.G0V语料库和关键资源训练集合 FE类 非FLE类 面页长度☐ 上的不同分布百分比.由数据可以看出，站点自身出 站点自身 1000 链接文本比率较高的页面更可能是关键资源页面.此 出链接文本比案 非关键资源 关键资源 ≤0.17 、>0.1 页面 页面 特征的分布曲线与站点自身出链接个数特征非常类 非关键资源 页面长度 似，但在区分关键资源的能力上更强一些.有超过 页面 站点百身出链接数目 ≤1000/J000 76%的.G0V语料库页面出链接文本比率不足0.1， 50 、>50非关键资源页面关键资源页面 但在关键资源训练集中，这个比率只有39%. 非关键资源页面项面长度☐ 3非内容特征与关键资源页面判定 <1000/1000 非关键资源页面关键资源页面 决策树学习(decision tree learning)的方法被 图3利用非内容特征进行关键资源页面判定的决策树 选择用于进行web页面非内容特征的综合，这是由 Fig.3 Key resource decision tree constructed with ID3 于决策树算法自身的一些特点所决定的.决策树学 and nomcontent features 习适合解决目标函数具有离散输出值的问题，而且 4 往往是特征数目较少时，解决此类问题的最简单有 实验与结果分析 效的途径之一.文中使用的决策树学习算法，是由 本节将重点讨论根据.GOV数据得到的关键资 Quinlan在1986年提出的D3算法).算法引入了 源页面集合在实验中的若干统计与检索特性.在讨 信息增益的概念，并使用信息增益的多少来决定树 论这些特性之前，还将介绍文中实验所使用的训练 的结点需要测试的属性 与测试集合 具体到关键资源页面判定的问题，我们把页面 4.1训练集与测试集 非内容属性的取值离散化为一个布尔变量，即对于 文中所采用的实验数据均来源于.GOV语料库 某个非内容属性A而言，某页面P的取值只有“0” 中的页面，为获取可信的关键资源页面训练集与测 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
比率与站点自身出链接个数是类似的非内容特征 ,2 者的不同在于 ,站点自身出链接文本比率一定程度 上反映了站点自身出链接质量的高低. 仅仅列出导 航信息的站点自身出链接 ,与给出子页面简要介绍 的站点自身出链接 ,其质量是显然不同的. 站点自身 出链接文本比率较高的页面 ,可以认为其出链接质 量较高. 关键资源页面一般都是关键资源站点的入口页 面 ,其对应的站点自身出链接担负着引导用户访问 的任务 ,因此链接质量较高 ,这类页面也相应的拥有 较大的出链接文本比率. 如图 2 所示. 图 2 站点自身出链接比率在关键资源训练集合和. GOV 语料库上的不同分布 Fig. 2 Site self link anchor text rate of key resource training set and . GOV 图中横坐标表示站点自身出链接文本比率的大 小 ,而纵坐标表示. GOV 语料库和关键资源训练集合 上的不同分布百分比. 由数据可以看出 ,站点自身出 链接文本比率较高的页面更可能是关键资源页面. 此 特征的分布曲线与站点自身出链接个数特征非常类 似 ,但在区分关键资源的能力上更强一些. 有超过 76 %的. GOV 语料库页面出链接文本比率不足 0. 1 , 但在关键资源训练集中 ,这个比率只有 39 %. 3 非内容特征与关键资源页面判定 决策树学习 ( decision tree learning) 的方法被 选择用于进行 web 页面非内容特征的综合 ,这是由 于决策树算法自身的一些特点所决定的. 决策树学 习适合解决目标函数具有离散输出值的问题 ,而且 往往是特征数目较少时 ,解决此类问题的最简单有 效的途径之一. 文中使用的决策树学习算法 ,是由 Quinlan 在 1986 年提出的 ID3 算法[14 ] . 算法引入了 信息增益的概念 ,并使用信息增益的多少来决定树 的结点需要测试的属性. 具体到关键资源页面判定的问题 ,我们把页面 非内容属性的取值离散化为一个布尔变量 ,即对于 某个非内容属性 A 而言 ,某页面 P 的取值只有“0” 和“1”2 类. 离散化属性取值的目的 ,是为了适应 ID3 算法处理的要求 ,将取值类别局限在布尔变量 上 ,则是出于减少算法复杂度的需要. 离散化的具体 方式是选取特征阈值 ,比阈值大的样例特征取值为 1 ,否则取值为 0. 阈值的选取总体遵循保证信息增 益最大的原则 ,但也可以作调整以得到满足不同需 要的决策树. 取值离散化后 ,根据 ID3 算法的要求 ,信息增 益最大的非内容特征(页面入度特征) 选作决策树的 根节点. 训练样例集在根节点被分类后 ,每个子集重 复计算信息增益的过程 ,并选取信息增益最大的非 内容特征作为这个子集对应的决策树节点的分类特 征. 当满足下列条件之一时算法结束 : 1) 所有样例都具有近似相同的分类结果 ; 2) 所有属性都已在每条从根节点到叶子节点的 路径上被测试. 由上述步骤生成的决策树如图 3 所示 ,利用此 决策树 ,判定任意 web 页面是否可以归入关键资源 页面的范畴就成为可能. 如果对全体 web 页面施行 决策树判定算法 ,就可以得到一个 web 页面全集的 子集 ———关键资源页面集合. 图 3 利用非内容特征进行关键资源页面判定的决策树 Fig. 3 Key resource decision tree constructed with ID3 and non2content features 4 实验与结果分析 本节将重点讨论根据. GOV 数据得到的关键资 源页面集合在实验中的若干统计与检索特性. 在讨 论这些特性之前 ,还将介绍文中实验所使用的训练 与测试集合. 4. 1 训练集与测试集 文中所采用的实验数据均来源于. GOV 语料库 中的页面 ,为获取可信的关键资源页面训练集与测 第 1 期 刘奕群 ,等 :基于非内容信息的网络关键资源有效定位创 · 94 ·
·50 智能系统学报 第2卷 试集，实验基本沿用了TREC2002与TREC2003主 口测试集在实验结果集中的比例 100▣训练集在实验结果集中的比例 题提炼任务的查询主题及标准答案.由于 实验结果集在.GOV中的比例 TREC2002主题提炼任务的目标是查找关键资源站 点所包含的页面而不一定是关键资源页面41，因 此专门对这部分的答案集合进行了手工筛选，以找 出标准答案页面对应的站点/子站点入口页面 例如TREC2002主题提炼任务的599号主题 集2 集3 集4 集5 “scientific research misconduct”,原有的答案包括 结果 子站点http://ori.dhhs.gov/html/misconduct/内 图4不同特征判定阈值下的实验结果集合数据 的24个页面，手工筛选后，将这些页面用这个子站 Fig.4 Key resource coverage and result set size with 点的入口页面http:/ori.dhhs.gov/html/miscon- different nomcontent feature threshold 特征判定阈值下，都可以用20%左右的网页数量 duct/casesummaries.asp代替. 覆盖超过70%的关键资源页面.这说明依靠非内容 关键资源测试集直接采用了TREC2003主题 提炼任务的查询主题与标准答案，此任务共提供了 特征进行关键资源页面的定位是完全可能的.实验 50个查询主题和对应主题的516个标准答案.任务 得到的“关键资源页面集合"”确实能够覆盖大部分关 键资源页面.这也说明仍有约30%的关键资源页面 的目的是查找与主题相对应的关键资源页面，查询 不被实验结果集合所包括，因此在实验结果集合上 主题来源于真实网络搜索引擎的用户查询，包含的 内容领域涉及社会政治经济生活的方方面面，因此 进行主题提炼查找的性能上限即为70%左右.但 具有较高的权威性 是，当前主题提炼任务按平均精度计算的性能一般 都在20%上下浮动4·引，因此这个上限对主题提炼 4.2基于关键资源页面集合的统计结果 特征取值离散化时判定阈值的选取不同，得到 任务的性能影响甚微 的决策树形式也会有不同；对应的，关键资源页面集 2)实验结果得到的高质量集合覆盖关键资源页 合的规模也有差异，实验中不同的实验结果集对应 面的比例是随着这个集合的规模而增加的.与 的非内容特征阈值如表3所示，而图4则给出了这 GOV集合规模相等的关键资源页面集合可以覆盖 些实验结果集合覆盖关键资源页面的相关实验数 所有的关键资源，但这个集合显然不能称之为“高质 据 量”，因此必须定义一个评价标准，从而能够在关键 资源覆盖率与页面集合大小之间找到较好的平衡 表3对应不同实验结果集合的非内容特征阈值 点，从而筛选出质量较高的关键资源页面 Ta ble 3 Corresponding non-content feature thresholds for 4.3关键资源页面集合的评价标准 different result sets 关键资源页面判定结果的评价与一般的分类问 结果结果结果结果 结果 题有类似之处，其问题可以归结到“用最小规模的关 集1 集2 集3 集4 集5 键资源页面集合覆盖最大数量的关键资源页面”，对 站点自身出 50 50 30 10 10 于此类问题，一般采用精度一召回率的评价标准.召 链接数目 回率和精度的一般定义为 站点自身出 0.10.050.050.1 0.05 链接文本比率 recall=相关页面集合n检索结果页面集合L #相关页面集合 2 图4中的纵轴标志着不同比例的数值，分别是： 测试集在实验结果集中的比例R,训练集在实验结 precision=兰相关页面集会n检索结果顶面集金 #检索结果页面集合 果集中的比例和实验结果集在.GOV语料库中 (3 的比例.一个理想的实验结果，应该用较小的页 由于无法判断实验结果集合中所有的关键资源页 面数，包括较多的关键资源页面，也就是说要在 面，因此在精度和召回率的计算中必须进行关键资 尽量小的情况下，保证R和R较大 源数目的估计.为此引入如下假设： 从图4的实验结果中可以得到如下2个重要结 1)关键资源训练集合是.GOV中所有关键资源 论 页面的一个均一采样k; 1)使用文中提出的关键资源定位算法，在多种 2)关键资源页面占.G0V页面总量的比例为k 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
试集 ,实验基本沿用了 TREC2002 与 TREC2003 主 题 提 炼 任 务 的 查 询 主 题 及 标 准 答 案. 由 于 TREC2002 主题提炼任务的目标是查找关键资源站 点所包含的页面而不一定是关键资源页面[ 4 ,6 ] ,因 此专门对这部分的答案集合进行了手工筛选 ,以找 出标准答案页面对应的站点/ 子站点入口页面. 例如 TREC2002 主题提炼任务的 599 号主题 “scientific research misconduct”,原有的答案包括 子站点 http :/ / ori. dhhs. gov/ html/ misconduct/ 内 的 24 个页面 ,手工筛选后 ,将这些页面用这个子站 点的入口页面 http :/ / ori. dhhs. gov/ html/ miscon2 duct/ casesummaries. asp 代替. 关键资源测试集直接采用了 TREC2003 主题 提炼任务的查询主题与标准答案 ,此任务共提供了 50 个查询主题和对应主题的 516 个标准答案. 任务 的目的是查找与主题相对应的关键资源页面 ,查询 主题来源于真实网络搜索引擎的用户查询 ,包含的 内容领域涉及社会政治、经济生活的方方面面 ,因此 具有较高的权威性. 4. 2 基于关键资源页面集合的统计结果 特征取值离散化时判定阈值的选取不同 ,得到 的决策树形式也会有不同 ;对应的 ,关键资源页面集 合的规模也有差异 ,实验中不同的实验结果集对应 的非内容特征阈值如表 3 所示 ,而图 4 则给出了这 些实验结果集合覆盖关键资源页面的相关实验数 据. 表 3 对应不同实验结果集合的非内容特征阈值 Table 3 Corresponding non2content feature thresholds for different result sets 结果 集 1 结果 集 2 结果 集 3 结果 集 4 结果 集 5 站点自身出 链接数目 50 50 30 10 10 站点自身出 链接文本比率 0. 1 0. 05 0. 05 0. 1 0. 05 图 4 中的纵轴标志着不同比例的数值 ,分别是 : 测试集在实验结果集中的比例 R1 ,训练集在实验结 果集中的比例 R2 和实验结果集在. GOV 语料库中 的比例 R3 . 一个理想的实验结果 ,应该用较小的页 面数 ,包括较多的关键资源页面 ,也就是说要在 R3 尽量小的情况下 ,保证 R1 和 R2 较大. 从图 4 的实验结果中可以得到如下 2 个重要结 论 : 1) 使用文中提出的关键资源定位算法 ,在多种 图 4 不同特征判定阈值下的实验结果集合数据 Fig. 4 Key resource coverage and result set size with different non2content feature threshold 特征判定阈值下 ,都可以用 20 %左右的网页数量 , 覆盖超过 70 %的关键资源页面. 这说明依靠非内容 特征进行关键资源页面的定位是完全可能的. 实验 得到的“关键资源页面集合”确实能够覆盖大部分关 键资源页面. 这也说明仍有约 30 %的关键资源页面 不被实验结果集合所包括 ,因此在实验结果集合上 进行主题提炼查找的性能上限即为 70 %左右. 但 是 ,当前主题提炼任务按平均精度计算的性能一般 都在 20 %上下浮动[4 - 5 ] ,因此这个上限对主题提炼 任务的性能影响甚微. 2) 实验结果得到的高质量集合覆盖关键资源页 面的比例是随着这个集合的规模而增加的. 与. GOV 集合规模相等的关键资源页面集合可以覆盖 所有的关键资源 ,但这个集合显然不能称之为“高质 量”,因此必须定义一个评价标准 ,从而能够在关键 资源覆盖率与页面集合大小之间找到较好的平衡 点 ,从而筛选出质量较高的关键资源页面. 4. 3 关键资源页面集合的评价标准 关键资源页面判定结果的评价与一般的分类问 题有类似之处 ,其问题可以归结到“用最小规模的关 键资源页面集合覆盖最大数量的关键资源页面”. 对 于此类问题 ,一般采用精度 —召回率的评价标准. 召 回率和精度的一般定义为 recall = # (相关页面集合 ∩检索结果页面集合) # 相关页面集合 . (2) precision = # (相关页面集合 ∩检索结果页面集合) # 检索结果页面集合 . (3) 由于无法判断实验结果集合中所有的关键资源页 面 ,因此在精度和召回率的计算中必须进行关键资 源数目的估计. 为此引入如下假设 : 1) 关键资源训练集合是. GOV 中所有关键资源 页面的一个均一采样 k ; 2) 关键资源页面占. GOV 页面总量的比例为 k. · 05 · 智 能 系 统 学 报 第 2 卷
第1期 刘奕群，等：基于非内容信息的网络关键资源有效定位创 ·51· 在上述假设下，召回率可以通过关键资源测试 面检索的效果有明显的提高，如下面的结果列表所 集在实验所得到的结果集合中的覆盖度来估计，即： 示 recall=兰实验结果集合n关键资源测试集 表4不同页面集合上的检索效果比较 #.关键资源测试集 Table 4 Content retrieval results for different result sets 4) 在精度的计算中，由于关键资源页面的总数可 全部页 关键资源 TREC2003 评价方式 以用.GOV页面总数和K来计算，而#(.GOV页 面集合 页面集合 最优结果 面集合)XK Xrecall则表示了关键资源页面在实验 Precision @10 0.0720 0.1240 0.1240 结果集中的数目，因此精度表达式为 R-precision 0.1145 0.1670 0.1636 precision #LGOV页面集合)X K Xrecall #(实验结果集合) 实验比较了TREC2003主题提炼任务在2个 (5) 页面集合上的性能，可以看出关键资源页面集合的 为了在关键资源覆盖率与页面集合大小之间找 检索效果明显好于页面全集.为了方便比较，2组实 到较好的平衡点，利用通常使用的均衡评价精度与 验都只采用了BM2500权重计算公式和此公式默认 召回率的F-measure评价is7,它的定义为 的实验参数.评价方式采用的是TREC网络信息检 F(r.p)=1+a tecall Xprecision 索任务通用的前l0位结果平均精度(Precision@ 6) recall +a Xprecision l0)和R精度(R-precision).在Precision@I0评价 式中precision的权重为1，而recall的权重为a.在 上，关键资源页面检索比较全部页面集合检索有 关键资源页面性能判定的评价中，由于试图用实验 72.22%的提高，而在R-precision评价上性能提高 得到的关键资源页面集合代替原有页面集合进行检 的比例是45.85%.检索性能的差异可以作如下解 索，因此关键资源页面的召回率应当得到更多的重 释：关键资源页面集合中用少量的页面集中了大量 视，以保证原有页面集合信息尽量少丢失由此设定 的关键资源，在这样的集合里进行主题提炼检索的 a=2.取K=1/6,则根据此实验数据得到的精度一 难度要远小于在页面全集上进行检索.从另一个角 召回率评价结果如下（与图4中的实验结果集合一 度，也可以认为关键资源页面定位的过程去除了 一对应)： web信息环境中的大量冗余信息，在一个信息有效 ◆-precision。-recall 性高的页面集合上进行检索的效果自然会好 0.75 --F2-measure 为了验证方法的有效性，还把这2组结果与 065 TREC2003的最优结果1进行了比较，实验证明，关 0.55 键资源页面集合上的检索效果与TREC2003主题 提炼任务的最优结果性能相当，在R-precision评价 0.45 上还优于这个结果.这也充分说明了基于非内容信 0.35 息进行关键资源定位对于主题过滤任务是行之有效 集1 集2集3 集4 集5 的 结果 图5不同实验结果集合的精度、召回率和 5结论与未来工作 F-measure评价数值比较 网络数据的爆炸性增长与低质量信息的泛滥给 Fig.5 Recall,Precision and F-measure values of 网络信息检索技术的发展带来了巨大的挑战，文中 different result sets 提出了一种综合利用web页面的非内容信息进行 从实验结果可以看出，随着召回率的上升，实验 关键资源页面提取的方法，利用这种方法得到的关 结果集合的精度是逐步下降的，而F-measure值则 键资源页面集合，可以用20%左右的web页面数 先增后减，结果集4的F-measure评价最高.此结果 量，覆盖超过70%的关键信息.基于关键资源页面 集的页面数占页面总量的24.89%，但其包含的关 集合的检索，也获得了远远超过在页面全集上检索 键资源页面却占测试集的73.12%，满足用较少页 的效果.这说明利用web页面正文内容以外的信 面覆盖较多关键资源信息的要求，下面的检索实验 息，去除冗余页面，在保证检索效果的前提下，将搜 中就是基于这个页面集合完成的， 索引擎索引的页面控制在少量高质量页面上是完全 4.4基于关键资源页面集合的检索实验结果 可能的.这对于在索引量一定的条件下提高搜索引 关键资源页面定位的最终结果评价，还要落实 擎的信息覆盖率至关重要；同时也为在信息覆盖率 到关键资源页面集合检索的效能提高上.实验结果 一定的情况下减少搜索引擎维护索引的成本提供了 说明，基于关键资源页面集合的检索效果比全部页 一个解决途径 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
在上述假设下 ,召回率可以通过关键资源测试 集在实验所得到的结果集合中的覆盖度来估计 ,即 : recall = # (实验结果集合 ∩关键资源测试集) # 关键资源测试集 . (4) 在精度的计算中 ,由于关键资源页面的总数可 以用. GOV 页面总数和 K 来计算 ,而 # (. GOV 页 面集合) ×K ×recall 则表示了关键资源页面在实验 结果集中的数目 ,因此精度表达式为 precision = # (. GOV 页面集合) ×K ×recall # (实验结果集合) . (5) 为了在关键资源覆盖率与页面集合大小之间找 到较好的平衡点 ,利用通常使用的均衡评价精度与 召回率的 F2measure 评价[15 ] ,它的定义为 Fα( r, p) = (1 +α) recall ×precision recall +α×precision . (6) 式中 :precision 的权重为 1 ,而 recall 的权重为α. 在 关键资源页面性能判定的评价中 ,由于试图用实验 得到的关键资源页面集合代替原有页面集合进行检 索 ,因此关键资源页面的召回率应当得到更多的重 视 ,以保证原有页面集合信息尽量少丢失. 由此设定 α= 2. 取 K = 1/ 6 ,则根据此实验数据得到的精度 — 召回率评价结果如下 (与图 4 中的实验结果集合一 一对应) : 图 5 不同实验结果集合的精度、召回率和 F2measure 评价数值比较 Fig. 5 Recall , Precision and F2measure values of different result sets 从实验结果可以看出 ,随着召回率的上升 ,实验 结果集合的精度是逐步下降的 ,而 F2measure 值则 先增后减 ,结果集 4 的 F2measure 评价最高. 此结果 集的页面数占页面总量的 24. 89 % ,但其包含的关 键资源页面却占测试集的 73. 12 % ,满足用较少页 面覆盖较多关键资源信息的要求 ,下面的检索实验 中就是基于这个页面集合完成的. 4. 4 基于关键资源页面集合的检索实验结果 关键资源页面定位的最终结果评价 ,还要落实 到关键资源页面集合检索的效能提高上. 实验结果 说明 ,基于关键资源页面集合的检索效果比全部页 面检索的效果有明显的提高 ,如下面的结果列表所 示. 表 4 不同页面集合上的检索效果比较 Table 4 Content retrieval results for different result sets 评价方式 全部页 面集合 关键资源 页面集合 TREC2003 最优结果 Precision @ 10 0. 072 0 0. 124 0 0. 124 0 R2precision 0. 114 5 0. 167 0 0. 163 6 实验比较了 TREC2003 主题提炼任务在 2 个 页面集合上的性能 ,可以看出关键资源页面集合的 检索效果明显好于页面全集. 为了方便比较 ,2 组实 验都只采用了BM2500 权重计算公式和此公式默认 的实验参数. 评价方式采用的是 TREC 网络信息检 索任务通用的前 10 位结果平均精度 (Precision @ 10) 和 R2精度 (R2precision) . 在 Precision @10 评价 上 ,关键资源页面检索比较全部页面集合检索有 72. 22 %的提高 ,而在 R2precision 评价上性能提高 的比例是 45. 85 %. 检索性能的差异可以作如下解 释 :关键资源页面集合中用少量的页面集中了大量 的关键资源 ,在这样的集合里进行主题提炼检索的 难度要远小于在页面全集上进行检索. 从另一个角 度 ,也可以认为关键资源页面定位的过程去除了 web 信息环境中的大量冗余信息 ,在一个信息有效 性高的页面集合上进行检索的效果自然会好. 为了验证方法的有效性 ,还把这 2 组结果与 TREC2003 的最优结果[5 ]进行了比较 ,实验证明 ,关 键资源页面集合上的检索效果与 TREC2003 主题 提炼任务的最优结果性能相当 ,在 R2precision 评价 上还优于这个结果. 这也充分说明了基于非内容信 息进行关键资源定位对于主题过滤任务是行之有效 的. 5 结论与未来工作 网络数据的爆炸性增长与低质量信息的泛滥给 网络信息检索技术的发展带来了巨大的挑战 ,文中 提出了一种综合利用 web 页面的非内容信息进行 关键资源页面提取的方法 ,利用这种方法得到的关 键资源页面集合 ,可以用 20 %左右的 web 页面数 量 ,覆盖超过 70 %的关键信息. 基于关键资源页面 集合的检索 ,也获得了远远超过在页面全集上检索 的效果. 这说明利用 web 页面正文内容以外的信 息 ,去除冗余页面 ,在保证检索效果的前提下 ,将搜 索引擎索引的页面控制在少量高质量页面上是完全 可能的. 这对于在索引量一定的条件下提高搜索引 擎的信息覆盖率至关重要 ;同时也为在信息覆盖率 一定的情况下减少搜索引擎维护索引的成本提供了 一个解决途径. 第 1 期 刘奕群 ,等 :基于非内容信息的网络关键资源有效定位创 · 15 ·
·52 智能系统学报 第2卷 关键资源页面提取方法也带来了新的问题，从 evidence in home page finding [J ]In ACM Transac- 文中的实验结果中可以看出，提取出的关键资源页 tions on Information Systems TOIS),2003,21 (3): 面集合在检索特征上与web页面全集有明显的不 286.313 同，因此系统考察己有检索方法在关键资源页面集 [10]WESTERVELD T,HIEMSTRA D,KRAAD W.Re- 合上的表现，从而确立这个集合上可以应用的方法 trieving web pages using content,links,URLs and an- 体系是很有必要的.需要考察的可能内容包括：各种 chors [A].In Voorhees and Harman [7][C].[s.1.] 己有检索模型的性能如何；各种链接分析算法是否 2000. 有效；通常使用的链接文本检索方法是否能取得性 [11]KRAAU W,WESTERVELD T,HIEMSTRA D.The 能的提高等等.此外，尽管文中在评价关键资源页面 importance of prior probabilities for entry page search 集合本身的质量上完成了一些工作，但仍然缺乏从 [A].In 25th annual international ACM SIGIR confer- 检索性能层次评价集合质量的尝试.这些可能都是 ence on research and development in information retriev- 未来研究工作的方向」 al [C].pages 27-34. [12]BRODER A.A taxonomy of Web search [J ]SIGIR 参考文献： Forum,2002,36(2):1-8. [1]SULLIVAN D.Search engine sizes EB/OL ]From [13 ]CRASWELL N,HAWKING D.Stephen robertson.effec- search engine watch web site http:/searchenginewatch. tive site finding using link anchor information [A].In 24th com/reports/article.php/2156481,2005-01 -28/2005 ACM-SIGIR Conference on Research and Development in -06-18. Information Retrieval [C].pages 250-257. [2]L YMAN P,HAL R V.How much information 2003 [14]MITCHELL T M.Chapter 3:Decision Tree Learning, EB/OL ]On line at:http://www.sims.berkeley. in Machine Learning M].McGraw-Hill International cdu/how-muchrinfo2003,2003-10-30/2005-06- Editions,1997. [15]RU SBERGEN C J.Information Retireval M].Butter- 18. [3]MONIKA R H,MOTWANI R,SILVERSTEIN C. worths,London,1979 Challenges in web search engines [A ]Georg Gottlob, [16]HA WKIN GD,CRASWELL N.Overview of the TREC Toby Walsh eds.D CAI-03,Proceedings of the Eigh- -2001 web track [A].In Voorhees and Harman [7] teenth International Joint Conference on Artificial Intelli- [C1.[s.1.],2001. gence [C].San Francisco:Morgan Kaufmann Press, 作者简介： 2003. 刘奕群，男，1981年生，博士研究 [4]HAWKINGD,CRASWELL N.Overview of the TREC 生.主要研究方向为信息检索、机器学 习与网络用户行为分析.发表学术论文 -2002 web track [A ]In Voorhees and Buckland [6] 10余篇」 [C].[s.1.】,2002 [5]HAW KIN G D,CRASWELL N.Overview of the TREC Email:liuyiqun03 @mails.tsing- 2003 web track EB/OL ]On line at:http://trec.nist. hua.edu.cn. gov/pubs/trec12/papers/WEB.OVERVIEW.pdf,2004 张敏，女，1977年生，助理研究 -02/2005-01. [6]VOORHEES E M,BUCKLAND PL.The eleventh text 员.主要研究方向为信息检索、机器学 习、自然语言处理、基于认知的信息处 retrieval conference (TREC-2002),volume 11 M]. National Institute of Standards and Technology,NIST, 理，以及在网络环境下用户行为模式的 2003. 抽取和分析，及其对相关网络信息获取 技术.发表学术论文40余篇。 [7]DAVISON B D.Topical locality in the web [A].Pro- ceedings of the 23rd Annual International Conference on 马少平，男，1961年生，教授，博士 Research and Development in Information Retrieval [C]. 生导师.主要研究方向为知识工程、信 [s.1.],2000 息检索、汉字识别与后处理以及中文古 [8 ]BHARAT K,HENZIN GER M.Improved algorithms 籍数字化.承担过多项国家自然科学基 for topic distillation in a hyperlinked environment [A ] 金、“863”高技术项目、“973”项目及国 In 21st International ACM SIGIR Conference on Re- 际合作项目.在脱机手写体汉字识别和 search and Development in Information Retrieval [C]. 后处理方面达到了国际先进水平.“脱 [s.1.1,1998 机手写体汉字与数字识别系统”1998年1月获得国家教委 [9]CRASWELL N,HAWKIN G D.Query-independent 科技进步二等奖.发表论文60余篇，出版教材2部. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
关键资源页面提取方法也带来了新的问题 ,从 文中的实验结果中可以看出 ,提取出的关键资源页 面集合在检索特征上与 web 页面全集有明显的不 同 ,因此系统考察已有检索方法在关键资源页面集 合上的表现 ,从而确立这个集合上可以应用的方法 体系是很有必要的. 需要考察的可能内容包括 :各种 已有检索模型的性能如何 ;各种链接分析算法是否 有效 ;通常使用的链接文本检索方法是否能取得性 能的提高等等. 此外 ,尽管文中在评价关键资源页面 集合本身的质量上完成了一些工作 ,但仍然缺乏从 检索性能层次评价集合质量的尝试. 这些可能都是 未来研究工作的方向. 参考文献 : [1 ] SULL IVAN D. Search engine sizes [ EB/ OL ]. From search engine watch web site http :/ / searchenginewatch. com/ reports/ article. php/ 2156481 , 2005 - 01 - 28/ 2005 - 06 - 18. [2 ]L YMAN P , HAL R V. How much information 2003 [ EB/ OL ]. On line at : http :/ / www. sims. berkeley. edu/ how2much2info22003 , 2003 - 10 - 30/ 2005 - 06 - 18. [3 ] MONIKA R H , MO TWANI R , SILV ERSTEIN C. Challenges in web search engines [ A ]. Georg Gottlob , Toby Walsh eds. IJCAI - 03 , Proceedings of the Eigh2 teenth International Joint Conference on Artificial Intelli2 gence [ C ]. San Francisco : Morgan Kaufmann Press , 2003. [4 ] HAWKIN G D , CRASWELL N. Overview of the TREC - 2002 web track [ A ]. In Voorhees and Buckland [ 6 ] [C]. [s. l. ] ,2002. [5 ] HAWKIN G D , CRASWELL N. Overview of the TREC 2003 web track [ EB/ OL ]. On line at : http :/ / trec. nist. gov/ pubs/ trec12/ papers/ WEB. OV ERVIEW. pdf , 2004 - 02/ 2005 - 01. [6 ]VOORHEES E M , BUCKLAND P L. The eleventh text retrieval conference ( TREC - 2002) , volume 11 [ M ]. National Institute of Standards and Technology , NIST , 2003. [7 ]DAVISON B D. Topical locality in the web [ A ]. Pro2 ceedings of the 23rd Annual International Conference on Research and Development in Information Retrieval [C]. [s. l. ] ,2000. [8 ] B HARA T K , HENZIN GER M. Improved algorithms for topic distillation in a hyperlinked environment [ A ]. In 21st International ACM SIGIR Conference on Re2 search and Development in Information Retrieval [ C ]. [s. l. ] , 1998. [9 ] CRASWELL N , HAWKIN G D. Query - independent evidence in home page finding [J ]. In ACM Transac2 tions on Information Systems ( TOIS) , 2003 , 21 ( 3) : 286 - 313. [10 ]WESTERV ELD T , HIEMSTRA D , KRAAIJ W. Re2 trieving web pages using content , links , URLs and an2 chors [ A ]. In Voorhees and Harman [ 7 ] [ C]. [ s. l. ] , 2000. [11 ] KRAAIJ W , WESTERV ELD T , HIEMSTRA D. The importance of prior probabilities for entry page search [ A ]. In 25th annual international ACM SIGIR confer2 ence on research and development in information retriev2 al [C]. pages 27 - 34. [12 ]BRODER A. A taxonomy of Web search [J ]. SIGIR Forum , 2002 , 36 (2) :1 - 8. [13 ]CRASWELL N , HAWKING D. Stephen robertson. effec2 tive site finding using link anchor information [ A ]. In 24th ACM - SIGIR Conference on Research and Development in Information Retrieval [C]. pages 250 - 257. [14 ]MITCHELL T M. Chapter 3 : Decision Tree Learning , in Machine Learning [ M ]. Mc Graw2Hill International Editions , 1997. [15 ]RIJ SBERGEN C J. Information Retireval [ M]. Butter2 worths , London , 1979. [ 16 ] HAWKIN G D , CRASWELL N. Overview of the TREC - 2001 web track [ A ]. In Voorhees and Harman [ 7 ] [C]. [s. l. ] ,2001. 作者简介 : 刘奕群 ,男 , 1981 年生 ,博士研究 生. 主要研究方向为信息检索、机器学 习与网络用户行为分析. 发表学术论文 10 余篇. E2mail : liuyiqun03 @ mails. tsing2 hua. edu. cn. 张 敏 ,女 , 1977 年生 ,助理研究 员. 主要研究方向为信息检索、机器学 习、自然语言处理、基于认知的信息处 理 ,以及在网络环境下用户行为模式的 抽取和分析 ,及其对相关网络信息获取 技术. 发表学术论文 40 余篇. 马少平 ,男 ,1961 年生 ,教授 ,博士 生导师. 主要研究方向为知识工程、信 息检索、汉字识别与后处理以及中文古 籍数字化. 承担过多项国家自然科学基 金“、863”高技术项目、“973”项目及国 际合作项目. 在脱机手写体汉字识别和 后处理方面达到了国际先进水平.“脱 机手写体汉字与数字识别系统”1998 年 1 月获得国家教委 科技进步二等奖. 发表论文 60 余篇 ,出版教材 2 部. · 25 · 智 能 系 统 学 报 第 2 卷
