杜 晶，陳 群，劉海龍

(西北工業(yè)大學(xué)計算機(jī)學(xué)院，陜西 西安 710129)

0 引言

隨著信息技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)上的數(shù)據(jù)量與日俱增，其蘊(yùn)含的大量有價值的信息引起人們的關(guān)注和重視。越來越多的應(yīng)用通過Web來獲取正確的信息。問答系統(tǒng)通過Web獲取問題的正確答案［1］，數(shù)據(jù)修復(fù)系統(tǒng)通過Web獲取錯誤或缺失數(shù)據(jù)的正確值。相較于傳統(tǒng)的基于統(tǒng)計的數(shù)據(jù)修復(fù)方法［2］，基于Web的實現(xiàn)方法不依賴數(shù)據(jù)約束條件且可以獲得更準(zhǔn)確的結(jié)果。然而，要想在Web巨大的信息量中獲取所需的正確信息，通過已知的數(shù)據(jù)形成有效的查詢關(guān)鍵詞是一個關(guān)鍵因素，不合適的查詢關(guān)鍵詞會導(dǎo)致所需的信息在搜索結(jié)果中排名低或不存在，進(jìn)而影響整個系統(tǒng)無法提取出所需要的結(jié)果。

目前問答系統(tǒng)通過分析問題的詞法、語法和語義信息來構(gòu)造查詢關(guān)鍵詞［1，3］，但是這種方法并不適用于所有場合，在數(shù)據(jù)修復(fù)系統(tǒng)中無法采用這種方法對關(guān)系數(shù)據(jù)中的錯誤或缺失數(shù)據(jù)構(gòu)造查詢關(guān)鍵詞。針對這種情況，需要選擇與缺失屬性強(qiáng)相關(guān)的數(shù)據(jù)屬性子集為錯誤或者缺失數(shù)據(jù)構(gòu)造查詢關(guān)鍵詞，使得搜索引擎能從Web上返回其正確值。對于屬性的選擇，可以抽象為組合優(yōu)化的NP難問題。如果人工選擇［4］，不能實現(xiàn)自動化，也不能確保形成查詢的有效性。如果窮舉搜索空間來選取最優(yōu)信息，也不合適，因為總的搜索空間與屬性個數(shù)呈指數(shù)增長，導(dǎo)致構(gòu)造查詢關(guān)鍵詞的時間復(fù)雜度亦隨屬性個數(shù)呈指數(shù)增長，顯然，這樣的效率在實際應(yīng)用中是不能讓人滿意的。

針對以上問題，本文提出一種基于遺傳算法［5］的查詢關(guān)鍵詞自動構(gòu)造方法，通過在訓(xùn)練集上應(yīng)用遺傳算法，學(xué)習(xí)到與目標(biāo)屬性強(qiáng)相關(guān)的屬性子集，為其構(gòu)造查詢關(guān)鍵詞，可以大大減少搜索空間，并得到比較滿意的結(jié)果。

1 問題概述

針對離散的關(guān)系數(shù)據(jù)，在利用Web獲取知識時，如何在已知屬性集中選擇與目標(biāo)屬性強(qiáng)相關(guān)的屬性子集來構(gòu)造查詢關(guān)鍵詞是解決問題的關(guān)鍵所在。

用 R(A1，A2，...，An)表示關(guān)系 R，其有 n 個屬性(A1，A2，...，An)，D 為 R 的一個實例，ri表示 D 的第i個元組，rij表示元組ri的Aj屬性的屬性值。假設(shè)元組ri某個屬性Aj有錯值或缺值，此時需要利用Web獲取其正確值，稱ri為目標(biāo)元組，Aj為目標(biāo)屬性，其他屬性為已知屬性。則問題歸結(jié)為從ri的已知屬性集中選擇與Aj強(qiáng)相關(guān)的屬性子集，為rij構(gòu)造查詢關(guān)鍵詞，使得Web返回的搜索結(jié)果盡可能多地包含rij的正確值。

