（计算机应用技术专业论文）基于用户点击行为的数字图书搜索系统研究与实现.pdf

浙江大学硕士学位论文摘要 摘要 数字图书馆( d i g i t a ll i b r a r y ) 在世界很多国家受到了高度关注，并取得 了迅猛发展，已经成为人们获取信息与知识的重要途径。数字图书搜索则是数字 图书馆必须提供的支撑性服务，本论文针对数字图书搜索阻及搜索结果排序问题 做了深入研究与开发，以便读者能够在海量数字图书资源中快速发现他所需要的 数字图书。 传统数字图书搜索建立在关系型数据库之上，采用关键词的简单匹配来判别 相关程度，不能反映图书的质量信息和受关注程度，缺乏有效的综合排序机制， 不能综合利用多种排序依据。 本文的主要工作如下：一、利用数字图书馆门户丰富用户使用日志数据，提 出两个点击流上的随机行走算法：b o o k r a n k - - 基于访问关联图的图书评分算法， 提供图书相关性排序功能；q u e r y c l u s t e r _ 基于查询一阅读行为的查询词聚类算 法，利用读者对检索结果的隐式反馈信息，提供对查询词的聚类功能。二、抓取 互联网上的图书评分相关数据，将其整合进我们的图书搜索排序系统中去作为搜 索结果排序的一个重要依据。三、在查询词聚类的基础之上，实现一种多排序依 据集成方法，针对每类查询词，综合利用从访问关联图得出的图书相关性排序、 互联网上的图书评分以及文本相似度这三种信息源，形成最终的搜索结果排序。 四、开发完成相应的数字图书搜索系统，部署在高等学校中英文数字图书合作计 划( c a d a l ) 的网站上，根据用户在实际使用中的反映，与传统数字图书搜索相 比，新搜索系统的搜索结果排序更加合理。 关键词：数字图书馆，关联图，b o o k r a n k ，查询词聚类，多信息源集成 浙扛大学硬士学位论文 a b s t r a c t m a n yd e v e l o p e da n dd e v e l o p i n gc o u n t r i e so v e rt h ew o r l dh a v ep u tl a r g ee f f o r t s o nt h ed e v e l o p m e n to fd i g i t a ll i b r a r ys i f i t h em i d1 9 9 0 s d i g i t a ll i b r a r yh a sb e c o m e a ni m p o r t a n tm e a n sf o rp e o p l et oa c c e s sd e s i r e dk n o w l e d g ea n di n f o r m a t i o n d i g i t a l b o o ks e a r c hi st h es u s t a i n a b l es e g v j c et h a td i g i t a lh l o r a r ys h o u l dp r o v i d e t h i sp a p e r e x c l u s i v e l yf o c u s e so nt h ed e v e l o p m e n to fd i g i t a lb o o ks e a r c ha n de x p l o r e si nd e p t h t h ep r o b l e mo fs e a r c hr e s u l t s 瑚n l 由瑶s ot h a tt h ev i s i t o r so fd i g i t a ll i b r a r yc a nq u i c k l y f i n db o o k ss a t i s f y i n gt h e i rn e e d si nt h em a s s i v eb o o kr e s o u r c e s t h et r a d i t i o n a ld i g i t a lb o o ks e a r c hi sb a s e d0 1 1t h em a t c h i n gt e c h n i q u e so f r e l a t i o n a ld a t a b a s e i tc a no m yf i n do u tt h er e l e v a n tb o o ke n t r i e sw h i c hc o n t a i nt h e k e y w o r d st h er e a d e re n t e r e d m o r e o v e r , i tl a c k se f f e c t i v eb o o kr a n k i n gm e c h a n i s mt o s o r tr e s u l t so f r e l e v a n tb o o k s ，a n di g n o r e st h ep o p u l a r i t ya n dq u a l i t yo ft h e s eb o o k s t h em a i nw o r ko ft h i sp a p e ri ss u m m a r i z e da sf o l l o w s ：1 e x t r a c tb e h a v i o r i n f o r m a t i o no fu s e rc l i c k i n go i lb o o k so u to ft h ea c c c s sl o g s , c o n s t r u c tc o r r e l a t i o n g r a p ho fb o o k s r e a db yu 娜。a n du s er a n d o mw a l ka l g o r i t h m 幻r a n kt h eb o o k sb y r e l e v a n c e 2 e x t r a c tq u e r yw o r d sa n db o o kr e a d i n gr e c o r d so u to ft h ea c c 豁sl o g s , a n d u t i l i z et h ec l u s t e r i n ge f f e c to fr a n d o mw a l k st oc l u s t e rq u e r yw o r d s 3 c r a w lb o o k s c o r ed a t af r o mw a l l - k n o w n0 1 1 j n eb o o k s t o r e so nt h ei n t e r a c t , w h i c ha c ta sa n o t h e r i m p o r t a n ti i i e i l s u i f o rb o o kr a n k i n g 4 p r o p o s ea r ta p p r o a c ht oi n t e g r a t i n gm u l t i p l e b o o kr a n k i n gi n f o r m a t i o nf o re a c hc l a s so fq u e r y t h ef i n a lr a n k i n gl i s to fr e s u l t so f b o o ks e a r c hi sg a i n e db yf h s i n gt e x ts i m i l a r i t y , b o o ks o o r ed a t af r o mo n l i n eb o o k s t o r e s a n db o o kn m t d n gf r o mc o r r e l a t i o ng r a p h 5 w eh a v ed e v e l o p e dad i g i t a ib o o ks e a r c h s y s t e ma n dd e p l o y e di t i nt h ec a d a lp o r t a lu s i n gt h ea b o v ea l g o r i t h m sa n d t e c h n i q u e s u s e r sh a v er e p o r t e dt h a tt h en 昏vb o o ks e a r c hs y s t e mp r o v i d e st h em o r e r e a s o n a b l er a n k i n go fs e a r c hr e s u l t sc o m p a r e dw i t ht h eo r i g i n a lb o o ks e a r c hm o d u l e k e y w o r d s ：d i g i t a ll i b r a r y , c o r r e l a t i o ng r a p h , b o o k r a n k , q u e r yc l u s t e r i n g ， e n s e m b l eo fm u l t i p l ei n f o r m a t i o ns o u r c e s n 浙江大学硕士学位论文 图目录 图目录 图2 1p a g e r a n k 的一个简单示饲1 2 图2 2h i t s 的一个简单示例1 3 图3 1 使用日志中提取的查询阅读序列2 4 图3 2 查询一阅读行为示例2 5 图3 3b o o k r a n k 与q u e r y ( ；l u s t e r 的数据构建比较2 7 图4 + l 互动出版网的书评页面。3 0 图4 2 当当网的书评页面3 0 图4 r 3 亚马逊卓越网的书评页面3 1 图4 4 整合图书评分数据基本框架图。3 2 图4 5l u c e n e 索引基本结构。3 5 图5 1 图书搜索系统整体架构4 2 图5 2 图书有效阅读记录提取4 6 图5 3b o o k r a n k 计算的任务块分配和磁盘文件映射4 8 图5 4 书评页面抓取程序结构4 9 i u 浙江大学硕士学位论文表目录 表目录 表4 1 提取出的图书评分数据。3 l 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 杰j 、j签字日期：沙略年多月7 日 学位论文作者签名：名一t 7 签字日期：沙略年多月7 日 学位论文版权使用授权书 本学位论文作者完全了解澎江盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝望盘生可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 表、。j 签字日期：印哆年f 月7 日 导师签名： 签字日期：2 一眵年6 月7 日 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 课题背景 2 l 世纪是数字化的时代，随着计算机技术、海量存储技术和网络技术的飞速 发展，信息载体的数字化和信息传播的网络化得到了空前的深化，图书馆的数字 化成为一个必然趋势。数字图书馆在世界很多国家受到了高度关注，并取得了迅 猛发展，已经成为人们获取信息与知识的重要途径。 国家计委、教育部、财政部于2 0 0 2 年9 月将“中英文图书数字化国际合作 计划( 简称c a b a l ) 斗列为“十五期问“2 l l 工程”公共服务体系建设的重要 组成部分c a b a l 与冉中国高等教育文献保障系统( c a l i s ) ”一起，共同构成中 国高等教育数字图书馆的框架h 1 。c a d a l 项目目前已经数字化1 0 0 多万册中英文 图书。其中的英文图书有效扭转了国内高校和科研机构英文原版图书资源严重不 足的状况；中文图书资源突出高校教学科研的需要，兼顾保存和传承我国优秀传 统文化的要求嘲。c a d a l 项目形成了一套成熟的支持百万册数字对象制作、管理 与服务的技术平台；探索了多媒体、虚拟现实等技术在数字图书馆中的应用。 百万册数字图书馆服务平台是一套具有集成能力、可灵活扩展、可定制的 “数字图书馆门户构建平台”毗及其它与数字图书馆相关的一系列应用系统。百 万册数字图书馆服务平台本身提供了一批基础设施，如用户数据访问，元数据访 问，数字对象访问，日志访问和认证授权信息获取跚。普通图书馆采用该平台就 可快速构建出百万册级别的数字图书馆服务平台，通过与自身资源和其他应用系 统的集成，向不同地区不同文化程度的读者提供相适应的数字图书馆服务。普通 图书馆无需独自重复开发一套系统平台，只需要在百万册数字图书馆服务平台基 础之上，在“以用户为中心”、“服务至上”的理念的驱动下专注于建设特色 馆藏，研发特色应用，就可为读者提供一站式、个性化、全面的服务，使读者能 够方便快速地从多种资源与应用中获取自身所需的信息口1 。 本论文即是以百万册数字图书馆服务平台为背景的一个子课题，目的在于研 折江太学碗士学位论空弟i 章堵电 究和开发适合海量数字图书资源服务平台的数字图书搜索以及搜索结果排序技 术，使得读者能够在海量数字图书资源中快速发现他所需要的数字图书，充分提 高数字图书馆的数字图书资源服务效率。 1 - 2 研究意义 c a d p t l 项目目前已经数字化了t 0 0 多万册中英文图书，而且这个数目还在不 断增加中，如何有效的利用这些丰富而宝贵的资源让数字图书馆读者能够更充 分的利用他们就显得非常重要。数字图书搜索是百万册数字图书馆服务平台中最 为基本，但也是最为重要的一个功能模块。他使得读者能够很好地找到赣要舶图 书资源，是数字图书馆服务平台的“第一线8 。 现有的图书资源统一搜索系统是基于关系数据库的简单匹配查找，只能过滤 出与读者所输入的关键字相匹配的相关图书条目，并没有使用有效的图书排序机 制以提高读者检索的满意度，而且性能和用户体验不佳。c a d a l 门户去年向读者 推出了“c a d a l 服务改进意见”的问卷调查，在调查反馈结果中，“对图书资源统 一搜索进行改进即是据的最多的意见之一。本文便是针对数字图书搜索以及搜索 结果排序问题的研究与开发。 c a d a l 门户已经对外服务很长时间，积累了大量的用户使用日志数据信息， 车文将提出基于用户点击流信息挖掘的图书相关性排序掉法和查询词聚类算法， 利用它们可以报好地提高图书搜索的质量。 传统的基于关系数据库的图书元数据检索只能保证精确性，但是不能提供排 序功能，而且性能较差。本文将使用基于文本相似度的检索算法来检索图书元数 据，布仅提供基于文本相似度的排序功能，还能提高检索性能提供按字段的权 值设置功能。 传统的数字图书馆是一个干日对静态和封闭的系统。本立将提出使用互联网上 的关于图书的数字资讴信息来瞽补这一不足，抓取互联网匕的图书评分相关信 息，将其整合进我们的图书搜索系统中去。 我们最后综合利用文本相似度、网络书店图书评分以及使用b o o k r a n k 算法 2 浙江大学硕士学位论文 第l 章绪论 得出的图书相关度这三种信息源，形成最终的搜索结果排序，提供更好的图书搜 索排序质量，这将使得数字图书馆用户更加容易的找到需要的图书，提高数字图 书馆的资源利用效率，使数字图书馆发挥更大的作用。 1 3 本文的主要工作 首先，本文研究现有的与信息检索相关的技术和算法，研究w e b 使用挖掘技 术以及其在信息检索、个性化推荐方面的应用。这里面包括传统的基于文本内容 相似度的检索排序算法、基于链接结构的排序算法以及基于用户使用行为信息的 检索改进算法。然后，分析数字图书馆中现有图书资源搜索系统存在的问题和不 足，利用w e b 使用挖掘技术对c a d a l 的用户使用信息数据进行分析，提出有效的 改进数字图书搜索质量的技术和算法。最后，在c a d a l 门户中实现基于上述研究 结果的图书统搜索系统。 本文的主要工作如下： 1 利用c a d a l 门户丰富用户使用日志数据，提出两个点击流上的随机行走 算法：b o o k r a n k 一基于访问关联图的图书评分算法，提供图书相关性排 序功能；q u e r y c l u s t e r 甚于查询一阅读行为的查询词聚类算法，利用读 者对检索结果的隐式反馈信息，提供对查询词的聚类功能。 2 提出抓取互联网上的图书评分相关数据，将其整合进我们的图书搜索排 序系统中去作为搜索结果排序的一个重要依据。 3 基于对c a d a l 门户用户检索和阅读行为的分析，提出使用基于文本相似 度的检索算法来检索图书的元数据，提供基于文本相似度的排序功能和 按字段的权值设置功能，并且可以提高检索性能。 4 在查询词聚类的基础之上，实现一种多排序依据集成方法，针对每类查 询词，综合利用从访问关联图得出的图书相关性排序、互联网上的图书 评分以及文本相似度这三种信息源，形成最终的搜索结果排序。 5 使用上述的算法和技术，实现图书搜索系统，并将其使用在c a d a l 门户 中去替代原有的图书搜索模块。 3 浙江大学硕士学位论文 第l 章绪论 1 4 本文的组织结构 本文内容组织如下： 在本文的第一章中，我们简要介绍中英文图书数字化国际合作计划( 简称 c a d a l ) 和本文的课题背景，然后介绍本文的研究意义，以及本文的主要工作和 组织结构。 在本文的第二章中，我们对相关研究进行综述。介绍数字图书馆的概念，以 及与数字图书馆相关的技术和研究方向，介绍c a d a l 概况和特点；然后我们介绍 元素据的概念，数字图书元数据的含义以及现有的数字图书元数据检索方式；接 下来，介绍几个检索排序的算法，包括基于文本内容相似度的向量空间模型v s m ， 以及基于连接结构的p a g e r a n k 算法和h i t s 算法；最后，介绍w e b 使用挖掘的概 念和应用。 在本文的第三章中，我们提出两个点击流上的随机行走算法，分别是：基于 访问关联图的图书相关性排序算法( b o o k r a n k ) 和基于查询一阅读行为的查询词 聚类算法( q u e r y c l u s t e r ) ，讨论它们的算法思想、数据集定义、算法设计以及 在图书搜索中的应用。另外，还提出一个基于b o o k r a n k 的数字图书个性化搜索 算法，可以提供图书搜索的个性化服务。 在本文的第四章中，我们介绍多排序信息源及其集成。提出抓取互联网上的 图书评价相关数据作为我们的数字图书搜索排序的一个来源，然后介绍使用基于 文本相似度的数字图书元数据检索方法来检索数字图书，最后将这两个排序源和 第三章中提出的算法相结合，提出多个排序信息源的集成技术，将它使用在我们 的数字图书搜索系统之中。 在本文的第五章中，我们在c a d a l 门户中实现使用第三和第四章中的算法和 技术的图书搜索系统，首先给出图书搜索系统的整体架构和实现，然后着重分析 系统中几个子系统的详细设计和实现。 在本文的第六章中，我们对全文进行总结，、并对未来提出展望。 4 浙江大学硕士学位论文第l 章绪论 1 5 本章小结 在本文中，我们介绍了中英文图书数字化国际合作计划( 简称c a d a l ) 和本 文的课题背景，然后介绍了本文的研究意义，以及本文的主要工作和组织结构。 5 浙江大学硕士学位论文第2 章相关研究综述 第2 章相关研究综述 2 1 数字图书馆 近年来，数字图书馆( d i g i t a ll i b r a r y ) 的建设在世界很多国家得到了迅 猛的发展，与数字图书馆相关的研究工作也非常活跃。数字图书馆的含义很广， 它是一整套面向对象的、分布式的数字化资源的集合。数字图书馆包括所有数字 形式的图书馆资源：经过数字化转换的资料或本来就是以电子形式出版的资料， 新出版的或经过回溯性加工的资料；各类资源类型，包括期刊、参考工具书、专 著、视频声频资料等。数字图书馆是高技术的产物，它涉及了网络技术、数字化 技术、数据库技术、信息检索技术、多媒体信息处理技术、信息压缩与传送技术、 分布式技术、数据挖掘技术等多项技术。 2 1 1c a d a l 项目情况 国家计委、教育部、财政部在2 0 0 2 年9 月下发的关于“十五”期间加强 。2 1 1 工程”项目建设的若干意见的文件中，将“中英文图书数字化国际合作 计划( c a d a l ) 列入“十五”期间“2 1 1 工程”公共服务体系建设的重要组成部 分n 1 。c a d a l 与“中国高等教育文献保障系统( c a l i s ) ”一起，共同构成中国高 等教育数字图书馆的框架h ，。 c a d a l 项目的建设目标是：在“十五”期间，建设为我国高校教学科研服 务的百万册图书规模的数字资源，建成2 个数字图书馆技术中心( 浙江大学，中 国科学院研究生院) 和1 4 个数字资源中心( 北京大学，清华大学，浙江大学，复 旦大学，南京大学，中国科学院研究生院，上海交通大学，西安交通大学，武汉 大学，华中科技大学，吉林大学，中山大学，四川大学，北京师范大学) ，形成 一套成熟的支持t b 量级数字对象制作、管理与服务的技术平台，探索多媒体、 虚拟现实等技术在数字图书馆中的应用，推动我国数字图书馆技术达到国际领先 水平，为数字图书馆建设与服务的可持续发展奠定资源和技术基础。 6 浙江大学硕士学位论文 第2 章相关研究综述 c a d a l 项目的实施对于改善我国高校教学科研的信息环境、建设一流大学具 有重要意义脚。c a d a l 项目将推动海量数据存储、管理、检索和多媒体处理等方 面的研究工作，促使我国在大规模数字图书馆建设和信息服务领域向世界先进水 平迈进h 1 。c a d a l 项目具有重大的实用意义、研究价值和发展前景。 2 1 2 数字图书元数据检索 元数据( m e t ad a t a ) 定义为：d a t aa b o u td a t a ( 关于数据的数据) ，在许多 领域有其具体的定义和应用嘲。i e e e ( t h ei n s t i t u t eo fe l e c t r i c a la n d e l e c t r o n i c se n g i n e e r s ，电气和电子工程师委员会) 的海量存储系统和技术委员 会( m a s ss t o r a g es y s t e m sa n dt e c h n o l o g yc o m m i t t e e ，淞s t c ) 在1 9 9 3 年8 月提出了一个元数据的比较系统的定义1 ：“元数据是关于存储的信息实体、存储 的管理以及存储和实体的使用信息。信息实体包括语义或信息内容、存储的结构 映射、要素的类型和编码、实体之间的关系、格式、结构和类型、相关的数据、 导出派生信息；存储的管理包括定位、访问时间和访问方法；存储和实体的使 用包括限制、用法和历史记录雎1 。 在数字图书馆中，元数据被定义为：提供关于信息资源或数据的一种结构化 的数据，是对信息资源的结构化的描述。其作用为：描述信息资源或数据本身的 特征和属性，规定数字化信息的组织，具有定位、发现、证明、评估及选择等功 能。由于元数据能够很好地概括其对应资源的信息，所以通过检索元数据，用户 可以寻找到满足自己需求的资源。 数字图书馆通常提供两种类型的图书元数据检索，以c a d a l 数字图书馆为例， 包括统一检索和高级检索两种。统一的检索可以让用户非常方便和迅捷的进行资 源检索。c a b a l 门户的统一检索设计类似于g o o g l e 和b a i d u ，但又稍有不同。用 户通过在统一检索输入某一个检索词，并且勾选要检索的资源库，门户将根据输 入的检索词，在指定的资源库中检索符合要求的元数据，并且将结果在一个统一 的界面中反馈给用户嘲。统一检索的输入框只有一个，但是用户可以通过空格隔 开多个单词从而达到输入多个检索词进行检索的要求。门户会将多个检索词通过 7 浙江大学硕士学位论文第2 章相关研究综述 “与”的关系进行检索，即：同时满足输入的检索词的元数据才会被作为检索结 果返回给用户删。 高级检索将资源库分库，使得用户在进行检索的时候可以设置更加详细的检 索条件，从而更加精确地定位到需要的资源嘲。当前c a d a l 门户的高级检索针对 的是资源库中的图书，所以在高级检索中能够检索的都是图书资源。门户上将这 些图书资源按照检索范围分为：全部图书、民国图书、古籍图书、期刊、硕博论 文、英文图书和现代图书共七个检索范围。对于不同类型的图书，检索项( 即对 应的元数据项) 并不尽相同哺1 。例如：古籍图书并没有中图分类号等现代图书才 有的元数据资源( 对应的元数据项存在。但是该项对于该类图书没有标注信息) ； 再比如期刊特有的统一刊号等等。 2 2 检索排序算法 随着人类社会的发展和信息化的不断深入，各种信息资源呈现出爆炸式的增 长，特别是随着互联刚的飞速发展，各种信息资源得到了充分的整合和利用。如 何在海量的信息中快速、有效的找出我们需要的信息成为一个非常关键的问题， 信息检索也成为了一个热门的研究方向。 在用户的次信息检索事件中，准确地找到与用户输入条件相匹配的信息固 然十分重要，但是在这些匹配的信息条目中有效地区分哪些是用户需要的，哪些 是用户不需要的才能更好的提高检索的质量。设想在一个没有检索排序的w e b 搜 索引擎上查找某个关键字，搜索引擎返回了上万条与关键字相匹配的页面链接， 用户需要在这些结果中找到自己需要的东西，这是一个非常艰巨的任务。对检索 结果的相关性捧序显得非常重要。现在各种通用信息检索系统，比如g o o g l e 这 样的搜索引擎，都提供了对检索结果的排序，以提高检索的质量。 早期的信息检索系统按照关键词和信息库的文本内容相关性来对检索结果 进行排序，后来在诸如论文检索，w e b 页面检索这样的检索系统中出现了基于链 接分析的排序方法，它使得通过信息单元的链接关系量化信息单元的重要性变得 可能。本节将对基于文本内容和链接结构的排序算法进行简要分析。 8 浙江大学硕士学位论文第2 章相关研究综述 2 2 1 基于文本内容的排序算法 信息检索中具有代表性的文本模型主要有布尔模型、向量空间模型( 简称 v s m ) 、概率模型等n3 1 。这些模型从不同角度使用不同的方法处理特征加权、类别 学习和相似计算等问题，而向量空间模型是最有效的文本表示模型之一n 甜。 向量空间模型v s m 的概念是s a l t o n 等人于6 0 年代末提出的，后来被用于著 名的s m a r t 系统中，获得很大的成功蚴，该模型及相关技术在文本分类、信息检 索领域得到了广泛的研究和应用。 v s m 模型有下面几个基本概念n 3 1 ： 文档d ( d o c u m e n t ) ，指文档或文档中的一个片段。 特征项t ( t e r m ) ，它是指出现在文档中的能够代表文档性质的基本语言 单位( 字、词、词组或短语等) 。这样一个文档d 就可以表示为 j = ( ，f 2 ，气) 。 项的权重w ( t e r mw e i g h t ) ：在一个文档中，每个特征项都被赋予了一个 权重，以表示这个特征项在该文本中的重要程度。权重一般都是以特 征项的频率为基础进行计算的，这样文本就表示为：d = ( m ，w 2 ，) ， 这里心代表气在文档d 中的权重，其中1 k n 在v s m 模型中，m 个文档组成的文档集合就可以表示为d = 盔，a 2 ，厶) 。我 i r j 令z = t , ，乞，) 为一个大小为n 的词典，是词典中的特征项。当m 个文档的 文档集合被n 个特征项索引时可表示为一个m * n 的文档前征项矩阵： 口l l 口l 蚪1 彳= i ：；i 公式2 1 l 口脚1 口m 一 其中表示特征项0 在文档喀中出现的次数，即词频t f 。 在一个文档4 = ( ，口，：，) 或者一个查询g = ( 岛，岛，吃) 中如果某二项 或嘻为0 ，则表示特征项气在相应的文档或这查询中没有出现。 9 浙江大学硕士学位论文 第2 章相关研究综述 如果一个词0 在多个文档中都出现，尽管这个词在单个文档中可能有很高的 词频，但它并不能有效地区别不同的文档，因此我们将分配给它一个较小的权重， 为了描述这种情况，我们引入了文档频率d f ( d o c u m e n tf r 舭y ) 的概念n 射。我 们用勺表示特征项0 在文档集合d 中涉及的文档个数，m 表示集合d 的大小， 因此文档频率d f 的计算公式为n 引： 钟( o ) = 皇m 公式2 2 然后定义倒置文档频率i d f ( i n v e r t e dd o c u m e n tf r a q u e y ) 如公式2 3 ，结合词 频计算公式，最后得到经典的t f * i d f 词项权重函数n 引，如公式2 4 。 脚= 培 嘞刮小胼( 小素培 相似度指两个文档内容相关程度的大小，当文档以向量来表示时，可以使用 嘞宰嘭 s ( “) = 衙 公舰5 ( 其中嘭为0 在q 中的权重。) 向量空间检索的优点在于将非结构化的文本表示为向量形式，使得各种数学 处理成为可能：利用计算得到的相似度可以对获取的文档按照相关度排序。 2 2 2 基于链接结构的排序算法 在具有引用、参考、推荐等关系的文档集中，我们不仅仅使用基于文本内容 的检索排序算法，还可以将文档之间的链接结构引入进来作为检索排序的重要考 1 0 浙江大学硕士学位论文第2 章相关研究综述 虑因素，比如通用的w e b 搜索引擎就使用网页之间的链接关系来对网页进行排序。 p a g e r a n k 和h i t s 便是两种著名的基于链接结构的排序算法 2 2 2 1p a g e r a n k p a g e r a n k 是g o o g l e 创始人在s t a n d f o r d 大学提出的页面质量评价算法。 p a g e r a n k 不只建立在链接的流行度的基础上，它更多考虑的是指向它的网页的质 量及重要程度呻1 。如果一个p a g e r a n k 高的网页a 有一个链接指向网页b ，那么网 页b 也将会获得就较高的p a g e k a n k 值。 假设i 1 是一个网页n ： e 是网页u 指向的网页的集合 且是指向网页u 的网页的集合 饥= i e l 表示网页u 所包含的链接的数量 公式2 6 是一个简单的p a g e r a n k 计算公式： 呻) = 荟掣 i e 肌1 p 同时网页ve 曰的p a g e r a n k 又取决于链接到它们网页的p a g e r a n k 。所以，一 个阏页的p a g e r a n k 值是由其它网页来递归决定的，它的值也同时将会影响到与它 存在链接关系的页面，网页的p a g e r a n k 值由链向它的网页的p a g e r a n k 值决定，每 个反向链接网页的贡献的值是不同的n 。如果网页v 中向外的链接数目越多，它 对当前网页t l 的贡献就越小，u 的反向链接网页越多，其p a g e r a n k 值也越高。图 2 1 为p a g e r a n k 值的一个简单例子，页面上的数值为相应页面的p a g e r a n k 值n 。 浙江大学硕士学位论文第2 章相关研究综述 图2 1p a g e r a n k 的一个简单示饲 我们可看出一个网页的p a g e r a n k 值受反向链接数目、反向链接是否来自 p a g e r a n k 高的页面、反向链接源页面的链接数等因素的影响。首先被许多页面链 接会使得p a g e r a n k 提高，也就是说被许多页面链接的受欢迎的页面，必定是优 质的页面n 引。同时，好的页面所推荐的页面，必定也是同样好的页面。如果从s i n a 这样的p a g e r a n k 非常高的站点的页面被链接的话，此网页的p a g e r a n k 也会上升 很多；相反，无论有多少反向链接数，如果全都是从那些p a g e r a n k 非常低的页 面链接过来的话，p a g e r a n k 也不会上升很多n 驹。 z z z zh i t s h i t s ( h y p e r t e x t i n d u c e dt o p i cs e a r c h ) 算法是由j o nk l e i n b e r g 博士于 1 9 9 8 年首先提出的n 对。k l e i n b e r g 认为搜索开始于用户的检索提问，每个页面的 重要性也依赖于用户的检索提问，他将用户检索提问分为三种：特指主题检索提 问、泛指主题检索提问及相似网页检索提问“孙。h i t s 算法则专注于改善泛指主题 检索的结果。 对于每个页面p ，h i t s 算法计算两个值，即a u t h o r i t y 和h u b 。a u t h o r i t y 和h u b 之间满足如下关系：对于h u b ，如果p 指向越多具有好a u t h o r i t y 的页面， p 的h u b 值就越大；对于a u t h o r i t y ，如果有越多具有好h u b 的页面指向p ，p 的 a u t h o r i t y 值就越大 1 5 o 对整个w e b 集合而言，a u t h o r i t y 和h u b 是相互依赖、 浙江大学硕士学位论文 第2 章相关研究综述 相互加强的关系。a u t h o r i t y 和h u b 之间相互优化的关系，即为h i t s 算法的基础。 该算法主要包括两个过程：构造页面邻域图和迭代链接分析n 町 l 构造页面邻域图 给定一个泛指主题检索查询q ，h i t s 的页面邻域图构造算法的基本步骤 是： 首先，将查询q 提交给传统的基于关键字匹配的检索系统，从检索系统 的查询结果集中排序分值最高的一组结果页面构成一个根集( r o o ts e t ) 足。 然后，使用毛中页面的邻近页面来扩充墨，形成一个页面基集( p a g e b a s es e t ) 吃最后，从页面基集& 导出页面邻域图g 名 = ( v ，e ) 。 2 迭代链接分析 h i t s 算法对邻域图g 见】= ( v ，e ) 中每个结点p 赋予两种排序分值：权威 分值a p 与中心分值h p 。前者用于度量一个页面的权威性，而后者用于度 量一个页面的中心性n 们。任一结点p 的权威分值和中心分值分别用以下两种 操作计算，如图2 2 所示： 图2 2h i t s 的一个简单示例 浙江大学硕士学位论文第2 章相关研究综述 i 操作：口【p 】= h a l + h l b l + h c 】 公式2 7 o 操作：“p 】= “d 】+ “e 1 + 4 【，】 公式2 8 计算步骤如下： r 1 个结点的权威与中心分值分别构成两个n 维( 列) 向量4 r 6 和 e f a 和h 初始化为向量z = 【1 ，1 ，1 t e r 。； 对向量a 和h 进行反复迭代计算，即在h 上运用i 操作来计算a ，在a 上运用0 操作来计算h ，每次迭代后对a 和h 进行单位化，直到a ，h 收 敛。 输出一组具有较大中心值的网页和具有较大权威值的网页。 很多实验数据表明，h i t s 的j 名准确性比p a g e r a n k 高。但是h i t s 有一个很 大的问题在于它是一个依赖于查询关键字的算法，在线运算量大，极大地影响了 算法的可伸缩性，从而难以应用于太规模的网页数据集。 2 3w e b 使用挖掘 我们换一个角度来考察检索算法。检索系统比如通用的w e b 搜索引擎在向用 ， 户提供服务的同时也积累了大量的用户使用日志信息。通过挖掘检索系统的使用 日志信息，菝们可以通过一些算法来改善已有的检索系统，利用这些使用信息来 提高检索的质量和性能。 随着互联网的飞速发展，网络数据资源正在飞速的增长，如何开发和利用这 些丰富的资源就成为人们普遍关注的问题。肿上的站点数目和访问数量都达到 了空前的规模，数据挖掘技术和例应用研究相结合构成了先进非常活跃的研究 领域呵e b 数据挖据n7 。 w e b 数据挖掘是- f l 交叉性学科，涉及数据挖掘、机器学习、模式识别、统 计学等多个领域n 。w e b 数据挖掘定义为：w e b 数据挖掘就是从与w w w 相关的资 源和用户浏览行为中抽取有用的、感兴趣的模式和隐含信息。w e b 挖掘可分为三 类：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使用挖掘( w e bu s a g em i n i n g ) 呻1 。 1 4 浙江大学硕士学位论文第2 章相关研究综述 w e b 使用挖掘的主要目标则是从w e b 的访问日志中抽取感兴趣的模式。w e b 使用挖掘工具发现和分析用户的行为，从而帮助网站设计人员改进站点的结构以 提高访问率，或为用户提供个性化的服务。这方面的研究主要有两个方向：一般 的访问模式追踪和个性化的使用记录追踪 1 7 ow e b 日志数据挖掘可分为三个主要 部分：数据预处理、w e b 日志挖掘的使用模式、模式发现。 w e b 日志数据挖掘主要应用于以下几方面u 刀：为用户提供个性化的服务；改 善系统，提高性能，提高系统服务质量：提高网站结构设计质量；当然还有一个 非常重要的应用就是改进搜索引擎的搜索排序质量，这也是本文中提出的算法和 系统的基本出发点。 2 4 本章小结 在本章中，我们首先简要的介绍了数字图书馆的概念，以及与数字图书馆相 关的技术和研究方向的，随后我们介绍了“中美百万册书数字图书馆合作计划” ( c h i n a - o sm i l l i o nb o o kd i g i t a ll i b r a r yp r o j e c t ) 的背景、概况和特点。 然后我们介绍了元素据的概念，数字图书元数据的含义，以及现有的数字图书元 数据检索方式，我们以c a d a l 为例简要介绍了两种图书元数据的检索方式。接下 来，我们介绍了几个检索排序的算法，包括基于文本内容相似度的向量空间模型 v s m ，以及基于连接结构的p a g e r a n k 算法和h i t s 算法。其中p a g e r a n k 算法就是 一个随机行走算法的典型例子最后，我们介绍了w e b 使用挖掘的概念和应用， 我们后面的几个算法都是在w e b 使用挖掘的基础上提出的。 浙江大学硬士学位论文第3 章点击流上的随机行走算法 第3 章点击流上的随机行走算法 在本章中我们将提出两个基于读者访问日志的点击流上的随机行走算法，分 别是：基于访问关联图的图书相关性排序算法( b o o k r a n k ) 和基于查询一阅读行 为的查询词聚类算法( q u e r y c l u s t e r ) 。b o o k r a n k 算法利用读者的图书阅读行为 信息建立图书之间的相关性关系( 图书访问关联图) ，然后使用该关联关系来捧 序数字图书，该算法还可以用于图书的个性化搜索中。通常读者在进行了某次图 书检索以后会选择一个或者多个相关的图书进行阅读。q u e r y c l u s t e r 算法就是分 析这样的“查询一阅读行为使用日志信息，对查询词进行聚类，该算法将在 我们后面的多排序信息源集成中起到重要的作用。 3 1b o o k r a n k 基于访问关联图的图书相关性排序算法 c a d a l 门户自2 0 0 5 年1 1 月开始对外服务已经有很长的一段时间了，已经拥 有了大量的用户群，目前的注册用户i d 有3 3 1 1 5 个，最近半年的有效图书阅读 人次为2 0 7 万次( 我们视一个读者阅读了一本书的2 0 以上的书页为一次有效的 阅读) 。 在这段时间中我们已经积累了大量的读者图书阅读日志记录信息，本节中我 们将利用读者的图书阅读行为在图书之间建立相关性关联，然后构造图书之间的 读者访问关联图，最后通过一个基于随机行走模型的迭代算法来计算图书之间的 相关性捧序。 3 1 1 数据集定义 在这里我们考察读者、图书以及读者的图书阅读行为三个要素。设读者的集 合为： u = q ：o f 埘 m 为读者的数量；图书的集合为： 公式3 t 浙江大学硕士学位论文第3 章点击流上的随机行走算法 曰= 哆：o j 刀) 公式3 2 n 为图书的数量。读者与图书的阅读关系表示为： z = 岛。，：u a b j 曰，o i m ，o j o ，q 。，为边的权重。 有一点需要注意，虽然e 是一个对称矩阵，但是c 并不是个对称矩阵，所以边 ( 岛，岛) 和边纯，匆) 的权重并不是一致的，g c 是一个有向加权图。 我们举一个简单的示例。我们假设有4 本图书，分别是图书a ，b ，c 和d