（模式识别与智能系统专业论文）面向博客空间的搜索排序研究.pdf

ab s t r a c t wi t h t h e w i d e s p r e a d o f ww t e c h n o l o g y a n d 阮 d e v e l o p m e n t o f w e b c o n t e n t p u b l i s h i n g t e c h n o l o g y , p e o p l e f r o m v a r io u s p r o f e s s i o n s b e g i n t o p u b l i s h in f o r m a t io n v i a w e b l o g p u b li s h i n g s y s t e m in t h e f o r m o f b lo g p o s ts , w h i c h f o r m s a n i n f o r m a ti o n - - r i c h b u t d is o r d e r e d b l o g o s p h e r e w i t h l a r g e q u a n t i ti e s o f b l o g w e b s i t e s . a n d w i t h t h e c o n t i n u o u s g r o w th o f t h e b l o g o s p h e r e , t h e n e e d s o f b lo g s e a r c h i s b e c o m i n g u r g e n t . h o w e v e r , a s t h e s t r u c t u r e , f o r m a t a n d o r g a n i z a t io n o f c o n t e n t s o f t h e b l o g w e b - - s i t e s a r e q u i t e d i ff e r e n t fr o m t r a d i ti o n a l w e b s i t e s , t r a d i ti o n a l w e b s e a r c h e n g i n e f a i l e d t o m i n e t h i s b l o g o s p h e r e e ff e c t iv e 卜a n d e x t r a c t m o s t v a l u a b l e i n f o r m a ti o n f o r w e b s e a r c h u s e r s . o n e o f t h e m o s t i m p o r t a n t p r o b l e m s i s : h o w t o m e a s u r e t h e i m p o r ta n c e o f a s in g l e b l o g p o s t o r b l o g w e b s i t e , a n d h o w t o r a n k v a s t n u m b e r o f b l o g p o s ts a c c o r d i n g t o t h i s m e a s u r e o f i m p o r ta n c e . b e i n g f a c e d w it h t h i s p r o b l e m , t h e p a p e r t h r o u 浏y i n v e s t i g a t e d t h e u n i q u e f e a t u r e s o f b l o g w e b s it e s a n d b l o g o s p h e r e , r e f e r e d a lo t o f r e l a t e d t h e o r e t ic a l a n d t e c h nic a l r e s e a r c h f r u i t s a n d 二， 4- a n e x t e n c i v e d i s c u s s i o n o v e r t h e b a s i c c h a r a c te r i s t i c s o f b l o g o s p h e re i n f o r m a t i o n r e tr i e v a l . b a s e d o n t h e s e i n v e s t i 脚 o n w o r k a n d p r e v i o u s r e s e a r c h f in d i n g s o f t h e i n t e ll i g e n t i n f o r m a ti o n p r o c e s s 吨 l a b o r a t o ry , t h e p a p e r d e s i g n e d a n d i m p l e m e n t e d a b l o g s e a r c h p r o t o t y p e s y s t e m b l o g b e e . b y u s i n g t h i s p r o t o t y p e s y s t e m , r e s e a r c h e r s c a n e x p e d i e n t l y b u i ld f u ll - t e x t i n d e x o n a g i v e n b l o g p o s t d a t a s e t , r a n k b l o g p o s t a c c o r d i n g t o t h e i r d e g r e e o f f a m e , a n d p e r f o r m f u l l - t e x t r e t r ie v a l o n t h e b l o g p o s t d a t a s e t v i a k e y w o r d s e a r c h . i n o r d e r t o e v a l u a t e t h e u s a b i l i t y o f t h e p r o t o t y p e s y s te m , t h e p a p e r p e r f o r m e d a s e r i e s o f s e a r c h r e s u l t r a n k i n g e x p e r i m e n t s . t h e r e s u lt o f t h e e x p e r i m e n t s p ro v e d t h a t t h e p r o t o t y p e s y s t e m c a n e ff e c t i v e l y m e r g e t h e d e g r e e o f f a m e r a n k i n g a n d d e g r e e o f k e y w o r d - q u e ry re l e v a n c e a n d g e n e r a t e a s u p e r i o r o v e r a l l r a n k i n g r e s u l t . t o c o n c l u d e t h e p a p e r , t h e a u t h o r c o n c e i v e d t h e p o s s ib l e f u tu r e o f t h e b l o g s e a r c h r e s e a r c h . k e y w o r d s : w e b l o g , s e a r c h e n g i n e , i n f o r m a ti o n r e t r ie v a l , b l o g r a n k i n g , b l o g b e e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意如下各项内容: 按照学校要求提交学 位论文的印 刷本和电子版本; 学校有权保存学位论文的印刷本和电 子 版，并采用影印、缩印、扫描、数字化或其它手段保存论文:学校有权提供目录检索以及 提供本学位论文全文或 者部分的阅览服务:学校有权按有关规定向国 家有 关部门 或者机构 送交论文的复印 件和电 子版; 在不以 赢利为目 的的前提下， 学校可以 适当复制论文的 部分 或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 躺 ” 7 年 t- 月 ( s 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书 。 指导教师签名:学位论文作者签名: 多笛 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内 部 5 年 ( 最长5 年， 可少于6 年) 秘 密 1 0 年( 最 长t o 年 ， 可 少 于10 年 ) 机 密 2 0 年 ( 最 长2 0 年， 可 少 于2 。 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文，是 本人在导师指导下， 进行研究 工作 所取得的 成果.除文中已注明引用的内 容外， 本学 位论文的 研究 成果不 包含任 何他 人创作的、已公开发表或者没有公开发 表的 作品内容。 对本 论文 所涉及的 研究 工作做出 贡献的个 人和集体， 均已 在文中以明 确方式 标明。 本学 位论文原 创性的法律责任由本人承担。 学 位 论 文 作 者 签 名 :,临 71 07 7 年 s a i 8 日 第一章 综述 第一章绪论 1 . 1 研究背. 1 . 1 . 1 博客搜索排序问题的研究价值 面向博客空间的 搜索结果排序问题是w e b 数据挖掘研究方向中的一个新兴 研究主题，其主要研究内容是在规模庞大的博客空间中为有特定信息需求的搜 索用户优选出最能够满足需求的信息，如符合特定内容主题的博客文章或博客 站点等。 尽管在当前面向整个万维网的搜索结果排序理论己经相对成熟，专门针对 万维网的子集博客空间 进行搜索结果排序研究仍然是有价值的，这主要是因为 博客站点与博客空间具有一些普通网站不具备的特点， 这些特点主要表现在以 下几方面: 博客空间的内容特点 调查显示，多数博客站点是作为博客作者自由表达个人思想的一种媒介而 设，由于不受统一、刻板的内容规范管控，其中常常会探讨一些传统商业网站 中几乎涉及不到的问 题，如相对迅捷的地方性新闻 消息， 某种产品的质量评价， 针对某公司信誉评价等， 而诸如此类的文章内 容显然能 给搜索用户带来很多 指 导性信息。因此，博客空间中的内容非常有挖掘价值。 博客空间的结构特点 从单个博客站点来看，博客站点与传统网站不同之处在于，其网页代码结 构比较统一和规范， 不但更便于编程分析， 可提取的 排序特征也更多; 从整个博客空间来看，因为博客站点通常由单个博客作者维护，博客空间 中的链接结构既体现了 信息之间的关系，也在一定程度上体现了 人与人之间的 关系，如某些链接反映文章之间的推荐关系，而另一些链接则体现博客作者之 间的推荐关系等等。 第一章 综述 总之，博客站点的结构特点为搜索结果排序提供了更多方便。 博客站点的内容组织特点 博客站点另一特点就在于它的内容组织方式。与传统网站不同，博客站点 中的文章均按照发表时间呈线性列表方式排列，且每篇文章都被标以发布时间， 这种统一规范的内 容组织方式使得对博客 文章的编程抓取相对便利。 从另一个角度看，由于人们通常更偏爱较新发布的信息，博客文章发布时 间也可作为一项重要的排序特征使用。 总起来说，从博客空间中挖掘出的知识能给许多人带来实惠。 若能够针对 博客空间的特点设计出更好的博客搜索结果排序方法，将能够从博客空间中挖 掘出传统万维网搜索无法获取的新知识。 1 . 1 .2 博客站点与博客空间简介 为了后文讨论的方便，首先对博客站点与博客空间的相关背景知识做一些 简单介绍。 博客站点的定义 博客 【 1 ( w e b l o g ) 源自 英文词组， e b l o g ， 通常简称为b l o g ， 一般由 单 个 作 者在其上以非正式的日 记式的文章公开发表他们的思想，评论或日 常琐事。 博 客站点的内容更新频率通常比一般网站更高，其具体内容通常为博客作者的个 人知识的映射.除这些基本特点外，一个典型的博客站点一般具有以下一些不 同于一般网站的特点: . 包含一系列标注了发布日期的 文章， 它们通常由一个固定的作者编写 . 文章一般按反时间顺序排列，较新发布的文章位置更靠前 . 每篇文章都拥有唯一固定的超链接地址，以方便其它网页引用 . 采用固定的网 页模版发布文章， 页面结构比 较规范 . 在网站首页设置固定的信息栏以 显示文章存档和友情链接等信息 . 在文章结尾处提供评论机制以鼓励读者反馈 . 提供引 用 通告机制( t r a c k b a c k ) 供其 它 博客 站点就本站文章 做进一 步 讨 论 . 通过 r s s内容聚合机向其它内 容网站提交本站的文章更新信息 第一章 综述 擎a r c h i e ，此搜索引擎可检索所有f t p服务器上可公开访问的资源，并向 用户 提供查询服务. 同 年， t i m b u rn e r s - l e . 发明了 万维网， 成为h y p e r te x t 概念最为 成功的 应用， 也促使越来越多的 信息以 超文本标记语言网 页( h t m l -h y p e r te x t m a r k u p l a n g u a g e ) 的 形式 发 布， 而网 页之间则 使 用 超 链接 互联. 1 9 9 3 年， m a tt h e w g r a y 编写了 第 一 个w e b 挖掘 机 器 人， a n d e r e r ， 并 借 此建 立了 第一 个面向， 7 e b 的搜索引擎w a n d e x o 1 9 9 4 年， b r i a n p i n k e r t o n 发布了 第一个支持全文检索的w e b 搜索引 擎w e b c r a w l e r e l y c o s , i n f o s e e k , e x c it e 和a l t a v i s ta 等紧随 其后. 1 9 9 8 年， 斯 坦 福 大 学的 两 位 博 士 生l a r r y p a g e 和s e r g e y b r i. 提出p a g e r a n k 超 链 接 分 析 模 型并 将其 应 用于g o o g le 搜 索引 擎的 网 页 排 序 ， 最 终获 得了 巨 大的 商 业成 功。 g o o g le 也因 此 成为 当 代 搜 索 引 擎的 代 表。 搜索引擎的主要功能 对多数用户而言， 搜索引 擎的主要作用有以 下几种 司 : . 网址导航 随着新网站的不断增加， 通过记忆网站首页网址或查询网站目 录的方式访 问某些公司或机构的网站已不现实，而搜索引擎则能够起到网址导航的作用。 通常情况下，只需在搜索界面输入诸如 i b m, mi c r o s o ft这样的公司名称，即可 得到对应的公司首页网址; . 信息查询 许多时候人们需要查询一些实用但非频繁使用的信息，如新闻背景，百科 常识，列车车次等信息时，借助搜索引擎通常是成本较低的一种选择; . 辅助日 常事务 对于某些科研、技术人员， 为解决某一问 题，常常需要参考许多同 行的 研 究工作。而随着网 络的发达， 越来越多的人将自己的研究工作公开在网上供其 他人分享。为快速获取这些信息，几乎随时都要借助搜索引擎，这就使搜索成 为一种日 常事务。 与早期的 搜索引擎相比， 今天的搜索引擎在挖掘覆盖度、更新速度、 排序 质量和 用户界 面 上都 取得了 长足的 进步。 截至2 0 0 6 年， g o o g l e 已 索引了 约2 0 0 亿规模的网 页. 其他大型搜索引擎如y a h o o 和m s n搜索的 索引网页数也达到了 相当之规模。除了 通用搜索引擎之外，各种面向 具体信息主题的专门 化垂直搜 索引擎也不断涌现出来，如学术搜索、新闻搜索、购物搜索、博客搜索等。总 第一章 综述 之， 搜索引擎已 经深刻地改变了 人们获取信息的方式，逐渐成为人们的日 常工 具。 1 . 1 .4 博客搜索的意义 尽管目 前主流的通用搜索引擎已 成为人们在网上获取信息的首选工具，但 诸如博客搜索这样的垂直搜索引擎仍然有存在的必要性。 相关 调 查 表明， 博客 搜索需 求 主 要有两 方 面， 相关 信息 搜索 和 概念搜索 刀 。 相关信息搜索是指在博客空间中跟踪关于某个命名实体的多方面资料，以 便获 得关于该实体的比较详尽的知识:概念搜索是指就某一给定的概念或主题，查 找聚焦于此主题的博客站点或博客文章。 更进一步，与普通网页搜索用户相比，博客搜索用户更关注当前正在发生 的事件。 在浏览搜索结果行为方面，博客搜索用户与普通网页搜索用户是类似 的，他们通常只对搜索结果列表中的前几项感兴趣。通过对大量查询请求进行 归类发现，与普通网页搜索用户相比，博客搜索用户表现出更多对新闻、娱乐 和科技等主题信息的关注。 由此可见，尽管一般网页空间中的信息己经很丰富，人们仍然有在博客空 间中搜索的需求，而传统的通用搜索引擎尚不能很好地满足这类需求，故博客 搜索研究的发展前景依然比较广阔。 1 . 2 博客搜索学术研究现状 1 .2 . 1 国内外学术研究现状 近年来博客站点的迅猛发展不仅吸引了 包括传媒、广告在内的产业界的关 注，也逐渐引起了学术界的重视。一篇关于博客信息检索研究的调查报告指出， 博客的迅速发展及其带来的改变吸引了 很多商业上的关注，在这种关注之下， 与博客站点和博客空间相关的学术研究也如雨后春笋般不断涌现出来。当前， 相关研究己 经触及诸多领域， 从种族学、 人口 统计学等社会学研究领域到一些 面向博客空间的信息流数学模型研究等科学研究领域。特别是在以数值计算为 第一章 综述 基础的博客分析流派中，传统和新兴的信息检索技术都被应用到博客之上，形 成了 一 个日 趋活跃的 面向 博 客 空间 信息 检 索 研究领域. 2 目 前，博客信息检索研究领域中主要的代表性活动有以下几项: .w w e ( w o r k s h o p s o n th e w e b l o g g in g e c o s y s t e m ) 8 一 年 一 度的w o r k s h o p s o n th e w e b lo g g in g e c o s y s te m会 议自 2 0 0 4 年 起开办， 截至今年已连续举办三年。随着博客社区不断进化，博客站点也得到越来越多 的曝光率，博客写作者的数目 不断 增加， 单个博客作者的贡献能力和影响力也 逐渐变得更加显著。博客空间的动态特性在引用链接，博客友情链接，文章评 论， 文章类别标签，共同的兴趣和主题群组方面得到了充分的体现，吸引了许 多学术和商业领域的研究者的关注。目 前主要的相关领域包括文本挖掘，社会 网络分析，计算语言学，商业与市场智能，图书馆科学，分类度量学，图论和 数据可视化等。 w we会议的主要目的是将来自多个领域的研究者聚集起来， 在商业和学术 的双重背景下共同探讨博客空间这样一个技术、社会和文化影响力日 益扩张的 领域中的种种问题。 . c a a w( c o m p u t a t i o n a l a p p r o a c h e s t o a n a l y z in g we b l o g s ) 9 美国 人工智能协会主办的c o m p u ta t i o n a l a p p ro a c h e s t o a n a l y z i n g w e b l o g s 2 0 0 6年春季研讨会，其目 的是将不同 领域的研究者聚集起来共同 讨论如何用计 算性方法分析博客空间的问 题。 2 0 0 7 年开始举办的i c ws m会议， 此会议是原wwe会议， www与 a a a 主办的c a a w会议的结合。此会议的目 的是鼓励多个主题领域的研究者共同交 流，并将他们的研究结果相互融合。 . i c ws m ( i n t e m e t c o n f e r e n c e o n w e b l o g s a n d s o c i a l m e d i a ) 1 0 2 0 0 7 年开 始举办的i n t e rn e t c o n f e r e n c e o n w e b l o g s a n d s o c i a l m e d i a 会议是 原 wwe会议， www 会议和 c a a w 会议的结合。 其举办目 的是鼓励来自 不 同领域的研究者共同交流。 i c ws m会议源于两大重要学术活动: 与www会议 协同 举办的 一年一度的ww e 系列研讨会( w w e 2 0 0 6 , ww e 2 0 0 5 , w w e 2 0 0 4 ) 和由a a a 】 组织的c a a w春季研讨会。 i c w s m会议旨 在将来自 各 个不同 学 科 领域 ( 计算 机科学， 语言 学， 心理学， 统计 学， 社会学多 媒体 与 语义网 络技 术 ) 的 研究 者们聚 集起来， 通过 观点的 碰撞 促成新的研究思路。此会议中有关博客信息检索的研究主题包括:博客的影响 第一章 综述 力衡量，博客的相关度排序，基于博客的网页排序，网络爬虫和网页索引技术， 博客文章分类，博客作者性别与年龄的识别，博客空间中的垃圾信息过滤等。 . t r e c b l o g t r a c k 川 自2 0 0 6 年起， 信息 检 索 领 域内 最为 著名 的t r e c 会议 也 设 立了 专门 的 b l o g t r a c k ， 其主要目 的在于探索博客圈中的信息获取模式。 t r e c是一系列与信息 检索相关的 研讨会，自2 0 0 6 年 起， t r e c启 动了 一 项新的b l o g t r a c k ，目 的 在 从博客文章中抽取作者观点，未来还可能包括观点倾向性辨识等研究主题;而 2 0 0 7 年的b l o g t r a c k 还 会 提出 博客f e e d 搜 索 ( b lo g f e e d s e a r c h ) 的 任务， 其目 的 在于通过主题关键词搜索定位相关的博客f e e d . 根据 b l o g t r a c k 的 描述，博客 搜索用户通常希望通过 一个指定的主题辨识一系列内 容相关的 博客 f ee d ，以 便 订阅这些f e e d ，并在未来定期阅览它们。这项任务通常表现在以下两种情形: 筛选: 用户将经常搜索的 主 题内容之搜索结果订阅 到他们的r s s 阅读器中: 取精: 用户搜索一些 拥有固 定兴趣中 心的 博客站点， 并将其f e e d 订阅到他 们的r s s 阅读器中。 研究者们推荐在2 0 0 7 年的t r e c中将后一种情形作为 研究任务加入。 这项 任务可以 如下方式定义: 给定一个兴趣领域x ， 搜索系统分析所有己知博客f e e d 在一定时间段中的内容， 找出与x相关并可能吸引用户兴趣的f e e d ，并向搜索 用户推荐。 以上均为国外科研机构或组织针对博客信息检索的研究工作，相比 之下， 国内在博客空间信息检索方面的研究相对不足，在中国学术期刊全文数据库中 检索“ 博客” ， 涉及的 研究 成果集中在传媒学和教育学 等社 会科学领域。 1 2 1 . 2 .2 博客搜索产品的发展现状 将博客空间作为一个信息源进行研究的具体门类有很多，包括垃圾信息辨 识、博客门 类辨识、文章情态分析、文章观点抽取等等，但对最终用户而言最 具实用价值的当属以 现代信息 检索技术为背景的 博客 搜索技术。 相关研究指出，尽管在针对整个万维网的网页搜索中，通用网页搜索引擎 已 经能够很好地适应多数的需要， 但在面向 博客空间的信息检索任务中， 仍然 有很多可以深入挖掘的工作，这促使人们研究专门面向博客空间的搜索技术。 目 前，领域内比较有特点的博客搜索服务有以 下几家: 第一章 综述 本文的主要工作有以下几方面: 第一章主要分析博客网 站与博客空间的概念和基本特点，并在深入讨论博 客空间信息检索需求的基础上，提出博客信息检索和搜索排序的问题，界定本 文的研究内容。 第二章介绍w e b 信息检索和搜索引擎的相关背景知识， 包括互联网的图模 型，搜索引擎的基本组成和工作原理，各类基于链接的排序算法和基于内容相 关度的排序算法，并分析这些排序算法各种的专长和不足之处。同时介绍一些 常见的用于评估信息检索和排序算法性能的指标。 第三章讨论博客搜索系统的相关内容，包括博客搜索系统的典型结构及其 整体设计思想，各组成部分的主要功能及其相互关系，专门针对博客特点的排 序算法等内容，以及用于博客搜索实验的原型系统的设计实现。开发该系统的 主要目 的是为在含有大量博客文章的数据集上进行检索和排序的研究与实验提 供方便。 第四章原型系统上进行的搜索排序实验及其结果分析。 论文的最后对全文研究工作进行总结，并探讨进一步的研究方向。 第二章 w e b 信息检索相关工作介绍 第二章信息检索相关工作介绍 博客空间是万维网的一个子集，因此博客搜索研究在很多方面都将得益于 传统w e b 信息检索和网 页搜索引擎方面的研究 2 . 1 搜索引单的基本理论 2 . 1 . 1 搜索引擎的工作原理 图2 . 1 搜索引 擎的 主要 组成部分 搜索引擎并不直接搜索万维网，而是对预先建立好的本地网页索引库进行 检索。实际意义上的搜索引擎，通常指的是采集了万维网中上千万甚至数十亿 张网页并对网页中的重要词汇进行索引， 并建立索引 数据库的全文搜索引擎。 用户查找某个关键词的时候，所有在页面内 容中 包含了该关键词的网页将作为 搜索结果列表中的单元返回，在经过复杂的算法进行排序后，这些结果将按照 第二章 w e b 信息检索相关工作介绍 与搜索关键词的相关度高低，依次排列。 从组成模块上看， 搜索引擎主要由网 页抓取、预处理、检索和用户界面等四 大模块组成。 如图2 . 1 所示， 搜索引 擎的 工 作流 程大 致 如下: 网 络抓 取器 ( w e b c r a w l e r ) 从 互 联网 上 抓取网 页，把网 页 送入原 始网 页 数据 库( r a w w e b p a g e d b ) ; 系 统从 网 页 数据 库中 得 到 文 本信息， 并由 索引 模 块 ( i n d e x e r ) 建 立全文 索引 ， 形 成索引 数 据库 ( i n d e x e d w e b p a g e d b ) ; 另 一方 面由 链 接提取器 ( h y p e r l i n k e x t r a c t o r ) 对网 页 数据 库 进行 链 接 提取， 把网 页中 的 超 链 接 信 息 ( 包括链 接文本 、 链接目 标 等信息 ) 存入链接数据库， 作为网页评级的依据。最后，当用户提交查询请求给网页服 务器时，服务器在索引数据库中查找相关网页，同时结合网页评级信息，把查 询请求和链接信息结合起来对搜索结果进行相关度评价，按照相关度进行排序， 并将搜索结果组织为有序的文档列表返回给用户。 2 . 1 .2 搜索引 擎的组成模块 网页抓取模块 搜索器的功能是在万维网中漫游，发现和搜集信息。它常常是一个计算机 程序，日 夜不停地运行。它要尽可能多、 尽可能快地搜集各种类型的 新信息， 同时因为万维网上的信息更新很快，所以还要定期更新已经搜集过的旧信息， 以 避免死连接和无效连接。目 前有两种搜集信息的策略: l . 从 一 个 起 始u r l 集合开 始， 顺 着 这些u r l 中的 超链接 ( h y p e r li n k ) ， 以 广 度优先、深度优先或启发式方式循环地在万维网中发现信息。这些起始u r l可 以 是 任意的u r l ， 但常常是 一 些非 常 流 行、 包 含很多 链接的 站点 ( 如y a h o o l ) . 2 . 将w e b 空间按照域名、 i p 地址或国 家域名划分， 每个搜索器负 责一个子 空间的穷尽搜索。搜索器搜集的信息类型多种多样，包括 h t m l , 1 m i l , n e w s g r o u p 文 章、 f t p 文 件、 字处理 文 档、 多 媒 体信息。 搜索器的 实 现常 常 用分 布式、 并行计算技术，以 提高信息发现和更新的 速度。商业搜索引擎的 信息发 现可以达到每天几百万网页。 预处理模块 预处理模块的主要功能是理解搜索器所搜索的信息，从中抽取出 索引项， 用于表示文档以及生成文档库的索引表。 第二章 w e b 信息检索相关工作介绍 索引项有客观索引 项和内 容索引项两种: 客观索引 项与文档的语意内容无 关，如作者名、 u r l 、更新时间、 编码、长度、链接流行度等等;内 容索引项 是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可 以 分为单索引 项和多 索引 项( 或称短语索引项) 两种. 单索引 项对于 英文来讲是英 语单词， 比 较容易提取，因为 单 词之间有天然的分隔符 ( 空 格 ) ; 对 于中 文等连续 书写的语言，就必须进行词语的切分。在搜索引擎中，一般要给单索引项赋与 一个权值，以表示该索引项对文档的区分度，同时用来计算查 询结果的相关度。 使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计 法、 概 率法和语言学 法。 索引 表一 般使用某种 形式的 倒 排 表 ( i n v e r t e d l i s t) ， 即由 索引项查找相应的文档。索引表也可能要记录索引项在文档中出 现的位置，以 便检索器计算索引项之间的相邻或接近关系。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必 须实现实时索引，否则将无法跟上信息量急剧增加的速度。索引算法对索引器 的性能 ( 如大规模峰值查询时的 响 应速度) 很大的影响. 一个搜索引 擎的 有效性在 很大程度上取决于索引的质量。 检索器 检索器的功能是根据用户的查询在索引库中快速检出文档， 进行文档与查 询的相关度评价， 对将要输出的结果进行排序，并实现某种用户相关性反馈机 制。检索器使用的信息检索模型有许多种，后文中将对这些信息检索模型作进 一步介绍，此处不再赘述。 用户界面 用户界面的作用是接受用户查询并显示查询结果，其主要的目 的是方便用 户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、 及时的信息。用 户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。 搜索的处理过程是对关键字进行匹配的过程，首先对用户输入的搜索关键 字进行分析处理，然后在索引库中得到文档列表，并对文档列表进行扫描，来 与处理后的关键字进行匹配。 提取满足条件的网页，然后计算网 页和关键词的 相关度，根据相关度的数值将前 n篇结果返回给用户。如果用户查看下一页结 第二章 w e b 信息检索相关工作介绍 果， 重新进行搜索， 把排序结果中 在第n + l 到2 、的网 页组织返回给用户， 依 此类推。其处理流程如图2 . 2 所示。 图2 .2 搜索引擎检索过程图 2 . 1 . 3 搜索结果排序的基本策略 对万维网上数以亿计的网页进行排序是件非常复杂的工作， 其中一个关键 性问题就是用哪些特征信息来客观衡量每张网页在整个万维网中的重要程度。 评价网页排序质量的最终标准是人的主观判断， 而网页浏览者却是来自 各行业 的人，不同行业的人对同一内容的网页可能有截然不同的看法，同一内容的网 页对不同行业的人的实用价值也不尽相同，这就在客观上决定了不存在以网页 内容为核心的绝对评价标准。即便存在这样的标准，也需要大规模使用自 然语 言理解技术，而目 前这方面技术尚不成熟，大规模使用不仅成本过高，处理效 率也很难保证。 第二章 w e b 信息检索相关工作介绍 另一方面，网页排序模型还需要考虑针对搜索引擎的作弊行为。由于人们 普遍通过搜索引擎定位万维网上的重要网页， 那些在搜索结果列表中排名前列 的网页就会得到更多人的点击和浏览，这使得许多商家竞相通过针对搜索引擎 排序算法的特点调整自己的网站， 使搜索结果排序失去公正性。从这个角度看， 设计搜索排序算法时应尽量避免使用可人为捏造或篡改的信息作为排序特征。 总而言之， 搜索排序模型必须综合考虑多方面因素。只有尽可能利用那些 相对客观、计算机容易处理且网站经营者不容易操控的信息，才能对网页的重 要度做出 更为客观、公平的 评价。 网 页 排 序 算 法 可 分为 两 类， 一 类是 基 于 链 接 分 析的 网 页 排 序 算 法 ( 也可 称 为 与查询无关的网 页排序算法 ) ， 另一类是与查 询关键词相关的 排序算法. 前者是 为了估计一张网页在整个万维网中的影响力，后者是为了衡量网页与给定查询 关键词的匹配程度。 对搜索引擎而言， 这两类算法分别对应着两个处理步骤。 基于链接分析的网页排序不考虑具体的查询关键词，直接根据网页之间的链接 结构估计网页在整个万维网中的重要度或影响力，相当于一次粗排序;而与查 询关键词相关的排序算法则从经过粗排序后的网页数据集中按顺序筛选出与给 定关键词相关的网页子集，并根据查询关键词与网页内容之间的相关度再次排 序。 尽管对网页进行排序的策略相对直观， 但若希望得到高效的网页排序模型， 则必须在尽可能反映客观实际的人工标注数据上通过反复的实验才能实现。寻 找合适的排序模型对网页进行有效的排序归根究底是一个机器学习问题，从这 个角度看，欲提高网页排序的质量， 研究者需要做出两方面的努力:提出更好 的排序模型或者获取更能反映客观实际的训练数据。 下一节将对两类排序策略及其对应的代表算法进行详细介绍。 2 . 2 基于链接分析的网页排序 上一节曾 经提到，网页排序算法应尽可能利用那些相对客观、 计算机容易 处理且网站经营者不容易操控的信息进行排序，基于链接分析的网页排序算法 恰好能够满足这些要求。 首先，网页中的超链接是以 标准的语法表达的， 很容易 用机械的 方法识别; 第二章 w e b 信息检索相关工作介绍 其次，网页之间的超链接通常表达了一种导航或推荐关系，若许多彼此不 相关的网页上都出 现了指向同一网页的 链接， 便可以 很直观地认为这个被指向 的网页上含有一些重要的信息; 第三，超链接在一定程度上起到了引导浏览量的作用，若将网站的每个浏 览者的 行为看作一个沿网 页超链接随 机行进的 过程，则一个网页被其它网页链 接的总数越大， 在一个固定时间段内 可能来访的浏览者就越多; 第四，网站经营者不容易操控超链接信息。尽管他可以 在自己的网站上建 立许多指向自己网页的网页，却难以 低成本地操纵大量不相关的网站做同 样的 工作。 网页中的超链接信息因为具有以上这些优良 性质而得到很多排序算法的利 用，下面就对这类算法中的一些代表算法进行介绍。 2 .2 . 1 万维网的图模型 在深入剖析网页搜索排序的原理之前，需要首先对万维网的图论模型做一 简单介绍。 如图2 . 3 所示， 万维网是由 大量网页通过有向的超链接彼此相连而成， 若将万维网中的每个网页看作图中的顶点，同时将网页之间的超链接看作图中 的有向边，则整个万维网就被映射为一个有向图结构，如图所示。 在这个模型中，一个网页的出度被定义为该网页上所有指向 其它网页的超 链接的个数， 一个网页入度则定义为从其它网页发出的指向该网页的超链接总 数。例如，图中a网页的出度为2 ，入度为0 ; b网页的入度为3 ，出度为l a 图2 .3 万维网图模型示愈图 第二章 w e b 信息检索相关工作介绍 2 .2 .2 基于入度的排序算法 基于入度的算法是相对最为简单的一种基于链接的排序算法，其排序依据 就是某个网页被其它网 页链接的次数。 如果 将a网页指向b网 页的 链接看作a 对b的 投票，则基于入度的 排序算法也可看作是一种简单的民主 投票模型，得 到票数较多的网页排名也比 较靠前。以下是基于入度的排序算法的网页重要度 计算公式: r a n k a = l n d e g r e e ( a ) ( 2 . 1 ) 然而，基于入度的排序算法存在一些不可克服的缺点，即所有的投票都被 看作同等重要的， 会导致只重投票数量而不重投票质量。能够说明这一问题的 一个典型的例子就是:某个网站专门为其它网站制作网页模板，为了宣传自己 的站点，设计者在模板中加入了 此网站的首页地址，于是所有采用其模板的网 站中都会存在一些指向该网站首页的链接，这就使得该网站首页的入链接非常 多， 从而拥有很高的入度， 但这类首页通常并不含有大多数人都感兴趣的信息。 为了 解决 这一问 题， 研究 者 们提出了 一 些更 好的 排 序算 法， 如p a g e r a n k 和 h i t s等。 2 . 2 . 3排序算法 p a g e r a n k 2 0 网 页 排 序 算 法是由larry p a g e 和s e r g e y b r i n 于1 9 9 8 年提出的， 该模型的思想来源于学术文献的引文网络。在引文网络中，被引用次数较多的 文献通常被认为是高水平的 ， 且被高水平文章引用的文章被认为比 被低水平文 章引 用的 文章水 平更高. p a g e r a n k 将这 一思 想 应用到万 维网中 ， 网 页a指向 网 页b的 链接可被认为是网页a对网 页b的 一次推荐， 且推荐的“ 力度” 与网 页a自 身的r a n k 值成正比，与网页a网的总链接数成反比。 p a g e r a n k 网 页排序算法的网 页重要 度计算公式为: p r ( 助= 三 十 。 一 办艺 p r ( a , ) / o u td e g r* 再 ) ( 0 上述c g并没有反映出n d c g在提出的时 候的 第二点 文档所排的位置 越靠后，其重要性就越小，因此对于具有相同贡献值的文档，其所在的位置越 靠后，则其加在 c g上的 值应该越小。一个简单的办法就是在其贡献值上除以 其位置值的 对数函数， 这样就得到了d c g i : 二1= c g i if i b ( 2 . 8 ) 第二章 we b 信息检索相关工作介绍 需 要注意的 是 对于i 为1 的 情况不 取对数函 数， 因 为l o g ( 1 娜，同 样， 对于 i ( 2 .9 ) 为了便于比 较，需要把d c g进行归一化， 使得所有的值都在0 到1 之间， 因此在每一个位置上都除以 其最优排序时的d c g值。 形式化的表达为: 给定一 个根据某个排序计算出 来的d c g序列: d c c r -v l , v 2 , . . . , v t ( 2 . 1 0 ) 而根据最优排序计算出的d c g序列为: d c c - i l , 坛“ . ， 诊( 2 . 1 1 ) 最后，此排序对应的n d c g序列为: n d c c r - v , / i i , v 2 r l 2 , . . . , v d 4 ? ( 2 . 1 2( 2 . 1 2 ) 对于上述的例子，其最终的n d c g序列为: n d c g - ( 2 . 1 3 ) 第三章 b l o g b e e 博 客 搜 索原型系统 第三章 b 1 o g b e e 博客搜索原型系统 前面两章对博客网站的 特点、博客空间的发展现状、博客搜索的需求和相 关的理论、技术等进行了总结和回顾， 本章将主要针对博客搜索系统的特点展 开，首先介绍博客搜索系统的主要组成部分及其典型系统架构，然后介绍 b l o g b e e 博 客 搜 索 原型 系统的 架构设 计 ， 模 块设 计和具 体实 现等内 容。 3 . 1 博客搜索系统的组成 博客搜索系统与通用网页搜索系统很类似，但由 于博客站点和博客空间具 有一些的独特属性， 博客搜索引 擎的 各个组成模块也有一些通用搜索引擎所不 具备的特点。本节就对博客搜索引擎的独特之处做一简单介绍。 3 . 1 . 1 博客搜索系统的典型架构 如图3 . 1所示，一个典型的博客搜索引擎大致由博客文章抓取( b l o g c r a w l e r ) ， 命 名 实 体 词汇 挖掘 ( v o c a b u l a r i e s m i n e r ) ， 博客文章 预处理 ( p r e p r o c e s s i n g c o m p o n e n ts ) ， 文 本 检索引 擎 ( t e x t s e a r c h e n g 加 e ) ， 用户 界面 (us e r i n t e r f a c e ) 等五 个主要功能模块组成。 图3 . 1典型博客搜索引 攀的系统结构 2 6 1 第三章 b i o g b e e 博客搜索原型系统 五大功能模块的主要作用如下:博客文章抓取模块负责将博客空间中的博 客文章下载到本地:语词挖掘组件负责在万维网中收集流行词汇并利用所得的 词汇表辅助对博客文章的内容分析;预处理模块负责博客搜索结果排序及其它 一 些对搜索结果进行分类和过滤的工作。 不难看出，博客搜索系统与一般的网 页搜索系统有很多相似之处，但也有一些明 显的不同。 下面将对博客搜索系统组成和结构上的特点做进一步介绍。 3 . 1 . 2 文章预处理模块 参考文章