基于用戶興趣模型的元搜索引擎算法研究

王倩，宋朝

（黃河科技學(xué)院 河南 鄭州 450063）

搜索引擎是獲取信息的重要手段[1]，在使用普通搜索引擎搜索信息時，總是存在這樣的問題[2-3]：返回的結(jié)果數(shù)目龐大，很多結(jié)果與查詢并不相關(guān)，依然要花費大量的時間尋找有用的信息。為了幫助用戶在避免無用信息干擾的情況下獲得其所需的信息，提高查詢效率，本文研究了基于用戶興趣模型的元搜索引擎實現(xiàn)技術(shù)，利用元搜索引擎修正普通搜索引擎搜索范圍較窄，檢索結(jié)果不夠全面的缺點；利用構(gòu)建用戶興趣模型消除歧義，縮小用戶查詢的范圍，修正元搜索引擎在處理不同用戶需求方面的不足。

1 構(gòu)建用戶興趣模型

用戶興趣建模的過程是根據(jù)用戶的個人信息和偏好的瀏覽內(nèi)容進行歸納量化，設(shè)計出可以用數(shù)學(xué)方式表示的用戶興趣模型[4]。

1.1 用戶興趣模型總體結(jié)構(gòu)

模型的結(jié)構(gòu)及創(chuàng)建步驟如圖1所示。用戶的訪問歷史集存放在頁面集合庫中，長期興趣庫和短期興趣庫中按照時間長短存放經(jīng)興趣分析以及興趣特征優(yōu)化后得到的興趣信息。

圖1 用戶興趣模型總體結(jié)構(gòu)Fig.1 User interest model structure

1.2 用戶興趣類別表示

在模型中的興趣生成模塊需要構(gòu)建興趣類別。我們通過對興趣特征等級特性的定義來生成一個開放目錄，對用戶可能有的興趣特征采用一個分類的層次結(jié)構(gòu)模型表示。這是一個類似于對象繼承的關(guān)系結(jié)構(gòu)。興趣特征基類包含興趣特征派生類的所有共同特征，而興趣特征派生類相比興趣特征基類則具有各自不同的特點屬性。結(jié)構(gòu)如圖2所示，圖中興趣類別用方框表示，特征詞和擴充的特征詞用橢圓表示。

圖2 用戶興趣分類參考模型Fig.2 User interest classification model

根據(jù)該參考模型，我們可以構(gòu)建用戶興趣樹形結(jié)構(gòu)，考慮到用戶興趣的動態(tài)變化和局部性，對興趣類別和特征詞可以分別賦予不同的權(quán)值。

以 C 表示用戶興趣集，其包含元素為（c1，c2，…，cm），m 表示用戶的興趣類別總數(shù)目，ci（1≤i≤m）為集合C的一個元素，代表一個興趣類別。以T（ci）表示用戶興趣特征詞集合，其包含元素為（t1，t2，…，tk），k 表示用戶興趣特征詞總數(shù)目，ti（1≤i≤k）表示為ci的特征詞。所以用戶所有特征詞集的并集就是用興趣特征詞集，表示為T（C）。即：

以二元組（c，w）表示用戶興趣節(jié)點 Node（c），c∈C，w 為 c的權(quán)重。 以二元組（t，w）表示 c 的特征詞節(jié)點 Leaf（c，t），t∈T（c），w為t在c中的權(quán)重。以此為基礎(chǔ)，我們以m元組U（C）來表示用戶的興趣向量，其表示形式為 Node（c1），Node（c2），…，Node（cm））。

1.3 用戶查詢到用戶興趣類別的映射算法設(shè)計

本節(jié)提出一種生成用戶興趣類的方法。通過該方法，可以對用戶的查詢信息確定用戶興趣類別[5-6]。這個過程的主要步驟是對用戶查詢信息與已建模的用戶興趣類別之間的相似度進行計算，把用戶的查詢結(jié)果限制在相似度最高的幾個用戶興趣類別中。

將用戶查詢 q 表示為向量（t1，t2，…，tm），其中每個分量代表查詢q的一個查詢特征詞，查詢特征詞的總數(shù)目為m。查詢q的查詢特征詞集我們用Q表示。存在兩種情況：

