基于向量空間模型的個(gè)性化網(wǎng)頁搜索算法研究

盧 洋，石元博

（遼寧石油化工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，遼寧 撫順 113001）

據(jù) 國 際 數(shù) 據(jù) 公 司 (International Data Corporation, IDC)估計(jì)，到2020 年，所有創(chuàng)建、復(fù)制和消費(fèi)的數(shù)字?jǐn)?shù)據(jù)將達(dá)到40 Zb[1]。信息量爆炸式的增長(zhǎng)使人們對(duì)在海量數(shù)據(jù)中查找更加符合自己要求的信息更為渴望。完成個(gè)性化搜索、提高用戶對(duì)搜索結(jié)果的滿意度，是信息檢索的主要任務(wù)。

在信息檢索過程中，網(wǎng)頁排序算法尤為重要。作為谷歌的重要網(wǎng)頁排序算法，PageRank 算法是由Google 創(chuàng) 始 人B.Sergey 和P.Lawrence 于1998 年 提出的一種網(wǎng)頁排名算法[2]。但是，PageRank 算法在其提出過程中并沒有考慮用戶的個(gè)性化需要[3]。因此，對(duì)PageRank 算法進(jìn)行改進(jìn)，使其能完成個(gè)性化搜索成為許多研究者所關(guān)注的問題。王沖等[4]構(gòu)建用戶興趣度因子，同時(shí)結(jié)合主題相關(guān)度因子對(duì)網(wǎng)頁P(yáng)ageRank 值進(jìn)行修正。黃賢英等[5]利用用戶搜索歷史記錄網(wǎng)頁瀏覽時(shí)間以及同類用戶協(xié)同過濾這些基于用戶興趣度的主觀特性來改進(jìn)PageRank 算法。Y.Tang 等[6]設(shè)計(jì)了一種通過用戶點(diǎn)擊率修正參數(shù)的個(gè)性化PageRank 算法，從而提高檢索結(jié)果的排序質(zhì)量。其他許多研究者也做了類似改進(jìn)，不過此種改進(jìn)方法大多偏重用戶的網(wǎng)頁停留時(shí)間、點(diǎn)擊率等瀏覽信息，并不能全面系統(tǒng)地描述用戶的興趣。

本文引入用戶畫像（User profile）這一在個(gè)性化推薦領(lǐng)域常用的方法來建立一個(gè)相對(duì)完整的用戶興趣度描述模型，提高用戶對(duì)搜索結(jié)果的滿意程度。用戶畫像是基于大數(shù)據(jù)開展精準(zhǔn)營銷的核心，王碩慜等[7]提出了一種基于節(jié)目標(biāo)簽和用戶標(biāo)簽的個(gè)性化推薦算法，此算法以電視節(jié)目與電視用戶具有的特點(diǎn)為基礎(chǔ)來建立用戶畫像。針對(duì)本文提出的問題，根據(jù)網(wǎng)頁與用戶興趣信息、用戶搜索內(nèi)容多為文字的特點(diǎn)，采用向量空間模型(Vector Space Model, VSM)建立用戶畫像。袁仁進(jìn)等[8]提出了一種基于VSM 和Bisecting K‐means 聚類的新聞推薦方法，但其僅以用戶瀏覽過的新聞為基礎(chǔ)建立用戶興趣模型，并未考慮個(gè)人背景等用戶信息。為了更加全面地刻畫用戶興趣，本文以用戶個(gè)人信息、網(wǎng)頁瀏覽歷史、搜索歷史、下載歷史等為基礎(chǔ)，通過VSM 建立用戶畫像。王東[9]將用戶畫像應(yīng)用于個(gè)性化書籍推薦，進(jìn)一步證明了用戶畫像可以有效地提升用戶滿意度，其優(yōu)點(diǎn)可以彌補(bǔ)其他研究者對(duì)個(gè)性化PageRank 算法改進(jìn)的不足，根據(jù)這一特點(diǎn)，本文提出了基于VSM 的個(gè)性化網(wǎng)頁搜索算法。

1 向量空間模型

VSM 是信息檢索領(lǐng)域最為經(jīng)典的計(jì)算模型,在該模型中,用特征向量來表示文檔中的多維信息,然后通過計(jì)算特征向量計(jì)算之間相似程度對(duì)文檔內(nèi)容進(jìn)行劃分[10]。為了使搜索結(jié)果更加準(zhǔn)確地貼近用戶興趣，采用K 最近鄰(K‐Nearest Neighbors,KNN)算法進(jìn)一步得出網(wǎng)頁與用戶興趣的相關(guān)性。

