基于遺傳算法的主題信息搜索系統(tǒng)研究

〔摘 要〕針對(duì)網(wǎng)絡(luò)信息資源“迷向”與“過(guò)載”的現(xiàn)象，本文通過(guò)對(duì)遺傳算法的分析應(yīng)用，構(gòu)建了由基于遺傳算法的主題爬蟲(chóng)、信息處理和查詢服務(wù)三部分組成的主題信息搜索系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，應(yīng)用該系統(tǒng)可以獲取與主題相關(guān)度高的網(wǎng)頁(yè)信息。

〔關(guān)鍵詞〕主題；遺傳算法；爬蟲(chóng)；搜索系統(tǒng)

〔中圖分類(lèi)號(hào)〕TP311 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕1008-0821(2009)03-0176-03

隨著農(nóng)業(yè)信息化工作的開(kāi)展，我國(guó)建設(shè)了大量的農(nóng)業(yè)信息網(wǎng)站。鑒于大部分農(nóng)民的科技素質(zhì)，面對(duì)大量的農(nóng)業(yè)網(wǎng)絡(luò)信息，農(nóng)業(yè)信息化工作中出現(xiàn)了信息資源“迷向”與“過(guò)載”的現(xiàn)象。目前的搜索引擎大多數(shù)是綜合性搜索引擎，隨著信息多元化的增長(zhǎng)，對(duì)于特定的信息查詢，綜合性搜索引擎的召回率和精確率都不能滿足用戶的查詢需求。因此，有選擇性的抓取與農(nóng)業(yè)主題相關(guān)的網(wǎng)頁(yè)，并建立農(nóng)業(yè)主題信息搜索系統(tǒng)，為用戶提供相關(guān)領(lǐng)域準(zhǔn)確全面的信息就尤為重要。遺傳算法是一種模擬生物在自然環(huán)境中遺傳和進(jìn)化過(guò)程而形成的自適應(yīng)全局優(yōu)化概率搜索算法，在復(fù)雜函數(shù)優(yōu)化、生產(chǎn)調(diào)度及機(jī)器學(xué)習(xí)等眾多領(lǐng)域都獲得了成功的應(yīng)用。本文通過(guò)對(duì)遺傳算法的分析應(yīng)用，由基于遺傳算法的主題爬蟲(chóng)、信息處理和查詢服務(wù)三部分構(gòu)建了主題信息搜索系統(tǒng)，以提高相關(guān)網(wǎng)頁(yè)信息搜索的準(zhǔn)確率。

1 基于遺傳算法的主題爬蟲(chóng)

1.1 主題爬蟲(chóng)的設(shè)計(jì)

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它簡(jiǎn)單、魯棒性好，具有自組織性、自適應(yīng)性、自學(xué)習(xí)性。遺傳算法具有內(nèi)在啟發(fā)式隨機(jī)搜索特性，可指導(dǎo)主題爬蟲(chóng)在采用一定的適應(yīng)度函數(shù)評(píng)估個(gè)體的情況下，能采用概率的變遷規(guī)則來(lái)指導(dǎo)它的搜索方向；它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。結(jié)合遺傳算法的特點(diǎn)，通過(guò)對(duì)網(wǎng)頁(yè)特性的分析[1，3]，基于遺傳算法的主題爬蟲(chóng)在普通主題爬蟲(chóng)基礎(chǔ)上通過(guò)如下擴(kuò)充實(shí)現(xiàn):通過(guò)選擇操作，選出適應(yīng)度高的個(gè)體(URL)作為下一代的種子，縮小新種子數(shù)量，加快抓取網(wǎng)頁(yè)速度；通過(guò)變異操作，擴(kuò)大搜索范圍(URL集)。在網(wǎng)頁(yè)處理過(guò)程中增加選擇操作，在每代種子挑選過(guò)程中增加變異和交叉操作，以此來(lái)優(yōu)化種子集合，其流程如圖1所示。

1.2 遺傳算子設(shè)計(jì)

1.2.1 選擇操作

選擇操作定義:設(shè)種子集合為S，抓取集合S中第i個(gè)URL對(duì)應(yīng)的網(wǎng)頁(yè)信息，計(jì)算該網(wǎng)頁(yè)的主題相關(guān)度r，當(dāng)主題相關(guān)度r≥r0(r0是根據(jù)需要設(shè)定值，通常在0和1之間)時(shí)，則將該網(wǎng)頁(yè)信息保存到數(shù)據(jù)庫(kù)中，否則丟棄該頁(yè)面，同時(shí)將該網(wǎng)頁(yè)對(duì)應(yīng)的URL插入到丟棄隊(duì)列中。

