帶有聚類功能的個(gè)性化元搜索引擎的設(shè)計(jì)

摘要：隨著英特網(wǎng)上信息量的迅速增長(zhǎng)，用戶想要從中找到感興趣的信息變得越來(lái)越困難，傳統(tǒng)的搜索引擎不能很好地解決這個(gè)問(wèn)題。因此本文提出了一種帶有聚類功能的個(gè)性化元搜索引擎，系統(tǒng)通過(guò)用戶注冊(cè)獲得用戶數(shù)據(jù)并對(duì)所有的用戶進(jìn)行聚類形成不同用戶群病產(chǎn)生用戶模式，搜索引擎調(diào)度模塊通過(guò)用戶模式來(lái)選擇適合的搜索引擎進(jìn)行調(diào)度得到個(gè)性化的搜索結(jié)果，再將檢索到的結(jié)果進(jìn)行聚類處理，返回給用戶個(gè)性化的搜索結(jié)果。分析了帶有聚類功能的個(gè)性化元搜索引擎的系統(tǒng)構(gòu)成，詳細(xì)介紹了每個(gè)模塊的功能，最后展望了它的發(fā)展前景。

關(guān)鍵詞：信息檢索；元搜索引擎；聚類；個(gè)性化

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)34-1581-02

Design of Personalized Meta-Search Engine Based on Clustering

CHEN Ju-hong

(Institute of Information Science and Technology， Southwest Jiaotong University， Chengdu 610031， China)

Abstract: With the rapid growth of online information， it has become increasingly difficult for users to search for information of their interests; the traditional search engines can not satisfy this need. In this paper a customized search engine of cluster function is introduced. First， the registration system obtains user date through their registrations and categorizes these applicants into different user groups to create user custom. The scheduling module of search engine selects the appropriate search engine by the sort of user custom to obtain customized search results， then it makes cluster processing and put out the final result. The constitute of clustering customable search engine is introduced in this paper， each of the modules' function and relating technology are introduced in detail. The perspective of this search engine is discussed in the end of this paper.

Key words: information retrieval; meta-search engine; clustering; personalized model

1 引言

隨著Internet/Intranet的迅速發(fā)展，對(duì)Internet/Intranet上的信息處理將日益成為人們關(guān)注的焦點(diǎn)[1] 。面對(duì)網(wǎng)上資源急劇增長(zhǎng)的狀況， 用戶在尋找信息存在很大的困難，主要表現(xiàn)在：1) 信息過(guò)載：收到的或已經(jīng)下載的信息難以消化，導(dǎo)致用戶的查詢?cè)L問(wèn)經(jīng)常存在大量無(wú)關(guān)的信息；2) 信息迷向：用戶不知道知何貼切表達(dá)真正想要的網(wǎng)上資源的需求。

目前搜索引擎是人們從Internet上獲取信息的主要工具，但當(dāng)前單個(gè)搜索引擎的覆蓋率受到很大限制。據(jù)統(tǒng)計(jì)，任何一個(gè)搜索引擎索引的 Web 頁(yè)面實(shí)際上都不到頁(yè)面總數(shù)的三分之一，而且由于檢索機(jī)制、范圍、算法等的不同，導(dǎo)致同樣一個(gè)查詢請(qǐng)求不同搜索引擎中的查詢結(jié)果重復(fù)率比較低。而且據(jù)艾瑞市場(chǎng)咨詢[2]的最新調(diào)查結(jié)果顯示，在中國(guó)搜索引擎用戶不滿意的因素中，搜索結(jié)果排序欠佳、搜索結(jié)果太雜亂這兩項(xiàng)的比例分別是43%和37%。搜索引擎得到的結(jié)果量非常巨大，對(duì)于一個(gè)普通的查詢往往會(huì)返回成千上萬(wàn)的結(jié)果，例如在Google中搜索“數(shù)據(jù)挖掘”會(huì)得到1，850，000項(xiàng)結(jié)果，然而顯示結(jié)果卻是一個(gè)線性列表(ranked list)，其中相關(guān)信息和無(wú)關(guān)信息混雜在一起。用戶不得不逐個(gè)瀏覽各項(xiàng)搜索結(jié)果，使得用戶找到自己真正需要的信息仍然如同大海撈針一樣困難。

