搜索引擎中智能代理技術(shù)及啟發(fā)式搜索策略研究

杜友福，程彩鳳，趙 鳴 (長江大學(xué)計算機科學(xué)學(xué)院，湖北 荊州 434023)

搜索引擎中智能代理技術(shù)及啟發(fā)式搜索策略研究

杜友福，程彩鳳，趙 鳴 (長江大學(xué)計算機科學(xué)學(xué)院，湖北 荊州 434023)

提出了啟發(fā)式搜索應(yīng)用于搜索引擎來獲取特定的信息的策略。通過引入智能代理系統(tǒng)，自動完成搜索到的頁面類型的判斷，更快更準(zhǔn)確地命中目標(biāo)網(wǎng)頁。試驗結(jié)果表明，引入智能代理后的啟發(fā)式搜索算法與傳統(tǒng)的深度優(yōu)先和寬度優(yōu)先算法相比，獲取信息的準(zhǔn)確性更高。

搜索引擎；啟發(fā)式搜索；智能代理；文本表示；估價函數(shù)

搜索引擎是以一定的策略在互聯(lián)網(wǎng)中搜集和發(fā)現(xiàn)信息，并對信息進行理解、提取、組織和處理，最終為用戶提供檢索服務(wù)，從而達到信息導(dǎo)航的目的。搜索引擎中的網(wǎng)絡(luò)蜘蛛程序是依靠一定的算法來遍歷Internet中的網(wǎng)頁，抽取相關(guān)信息，最后將其保存在數(shù)據(jù)庫中。依靠網(wǎng)絡(luò)蜘蛛，搜索引擎才能獲取足夠的信息供用戶檢索和查找。由于網(wǎng)絡(luò)中信息分布的不確定性導(dǎo)致了信息收集的盲目性，從而使得使用傳統(tǒng)的寬度和深度優(yōu)先搜索算法的網(wǎng)絡(luò)蜘蛛程序在特定信息資源獲取上效率和效果都不甚理想。筆者將啟發(fā)式搜索和智能代理技術(shù)引入到搜索引擎中，依靠啟發(fā)信息，可以避免遍歷過多的無用鏈接，提高網(wǎng)絡(luò)蜘蛛類程序的效率和信息獲取的準(zhǔn)確度。

1 搜索引擎的工作原理

搜索引擎的原理[1]可以分為以下4步：

1)從互聯(lián)網(wǎng)上抓取網(wǎng)頁 利用能夠從互聯(lián)網(wǎng)上自動收集網(wǎng)頁的網(wǎng)絡(luò)蜘蛛程序，自動訪問互聯(lián)網(wǎng)，并沿著任何網(wǎng)頁中的所有URL爬到其他網(wǎng)頁，重復(fù)這過程，并把爬過的所有網(wǎng)頁收集到服務(wù)器中。

2)建立索引數(shù)據(jù)庫 由索引系統(tǒng)程序?qū)κ占貋淼木W(wǎng)頁進行分析，提取相關(guān)網(wǎng)頁信息，根據(jù)一定的相關(guān)度算法進行大量復(fù)雜計算，得到每一個網(wǎng)頁針對頁面內(nèi)容中及超鏈中每一個關(guān)鍵詞的相關(guān)度(或重要性)，然后用這些相關(guān)信息建立網(wǎng)頁索引數(shù)據(jù)庫。

3)在索引數(shù)據(jù)庫中搜索 當(dāng)用戶輸入關(guān)鍵詞搜索后，分解搜索請求，由搜索系統(tǒng)程序從網(wǎng)頁索引數(shù)據(jù)庫中找到符合該關(guān)鍵詞的所有相關(guān)網(wǎng)頁。

4)對搜索結(jié)果進行處理排序 所有相關(guān)網(wǎng)頁針對該關(guān)鍵詞的相關(guān)信息在索引庫中都有記錄，只需綜合相關(guān)信息和網(wǎng)頁級別形成相關(guān)度數(shù)值，然后進行排序，相關(guān)度越高，排名越靠前。最后由頁面生成系統(tǒng)將搜索結(jié)果的鏈接地址和頁面內(nèi)容摘要等內(nèi)容組織起來返回給用戶。

2 啟發(fā)式搜索

2.1啟發(fā)式搜索過程

啟發(fā)式搜索基本過程如下[2]:

1) 給定初始狀態(tài)S,產(chǎn)生一個狀態(tài)的有限描述。

