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

王倩，宋朝

（黃河科技學院 河南 鄭州 450063）

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

1 構建用戶興趣模型

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

1.1 用戶興趣模型總體結構

模型的結構及創建步驟如圖1所示。用戶的訪問歷史集存放在頁面集合庫中，長期興趣庫和短期興趣庫中按照時間長短存放經興趣分析以及興趣特征優化后得到的興趣信息。

圖1 用戶興趣模型總體結構Fig.1 User interest model structure

1.2 用戶興趣類別表示

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

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

根據該參考模型，我們可以構建用戶興趣樹形結構，考慮到用戶興趣的動態變化和局部性，對興趣類別和特征詞可以分別賦予不同的權值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二部分是數據庫D′（ci）中包含的所有術語t及其權值p′（t|D′（ci）），其中

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

為方便構建算法，對近似內容摘要給出相關的描述如下。

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

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

3 基于用戶興趣模型的元搜索引擎調度算法

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

3.1 數據庫與用戶查詢的相關度計算

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

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

1）查詢q與數據庫的近似內容摘要的相似度計算

在前面的算法中我們已經得到了與查詢q相關度最高的用戶興趣類別集合，一般我們取前2~3個，用CS表示。

2）用戶對成員引擎的偏好權重的計算

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

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

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

4）查詢q與數據庫的相關度計算

有了上面3個值之后，查詢q與數據庫Di的相關度可用下式計算出來：

3.2 元搜索引擎調度成員引擎的過程

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

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

3.3 調度算法的特性分析

根據前文中對調度算法的推導過程可以做如下特性分析：

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

2）用戶查詢若具有較高的區分能力，則更易于選擇合適的成員引擎用于此查詢。

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

4）成員引擎對用戶查詢的響應時間也會影響其相關度高低。

4 結束語

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

[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].計算機工程與設計，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]楊智奇，朱大勇.個性化元搜索引擎的研究與設計[J].計算機與現代化，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]徐科，黃國景，崔志明.元搜索引擎中基于用戶興趣的個性化調度模型[J].清華大學學報：自然科學版，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].圖書館學研究，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]李村合，孟文杰.基于分類評價的元搜索引擎調度策略[J].計算機工程與設計，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.