改進PageRank算法的網(wǎng)頁權(quán)重分析

黃 艷，李朝榮

（宜賓學院人工智能與大數(shù)據(jù)學部，四川宜賓 644000）

使用網(wǎng)頁搜索引擎時，系統(tǒng)需要根據(jù)網(wǎng)頁的重要性將搜索的網(wǎng)頁推薦給用戶，以提高系統(tǒng)人性化和智能化水平. 網(wǎng)頁中的鏈接（包括數(shù)量和質(zhì)量）和主題內(nèi)容是網(wǎng)頁排序的兩個關(guān)鍵依據(jù)[1]. 網(wǎng)頁中的鏈接較多，其鏈接指向的其他網(wǎng)頁質(zhì)量較高，則該網(wǎng)頁通常是較重要的網(wǎng)頁；網(wǎng)頁主題內(nèi)容如果是熱點，或者與用戶的關(guān)鍵詞更相關(guān)，也會讓該網(wǎng)頁排序更靠前[2].常見的網(wǎng)頁排序有以下幾種：

（1）基于關(guān)鍵詞統(tǒng)計的排序[3]

利用關(guān)鍵詞在網(wǎng)頁中出現(xiàn)的頻率和重要性排序是搜索引擎最早期排序的主要思想，其技術(shù)發(fā)展也最為成熟，是第一代搜索引擎使用的主要技術(shù)，至今仍是主流搜索引擎必備的排序技術(shù). 其實現(xiàn)的基本依據(jù)是，關(guān)鍵詞在網(wǎng)頁中詞頻越高、越重要，則被認為與用戶檢索的詞的匹配程度越好.

（2）基于鏈接分析的排序[4]

根據(jù)鏈接分析進行網(wǎng)頁排序的主要思想是：如果某網(wǎng)頁被別的網(wǎng)頁引用的次數(shù)越多，并且這些引用的網(wǎng)頁越權(quán)威，則該網(wǎng)頁的價值就越大. 被別的網(wǎng)頁引用次數(shù)越多，說明該網(wǎng)頁受到的關(guān)注程度比較高；被越權(quán)威的網(wǎng)頁引用，說明該網(wǎng)頁質(zhì)量越高.基于鏈接分析排序算法可以歸結(jié)為兩大類：基于隨機漫游模型的算法，最典型的就是PageRank[5]；基于概率模型的算法，常見的模型有SALSA和HITS[6].

（3）綜合主題內(nèi)容的排序

綜合主題內(nèi)容的排序也稱為智能化排序，屬于第三代搜索引擎涉及的范疇. 該類方法除了考慮上述兩種傳統(tǒng)的排序技術(shù)外，還要重點考慮網(wǎng)頁內(nèi)容和用戶搜索內(nèi)容的相關(guān)性來排序網(wǎng)頁. 由于語言文本的復雜性和模糊性，僅僅通過鏈接分析及網(wǎng)頁的表面特征來判斷檢索詞與網(wǎng)頁的相關(guān)性是片面的，因而需要利用機器學習、人工智能等相關(guān)技術(shù)分析網(wǎng)頁內(nèi)容. 目前流行的技術(shù)包括基于向量空間模型的SVM 模型[7]，以及基于深度網(wǎng)絡(luò)的BERT[8]、Transformer[9]等文本分析模型.

1 PageRank 算法分析及其改進

1.1 PageRank算法

PageRank 是Google 用于標識網(wǎng)頁等級（也稱為重要性）的一種方法，是用來衡量一個站點好壞的一種標準. 在揉合了諸如網(wǎng)頁標題和關(guān)鍵字等標識后，通過PageRank 調(diào)整結(jié)果，使那些更具“等級/重要性”的網(wǎng)頁在搜索結(jié)果中令站點排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量. PageRank 利用網(wǎng)頁之間的鏈接關(guān)系，計算出代表網(wǎng)頁重要程度的值（PageRank 值，簡稱PR值）來排序網(wǎng)頁，PR值越高，說明該網(wǎng)頁越受歡迎（越重要）.

PageRank 算法基于兩個假設(shè)：①如果某網(wǎng)頁被很多網(wǎng)頁引用，則該網(wǎng)頁是一個重要網(wǎng)頁，稱為數(shù)量假設(shè)；②如果有高質(zhì)量的網(wǎng)頁（權(quán)威網(wǎng)頁）指向某網(wǎng)頁，則該網(wǎng)頁也是一個重要網(wǎng)頁，稱為質(zhì)量假設(shè).PageRank算法的核心公式如下：

其中：PR(pi)是網(wǎng)頁pi的PageRank 值，M(pi)是鏈入pi網(wǎng)頁的集合，L(pj)是網(wǎng)頁pj鏈出網(wǎng)頁的數(shù)量，N是集合中所有網(wǎng)頁的數(shù)量，d為阻尼因子，通常取0.85[9]. 集合中所有網(wǎng)頁的PR值可以用一個向量A來表示：

根據(jù)PageRank 公式（1），公式（2）可以寫成如下的矩陣形式迭代公式：

其中：At是在t步迭代時所有網(wǎng)頁的PR值.l(pi，pj)表示從網(wǎng)頁j指向網(wǎng)頁i的鏈接數(shù)與網(wǎng)頁j中含有的外部鏈接總數(shù)的比值；如果pi和pj之間沒有鏈接，則l(pi，pj)=0.

PageRank有如下的優(yōu)缺點：

優(yōu)點：PageRank 是一個與查詢無關(guān)的靜態(tài)算法，所有網(wǎng)頁的PR值通過離線計算獲得；能有效減少在線查詢時的計算量，極大降低了查詢響應(yīng)時間.

