基于時(shí)間感知的頁(yè)面排序算法的改進(jìn)

，， ，，，

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

1 國(guó)內(nèi)外時(shí)間感知頁(yè)面排序算法的研究

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

隨著互聯(lián)網(wǎng)信息的不斷更新，用戶對(duì)信息時(shí)效性的追求越來(lái)越高。在頁(yè)面的排序算法中融入時(shí)間屬性可讓用戶獲得更加滿意的結(jié)果，同時(shí)使搜索引擎更加精確、更加智能化，提高用戶對(duì)搜索引擎的使用率。本文針對(duì)目前頁(yè)面排序算法存在的不足，融入時(shí)間屬性及個(gè)性化服務(wù)對(duì)排序算法進(jìn)行改進(jìn)。

2 改進(jìn)的時(shí)間感知算法

2.1 基本思路

在獲得了查詢的時(shí)間信息后，對(duì)頁(yè)面進(jìn)行融合了時(shí)間屬性的查詢時(shí)，本文將采用公式(1)來(lái)對(duì)查詢結(jié)果進(jìn)行排序：

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

其中，D代表文檔，Q代表用戶的查詢，Stemporal(D,Q)代表查詢時(shí)間和頁(yè)面內(nèi)容時(shí)間之間的相關(guān)性強(qiáng)度，用公式進(jìn)行表示：Stemporal(D,Q)，其中Sk是常數(shù)，需根據(jù)查詢?cè)~條所涉及的時(shí)間粒度來(lái)決定；Tq代表當(dāng)前查詢?cè)~條所包含的時(shí)間；Td則代表數(shù)據(jù)庫(kù)所含頁(yè)面的內(nèi)容所表達(dá)的時(shí)間。S(D，Q)是由排序算法獲得的D和Q之間的相關(guān)程度，為了使它的取值介于0和1之間需對(duì)兩者的相關(guān)度進(jìn)行標(biāo)準(zhǔn)化處理。張乃洲等學(xué)者[3]在此處運(yùn)用PageRank算法得出S(D,Q)，但是PageRank算法存在同類網(wǎng)頁(yè)間連接較少和對(duì)用戶沒(méi)有區(qū)分(無(wú)法感知不同的網(wǎng)頁(yè)對(duì)不同用戶的重要性的不同)等不足。

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

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

2.2 改進(jìn)方法

關(guān)于基于時(shí)間感知頁(yè)面排序算法的改進(jìn)針對(duì)部分的獲取主要分為2個(gè)步驟：一是參照PageRank算法的原有思想，形成一個(gè)投票分值加入到影響Rank值得計(jì)算當(dāng)中去，得到被修改后的Rank值即P_VRank值；二是將網(wǎng)頁(yè)的頁(yè)面質(zhì)量與用戶興趣模型數(shù)據(jù)相互結(jié)合獲得P_URank值。

2.2.1 獲得P_VRank值

超鏈接是PageRank算法的核心，通過(guò)網(wǎng)頁(yè)之間的鏈接，獲得質(zhì)量較高的網(wǎng)頁(yè)來(lái)反饋給用戶。這僅僅是從商家的角度進(jìn)行鏈接分析，不僅不利于同類網(wǎng)頁(yè)之間的公平競(jìng)爭(zhēng)，而且沒(méi)有顧及到用戶的反饋，缺乏全面性。因此引入字段Vote來(lái)表示用戶對(duì)網(wǎng)頁(yè)的投票，把用戶對(duì)網(wǎng)頁(yè)的反饋添加到網(wǎng)頁(yè)的質(zhì)量評(píng)估當(dāng)中去。用戶對(duì)該網(wǎng)頁(yè)表示滿意好評(píng)的，該網(wǎng)頁(yè)的Vote值對(duì)應(yīng)地加1；用戶對(duì)該網(wǎng)頁(yè)不滿意表示差評(píng)的，則該網(wǎng)頁(yè)的Vote值相應(yīng)地扣掉1。一個(gè)月結(jié)束時(shí)對(duì)各網(wǎng)頁(yè)的Vote值進(jìn)行統(tǒng)計(jì)，最后與原有的PageRank算法融合獲得P_VRank值。這一步的數(shù)據(jù)計(jì)算量較大，計(jì)算結(jié)果表現(xiàn)的是從商家和用戶兩個(gè)方面反映出來(lái)的頁(yè)面質(zhì)量，得出的頁(yè)面質(zhì)量評(píng)估結(jié)果更為精準(zhǔn)。具體的過(guò)程如下：

一是通過(guò)PageRank算法獲得網(wǎng)頁(yè)的質(zhì)量排名(PageRank)，計(jì)算公式如下：

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

二是獲得網(wǎng)頁(yè)的投票排名(VoteRank)，計(jì)算過(guò)程分為兩步：

首先，計(jì)算出某一網(wǎng)頁(yè)(i)的Vote值(得票數(shù))在全體的Vote值總和當(dāng)中所占的比例，用WRi表示，見(jiàn)公式(3)。

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

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

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

i為阻尼系數(shù)，目的是將用戶投票對(duì)排序結(jié)果產(chǎn)生的影響控制在一定的范圍之內(nèi)，以避免PR和VR出現(xiàn)某一方面決定排序結(jié)果的情況。暫且對(duì)i取值為0.6，這一數(shù)值還需通過(guò)后續(xù)的大量實(shí)驗(yàn)進(jìn)行考證。