2) 使用發(fā)生函數(shù)Q(x)對S產(chǎn)生其后的每個后續(xù)狀態(tài)。

3) 對產(chǎn)生的狀態(tài)檢查,有無目標(biāo)狀態(tài)G,如果有則搜索成功。

4) 如果目標(biāo)狀態(tài)G沒有出現(xiàn),就用估價函數(shù)f(x)對這些節(jié)點進行評估,選擇最有希望的節(jié)點,繼續(xù)使用Q(x)產(chǎn)生它的子節(jié)點,重復(fù)步驟3)。

5) 如果所有可能的節(jié)點都使用Q(x)拓展過,目標(biāo)狀態(tài)G還是沒出現(xiàn),則搜索失敗。

以上搜索步驟可以應(yīng)用于任何狀態(tài)空間問題的搜索。智能啟發(fā)式搜索區(qū)別于其他搜索的主要特點是估價函數(shù)f(x)的設(shè)計。

2.2估價函數(shù)的設(shè)計

估價函數(shù)的作用是估計Open表(Open表保存所有已經(jīng)生成而未擴展的節(jié)點)中每個狀態(tài)的估價函數(shù)值,按照值的大小重新排序。設(shè)計估計函數(shù)要考慮兩方面內(nèi)容，即已經(jīng)付出的代價和將要付出的代價。一般把估價函數(shù)f(x)定義為初始節(jié)點經(jīng)過n節(jié)點到達目標(biāo)節(jié)點的最小代價路徑的代價估計值。其一般形式[3]為:

f(n)=g(n)+h(n)

式中，g(n)是從初始點S到n的實際代價,而h(n)是從n到目標(biāo)節(jié)點G的最佳路徑的估計代價。對網(wǎng)站類型進行判斷中，需要設(shè)計一張門戶網(wǎng)站網(wǎng)址列表，所要判斷的網(wǎng)址都要對該列表進行比對。如果屬于該列表則可認(rèn)為是門戶網(wǎng)站，否則認(rèn)為是一般網(wǎng)站?？紤]Web頁面中鏈接的特點，在估價函數(shù)中必須要對鏈接文本的信息和鏈接本身的信息作出判斷。因此必須建立一個相關(guān)的知識庫，在試驗中以保存在文本中的關(guān)鍵字來表示，這些知識庫為蜘蛛程序提供了對鏈接判斷的依據(jù)。

因此，估價函數(shù)主要是對鏈接進行判斷，當(dāng)獲取一個URL后，估價函數(shù)對其進行判斷，如果為門戶型網(wǎng)站則獲取其站內(nèi)鏈接，對這些鏈接進行判斷，是否含有關(guān)鍵字表中所列的關(guān)鍵字，如果有則對該URL的估價值加20,沒有則返回。如果該鏈接是一般的主題網(wǎng)站網(wǎng)址，則獲取其外部鏈接，如果這些鏈接中含有關(guān)鍵字，則該鏈接的估價值加10。站內(nèi)的鏈接估價值要比外部的高，因為這樣可以使該站有價值的頁面盡快被訪問，而不需要等以后訪問其他網(wǎng)頁后重新訪問，可以減少客戶和服務(wù)器重新鏈接帶來的開銷。具體流程圖如圖1所示。

圖1 估價函數(shù)對頁面進行判斷的流程圖

3 智能代理技術(shù)的引入

把智能代理技術(shù)應(yīng)用到搜索引擎中，讓其自動完成文檔的分類或者判斷其所屬類型，能夠判斷該頁面是否屬于所需要的網(wǎng)頁。

3.1Web文本的分類判斷

假設(shè)給出各關(guān)鍵字的詞頻，構(gòu)成一個文本向量，用文本文件存放。對文本的分類可以按以下2種情況來判斷[4]。

1)根據(jù)鏈接的html網(wǎng)頁的title和meta屬性 這兩者往往能提供一些網(wǎng)頁的類別信息。如果title或meta包含關(guān)鍵字表中的關(guān)鍵字，那么可以認(rèn)為是所需要的網(wǎng)頁。但是關(guān)鍵字出現(xiàn)在title屬性和meta屬性中所表示的網(wǎng)頁權(quán)重不同。關(guān)鍵字如果出現(xiàn)在title中，則網(wǎng)頁的權(quán)重就高些，這里假設(shè)其系數(shù)是3，關(guān)鍵字如果出現(xiàn)在meta中，則網(wǎng)頁的權(quán)重系數(shù)為2。