為解決以上問(wèn)題，本文提出了帶有聚類功能的個(gè)性化元搜索引擎的設(shè)計(jì)框架，用戶提出搜索要求，由元搜索引擎進(jìn)行加工，轉(zhuǎn)換成多個(gè)獨(dú)立的搜索引擎一起搜索，并將搜索結(jié)果處理后返回給用戶。整個(gè)系統(tǒng)的關(guān)鍵是在用戶個(gè)人模型和搜索結(jié)果上運(yùn)用聚類分析，形成不同的用戶群及針對(duì)不同用戶返回個(gè)性化搜索結(jié)果。

2 元搜索引擎

元搜索引擎[3]建立在搜索引擎基礎(chǔ)之上的搜索引擎，它通過(guò)接口向多個(gè)成員發(fā)送請(qǐng)求，調(diào)用成員搜索引擎返回的搜索結(jié)果，而無(wú)需自己建立和維護(hù)龐大引數(shù)據(jù)庫(kù)。元搜索引擎通常都包含用戶接口，查詢分發(fā)器，結(jié)果整合器三個(gè)組成部分。它們之間的流程關(guān)系如圖所示，根據(jù)箭頭的流向可以看出搜索引擎在處理用戶的查詢請(qǐng)求時(shí)的處理流程。

■

圖1 元搜索引擎結(jié)構(gòu)圖

用戶接口：負(fù)責(zé)提供一個(gè)統(tǒng)一的查詢接口和結(jié)果顯示界面。力求界面友好，操作簡(jiǎn)單，符合人們的使用和思維習(xí)慣。

查詢分發(fā)器：如果成員搜索引擎的數(shù)目較小，無(wú)需進(jìn)行成員引擎的調(diào)度，那么該模塊直接將用戶的搜索請(qǐng)求分別轉(zhuǎn)化為每個(gè)成員搜索引擎能夠識(shí)別的格式；如果成員搜索引擎數(shù)目很多且不同的成員引擎所覆蓋的領(lǐng)域大不相同，那么該模塊除了負(fù)責(zé)將用戶的搜索請(qǐng)求分別轉(zhuǎn)化為每個(gè)成員搜索引擎能夠識(shí)別的格式外，還要負(fù)責(zé)對(duì)成員搜索引擎進(jìn)行調(diào)度。

結(jié)果整合器：負(fù)責(zé)對(duì)成員搜索引擎返回的結(jié)果頁(yè)而進(jìn)行結(jié)構(gòu)分析，抽取結(jié)果集，并對(duì)結(jié)果集進(jìn)行二次處理，如刪除重復(fù)的結(jié)果、結(jié)果整合、重新排序等，并將處理后的搜索結(jié)果顯示給用戶。

以上三個(gè)模塊是元搜索引擎必不可少的部分，具體在設(shè)計(jì)的時(shí)候，還可以在這些模塊基礎(chǔ)之土添加新的模塊，以實(shí)現(xiàn)特殊的功能。

3 系統(tǒng)框架和功能介紹

3.1 系統(tǒng)體系結(jié)構(gòu)框架

本系統(tǒng)是針對(duì)傳統(tǒng)搜索引擎的不足，在現(xiàn)有的搜索引擎的基礎(chǔ)上[4]，充分考慮個(gè)性化、便捷性等的要求，并且結(jié)合Agent技術(shù)與數(shù)據(jù)挖掘技術(shù)而設(shè)計(jì)的。其系統(tǒng)結(jié)構(gòu)如圖2所示。

3.2 系統(tǒng)各功能的介紹

3.2.1 用戶模式生成模塊

用戶模式生成模塊負(fù)責(zé)用戶與系統(tǒng)的交互，提交用戶的查詢關(guān)鍵詞并生成用戶的興趣模式。本模塊可以通過(guò)對(duì)用戶的注冊(cè)信息進(jìn)行分析，并進(jìn)行用戶群聚類，形成新的用戶興趣庫(kù)，用戶興趣庫(kù)可以通過(guò)對(duì)用戶使用日志的挖掘以及用戶對(duì)結(jié)果的反饋進(jìn)行更新。用戶登錄系統(tǒng)后在輸入， 輸出界面上輸入自己的查詢要求，系統(tǒng)將根據(jù)用戶信息從用戶興趣庫(kù)中挑用該用戶的用戶興趣模式，然后送到下一層模塊檢索。用戶模式生成模塊具有一定的學(xué)習(xí)性和反應(yīng)性，它通過(guò)對(duì)用戶提出的查詢要求和用戶已瀏覽過(guò)的查詢結(jié)果不斷地分析和訓(xùn)練，使用戶模式能更好地應(yīng)用戶的動(dòng)態(tài)需求變化。 隨著用戶的不斷使用，能擁有一個(gè)比較準(zhǔn)確的用戶興趣模型和一定的適用經(jīng)驗(yàn)，對(duì)搜索信息的個(gè)性化有極大的幫助。