缺點：PageRank 只根據(jù)網(wǎng)頁的鏈接情況來分析重要性，忽略了主題相關(guān)性和環(huán)境等因素，導致排序的結(jié)果不是很合理. 例如一個新網(wǎng)頁，即使該網(wǎng)頁受到較多關(guān)注也不會有很多上游鏈接，其排序會較低，除非它是某個子站點.

1.2 改進的PageRank算法：EPageRank

通常衡量一個網(wǎng)頁的重要性還應(yīng)包括：

（1）網(wǎng)頁的點擊量：網(wǎng)頁的點擊量高，說明網(wǎng)頁越受關(guān)注，也越重要.

（2）時間因素：時間越久（越老）的網(wǎng)頁，其重要程度要降低.

為了克服PageRank 的缺陷，本文提出了改進的PageRank算法，稱為EPageRank，其PR值計算如下：

其中：hi表示點擊量因子，值越大點擊量越高，對PR值貢獻越多；ti表示時間因子，數(shù)值越大對PR值貢獻越小.

2 實驗與分析

阻尼系數(shù)d的含義是，在任意時刻，用戶到達某網(wǎng)頁后并繼續(xù)瀏覽該網(wǎng)頁的概率，同義，可以理解1-d是用戶到達某網(wǎng)頁后離開（跳轉(zhuǎn)到其他網(wǎng)頁）的概率. 為了說明d在算法中的作用，本文設(shè)計了4 個網(wǎng)頁的集合[A，B，C，D]，網(wǎng)頁之間的鏈接關(guān)系如圖1所示. 圖中的邊是有向箭頭，箭頭指向表示該網(wǎng)頁包含另外一個網(wǎng)頁的鏈接（從該網(wǎng)頁能夠跳轉(zhuǎn)到另外一個網(wǎng)頁）.例如A→D表示A包含指向網(wǎng)頁D的鏈接，A?C表示A包含C的鏈接，C也包含A的鏈接.

圖1 網(wǎng)頁及其之間的鏈接關(guān)系

將阻尼系數(shù)d設(shè)置變化從0.2 到0.95，分別計算四個網(wǎng)頁的PR值，結(jié)果見表1. 可以看出阻尼系數(shù)會影響PR值，但是對于排序并沒有多大影響，表1中四個網(wǎng)頁的排序均為2、3、1、4. 這說明PR值及其排序主要是網(wǎng)頁及其包含的鏈接所決定的，阻尼系數(shù)、網(wǎng)頁主題等因素對網(wǎng)頁的排序影響非常有限.

表1 不同阻尼系數(shù)下的網(wǎng)頁PR值及其排序

觀察EPageRank中阻尼系數(shù)d以及點擊量、時間因子等對PR值及其排序的影響，將點擊量和時間因子均設(shè)置為1～8 個值（根據(jù)情況可以設(shè)置為其它的值），設(shè)置情況見表2. 點擊量因子h由點擊量確定，例如0～10次點擊量，該網(wǎng)頁的點擊量因子h設(shè)置為1；11～50 次點擊量，h設(shè)置為2. 時間因子t則根據(jù)網(wǎng)頁存在的天數(shù)來確定，例如網(wǎng)頁存在0～1 天，該網(wǎng)頁的時間因子t設(shè)置為1；2～3天，t設(shè)置為2.

表2 點擊量和時間因子設(shè)置

表3和表4列出了EPageRank的評估結(jié)果.

表3 EPageRank排序結(jié)果（A(8，1)，B(3，6)，C(7，2)，D(5，5)）

表4 EPageRank排序結(jié)果（A(1，5)，B(1，7)，C(8，3)，D(8，6)）

表中的X(h，t)表示網(wǎng)頁X的點擊量因子為h、時間因子為t，如A(8，1)表示網(wǎng)頁A的點擊量因子為8，該網(wǎng)頁的點擊量比較高，時間因子為1，表示該網(wǎng)頁比較新. 由于EPageRank 采用了log10，PR值可能為負數(shù)，具體見表4. 從兩個表的結(jié)果可以看出，由于時間和點擊量因子加入，阻尼系數(shù)對PR值的影響力加大. 這說明時間和點擊量會影響該網(wǎng)頁，對用戶在該網(wǎng)頁繼續(xù)瀏覽和跳轉(zhuǎn)到其他網(wǎng)頁的影響力增大，更加符合實際情況. 在同樣的網(wǎng)頁及其鏈接關(guān)系下，網(wǎng)頁的點擊量和網(wǎng)頁存在時間，會明顯改變網(wǎng)頁排序結(jié)果. 同樣的阻尼系數(shù)0.5，當四個網(wǎng)頁的點擊量和時間因子分別是A(8，1)、B(3，6)、C(7，2)、D(5，5)，其排序情況是1、2、3、4；當四個網(wǎng)頁的點擊量和時間因子分別是A(1，5)、B(1，7)、C(8，3)、D(8，6)時，其排序情況是3、4、1、2. 結(jié)合表1、表3 和表4，可以看出網(wǎng)頁A在PageRank 下的排序為2，當考慮時間和點擊量因子為A(8，1)時（說明該網(wǎng)頁點擊量高，也比較新），其排名提升到第一位；當為A(1，5)時（說明該網(wǎng)頁點擊量低，存在時間也比較久）其排名降低到第三位.

3 總結(jié)

本文提出了PageRank 的改進版，在進行網(wǎng)頁排序時，除了考慮網(wǎng)頁鏈接關(guān)系外，還加入了點擊量和時間因子，以此彌補PageRank 的不足，更加切合實際應(yīng)用. 本文對點擊量和時間因子的設(shè)置可能不夠完善，還可以根據(jù)實際情況進行設(shè)置；EPageRank 的公式中采用了對數(shù)形式，該形式不唯一，可以考慮使用其他不同的形式.