一種基于用戶偏好和反饋的頁面排序技術(shù)*

廖輝傳

(華東交通大學(xué)信息工程學(xué)院，江西 南昌 330013)

摘要：傳統(tǒng)的排名方法沒有考慮用戶的喜好、反饋和用戶興趣，很難滿足用戶的個性化需求.針對這個問題，提出一種新的網(wǎng)頁排名方法，將網(wǎng)頁的相似度、鏈接結(jié)構(gòu)信息、用戶偏好及用戶反饋相結(jié)合進行頁面排名.實驗結(jié)果表明，改進的排序算法在一定程度上幫助用戶提高檢索網(wǎng)頁的質(zhì)量，最大限度地滿足用戶的需求.

關(guān)鍵詞：網(wǎng)頁排名；搜索引擎；鏈接分析；用戶偏好

萬維網(wǎng)是一個巨大的、多樣的和動態(tài)的信息來源.為了查找相關(guān)數(shù)據(jù)，用戶必須使用各種搜索引擎尋找需要的資源.搜索引擎能夠收集、分析、整理來自互聯(lián)網(wǎng)的數(shù)據(jù)，并且為這些用戶提供檢索網(wǎng)絡(luò)資源的界面.搜索引擎返回的結(jié)果集包含了與查詢相關(guān)和不相關(guān)的各種網(wǎng)址信息，為了向用戶提供相關(guān)的高質(zhì)量信息，其根據(jù)查詢的相關(guān)性和重要性，使用頁面排名模塊來對網(wǎng)頁進行排名.

基于鏈接結(jié)構(gòu)的網(wǎng)頁排名是當(dāng)今搜索引擎中的一個重要技術(shù).最成功的2個Web信息檢索方法是Google的PageRank和Kleinberg提出的HITS算法.它們都是基于鏈接結(jié)構(gòu)的方法.鏈接結(jié)構(gòu)是將網(wǎng)絡(luò)作為一個有向圖，其中網(wǎng)頁形成圖的節(jié)點，超鏈接為有向邊，可以根據(jù)輸入和輸出鏈路的數(shù)目計算網(wǎng)頁的整體排名.然而，不同的人有不同的需求和選擇，一個統(tǒng)一的排名可能不滿足所有用戶的要求.在搜索結(jié)果集中，由于缺乏任何偏好、分類和細(xì)化，搜索引擎不能夠提供精確的信息，因此用戶還必須手動地對結(jié)果信息進行提煉.筆者提出一種新的網(wǎng)頁排序算法，該算法結(jié)合Web內(nèi)容挖掘、Web使用挖掘和結(jié)構(gòu)挖掘，使得網(wǎng)頁的排序結(jié)果更好地滿足用戶查詢的要求.

1相關(guān)工作和背景

網(wǎng)頁排名是搜索引擎使用的一種優(yōu)化技術(shù)，根據(jù)重要性原則對成百上千的網(wǎng)頁給出一個相關(guān)的排序.搜索引擎一般使用2種不同的排名因素：依賴查詢因素(即詞的頻率、查詢詞的位置等)和獨立查詢因素(即鏈接率、點擊率等).依賴查詢因素包含了查詢文本所有的排名因素.獨立查詢因素是與具體文檔相關(guān)的，并不關(guān)心給定的查詢文本如何.基于鏈接的排序算法在當(dāng)前的搜索引擎中占主導(dǎo)地位.頁面排序算法指出，如果一個網(wǎng)頁具有一些重要的輸入鏈接，那么它的輸出鏈接也變得非常重要.在PageRank中，一個網(wǎng)頁的等級評分(P)平均分配給其所有的輸出鏈接.HITS(超鏈接引起的主題搜索)算法則將每個頁面分為權(quán)威頁面(Authority)和中樞(Hub)頁面.表達某一主題的頁面稱為權(quán)威頁面.將權(quán)威頁面結(jié)合在一起就成為中樞頁面.一般而言，好的中樞頁面會指向很多好的權(quán)威頁面，好的權(quán)威頁面也會有許多中樞頁面指向它.頁面根據(jù)它們的中樞頁面和權(quán)威頁面的得分推送給用戶.這2種方法的優(yōu)缺點在文獻[1-2]中都作了介紹.

目前主要的網(wǎng)頁排序技術(shù)不足之處如下所述[3-4]：

(1)基于網(wǎng)頁結(jié)構(gòu)挖掘的網(wǎng)頁排序算法與用戶查詢不太相關(guān)，因為它們不考慮網(wǎng)頁內(nèi)容和當(dāng)前主題的用戶趨勢.

(2)基于網(wǎng)頁內(nèi)容的排序算法完全忽略頁面的價值，它們完全依賴于傳統(tǒng)的搜索引擎和元搜索引擎返回的結(jié)果集.