由于構(gòu)造查詢關(guān)鍵詞的目的是為了能在Web上獲取準(zhǔn)確的目標(biāo)值，因此對于構(gòu)造的查詢關(guān)鍵詞，優(yōu)化目標(biāo)為以下兩方面:

(1)支持度。構(gòu)造的查詢關(guān)鍵詞，能夠使得盡可能多的訓(xùn)練樣例在搜索引擎返回結(jié)果中都找到對應(yīng)目標(biāo)屬性的正確值。

(2)查準(zhǔn)率。構(gòu)造的查詢關(guān)鍵詞，對于每個訓(xùn)練樣例，其目標(biāo)屬性的正確值在搜索引擎返回結(jié)果中出現(xiàn)的次數(shù)盡可能多。

其中支持度是前提，查詢關(guān)鍵詞的選取應(yīng)在支持度得到較好滿足的前提下，選擇查準(zhǔn)率也較高的屬性子集，因為只有在支持度得到較好滿足時，才能保證訓(xùn)練得到的查詢關(guān)鍵詞對于測試集同樣有效。在此基礎(chǔ)上，查準(zhǔn)率越高，返回結(jié)果中目標(biāo)屬性的正確值出現(xiàn)次數(shù)越多，越容易將其從返回結(jié)果中抽取出來。

2 基于遺傳算法的查詢關(guān)鍵詞形成方法(GQFA)

2.1 遺傳算法概述

遺傳算法是一種模擬生物進(jìn)化的隨機(jī)搜索與優(yōu)化算法，可以在線性的時間內(nèi)使用進(jìn)化的原理從較大的搜索空間中獲得一個可行解。它是一種迭代算法，迭代是從隨機(jī)生成的初始群體開始的，通過不斷地執(zhí)行遺傳操作來生成下一代群體。每一次迭代，都將根據(jù)適應(yīng)度函數(shù)來評估群體中的成員，而后通過概率方法選出適應(yīng)度高的成員作為產(chǎn)生下一代的種子，這一過程不斷重復(fù)，直到找到具有理想適應(yīng)度的成員為止［1］。遺傳算法的設(shè)計中，關(guān)鍵在于編碼、適應(yīng)度和遺傳操作的設(shè)計。

2.2 GQFA 算法

GQFA算法首先選擇數(shù)據(jù)集中完整正確的元組作為訓(xùn)練集，利用遺傳算法作為學(xué)習(xí)方法，得到針對于某一目標(biāo)屬性強(qiáng)相關(guān)的屬性子集，然后針對目標(biāo)元組構(gòu)造查詢關(guān)鍵詞。其中采用的查詢關(guān)鍵詞的構(gòu)造策略是元組目標(biāo)屬性的屬性名加上訓(xùn)練得到的強(qiáng)相關(guān)屬性子集的屬性值作為查詢關(guān)鍵詞，如對于錯值或缺值rij，如果遺傳算法選取的已知屬性子集為(A1，A2)，那么其查詢關(guān)鍵詞為:

2.2.1 GQFA編碼方式和初始種群生成

在應(yīng)用算法之前，需要針對問題設(shè)計染色體，即，將搜索空間的可行解以編碼的方式呈現(xiàn)出來。在GQFA中，一個個體的編碼用于表示構(gòu)造查詢時一種可能選取的屬性子集。在編碼方案上，采用經(jīng)典的二進(jìn)制位串編碼方案。一個二進(jìn)制位串表示搜索空間中的一個可能解，每一位代表數(shù)據(jù)集中的一個屬性，為0代表不選擇此屬性，為1代表選擇此屬性，二進(jìn)制位串的長度等于已知屬性的個數(shù)。例如，對于5個屬性的數(shù)據(jù)集Book(ISBN，Title，Author，Publication Year，Publisher)，如果某個元組的Author值有錯誤或缺失，其他值已知，那么一個可能解為一個長度為4的二進(jìn)制位串，如1100，則表示選取的屬性子集為(ISBN，Title)，那么針對此元組構(gòu)成的查詢?yōu)?Author+此元組ISBN屬性值+此元組Title屬性值。這種編碼方案實現(xiàn)簡單，易于操作。

