徐一紅

(山東管理學院機電學院,山東 濟南 250100)

本體是概念模型的明確規(guī)范說明[1],是描述某個領(lǐng)域內(nèi)的概念以及概念間的關(guān)系,使得這些概念和關(guān)系在共享的范圍內(nèi)具有大家共同認可的、明確的、唯一的定義[2]．近年來,本體被廣泛應用到語義web、智能信息檢索、信息集成及人工智能等多個領(lǐng)域．但是本體的構(gòu)建大多采用人工構(gòu)造,需耗費大量的人力、物力,本體學習應運而生．非分類關(guān)系是本體學習中的高層概念.當前,國外對英文非分類關(guān)系的提取常采用3種模式:詞匯-句法模式[3]、句法分析模式[4]以及關(guān)聯(lián)規(guī)則模式[5]．文獻[6]中對英文,利用了詞匯-句法模式和關(guān)聯(lián)規(guī)則模式抽取英文的非分類關(guān)系．中文本體非分類關(guān)系抽取的研究相對較少,文獻[7]大多利用挖掘關(guān)聯(lián)規(guī)則的方式抽取中文的非分類關(guān)系．

一些科研人員意識到了關(guān)聯(lián)規(guī)則挖掘在中文非分類關(guān)系抽取中的應用價值．仿生智能算法以其尋優(yōu)速度快,魯棒性強等優(yōu)勢已成挖掘關(guān)聯(lián)規(guī)則的重要研究算法,應用較廣泛的有Marco Dorigo在1992年提出的蟻群算法(ACO)[8], 1995 年由Eberhart博士和Kennedy博士提出的粒子群算法(PSO)[9],Ferreira于2001年提出的基因表達式編程算法(GEP)[10],Karaboga在2005年提出的人工蜂群算法(ABC)[11],Yang于 2008 年提出了一種啟發(fā)式隨機優(yōu)化算法——螢火蟲算法 (FA)[12].FA算法在函數(shù)尋優(yōu)方面得到了廣泛應用[13],但由于FA算法本身的局限性易使尋優(yōu)陷入局部最優(yōu)．本文提出了一種基于小生境技術(shù)的螢火蟲算法,該方法整合了螢火蟲算法及小生境技術(shù)的優(yōu)勢,克服了傳統(tǒng)方法存在的容易出現(xiàn)早熟現(xiàn)象和易陷入局部最優(yōu)的問題,在有效規(guī)則的抽取效率上優(yōu)于傳統(tǒng)的算法．

1 基本概念

1.1 螢火蟲算法(FA)[12]

螢火蟲算法是模擬自然界中螢火蟲的生物特性發(fā)展而來的,通過迭代完成尋優(yōu)的一種隨機搜索算法．螢火蟲算法包含2個要素,即亮度和吸引度．亮度體現(xiàn)了螢火蟲所處的位置的好壞,吸引度決定了螢火蟲移動的距離,通過吸引度和亮度的不斷更新實現(xiàn)目標尋優(yōu)．

螢火蟲的相對熒光亮度為式(1):

I=I0×e-γrij.

(1)

I0定義為螢火蟲的最大熒光亮度,γ為光強吸收系數(shù),一般設為1.0,rij為螢火蟲i與j之間的距離．

螢火蟲的吸引度為式(2):

(2)

β0定義為最大吸引度,γ,rij意義同式(1)．

螢火蟲i被螢火蟲j移動的位置更新由式(3)定義:

xi=xi+β×(xj-xi)+α×(rand-1/2). (3)

1.2 小生境技術(shù)

小生境是指生物在進化過程中的一種生存環(huán)境,在小生境中同種生物存在著信息交換及相互競爭．小生境技術(shù)的基本思想是根據(jù)個體之間的相似特征形成多個小生境,在各個小生境中利用融合及演化機制對個體進行調(diào)整,以保證種群的多樣性,同時根據(jù)平均適應度的變化,對規(guī)模的大小進行動態(tài)調(diào)整[14-15]．