(3)僅根據(jù)鏈接關(guān)系而不考慮用戶對網(wǎng)頁的興趣和偏好.

隨著搜索引擎的普及，用戶與搜索引擎的交互作用可以用來改進排名技術(shù).個性化網(wǎng)頁排名技術(shù)需要大量的計算和存儲設(shè)備，因此，有必要設(shè)計一種新的頁面排序技術(shù)，可以方便快捷地提供用戶特定的和相關(guān)的信息，可以分析隱含的和明確的用戶反饋.

2改進的網(wǎng)頁排序算法

如上所述，目前網(wǎng)頁排名算法中普遍存在不足，用戶無法通過他們的搜索查詢獲得準(zhǔn)確的結(jié)果.為了克服這些不足，提出了一種新的網(wǎng)頁排名方法.這種方法將網(wǎng)頁結(jié)構(gòu)(網(wǎng)頁的鏈接結(jié)構(gòu))、網(wǎng)絡(luò)使用(基于域名和頁面類型的網(wǎng)頁過去的使用模式和用戶偏好)和網(wǎng)頁內(nèi)容挖掘(查詢詞與頁面內(nèi)容的匹配關(guān)聯(lián)度)組合在一起，目的是為用戶提供最佳的需求與利益的結(jié)合.圖1給出了該算法的體系結(jié)構(gòu).

圖1　改進的排序算法結(jié)構(gòu)

關(guān)鍵詞用戶首先鍵入查詢和選擇自己感興趣的網(wǎng)頁域名或類型，這些細(xì)節(jié)由查詢處理器完成.所有與用戶查詢匹配的頁面從存儲庫轉(zhuǎn)發(fā)到頁面排序模塊，并根據(jù)依賴查詢(域名和內(nèi)容簡介)和獨立查詢(鏈接數(shù)量和用戶行為)分配一個頁面等級.排序好的頁面通過查詢處理器返回給用戶.

算法的主要組成部分為：(1)查詢界面模塊.用于提供給用戶輸入查詢信息和顯示排序結(jié)果的界面.(2)存儲庫.用于存儲庫檢索網(wǎng)頁，包含4個檢索項，分別為檢索詞、網(wǎng)址、域名信息和花費在出現(xiàn)檢索詞的網(wǎng)址上的平均時間.(3)服務(wù)器日志.它是用來存儲一組用戶在多個搜索會話中的花費在每個網(wǎng)頁的平均時間.(4)查詢處理器.用于接收用戶的查詢和域名偏好信息，然后，它從查詢字符串中過濾掉一些不構(gòu)成直接影響的單詞，再進行來自查詢字符串中的相關(guān)關(guān)鍵詞的檢索.(5)頁面排序模塊.

為了給從存儲庫中獲得的網(wǎng)頁進行排序，需要計算頁面的排序分?jǐn)?shù)，在這主要考慮如下4個權(quán)重值：

(1)頁面的流行程度權(quán)重(PR).每一個網(wǎng)頁的流行程度可通過其鏈接結(jié)構(gòu)來衡量，將網(wǎng)絡(luò)看作一個有向圖，網(wǎng)頁為圖的節(jié)點，網(wǎng)頁之間的超鏈接為圖的有向邊.設(shè)網(wǎng)頁A有n個網(wǎng)頁(T1,T2，…，Tn)指向它，Q(Ti)是一個從網(wǎng)頁 A輸出的網(wǎng)頁數(shù)量，則頁面A的流行度權(quán)重PR值為

計算基于鏈接結(jié)構(gòu)的頁面排名算法如下：

(ⅰ)給每個頁面的排名值初始化為1/n,其中n為參與排名的頁面總數(shù)，即A=1/n(0

(ⅱ)取阻尼因子的值0

(ⅲ)重復(fù)每一個結(jié)點i(0≤i

(ⅳ)更新A的值，A=PR(0≤i< n).

重復(fù)(ⅲ)直到排序值收斂.

(2)頁面的歷史權(quán)重(PH_Score).網(wǎng)頁的瀏覽歷史是由一組用戶在一個搜索會話中所花費的平均時間決定.此信息由服務(wù)器日志維護，每一個網(wǎng)頁停留時間(平均花費時間)都與其他網(wǎng)址和域名信息一起存儲在存儲庫中.

(3)用戶偏好權(quán)重(Dm).用戶偏好權(quán)重基于網(wǎng)頁句法分類或網(wǎng)頁域名，即用戶想要獲取的頁面類型或從什么域名獲取.域名權(quán)重(Dm)被定義為一個單位函數(shù)：

(4)文檔內(nèi)容權(quán)重(PC_Score).內(nèi)容權(quán)重是根據(jù)頁面字段中(如URL文本、Meta標(biāo)記、Head標(biāo)簽、Body標(biāo)簽)有多少項和查詢關(guān)鍵詞匹配來決定的，不同類型的頁面其計算方法是不同的.例如可用下式來計算HTML頁面內(nèi)容分?jǐn)?shù)：

