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

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

廖輝傳

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

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

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

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

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

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

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

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

(1)基于網(wǎng)頁(yè)結(jié)構(gòu)挖掘的網(wǎng)頁(yè)排序算法與用戶查詢不太相關(guān)，因?yàn)樗鼈儾豢紤]網(wǎng)頁(yè)內(nèi)容和當(dāng)前主題的用戶趨勢(shì).

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

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

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

2改進(jìn)的網(wǎng)頁(yè)排序算法

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

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

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

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

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

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

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

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

(ⅱ)取阻尼因子的值0

(ⅲ)重復(fù)每一個(gè)結(jié)點(diǎn)i(0≤i

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

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

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

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

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

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

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

同樣地，研究頁(yè)面和廣告頁(yè)面也可分別由下式計(jì)算：

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中的查詢?cè)~數(shù)目/pdf中總的詞匯數(shù)；no_of_images為圖片數(shù)；no_of_hyperlink為超鏈接數(shù)目.

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

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

3實(shí)驗(yàn)仿真

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

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

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

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

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

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

DOI:10.3969/j.cnki.jdxb.2015.06.005

收稿日期：*2015-09-29

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

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

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

表3　file_index表

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

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

4測(cè)試結(jié)果

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

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

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

表4　改進(jìn)的頁(yè)面排序方法的精度

表5　Google排序法的精度

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2]王沖，曹姍姍.基于用戶反饋與主題關(guān)聯(lián)度的網(wǎng)頁(yè)排序算法改進(jìn).計(jì)算機(jī)應(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é)任編輯向陽(yáng)潔)