1）假設(shè)q中的查詢特征詞在用戶興趣樹中所屬的所有興趣類別集合用C（q）表示，c（c∈C）表示用戶興趣類別，它的特征詞表示為集合（w1，w2，…，wn），記作 p（c）。 其中 wi是它所對應(yīng)的特征詞ti在用戶興趣類別c中的權(quán)重，即

2）若用戶查詢對應(yīng)的興趣類別不存在于用戶興趣類別中，即T（C）∩Q=Φ，則可以進行如下定義：

用Cr表示興趣分類參考模型中所有興趣類別的集合，用戶興趣類別 c（c∈Cr）的查詢特征詞權(quán)重向量 p（c）中的 wi定義為：

根據(jù)上述兩種情況，可以從用戶興趣向量U（C）和用戶查詢條件q得到計算用戶查詢條件和用戶興趣類別相似度的算法，進而得到跟用戶查詢條件相近的用戶興趣類別。

2 基于興趣分類采樣的成員引擎特征表示

在構(gòu)建數(shù)據(jù)庫的特征表示之前，定義TD（ci）表示興趣類別 ci的分類辭典，且有 TD（ci）={t|t∈T（ci）∧ci∈Cq}，所有興趣類別的分類辭典總辭典表示為 TD（Cq）={TD（c1），TD（c2），…，TD （cn）}，n為興趣類別的總數(shù)。也就是說TD來源于兩個方面，一方面是表示ci的類別名；另一方面是類的特征詞。

我們假設(shè)D′是由數(shù)據(jù)庫D中采樣文檔d的集合組成，D′數(shù)據(jù)庫創(chuàng)建的內(nèi)容摘要為 S（D′），則 S（D′）就是數(shù)據(jù)庫 D 的近似內(nèi)容摘要[9]。對數(shù)據(jù)庫D′按照用戶興趣分類，可以得到D′={D′（c1），D′（c2），...，D′（cn）}，近似內(nèi)容摘要 S′（D）也進行細分為 S′（D）={S′（c1，D），S′（c2， D），...，S′（cn， D）}， 其中 D′（ci）表示在數(shù)據(jù)庫D′中根據(jù)興趣類別ci采樣得到文檔的集合所組成的數(shù)據(jù)庫。S′（ci，D）則表示以上數(shù)據(jù)的創(chuàng)建的近似內(nèi)容摘要。

數(shù)據(jù)庫D基于用戶興趣類別ci的近似內(nèi)容摘要S′（ci，D）是由兩個基本部分組成：

第一部分是 D′（ci）中實際文檔總數(shù)目|D′（ci）|；

第二部分是數(shù)據(jù)庫D′（ci）中包含的所有術(shù)語t及其權(quán)值p′（t|D′（ci）），其中

常用的成員引擎特征表示方法有：基于查詢采樣（Query-Based Sampling，QBS）[7]的近似內(nèi)容摘要表示法和聚焦探測（Focused Probing，F(xiàn)P）[8]的近似內(nèi)容摘要構(gòu)建算法。我們將用戶興趣模型同近似內(nèi)容摘要法相結(jié)合，提出了一種新的算法：基于用戶興趣分類的近似內(nèi)容摘要表示法。

為方便構(gòu)建算法，對近似內(nèi)容摘要給出相關(guān)的描述如下。

首先規(guī)定數(shù)據(jù)庫D的內(nèi)容摘要S（D）由兩部分組成：第一部分是D中實際文檔總數(shù)，表示為|D|；第二部分是D中包含的所有術(shù)語t及其權(quán)值p（t|D），其中

利用以上描述就能夠根據(jù)不同興趣類別較好地表示對應(yīng)數(shù)據(jù)庫的近似內(nèi)容摘要，并且可以表達出不同的搜索引擎數(shù)據(jù)庫基于用戶興趣類別的文檔信息。

3 基于用戶興趣模型的元搜索引擎調(diào)度算法

本節(jié)中提出的算法能根據(jù)用戶的興趣愛好來選擇調(diào)度最接近用戶偏好文檔的搜索引擎。采用基于用戶興趣分類采樣的特征表示算法來表示數(shù)據(jù)庫的特征。在用戶提交查詢信息到搜索引擎時和用戶興趣類別進行映射，得到相應(yīng)的興趣類別。元搜索引擎調(diào)度模塊首先根據(jù)用戶興趣類別對成員引擎數(shù)據(jù)庫和用戶查詢信息之間相似度進行計算，然后根據(jù)計算所得的相似度結(jié)合用戶興趣類中成員搜索引擎的權(quán)重和搜索引擎對用戶查詢的平均響應(yīng)時間計算得出成員搜索引擎同用戶查詢信息之間的相關(guān)度。算法原理及實現(xiàn)描述如下：

