社会环境下网页重要性的研究论文28735.doc

社会环境下网页重要性的研究 社会环境下网页重要性的研究 中文摘要近年来，随着internet的不断发展，web已经成为人们的重要信息来源，为人们提供了丰富的信息资源。与此同时，它所具有的海量数据、复杂性、极强的动态性和用户的多态性等特点也给we资源的发展发掘造成了相当的难度。通过分析和研究作为一种相当成功的基于超链分析的算法google pagerank，可以有效地衡量网页重要度权值 ,然而进一步的研究也表明 ,这种纯粹依赖于超链分析的算法由于没有考虑到网页访问者对网页重要度权值的影响 ,所以在一定程度上会造成偏差 。因此 ,合理的将两者进行结合,充分利用访问者的知识水平和网页内容特征对pagerank 算法进行改进，得出最终搜索引擎排序优化算法，可以极大的提高这种算法的有效性和正确性。关键词：超链分析，pagerank，算法，访问者，优化abstract in recent years, along with the continuous development of the internet, web has become an important source of information, the people for the people provides abundant information resources. meanwhile, it has the mass data, complexity, and strong dynamics and characteristics of the user to ship polymorphism of the development of resources of excavation caused considerable difficulty. through the analysis and research as a fairly successful based on the analysis of the algorithm is hyperlinked pagerank google, which can effectively measure web importance weights, however, further studies have also shown that this kind of dinkum chain analysis depends not considering the algorithm due to web page visitors the influence degree of important value, so to some extent. therefore, both are reasonable, fully utilize the knowledge level and visitors to page features pagerank algorithm was improved, the search engine optimization algorithm, can sort of improving the correctness and validity of this algorithm.keywords: hyperlink analysis algorithm, the visitor, pagerank optimization 目录1google 搜索引擎简介51.1 google的软件文化理念51.2 搜索引擎的分类51.3 google搜索引擎工作原理362传统google pagerank算法分析92.1 传统google pagerank算法概述492.2 传统 pagerank算法回顾102.2.1传统 pagerank算法代数表达形式102.2.2 传统 pagerank算法向量表达形式122.3 传统google pagerank的缺陷和改进方法133google pagerank 算法改进153.1由访问者知识水平及其投票的情况决定网页排名的 pagerank 算法153.1.1 算法中pr值的含义153.1.2 从投票角度分析算法的本质153.1.3 算法改进的详细设计思路163.2 计算每个访问者的pagerank值173.2.1 计算访问者pr值的数学表达式173.2.2 访问者pr值的循环收敛计算方法193.2.3访问者pr值算法的简单模型213.2.4 visual basic编程验证算法收敛233.2.5 matlab编程验证算法收敛293.3 网页pr值的计算方法373.3.1 计算网页pr值的理论基础373.3.2 建立数学模型383.3.3 visual basic编程验证算法的正确性393.3.4 matlab编程验证算法的正确性424改进算法的事实可行性445将改进算法与google pagerank传统算法结合的最完美排序方法466小结48附录49参考文献51致谢521google 搜索引擎简介1.1 google的软件文化理念根据中国互联网络发展状况统计报告 ( 2005/1) 用户在互联网上获取信息最常用的方法是通过搜索引擎:占70. 7 %。远远高于位于第二位的直接访问已知的网站:占24. 6% 。搜索引擎的后起之秀 google 每天处理的搜索请求已达 2 亿次。现在全球有75%的网上信息搜索是靠google的技术完成，大大促进了人类的信息搜索的效率。而作为品牌价值，仅google这个名字的无形资产，竟出人意料地在如此短的时间，一下子超过了苹果、imb、可口可乐，真正实现了跳跃性的发展。google主页面不以花哨取胜，而以功能表现为本。它的先进的软件理念正是建立在软件功能模块上，研究其功能特点，我们发现google技术上的先进，来自于文化理念上的先进，并敢于打破传统独树一帜1。首先，google用先进的pagerank技术理念，以平等、实用、公正为组织原则，优化整合全球web网页资源。在搜索方法上，google更是化繁为简，为大多数网民利益考虑，做到软件使用大众化。其次，在对待语言工具的问题上，不搞大国沙文主义，真正摈弃了语言上的贵贱之分，将多种语言平等地整合在同一界面，实现了以人为本的软件理念。同时注重创新，注意吸纳新网站，以组成世界信息大家庭，并且充分尊重新网站的特殊要求和选择权利，再进行搜索引擎数据库的录入处理。再次，google的中文搜索引擎的完美设计，体现了设计者的国际市场合作精神，google搜索引擎对中文的支持力度，使它成为目前是收集亚洲网站最多的搜索引擎，同时能够取他人之长，与他人联手，以团队合作精神推出新技术新功能。1.2 搜索引擎的分类搜索引擎是指因特网上专门提供查询服务的一类网站,它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理,并为用户提供检索服务，从而起到信息导航的作用。搜索引擎系统可以分为：目录式搜索引擎、机器人搜索引擎和元搜索引擎。目录式搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新不及时。机器人搜索引擎:是指通过网络搜索软件(又称为网络蜘蛛2,网络爬行机器人,网络搜索机器人) 或网站登录等方式 ,以某种策略自动地在互联网中搜集和发现信息,经过加工处理后建库,从而能够对用户提出的各种查询作出响应,提供用户所需的信息。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是： altavista 、northern light 、excite 、infos2 eek 、inktomi 、fast、lycos 、google ; 国内代表为：“天网”、 “百度”等。本文论述的google 搜索引擎就是机器人搜索引擎，通过网络蜘蛛(crawler) 搜集和发现网页排序所需要的信息。目录式搜索引擎和机器人搜索引擎，各有优缺点，应用都很广泛。机器人搜索引擎的自动化程度比目录式搜索引擎高。网络信息量太大了，用计算机代替人去查找，可以节省大量的人力。元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表是webcrawler 、infomarket 等 .1.3 google搜索引擎工作原理3搜索引擎一般由网络爬行机器人crawler、知识库repository、索引系统(包括索引器indexer，桶barrels ,文件索引等)、排序器sorter和搜索器searcher 5个部分组成。google pagerank一般一年更新四次(由crawler程序的效率及搜索引擎的规模决定)，所以刚上线的新网站不可能获得pr值。你的网站很可能在相当长的时间里面看不到pr值的变化，特别是一些新的网站。pr值暂时没有，这不是什么不好的事情，耐心等待就好了。google pagerank每更新一次都是按照以下的步骤进行：(1)google使用高速的分布式爬行器(crawler)系统中的漫游遍历器(googlebot)定时地遍历网页，将遍历到的网页送到存储服务器(store server)中。(2)存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据repository中。repository获得了每个网页的完全html代码后，对其压缩后的网页及url进行分析，记录下网页长度、url、url长度和网页内容，并赋予每个网页一个文档号(docid)。(3)索引器(indexer)从repository中读取数据，以后做以下四步工作：(4)(a)将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词(wordid)的若干索引项(hits)，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(barrels)中，并生成以文档号(docid)部分排序的顺排档索引。索引项根据其重要程度分为两种：当索引项中的关键词出现在url、标题、锚文本(anchor text)和标签中时，表示该索引项比较重要，称为特殊索引项(fancy hits)；其余情况则称为普通索引项(plain hits)。 顺排档索引和hit的存储结构如图1.1所示。(b)索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其anchor text、url指向等关键信息存入到anchor文档库中。(c)索引器生成一个索引词表(lexicon)，它包括两个部分：关键词的列表和指针列表，用于倒排档文档相连接(如图1.1所示)。 (d)索引器还将分析过的网页编排成一个与repository相连接的文档索引(document index)，并记录下网页的url和标题，以便可以准确查找出在repository中存储的原网页内容。而且把没有分析的网页传给url server，以便在下一次工作流程中进行索引分析。(5)url分析器(url resolver)读取anchor文档中的信息，然后做中的工作。(6)(a)将其锚文本(anchor text)所指向的url转换成网页的docid；(b)将该docid与原网页的docid形成“链接对”，存入link数据库中；(c)将anchor text指向的网页的docid与顺排档特殊索引项anchor hits相连接。 (7)数据库link记录了网页的链接关系，用来计算网页的pagerank值。 (8)文档索引(document index)把没有进行索引分析的网页传递给url server，url server则向crawler提供待遍历的url，这样，这些未被索引的网页在下一次工作流程中将被索引分析。 (9)排序器(sorter)对数据桶(barrels)的顺排档索引重新进行排序，生成以关键词(wordid)为索引的倒排档索引。倒排档索引结构如图所示： 图1.1(10)将生成的倒排档索引与先前由索引器产生的索引词表(lexicon)相连接产生一个新的索引词表供搜索器(searcher)使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引(document index)和link数据库计算的网页pagerank值来匹配检索。在执行检索时，google通常遵循以下步骤(以下所指的是单个检索词的情况)： (1)将检索词转化成相应的wordid；(2)利用lexicon，检索出包含该wordid的网页的docid；(3)根据与lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引； (4)根据各网页的匹配程度，结合根据link产生的相应网页的pagerank情况，对检索结果进行排序；(5)调用document index中的docid及其相应的url，将排序结果生成检索结果的最终列表，提供给检索用户。 这些过程都是离线进行的。当用户在线提交一个查询时，先从反向索引库中查找含有查询关键词的网页，返回一系列相关的网页的docid，由docid在存储pagerank的库中找到它们对应的pagerank值，然后将所有结果进行排序输出给用户。可以看出，整个过程中在线进行的只是查询，所有的计算都是离线进行的，因此搜索引擎能以较快的速度将结果返回给用户。另外，查询过程没有考虑用户提交的关键词和访问者的自身情况。基于链接的pagerank离线进行计算一次后，会在一段时间保持不变。据资料称，google的pagerank计算周期大概是三个月。 2传统google pagerank算法分析2.1 传统google pagerank算法概述4我要做的工作是将pagerank的算法改进，所以先简述google pagerank的情况方便下面的改进修改和对照。超链分析技术主要是指利用网页间存在的各种超链指向, 对网页之间的引用关系进行分析，依据网页链入数的多少计算该网页的重要度权值，一般认为 ,如果a网页有超链指向b网页，相当于a网页投了b网页一票，即a认可b网页的重要性。深入理解超链分析算法，可以根据链接结构把整个网页文档集看作一个有向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的链接就构成了结点间的有向边，按照这个思想，可以根据每个结点的出度和入度来评价网页的作用。其中有代表性的算法主要是 larry page等人设计的pagerank算法和 kleinberg 创造的hits算法。其中pagerank算法在实际使用中的效果要好于 hits算法，这主要是由于以下原因: a. pagerank 算法可以一次性、脱机并且独立于查询地对网页进行预计算，以得到网页重要度的估计值，然后在具体的用户查询中，结合其他查询指标值再一齐对查询结果进行相关性排序，从而节省了系统查询时的运算开销；b. pagerank 算法是利用整个网页集合进行计算的，不像hits算法易受到局部连接陷阱的影响而产生“主题漂移”,所以现在这种技术广泛地应用在许多信息检索系统和网络搜索引擎中，google 搜索引擎的成功也表明了以超链分析为特征的网页相关度排序算法日益成熟。但是 pagerank算法由于只考虑到网页间的超链关系并仅仅以此进行网页重要度的分析，所以不可避免地会产生很多问题，其中，比较明显的问题在于它在计算每个网页具体的重要度权值的时候，根本没有考虑到任何网页本身内容特征对权值的影响，如pagerank算法完全忽略了网页具有的不同主题，不同的主题应该具有不同的重要度权值，进一步说，在用户查询的时候，网页的重要程度值的大小与查询所表达的主题关系很大，其实，在hits算法5中恰恰考虑了这种因素，所以它更易于表达与特定查询主题的相关度排序，有效地在pagerank算法中考虑查询主题对网页权重值的影响是一个有效改进此算法的重要方法，再如，pagerank算法也没有考虑网页的创建时间 ,并不对新旧网页进行有效的区分,相反 ,按照 pagerank 的既有算法甚至会产生旧网页比新网页具有较高重要度权值的可能性。这些都是google pagerank存在的缺点，也是本文对pagerank算法进行改进的原因。2.2 传统 pagerank算法回顾pagerank技术：通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，pagerank 能够对网页的重要性做出客观的评价。pagerank 并不计算直接链接的数量，而是将从网页 a 指向网页 b 的链接解释为由网页 a 对网页 b 所投的一票。这样，pagerank 会根据网页 b 所收到的投票数量来评估该页的重要性。虽然 pagerank 认为网页的链入超链数可以反应该网页的重要程度 ,但是现实中人们在设计网页的各种超链时往往并不严格，有很多网页的超链纯粹是为了诸如网页导航、商业推荐等目的而制作的，显然这类网页对于它所指向网页的重要度贡献程度并不高，但是，由于算法的复杂性，pagerank 没有过多考虑网页超链内容对网页重要度的影响,只是使用了两个相对简单的方法： 其一，如果一个网页的链出网页数太多，则它对每个链出网页重要度的认可能力相应降低；其二， 如果一个网页由于本身链入网页数很低造成它的重要度降低，则它对它的链出 网页重要度的影响也相应降低。综上而言，一个网页的重要性决定着同时也依赖于其他网页的重要性。pagerank绝对是个很科学的小创意。说他科学，你会在我以后的文章中看到google是如何将数学(具体来说多数是统计学)理论淋漓尽致地发挥在搜索技术之中。说他“小”，因为这些理论对于搞数学的人来说实在太微不足道了，甚至稍微有些科学高数知识的人都能理解。他所用到的统计学就是循环迭代计算收敛值的方法！62.2.1传统 pagerank算法代数表达形式按照上面思路，page给出了pagerank的简单定义7： (2.1)此处的u表示一个网页，r ( u) 表示网页u的pagerank值，b ( u)表示链接到网页u的网页集合，即网页u 的链入网页集合，n ( v ) 表示从网页 v 向外的链接数量，即网页v 的链出网页数，c为规范化因子，用于保证所有网页的pagerank总和为常量 (如为1)。这就是算法的形式化描述，也可以用矩阵来描述此算法，设a为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则aij=1/ni，否则aij=0。设v是对应网页集的一个向量，有v=cav，v为a的特征根为c的特征向量。实际上只需要求出最大特征根的特征向量，就是网页集对应的最终pagerank值，这可以用迭代方法计算。具体计算时，可以给每个网页一个初始的pagerank值，然后反复迭代运算，即 ： r(i+1)(v)=r(i)(u)/nu (2.2)此处的 v 代表所有的网页集合,每一个第i+1次的pagerank 值都是基于上次的pagerank值重新计算的。具体的迭代次数在实际运算中是有限的。lawrence page和sergey brin在个别场合描述了pagerank最初的算法。这就是pr(a) = (1-d) + d (pr(t1)/c(t1) + . + pr(tn)/c(tn) 式中：pr(a) :网页a页的pagerank值； pr(ti) :链接到a页的网页ti的pagerank值； c(ti) :网页ti的出站链接数量； d :阻尼系数，0d)/pagerank收敛前的循环计算判断=0.0000000000001i=1for each nnprin(i)= (kijn zijnprin(i-1)kijn)pri=ci= /设置归一化常数,规范因子的计算，以保证计算结果的正确性prin(i)= ci prin(i) /进行规范化得出的结果i=i+1随着循环次数的增加，计算结果越来越收敛，越来越接近真实的pr值，只要循环次数足够多可以得到任何精度的网页pr值。3.2.3访问者pr值算法的简单模型据统计，web已经拥有100亿左右的静态网页和550亿左右的动态网页，网民数量仅中国就有4.16亿，因此，pagerank要处理的矩阵是“世界上最大的矩阵”，为了便于