基于時間感知的頁面排序算法的改進

，， ，，，

互聯網網頁的信息大多都具有時效性，而搜索引擎在處理具有時間屬性的查詢還存在一定的問題[1-3]。比如，2016年10月，在百度中輸入“十大電影排名”時，首先出現的是近期上映的電影，然后才出現近年的“十大電影排名”搜索結果，前幾條記錄均是2015年、2014年發布的消息，2016年發布的消息則排到第6條記錄。搜索引擎并不能對用戶查詢信息時間敏感性的要求對信息進行加工與處理[4]，顯然結果不能讓用戶滿意。于是利用時間感知對信息搜索結果進行排序的研究顯得很有必要。

1 國內外時間感知頁面排序算法的研究

有關時間感知的查詢，目前已有部分學者進行了相關研究。ShengLin[5]等人提出了一個關于時間感知的頁面排序算法，用一個四元的方式來表示文檔的時間，通過頁面時間與查詢時間之間的比較，獲得兩時間之間的相似度，從而獲得基于時間感知的頁面排序算法。他們運用了6 455 985組數據進行實驗，其中含有顯式時間的數據有3 763 923組(占58%)，隱式時間的數據有2 692 062組(占42%)，實驗結果顯示，查詢的精確度較沒有運用此算法之前至多提高了15.13%。在國內，在張乃洲等人[6]也研發出了一種基于時間感知的搜索引擎模型[3]。該模型主要分為頁面時間屬性抽取器、時間感知查詢處理模塊、基于時間感知的頁面排序模塊三大部分，其中運用到時間粒度來對頁面與查詢間的時間相關度進行計算，最后通過時間感知度因子權衡得出結果頁面的排序算法。在頁面時間屬性抽取部分，對于含顯式時間的頁面其抽取精度可達0.93，然而對于隱式時間的頁面抽取精度僅為0.76。查詢結果顯示，除了個別查詢外，大部分查詢的精度值都可得到不同程度的提升，提升幅度與Google原始查詢的精度值有關。例如某一查詢類型為月的查詢從初始的精度值約0.4提高到約0.8，而另一查詢類型為日的查詢(如汽油價格)初始值已達1.0，改進后仍然為1.0。此外，該實驗加入了查詢結果序關系對排序結果影響的AP指標，即排序算法對排序結果的作用。

隨著互聯網信息的不斷更新，用戶對信息時效性的追求越來越高。在頁面的排序算法中融入時間屬性可讓用戶獲得更加滿意的結果，同時使搜索引擎更加精確、更加智能化，提高用戶對搜索引擎的使用率。本文針對目前頁面排序算法存在的不足，融入時間屬性及個性化服務對排序算法進行改進。

2 改進的時間感知算法

2.1 基本思路

在獲得了查詢的時間信息后，對頁面進行融合了時間屬性的查詢時，本文將采用公式(1)來對查詢結果進行排序：

ST(D,Q)=(1-ω)*S(D,Q)+ω*Stemporal(D,Q) (1)

其中，D代表文檔，Q代表用戶的查詢，Stemporal(D,Q)代表查詢時間和頁面內容時間之間的相關性強度，用公式進行表示：Stemporal(D,Q)，其中Sk是常數，需根據查詢詞條所涉及的時間粒度來決定；Tq代表當前查詢詞條所包含的時間；Td則代表數據庫所含頁面的內容所表達的時間。S(D，Q)是由排序算法獲得的D和Q之間的相關程度，為了使它的取值介于0和1之間需對兩者的相關度進行標準化處理。張乃洲等學者[3]在此處運用PageRank算法得出S(D,Q)，但是PageRank算法存在同類網頁間連接較少和對用戶沒有區分(無法感知不同的網頁對不同用戶的重要性的不同)等不足。

本次基于時間感知排序算法的改進從此處著手，運用改進后的PageRank算法得出S(Q,Q)。對原始的PageRank算法加入用戶投票計算“P_VRank”，加入用戶模型向量計算“P_URank”值，使改進后基于時間感知的頁面排序算法實現個性化服務，更好地滿足用戶的需求。ω是一個用來表示時間感知度的大小的因子，它的取值與用戶鍵入的查詢有關——如果用戶鍵入的查詢具有對時間的要求，則ω的取值較大，如果用戶鍵入的查詢對時間要求較低，則 的取值較少。

