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

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

〔中圖分類號〕TP311 〔文獻標識碼〕A 〔文章編號〕1008-0821(2009)03-0176-03

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

1 基于遺傳算法的主題爬蟲

1.1 主題爬蟲的設(shè)計

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

1.2 遺傳算子設(shè)計

1.2.1 選擇操作

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

1.2.2 交叉操作

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

1.2.3 變異操作

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

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

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

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

F(x)3.0 標簽修飾

2.0 標簽修飾

1.8 標簽修飾

1.0 其它

2 信息處理

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

2.1 網(wǎng)頁凈化

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

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

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

2.2 分詞處理

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

2.3 特征項的提取與量化

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

3 查詢服務(wù)

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

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

4 實驗結(jié)果

4.1 性能測試

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

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

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

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

5 結(jié) 語

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

參考文獻

[1]朱煒，王超.Web超鏈分析算法研究[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)頁搜索系統(tǒng)[J].上海交通大學(xué)學(xué)報，2003，37(3):401-403.