盧 洋，石元博

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

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

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

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

1 向量空間模型

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

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

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

對某文檔中的詞語，其TF 公式為：

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

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

1.2 相關(guān)性計算

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

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

2 算法流程

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

圖1 算法整體過程

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

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

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

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

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

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

然后，根據(jù)式(2)計算得出網(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ìn)而確定該頁面的排名順序[15]，其計算公式為：

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

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

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

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

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

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

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

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

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

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

3 實驗及結(jié)果分析

3.1 實驗描述

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

3.2 評價標(biāo)準(zhǔn)

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

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

3.3 實驗結(jié)果

首先，通過傳統(tǒng)PageRank 網(wǎng)頁排序算法計算出網(wǎng)頁排名情況。然后，通過基于向量空間模型的個性化網(wǎng)頁搜索算法得出3 個不同專業(yè)學(xué)生對“病毒”的搜索結(jié)果。通過傳統(tǒng)算法得出排名前15 位的網(wǎng)頁在不同專業(yè)學(xué)生的搜索結(jié)果中排名變化情況。傳統(tǒng)PageRank 算法及本文算法搜索結(jié)果如圖2 所示。為使實驗結(jié)果更加清晰，根據(jù)網(wǎng)頁內(nèi)容對網(wǎng)頁進(jìn)行編碼。折線圖為通過傳統(tǒng)PageRank 算法得出的前15 位網(wǎng)頁的排名情況，柱狀圖為采用本文算法得出的3 個專業(yè)學(xué)生的搜索結(jié)果中這15 個網(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ī)學(xué)學(xué)科有較高的相關(guān)性，兩個專業(yè)關(guān)于“病毒”研究有很多相似點，所以在生物學(xué)專業(yè)學(xué)生搜索醫(yī)1、醫(yī)2、醫(yī)4、醫(yī)5、醫(yī)7、醫(yī)10，醫(yī)學(xué)專業(yè)學(xué)生搜索生4、生7、生9、生10 時也會出現(xiàn)排名上升的情況；因為生物學(xué)與醫(yī)學(xué)專業(yè)與計算機(jī)專業(yè)相差較遠(yuǎn)，所以兩專業(yè)學(xué)生搜索“計算機(jī)病毒”相關(guān)網(wǎng)頁排名明顯下降。

從圖2 還可以看出，在計算機(jī)專業(yè)學(xué)生搜索結(jié)果中網(wǎng)頁編碼為計1、計4、計7、計9、計10 的“計算機(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 個網(wǎng)頁中相關(guān)文檔的比例。表1 列出了以傳統(tǒng)PageRank 算法得出的PR 值作為網(wǎng)頁排序標(biāo)準(zhǔn)的前K 個網(wǎng)頁中各專業(yè)相關(guān)網(wǎng)頁占比，以及針對不同用戶以本文算法得出的PR( p)值作為網(wǎng)頁排序標(biāo)準(zhǔn)的前K 個網(wǎng)頁中相關(guān)專業(yè)網(wǎng)頁占比。

表1 實驗結(jié)果評價

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

4 結(jié)束語

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