一种基于空间向量模型的主题PageRank算法

摘要：该文基于传统的PageRank链接分析原理，分析了PageRank在页面主题内容分析方面的不足之处，结合传统的基于内容的VSM文本分析模型，提出了一种基于向量空间模型的主题算法，并通过实验对改算法的性能进行分析。

关键词：PageRank；VSM；网页排序；搜索引擎

中图分类号：TP312文献标识码：A文章编号：1009-3044(2009)04-0883-03

A Vector Space Model Based Topic PageRank Algorithm

ZHANG Ran1, XIA Su-ping2

(Department of Statistic and Information Management, Xinjiang University of Finance Economics, Urumuqi 830011, China; 2.Department of Computer, Xinjiang Technical College of Building, Urumuqi 830054, China)

Abstract: The article base on the principle of traditional PageRank, discussed the shortage of the PageRank in topic rank. Combination of traditional content-based VSM model, a vector space model based topic PageRank algorithm is presented. At last, the conclusions were summarized and future research directions were discussed.

Key words: PageRank; VSM; Web page ranking; search engine

1 前言

目前在搜索引擎中常用的页面排序方法是PageRank[1]方法，利用web页面间的超链结构来计算每个页面的权重。但是PageRank算法会忽略某些页面的内容，一些与用户兴趣无关的知名网站也会被赋予过高的权重。致使用户很难从中快速筛选出真正需要的信息。如果搜索引擎只返回相关度高的重要网页，这样既可以很大程度地节省用户时间，又可以减轻网络流量。

文中提出了一种基于向量空间模型的主题PageRank页面排序算法，结合基于内容和基于链接分析权重各自的特点，构造出主题PageRank算法。

2 PageRank

2.1 PageRank理论模型

PageRank的基本思想来自传统文献计量学中的文献引文分析，即如果一个页面被多次引用，那么这个页面很可能是重要的；如果一个页面尽管没有被多次引用，但是却被一个重要的页面引用，那么这个页面很可能是重要的；一个页面的重要性被均分并传递到它所引用的页面。基于这种思想：设u是一个web页面，Fu是u引用的页面集合，Bu是引用u的页面集合，则网页u的重要性R（u）可定义为：

■(1)

其中，Nu表示u引用的页面个数，c为规范化因子。

2.2 修正的PageRank算法

公式(1)有一个假设前提：所有的页面链接形成一个强连通图。但是实际的网络超链接环境没有这么理想，会存在一些没有外出链接的独立页面或页面集合，这种页面称之为悬挂页面（dingle page）。因为这种页面没有外出链接，所以在迭代计算的时候页面的重要性时，它不会传出任何重要性，这将导致一个称之为等级泄露（rank sink）的重要问题。为了解决这个问题，必须引入一个等级源[2]（rank source）来补充每个页面的PageRank值，以使得PageRank值不完全依赖于网络链接。因为浏览者在网络上浏览网页的过程实际是一个随机的过程，浏览者很少会沿着一个链接向下一直走到底。在每一个页面，浏览者都有可能不再对本页面的链接感兴趣，从而随机选择一个新的页面开始新的浏览。所以修正后的PageRank定义为：

■ (2)

公式（2）中的等级源E一开始是为了修正页面间的等级泄露而设计的，后来Page和Brin又提出了E在调整页面的排列顺序方面的作用。它认为浏览者每一次在随机选择一个新的页面并开始新的浏览时，都会与个人的兴趣有关。于是可以根据不同浏览者的喜好，构造不同的等级源E，从而提出了PageRank在主题个性化方面的应用前景。

3 利用空间向量模型构造个性化的PageRank算法

从上面的分析，我们可以看到主题PageRank的关键就是等级源的构造。通过对每一个页面进行基于主题的分类，然后针对每一个主题分别计算出对应主题的主题性页面等级得分，构造出面向不同浏览者的等级源E。

3.1 VSM

文本的特征表示是文本分类面临的首要问题。向量空间模型VSM[3](Vector Space Mode1)是目前应用最多且效果较好的文本表示法之一。VSM引入了线性代数中的某些概念，主要思想是选出若干独立的词项作特征项，每一篇文档都被映射成多维向量空间中的一个向量，对于所有的文档类和未知文档，都可用此空间中的向量Dj (w1,j, w2,j,…, wt,j)来表示。其中，t是系统中所有特征项的个数。wi,j为特征项ki在文档dj中对应的权值，用以刻画该特征项在描述此文档内容时的重要程度，使用公式进行计算：

wij=tfij×idfj=tfi×(log2(N/nj)+1)(3)

其中，tfij表示特征项ki在文档Dj中出现的频率，N代表文档集合中的文档数量，nj代表在文档集合中出现特征项ki的文档数目。

从而将文档信息的表示和匹配问题转化为向量空间中向量的表示和匹配问题来处理。那么，就可以使用向量空间模型来计算文档之间的主题相关程度。这种关系可以定量表示，一般用这两个文档生成的空间向量之间的夹角余弦值来计算。即