1.1 特征詞權(quán)重計(jì)算

最常用的計(jì)算特征詞權(quán)重的方法為TF‐IDF 算法，TF‐IDF 由兩部分組成：詞頻（TF）指的是某一個(gè)特定的詞語在該文本中出現(xiàn)的頻率；逆文檔頻率（IDF）,即文本數(shù)量與某一個(gè)特定的詞語在文本集中出現(xiàn)的次數(shù)的比值[11]。TF‐IDF 實(shí)際上是TF×IDF[12]。

對(duì)某文檔中的詞語，其TF 公式為：

某文檔dj中的詞語ti，其IDF 公式為：

式中，D 為文件的總數(shù)目；mti為包含詞語ti的文檔數(shù)目；f (ti,dj) 為特征詞ti在文檔里出現(xiàn)的頻次；為文檔dj中所有字詞出現(xiàn)的頻次總和。

1.2 相關(guān)性計(jì)算

KNN 算法是一種主要用于分類以及回歸的非參數(shù)統(tǒng)計(jì)方法[13]。在文本分類中，采用KNN 算法將文檔用經(jīng)過特征加權(quán)后的特征項(xiàng)表示成空間向量后，根據(jù)相應(yīng)的方法計(jì)算待分類文本的空間向量與已知類別的文本向量間相似程度，得到相似程度最高 的K 個(gè) 文 本[10]。

通過上述特征詞權(quán)重計(jì)算方法可以得到用戶畫像向量空間，根據(jù)此向量空間采用常用的余弦相似度計(jì)算方法得到K 個(gè)最近鄰用戶畫像向量，并通過該K 個(gè)用戶畫像向量得出網(wǎng)頁和用戶興趣的相關(guān)度[14]。其中ai、bi兩個(gè)文本余弦相似度計(jì)算公式為：

2 算法流程

算法整體過程如圖1 所示。首先通過向量空間模型建立用戶畫像模型U，其次使用KNN 方法計(jì)算出網(wǎng)頁與用戶畫像向量之間的關(guān)聯(lián)概率，最后結(jié)合PageRank 算 法 得 出 最 終 的PageRank 值PR( p)，根據(jù)PageRank 值得出最終網(wǎng)頁排序結(jié)果。

圖1 算法整體過程

步驟1 通過TF‐IDF 算法計(jì)算用戶興趣特征詞權(quán)重wi及網(wǎng)頁特征詞權(quán)重wi'，wi的計(jì)算公式為：

對(duì)于某個(gè)網(wǎng)頁，計(jì)算其特征詞權(quán)重時(shí)并未涉及到文檔總數(shù)這一概念，只計(jì)算某特征詞ti'在該網(wǎng)頁文檔中的出現(xiàn)的頻率，所以用TF 值來表示其特征詞權(quán)重值wi',即：

步驟2 通過步驟1 可得到用戶畫像向量空間U 及網(wǎng)頁向量p，用戶畫像向量空間U={u1,u2,…,un}，由用戶的各個(gè)用戶興趣向量ui組成，ui及網(wǎng)頁向量p 表示為：

步驟3 根據(jù)向量空間，通過KNN 算法計(jì)算網(wǎng)頁與用戶興趣的相關(guān)性。

首先，通過式（6）計(jì)算網(wǎng)頁向量和用戶畫像向量之間的余弦值。

根據(jù)余弦值可以得到網(wǎng)頁的K 最近鄰用戶畫像向量U'。

然后，根據(jù)式(2)計(jì)算得出網(wǎng)頁向量p 和用戶畫像向量空間U 之間的關(guān)聯(lián)概率PU( p)，即網(wǎng)頁與用戶興趣之間的相關(guān)性。

式中，yi為ui所歸屬的用戶畫像空間。

步驟4 改進(jìn)傳統(tǒng)PageRank 算法，通過本文算法得到網(wǎng)頁最終的PageRank 值PR( p)及最終網(wǎng)頁排名。

PageRank 算法的核心思想是通過研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和計(jì)算頁面的入度，進(jìn)而確定該頁面的排名順序[15]，其計(jì)算公式為：