3.1 數(shù)據(jù)庫與用戶查詢的相關(guān)度計算

假設(shè) D 為數(shù)據(jù)庫，M 元組（D1，D2，…，Dm）為元搜索引擎中所有成員搜索引擎的數(shù)據(jù)庫集，記作DS[10]。根據(jù)上節(jié)可以得到各個數(shù)據(jù)庫的近似內(nèi)容摘要。第i個數(shù)據(jù)庫Di的近似內(nèi)容摘要記作 S′（D），S′（D）={S′（c1，Di），S′（c2，Di），...，S′（cj，Di）}（1≤i≤m，1≤j≤n）。 其中 n 為用戶興趣類別數(shù)目，S′（cj，Di）為數(shù)據(jù)庫Di在用戶興趣類別ci的近似內(nèi)容摘要。t表示用戶查詢術(shù)語，q表示用戶查詢，為 t的h元組集合，則 q=（（t1，t2，...，th）。 其中，h 為查詢術(shù)語數(shù)目。

還需要作查詢q與數(shù)據(jù)庫集合DS中包含的每個數(shù)據(jù)庫相關(guān)度的計算[11]。假設(shè)查詢q與數(shù)據(jù)庫Di的相似度記為rel（q，Di），計算它的前提是要先完成三個值的計算[12-13]，下面分別進行表述。

1）查詢q與數(shù)據(jù)庫的近似內(nèi)容摘要的相似度計算

在前面的算法中我們已經(jīng)得到了與查詢q相關(guān)度最高的用戶興趣類別集合，一般我們?nèi)∏?~3個，用CS表示。

2）用戶對成員引擎的偏好權(quán)重的計算

用戶若頻繁使用搜索引擎，應(yīng)該會察覺到某些成員搜索引擎會比其他成員引擎更好地搜索到有用的信息，也會較多地點擊該成員引擎返回的結(jié)果。系統(tǒng)會記錄最近k次用戶對查詢結(jié)果的點擊情況以監(jiān)測成員引擎對用戶查詢的幫助表現(xiàn)。用戶越多地瀏覽從某個數(shù)據(jù)庫返回的結(jié)果，越說明這個數(shù)據(jù)庫更受用戶的偏好。

3）成員引擎對用戶查詢的平均響應(yīng)時間計算。

為避免使用響應(yīng)時間太長的成員引擎，系統(tǒng)會記錄成員引擎在用戶的最近k次查詢中響應(yīng)時間的平均值tr。系統(tǒng)事先規(guī)定th為響應(yīng)時間閾值，to為響應(yīng)超時時間[14]，若對于某個成員引擎Di，tr的值大于th，則該成員引擎對用戶查詢的權(quán)值減少量為 pr（Di）=（tr-th）2/（to-th）2。

4）查詢q與數(shù)據(jù)庫的相關(guān)度計算

有了上面3個值之后，查詢q與數(shù)據(jù)庫Di的相關(guān)度可用下式計算出來：

3.2 元搜索引擎調(diào)度成員引擎的過程

1）將用戶查詢q與各成員引擎數(shù)據(jù)庫的相關(guān)度計算出來；2）將成員引擎根據(jù)相關(guān)度降序排列；

3）根據(jù)排序后的列表，選擇相關(guān)度最大的幾個成員引擎為用戶提供查詢服務(wù)。

3.3 調(diào)度算法的特性分析

根據(jù)前文中對調(diào)度算法的推導(dǎo)過程可以做如下特性分析：

1）若成員引擎的所有文檔中與用戶查詢映射的興趣類相關(guān)的較多，則該成員引擎與用戶查詢的相關(guān)性較高；

2）用戶查詢?nèi)艟哂休^高的區(qū)分能力，則更易于選擇合適的成員引擎用于此查詢。

3）成員引擎越多地被用戶點擊，就越能獲得較高的相關(guān)度；

4）成員引擎對用戶查詢的響應(yīng)時間也會影響其相關(guān)度高低。

4 結(jié)束語

