面向Web檢索服務的個性化詞典的研究與實現

李力沛 羅穎

（1. 長江師范學院數學與計算機學院， 重慶 408100； 2. 中冶賽迪技術股份有限公司）

摘要： 為了更好地向用戶提供個性化的Web檢索服務，實現了一種改進的個性化詞典的生成算法——IGAUPD，用于在用戶瀏覽的大量興趣網頁中挖掘出真正符合用戶興趣的詞語，以此縮小傳統詞庫的容量，使得在用戶興趣建模時，能更快更準確地形成興趣網頁的特征描述，并更好地支持個性化檢索。IGAUPD算法采用新的詞權計算公式IWTUPD，以更好地描述詞語在網頁集中的重要性，有效排除頻繁詞。最后，用實驗驗證了由IGAUPD算法生成的個性化詞典的優勢。

關鍵詞： 個性化詞典； 頻繁詞； 用戶興趣建模； 二級向量； Web檢索服務

中圖分類號：TP391.3文獻標志碼：A 文章編號：1006-8228（2012）11-01-03

Research and implementation of personalization dictionary for web retrieval service

Li Lipei1， Luo Ying2

（1. College of Mathematics and Computer Science， Yangtze Normal University， Chongqing 408100， China； 2. CISDI）

Abstract： For the sake of providing better personalizing service of web information retrieval for users， an improved generating algorithm of user personalizing dictionary has been accomplished in the paper， which can be used for mining the terms which can tally with interests of users truly from a mass of web pages that browsed by users， resulting in narrowing the size of traditional dictionary， helping to generate the feature description of interested web pages more quickly and accurately， and supporting the personality retrieval better. The importance of words in the web pages is better described and frequently-used words are excluded more efficiently in the IGAUPD， in which a new formula about the weight of words named IWTUPD has been used. Finally， some experiments have proved the advantages of the user personalization dictionary created by IGAUPD.

Key words： user personalization dictionary； frequently-used word； double vector； user interests modeling； the service of web information retrieval

0 引言

近十幾年來，因特網上的各種信息呈指數級的速度增長，使得互聯網用戶想要快速找到其真正所需要的信息或資料越來越困難。因此需要針對每個用戶提供個性化的檢索服務，以解決因特網中信息的多樣化與用戶需求的專一化之間的矛盾。

提供個性化的Web檢索服務，首先需要掌握每個用戶特有的興趣，即對用戶的興趣進行建模，形成針對某特定用戶的興趣描述文件。網頁文本的分詞及特征提取在大多數用戶興趣建模系統中占有重要地位，如文獻[2]采用基于遺傳算法的BP神經網絡系統學習用戶興趣，其學習模型包括三個模塊：頁面處理、興趣提取和興趣更新，其中頁面處理模塊就包括了中文分詞。文獻[3]提出一種基于主成份支持向量機的網頁自動分類方法進行建模，首先還是對網頁進行分詞及特征提取。文獻[4，5，9]則著重網頁文本的特征描述。文獻[5]對權重公式和向量空間模型同時進行改進，以更好的方式描述網頁文本，這個過程中自然也包括網頁文本分詞。文獻[9]采用基于詞性的方法提取網頁中的特征詞并用DF與TF相結合的公式計算詞權。文獻[4]通過“打碎”網頁文檔，提取出“精細化”、“條目化”的網頁特征，在提取特征詞的過程中，應用了特征詞典，卻沒有對特征詞典作進一步的闡述。文獻[2-5，9]在網頁特征提取的過程中均需使用詞典，只有文獻[4]提出特征詞典的概念。若借助傳統的全局詞典（詞量通常在10萬以上）提取網頁內容的特征，會使提取網頁特征的時間開銷較大，并且由于傳統詞典里大量的詞其實對于用戶興趣建模沒有直接作用，且很多詞是頻繁詞，如果這些詞進入了網頁特征向量里反而會形成噪聲，影響網頁內容的挖掘效果。因此有必要像文獻[4]一樣建立特征詞典。本文提出一種針對用戶的興趣特征建立的大致符合用戶興趣的個性化詞典，該詞典包含的詞量較少，絕大部分詞都能反映用戶的興趣，并且盡量排除頻繁詞，避免在提取網頁特征時形成噪聲數據。

本文提出的個性化詞典是在傳統詞典的基礎上，以用戶的瀏覽歷史網頁集合為依據，形成每個用戶獨立的詞典空間，該詞典空間分為兩級，即關鍵詞詞典和擴展詞詞典，分別用于描述用戶的核心興趣和興趣偏好，以支持用二級向量描述的用戶模型[7]。

1 個性化詞典的定義

個性化詞典UPD（User Personalization Dictionary）由關鍵詞詞典（KeyDict）和擴展詞詞典（ExDict）兩級構成，位于兩級詞典中的詞分別定義為關鍵詞和擴展詞。