式中，PR(Ti) 為指向該頁面的其他頁面Ti的PageRank 值；C(Ti)為頁面Ti指向其他頁面的鏈接數(shù)；d 為阻尼系數(shù)，表示用戶隨機(jī)到達(dá)一個(gè)頁面的概率，通常d=0.85。

綜上，網(wǎng)頁最終的PageRank 值PR( p)計(jì)算公式為：

最后，根據(jù)PR( p)值對(duì)網(wǎng)頁進(jìn)行排序得到最終網(wǎng)頁排序結(jié)果。偽代碼描述算法過程為：

輸入：網(wǎng)頁指向關(guān)系文檔file，網(wǎng)頁pi，用戶興趣文檔dj

輸出：網(wǎng)頁排名

（1）計(jì)算網(wǎng)頁初始排名PR ←PageRank(file)；

（2）計(jì) 算 網(wǎng) 頁 pi特 征 詞 ti' 及 權(quán) 重

（5）計(jì)算p 和ui的相似度cos( p,ui)，選取k 值；

（6）得出pi與dj的關(guān)聯(lián)概率PU( p)；

（7）輸出網(wǎng)頁排名PR( p)←PR×PU( p)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)描述

經(jīng)由網(wǎng)絡(luò)爬蟲獲取的網(wǎng)站初始數(shù)據(jù), 存在大量冗余的、有噪音的、不精確的、不完整的或者不一致的數(shù)據(jù)[16]。為了減少網(wǎng)頁噪聲對(duì)實(shí)驗(yàn)結(jié)果的影響，采用從中國知網(wǎng)(http://www.cnki.net/)下載的文獻(xiàn)作為網(wǎng)頁數(shù)據(jù)源。為了驗(yàn)證本文方法，采用“病毒”這一具有歧義性的詞語作為查詢關(guān)鍵詞，實(shí)體名稱的歧義性是指一個(gè)實(shí)體名字可能代表不同的事物或者意義[17]。下載計(jì)算機(jī)、生物學(xué)、醫(yī)學(xué)相關(guān)文獻(xiàn)30 篇，其中包括“計(jì)算機(jī)病毒”“生物病毒”“醫(yī)學(xué)病毒”相關(guān)文獻(xiàn)各10 篇，并根據(jù)論文引用關(guān)系等信息模擬網(wǎng)頁鏈接關(guān)系。以計(jì)算機(jī)、生物、臨床醫(yī)學(xué)3 個(gè)專業(yè)的3 名學(xué)生作為用戶，根據(jù)其瀏覽歷史、搜索歷史、下載歷史、個(gè)人信息等來建立其用戶畫像，并通過本文提出的算法得出不同專業(yè)學(xué)生對(duì)“病毒”的搜索結(jié)果。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

采用的評(píng)價(jià)標(biāo)準(zhǔn)為P@K[18]，該指標(biāo)衡量的是用戶對(duì)整體檢索結(jié)果的滿意度，它反映檢索的前K 個(gè)結(jié)果中被認(rèn)為是相關(guān)的文檔比例[19],其表達(dá)式為：

式中，Ks為前K 個(gè)查詢結(jié)果中相關(guān)網(wǎng)頁的個(gè)數(shù)。

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

首先，通過傳統(tǒng)PageRank 網(wǎng)頁排序算法計(jì)算出網(wǎng)頁排名情況。然后，通過基于向量空間模型的個(gè)性化網(wǎng)頁搜索算法得出3 個(gè)不同專業(yè)學(xué)生對(duì)“病毒”的搜索結(jié)果。通過傳統(tǒng)算法得出排名前15 位的網(wǎng)頁在不同專業(yè)學(xué)生的搜索結(jié)果中排名變化情況。傳統(tǒng)PageRank 算法及本文算法搜索結(jié)果如圖2 所示。為使實(shí)驗(yàn)結(jié)果更加清晰，根據(jù)網(wǎng)頁內(nèi)容對(duì)網(wǎng)頁進(jìn)行編碼。折線圖為通過傳統(tǒng)PageRank 算法得出的前15 位網(wǎng)頁的排名情況，柱狀圖為采用本文算法得出的3 個(gè)專業(yè)學(xué)生的搜索結(jié)果中這15 個(gè)網(wǎng)頁的排名情況。

圖2 傳統(tǒng)PageRank 算法及本文算法的搜索結(jié)果

從圖2 可以看出，與傳統(tǒng)PageRank 算法排名相比，生物專業(yè)學(xué)生搜索結(jié)果中網(wǎng)頁編碼為生4、生7、生9、生10 的“生物病毒”相關(guān)網(wǎng)頁排名有所上升，醫(yī)學(xué)專業(yè)學(xué)生搜索結(jié)果中網(wǎng)頁編碼為醫(yī)1、醫(yī)2、醫(yī)4、醫(yī)5、醫(yī)7、醫(yī)10 的“醫(yī)學(xué)病毒”相關(guān)網(wǎng)頁排名也有所上升；因?yàn)樯铩⑨t(yī)學(xué)學(xué)科有較高的相關(guān)性，兩個(gè)專業(yè)關(guān)于“病毒”研究有很多相似點(diǎn)，所以在生物學(xué)專業(yè)學(xué)生搜索醫(yī)1、醫(yī)2、醫(yī)4、醫(yī)5、醫(yī)7、醫(yī)10，醫(yī)學(xué)專業(yè)學(xué)生搜索生4、生7、生9、生10 時(shí)也會(huì)出現(xiàn)排名上升的情況；因?yàn)樯飳W(xué)與醫(yī)學(xué)專業(yè)與計(jì)算機(jī)專業(yè)相差較遠(yuǎn)，所以兩專業(yè)學(xué)生搜索“計(jì)算機(jī)病毒”相關(guān)網(wǎng)頁排名明顯下降。

