网页排序问题

1、【E题】网页排序问题指导教师:通信与信息工程学院2010年8月19日网页排序问题摘要随着互联网的发展，搜索引擎的重要性与日俱增。如何有效的查找需要的信息是非常关键的，一个好的搜索引擎可以极大的节省用户查找信息的时间。搜索引擎包含多个组成部分，其中网页排序是搜索引擎设计的核心问题，排序结果的准确率直接决定了搜索引擎的性能和用户体验。信息检索领域中有许多的网页排序算法。而PageRank技术在著名的Google搜索引擎中被成功的应用。使得Google的搜索精度大大超过了以前的搜索引擎。但是这种算法只考虑网页的具体内容和网页的超链接信息，并没有考虑网页的客户应用信息，因此这种网页排序方法并不全面。它

2、会使得用户并不关心的一些网页排在前面，而真正满足用户需要的网页排到了后面。本文对PageRank排序算法做了进一步研究，通过对网页类型、网页更新时问等网页性质进行分析，提出了一种更加全面的网页排序算法。我们对这3个关键因素分别建立了：网页更新时间与网页类型的函数关系TP、网页点击率与网页类型的函数关系CR再结合文档相关度Sim、网页质量Q,最终得到一个可以对网页重要性进行定量说明的网页得分模型：Score=PageRankxTPxCPxSim0根据Score分数的高低进行排序，从而建立了一个新的网页排序规则。最后对所建立的网页排序规则进行验证。我们利用模糊综合评价模型，从宏观角度进行了验证。同

3、时，也利用实验抽样的方法，从微观角度进行了验证。最终得出结论：改进后的网页排序算法是合理的，并且优于现在流行的pagerank排序算法(Google)。关键词：搜索引擎网页排序pagerank算法模糊综合评价蚁群算法1 .问题重述当我们利用搜索引擎，如google、百度等按关键字搜索时，往往希望我们感兴趣的网页靠前排序。实际中你可能也注意到所搜索到的结果是进行了排序的。现在请你们建立数学模型解决下面的问题：1、试设计一种你们认为合理的排序规则，使搜索到的网页结果排序满足要求;2、选取若干个网页为例，试用你们的规则进行一次排序，并说明规则的合理性。2 .基本假设(1)网页的点击是正常的，不存在为

4、了某种利益，进行人为恶意的点击；(2)如果网页排序相差不大的，那么我们认为此类网页的重要程度基本相同;(3)网页的更新时时间是以天为单位；(4)网页都能准确地进行分类，即每个网页都有它唯一对应的类别；3 .主要符号说明PR:某网页的权值(重要性)；Q:某网页的综合得分；cpti：第1个网页的点击率;TP:某网页的更新时间函数；CP:某网页的点击率函数；4 .问题分析当今是一个信息时代，信息的数量呈指数级增长，记载着人们需要的信息和知识的已经不仅仅是传统的书籍和报刊，个人电脑、数字通信设备、网络都储存着大量的信息。众所周知。互联网的规模一直在高速增长，1994年最早的搜索引擎WorldWideW

5、ebWorm标引了11万网页，如今可标引的网页已超过100亿。搜索引擎在网络中的作用越来越重要。人们通过搜索引擎在海量的互联网信息中查找自己所需的信息。互联网上的信息包罗万象，几乎包含了整个人类发展历史中所积累的全部知识，并且还在以每天超过100万张网页的速度增长。如何在此巨大的信息海洋中快速检索到自己想要的信息成为人们最关注的问题。而这个问题的关键又在于搜索引擎，搜索引擎原理如图一。图一搜索引擎原理图1998年，斯坦福大学的SergeyBrin和LawrencePage提出了PageRan©法，并以此为核心开发出的搜索引擎google在商业应用中获得极大成功。由于人们都希望通过搜索

