（模式识别与智能系统专业论文）相关性排序技术的几点研究.pdf

相关性排序技术的几点研究 摘要 本文针对搜索引擎相关性排序中的三方面技术进行了系统的研 究：链接分析，段落检索和相关反馈，它们分别从不同的角度来改进 相关性排序结果。主要创新工作和成果如下： 第一，提出p a g e r a n k 链接分析算法的存储优化方法。 基于链接分析的p a g e r a n k 算法需要计算网络所有结点的网页重 要性分数，即p a g e r a n k 值，因而网页结点的合理存储是该算法顺利 运行的关键，本文通过数学推导以及利用稀疏矩阵的特点将算法空间 复杂度由o ( n 2 ) 降至o ( n ) ，同时大大提高了算法迭代效率。 第二，提出段落检索与全文检索相结合的排序方法。 以段落为粒度索引的排序方法能够有效的提高检索的准确率，但 会使得召回率有所下降，为了减轻召回率的损失，提出将段落权重和 全文权重相结合的排序方法，结果使得准确率得以提高，同时确保了 召回率。 第三，实验分析r o c c h i o 相关反馈算法在应用中的优劣势。 r o c c h i o 是经典的基于向量空间模型的相关反馈算法，本文通过 实验分析了其在改进排序结果上的有效性以及算法的优劣势。 关键词：相关性排序p a g e r a n k 段落检索r o c c h i o r e s e a r c ho nr e l e v a n c er a n k i n g a b s t r a c t f o rr e l e v a n c er a n k i n gi ns e a r c he n g i n et e c h n o l o g y , t h i sp a p e rm a i n l yr e s e a r c h e s o nt h r e et e c h n o l o g i e s ：l i n ka n a l y s i s ，p a r a g r a p hr e t r i e v a l ，r e l e v a n c ef e e d b a c k t h e ya l l c a ni m p r o v er e t r i e v a lw i t hd i f f e r e n tm e t h o d t h em a i ni n n o v a t i o nc o n t r i b u t i o n so f t h i sp a p e ra r el i s t e db e l o w ： f i r s t ，t h i sp a p e rp r o p o s e sas t o r i n gm e t h o do fp a g e r a n ka l g o r i t h mb a s e do nl i n k a n a l y s i s a sa l lk n o w n ，p a g e r a n ka l g o r i t h mn e e d st oc o m p u t et h es c o r eo fe v e r yw e b p a g e ，w h i c hm a k e st h ep r o b l e mo fs t o r i n gt h e s ew e bn o d e sc r i t i c a l t h i sp a p e ru s e s f o r m u l ad e d u c t i o na n dc h a r a c t e r i s t i c so fs p a r s ea r r a yt os o l v et h i sp r o b l e m ，a n da tt h e r e s u l t ，r e d u c e dt h es p a c ec o m p l e x i t yf r o ms q u a r et ol i n e a r , a n di m p r o v e dt h e c o m p u t a t i o ne f f i c i e n c ym e a n w h i l e s e c o n d ，t h i sp a p e rp r o p o s e sam e t h o do fc o m b i n i n gp a r a g r a p hr a n k i n ga n df u l l t e x tr a n k i n gt oi m p r o v er e t r i e v a lr e s u l t t h em e t h o do fr a n k i n gb a s e do np a r a g r a p h s c a ni m p r o v ep r e c i s i o nb u tw i l lm a k er e c a l lr e d u c e ，t oa v o i dt h i s ，t h i sp a p e rc o m b i n e d t h es c o r eo fp a r a g r a p hr a n k i n gw i t hf u l lt e x tr a n k i n g ，t h a tw i l lm a k es u r et h er e c a l lo f r e t r i e v a l t h i r d ，t h i sp a p e ra n a l y s i st h ea d v a n t a g e sa n dd i s a d v a n t a g e so fr o c c h i or e l e v a n c e f e e d b a c ka l g o r i t h m ，w h i c hi sb a s e do nv e c t o rs p a c em o d e l k e yw o r d s ：r e l e v a n c er a n k i n g ，p a g e r a n k ，p a r a g r a p hr e t r i e v a l ，r o c c h i o 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： f 至l 立 日期： 邋：z ：z 2 1 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文丕属于保密范围，适用本授权书。 本人签名： ! 至i 生日期：竺翌：! ：j 导师签名： 北京邮电大学硕士学位论文相关性排序技术的几点研究 第一章绪论 1 1 相关性排序技术的研究背景及现状 在全文检索系统和早期的搜索引擎中，信息检索结果的排列只是以检索系统 在数据库中找到匹配网页的先后次序排列。随着互联网的普及，互联网信息数据 量不断膨胀，每次检索都可能得到几百万甚至上千万的结果数据。而用户在使用 搜索引擎检索信息时，更希望在最短的时间内找到尽量准确的结果，而不是大量 无关的结果集合。这就需要搜索引擎提供对结果排序的算法，搜索引擎排序质量 的好坏直接影响到搜索引擎的最终质量和结果n 1 。 近几十年来，关于相关度排序的研究思路和成果层出不穷。从基于统计的检 索模型，如布尔模型，向量空间模型，概率模型等，到基于语义的检索模型，如 潜在语义索引模型和神经网络等；从基于内容分析的检索模型，到基于链接分析 的检索模型，如g o o g l e 著名的p a g e r a n k 算法，h i t s 算法等；从全文检索到段 落检索；以及通过用户相关反馈来进一步调整排序的方法等等。 1 2 本文的工作及内容安排 本文主要对相关性排序技术的三类方法进行了比较系统的研究：一是基于链 接分析的p a g e r a n k 排序算法，二是段落检索与全文检索相结合的排序方法，三 是r o c c h i o 用户相关反馈排序算法。这三类方法在原理上截然不同，但都是相关 度排序改进的重要方法。 本文的主要安排如下：首先在第二部分中简单阐述相关度排序的评估标准， 接下来在第三、四、五三部分中分别对上述三方面的方法进行系统的研究和实验， 第六为总结展望。 北京邮电大学硕士学位论文相关性排序技术的几点研究 第二章相关度排序评估的主要标准 2 1in t e r p oia t e d p r e cisio n ( 以内插值替换的准确率) 众所周知，准确率和召回率是相关度排序评估的基本标准。而今，有一个更 为标准简洁的方式去表现这两项指标，就是以内插值替换的准确率乜1 。这个指标 p i n t e r p 的定义为：召回率为r 的准确率等于在任何召回率r = r 范围内的最高准 确率，即： p i n t e r e ( r ) 4 臀p ( ，) 下面就是一个1 1 点以内插值替换的平均准确率的例子， 曲线图如图2 2 所示： r e c a l l l n t e r p p r e c i s i o n o o1 。o o o 1o 6 7 o 20 ，6 3 0 30 5 5 o 4o 4 5 o 50 4 1 o 60 3 6 o 7o 2 9 o 。8o 1 3 o 9o 。童l a i 1 oo 0 8 式( 2 1 ) 如图2 - 1 ，对应的p r 图2 - 21 1 点内插值替换法的平均准确率 北京邮电大学硕：仁学位论文 相关性排序技术的几点研究 1 o 0 8 舌0 6 o 星o 4 o 2 o o r 1 广- r r o oo 。2o 4o 6o 81 g r e c a l l 图2 - 2p r 曲线图 2 2m a p ( m e a na v e r a g ep r e cisio n ，平均准确率) 这个标准是t r e c 评测的最主要标准，对于其它方法，m a p 尤其具备非常 好的区分性和稳定性。其定义如下： 脚= 击墨南曼测吣，加彩 2 3p r e cisjo na tk ，p k 对于网络搜索来说，我们通常不特别要求召回数量而更看重排名靠前的一些 结果的准确程度，比如第一页或前三页中有多少相关结果。这样就产生了固定某 - - d 数量结果数中计算准确率的方法，比如说p i o 。这个标准的优势在于小数 量评估的易行性，而劣势在于它是最不稳定的一个标准，因为对每个查询而言， 相关文档的数量总数都是大不相同的，因此它无法很好的作平均。 北京邮电大学硕士学位论文相关性排序技术的几点研究 2 4r - p r e cisjo n 为了减轻p k 的问题，产生了r p r e c i s i o n 标准心1 。它要求有一定数量的已 知相关文档集，这个集可以是不完全的相关文档集，然后计算这个集中的文档在 结果返回时的准确率。r p r e c i s i o n 这个标准能适应相关文档的大小，也就是说一 个完美的系统对于每个查询来说这个指标值为1 ，而对于p 2 0 来说，即便是完 美的系统而只有8 篇相关文档的话这个值也只能是0 4 。加入对于一个查询来说 有r 篇相关文档，在前r 个返回结果中找到r 个相关文档，那么此时的r p r e c i s i o n 就等于以，这个值不仅是准确率，也是召回率。 2 5n d c g ( n o r m ai z e ddis c o u n t e dc u m uia tiv eg ain ) 每个返回结果都有不同程度的相关性，累积增益是指相关性的累积和，折扣 是指对排名的折扣力度，即排名越靠后的结果的相关性增益越小。归一化是确保 指标在0 1 之间，以理想情况( 结果按相关性降序排列) 的d c g ，即i d c g ，作 为归一的基。计算公式如下乜1 ： 一g e q 忙棚z k m 三= l 等杀 其中z k 就是归一化系数。这个标准在t r e c 中越来越普及， 器学习方法排序上被广泛采用。 4 式( 2 3 ) 尤其在应用机 北京邮i 乜人学硕士学位论文 栩关性 8 序技术的几点研究 第三章基于链接分析的排序算法 3 1 基于链接分析排序算法的研究背景 当今很多搜索引擎在面对用户的查询时会采取两个步骤返回结果文档。第一 步，通过传统的文本处理过程找到与查询在语义上匹配的所有相关文档。这一步 是通过查询倒排索引，以向量空间模型、概率模型等方法完成的。但面对互联网 规模已然如此庞大的现实，第一步的结果返回量很有可能是成千上万的网页。为 提高系统的查准率，很多搜索引擎采用了各式各样的排序法则对结果进行排序的 改进。这时，挖掘网页问的链接结构信息作为一种创新的排序方法应运而生，也 就是链接分析口1 。 网页搜索中的链接分析技术的祖先是学术引用分析，学术引用分析通过对学 术文章的引用模式进行分析来量化文章本身的影响力。就像引用是学术文章对其 他学术文章的一种权威推荐一样，网页链接分析也把从一个网页到另一个网页的 超链接作为一种权威的推荐。显然，并非每个引用或是超链接都隐含着这样的权 威推荐，基于这个原因，简单地利用网页的入链链接数量是不足以衡量该网页的 权威度的。例如，某人故意用多个网页链向某个目标网页，目的是人工地提高目 标网页的入链数量。这种现象就是超链接垃圾。然而，引用的现象足够普遍也足 够可靠，网页搜索引擎可以通过复杂的链接分析技术充分的利用好这块庞大的资 源。此外，链接分析在爬虫领域也具备应用价值，已经有证明证实链接分析能够 指示哪些网页应该被优先爬取。 链接分析是基于两个先验假设的口4 1 ： 第一，指向网页的超链接锚文字是对该网页的一个很好的描述； 第二，网页a 通过超链接链向网页b 意味着网页a 对b 的某种认可和支 持，也就是说，网页b 不仅与网页a 是主题相关的，而且对网页a 来说是值得 关注的页面。这一点并不总是如此，比如网站内部的网页一般具有共同的模板设 计，很多网站主页都被来自网站内部的网页所链，这当然不能称作一种支持。但 是相应的，链接分析算法的应用将对这种内部链接进行折扣处理。 关于锚文字h 1 ，它在链接分析中的作用也是不可忽视的。在整个网络中，绝 大部分网页不能提供对自身内容的一个很好的描述。很多情况表明关键在于网页 5 北京邮电大学硕上学位论文相关性排序技术的几点研究 设计者想如何展示自己，对很多大公司的网站来说，网页展示是个市场描述。例 如，i b m 公司并没有在自己的网页中包含“电脑”这个词，尽管它是全球最大的电 脑制造商。同样，y a h o o 网站的主页也没有出现“门户”这个词。因此，网页中出 现哪些词与网页设计者想如何表现网页之间经常是有区别的。但事实上，有很多 链向i b m 网站的超链接中的锚文字是包含“电脑”这个词的，而锚文字是可以被 搜索引擎抓取到的。我们可以把锚文字作为检索目标网页的关键词。因此，“电 脑”这个词就可以被包含到i b m 网站中，而“门户”也可以被包含到y a h o o 中，我 们可以用个特殊的标识指示这些词是出现在锚文字中。锚文字的权重经常基于词 频，当然会排除掉一些出现频率特别大的词，比如“点击”和“这里”等等。实际上 这些词的权重会通过机器学习方法得到。锚文字的应用有一些有趣的副作用。在 搜索引擎中输入“b i gb l u e ”，会返回i b m 公司的主页，并且排名第一，“b i gb l u e ” 是i b m 一个很流行的绰号。而另一方面，也有很多关于锚文字应用的反面例子， 比如一些网站会生成一些误导性的锚文字，借以提高搜索结果中的排名。因此， 检测对付这些锚文字的语义滥用成为搜索引擎垃圾检测的一个方面。锚文字附近 的文本经常和锚文字本身具有同样的作用，因此对于锚文字附近文本的选择也已 经成为研究的热点。 总而言之，链接分析技术已经作为搜索引擎计算复合相关度的一个重要因素 而得到广泛应用。 3 2 基于链接分析的主要排序算法 1 9 9 8 年是为链接分析模型忙碌的一年。卡耐基大学的年轻科学家j o n k l e i n b e r g 参与了一个称作h i t s 的网络搜索引擎的项目。他的算法应用网络的超 链接结构来改进搜索引擎的结果。对于当时绝大多数搜索引擎只是利用文本内容 返回相关结果来说，这无疑是个创举。几乎与此同时，斯坦福大学的两名研究生 也在为相似的项目忙碌，他们是s e r g e yb r i n 和l a r r yp a g e ，都是计算机科学的学 生，从1 9 9 5 年起二人就开始为他们的网络搜索引擎谋划，他们把自己的项目起 名为p a g e r a n k ，而他们的搜索引擎后来成为举世闻名的g o o g l e 。h i t s 和 p a g e r a n k 两个模型具有很强的联系，很难说谁启发了谁，但是，鉴于p a g e r a n k 算法上的一些优势以及c o o g l e 在商业上的巨大成功，p a g e r a n k 算法已经成为链 接分析的主导模型瞄6 ，。 一般来说p a g e r a n k 分数比h i t s 分数更具有稳定性，因为对于整个网络拓 扑结构，p a g e r a n k 对细小的变化不太敏感。但是p a g e r a n k 算法中的“随机跳转” 6 北京邮电大学硕士学位论文相关性排序技术的几点研究 过程会对模型的鲁棒性有重要的影响。另外，无论是p a g e r a n k 还是h i t s ， 都 无法回避刻意制造链接这种垃圾行为。 3 3p a g e r a n k 算法的基本概念和原理 3 3 1 概念 p a g e r a n k ， 是指通过分析网络链接结构为网页计算的重要性分数。口1 每个 网页在整个网络中被看作是一个结点，而每个结点的p a g e r a n k 值由结点的链接 结构关系决定。当给出一个查询时，搜索引擎就会为每个网页计算出一个复合的 分数，包含上百个特征，比如说余弦相似度，关键词近似程度，也包含p a g e r a n k 分数。这个复合分数，会为查询提供一个有序的返回结果。 3 3 2 随机冲浪 假设现在有个网上随机冲浪者从某个网页开始，即网络结构中的一个结点， 然后开始随机冲浪口1 。每一步都从当前浏览页随机选择一条超链接进入下一页面。 如图3 - 1 ，结点a 有三条超链接，分别为b ，c ，d ，即从结点a 跳转到其中二 个的概率为1 3 。当在网络中持续的做随机跳转，必然有一部分网页会比其他一 些网页访问的次数多，从直觉上看，这些访问频繁的网页具有比一般网页更多的 入链，而p a g e r a n k 背后的思想就是网页被访问的次数越多，网页就越重要。 图3 1 网页结点链接关系图 北京邮电大学硕士学位论文相关性排序技术的几点研究 3 3 3 随机跳转 如果结点a 没有出链呢? 为应对这种情况我们引入一种附加的操作，称为 “随机跳转”陋1 。在这个操作中，随机冲浪者可从网络图中的结点跳转到其他任意 的结点上。现实的操作就是用户在浏览器上输入u r l 。这样一来，假如网络中 总共有n 个结点，“随机跳转”的结果就是每个结点的跳转概率为1 n 。 为给网络图中的每个结点都分配适当的p a g e r a n k 值，我们可以以两种方式 应用“随机跳转”操作：第一，当某个结点没有出链时，冲浪者将启动此操作。第 二，如果结点存在出链，冲浪者会以概率a ( 0 y 表示从v 到y 存在一条链接。迭代算法的核心就是中心度和权威度这一对分数的迭代更新，如 下公式所示，它蕴含着我们最初的直觉假设即好中心指向好权威，好权威被好中 心所指向： j l ( 秽) 一e 蹿( 3 ，) 一y 疗秽) 。ej l ( ! ) 妒护 式( 3 9 ) 如公式所示，第一行设置网页v 的中心度等于v 的所有出链结点的权威度之 和，换句话说，如果v 链向权威度高的网页，那么它自己的中心度分数就会提高。 同样第二行是倒过来，假如v 的入链是中心度很高的网页，那么v 的权威度分数 就会提高。 那么当我们进行迭代更新时会发生些什么? 重新计算中心度分数，然后在此 基础上更新权威度分数? 我们将上个公式转化成矩阵的形式。令h 和a 分别表示 所有结点的中心度和权威度的分数向量。用a 表示网络的邻接矩阵，a 是个方 阵，每行没列就对应着子集中的一个结点的链接信息。我们令a i j 等于1 如果从 结点i 到结点j 存在一条超链接，否则元素值设为0 然后我们修改公式如下： 秀。a 万扣a 了瓦 1 5 式( 3 1 0 ) 北京邮电大学硕士学位论文相关性排序技术的几点研究 a t 表示矩阵a 的转置。然后我们分别用上式的h 和a 代入各自的公式， 结果如下： 嚣。a a r f 哩 万卜a 。a 万 式( 3 一1 1 ) 接着我们通过引入特征值，将 符号变成_ 号，如下： 矗= ( 1 a h ) a a 2 玉 万 = ( 1 九) a 。a 覆 式( 3 1 2 ) 这里我们用地表示a a t 的特征值而用h 表示a t a 的特征值，由此，我 们可以得出如下结论： 第一，当给予适当的特征值，通过计算a a “t 和a t a 的特征向量就可以进 行幂迭代，假设它们的主特征值是唯一的，那么迭代计算的h 和a 将会稳定在某 个唯一值，可以由矩阵a 的元素和网络结构完全决定。 第二，当计算这些特征向量时，我们不是必须使用幂迭代方法，事实上，我 们可以采用很多快捷的方法来计算一个随机矩阵的主特征向量。 因此，计算的结果将会是如下流程： 首先，选定目标子集，根据链接关系计算a a t 和a “t a 。接下来，计算 a a t 和a t a 的主特征向量以便得到中心度分数h 和权威度分数a 。最后，返 回中心度和权威度高的网页作为结果。 3 4 2 网络子集的选择 当针对一个话题，比如白血病，我们要收集一个网络的子集，而事实上这个 子集中的权威网页很有可能不包含话题中的具体词，比如“白血病”这个词。这是 非常有可能的，比如当一个权威网页为了某种市场目的采用别的方式描述自己的 主页。就像i b m 的很多网页都包含计算机硬件的权威信息，但是在这些网页中 甚至都不曾出现“计算机”和“硬件”这两个词。但是，同样很有可能有这样的中心 网页，它会在自己的网页中出现这些词，而且还会加条链接链到i b m 网站。基 于这样的观察，我们可以通过以下的程序获得子集以计算出网页的权威度和中心 度分数3 ： 第一步，给出一个查询，比如“白血病”，通过一个文本索引得到所有包含“白 血病”这个词的网页，这样得到的网页集我们称它为“根集”。 第二步，建立网页的“基集”。就是说我们挖掘“根集”中的链接关系，将链入 1 6 北京邮电大学硕士学位论文相关性排序技术的几点研究 链出根集中结点的根集之外的结点囊括进来，这样得到的集合就称为“基集”。 这样我们利用这个基集去计算中心度和权威度分数。建立这个基集有以下三 个原因： 1 一个好的权威网页很有可能不包含关键词，比如计算机硬件那个例子。 2 假如查询文本捕捉到根集中的一个好的中心网页v ，那也就意味着捕捉到 了所有被v 链向的好的权威网页，而这些权威网页出现在基集中。 3 相对的，假如查询文本捕捉到根集中的一个好的权威网页v ，那么链向v 的一些好的中心网页也会出现在基集中。总而言之，将根集扩展到基集 可以将更多的好中心网页和好权威网页囊括进来。 采用h i t s 算法做查询时会有很有意思的发现。比如返回靠前的结果中很可 能出现查询语言之外的其它语言形式。口这些网页会落入基集，因此某些交叉语 言检索在这里是有依据的。有趣的是，这里的交叉语言效应不是由语言翻译引起， 而纯粹是由链接分析中挖掘出的。 对这种算法有几点需要说明：根集中包含所有和查询匹配的网页，但事实上， 研究表明2 0 0 个网页作为根集就足够了，而不需要所有查询匹配的网页。任何计 算特征向量的方法都可以用于计算中心度和权威度分数的向量，但是我们不需要 计算出它们的精确值，我们只需知道它们的相对大小能够排序这就足够了。最后， 很少的迭代次数就能产生排名靠前的中心和权威网页是完全可能的。实验已经证 明经过5 次迭代后的结果已经很优秀。此外，因为网络图的链接结构是非常稀疏 的，( 每个网页的平均链接数只有几个) ，我们可以不对矩阵做迭代而是直接对向 量操作。 3 5p a g e r a n k 算法实验 3 5 1 实验背景及算法选择 基于链接分析的排序算法，与基于内容分析的排序算法在原理上有本质的不 同，考虑到c o s e 项目( 意指校园对象搜索引擎项目，为实验室自立项目) 中所 用的l u c e n c e 检索模型是基于内容分析的相关性排序算法，而链接分析是对基于 内容排序算法的一个重要辅助，它通过考虑网页间的链接关系将网页自身价值体 现出来，这无疑对基于内容的排序结果是个很有必要的修正和改善。 基于链接分析的排序算法有两大主流，一是g o o g l e 闻名的p a g e r a n k 算法， 北京邮电大学硕士学位论文相关性排序技术的几点研究 另一是h i t s 算法。经过对这两种算法的深入研究和分析，本文决定采用p a g e r a n k 算法进行实验。原因有以下几点： ( 1 ) p a g e r a n k 是离线算法而h i t s 是在线算法。且o p a g e r a n k 可以在把所有网页结 构全部爬下来之后，离线地进行迭代计算，最后得出每个网页的权威度分数。这 个方法的主要依据是网页之间的结构在短时间内不会有很大的变动，因此只需每 隔一段不长的时期( 如一个月左右) 将网页重新爬取再重新计算p a g e r a n k 值即可。 而h i t s 算法是在用户输入查询后，先得到一个小的结果集，称为b a s e 集，然后 在线的在网络中计算与b a s e 集中每个网页相邻节点的权威值和中心值，然后进行 排序再返回结果。这个过程虽然比p a g e r a i l l 【的计算时问要短很多，但是与查询相 应的时间相比就显得多了，我也阅读过一些如何压缩数据以解决h i t s 时效的这 个问题的相关论文，但是鉴于实验室有限的硬件条件，认p a g e r a n k 算法的可实 现性更高。 ( 2 ) p a g e r a n k 不易产生主题偏移的问题。这还是相对h i t s 算法的原理来说的。 由于h i t s 算法中要对b a s e 集进行外围的扩充，这个过程很可能造成将一些与话 题无关的网页扩充进来，尤其是当这些无关网页的权威度很高时，会对最终的返 回结果造成非常不利的影响。 基于以上两点考虑，决定采用p a g e r a n k 算法。 3 5 2 实验内容及流程 本实验的主要内容为p a g e r a n k 算法的实现，并重点研究该算法在存储效率上 的优化。鉴于当时c o s e 项目的数据不足，本文使用t r e cb l o g0 6 数据进行算法 实现。但是这个数据集有其特殊性，因其数据主要来自国外几个知名的b l o g 站点， 因此在网络结构上带有社区的性质，即不能完全模拟实际的无序网络，但是鉴于 网页结点之间确实存在链接关系，能够形成链接网络，因此在算法的实现上并不 影响。在本实验中，总共抽取了1 7 万余网页，对这些网页结点的链接关系进行分 析并计算其p a g e r a n k 值。 ( 1 ) 链接提取及关系建立 由于t r e cb l o g 数据集为已爬取之后的文本文件，每个网页的u r l 在 标签中标记，而每个网页中的超链接在 标签中标记，通过正 则表达式匹配将所有链接提取出来，并对其进行编号。与此同时，完成链接关系 的存储，去除掉链向自身结点的链接。最后用两个向量存储每个节点的出链数量 和入链节点序号集。 ( 2 ) 算法设计及实现 1 8 北京邮电大学硕士学位论文相关性排序技术的几点研究 p a g e r a n k 算法模型实际上是个马尔可夫链模型，马尔可夫链是用1 1 维转移 矩阵来表现网络结点间的链接关系的。在本文中不区分出链质量，即某结点的出 链数求算术平均代表该结点到出链结点的转移概率，这时的转移矩阵为p ，但是 由于有很多节点没有出链，这表现为转移矩阵中有一些行均为0 ，考虑到实际中 我们会有一定概率不沿着出链接继续浏览网页，而是随机跳转到其他网页，即随 机跳转，这样就可以将无出链结点所代表的行元素由0 修改为1 n ，n 为网络中 节点的总数。此时的转移矩阵称为p 。同时我们也想到对于有出链的节点也存 在这种随机的跳转性，因此对所有有出链节点所代表的行元素也需要进行上述的 修改，并保持行的和为1 ，引入阻尼系数以平衡随机冲浪和随机跳转的比例。此 时的转移矩阵称为p ”。这时的转移矩阵是满足强连接的，因此可以通过设定初 始分布，一次次和转移矩阵做迭代相乘最后求得平稳分布，即每个网页结点的 p a g e r a n k 值。 但是在算法实现中，这样的迭代相乘是不仅耗时而且存储消耗也很巨大，因 为矩阵中的每一个元素都是浮点型，迭代计算比整型慢很多，并且如果将整个转 移矩阵存储f 来的话，将是n 平方级的存储，在有限的硬件环境中是不允许的， 所以必须想办法优化存储结构。 通过推导了上述三个矩阵之间的关系，如下： = a p + ( 1 一a ) e ( v t ) = a p + ( a a + ( 1 - a ) e ) ( v a t )式( 3 1 3 ) 其中v 是每个元素为1 n 的1 1 维向量，a 表示若所对应行的节点无出链，则 a 为1 ，否则为0 。这样推导的目的在于将密集矩阵还原成原始的稀疏矩阵。这 样就可以避开存储浮点型的i 1 平方矩阵，而只存储稀疏矩阵中非零元素的信息。 因为网络中平均入链和出链数为5 至6 个，这相对于整个网络的维数是微不足道 的，因此，通过这样的存储方式，可以将空间复杂度由o ( n “2 ) 降至o ( n ) ，大大 节省了空间。同时在排列结点时，将沉没结点全部置于向量尾