3.2.2 檢索模塊

檢索模塊主要包含兩個(gè)模塊和一個(gè)數(shù)據(jù)庫(kù)：搜索引擎調(diào)度模塊、查詢格式轉(zhuǎn)換模塊和搜索引擎知識(shí)庫(kù)。搜索引擎調(diào)度模塊中儲(chǔ)存有搜索引擎調(diào)度算法，根據(jù)算法從搜索引擎知識(shí)庫(kù)中查找合適的引擎進(jìn)行搜索。查詢格式轉(zhuǎn)換模塊將查詢要求轉(zhuǎn)換成對(duì)應(yīng)搜索引擎所能識(shí)別的搜索格式。知識(shí)庫(kù)中存儲(chǔ)有各個(gè)搜索引擎的搜索情況和搜索格式，包括搜索專題的劃分情況、某類專題的搜索速度、查準(zhǔn)率和查全率、權(quán)威頁(yè)面檢索率等信息。

3.2.3 結(jié)果處理模塊

結(jié)果處理模塊將各搜索引擎返回的搜索結(jié)果進(jìn)行處理，包括將文本形式的結(jié)果轉(zhuǎn)換成相應(yīng)的數(shù)據(jù)格式，再將檢索結(jié)果綜合處理，去掉無(wú)鏈接的頁(yè)面，去除冗余、重復(fù)、多余的數(shù)據(jù)，然后對(duì)得到的結(jié)果進(jìn)行聚類處理并根據(jù)用戶興趣模式對(duì)類內(nèi)的結(jié)果進(jìn)行排序，最后將結(jié)果以統(tǒng)一的格式返回到輸入輸出界面。同時(shí)，搜索引擎評(píng)價(jià)模式抽取所得到的搜索引擎檢索情況中的有用數(shù)據(jù)項(xiàng)，來(lái)更新搜索引擎知識(shí)庫(kù)。

4 系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)

4.1 搜索引擎調(diào)度策略

元搜索引擎的調(diào)度過(guò)程為：

1) 計(jì)算各成員引擎的數(shù)據(jù)庫(kù)與用戶查詢q的相關(guān)度rel(q，Di)

■

其中Di表示成員引擎數(shù)據(jù)庫(kù)；q表示用戶查詢；sim(q，Si(Di))表示數(shù)據(jù)庫(kù)的近似內(nèi)容摘要熵對(duì)于查詢q的相似度

■(其中twij表示tj在第i個(gè)數(shù)據(jù)庫(kù)中的權(quán)重占所有數(shù)據(jù)庫(kù)中tj的權(quán)重的比例；distj表示查詢術(shù)語(yǔ)tj與其它術(shù)語(yǔ)的區(qū)分能力);pc(Di)表示用戶對(duì)數(shù)據(jù)庫(kù)Di偏好的權(quán)重，m為成員引擎的總數(shù)■(aclick(Di)第k次查詢中用戶平均點(diǎn)擊次數(shù)) 。

2) 再根據(jù)相關(guān)度的大小對(duì)成員引擎進(jìn)行降冪排序；

3) 選取排名最前的幾個(gè)(通常3~10個(gè))成員引擎為用戶查詢服務(wù)。

4.2 查詢格式轉(zhuǎn)化策略

在確定了元搜索引擎要調(diào)用的成員搜索引擎后，我們需要把用戶輸入的查詢轉(zhuǎn)化為各個(gè)成員搜索引擎的查詢語(yǔ)法格式，并送到各個(gè)成員搜索引擎。表1給出了幾個(gè)著名的搜索引擎的查詢語(yǔ)法格式：

其中%searchkeywords%代表的是輸入的查詢關(guān)鍵字。如果要增加新的成員搜索引擎，只需在該成員搜索引擎中輸入查詢的關(guān)鍵字后搜索，根據(jù)地址欄中的地址來(lái)得到新的搜索引擎的查詢語(yǔ)法格式。（下轉(zhuǎn)第1611頁(yè)）