6、引擎尽快找到自己真正所需的信息，作为搜索引擎的核心部分，对所搜索网页的排名算法的优劣自然成为评价一个搜索引擎好坏的主要指标。PageRan©法作为著名搜索引擎google的核心算法而备受瞩目，但仍有自己的优缺点，因此我们对其缺点进行改进，得出更加合理的排序算法。5 .模型建立与求解5.1问题15.1.1（模型一）PageRank算法PageRank算法的主要设计理念是每一个到该网页的链接就是对此网页的一次投票，被链接得越多，就说明有越多的网页愿意将它们自己与此网页挂钩，即链接流行度越高。链接流行度越高，此网页的权值就越大，排名也会更靠前。PageRank算法通过分析此网页被链接的数量

7、和接入网页的质量来确定网页本身最终的权值。PageRank算法模拟用户随机浏览的过程，即当用户浏览网时，其跳转到一个随机页面上的概率是d,即其沿着一个（当前页的）随机链接迁移的概率为1-d。假定这个用户不会回退浏览以前访问过的网页，则此过程可以用Markov链来建模，从而求出每个页面的平均概率。我们将整个网络看成一个有向图，则网页为此有向图中的节点，网页间的链接看作有向边。若网页A中有连接到网页B的链接，即，A指向B,为A对B的一次投票。假设网页A有n个网页对其进行了投票，记为（工,丁2,Tn）,设C（Ti）为网页Ti的外向链接数，PR（Ti）为页面正的权值，则可以得到此网页的权值（重要性）计

8、算公式:PR(Ti)C(T)nPR(A)=d(1-d)vi4其中：d为系统设定的经验值，一般取0.15；PR（Ti）为网页Ti的权值PR（Ti）C（T）被平均分成C（）份后对网页A的投票；（1-d）是为了防止接入页面产生过大的影响而对其传给网页的权值进行阻尼；d是为了弥补阻尼掉的权值为防止网页无外部链接时初始PR值为00PageRank算法通过重复执行算法对网页的权值进行迭代，从而得出网页的PageRank值。网页排序：网页排序是根据网页的得分来进行的。网页的得分分为两个部分，即网页相关性和网页重要性（PageRank值）。计算公式为：Q=PRsim为了更加深入的表示PageRank算法，我们

9、决定对其进行一个简单的演示我们对给定的互联网超链接结构，通过此算法进行模拟排序。Ti>Tjelse01100011010000000000000000100111011002.邻接矩阵H通过规范化进一步约化成矩阵S和随机矩阵S。其中S的图二网页链接实例1.将一个互联网超链接结构考虑成一个图，将图表示成hij=1苴中jh=0,S.一.兀素Sij表小从网页i跳转一次至网页j的概率。得到101/21/2000000000S=1/31/3001/3000001/21/20001/201/2000010但如果网页i没有向外的指向，那么矩阵S的第i行的和将是0,这样的网页叫悬虚网页。它可能是一个pd

10、f文件或者是网页向外指向的超链接还没有被搜索引擎搜集到。所以在将H矩阵变化到矩阵S后，我们可以用向量vT=(1/n)eT来替换矩阵S中行和为0的行，eT是一个全1的行向量。定义s'=S+deT/n,其中d是一个标记悬虚网页的向量：di=1di=0,第i个网页是悬虚网,第i个网页不是悬虚通过这种处理，S不再有行和为0的行了，S是一个随机矩阵,此时'01/21/20001/61/61/61/61/61/6'1/31/3001/30S=000001/21/20001/201/20001003.Google矩阵为',T',TG=dS+(1-d)E=dS+(1-d

11、)/nee所以11X1G=0.85xS+0.15x-x161一11111-1/409/209/201/401/401/401/61/61/61/61/61/637/12037/1201/401/4037/1201/401/401/401/401/409/209/201/401/401/409/201/409/201/401/401/409/101/401/40PageRank向量，也是Google矩阵特征值为1时所对应的特它的平稳分布即征向量4,求解Google矩阵的平稳分布为i：T=二TgTJ；e=1T-0.05170.07370.05740.34870.19990.2686相应的网页重要性