初始種群是遺傳操作開始的起點(diǎn)，GQFA算法采用隨機(jī)生成的方法，對于種群中每個個體，隨機(jī)生成0、1組合的二進(jìn)制位串表示選擇的屬性子集。

2.2.2 GQFA 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評價假設(shè)好壞的標(biāo)準(zhǔn)，整個算法的迭代優(yōu)化是在適應(yīng)度函數(shù)的引導(dǎo)下進(jìn)行的，適應(yīng)度函數(shù)的好壞直接決定了最終選取的成員的優(yōu)劣程度。根據(jù)以上分析所得的優(yōu)化目標(biāo)，這里適應(yīng)度函數(shù)主要由以下公式計算:

其中S為訓(xùn)練樣例對查詢關(guān)鍵詞的支持度，P為查詢關(guān)鍵詞對于訓(xùn)練樣例的平均查準(zhǔn)率，α、β為比例系數(shù)，且α+β=1。

(1)訓(xùn)練樣例對查詢關(guān)鍵詞的支持度S。

一個訓(xùn)練樣例I支持對應(yīng)于它的查詢關(guān)鍵詞Q(I)，則表示Q(I)返回的查詢結(jié)果中能夠抽取出I中目標(biāo)屬性的正確值［7］，采用的抽取方法是自然語言處理技術(shù)［8］和命名實體識別技術(shù)［9］。

其中N為選取的訓(xùn)練樣例的個數(shù)，|Support|為訓(xùn)練樣例中支持其相應(yīng)查詢關(guān)鍵詞的個數(shù)。

支持度越高，說明越多的訓(xùn)練樣例可由學(xué)習(xí)得到的屬性子集構(gòu)造的查詢關(guān)鍵詞找到正確的目標(biāo)屬性值，那么對于有錯值或缺值的元組即目標(biāo)元組，即測試集，由這種方式構(gòu)造的查詢關(guān)鍵詞找到其目標(biāo)屬性值的概率就越大。

(2)查詢關(guān)鍵詞對訓(xùn)練樣例的平均查準(zhǔn)率P。

對于每個訓(xùn)練樣例，其查詢關(guān)鍵詞的查準(zhǔn)率定義為包含目標(biāo)屬性值的查詢結(jié)果在返回的查詢結(jié)果中的比例，即:

其中C為包含目標(biāo)屬性值的查詢結(jié)果，T為查詢關(guān)鍵詞返回的結(jié)果數(shù)。

平均查準(zhǔn)率P即為所有訓(xùn)練樣例查詢關(guān)鍵詞的查準(zhǔn)率的平均值，即:

其中N為選取的訓(xùn)練樣例的個數(shù)，pi為第i個訓(xùn)練樣例的查詢關(guān)鍵詞的查準(zhǔn)率。

平均查準(zhǔn)率越高，說明訓(xùn)練樣例目標(biāo)屬性值在查詢關(guān)鍵詞的返回結(jié)果中出現(xiàn)的次數(shù)越多，那么對于目標(biāo)元組，從返回結(jié)果中提取出目標(biāo)屬性正確值的概率就越大。

(3)比例系數(shù)α、β的確定。

由于實際需求，需要優(yōu)先保證由所選屬性構(gòu)造的查詢關(guān)鍵詞的返回結(jié)果中包含目標(biāo)元組的目標(biāo)屬性值，即需要優(yōu)先保證支持度S達(dá)到一定的閾值，在此基礎(chǔ)上，找查準(zhǔn)率盡可能大的查詢關(guān)鍵詞。因此，設(shè)置比例系數(shù) α =0.8，β =0.2。

2.2.3 GQFA 遺傳操作

(1)選擇操作。

選擇操作是從當(dāng)前群體中選擇適應(yīng)度較高的成員進(jìn)行后續(xù)的進(jìn)化。適應(yīng)度越高的成員，被選擇的概率也越大［11］。目前已有多種選擇算法，如輪盤賭選擇、錦標(biāo)賽選擇、排序選擇等。

