第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,/ >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 ·