摘要：該文基于傳統(tǒng)的PageRank鏈接分析原理，分析了PageRank在頁(yè)面主題內(nèi)容分析方面的不足之處，結(jié)合傳統(tǒng)的基于內(nèi)容的VSM文本分析模型，提出了一種基于向量空間模型的主題算法，并通過(guò)實(shí)驗(yàn)對(duì)改算法的性能進(jìn)行分析。

關(guān)鍵詞：PageRank；VSM；網(wǎng)頁(yè)排序；搜索引擎

中圖分類(lèi)號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 前言

目前在搜索引擎中常用的頁(yè)面排序方法是PageRank[1]方法，利用web頁(yè)面間的超鏈結(jié)構(gòu)來(lái)計(jì)算每個(gè)頁(yè)面的權(quán)重。但是PageRank算法會(huì)忽略某些頁(yè)面的內(nèi)容，一些與用戶興趣無(wú)關(guān)的知名網(wǎng)站也會(huì)被賦予過(guò)高的權(quán)重。致使用戶很難從中快速篩選出真正需要的信息。如果搜索引擎只返回相關(guān)度高的重要網(wǎng)頁(yè)，這樣既可以很大程度地節(jié)省用戶時(shí)間，又可以減輕網(wǎng)絡(luò)流量。

文中提出了一種基于向量空間模型的主題PageRank頁(yè)面排序算法，結(jié)合基于內(nèi)容和基于鏈接分析權(quán)重各自的特點(diǎn)，構(gòu)造出主題PageRank算法。

2 PageRank

2.1 PageRank理論模型

PageRank的基本思想來(lái)自傳統(tǒng)文獻(xiàn)計(jì)量學(xué)中的文獻(xiàn)引文分析，即如果一個(gè)頁(yè)面被多次引用，那么這個(gè)頁(yè)面很可能是重要的；如果一個(gè)頁(yè)面盡管沒(méi)有被多次引用，但是卻被一個(gè)重要的頁(yè)面引用，那么這個(gè)頁(yè)面很可能是重要的；一個(gè)頁(yè)面的重要性被均分并傳遞到它所引用的頁(yè)面。基于這種思想：設(shè)u是一個(gè)web頁(yè)面，F(xiàn)u是u引用的頁(yè)面集合，Bu是引用u的頁(yè)面集合，則網(wǎng)頁(yè)u的重要性R（u）可定義為：

■(1)

其中，Nu表示u引用的頁(yè)面?zhèn)€數(shù)，c為規(guī)范化因子。

2.2 修正的PageRank算法

公式(1)有一個(gè)假設(shè)前提：所有的頁(yè)面鏈接形成一個(gè)強(qiáng)連通圖。但是實(shí)際的網(wǎng)絡(luò)超鏈接環(huán)境沒(méi)有這么理想，會(huì)存在一些沒(méi)有外出鏈接的獨(dú)立頁(yè)面或頁(yè)面集合，這種頁(yè)面稱(chēng)之為懸掛頁(yè)面（dingle page）。因?yàn)檫@種頁(yè)面沒(méi)有外出鏈接，所以在迭代計(jì)算的時(shí)候頁(yè)面的重要性時(shí)，它不會(huì)傳出任何重要性，這將導(dǎo)致一個(gè)稱(chēng)之為等級(jí)泄露（rank sink）的重要問(wèn)題。為了解決這個(gè)問(wèn)題，必須引入一個(gè)等級(jí)源[2]（rank source）來(lái)補(bǔ)充每個(gè)頁(yè)面的PageRank值，以使得PageRank值不完全依賴(lài)于網(wǎng)絡(luò)鏈接。因?yàn)闉g覽者在網(wǎng)絡(luò)上瀏覽網(wǎng)頁(yè)的過(guò)程實(shí)際是一個(gè)隨機(jī)的過(guò)程，瀏覽者很少會(huì)沿著一個(gè)鏈接向下一直走到底。在每一個(gè)頁(yè)面，瀏覽者都有可能不再對(duì)本頁(yè)面的鏈接感興趣，從而隨機(jī)選擇一個(gè)新的頁(yè)面開(kāi)始新的瀏覽。所以修正后的PageRank定義為：

■ (2)

公式（2）中的等級(jí)源E一開(kāi)始是為了修正頁(yè)面間的等級(jí)泄露而設(shè)計(jì)的，后來(lái)Page和Brin又提出了E在調(diào)整頁(yè)面的排列順序方面的作用。它認(rèn)為瀏覽者每一次在隨機(jī)選擇一個(gè)新的頁(yè)面并開(kāi)始新的瀏覽時(shí)，都會(huì)與個(gè)人的興趣有關(guān)。于是可以根據(jù)不同瀏覽者的喜好，構(gòu)造不同的等級(jí)源E，從而提出了PageRank在主題個(gè)性化方面的應(yīng)用前景。