12、排序结果为：表网贝123456排名6451325.1.2(模型二)PageRank改进算法模型1、模型的提出当我们利用搜索引擎，如Google、百度等按关键字搜索时，往往希望我们感兴趣的网页靠前排序。实际中我们也注意到所搜索到的网页是进行了排序的。通过查阅资料发现Google搜索引擎所使用的搜索算法只是考虑网页的具体内容和网页的链接信息，并没有考虑网页的客户应用信息，因此这种网页排序方法并不全面，它会使得用户并不关心的一些网页排在前面，而真正满足用户需要的网页排到了后面。本文模型二对网页排序进行了进一步研究，通过对网页更新时间、网页点击率、网页类型进行分析，从而对网页的质量进行优化，提出一种更

13、加全面的网页排序算法并在后文中得以有效的验证。(1)网页更新时间：网页更新时间即为网页上次更新时间，我们可以能过输入javascript:alert(document.lastModified)命令来获取。网页年龄(单位：天)T=t0-1,其中t。为为当前时间，t为网页的更新时间。我们认为网页年龄小的网页质量高，应该排在前面。用户不关心的而又长时间没有更新的网页应该排在后面。(2)网页点击率：我们定义网页点击率为一个网页的被点击次数和上述网页年龄之比，而网页点击次数可在(3)网页类型：仅仅考虑网页更新时间和网页的点击率是不够的。不同的网页类型对更新时间的要求不同，如体育新闻、财经信息等对更新时

14、间的要求较高，而地理知识、编程技术等文本对更新时间的要求就相对比较低。同样网页点击率也和网页类型相关。因此，我们在把网页更新时间和网页点击率作为网页排序考虑因素的时候，必须要考虑网页类型的影响。2、模型的建立按照网页内容对网页更新时间和网页点击率的要求将网页进行类型分类，比如可以按Yahoo分类方法将网页分类(Yahoo将网页分为14个顶级类，分别是：1艺术与人文、2商业与经济、3电脑与因特网、4教育、5娱乐、6政府与政治、7健康与医药、8新闻与媒体、9休闲与运动、10参考资料、11区域、12科学、13社会科学、14社会与文化)。(1)网页更新时间与网页类型的函数关系:定义网页更新时间的相关函

15、数CP=(1cti)/(1cti*Ti/T)其中%值表示网页类型i的网页质量对更新时间的依赖，在(0,1)范围内取值。对更新时间要求较高的网页类型，cti取较大的值，对更新时间要求较低的网页类型，cti取较小的值。这样就可以把TP作为计算网页质量Q的一个因子.用来表示网页更新时间对网页质量的影响。(2)网页点击率与网页类型的函数关系：分别计算每个网页的点击率：cpti=clicksT定义网页点击率的相关函数：1ncpt=-gcptiniH4_(cpt+cgXcpti)CP-(1+cci)Mcptcci值表示网页类型i的网页质量对点击率的依赖。用户点击率较高的网页类型，CCi取较大的值，用户点击

16、率较低的网页类型，CCi取较小的值。(3)改进后的网页排序：综合排序中需要考虑的因素有：文档的相关度Sim、网页质量Q而网页质量的贡献又来自于网页的超链接信息、网页类型、网页更新时间和网页的点击率。网页得分的计算公式：Score=QSim.Q=PageRankTPCP其中，PageRank网页的Pagerank值，Sim为网页相关度，TP为网页的更新时函数，CP为网页点击率函数。对于每一个网页计算Score值，然后根据Score值由高到低进行排序。得分高的网页靠前排，得分低的网页靠后排。综上所述，得到模型二，即改进后的网页排序模型可归纳为:TP=(1cti)/(1cti*T/T)(cpt+cG

17、Mcpti)CP(1cci)cptScore=PageRankTPCPSimQ二PageRankTPCP建模流程概括如下:图三网页排序计算过程流图5.2问题2我们现在需要做的工作是对新的网页排序规则进行评判，看它是不是更加的合理、实用。为了比较准确的评判规则的优劣，我们采取了从宏观与微观两个相互补充的层面，利用数学知识进行数学建模，从而得出两个评价模型。5.2.1 宏观评价模型模糊综合评价法是一种基于模糊数学的综合评价方法。这个综合评价法根据模糊数学的隶属度理论把定性评价化为定量评价，即用模糊数学对收到多种因素制约的事物或对象做出一个总体的评价。它具有结果清晰，系统性强的特点，能较好地解决模糊