（上接第1582頁(yè)）

4.3 對(duì)查詢結(jié)果進(jìn)行聚類處理

本文利用聚類有關(guān)方法對(duì)搜索引擎返回的結(jié)果進(jìn)行初步聚類，然后分析各類和用戶查詢請(qǐng)求之間的相關(guān)度獲得類排序，接著計(jì)算類內(nèi)各結(jié)果與用戶興趣模型的相關(guān)度，并按相關(guān)度的大小對(duì)類內(nèi)的結(jié)果進(jìn)行排序。

基本步驟是：

1) 對(duì)各搜索引擎的查詢結(jié)果進(jìn)行聚類分析，形成對(duì)查詢結(jié)果的自動(dòng)分類。

文本聚類基于“聚類假設(shè)”，是一種無(wú)指導(dǎo)的文本分類，它把一個(gè)文本集分成若干稱為簇（clustering）的子集，每個(gè)簇中的文本之間具有較大的相似性，而簇之間的文本具有較小的相似性。本文采用模糊c均值聚類算法，該算法是目前聚類分析中最受歡迎的算法之一。它把聚類問(wèn)題歸結(jié)為一個(gè)非線性規(guī)劃問(wèn)題，利用交替優(yōu)化策略求解無(wú)監(jiān)督分類問(wèn)題，取得令人滿意的效果。

聚類算法描述如下：

步驟1：獲得初始類總數(shù)c，再利用K-均值聚類法獲得初始的聚類；

步驟2：用式■計(jì)算c個(gè)聚類中心ci，i=1，…，c，■；

步驟3：根據(jù)式■ （這里uij介于0，1間；ci為模糊組I的聚類中心，dij=||ci-xj||為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)點(diǎn)間的歐幾里德距離；且m∈[1， ∞）是一個(gè)加權(quán)指數(shù)。）計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)值函數(shù)值的改變量小于某個(gè)閥值，則算法停止。

步驟4：用■計(jì)算新的U矩陣。返回步驟2。

2) 分析對(duì)各類和用戶查詢請(qǐng)求之間的相關(guān)度，并根據(jù)相關(guān)度確定類排序。在確定了各個(gè)類之后需要計(jì)算類內(nèi)各結(jié)果與用戶興趣模型的相關(guān)度，并按相關(guān)度的大小對(duì)類內(nèi)的結(jié)果進(jìn)行排序。

3) 將相關(guān)度最大的類中的結(jié)果返回用戶。

5 結(jié)束語(yǔ)

文中介紹的帶有聚類功能的個(gè)性化元搜索引擎針對(duì)傳統(tǒng)搜索引擎的不足進(jìn)行了相應(yīng)的改進(jìn)，將聚類技術(shù)與智能技術(shù)應(yīng)用于元搜索引擎，不僅提高的搜索引擎的查準(zhǔn)率與查全率，而且根據(jù)用戶的興趣對(duì)返回的結(jié)果進(jìn)行個(gè)性化處理，提高了返回結(jié)果的準(zhǔn)確性和友好性。總之，該模型較好地考慮了用戶個(gè)性化，能挖掘用戶所想表達(dá)的查詢要求，具有一定的智能性。

該論文將繼續(xù)在用戶興趣模型與聚類算法的改進(jìn)方面作進(jìn)一步的研究，從而提高本系統(tǒng)的運(yùn)行效率。

參考文獻(xiàn)：

[1] 郭宏蕾.WWW信息智能檢索技術(shù)研究[J].北京航空航天大學(xué)博士后研究工作報(bào)，1999(5):12-16.

[2] 艾瑞市場(chǎng)咨詢[EB/OL].http://www.iresearch.com.cn/.

[3] 彭麗.原搜索引擎技術(shù)的研究與應(yīng)用[D].西安:西北工業(yè)大學(xué)，2007.

[4] 騰躍.基于用戶興趣的個(gè)性化 WEB檢索[D].北京:清華大學(xué)，2004.

[5] Keyhanipour A H，Moshiri B，Kazemian M，et al.Aggregation of web search engines based on users' preferences in WebFusion[J]. Knowledge-Based Systems，2007，20(4):321-328.