PC_Score=0.2*URLT+ 0.2*TitleT+0.3*LinkT+0.3*BodyT.

關(guān)鍵詞其中：URLT為出現(xiàn)在頁面URL中的查詢數(shù)目/URL文本中總的詞匯數(shù)；TitleT為出現(xiàn)在頁面Tile Tag中的查詢關(guān)鍵詞數(shù)目/Title Tag中總的詞匯數(shù)；LinkT為出現(xiàn)在頁面Link Tag中的查詢關(guān)鍵詞數(shù)目/Link Tag中總的詞匯數(shù)；BodyT為出現(xiàn)在頁面Body Tag中的查詢關(guān)鍵詞數(shù)目/Bodyr Tag中總的詞匯數(shù).

同樣地，研究頁面和廣告頁面也可分別由下式計算：

PC_score=0.4*TitleT+0.6*BodyT，

PC_score=0.5*no_of_images + 0.5*no_of_hyperlink.

關(guān)鍵詞其中：TitleT為出現(xiàn)在標(biāo)題中的的數(shù)目/標(biāo)題中總的詞匯數(shù)；BodyT為出現(xiàn)在pdf body中的查詢詞數(shù)目/pdf中總的詞匯數(shù)；no_of_images為圖片數(shù)；no_of_hyperlink為超鏈接數(shù)目.

最后，所有的權(quán)重值相加，共同組成排序總成績(PageRankScore)的值.PageRankScore分?jǐn)?shù)高的頁面給定的等級也高，并提交給用戶參考：

PageRankScore = 0.2*PR + 0.2*PH_Score + 0.3*PC_Score +0.3*Dm.

3實驗仿真

為了驗證改進排序算法的可行性，設(shè)計以JAVA作為前端開發(fā)工具，MySQL作為后臺數(shù)據(jù)庫管理系統(tǒng)的實驗環(huán)境.一個網(wǎng)頁的流行度可以考慮用其鏈接結(jié)構(gòu)計算出來的，整個頁面被解析為提取頁面的鏈接.所提取的鏈接，存儲在適當(dāng)?shù)臄?shù)據(jù)庫表中.

當(dāng)訪問一個網(wǎng)頁時，腳本從網(wǎng)絡(luò)服務(wù)器端加載到客戶端.腳本用來檢查點擊事件的發(fā)生.當(dāng)一個點擊事件發(fā)生時，一個消息被發(fā)送到具有當(dāng)前網(wǎng)頁和超鏈接信息的網(wǎng)絡(luò)服務(wù)器.在服務(wù)器端，使用日志文件的數(shù)據(jù)庫來存儲網(wǎng)頁上的ID、超鏈接和超鏈接的點擊次數(shù).每點擊1次超鏈接，計數(shù)值每增加1次.數(shù)據(jù)庫或日志文件將通過網(wǎng)絡(luò)爬蟲的網(wǎng)絡(luò)抓取來訪問.點擊計數(shù)信息存儲在搜索引擎的數(shù)據(jù)庫中，并用于計算不同網(wǎng)頁或文檔的等級值.每個文檔的相關(guān)信息存儲在數(shù)據(jù)庫的Doc_info表中(表1).

為判斷用戶偏好的域名，需要考慮表2中列出的網(wǎng)頁特征.

關(guān)鍵詞計算網(wǎng)頁內(nèi)容的得分需要用到和文檔信息，關(guān)鍵詞和文檔信息存儲在數(shù)據(jù)庫的file_index表中(表3).當(dāng)用戶鍵入查詢關(guān)鍵字時就會在file_index表中搜索.

文章編號：1007-2985(2015)06-0018-05

中圖分類號：TP391.3文獻標(biāo)志碼：A

DOI:10.3969/j.cnki.jdxb.2015.06.005

收稿日期：*2015-09-29

作者簡介：廖輝傳(1973—)，男，江西萬載人，華東交通大學(xué)信息工程學(xué)院副教授，碩士，主要從事數(shù)據(jù)挖掘和人工智能研究.

表1　Doc_info表的表結(jié)構(gòu)

表2　不同類型的網(wǎng)頁及其特征

表3　file_index表

用戶搜索界面操作很簡潔，用戶首先在文本框中鍵入查詢字符串，并在下拉列表中選擇域名類型和文件類型，然后就可開始查詢.