■(4)

3.2 特征项的选择

构成网页中的文本的词汇，数量是相当大的，因此，表示网页的向量空间的维数也相当大，可以达到几万维，所有几万个词汇对网页分类的意义是不同的，因此我们需要进行维数压缩的工作，也就是进行特征项的选取。特征选择的基本思想通常是构造一个评价函数，对特征集的每个特征进行评估。这样每个特征都获得一个评估分，然后对所有的特征按照其评估分的大小进行排序，选取预定数目的最佳特征作为结果的特征子集。

互信息量法[4]（mutual information）是一种常用的评价函数，MI用于度量一个消息中两个信号之间的相互依赖程度。在特征选择领域中，特征t和类别C的互信息体现了特征与类别的相关程度。在某个类别C中出现的概率高，而在其它类别中出现的概率低的特征t将获得较高的互信息。MI可表示为：

■ (5)

其中P(w|Ci)是训练语料征项W出现在类别Ci中的频率，P(w)是训练语料征项W 出现的频率。经过比较之后,选择互信息量大与设定阈值的特征项作为该类的类别特征。

3.3 迭代计算PageRank值

为了方便计算网页集合中所有页面的PageRank值，通常采用线性代数的理论，利用公式(2)来计算。把页面的PageRank值表示为向量R，用户的兴趣矩阵表示为E，其中Eij=sim（di，Cj）。那么可以得到，

R=cAR+(1-c)E(6)

其中，假设有n个网页，A是一个n×n的矩阵，其元素aij为鼠标点击一次时从i页到j页的概率。最简单的模型是取aij=|Oi|，这说明这意味着无论从哪个网页开始，它通过任一外链接到达其他网页的概率几乎是相同的。

进一步分析公式(5)，发现矩阵A某些行的元素可能都是零，所以矩阵A不一定是随机矩阵。这种情况会在网页没有外链接(即aij=0)的情况下发生。许多这样的网页是存在的并被称作悬挂页面。一种简单的解决办法是用eT/n[4]来替代这些零向量，其中eT是元素都为1的行向量。被修正的矩阵A’(现为随机的)可以看作是矩阵A的秩1修正矩阵。令a为悬挂向量，其元素为

■ (7)

那么， A’=A+aeT/n(8)

把修正后的A’带入公式(5)，得到

R=c(A+aeT/n)R+(1-c)E(9)

由于修正后的A’是随机且不可约的，因此可以保证向量R可以收敛到一个稳定的值，并且该向量与初始值的取值无关。于是可以假设S为初始网页向量，每个分量的值都赋予1/n，然后根据公式（9）反复迭代计算，直到最后得到的PageRank值收敛于一个相对固定的值，Brin 和Page 的报告中成功迭代的收敛速度是50到100步[2]。

4 实验结果与分析

文中的训练集来自中文自然语言处理开放平台上用于文本分类的语料库，该语料库来自复旦大学计算机信息与技术系国际数据库中心自然语言处理小组。从中选取了计算机、环境和体育3个类别，其中计算机方面的文档有1357篇，环境方面的文档有1217篇，体育方面的有1253个。测试数据来源于使用网络爬虫框架Heritrix抓取得到的5000个页面。为了验证上述改进算法，本文对随机的关键词进行20次查询，在返回的前100个结果中，统计符合查询的网页篇数，实验的结果如图1所示。

从图1可以看到本次实验使用主题PageRank算法排序的查询精度在45%左右，要好于传统的PageRank算法。

5 总结

本文将VSM文本分析模型引入PageRank算法，构造出基于主题的PageRank算法。并通过实验证明该算法对页面主题分析的能力有了改善，因此查询精度方面也得到了相应的提高。但是在具体使用的时候，该算法的实现还需要进一步完善。在今后的工作中，将就以下两方面问题做出进一步研究：

1) 通过引入一些用户兴趣的动态因素（例如用户访问日志），来构造属于每个用户的兴趣集，来计算符合每个用户要求的网页排名。

2) 考虑对迭代算法的优化，确保大量主题搜索的效率。

参考文献：

[1] Page L,Brin S.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks,1998,30(1-7):107-117.

[2] Page L,Brin S,Motwani R,et al.The PageRank Citation Ranking:Bringing order to the Web[R].Technical report,Computer Science Department,Stanford University,1998.

[3] Ricardo B Y,Berthier R N.Moderninformation retrieval[M].北京:机械工业出版社,2005.

[4] Yang Y,Pederson J O.A comparative study on feature selection in text categorization[C].International Conference on Machine Learning (ICML),1997.

[5] Langville A N,Meyer C D.A survey of eigenvector methods of web information retrieval[J].The SIAM Review,2005,47(1).

张冉（1981-），女，新疆乌鲁木齐人，讲师，硕士研究生，研究方向：网络信息检索。