通過(guò)上述三大步驟獲得的結(jié)合用戶和商家兩者反饋的頁(yè)面質(zhì)量排序結(jié)果較單獨(dú)的PageRank算法獲得的排序結(jié)果更為科學(xué)精確，但這個(gè)結(jié)果對(duì)于每一個(gè)用戶來(lái)說(shuō)都是一樣的，沒(méi)有體現(xiàn)出個(gè)性化服務(wù)。

2.2.2 獲得P_URank值

在獲得P_URank值的這一步驟的計(jì)算中，雖然是計(jì)算量較小的計(jì)算，但是在用戶發(fā)出請(qǐng)求后進(jìn)行，需犧牲程序的運(yùn)行效率來(lái)進(jìn)行處理。通過(guò)使不同用戶間即使在查詢欄鍵入相同的查詢?cè)~，不同的用戶間所得到的查詢結(jié)果也是不一樣的，使用戶在前幾頁(yè)就能獲得滿意的結(jié)果。

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

IFnQ==niη=1ELSEη=0

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

然而，因?yàn)樯鲜鏊惴ㄖ袔в蠭F語(yǔ)句，在算法的編寫過(guò)程中，若先出現(xiàn)IF、ELSE、SWITCH等語(yǔ)句，將會(huì)大大地降低算法的運(yùn)行效率。為了減少這些語(yǔ)句的出現(xiàn)，需對(duì)上述計(jì)算過(guò)程進(jìn)行優(yōu)化，優(yōu)化后的計(jì)算過(guò)程如下：

為了避免在后續(xù)計(jì)算中頻繁重復(fù)地計(jì)算該用戶對(duì)所有類別認(rèn)可程度之和，先對(duì)該值進(jìn)行統(tǒng)一的運(yùn)算并記為A。用nq與ni之間的同或來(lái)代替IF語(yǔ)句的使用，提高了算法的運(yùn)行效率。通過(guò)優(yōu)化后的計(jì)算，大大地提高了每個(gè)頁(yè)面對(duì)應(yīng)的P_URank值的獲取效率，最后根據(jù)獲得的每個(gè)頁(yè)面的P_URank值進(jìn)行頁(yè)面排序使排序結(jié)果更加符合用戶的需求。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)方案

整個(gè)實(shí)驗(yàn)系統(tǒng)主要分為兩大模塊，第一大模塊是根據(jù)用戶的查詢?cè)~對(duì)數(shù)據(jù)文檔提取形成候選文檔數(shù)據(jù)庫(kù)，第二大模塊則是按照不同的算法對(duì)候選文檔數(shù)據(jù)庫(kù)當(dāng)中的文檔進(jìn)行重新排序并把結(jié)果反饋給用戶。具體實(shí)驗(yàn)系統(tǒng)框架如圖1所示。

圖1 實(shí)驗(yàn)系統(tǒng)整體框架

如實(shí)驗(yàn)系統(tǒng)整體框架圖所示，用戶鍵入查詢?cè)~后，系統(tǒng)將從服務(wù)器資料庫(kù)中檢索與查詢?cè)~相匹配的文檔，并將該文檔存入到候選文檔數(shù)據(jù)庫(kù)中，然后根據(jù)不同排序算法的不同排序規(guī)則對(duì)候選文檔數(shù)據(jù)庫(kù)當(dāng)中的文檔進(jìn)行重新排序的工作，最終把重新排序后的文檔排序結(jié)果反饋給用戶。

3.2 實(shí)驗(yàn)結(jié)果

下面分析針對(duì)“麥當(dāng)勞”這一查詢?cè)~3種算法的搜索結(jié)果中排名前40%的文檔，從文檔內(nèi)容時(shí)間、文檔類型、文檔質(zhì)量等3個(gè)方面對(duì)3種排序算法進(jìn)行綜合評(píng)價(jià)。

圖2 文檔時(shí)間分布比例

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

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

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

圖4 頁(yè)面質(zhì)量均值圖

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

通過(guò)以上3個(gè)方面對(duì)3種算法結(jié)果的分析，可以看出，改進(jìn)后的算法在文檔內(nèi)容時(shí)間與前兩者相差不大的情況下，在文檔類型與用戶興趣類型匹配、文檔頁(yè)面質(zhì)量這兩方面都有較大的提升。

4 結(jié)語(yǔ)

通過(guò)對(duì)頁(yè)面排序算法的改進(jìn)，使頁(yè)面排序算法在時(shí)效性和個(gè)性化服務(wù)方面有了一定的提高，但仍然存在不足。如改進(jìn)算法中只是把查詢時(shí)間和頁(yè)面的內(nèi)容時(shí)間的相關(guān)度進(jìn)行比對(duì)研究，未考慮頁(yè)面的更新時(shí)間。為了進(jìn)一步加強(qiáng)算法，全方位地提高搜索引擎的性能，應(yīng)將重點(diǎn)放在以下方面：如何把頁(yè)面的更新時(shí)間和內(nèi)容時(shí)間結(jié)合在一起為查詢結(jié)果排序提供參考，就算法的運(yùn)行效率方面進(jìn)行反復(fù)的思考優(yōu)化，以縮短算法的響應(yīng)時(shí)間，提高搜索引擎的查詢效率。