為了檢驗網(wǎng)頁排序模塊的效果，做了用戶模擬測試，對文中提出的網(wǎng)頁排名方法(基于網(wǎng)頁結(jié)構(gòu)、頁面內(nèi)容和網(wǎng)頁使用挖掘)和Google排名方法Page Rank(基于網(wǎng)頁結(jié)構(gòu))進行對比.選定一些研究生作為測試者，不給他們有關(guān)這項研究目標(biāo)的任何信息.該數(shù)據(jù)庫包括在50個數(shù)據(jù)挖掘?qū)W科的網(wǎng)頁中，選擇總共12個查詢來作研究.測試者開始在系統(tǒng)中鍵入查詢字符串，選擇指定的域名或網(wǎng)頁類型的.提交查詢后，測試者在屏幕上可以看到使用2種方法的排序結(jié)果.用戶界面的設(shè)計操作簡單，不容易評估錯誤.

4測試結(jié)果

當(dāng)測試者面對2套結(jié)果集時，他們將在每套結(jié)果集中選擇數(shù)量相等的URL，然后根據(jù)選定的網(wǎng)頁和用戶的查詢需求是否相關(guān)及相關(guān)程度進行標(biāo)記，主要分為“相關(guān)的”、“不相關(guān)”和“無關(guān)緊要”3種.分?jǐn)?shù)1，0.5，0分別表示相關(guān)度高、相關(guān)度低和不相關(guān)的網(wǎng)頁.可以使用下式計算每個搜索查詢的精度：

精度=通過排序方法得到的相關(guān)網(wǎng)頁分?jǐn)?shù)總和/得到的頁面總數(shù).

表4，5列出的是前N個結(jié)果的精度，分別對應(yīng)改進的新方法和Google Page Ranking方法.

表4　改進的頁面排序方法的精度

表5　Google排序法的精度

圖2繪制的是2種方法的平均精度(結(jié)果集合n=5，10，15).從圖2可看出，使用推薦的新系統(tǒng)的效果更好，能夠為用戶提供更多的相關(guān)網(wǎng)頁.這些初步的測試結(jié)果，雖然是基于少數(shù)用戶的研究數(shù)據(jù)，但為人們提供一個思路，就是在基于用戶偏好的基礎(chǔ)上為用戶提供高質(zhì)量的搜索結(jié)果.

圖2　2個排序系統(tǒng)的平均精度對比

5結(jié)語

許多互聯(lián)網(wǎng)用戶不懂如何使用查詢語法語言從搜索引擎獲得檢索結(jié)果，他們必須執(zhí)行多個查詢，才能獲得滿足他們需要和興趣的信息.而且，由于傳統(tǒng)頁面排序算法中普遍存在的弱點，一些重要的頁面可能不會出現(xiàn)在相對較高的排名位置.筆者提出網(wǎng)頁排名方法，不僅考慮了網(wǎng)頁的鏈接結(jié)構(gòu)和頁面內(nèi)容，還考慮用戶的反饋和喜好.這種改進的新方法的優(yōu)點是，用戶可以在前幾個網(wǎng)址得到需要的信息，而不必到搜索引擎返回的大量的搜索結(jié)果中去找尋.用戶測試結(jié)果表明，改進的排序算法在一定程度上幫助用戶提高檢索網(wǎng)頁的質(zhì)量，最大限度地滿足用戶的需求.

參考文獻：

[1]任麗蕓,楊武,唐蓉.搜索引擎網(wǎng)頁排序算法研究綜述.電腦與電信,2010(5):38-40.

[2]王沖，曹姍姍.基于用戶反饋與主題關(guān)聯(lián)度的網(wǎng)頁排序算法改進.計算機應(yīng)用,2014,34(12):3 502-3 506.

[3]TYAGI N,SHARMA S.Comparative Study of Various Page Ranking Algorithms in Web Structure Mining (WSM).International Journal of Innovative Technology and Exploring Engineering,2012,1(1):14-19.

[4]KUMAR G,DUHAN N,SHARMA A K.Page Ranking Based on Number of Visits of Webpages//International Conference on Computer & Communication Technology(ICCCT).DC,USA:IEEE Computer Society Washington,2011:11-14.

[5]DUBEY H B,ROY N.An Improved Page Rank Algorithm Based on Optimized Normalization Technique.International Journal of Computer Science and Information Techniques(IJCSIT),2011,2(5):2 183-2 188.

New Page Ranking Algorithm Based on User Preference and Feedback

LIAO Huichuan

(School of Information Engineering,East China Jiaotong University，Nanchang 330013，China)

Abstract:It is difficult to meet the individual requirements of users in the traditional ranking methods without considering the user preference,feedback and interest.In view of these problems,a new method of web page ranking is proposed based on web page similarity,link structure information,user preference and user feedback. Experimental results show that the improved ranking algorithm can improve the quality of web page retrieving and can meet the users’requirements greatly.

Key words:page ranking;search engine;link-analysis;user preference

(責(zé)任編輯向陽潔)