隨著信息技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)已經(jīng)成為人們工作和生活都離不開的工具，同時人們對從網(wǎng)上獲取信息的方式也提出了更高的要求，用戶迫切要求改進搜索方式。本文本著應(yīng)對用戶需求，提高搜索效率和精度的目標，研究了怎樣將個性化搜索技術(shù)融入到元搜索引擎中，在理論上確定了可行算法。本文根據(jù)用戶描述信息設(shè)計了用戶興趣模型，并進行了量化表示；研究了將用戶查詢映射到用戶興趣模型的算法，便于推測用戶興趣范圍，提高查詢結(jié)果精度。同時本文改進了元搜索引擎的成員引擎調(diào)度算法，選擇對用戶最可能有用的成員引擎完成檢索工作，使查詢質(zhì)量和查詢效率能明顯改進。

[1]喬亞男，齊勇，侯迪.文本信息檢索實驗方法研究[J].中國科技論文在線，2009，4（2）:126-129.

QIAO Yan-an，QI Yong，HOU Di.Research on experimental methods of text information retrieval[J].Sciencepaper Online，2009，4（2）:126-129.

[2]張宗仁，楊天奇.基于主題樹的個性化元搜索引擎[J].計算機工程與設(shè)計，2011，32（1）:149-152.

ZHANG Zong-ren，YANG Tian-qi.Personalized meta search engine based on subject tree[J].Computer Engineering and Design，2011（32）:149-152.

[3]楊智奇，朱大勇.個性化元搜索引擎的研究與設(shè)計[J].計算機與現(xiàn)代化，2009，（9）:52-55.

YANG Zhi-qi，ZHU Da-yong.Research on personal meta search engine[J].Computer and Modernization，2009， （9）:52-55.

[4]LI Zheng-wei，XIA Shi-xiong，NIU Qiang，et al.Research on the User Interest Modeling of personalized Search Engine[J].Wuhan University Journal of Natural Sciences，2007，12（5）:893-896.

[5]Gauch S，Wang G，Gomez M.ProFusion:Intelligent fusion from multiple，distributed search engines[J].Journal of Universal Computer Science，1996，2（9）:637-649.

[6]Howe A E，Dreilinger D.SavvySearch:A meta-search engine that learns which search engines to query[J].AI Magazine，1997，18（2）:19-25.

[7]Callan，J.P.； Connell，M.，Query-based sampling oftext databases[Z].ACM TOIS， 2001，19（2）

[8]Panagiotis，G.，Ipeirotis，Gravano，L.， Summarizing and searching hidden-web databases.hierarchically using focused probes[R].Technical Report CUCS-015-01，Columbia University， Computer Science Department，2001.

[9]徐科，黃國景，崔志明.元搜索引擎中基于用戶興趣的個性化調(diào)度模型[J].清華大學(xué)學(xué)報：自然科學(xué)版，2005，45（S1）:1916-1919.

XU Ke，HUANG Guo-jing，CUI Zhi-ming.Personalized scheduling algorithm based on user profile for meta search engine[J].J Tsinghua Univ：Sci&Tech，2005，45（S1）:1916-1919.

[10]ZHANG Wei-feng，XU Bao-wen，ZHOU Xiao-yu，etal.Scheduling in a meta search engine by Genetic Algorithm[J].Wuhan University Journal of Natural Sciences，2001，（Z1）:541-546.

[11]Salton G，McGill M J.Introduction to Modern Information Retrieval[M].New York:McGraw-Hill，1983：103-106.

[12]任洪平.中文元搜索引擎成員搜索引擎的選擇策略研究[J].圖書館學(xué)研究，2009（01）:40-43.

REN Hong-ping.Study on Sub-Search Engine Scheduling Strategy for Chinese Meta Search Engine[J].Researches in Library Science，2009（1）:40-43.

[13]李村合，孟文杰.基于分類評價的元搜索引擎調(diào)度策略[J].計算機工程與設(shè)計，2008，29（5）:1065-1066.

LI Cun-he，Meng Wen-jie.Scheduling strategy for meta search engine based on categorizing measurementof members[J].Computer Engineering and Design，2008，29（5）:1065-1066.

[14]Dreilinger D，Howe A.Experiences with selecting search engines using metasearch[J].ACM TOIS，1997，15（3）:195-222.

[15]Callan JP，ConnellM.Query-based sampling oftext databases[J].ACM TOIS，2001，19（2）:102-108.