Pagerank算法与网页排序方法的建模

Pagerank算法与网页排序方法的建模摘要随着互联网的飞速发展,各种杂乱无章的信息充斥其中，如何对数以亿记的相关网页进行排序成为搜索引擎的核心问题。针对这个现象本文根据题目要求建立了两个模型：模型一：结合Google的Pagerank算法，建立了网上冲浪模型，得到Pagerank算法定义：nii1iPR(T)PR(A)(1d)dC(T)用迭代算法通过MATLAB编程计算出网页的PR值；模型二：由于传统PR值算法仅考虑网页的外链和内链数量，偏重于旧网页；另外，传统算法不能区分网页中的链接与网页的主题是否相关，容易产生主题漂移现象；考虑其算法存在的缺陷，在此基础上为给出对搜索网页进行排序的方法，着重考虑搜索出的网页以下几个方面：外链，内链，时间反馈因子和相关度，对PR值进行改进，得到以下公式：WtVVTsimVTVsimTPRddpPRkimjjiiPi11,,)()()()1()(以PR值的高低来对搜索网页进行排序；对于如何使新网站在搜索引擎中排名靠前，从影响网页的PR值的因素：內链、外链、时间反馈因子和相关度出发对提高网页的PR值以使其在搜索引擎中排名靠前给出了稳健的建议。关键词Pagerank迭代算法MATLAB时间反馈因子相关度一、问题重述随着互联网的发展，面对众多杂乱无章的信息，如何对数以亿计的相关网页进行排序成为搜索引擎算法的核心问题。一个搜索引擎的算法，要考虑很多的方面。主要是“域名、密度、内链、外链、相关度、服务器稳定、内容更新、域名时间、内容数量”这些方面。不同的搜索引擎侧重点也不同，比如Google，它对收录的网站有一个重要性排名的指数，被称为Pagerank，作为对搜索网页排序的重要参数。根据搜索引擎与Pagerank，考虑如下问题：1.考察Google的Pagerank算法，建立数学模型，给出合理的Pagerank的计算方法；2.如果你是搜索引擎的建设者，请考虑你会侧重考虑搜索网页的那些方面，给出你对搜索网页进行排序的方法；3.如果你是某新网站的建设者，请考虑使你的网站在第2题中你建立的搜索引擎中排名靠前的方法。二、问题分析互联网的迅速发展，使现有的搜索引擎面临着巨大的挑战，面对众多杂乱无章的信息，如何对数以亿计的相关网页进行排序成为搜索引擎算法的核心问题，因此，搜索引擎排序算法也就称为众多搜索引擎关注的关键问题之一。对于问题1，根据题目要求，结合Google的Pagerank算法，PageRank算法的基本思想是：页面的重要程度用PageRank值来衡量，PageRank值主要体现在两个方面：引用该页面的页面个数和引用该页面的页面重要程度。若B网页设置有连接A网页的链接(B为A的导入链接时)，说明B认为A有链接价值，是一个“重要”的网页。当B网页级别(重要性)比较高时，则A网页可从B网页这个导入链接分得一定的级别(重要性)，并平均分配给A网页上的导出链接，由此建立了网上冲浪模型，用迭代算法计算出网页的PR值。对于问题2，经过对Google的Pagerank算法的分析，发现该算法仅考虑了搜索出的网页的外链和内链的数量，以此来确定网页的PR值偏重于旧网页，即越旧的网页排名越靠前；对一个刚放到网上不久的新网页，指向它的网页就很少，通过计算后的PR值就很低，在搜索结果中也就被排在了靠后的位置。然而在有些时候，比如新闻类网页和商务性信息，用户当然是希望先看到新的网页，因此我们在计算PR值时考虑加入时间反馈因子，使得在网络上存在时间比较长的网页被沉下去，在搜索结果中被排在靠后的位置；存在时间短的网页就会浮上来，在搜索结果中被排在较靠前的位置，方便用户查看。时间反馈因子利用搜索引擎的搜索周期来表征，即如果一个网页存在时间较长，它将在每个搜索周期中都能被搜到，对网页采取在同一个周期里不管搜到该网页几次，都算一次处理的方法，网页的存在时间正比于搜索引擎搜到该网页的次数，时间反馈因子与网页的存在时间成反比关系。另外，Google的Pagerank算法是基于网页链接结构进行分析的算法，不能区分网页中的链接与网页的主题是否相关，这样就容易出现搜索引擎排序结果中大量与查询主题无关的网页的现象，即产生主题漂移现象。为解决这个问题，引入主题相关度这个概念。主题相关度就是搜索出的网页与其链入和链出网页的相似度，可用余弦相似度来度量计算。在加入了时间反馈因子和相关性因素后，改进网页的PR值的算法，以PR值高低的来对搜索的网页进行排序。对于问题三，主要通过模型二的结果，加强有力的因素，避免不利的方面三、模型假设与符号说明3.1模型假设3.1.1问题1的模型假设（1）假设网页集合的主体之间有相关性，并且体现在他们的相互链接上；（2）假设用户一开始随机访问网页集合中的一个网页，以后跟随网页的外向连接向前浏览网页，不考虑他们后退的情况；（3）假设用户的大部分浏览具有相关性，或者说连贯性，当然也不排除用户直接跳转到无关网页的可能性；（4）假设用户顺序浏览网页，不考虑他们在网页上驻留的时间。（实际上如果用户在一个页面驻留时间长，那应该付给这个页面更大的权值，不过很难找到方法度量）。3.1.2问题2的模型假设（1）服务器的速度在正常范围之内，稳定性很好，质量很高；（2）每个页面的title和meta标签都不同，并且要与该页面的内容相符合；（3）title和meta标签中的关键词密度适当，核心关键词合理出现4次左右；（4）网页的排版满足用户的要求；（5）直接采用包含关键词的域名，文件名采用关键词；（6）导航结构清晰明了；（7）用户浏览网页的行为是和用户查询的主题相关的；（8）某一兴趣分类下的查询所获得的文档大都与该兴趣分类相关。3.2符号说明3.2.1问题1的符号说明（1）PR(A)：网页A的级别；（2）iPRT（）：网页iT的级别，页面iT链向页面A；（3）iC(T)：网页iT的外链数量。（4）d：阻尼系数，0d1；nii1iPR(T)dC(T)表示在随机模型中网页将自身d的份额的PR值平均分给每个外链。3.2.2问题2的符号说明（1）tW：时间反馈因子；（2）T：网页被搜索引擎搜索到的周期数次数；（3）e：常数，取值受到阻尼系数d的影响。四、模型建立与求解4.1模型建立4.1.1问题1的模型建立网页的等级一般是由该页面的链入数量和该页面的链入网页的PR值，以及该页面的链入网页的链出数量共同决定的。因此，假如要计算网页A的等级，那么它的PR值就是链入网页A的页面除以该页面的链入页面本身的链出数量的和。简单计算方法如图1所示，网页1被3个箭头所指向，假定共计得到100分。然后通过链接平均将这100分均分给它所指向的两个网页，网页2和网页3，平均分配是因为点击两个链接的可能性是相等的，通过计算每个网页得到分数的多少评价网页的重要性。26.55026.53253253网页1100网页253网页39网页450图1网页是彼此相连的，所以分数会不断传递下去，但PageRank的计算是收敛的，如图2所示，可知这3个网页的分数之和无论如何循环总是1，这种特性在数学上称为“不变分布”，这也是PageRank计算收敛的原理。网页A网页B0.20.20.20.4网页C0.40.20.4图2因此，其算法可定义如下：11nnnii1iPR(A)(1d)d(PR(T)/C(T)PR(T)/C(T))PR(T)(1d)dC(T)（1）在此假定网页集合为n个网页，通过外链方式其中任何一个网页就有n个可能的无条件去出。每种跳转的概率相等(均为1/n)，因此网页A得到了每个网页的(1/n)的（1-d）的分数。每个网页的分数初值都为1，其总值将总为n，因此1-d的分数是一个网页的基本分数，是固定不变的常数。另外，网页存在明确的指向网页A的链接，因此nii1iPR(T)dC(T)的分数分配给网页A。此算法不以站点排序，每个链入页面的贡献值都不同：如果iT页面中链出越多，它对当前页面A的贡献就越小，A的链入页面越多，其网页级别也就越高。阻尼系数的使用，可以减少可以减少其它页面对当前页面A的贡献。4.1.2问题2的模型建立在传统PR值算法基础上，引入时间反馈因子和主题相关度这两个因素，对PR值算法进行改进，作为对搜索出的网页进行排序的标准。4.2.1.1时间反馈因子网页的时间反馈因子用tW表示，网页被搜索引擎搜索到的周期数次数用T表示，时间反馈因子可表示为：tWe/T其中，e为常数，取值受到阻尼系数d的影响。4.2.1.2主题相关度余弦相似度是计算文件间距离的基本方法，假设有网页p和q，它们的虚拟文档向量为Vp和Vq，它们的相关性可表示为：pqp,qpqVVsim(VV)VV这个模型定义主题相关度，计算中可以令],,[,3,2,1,3,2,1mkqooooiiiiV，其中，1,2,3,kiii,i是网页p的实际链入网页的编号，moooo,,3,2,1是网页p的实际链出网页的编号。通过表达式可以发现，)(,qpVVsim是介于0到1之间的实数，它的值越接近于1，两个网页就越相关；值越接近于0，表明两个网页相关性越小。因此，在传统算法基础上，引入时间反馈因子和相关度后建立的PR值算法为：WtVVTsimVTVsimTPRddpPRkimjjiiPi11,,)()()()1()(此算法克服了传统算法偏重于旧网页及容易产生主题漂移的弊端，这样，在搜索引擎排序结果中比较新的重要网页就会排在比较靠前的位置，方便用户浏览。4.2模型求解4.2.1问题1的模型求解为计算出网页的PR值，采用迭代算法，用MATLAB编程（见附录1）可计算出PR值，在此以图2中网页关系给出具体计算方法。首先初始化一个矩阵P，若网页i存在一个指向网页j的链接。则ijp1；否则ijp0，则有011P001100取阻尼系数d=0.85，用MATLAB计算直到最后两次的结果相近或相同的情况下迭代结束。得结果为:表格1排名PR值网页11.19214299A21.163321999C30.644535000B迭代步数=16从结果可以看出，在这3个网页中，网页C级别最高，其次是网页A，最后是网页B。因为网页C被网页A和网页B指向；网页A被更高级别的网页C指向，而网页B被网页A指向，由于网页C的级别大于网页A，因此最终网页A的重要性大于网页B，与实际情况相符。4.2.2问题2的模型求解在计算该模型时，计算比较复杂，为了简化计算，可以参考传统的Pagepank算法在计算PR（p）时是依赖其链出网页Ti的PR（Ti）值的算法，同样该模型也是依赖其链出网页的PR（Ti）值，因此，在计算时，可以令：mijk1sim(i,j)S(i,j1,2,,N)sim(j,k)得到矩阵s，那么只要给出所有网页的PagePank值初始向量PR0，网页P的PagePank的值向量就可以通过迭代公式计算：)1(1mdPRmSdPR,3,2,1m由于矩阵1SS在，根据线性代数知识，迭代是趋于收敛的，是有限次的迭代运算。同样可以通过MATLAB编程求解。五．模型的检验与改进本段将建立一个实验模拟系统，来验证算法的可行性和有效性，通过构建Nutch系统，来验证改进后的算法确实可以提高搜索引擎搜索结果的准确性。选择Nutch作为搜索引擎基础构建平台。下载Tomcat6.0,JDK和Eclipse作为开发平台。Nutch的主要功能分为爬虫crawler和查询searcher两个部分，Ｃｒａｗｌｅｒ爬虫主要负责从网络上抓取网页建立索引，Ｓｅａｒｃｈｅｒ主要是利用索引，检索用户的查询关键词来产生查找结果。5.1系统流程管理员首先通过用户界面输入要查询的关键字，然后爬行程序根据输入的相关信息在互联网上搜集网页，将搜集到的网页存入数据库，然后再对网页进行预处理，分类后根据修正后的PagePank算法计算出网页的排名，最后，通过用户输出。可以用下面的图3表示管理员接口Crawer爬取网页建立搜索网页与处理计算网页PR值输出在验证算法的