每一級詞典中包含n個（n由人為設定）由詞和詞權構成的二元組，這些詞表示用戶特有的信息需求特征。例如：

某用戶的關鍵詞詞典為：[（筆記本，0.03211385）；（股票，0.02812798）；（蘋果，0.02620156）；（內存，0.02032729）；（籃球，0.01815624）；（運動員，0.01528336）；（李寧，0.011354642）；……（用戶，0.003213658）；……]

以上的關鍵詞詞典表示，從該用戶瀏覽的網頁提取的詞語中，這部分詞最能夠體現用戶的瀏覽興趣，即用戶關鍵詞，但它們在用戶興趣中的重要性不同，詞的權值越大，表示在用戶興趣中的重要性越大。

我們用類似的方法表示擴展詞詞典，擴展詞的重要性小于關鍵詞，在用戶建模中，擴展詞用于描述用戶在核心興趣點上的興趣偏好。

特定用戶的UPD能夠充分表達用戶對信息需求的傾向性，同時對基于二級向量的用戶興趣模型提供支持，是一種符合用戶興趣的私有詞典，在詞典設計上主要考慮如下原則：

⑴ 網頁文檔集合中，某詞出現的頻度越高，該詞對用戶興趣特征的描述能力越強；

⑵ 網頁文檔集合中，包含某詞的網頁數在達到某閾值前，數量越多，該詞對用戶興趣特征的描述能力越強，而超過某閾值后，數量越多則該詞對用戶興趣特征的描述能力越弱；

⑶ 對于一些網頁中比較常用的，沒有檢索價值的詞，本文稱之為頻繁詞，如：評論、版權、文章等。經過大量的統計發現，頻繁詞通常分布在網頁集合的大多數文檔中，而在單張網頁中出現的次數較少（一般為1-2次），在詞典中應該被過濾掉，以免對用戶的個人描述帶來噪音。

2 個性化詞典的實現

個性化詞典是在通用詞庫的基礎上，通過對用戶所瀏覽的網頁進行分詞、詞權計算、排序等過程的處理，最終形成每個用戶獨立的詞典空間，其中最重要的過程是詞權的計算。

2.1 詞權計算公式

文獻[1]中提出了一種基于傳統TF-IDF公式的個性化詞典詞權計算公式WTUPD（Weight of Term in the User Personalization Dictionary），如公式⑴所示。

⑴

公式⑴中，S為網頁文檔集合，T為詞空間，W（t，S）為詞t在S中的權重，tf（t，S）為詞t在S中的詞頻，N為S包含的文檔總數，nt為S中的文檔出現t的數量，分母為歸一化因子。文獻[1]認為：個性化詞典中的詞的權值與該詞在樣本集中的頻度成正比，而與包含該詞的樣本分布成反比，即在樣本集中，包含該詞的樣本越多，該詞的重要性越大，權值越大，反之重要性越小，權值越小。按照這種思路理解，包含于大量樣本中的頻繁詞可能就會具有較高的權值，但事實上頻繁詞應該具有更低的權值。

針對以上問題，本文認為個性化詞典中詞的權值與包含該詞的樣本數的關系應是隨樣本數的增加先遞增，到達一個閾值后再遞減。因為如果某個詞t只包含于少數的幾個樣本中，那么t難以表達用戶的主要興趣，只有當t包含于大多數的樣本中時，t才能反映用戶的主要興趣，但是當T出現在絕大多數樣本中后，t可能就是一個頻繁詞，從而失去提取價值。因此本文在WTUPD的基礎上進行改進，得到改進后的個性化詞典詞權計算公式IWTUPD（Improved Weight of Term in the User Personalization Dictionary），如公式⑵所示。

⑵

公式⑵中最后的Evenness（t）依然為均勻度的因子，即詞t在樣本集中的標準差。而P為包含詞t的樣本數閾值，本文認為超過閾值P，則包含詞t的樣本數對詞權的重要性就逐漸降低，因此在公式⑵中引入了二次曲線，P的表達式如下：

P=（2/3）*N⑶

另外，當樣本值超過閾值P后，重要性的下降速度要快于達到閾值P之前重要性的上升速度，所以又添加了第二項即nt-P用來調節重要性的下降速度。因此IWTUPD公式體現出樣本集中的詞對于樣本集的重要性是隨著該詞在樣本集中出現的頻度增加而增加，但是又受到包含該詞的樣本數的制約（即當包含該詞的樣本數低于閾值P時，隨著樣本數的增加，該詞的重要性遞增；當包含該詞的樣本數超過閾值P時，隨著樣本數的增加，該詞的重要性則遞減）。

2.2 個性化詞典的生成算法