本次改進算法的基本思想是在原有算法的基礎上，通過加入“用戶投票計算”(P_VRank)和“用戶模型向量計算”(P_URank)，為用戶實現查詢的個性化服務，使查詢結果的排序更加地貼切不同用戶的需要，提高用戶對搜索引擎的滿意程度。本改進算法的主要工作原理是通過一個時間感知度因子ω來控制查詢與頁面之間相關度S(D,Q )和查詢與頁面內容之間的時間相關度S(Q,D )兩者間的比重。對于基于時間感知的查詢，Stemporal(D,Q)的值較大，ω所占到的比重較大；對于基于非時間感知的查詢而言，ω則取值較小，S(D,Q )占到的比重較Stemporal(D,Q)大。

2.2 改進方法

關于基于時間感知頁面排序算法的改進針對部分的獲取主要分為2個步驟：一是參照PageRank算法的原有思想，形成一個投票分值加入到影響Rank值得計算當中去，得到被修改后的Rank值即P_VRank值；二是將網頁的頁面質量與用戶興趣模型數據相互結合獲得P_URank值。

2.2.1 獲得P_VRank值

超鏈接是PageRank算法的核心，通過網頁之間的鏈接，獲得質量較高的網頁來反饋給用戶。這僅僅是從商家的角度進行鏈接分析，不僅不利于同類網頁之間的公平競爭，而且沒有顧及到用戶的反饋，缺乏全面性。因此引入字段Vote來表示用戶對網頁的投票，把用戶對網頁的反饋添加到網頁的質量評估當中去。用戶對該網頁表示滿意好評的，該網頁的Vote值對應地加1；用戶對該網頁不滿意表示差評的，則該網頁的Vote值相應地扣掉1。一個月結束時對各網頁的Vote值進行統計，最后與原有的PageRank算法融合獲得P_VRank值。這一步的數據計算量較大，計算結果表現的是從商家和用戶兩個方面反映出來的頁面質量，得出的頁面質量評估結果更為精準。具體的過程如下：

一是通過PageRank算法獲得網頁的質量排名(PageRank)，計算公式如下：

PRi=(1-d)/N+d(PR(T1)/C(T1)+PR(Tn)/C(Tn)) (2)

二是獲得網頁的投票排名(VoteRank)，計算過程分為兩步：

首先，計算出某一網頁(i)的Vote值(得票數)在全體的Vote值總和當中所占的比例，用WRi表示，見公式(3)。

然后，比較前一步得出的VRi的獲得最大值VRmax，利用步驟(1)中獲得的PR值對VR值得權重進行評估，從而VR擁有與PR相同的比重，見公式(4)。

三是融合PR值和VR值，形成獲得一個新的Rank值，用P_VRank表示，計算公式如下：

P-VRank=z·VR+PR(5)

i為阻尼系數，目的是將用戶投票對排序結果產生的影響控制在一定的范圍之內，以避免PR和VR出現某一方面決定排序結果的情況。暫且對i取值為0.6，這一數值還需通過后續的大量實驗進行考證。

通過上述三大步驟獲得的結合用戶和商家兩者反饋的頁面質量排序結果較單獨的PageRank算法獲得的排序結果更為科學精確，但這個結果對于每一個用戶來說都是一樣的，沒有體現出個性化服務。

2.2.2 獲得P_URank值

在獲得P_URank值的這一步驟的計算中，雖然是計算量較小的計算，但是在用戶發出請求后進行，需犧牲程序的運行效率來進行處理。通過使不同用戶間即使在查詢欄鍵入相同的查詢詞，不同的用戶間所得到的查詢結果也是不一樣的，使用戶在前幾頁就能獲得滿意的結果。

此處需要運用到“用戶興趣向量”，此向量經過一段時間的獲取、統計、計算后可以挖掘、反映出某一用戶的興趣所指。通過這一向量，系統獲得了某一用戶對某一類別頁面的興趣程度，再把頁面的內容與用戶的興趣向量進行相似度比較(相似程度較高且頁面質量較高的網頁的P_URank值較高，相似程度低且頁面質量較低的網頁的P_URank值較低)，最后根據P_URank值對結果頁面進行排序，獲得的排序結果中，用戶感興趣的、最需要的頁面排名在前，給用戶提供的個性化的結果排序。初步獲得的計算過程(見公式6)如下：

IFnQ==niη=1ELSEη=0

上述公式中，ηi和ηq分別表示頁面 和用戶興趣分類 的分類號。如果兩者相等，表明該頁面符合用戶的興趣類型，則用公式(6)計算。tq表示該用戶對于某一類別頁面的認可程度大小，用數值表示，用戶對頁面表示認可則 值加1，反之則減1；N是頁面分類的總和。計算時，先獲得用戶對某一類頁面的感興趣程度，再與P_VRank進行乘積運算，最終得出關于這個頁面的一個可以體現用戶個性化需求的P_URank值。