在螢火蟲算法中引進小生境技術(shù)的概念, 讓個體在不同的小生境環(huán)境中進化,而不是全部聚集在一種環(huán)境中,這樣可以使算法在整個解空間中搜索,以找到更多的最優(yōu)個體．

小生境融合算法流程設計如下:

Step1:把n個小生境個體(nich1,…,nichn,分別為S1,…,Sn)全部存入nich1中;

小生境演化算法流程設計如下:

Step1:執(zhí)行螢火蟲算法得到子代G;將子代G與父代合并得P(t+1)=P(t)∪G;

Step2:在P(t+1)上執(zhí)行小生境融合算法;對其進行笛卡兒交叉,得到非劣集合OP(P(t+1),);

Step3:選取子代中適應度函數(shù)值最高的5%個體替換父代較差個體．

2 工業(yè)酶非分類關(guān)系抽取組合模型

2.1 適應度函數(shù)

適應度函數(shù)的設計對尋優(yōu)結(jié)果的影響非常重要[16]．在挖掘關(guān)聯(lián)規(guī)則中,由于支持度及置信度是關(guān)聯(lián)規(guī)則挖掘的重要參數(shù),分析中文非分類關(guān)系數(shù)據(jù)特點,組合模型的適應度函數(shù)f(i)定義如下:

(4)

spt(i)、cnf(i)分別是第i條規(guī)則的支持度值和置信度值;min-spt、min-cnf分別是最小支持度和最小置信度．

2.2 螢火蟲算法挖掘強關(guān)聯(lián)規(guī)則

設I={i1,i2,…,im}是m個項目構(gòu)成的集合,關(guān)聯(lián)規(guī)則的表示可以定義為R:X?Y,其中:X?I,Y?I且X∩Y=?,同時大于最小支持度min-spt和最小置信度min-cnf的規(guī)則被定義為強關(guān)聯(lián)規(guī)則[17-18]．強關(guān)聯(lián)規(guī)則的挖掘過程可描述為個體聚集在亮度最高的螢火蟲的位置上,實現(xiàn)尋優(yōu)的過程,其中螢火蟲i與j的坐標位置設置如下:首先對文檔按抽取的有效概念個數(shù)進行排序,對排好序的文檔依次抽取有效概念,按出現(xiàn)次數(shù)對有效概念從大到小依次排序,去除重復概念,構(gòu)成有效概念序列,組對(X-Y)出現(xiàn)的下標即為概念X和概念Y的序列號．

螢火蟲算法實現(xiàn)尋優(yōu)的過程如下:首先隨機產(chǎn)生螢火蟲群體,每一只螢火蟲因所處位置不同,根據(jù)式(4)適應度函數(shù)值也不同,通過比較適應度函數(shù)值,適應度函數(shù)值高的螢火蟲吸引適應度函數(shù)低的螢火蟲向自己移動,根據(jù)式(2)吸引度的大小決定移動的距離．為了避免過早陷入局部最優(yōu),在更新過程中增加了干擾項α×(rand-1/2),能擴大解的多樣性,根據(jù)式(3)計算更新取整后的位置．通過多次尋優(yōu)迭代后,螢火蟲個體將聚集在亮度高的螢火蟲位置上,從而實現(xiàn)尋優(yōu)．螢火蟲行為與強關(guān)聯(lián)規(guī)則挖掘?qū)P(guān)系如表1所示．

FA算法挖掘強關(guān)聯(lián)規(guī)則流程設計如下:

Step1:初始化參數(shù)．包括:螢火蟲個數(shù)m,最大吸引度β0,光強吸收系數(shù)γ,步長因子α,最大迭代次數(shù)maxT,隨機生成螢火蟲的位置．

Step2:按照式(4)和式(2)計算螢火蟲的相對熒光亮度和吸引度,根據(jù)熒光亮度決定螢火蟲的移動距離．

Step3:根據(jù)式(3)更新螢火蟲的空間位置,對處在最佳位置的螢火蟲進行隨機擾動．

表1 螢火蟲尋優(yōu)行為與強關(guān)聯(lián)規(guī)則對應關(guān)系

Step4:根據(jù)更新后螢火蟲的位置,重新計算螢火蟲的熒光亮度．