本文在文獻[1]提出的個性化詞典生成算法GAUPD（Generating Algorithm of User Personalization Dictionary）的基礎上進行改進，提出了改進后的個性化詞典生成算法IGAUPD（Improved Generating Algorithm of User Personalization Dictionary），以下是該算法的步驟。

首先根據通用詞庫對用戶所瀏覽的網頁文本進行提詞，獲得基本詞空間BTS（Based Term Space），同時利用IWTUPD公式計算BTS中的每個詞的權值，并將BTS中的詞按照詞權進行排序，經過這一步，重要的詞語會排序靠前，而頻繁詞會排序靠后。

然后按從大到小的順序在BTS中選擇一定比例的詞作為候選詞CT（Candidate Term）。本文建議對于興趣點較集中的用戶選擇前40%的詞，而興趣點較分散（核心興趣點5個以上）的用戶選擇前50%的詞，由于經過第一步排序后，頻繁詞基本被排到了后面，那么選擇出來的詞中包含頻繁詞的可能性就比較小。

接著從CT中篩選頻繁詞，根據前面對頻繁詞的描述，我們采用如下的函數篩選頻繁詞。

filter（t）={t|t∈W（3N/4）∩E（tf（t，S）/n）≤2}⑷

公式⑷中t∈W（3N/4）表示詞t出現在占用戶瀏覽的總網頁集中3/4的網頁中，E（tf（t，S）/n）≤2表示詞t在網頁中出現次數的均值不大于2。此函數找出所有在3/4及更大比例的網頁中出現且平均出現次數不大于2次的詞，這些詞將被視為沒有意義的頻繁詞而從CT中去除。

最后剩下的所有CT構成個性化詞典，選取個性化詞典中的前50%作為關鍵詞典，其余作為擴展詞典。

3 實驗及分析

本文使用的實驗數據來自于搜狗網提供的搜狐新聞網頁，覆蓋財經（bu），體育（sp），汽車（au），軍事（mi），IT（it）共5個類，每個類300張網頁，共1500張網頁，然后從這5個類中分別抽取一定數量的網頁作為用戶的興趣網頁，組成測試集。本文使用的測試集共4個，測試集包含的興趣點別和網頁數量如表1所示。

表1實驗數據集

[[＼&it＼&au＼&bu＼&sp＼&mi＼&T1＼&＼&65＼&60＼&60＼&＼&T2＼&50＼&50＼&40＼&65＼&＼&T3＼&50＼&55＼&60＼&60＼&55＼&T4＼&35＼&90＼&40＼&80＼&45＼&]]

表1中，T1包含3個興趣點共185張網頁，T2包含4個興趣點共205張網頁，T3包含5個興趣點共280張網頁，T4包含5個興趣點共290張網頁。其中T1、T2和T3中各興趣點的網頁數差距不大，而T4中各興趣點的網頁數差距較大。從T1到T4，興趣點的數目逐漸增多，網頁總數也逐漸增多，而T3與T4的區別主要是T3中各興趣點分布較均勻，而T4中各興趣點分布不均勻。

首先，采用文獻[6]提出的用戶興趣建模算法測試應用IGAUPD算法生成用戶個性化詞典后對用戶興趣建模的影響，用戶興趣建模主要使用個性化詞典中的關鍵詞。為了對比說明IGAUPD的效果，我們首先分別使用IGAUPD和GAUPD生成用戶個性化詞典，然后根據不同的個性化詞典分別對4個測試集提取網頁特征并進行10次用戶興趣建模，比較兩者之間的時間差異和建模準確性差異，實驗結果如表2所示。

表2用戶興趣建模的實驗結果對比

[[＼&T1＼&T2＼&T3＼&T4＼&＼&AT（m）＼&AA＼&AT＼&AA＼&AT＼&AA＼&AT＼&AA＼&IGAUPD＼&13.6＼&89.6%＼&16.2＼&86.5%＼&18.3＼&84.3%＼&20.4＼&79.5%＼&GAUPD＼&13.9＼&87.8%＼&16.1＼&83.4%＼&18.5＼&79.7%＼&20.1＼&72.3%＼&提高量＼&0.3＼&1.8%＼&-0.1＼&3.1%＼&0.2＼&4.6%＼&-0.3＼&7.2%＼&]]