然而，因為上述算法中帶有IF語句，在算法的編寫過程中，若先出現IF、ELSE、SWITCH等語句，將會大大地降低算法的運行效率。為了減少這些語句的出現，需對上述計算過程進行優化，優化后的計算過程如下：

為了避免在后續計算中頻繁重復地計算該用戶對所有類別認可程度之和，先對該值進行統一的運算并記為A。用nq與ni之間的同或來代替IF語句的使用，提高了算法的運行效率。通過優化后的計算，大大地提高了每個頁面對應的P_URank值的獲取效率，最后根據獲得的每個頁面的P_URank值進行頁面排序使排序結果更加符合用戶的需求。

3 實驗分析

3.1 實驗方案

整個實驗系統主要分為兩大模塊，第一大模塊是根據用戶的查詢詞對數據文檔提取形成候選文檔數據庫，第二大模塊則是按照不同的算法對候選文檔數據庫當中的文檔進行重新排序并把結果反饋給用戶。具體實驗系統框架如圖1所示。

圖1 實驗系統整體框架

如實驗系統整體框架圖所示，用戶鍵入查詢詞后，系統將從服務器資料庫中檢索與查詢詞相匹配的文檔，并將該文檔存入到候選文檔數據庫中，然后根據不同排序算法的不同排序規則對候選文檔數據庫當中的文檔進行重新排序的工作，最終把重新排序后的文檔排序結果反饋給用戶。

3.2 實驗結果

下面分析針對“麥當勞”這一查詢詞3種算法的搜索結果中排名前40%的文檔，從文檔內容時間、文檔類型、文檔質量等3個方面對3種排序算法進行綜合評價。

圖2 文檔時間分布比例

如圖2所示，PageRank算法獲得的文檔內容時間集中分布在最近的兩個月，然而也有10%的文檔內容時間為2015年4月。其中時間為2015年5月的文檔數最多；基于時間感知的排序算法獲得的文檔內容時間分布中，時間為2015年6月出現的比例為50%，是3種算法中比例最高的，剩余的50%也分布在較近的時間2015年5月，時間距今較近。改進后的算法獲得的文檔時間分布范圍較廣，整體數據呈負偏態分布，文檔整體的平均時間較前兩種算法低，但文檔出現的高峰在2015年5月，眾數值較前兩者變化不大。總的來說，在文檔時間分布方面，基于時間感知的排序算法表現較好，改進后的算法表現也不差，雖然分布范圍較廣，但文檔的時間分布仍集中在較新的時間。

圖3 符合用戶興趣類型的文檔比例

如圖3所示，由PageRank算法獲得的結果文檔的前40%的文檔中，符合用戶興趣類型的文檔所占比例達到50%，單獨來看，該值處于中等水平；基于時間感知的排序算法獲得的前40%結果中，符合用戶興趣類型的文檔達60%，較前一算法有10%的提高，差距不大。改進后的算法給出的前40%文檔中，符合用戶興趣類型的文檔高達90%，與PageRank算法的結果相差40%，與基于時間感知的排序算法的結果相差30%，改進后的算法在用戶興趣類型匹配上有了很大的提高。在文檔類型與用戶興趣類型匹配，改進后的算法表現最好，與其他兩種算法都拉開了較大的差距。

圖4 頁面質量均值圖

由圖4可以看出，在獲得的前40%結果文檔中，3種算法得出的文檔的頁面質量均值整體水平較高，三者之間相差不大。其中由基于時間感知的排序算法獲得頁面質量均值稍低為844；PageRank算法獲得的均值較基于時間感知的排序算法獲得的均值高出1.8，兩者之間沒有太大差距；改進后的算法獲得的頁面質量均值是849.9，比PageRank算法高出了4.1，與基于時間感知的排序算法相比高出了5.9，相比之下有較大的提高。在頁面質量這一方面，改進后的算法表現較好，與其他兩個算法之間的差距相對較大。

通過以上3個方面對3種算法結果的分析，可以看出，改進后的算法在文檔內容時間與前兩者相差不大的情況下，在文檔類型與用戶興趣類型匹配、文檔頁面質量這兩方面都有較大的提升。

4 結語

通過對頁面排序算法的改進，使頁面排序算法在時效性和個性化服務方面有了一定的提高，但仍然存在不足。如改進算法中只是把查詢時間和頁面的內容時間的相關度進行比對研究，未考慮頁面的更新時間。為了進一步加強算法，全方位地提高搜索引擎的性能，應將重點放在以下方面：如何把頁面的更新時間和內容時間結合在一起為查詢結果排序提供參考，就算法的運行效率方面進行反復的思考優化，以縮短算法的響應時間，提高搜索引擎的查詢效率。