Step5:當達到最大搜索次數(shù)則轉(zhuǎn)下一步;否則,搜索次數(shù)增加1,轉(zhuǎn)Step2,進行下一次搜索．

Step6:輸出強關(guān)聯(lián)規(guī)則．

算法的時間復雜度為O(m2),m是螢火蟲數(shù)目．

2.3 組合模型設計

組合模型的基本思想是通過普通的關(guān)聯(lián)規(guī)則法,可得出具有非分類關(guān)系的概念對[20]．螢火蟲算法的本質(zhì)是模擬螢火蟲的隨機尋優(yōu)原理,由于算法自身的特點易使算法陷入局部最優(yōu),針對這一問題,本文利用小生境技術(shù)的演化、融合算法增加種群的多樣性,能夠解決傳統(tǒng)的螢火蟲算法過早陷入局部最優(yōu)的問題,使尋優(yōu)過程更加優(yōu)化．其流程設計如下:

Step1:將本體概念集隨機平均分配到各小生境中;

Step2:如果滿足結(jié)束條件,則執(zhí)行Step7,如果不滿足結(jié)束條件則繼續(xù)執(zhí)行;

Step3:執(zhí)行小生境演化、融合算法;

Step4:如果存在相似的個體,則去除適應度小的個體,添加隨機個體;

Step5:轉(zhuǎn)到Step2繼續(xù)執(zhí)行;

Step6:生成頻繁項集;

Step7:輸出非分類關(guān)系．

2.4 評價函數(shù)

評價多樣性的分析函數(shù)定義如下:

(5)

其中:N是群體的規(guī)模;dm,n表示個體之間的距離．

3 算法驗證

3.1 強關(guān)聯(lián)規(guī)則

為驗證算法的可靠性,從中國知網(wǎng)選取2012年120篇關(guān)于工業(yè)酶的文章作為領(lǐng)域文本集,背景語料集選取中文文本分類語料庫TanCorpV1.0中的12個類別的語料庫．在這些關(guān)于工業(yè)酶的文章中,利用概念提取算法[19],得到2 044個有效概念,對獲得的有效概念進行統(tǒng)計,設閾值為10,得到143個有效概念,其中次數(shù)最高者為工業(yè)酶,共343次;次數(shù)最少者為棉線磨光等56個候選術(shù)語,僅用1次．在這些本體概念上對非分類關(guān)系進行抽取實驗,取min-spt=0.1,min-cnf=0.8, 抽取關(guān)系747個．其中次數(shù)最高者為“制劑——產(chǎn)品”,其頻次為2.92,頻次超過0.1的關(guān)系有160個,得到關(guān)系如表2所示．

表2 關(guān)系抽取結(jié)果

3.2 與其他算法的比較

分別應用Apriori算法、螢火蟲算法與組合模型進行驗證,所有實驗運行100次,實驗結(jié)果如表3所示．

表3 工業(yè)酶非分類關(guān)系

綜合比較可以發(fā)現(xiàn),組合模型比FA算法、Apriori算法在運行效率、挖掘有效關(guān)聯(lián)規(guī)則的數(shù)量以及平均適應度上都有較明顯的提高．

圖1是螢火蟲算法與組合模型的多樣性對比．通過分析可以發(fā)現(xiàn),隨著迭代的增加,FA算法與組合模型的多樣性都呈下降趨勢,但是組合模型的多樣性進化到800代時保持較高,解決了FA算法易陷入局部最優(yōu)的問題,為不斷獲得新解,獲取全局最優(yōu)提供了保障．

圖1 個體多樣性對比

圖2是FA算法與組合模型迭代過程的平均適應度比較．通過對比可以發(fā)現(xiàn),組合模型的平均適應度與FA算法的平均適應度都逐漸增加,但組合模型的平均適應度明顯高于FA算法的平均適應度．

4 結(jié) 語

