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

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

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

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

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

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

1 搜索引擎的工作原理

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

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

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

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

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

2 啟發(fā)式搜索

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

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

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

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

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

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

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

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

2.2估價(jià)函數(shù)的設(shè)計(jì)

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

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

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

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

圖1 估價(jià)函數(shù)對(duì)頁(yè)面進(jìn)行判斷的流程圖

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

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

3.1Web文本的分類判斷

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

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

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

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

圖2 頁(yè)面判斷部分流程圖

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

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

頁(yè)面判斷算法的流程圖如圖2所示。

3.2閾值的確定

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

4 試驗(yàn)結(jié)果

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

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

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

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

5 結(jié) 論

由上述試驗(yàn)可知，對(duì)于相同的關(guān)鍵字和種子網(wǎng)站，傳統(tǒng)的搜索算法得到的相對(duì)回報(bào)率都相對(duì)較低，啟發(fā)式搜索算法可以得到相對(duì)較高的回報(bào)率。這是因?yàn)閱l(fā)式搜索算法依靠啟發(fā)信息，對(duì)于那些無(wú)關(guān)的頁(yè)面可以不去訪問(wèn)，從而減少了遍歷的頁(yè)面數(shù)。試驗(yàn)結(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]王士同.多因素問(wèn)題的啟發(fā)式搜索算法MFRA[J].計(jì)算機(jī)學(xué)報(bào)，2006,19(2):149～152.

[編輯] 易國(guó)華

TP391

A

1673-1409(2009)02-N063-03

2009-03-26

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