1.2.2 交叉操作

交叉操作定義:解析出第i代種子主題相關(guān)度高的網(wǎng)頁(yè)包含的鏈接和鏈接提示信息(主要指之間的信息)，并計(jì)算所有鏈接提示信息與主題的主題相關(guān)度，假設(shè)總共有m個(gè)鏈接，每個(gè)鏈接對(duì)應(yīng)的鏈接提示信息的主題相關(guān)度為ri(i=1，2，……，m)，第i個(gè)鏈接對(duì)應(yīng)的網(wǎng)頁(yè)的主題相關(guān)度為r1i，則可以預(yù)測(cè)第i個(gè)鏈接對(duì)應(yīng)網(wǎng)頁(yè)的主題相關(guān)度為r2i=r1i+k*ri(其中k是參數(shù))，并按照主題相關(guān)度r2i進(jìn)行降序排序。設(shè)交叉概率為Pc，則選出前m*Pc個(gè)URL作為交叉結(jié)果，記為S1。

1.2.3 變異操作

變異操作定義:假設(shè)種子集合有m個(gè)URL，由選擇操作可知當(dāng)前網(wǎng)頁(yè)的主題相關(guān)度rwi(i=1，2，……，m)，按照主題相關(guān)度rwi進(jìn)行降序排序。設(shè)變異概率為Pm，則選出前m*Pm個(gè)URL進(jìn)行變異，得到集合記為S2。令S=S1∪S2，則將S集合中對(duì)應(yīng)的URL作為下一代的種子。

2009年3月第29卷第3期現(xiàn)?代?情?報(bào)Journal of Modern InformationMar.2009Vol.29 No.32009年3月第29卷第3期基于遺傳算法的主題信息搜索系統(tǒng)研究Mar.2009Vol.29 No.31.3 主題相關(guān)度計(jì)算

為了保證主題爬蟲(chóng)抓取的網(wǎng)頁(yè)能夠盡量與主題相關(guān)，必須對(duì)網(wǎng)頁(yè)進(jìn)行過(guò)濾，這里采用主題相關(guān)度的計(jì)算來(lái)決定網(wǎng)頁(yè)的主題相關(guān)與否。主題相關(guān)度的計(jì)算采用向量空間模型算法，把關(guān)鍵字的個(gè)數(shù)n作為向量空間的維數(shù)，每個(gè)關(guān)鍵字的權(quán)值wi作為每一維分量的大小，則主題向量可表示為α=(α1，α2，……，αn)，其中αi=wi，i=(1，2，3 ……，n)。對(duì)網(wǎng)頁(yè)進(jìn)行中文分詞處理，統(tǒng)計(jì)關(guān)鍵詞出現(xiàn)的頻率，并求出頻率之比，以出現(xiàn)頻率最高的關(guān)鍵詞作為基準(zhǔn)，其頻率用1表示，通過(guò)頻率比求出其它關(guān)鍵詞的頻率xi，則該頁(yè)面對(duì)應(yīng)向量的每一維分量為xiwi，頁(yè)面的主題用向量表示為β=(x1w1，x2w2，……，xiwi……，xnwn)，i=1，2，……，n。考慮到網(wǎng)頁(yè)是一種半結(jié)構(gòu)化的文本，充分利用其中的HTML標(biāo)記，可以更準(zhǔn)確地抽取出文檔主題[4]。設(shè)F(x)代表第x關(guān)鍵字應(yīng)賦予的權(quán)重，則主題相關(guān)度的計(jì)算公式為:

其中函數(shù)F(i)取值如下式:

F(x)3.0 標(biāo)簽修飾

2.0 標(biāo)簽修飾

1.8 標(biāo)簽修飾

1.0 其它

2 信息處理

為提高主題信息搜索結(jié)果的相關(guān)性和速度，需要對(duì)搜索的網(wǎng)頁(yè)進(jìn)行處理。處理包括:

2.1 網(wǎng)頁(yè)凈化