非分類關(guān)系抽取的研究在國內(nèi)才剛剛起步,本文在借鑒已有的挖掘關(guān)聯(lián)規(guī)則的經(jīng)驗基礎上,提出一種基于小生境技術(shù)的螢火蟲算法,該算法利用小生境技術(shù)的融合、演化算法豐富種群的多樣性,結(jié)合螢火蟲算法尋優(yōu)速度快的優(yōu)勢抽取非分類關(guān)系．通過驗證性實驗,相對于傳統(tǒng)的挖掘算法,該組合模型在效率、有效規(guī)則個數(shù)及平均適應度上都有明顯提高．

圖2 平均適應度對比

通過工業(yè)酶語料數(shù)據(jù)的繼續(xù)添加和合理的參數(shù)設定,以及盡量減少分詞和句法分析錯誤對結(jié)果造成的影響,該組合模型可為工業(yè)酶非分類關(guān)系抽取提供更有價值的參考．

參考文獻:

[1]Gruber T R. A translation approach to portable ontology specifications[J]. Knowledge acquisition,1993,5(2):199-220.

[2]杜小勇,李曼,王珊.本體學習研究綜述[J]. 軟件學報,2006,17(9):1832-1842.

[3]Girju R,Moldovan D I. Text Mining for Causal Relations[C]//FLAIRS Conference, Florida: AAAI Press,2002: 360-364.

[4]Ciaramita M, Gangemi A, Ratsch E, et al. Unsupervised Learning of Semantic Relations between Concepts of a Molecular Biology Ontology[C]//IJCAI, Edinburgh: Professional Book Center,2005: 659-664.

[5] Maedche A, Staab S. Discovering Conceptual Relations from Text[C]//Ecai,Berlin: Werner Horn IOS Press, 2000, 321(325): 27.

[6]李林,劉賀歡,劉椿年.Ontology自動構(gòu)造平臺OntoAGS[J]. 計算機工程,2006,32(13):212-214.

[7]方衛(wèi)東,袁華,劉衛(wèi)紅.基于Web挖掘的領(lǐng)域本體自動學習[J]. 清華大學學報:自然科學版,2005,45(增刊1):1729-1733.

[8]Kennedy J. Particle Swarm Optimization[M]//Encyclopedia of Machine Learning. New York: Springer US, 2010: 760-766.

[9]Von Frisch K. Decoding the language of the bee[J]. Readings in Zoosemiotics, 2011, 8: 141.

[10] Ferreira C. Gene expression programming: a new adaptive algorithm for solving problems[J]. Complex Systems, 2001, 13(2): 87-129.

[11]Yang Xinshe. Nature-inspired Metaheuristic Algorithms[M]. UK:Luniver Press, 2010.

[12] Yang Xinshe. Firefly Algorithms for Multimodal Optimization[M]//Stochastic Algorithms: Foundations and Applications. Berlin Heidelberg: Springer, 2009: 169-178.

[13] Jumadinova J, Dasgupta P. Firefly-inspired Synchronization for Improved Dynamic Pricing in Online Markets[C]//SASO.Venezia:IEEE Press,2008: 403-412.

[14]黃鋼,揚捷,李德華,等.基于GEP與小生境的關(guān)聯(lián)規(guī)則挖掘的研究[J]. 計算機應用研究,2009,26(1):56-58.

[15]崔挺,孫元章,徐箭,等. 基于改進小生境遺傳算法的電力系統(tǒng)無功優(yōu)化[J]. 中國電機工程學報,2011,31(19):43-50.

[16]沈國強,覃征.一種新的多維關(guān)聯(lián)規(guī)則挖掘算法[J]. 小型微型計算機系統(tǒng),2006,27(2):291-294.

[17]Xu Chuanfan,Duan Haibin. Artificial bee colony (ABC) optimized edge potential function (EPF) approach to target recognition for low-altitude aircraft[J]. Pattern Recognition Letters,2010,31(13): 1759-1772.

[18]潘慶先,于萍,婁蘭芳.關(guān)聯(lián)規(guī)則算法的研究及其在教學評價中的應用[J]. 煙臺大學學報:自然科學與工程版,2010,23(2):127-131.

[19]溫春,石昭祥,辛元.基于擴展關(guān)聯(lián)規(guī)則的中文非分類關(guān)系抽取[J]. 計算機工程,2009,35(24):63-65.