從圖2 還可以看出，在計(jì)算機(jī)專業(yè)學(xué)生搜索結(jié)果中網(wǎng)頁編碼為計(jì)1、計(jì)4、計(jì)7、計(jì)9、計(jì)10 的“計(jì)算機(jī)病毒”相關(guān)網(wǎng)頁的排名相較于其在傳統(tǒng)網(wǎng)頁排序算法結(jié)果中的排名有了明顯上升，而“生物病毒”與“醫(yī)學(xué)病毒”相關(guān)網(wǎng)頁排名都有所下降。

本文采用P@5、P@10、P@15、P@20 來衡量網(wǎng)頁排序結(jié)果前K 個(gè)網(wǎng)頁中相關(guān)文檔的比例。表1 列出了以傳統(tǒng)PageRank 算法得出的PR 值作為網(wǎng)頁排序標(biāo)準(zhǔn)的前K 個(gè)網(wǎng)頁中各專業(yè)相關(guān)網(wǎng)頁占比，以及針對(duì)不同用戶以本文算法得出的PR( p)值作為網(wǎng)頁排序標(biāo)準(zhǔn)的前K 個(gè)網(wǎng)頁中相關(guān)專業(yè)網(wǎng)頁占比。

表1 實(shí)驗(yàn)結(jié)果評(píng)價(jià)

從表1 可以看出，采用本文算法得到的搜索結(jié)果的P@K 值有了明顯的提高，即符合用戶興趣的相關(guān)網(wǎng)頁排名有所上升。這說明在本文的改進(jìn)算法下，某一網(wǎng)頁在具有較高PageRank 值的同時(shí)也應(yīng)與用戶畫像模型的相關(guān)性更高，該網(wǎng)頁排名才能靠前，即排名靠前的網(wǎng)頁更加符合不同用戶的需求。

4 結(jié)束語

提出一種基于向量空間模型的個(gè)性化網(wǎng)頁搜索算法，通過向量空間模型建立用戶畫像，更加全面地描述用戶興趣信息，再結(jié)合傳統(tǒng)的PageRank 網(wǎng)頁排序算法，完成用戶的個(gè)性化搜索。實(shí)驗(yàn)證明，與傳統(tǒng)的PageRank 算法相比，個(gè)性化網(wǎng)頁搜索算法能夠解決傳統(tǒng)PageRank 算法沒有考慮的用戶個(gè)性化需要的問題，提高了用戶對(duì)搜索結(jié)果的滿意度。另外，由于實(shí)驗(yàn)條件限制，實(shí)驗(yàn)采用的數(shù)據(jù)集較小，無法給出更加精確的算法提升效率值，下一步研究過程中應(yīng)更加貼近實(shí)際網(wǎng)絡(luò)環(huán)境，完善實(shí)驗(yàn)結(jié)果。