2)根據(jù)頁面內(nèi)容的文本信息 采用最簡單的向量分類算法。該方法的思路為：首先對較多的樣本進行分析抽取一個具有代表性的向量作為中心向量，然后計算中心向量與新向量的相似度。相似度一般用兩者向量的夾角表示，夾角越小，表示相似度越高。根據(jù)計算的結(jié)果，與閾值進行比較，判斷是否屬于需要的網(wǎng)頁類別。

相似度sim(d1，d2)用于度量2個文檔d1和d2之間的內(nèi)容相關(guān)程度[5]。當(dāng)文檔被表示為文檔空間的向量，就可以利用向量之間的距離計算公式來表示文檔間的相似度。常用的向量距離度量方法有歐氏距離、內(nèi)積距離和余弦距離。筆者采用的是余弦距離，其公式為：

圖2 頁面判斷部分流程圖

式中，di為新文本的特征向量；dj為中心向量；n為特征向量的維數(shù);ωk為向量的第k維。

假定如果關(guān)鍵字出現(xiàn)在文本內(nèi)容中，則其權(quán)重系數(shù)為1。中心向量為關(guān)鍵字的權(quán)重。結(jié)合這2種情況，分別計算各相似度，最后求其加權(quán)平均值，然后與閾值進行比較，滿足要求的就是所需要的頁面。

頁面判斷算法的流程圖如圖2所示。

3.2閾值的確定

在所有的數(shù)據(jù)挖掘算法中，閾值一般根據(jù)經(jīng)驗預(yù)設(shè)初始值。初始值的確定也很不容易，應(yīng)當(dāng)首先根據(jù)經(jīng)驗和簡單的測試而定，然后不斷的調(diào)整，使閾值落在一個比較合理的范圍內(nèi)[6]。在該試驗中，最后給定閾值初始值為0.6。

4 試驗結(jié)果

用啟發(fā)式搜索和智能代理技術(shù)的搜索算法(簡稱啟發(fā)式搜索算法)，在Windows環(huán)境下的試驗結(jié)果與傳統(tǒng)的深度優(yōu)先和寬度優(yōu)先算法相比，獲取信息的準(zhǔn)確性有很大的提高。筆者用相對回報率來評價搜索引擎中資源獲取的性能。相對回報率的公式如下:

設(shè)種子網(wǎng)站為4個，關(guān)鍵字表為有關(guān)“人工智能”的內(nèi)容，共有18個關(guān)鍵字。試驗結(jié)果如表1和表2所示。

表1 啟發(fā)式搜索算法試驗結(jié)果表

表2 寬度優(yōu)先搜索算法實驗結(jié)果表

5 結(jié) 論

由上述試驗可知，對于相同的關(guān)鍵字和種子網(wǎng)站，傳統(tǒng)的搜索算法得到的相對回報率都相對較低，啟發(fā)式搜索算法可以得到相對較高的回報率。這是因為啟發(fā)式搜索算法依靠啟發(fā)信息，對于那些無關(guān)的頁面可以不去訪問，從而減少了遍歷的頁面數(shù)。試驗結(jié)果證明啟發(fā)式搜索策略和智能代理技術(shù)結(jié)合能極大提高搜索的效率。

[1]徐寶文，張衛(wèi)豐. 搜索引擎與信息獲取技術(shù)[M].清華大學(xué)出版社，2003.

[2]蔡自興，徐光裕.人工智能及其應(yīng)用[M]. 第2版.北京:清華大學(xué)出版社，2005. 135～138.

[3]Nilson N J.Principles of Artificial Intelligence[M].Tioga Publishing Co.,2006. 258～259.

[4]Pearl J Heuristics.Intelligent Search Strategies for Computer Problem Solving[M].AddisonWesley Publishing Company, 2007. 368～339.

[5]Pearl J.Some recent results in heuristic search theory[J].IEEE Trans，2004,PAMI-6(1):1～12.

[6]王士同.多因素問題的啟發(fā)式搜索算法MFRA[J].計算機學(xué)報，2006,19(2):149～152.

[編輯] 易國華

TP391

A

1673-1409(2009)02-N063-03

2009-03-26

杜友福(1961-)，男， 1982年大學(xué)畢業(yè)，教授，現(xiàn)主要從事人工智能技術(shù)和數(shù)據(jù)庫技術(shù)方面的教學(xué)與研究工作。