GQFA采用的是輪盤賭選擇，也稱為適應(yīng)度比例選擇，選擇某成員hi的概率是通過這個成員的適應(yīng)度與當(dāng)前群體中其他成員的適應(yīng)度比值得到的，公式如下［1］:

其中F(hi)是假設(shè)hi的適應(yīng)度，F(xiàn)(hi)是當(dāng)前群體中所有成員的適應(yīng)度之和。

通過選擇操作，保留適應(yīng)度高的屬性子集，過濾掉適應(yīng)度低的屬性子集。

(2)交叉操作。

交叉操作以選擇的優(yōu)秀成員作為雙親，通過雙親的交換組合來產(chǎn)生新的優(yōu)秀成員。現(xiàn)有的常用交叉方法有:單點(diǎn)交叉、兩點(diǎn)交叉、均勻交叉等方法。

GQFA采用的是均勻交叉，均勻交叉具有更好的重組能力，可以減少重復(fù)，加快新的模式的發(fā)現(xiàn)，可防止收斂于局部極值點(diǎn)。均勻交叉合并了從兩個雙親以均勻概率抽取的位，應(yīng)用均勻交叉算子時，產(chǎn)生一個隨機(jī)的0、1位串作為交叉掩碼，其長度與個體長度相同，將其應(yīng)用到雙親產(chǎn)生新成員。

通過交叉操作，產(chǎn)生新的屬性子集。

(3)變異操作。

變異操作是另一種產(chǎn)生新成員的操作，通過單一的雙親產(chǎn)生單一的后代。變異算子對父輩的二進(jìn)制位串產(chǎn)生隨機(jī)的小變化。變異操作可確保遺傳基因多樣性，搜索能在盡可能大的空間中進(jìn)行，避免陷入局部解，獲得質(zhì)量較高的成員［11］。

GQFA方法是隨機(jī)選取一個位，然后取反，也就是隨機(jī)選取已知屬性的一個屬性，改變其選擇狀態(tài)，產(chǎn)生新的屬性子集，避免局部收斂。

2.2.4 GQFA 算法實現(xiàn)

GQFA算法偽代碼如下:

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

本實驗選取了以下兩個數(shù)據(jù)集:

(1)Book-Crossing公共數(shù)據(jù)集中的Book數(shù)據(jù)表［12］:包含約20幾萬個元組，5個屬性(ISBN，書名，作者，出版年份，出版社信息)。

(2)美國財富雜志評選出的世界前1000強(qiáng)企業(yè)信息數(shù)據(jù)表［13］:包含約1000個元組，10個屬性(企業(yè)名稱，企業(yè)地址，所在城市，所在州，郵政編碼，電話，網(wǎng)址，企業(yè)郵箱，CEO名字，CEO郵箱信息)。

這兩個數(shù)據(jù)集都是完整的關(guān)系數(shù)據(jù)，并且都可以在Web上獲取相關(guān)的信息。在實驗中，隨機(jī)抽取10條完整數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)。為了驗證遺傳算法訓(xùn)練得到的查詢關(guān)鍵詞的有效性，需要不完整數(shù)據(jù)作為測試集，隨機(jī)選取20條完整數(shù)據(jù)并移除某個屬性值作為測試集。

3.2 參數(shù)設(shè)置

本實驗中，采用Bing API［14］作為搜索引擎響應(yīng)查詢關(guān)鍵詞，通過返回的網(wǎng)頁內(nèi)容摘要來評估查詢的有效性，選取前20條摘要。

經(jīng)過反復(fù)實驗，遺傳算法中的交叉因子設(shè)置為0.8，變異因子設(shè)置為0.2，對于初始種群大小和遺傳代數(shù)閾值這兩個參數(shù)的選取，則根據(jù)數(shù)據(jù)集屬性個數(shù)來選擇。對于Book數(shù)據(jù)表，屬性個數(shù)較少，因此搜索空間較小，故而初始種群的大小設(shè)為5，遺傳代數(shù)閾值設(shè)為3。對于財富1000強(qiáng)數(shù)據(jù)表，屬性個數(shù)較多，搜索空間較大，初始種群大小設(shè)為10，遺傳代數(shù)閾值設(shè)為10，以保證能找到較優(yōu)的解。

