一種基于空間向量模型的主題ＰａｇｅＲａｎｋ算法

摘要：該文基于傳統的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-），女，新疆烏魯木齊人，講師，碩士研究生，研究方向：網絡信息檢索。