3 利用空間向量模型構(gòu)造個(gè)性化的PageRank算法

從上面的分析，我們可以看到主題PageRank的關(guān)鍵就是等級(jí)源的構(gòu)造。通過(guò)對(duì)每一個(gè)頁(yè)面進(jìn)行基于主題的分類(lèi)，然后針對(duì)每一個(gè)主題分別計(jì)算出對(duì)應(yīng)主題的主題性頁(yè)面等級(jí)得分，構(gòu)造出面向不同瀏覽者的等級(jí)源E。

3.1 VSM

文本的特征表示是文本分類(lèi)面臨的首要問(wèn)題。向量空間模型VSM[3](Vector Space Mode1)是目前應(yīng)用最多且效果較好的文本表示法之一。VSM引入了線性代數(shù)中的某些概念，主要思想是選出若干獨(dú)立的詞項(xiàng)作特征項(xiàng)，每一篇文檔都被映射成多維向量空間中的一個(gè)向量，對(duì)于所有的文檔類(lèi)和未知文檔，都可用此空間中的向量Dj (w1，j， w2，j，…， wt，j)來(lái)表示。其中，t是系統(tǒng)中所有特征項(xiàng)的個(gè)數(shù)。wi，j為特征項(xiàng)ki在文檔dj中對(duì)應(yīng)的權(quán)值，用以刻畫(huà)該特征項(xiàng)在描述此文檔內(nèi)容時(shí)的重要程度，使用公式進(jìn)行計(jì)算：

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

其中，tfij表示特征項(xiàng)ki在文檔Dj中出現(xiàn)的頻率，N代表文檔集合中的文檔數(shù)量，nj代表在文檔集合中出現(xiàn)特征項(xiàng)ki的文檔數(shù)目。

從而將文檔信息的表示和匹配問(wèn)題轉(zhuǎn)化為向量空間中向量的表示和匹配問(wèn)題來(lái)處理。那么，就可以使用向量空間模型來(lái)計(jì)算文檔之間的主題相關(guān)程度。這種關(guān)系可以定量表示，一般用這兩個(gè)文檔生成的空間向量之間的夾角余弦值來(lái)計(jì)算。即

■(4)

3.2 特征項(xiàng)的選擇

構(gòu)成網(wǎng)頁(yè)中的文本的詞匯，數(shù)量是相當(dāng)大的，因此，表示網(wǎng)頁(yè)的向量空間的維數(shù)也相當(dāng)大，可以達(dá)到幾萬(wàn)維，所有幾萬(wàn)個(gè)詞匯對(duì)網(wǎng)頁(yè)分類(lèi)的意義是不同的，因此我們需要進(jìn)行維數(shù)壓縮的工作，也就是進(jìn)行特征項(xiàng)的選取。特征選擇的基本思想通常是構(gòu)造一個(gè)評(píng)價(jià)函數(shù)，對(duì)特征集的每個(gè)特征進(jìn)行評(píng)估。這樣每個(gè)特征都獲得一個(gè)評(píng)估分，然后對(duì)所有的特征按照其評(píng)估分的大小進(jìn)行排序，選取預(yù)定數(shù)目的最佳特征作為結(jié)果的特征子集。

互信息量法[4]（mutual information）是一種常用的評(píng)價(jià)函數(shù)，MI用于度量一個(gè)消息中兩個(gè)信號(hào)之間的相互依賴(lài)程度。在特征選擇領(lǐng)域中，特征t和類(lèi)別C的互信息體現(xiàn)了特征與類(lèi)別的相關(guān)程度。在某個(gè)類(lèi)別C中出現(xiàn)的概率高，而在其它類(lèi)別中出現(xiàn)的概率低的特征t將獲得較高的互信息。MI可表示為：

■ (5)

其中P(w|Ci)是訓(xùn)練語(yǔ)料中特征項(xiàng)W出現(xiàn)在類(lèi)別Ci中的頻率，P(w)是訓(xùn)練語(yǔ)料中特征項(xiàng)W 出現(xiàn)的頻率。經(jīng)過(guò)比較之后，選擇互信息量大與設(shè)定閾值的特征項(xiàng)作為該類(lèi)的類(lèi)別特征。

3.3 迭代計(jì)算PageRank值