(1)提取網(wǎng)頁(yè)title和body標(biāo)簽中包含的內(nèi)容。最重要的信息一般是存儲(chǔ)在這里，但是也需要考慮到網(wǎng)頁(yè)制作者不規(guī)范的用法，做到系統(tǒng)的健壯性。

(2)去掉影響執(zhí)行效率，且無(wú)用的標(biāo)簽以及中間的內(nèi)容。比如，，等，這部分的識(shí)別，建立在大量的調(diào)試和對(duì)網(wǎng)頁(yè)標(biāo)簽結(jié)構(gòu)詳細(xì)了解的基礎(chǔ)上。通過(guò)這些標(biāo)簽的識(shí)別，基本能夠如實(shí)反應(yīng)原網(wǎng)頁(yè)內(nèi)容。

(3)將常見(jiàn)的網(wǎng)頁(yè)中的轉(zhuǎn)義字符轉(zhuǎn)化為通用字符的形式，便于最后網(wǎng)頁(yè)特征項(xiàng)提取。

2.2 分詞處理

為了使大量的搜索關(guān)鍵字都能有返回結(jié)果，同時(shí)又能體現(xiàn)主題搜索引擎的思想，在分詞過(guò)程中將中文詞典和主題詞集相結(jié)合進(jìn)行分詞。即以中文詞典為主進(jìn)行詞的切分，將中文詞典和主題詞集重復(fù)的關(guān)鍵字的權(quán)重加起來(lái)，得到新的權(quán)重。

2.3 特征項(xiàng)的提取與量化

本研究采用主題詞集來(lái)確立主題，其中每個(gè)主題詞擁有指定的不同權(quán)值。權(quán)值的設(shè)置采用手工設(shè)置和特征提取相結(jié)合的方法。手工設(shè)置的好處是實(shí)現(xiàn)簡(jiǎn)單，同時(shí)人的經(jīng)驗(yàn)一般比較準(zhǔn)確，跟實(shí)際情況不會(huì)出現(xiàn)大的偏差，缺點(diǎn)是可能有缺漏，權(quán)值的量化定義不夠精確。特征提取是指給定一個(gè)跟主題有關(guān)的網(wǎng)頁(yè)集合，由程序自動(dòng)提取這些網(wǎng)頁(yè)里面共同的特征，并根據(jù)頻率確定權(quán)值。特征提取的優(yōu)點(diǎn)是權(quán)值量化定義精確，但要求選取用來(lái)提取特征的網(wǎng)頁(yè)集合必須是很有代表性和全面概括性的，否則就可能出現(xiàn)很大的偏差。最佳的方法是綜合二者的優(yōu)點(diǎn)。

3 查詢服務(wù)

查詢服務(wù)用于和用戶交互，包括響應(yīng)用戶的查詢檢索和記錄用戶的行為。查詢服務(wù)主要包括:從用戶獲得用戶的查詢請(qǐng)求，提交給“查詢服務(wù)程序”；“查詢服務(wù)程序”檢索索引詞表和倒排表，產(chǎn)生排序結(jié)果按照一定的輸出格式顯示給用戶；記錄日志，包括用戶查詢短語(yǔ)和查詢時(shí)間等個(gè)性化信息，其中最主要的是根據(jù)查詢請(qǐng)求對(duì)網(wǎng)頁(yè)相關(guān)性進(jìn)行排序。Web上網(wǎng)頁(yè)的質(zhì)量參差不齊，大量的網(wǎng)頁(yè)組織性、結(jié)構(gòu)性比較差；同時(shí)，大部分檢索用戶經(jīng)常只輸入一個(gè)或者兩個(gè)檢索詞來(lái)檢索他們需要的網(wǎng)頁(yè)，對(duì)此本文結(jié)合主題搜索引擎的特點(diǎn)和PageRank技術(shù)，提出一種網(wǎng)頁(yè)排序算法，如下式:

其中，T為計(jì)算中的頁(yè)面總量，γ<1是阻尼常數(shù)因子，in(p)為所有指向p的頁(yè)面的集合，out(r)為頁(yè)面出鏈的集合，β為集合out(r)中每個(gè)頁(yè)面的主題相關(guān)度。

4 實(shí)驗(yàn)結(jié)果

4.1 性能測(cè)試