18、的，难以量化的问题，适合各种非确定性问题的解决。因此，我们在做对网页排序规则宏观评价的时候，决定采用此种方法。经过参考大量的前人研究及相关论文，归纳出判别网页排序规则优劣的3个关键因素，分别是网页准确性，网页安全性，网站的性能。现对这3个关键因素进行比较细致的说明：网页准确性：我们所搜索出的网页与我们输入关键字的接近程度。接近程度越大，则该网页准确率越高，进而该网页的排序规则越好。网页安全性：我们所搜索出的网页是恶意广告与病毒的概率。概率越低，网页的安全性越好，进而该网页的排序规则越好。网站的性能：我们所搜索出的网页的载入时间。时间越短，网站性能越好，进而该网页的排序规则越好。接下来，可以简单

19、地得到宏观评价模型：.确定评价对象的因素论域3个评价指标，U=(网页准确性，网页安全性，网站性能).确定评语等级论域V=(好，中，差)，并用李克特量表进行赋值，C=(5,3,1)。.确定评价因素的权向量通过相关论文的研究，可以确定出这3个因素的权向量：A=(0.50.30.2卜.建立模糊关系矩阵R我们分别通过两个网页排序规则进行关键字网页搜索，统计出了各自的性能。现逐个对被评价事物从每个因素u(=1,2,3)上进行量化，从而确定模糊关系矩阵：表二评价算法方案准确性安全性网站性能好中差中低好中差Pagerank排序算法0.80.10.11000.750.20.05改进的排序算法0.90.1010

20、00.70.250.055.合成模糊综合评价结果向量基于上述3个关键因素，分别对上述两种算法进行计算，求出所对应的综合评价矩阵：0.80.10.1B1=A®R1=(0.5,0.3,0.2)®1000.750.20.05二：i0.50.20.10.90.10B2=A®R2=(0.5,0.3,0.2)1000.70.250.05=0.50.20.056.计算得分因此可以得到Pagerank排序算法的得分：TCS1=BiC=4.00同时得到改进排序算法的得分:CS2=B2CT=4.20通过上面的计算，易知CS1<CS2,故而我们可以得出改进的排序算法优于pager

21、ank排序算法。根据客观事实，我们知道现在google这个搜索引擎采用的网页排序算法就是pagerank排序算法。而google作为搜索引擎显然是成功，因此可以说明pagerank排序算法是合理的，优秀的。当然，也就说明了我们改进的排序算法更是合理，优秀的。5.2.1微观评价模型不同的网页排序规则会产生不同的检索结果。我们用传统的网页排序算法（PageRan簿法）和以上我们改进的网页排序规则进行比较。首先，我们在Google搜索引擎中输入“毛泽东”作为关键字查询项，返回了17000000多项查询结果。我们取其前10项作为对比数据，比较pagerank排序算法和改进的网页排序算法的网页排序结果。

22、由于这些网页是在17000000多项项查询结果中选取的前10项（Q值最高的前10项）,因此Q1Q2,Q10的值相差不大，并且有Q1>Q2>AQ10。这里我们近7f以Q1=Q2=,=Q100现在我们用改进的网页排序算法对这10项查询结果重新计算，这里取ct4=0.4,ct8=0.8,ct10=0.2,004=0.5,cc8=0.3,cj。=0.7。利用模型二的算法可以得出下表：表三网页网页回Pagerank*SimTi/cpti/cptTPCPQ=Pagerank*Sim*TP*CP重新排名114社会Q10.00136.20141.79812.20033.9564q,51128新闻Q

23、20.00661.72561.19841.29881.5565q23314社会Q30.02110.67511.19500.86621.0351q3548新闻Q42.60690.00300.58390.76990.4495Q49514社会Q50.00921.23261.78681.05371.8828q52614社会Q60.85670.01601.02470.59510.6097Q67714社会Q72.76480.00190.77310.58900.4553Q7888新闻Q80.14610.07771.61900.78721.2688Q8498新闻Q93.37020.00440.71720.59

24、000.4232q910104教育Q100.23030.06171.28210.68720.8811Q106通过结果分析：利用改进的网页排序规则对Google搜索出的前10项网页重新搜索的排序次序已经发生了明显的变化。网页4、9的类型是新闻类的，可它却2000多天都没进行更新，这显然违反了新闻媒体的时效性。这种网页完全是应该被删除的，更不应该排在这么靠前的位置。在一点上，Google处理的显然不是很好，而我们的改进方法就很好的处理这种现象，把他们都排在了最末。根据常识，我们也应该了解大多数人搜索“毛泽东”的目的是为了了解毛泽东的生平事迹。凭着“搜索引擎应该人性化”的特点，故这类的网页应该排在最

25、前面。在一点上，改进的方法是比原方法处理得好的，比如，现在的毛泽东的生平事迹（社会类）的网页1、5排在了最前面。因此，从微观角度，也能得出改进的算法优于pagerank排序算法。综合宏观与微观两个角度，我们可以得出结论：改进的网页排序算法是合理的，并且优于现在流行的pagerank排序算法（Google）。.模型评价模型的优点我们的网页排序规则是基于现行pagerank排序算法，对其进行改进而得到的。这种那个算法对网页质量的评价更加全面，能更好地用于对网页的排序，使用户得到真正需要的查询结果，同时很好地体现了“人性化”。只需对现有的搜索引擎的网页排序算法简单加入我们的考虑因素，建立类似于我们的

26、改进算法，就能提高现有的搜索水平。因此，我们的改进方法有很好的实用价值与推广价值。模型缺点相比于现在流行的搜索引擎算法，我们改进后的网页排序算法虽然取得了一定的效果，但是算法思想还较为简单，一些系数的选取还需要做进一步的研究，如若在海量网页中作出更细致的统计分析，相信会得到更加满意的排序结果。另外，由于需要用到网页分类的信息，因此还需要研究目前较为前沿的网页类型分类技术，从而使我们的网页排序算法更具有时效性。.模型的改进针对模型二的不足之处，设想如果把我们引入的三个主要因素（即网页更新时间、网页点击率、网页类型）分别和蚁群算法结合起来，相信会得到更加精确的排序结果。下面以其中一个因素为例子进行

27、简单的说明，我们不妨选取网页的点击次数这一因素来和蚁群算法进行结合。考虑搜索完成以后所显示网页被点击的次数。对应于蚁群算法，建立以下映射其过程用到网络中网页排序的过程：1）用户T蚂蚁；2）关键字T食物；3）网络链接T不同路径；4）用户对链接的点击T蚂蚁留下的信息素。当用户通过关键字检索后，根据自己的主观判断对搜索显示的网页做出自己的选择。因为每个人判断的主要依据是网页链接与其所需信息的关联程度，所以那些真正被用户需求的网页会被大部分用户点击，其相应的信息度就会越来越高。我们可以通过对当前网页被点击的次数进行一定的函数变换，将其值作为网页本身权值的修正项，从而影响网页的排名，使用户能更快地找到其

28、所需的信息。通过蚁群算法的信息嫡的概念将用户的群体选择加入到网页权值计算中去，从而提高相关网页的查准率。当然，其它两个因素和蚁群算法的结合同样可以提高网页搜索的准确率各高效性，这里不再赘述。参考文献与网页1何晓阳，吴强，吴治蓉，HITS算法于PageRanK法比较分析J,情报杂志，2004,17(3):77-802吴淑燕，徐涛，PageRank算法的原理简介J,图书情报工作，2003,26(2):364-3673CordonS.LinoffMichaelJ.A.BerryMiningtheWeb:TransformingCustomerDataintCustomerValue4戚华春，黄德才等，具有时间反馈的PageRan畋进算法J,浙江工业大学学报，2005,33(3):272-2755宋聚平，王永成等，对网页PageRank算法的改进J,上海交通大学学报，2003,37(3):397-4026王立新，模糊数学与模糊控制教程M,北京：清华大学出版社，20037附录1functionQidxTPCP=quantity(day