為了方便計(jì)算網(wǎng)頁(yè)集合中所有頁(yè)面的PageRank值，通常采用線性代數(shù)的理論，利用公式(2)來(lái)計(jì)算。把頁(yè)面的PageRank值表示為向量R，用戶的興趣矩陣表示為E，其中Eij=sim（di，Cj）。那么可以得到，

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

其中，假設(shè)有n個(gè)網(wǎng)頁(yè)，A是一個(gè)n×n的矩陣，其元素aij為鼠標(biāo)點(diǎn)擊一次時(shí)從i頁(yè)到j(luò)頁(yè)的概率。最簡(jiǎn)單的模型是取aij=|Oi|，這說(shuō)明這意味著無(wú)論從哪個(gè)網(wǎng)頁(yè)開(kāi)始，它通過(guò)任一外鏈接到達(dá)其他網(wǎng)頁(yè)的概率幾乎是相同的。

進(jìn)一步分析公式(5)，發(fā)現(xiàn)矩陣A某些行的元素可能都是零，所以矩陣A不一定是隨機(jī)矩陣。這種情況會(huì)在網(wǎng)頁(yè)沒(méi)有外鏈接(即aij=0)的情況下發(fā)生。許多這樣的網(wǎng)頁(yè)是存在的并被稱(chēng)作懸掛頁(yè)面。一種簡(jiǎn)單的解決辦法是用eT/n[4]來(lái)替代這些零向量，其中eT是元素都為1的行向量。被修正的矩陣A’(現(xiàn)為隨機(jī)的)可以看作是矩陣A的秩1修正矩陣。令a為懸掛向量，其元素為

■ (7)

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

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

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

由于修正后的A’是隨機(jī)且不可約的，因此可以保證向量R可以收斂到一個(gè)穩(wěn)定的值，并且該向量與初始值的取值無(wú)關(guān)。于是可以假設(shè)S為初始網(wǎng)頁(yè)向量，每個(gè)分量的值都賦予1/n，然后根據(jù)公式（9）反復(fù)迭代計(jì)算，直到最后得到的PageRank值收斂于一個(gè)相對(duì)固定的值，Brin 和Page 的報(bào)告中成功迭代的收斂速度是50到100步[2]。

4 實(shí)驗(yàn)結(jié)果與分析

文中的訓(xùn)練集來(lái)自中文自然語(yǔ)言處理開(kāi)放平臺(tái)上用于文本分類(lèi)的語(yǔ)料庫(kù)，該語(yǔ)料庫(kù)來(lái)自復(fù)旦大學(xué)計(jì)算機(jī)信息與技術(shù)系國(guó)際數(shù)據(jù)庫(kù)中心自然語(yǔ)言處理小組。從中選取了計(jì)算機(jī)、環(huán)境和體育3個(gè)類(lèi)別，其中計(jì)算機(jī)方面的文檔有1357篇，環(huán)境方面的文檔有1217篇，體育方面的有1253個(gè)。測(cè)試數(shù)據(jù)來(lái)源于使用網(wǎng)絡(luò)爬蟲(chóng)框架Heritrix抓取得到的5000個(gè)頁(yè)面。為了驗(yàn)證上述改進(jìn)算法，本文對(duì)隨機(jī)的關(guān)鍵詞進(jìn)行20次查詢，在返回的前100個(gè)結(jié)果中，統(tǒng)計(jì)符合查詢的網(wǎng)頁(yè)篇數(shù)，實(shí)驗(yàn)的結(jié)果如圖1所示。

從圖1可以看到本次實(shí)驗(yàn)使用主題PageRank算法排序的查詢精度在45%左右，要好于傳統(tǒng)的PageRank算法。

5 總結(jié)

本文將VSM文本分析模型引入PageRank算法，構(gòu)造出基于主題的PageRank算法。并通過(guò)實(shí)驗(yàn)證明該算法對(duì)頁(yè)面主題分析的能力有了改善，因此查詢精度方面也得到了相應(yīng)的提高。但是在具體使用的時(shí)候，該算法的實(shí)現(xiàn)還需要進(jìn)一步完善。在今后的工作中，將就以下兩方面問(wèn)題做出進(jìn)一步研究：

1) 通過(guò)引入一些用戶興趣的動(dòng)態(tài)因素（例如用戶訪問(wèn)日志），來(lái)構(gòu)造屬于每個(gè)用戶的興趣集，來(lái)計(jì)算符合每個(gè)用戶要求的網(wǎng)頁(yè)排名。

2) 考慮對(duì)迭代算法的優(yōu)化，確保大量主題搜索的效率。

參考文獻(xiàn)：

[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].北京:機(jī)械工業(yè)出版社，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-），女，新疆烏魯木齊人，講師，碩士研究生，研究方向：網(wǎng)絡(luò)信息檢索。