3.3 實驗結(jié)果

(1)對于Book數(shù)據(jù)集，分別選取Author和Title為代表作為目標(biāo)屬性，測試訓(xùn)練集上學(xué)習(xí)得到的查詢關(guān)鍵詞上是否對于測試集同樣有效，實驗結(jié)果見表1。

表1 Book數(shù)據(jù)集實驗結(jié)果

(2)對于財富1000強(qiáng)數(shù)據(jù)集，分別選取了State、ZipCode、Website、GeneralEmail為代表作為目標(biāo)屬性，測試訓(xùn)練集上學(xué)習(xí)得到的查詢關(guān)鍵詞上是否對于測試集同樣有效。實驗結(jié)果見表2。

表2 財富1000強(qiáng)數(shù)據(jù)集實驗結(jié)果

由上述實驗結(jié)果可知，基于遺傳算法訓(xùn)練得到的查詢關(guān)鍵詞在測試集上的有效性和在訓(xùn)練集上的有效性相差無幾，并且能保證構(gòu)造的查詢關(guān)鍵詞返回的結(jié)果中能夠抽取出目標(biāo)屬性的正確值。因而，基于遺傳算法的查詢關(guān)鍵詞的構(gòu)造方法是有效的。

4 結(jié)束語

本文針對關(guān)系數(shù)據(jù)查詢關(guān)鍵詞的自動構(gòu)造問題，提出一種基于遺傳算法的構(gòu)造方法并對該方法進(jìn)行驗證。實驗結(jié)果表明，該方法學(xué)習(xí)到的查詢關(guān)鍵詞是有效的。然而本方法中，參數(shù)的選取是根據(jù)數(shù)據(jù)集的特征人工選擇的，下一步工作擬提出一種自適應(yīng)的查詢關(guān)鍵詞構(gòu)造方法，實現(xiàn)完全自動化。

［1］Kwok C，Etzioni O，Weld D S.Scaling question answering to the Web［J］.ACM Transactions on Information Systems(TOIS)，2001，19(3):242-262.

［2］Grzymala-Busse Jerzy W.Three approaches to missing attribute values:A rough set perspective［M］//Data Mining:Foundations and Practice.Springer Berlin Heidelberg，2008:139-152.

［3］Ramprasath M，Hariharan S.A survey on question answering system［J］.International Journal of Research and Reviews in Information Sciences(IJRRIS)，2012，2(1):171-178.

［4］Tang N，VemuriV R.Web-based knowledge acquisition to impute missing values for classification［C］//Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence.2004:124-130.

［5］Goldberg D E.Genetic Algorithms in Search，Optimization，and Machine Learning［M］.Boston:Addison-Wesley，1989.

［6］［美］米歇爾.機(jī)器學(xué)習(xí)［M］.曾華軍，等譯.北京:機(jī)械工業(yè)出版社，2003.

［7］Li Z，Sharaf M A，Sitbon L，et al.WebPut:Efficient Web-based data imputation［C］//Proceedings of the 13th International Conference on Web Information Systems Engineering.2012:243-256.

［8］The Apache Software Foundation.Welcome to Apache OpenNLP［DB/OL］.http://opennlp.apache.org/，2013-05-08.

［9］Finkel J R，Grenager T，Manning C.Incorporating non-local information into information extraction systems by gibbs sampling［C］//Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics.2005:363-370.

［10］The Stanford Natural Language Processing Group.Stanford Named Entity Recognizer(NER)［DB/OL］.http://nlp.stanford.edu/software/CRF-NER.shtml，2013-05-08.

［11］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，1999.

［12］GroupLens Website.Book-Crossing Dataset［DB/OL］.http://grouplens.org/datasets/book-crossing/，2013-05-27.

［13］Brown Computer Science.Fortune 500/1000 Contact Information(2008)［DB/OL］.http://cs.brown.edu/～ pavlo/fortune1000/，2013-5-27.

［14］Google Developers.Azure-Bing-Search-Java［DB/OL］.http://code.google.com/p/azure-bing-search-java/，2013-05-08.