在表2中，AT（Average Time）表示十次建模的平均花費時間，單位是分鐘（m），AA（Average Accuracy）表示十次建模的平均準確度，提高量表示在AT和AA這兩類數據上，IGAUPD相對于GAUPD的差距。從表2可以看出，在平均花費時間上，IGAUPD和GAUPD相差不大；但是在平均準確度上，基于IGAUPD生成的個性化詞典進行建模的結果明顯優于基于GAUPD生成的個性化詞典進行建模的結果，可以看出，隨著類的數目和網頁總數的逐漸增多，兩者的平均準確度都呈下降趨勢，但是兩者之間的準確度差距越來越大，這說明使用GAUPD后的建模準確度下降比IGAUPD更快。特別是當興趣點的分布不均勻時，即在T4測試集上，使用IGAUPD后的建模準確度與使用GAUPD后的建模準確度差距達到了7.2%，這說明當某用戶的各興趣點所包含的興趣網頁數量差距較大時，使用IGAUPD后再進行興趣建模，能更加準確地描述用戶的興趣。

其次，采用文獻[7]提出的個性化檢索系統來測試應用IGAUPD算法生成用戶個性化詞典后對Web檢索的影響，個性化檢索主要利用個性化詞典中的擴展詞。為了對比說明IGAUPD的效果，我們先分別使用IGAUPD和GAUPD生成用戶的個性化詞典，然后對T2測試集進行一次用戶興趣建模，并利用戶興趣模型中的所有關鍵詞在google上進行個性化檢索測試，將每個關鍵詞檢索到的前10頁結果作為一個樣本集合并求該集合的中心，再計算集合中心與對應的興趣點之間的余弦相似度。針對兩個個性化詞典的實驗數據對比如表3所示。

表3個性化檢索的實驗結果對比

[[＼&興趣點的搜索結果與用戶興趣模型的相似度＼&IGAUPD＼&GAUPD＼&提高比例＼&IT＼&0.1534＼&0.1427＼&7.5%＼&汽車＼&0.1452＼&0.1379＼&5.3%＼&財經＼&0.0859＼&0.0785＼&9.4%＼&體育＼&0.1187＼&0.1042＼&13.4%＼&平均值＼&0.1258＼&0.1158＼&8.6%＼&]]

從表3可以看出，在個性化檢索中，用基于IGAUPD的個性化詞典提供擴展詞，比基于GAUPD的個性化詞典有更好的檢索結果，四個興趣點的平均提高比例為8.6%，這說明基于IGAUPD的個性化詞典提供的擴展詞能準確地反映用戶的興趣偏好。

綜上所述，由于采用了IWTUPD，IGAUPD能夠比GAUPD更準確地計算詞權，基于IGAUPD的個性化詞典關鍵詞和擴展詞更能體現用戶的興趣和興趣偏好，且排序更準確，因此，在用戶興趣建模和個性化檢索中，使用基于IGAUPD的個性化詞典能夠更準確地建立用戶興趣模型，檢索到更符合用戶興趣的結果。總之，基于IGAUPD的個性化詞典比基于GAUPD的個性化詞典更有優勢。

4 結束語

本文針對個Web檢索中的個性化問題，提出了一種改進的權值計算公式IWTUPD用于計算個性化詞典中的關鍵詞和擴展詞的詞權，并對GAUPD算法進行了改進，提出了IGAUPD算法。實驗表明，IGAUPD算法生成的個性化詞典比GAUPD算法生成的個性化詞典能更好地支持用戶興趣建模和個性化檢索。在下一步的研究中，我們將研究更合適的權值計算公式用于生成個性化詞典，并研究如何動態地更新個性化詞典，使得個性化詞典能夠隨著用戶興趣的變遷而不斷調整。

參考文獻：

[1] 羅穎，朱征宇，李力沛，周智.Web檢索模型上個性化詞典的研究與實

現[J].計算機應用研究，2009.10.

[2] 劉靜，李華亮.個性化搜索引擎中興趣學習方法的研究[J].計算機時

代，2009.11：31-33

[3] 周序生，李爽.網頁自動分類的建模與仿真研究[J].計算機仿真，

2011.28（10）：121-124

[4] 陳志雄，朱向慶.基于特征詞統計的網頁結構化信息抽取[J].嘉應學

院學報，2011.29（2）：18-21

[5] 韓立毛，鞠時光，羊晶璟.個性化搜索引擎中網頁特征描述的研究[J].

計算機工程與應用，2011.47（11）：94-97

[6] Zhu Zhengyu， Tian Yunyan， Yuan Kunfeng， et al.An improved

Web documents claustering methord[J].Journal of Computational Information Systems，2007.3（3）：1087-1094

[7] 徐靜秋，朱征宇，譚明紅，任翔.基于二級向量描述的搜索引擎個性化

服務模型[J].計算機科學，2007.34（11）：89-93

[8] 羅欣，夏德麟，晏蒲柳.基于詞頻差異的特征選取及改進的TF-IDF公

式[J].計算機應用，2005.25（9）：2031-2033

[9] 于洪波.網頁特征提取技術研究[J].山東理工大學學報，2011.25（2）：

107-110

[10] 張敏.基于Web的個性化信息檢索關鍵技術研究[J].計算機時代，

2006.3：37-38