系統(tǒng)以C++語(yǔ)言實(shí)現(xiàn)，操作系統(tǒng)為Windows server 2000，關(guān)系數(shù)據(jù)庫(kù)為SQL server 2000，CPU 為P4 3.0G，硬盤(pán)為160G，通過(guò)10/100M以太網(wǎng)卡接入因特網(wǎng)。通過(guò)通用搜索引擎獲得可能相關(guān)的URL，除去重復(fù)的URL，然后在領(lǐng)域?qū)＜业闹笇?dǎo)下進(jìn)行人工篩選，選出與主題相關(guān)的URL作為種子集合。在主題信息獲取系統(tǒng)中下載的web信息內(nèi)容包括網(wǎng)頁(yè)地址、網(wǎng)頁(yè)標(biāo)題、網(wǎng)頁(yè)內(nèi)容、網(wǎng)頁(yè)正文、網(wǎng)頁(yè)等級(jí)、網(wǎng)頁(yè)下載時(shí)間、網(wǎng)頁(yè)的相對(duì)深度、是否包含圖片、網(wǎng)頁(yè)大小、網(wǎng)頁(yè)主題相關(guān)度、鏈接url、網(wǎng)頁(yè)等級(jí)、鏈接提示信息等。在主題信息獲取系統(tǒng)中設(shè)計(jì)的數(shù)據(jù)庫(kù)表包括中文詞庫(kù)表、初始種子表、網(wǎng)頁(yè)信息存儲(chǔ)表、鏈接信息表、主題詞表、測(cè)試表等。

為對(duì)本主題信息獲取系統(tǒng)的性能進(jìn)行驗(yàn)證，用廣度優(yōu)先搜索策略(BFS)及最佳搜索策略(OPS)和本文基于遺傳算法的搜索策略(GA)，在抓取的網(wǎng)頁(yè)數(shù)據(jù)質(zhì)量方面進(jìn)行了比較。測(cè)試結(jié)果如圖2所示，基于遺傳算法的搜索策略GA在抓取網(wǎng)頁(yè)時(shí)，抓取到的主題相關(guān)網(wǎng)頁(yè)數(shù)量明顯高于其它兩種搜索策略。這是因?yàn)镚A算法引入交叉操作，根據(jù)鏈接提示信息預(yù)測(cè)所鏈接網(wǎng)頁(yè)的主題相關(guān)度，減少抓取不相關(guān)網(wǎng)頁(yè)的可能性，提高主題爬蟲(chóng)的爬行效率；同時(shí)在URL選擇過(guò)程中引入變異操作，增加新的URL，一定程度上克服了主題爬蟲(chóng)局部搜索的局限性結(jié)果。

4.2 系統(tǒng)應(yīng)用

以花卉主題搜索為例設(shè)計(jì)了主題信息搜索系統(tǒng)。如圖3所示。系統(tǒng)界面設(shè)計(jì)遵照簡(jiǎn)單、清晰的原則。用戶通過(guò)此搜索界面輸入“一串紅”的搜索內(nèi)容時(shí)，結(jié)果如圖4所示。

5 結(jié) 語(yǔ)

本文構(gòu)建的基于遺傳算法的主題信息搜索系統(tǒng)，可以在一定程度上提高獲取相關(guān)主題信息的準(zhǔn)確率，系統(tǒng)的應(yīng)用對(duì)于解決農(nóng)業(yè)網(wǎng)絡(luò)信息資源“迷向”與“過(guò)載”的現(xiàn)象有一定促進(jìn)作用。如何通過(guò)擴(kuò)充、改進(jìn)系統(tǒng)功能，如何引入語(yǔ)義分析等以進(jìn)一步提高主題信息獲取系統(tǒng)的準(zhǔn)確率，仍需要進(jìn)一步研究。

參考文獻(xiàn)

[1]朱煒，王超.Web超鏈分析算法研究[J].計(jì)算機(jī)科學(xué)，2003，30(9):89-92.

[2]DeBra P，Houben G，Kornatzky Y，et al.Information Retrieval in Distributed Hypertexts.Proc 4th RIAO Conference.New York:Computer-assisted Information Retrieval，1994:481-491.

[3]Herseovici M，Jacov M，Yoelle S Marek.The Shark-Search Algorithm-An Application:Tailored Web Site Mapping.Computer Networks and ISDN Systems，1998，30:317-326.

[4]宋聚平，王永成，尹中航，等.面向主題的網(wǎng)頁(yè)搜索系統(tǒng)[J].上海交通大學(xué)學(xué)報(bào)，2003，37(3):401-403.