一种基于用户角色的综合网页排序算法

计 算 机 工 程 第37卷 第7期

Computer Engineering V ol.37 No.7

文章编号：1000—3428(2011)07—0053—03·软件技术与数据库·

2011年4月

April 2011

文献标识码：A

中图分类号：TP301.6

一种基于用户角色的综合网页排序算法

龙文明，彭敦陆，姜兴龙

(上海理工大学光电信息与计算机工程学院，上海 200093)

摘 要：通过对网页用户角色的分析发现，传统的基于PageRank算法的搜索引擎结果排序欠佳，是因为其没有兼顾所有角色对网页重要性的评价。为此，提出一种结合了所有角色评价的综合网页排序算法——ComPageRank(CPR)算法和一种基于点击量分析的Click- throughRank(CTR)算法。实验结果表明，相比PageRank为代表的网页排序算法，CPR算法更全面、合理。 关键词：网页排序；PageRank算法；综合网页排序算法；点击量分析算法

Comprehensive Page Ranking Algorithm Based on User Roles

LONG Wen-ming, PENG Dun-lu, JIANG Xing-long

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China) 【Abstract】According to the analysis of the user roles, this paper uncovers one reason of the disadvantage of PageRank–based searching engines, that is, lack of the evaluation of the pages’ importance from the point of view of all the roles. A comprehensive page ranking algorithm——ComPageRank(CPR) is proposed. The algorithm takes account the evaluation of all the roles. In addition, a Click-ThroughRank(CTR) algorithm is developed to analyze the click-through. Experimental results show that CPR is more comprehensive and reasonable compared with the PageRank-based algorithms.

【Key words】page ranking; PageRank algorithm; comprehensive page ranking algorithm; Click-ThroughRank(CTR) algorithm DOI: 10.3969/j.issn.1000-3428.2011.07.018

1 概述

如今有超过80%的人在利用搜索引擎获取网络信息。然而，目前的搜索引擎却存在着检索结果欠佳的局限性。因此，有必要对网页排序进行深入研究。

网页排序分为动态排序和静态排序。著名的静态排序算法有：PangRank[1]，通过对网页间相互引用的关系分析，改变了通过计算关键词和文本的相似度来对网页进行排序的传统检索方式，开创了静态排序的先河；fRank[2]，对独立于超链接的网页特征进行分析，收集用户浏览网页的频率用于改善排序结果；SocialPageRank(SPR)[3]，对社会化注释进行分析，使得检索结果具有语义分析的优点。本文从网页用户的角色入手，选取了最能代表各用户角色的网页评价量来对一个网页的重要性进行综合评价。

次数决定，所以，该算法仅从网页制作者和网页搜索者的角度进行评价；SPR是基于社会化注释分析的算法[3]，由于社会化注释仅由网页注释者给出，因此该算法仅从网页浏览者的角度进行评价。可见，这些算法均未兼顾所有角色的评价。

3 PageRank及SPR算法介绍

3.1 PageRank算法

PageRank[1]算法借鉴了传统情报检索理论中的引文分析方法，建立在随机冲浪者模型上，算法表达式如下：

PR(u)=(1 α)/N+∑PR(v)/N(v) (1)

v∈B(u)

2 网页用户的角色

一般来说，网页用户分为以下3个角色：

(1)网页制作者。网页的创建者，为搜索引擎提供了最基本的搜索材料。

(2)网页浏览者。是社会化注释的创建者，他们浏览网页，并对感兴趣的网页标注社会化注释。

(3)网页搜索者。是用搜索引擎来检索网页信息的用户，他们从搜索引擎返回的结果集中挑选贴近自己所需信息的网页并点击浏览。

基于以上角色的划分发现：PageRank是基于超链接分析的算法[1]，超链接仅由网页制作者创建，所以，这2个算法仅从网页制作者的角度进行评价；fRank是基于网页内容层次和搜索引擎点击率等特征进行分析的算法[2]，内容层次仅由网页制作者布局给出，点击率仅由网页搜索者访问网页的

其中，PR(u)表示网页u的PageRank值；B(u)表示链向网页u的网页集；v表示链向u的网页；N表示网页的数量；N(v)表示网页v的超链接数；α为衰减因子(Google取0.85)。

PageRank算法具有以下缺点：(1)PR值平均分配；(2)主题漂移[4]；(3)偏重于旧网页；(4)偏重于综合性网页。

鉴于以上缺点，很多学者在PageRank算法的基础上做了许多的改进工作：文献[5]提出TS-PageRank算法，通过使用已有的主题来代替网页搜索者检索的关键字，从而弥补了缺点(2)；文献[6]提出TCPageRank算法，通过为被链接的网页赋予一个权值，弥补了缺点(1)、缺点(2)。目前，尚未有较好的算法弥补缺点(3)、缺点(4)，本文提出的算法能有效地弥补这2个缺点。

基金项目：上海市自然科学基金资助项目(10ZR1421100)；上海市教委创新基金资助项目(08YZ98)

作者简介：龙文明(1985－)，男，硕士，主研方向：数据库技术，数据挖掘，综合网页排序算法；彭敦陆，副教授；姜兴龙，硕士 收稿日期：2010-08-20 E-mail：longwenming3319@http://www.77cn.com.cn

54 计 算 机 工 程 2011年4月5日 3.2 SPR算法

社会化注释是Web 2.0技术的一种运用，是网页浏览者用标签对自己感兴趣的网页进行的概括性标注。

SPR算法的表达式[3]如下：

SPR=Pi=(M·MT)·Pi-1=(M·MT)i·P0 (2)

CTR算法的表达式如下：

CTR(u)=

11C(u)

(3) +(1

T(u)T(u)max(C)

其中，M = MPU·MUA·MAP，NA为社会化注释集；NP为网页集；

NU为网页浏览者集；MPU为网页与网页浏览者之间的关系矩阵NP×NU；MAP为社会化注释与网页之间的关系矩阵NA×NP；MUA为网页浏览者与社会化注释之间的关系矩阵NU×NA；矩阵元素MPU(pi,uj)表示网页浏览者uj在网页pi上使用社会化注释的数量；矩阵元素MAP(ai,pj)表示网页pj上使用社会化注释ai的网页浏览者的数量，矩阵元素MUA(ui,aj)表示网页浏览者ui使用社会化注释aj进行注释的网页的数量。

算法描述[4]如下： 第1步 Input：

输入矩阵MPU、MUA及MAP并随机初始化P0 第2步 Do：

Ui=MTPU·Pi Ai=MTUA·Ui P’i=MTAP·Ai A’i=MAP·P’i U’i=MUA·A’ i Pi+1=MPU·U’i

其中，CTR(u)表示网页搜索者对网页u的评价得分；T(u)表示网页u被搜索引擎网页爬虫所爬到的周期总数；C(u)表示网页u上一个周期的点击量；max(C)表示上一个周期点击量最大的网页的点击量。

通过分析式(3)可知，1/T(u)起到使新网页上“浮”，旧网页下“沉”的作用。当网页u第1次被爬虫爬到时T(u)=1，它的点击次数C(u)=0，但CTR(u)=1，这是满分，表明CTR算法极力推荐新网页。随着网页u被爬到的周期总数T(u)的增加，1/T(u)会逐渐变小，这意味者网页u逐渐地变“旧”，若该旧网页是一个比较受网页搜索者欢迎的网页，那么通过式(3)后半部分的计算，它仍然可以获得很高的CTR值，同理，若该旧网页不受网页搜索者欢迎，则它的CTR值就会比较低。

分析 …… 此处隐藏：7002字，全部文档内容请下载后查看。喜欢就下载吧 ……