面向Web檢索服務(wù)的個性化詞典的研究與實現(xiàn)

李力沛 羅穎

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

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

關(guān)鍵詞： 個性化詞典； 頻繁詞； 用戶興趣建模； 二級向量； Web檢索服務(wù)

中圖分類號：TP391.3文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

1 個性化詞典的定義

個性化詞典UPD（User Personalization Dictionary）由關(guān)鍵詞詞典（KeyDict）和擴(kuò)展詞詞典（ExDict）兩級構(gòu)成，位于兩級詞典中的詞分別定義為關(guān)鍵詞和擴(kuò)展詞。

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

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

以上的關(guān)鍵詞詞典表示，從該用戶瀏覽的網(wǎng)頁提取的詞語中，這部分詞最能夠體現(xiàn)用戶的瀏覽興趣，即用戶關(guān)鍵詞，但它們在用戶興趣中的重要性不同，詞的權(quán)值越大，表示在用戶興趣中的重要性越大。

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

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

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

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

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

2 個性化詞典的實現(xiàn)

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

2.1 詞權(quán)計算公式

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

⑴

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

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

⑵

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

P=（2/3）*N⑶

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

2.2 個性化詞典的生成算法

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

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

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

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

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

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

最后剩下的所有CT構(gòu)成個性化詞典，選取個性化詞典中的前50%作為關(guān)鍵詞典，其余作為擴(kuò)展詞典。

3 實驗及分析

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

表1實驗數(shù)據(jù)集

[[＼&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張網(wǎng)頁，T2包含4個興趣點共205張網(wǎng)頁，T3包含5個興趣點共280張網(wǎng)頁，T4包含5個興趣點共290張網(wǎng)頁。其中T1、T2和T3中各興趣點的網(wǎng)頁數(shù)差距不大，而T4中各興趣點的網(wǎng)頁數(shù)差距較大。從T1到T4，興趣點的數(shù)目逐漸增多，網(wǎng)頁總數(shù)也逐漸增多，而T3與T4的區(qū)別主要是T3中各興趣點分布較均勻，而T4中各興趣點分布不均勻。

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

表2用戶興趣建模的實驗結(jié)果對比

[[＼&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）表示十次建模的平均準(zhǔn)確度，提高量表示在AT和AA這兩類數(shù)據(jù)上，IGAUPD相對于GAUPD的差距。從表2可以看出，在平均花費時間上，IGAUPD和GAUPD相差不大；但是在平均準(zhǔn)確度上，基于IGAUPD生成的個性化詞典進(jìn)行建模的結(jié)果明顯優(yōu)于基于GAUPD生成的個性化詞典進(jìn)行建模的結(jié)果，可以看出，隨著類的數(shù)目和網(wǎng)頁總數(shù)的逐漸增多，兩者的平均準(zhǔn)確度都呈下降趨勢，但是兩者之間的準(zhǔn)確度差距越來越大，這說明使用GAUPD后的建模準(zhǔn)確度下降比IGAUPD更快。特別是當(dāng)興趣點的分布不均勻時，即在T4測試集上，使用IGAUPD后的建模準(zhǔn)確度與使用GAUPD后的建模準(zhǔn)確度差距達(dá)到了7.2%，這說明當(dāng)某用戶的各興趣點所包含的興趣網(wǎng)頁數(shù)量差距較大時，使用IGAUPD后再進(jìn)行興趣建模，能更加準(zhǔn)確地描述用戶的興趣。

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

表3個性化檢索的實驗結(jié)果對比

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

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

綜上所述，由于采用了IWTUPD，IGAUPD能夠比GAUPD更準(zhǔn)確地計算詞權(quán)，基于IGAUPD的個性化詞典關(guān)鍵詞和擴(kuò)展詞更能體現(xiàn)用戶的興趣和興趣偏好，且排序更準(zhǔn)確，因此，在用戶興趣建模和個性化檢索中，使用基于IGAUPD的個性化詞典能夠更準(zhǔn)確地建立用戶興趣模型，檢索到更符合用戶興趣的結(jié)果?？傊?，基于IGAUPD的個性化詞典比基于GAUPD的個性化詞典更有優(yōu)勢。

4 結(jié)束語

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

參考文獻(xiàn)：

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

現(xiàn)[J].計算機(jī)應(yīng)用研究，2009.10.

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

代，2009.11：31-33

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

2011.28（10）：121-124

[4] 陳志雄，朱向慶.基于特征詞統(tǒng)計的網(wǎng)頁結(jié)構(gòu)化信息抽取[J].嘉應(yīng)學(xué)

院學(xué)報，2011.29（2）：18-21

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

計算機(jī)工程與應(yīng)用，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] 徐靜秋，朱征宇，譚明紅，任翔.基于二級向量描述的搜索引擎?zhèn)€性化

服務(wù)模型[J].計算機(jī)科學(xué)，2007.34（11）：89-93

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

式[J].計算機(jī)應(yīng)用，2005.25（9）：2031-2033

[9] 于洪波.網(wǎng)頁特征提取技術(shù)研究[J].山東理工大學(xué)學(xué)報，2011.25（2）：

107-110

[10] 張敏.基于Web的個性化信息檢索關(guān)鍵技術(shù)研究[J].計算機(jī)時代，

2006.3：37-38