基于最大Jaccard相似度的互激勵(lì)實(shí)體驗(yàn)證算法

劉寶超， 崔榮一

( 延邊大學(xué)工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科 智能信息處理研究室, 吉林 延吉 133002 )

基于最大Jaccard相似度的互激勵(lì)實(shí)體驗(yàn)證算法

劉寶超， 崔榮一*

( 延邊大學(xué)工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科 智能信息處理研究室, 吉林 延吉 133002 )

針對(duì)基于規(guī)則的信息抽取技術(shù)提出了一種互激勵(lì)實(shí)體驗(yàn)證算法.該算法兼顧了信息抽取過(guò)程中互激勵(lì)算法的優(yōu)點(diǎn)，并在此基礎(chǔ)上引入了實(shí)體等待隊(duì)列，用于存儲(chǔ)未被成功驗(yàn)證的實(shí)體，并以最大Jaccard相似度為原則進(jìn)行實(shí)體驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，將該算法應(yīng)用在基于規(guī)則的參考文獻(xiàn)命名實(shí)體抽取中，其抽取的準(zhǔn)確率要比SermeX系統(tǒng)高約15%,比Para Tools系統(tǒng)高約40%.

互激勵(lì)； 信息抽?。?參考文獻(xiàn)； 實(shí)體驗(yàn)證

基于規(guī)則的信息抽取是應(yīng)用比較廣泛的一種抽取方式，一般包括規(guī)則獲取和規(guī)則應(yīng)用兩個(gè)過(guò)程，其中規(guī)則獲取是該方式中最為關(guān)鍵的部分，只要能夠獲取規(guī)則，抽取工作就完成了一大部分，而且抽取效率極高[1-2].可是，就抽取的準(zhǔn)確率而言，基于規(guī)則的抽取方式要明顯低于基于NLP(自然語(yǔ)言處理)和基于統(tǒng)計(jì)學(xué)習(xí)的方式，其原因在于該方式?jīng)]有深入文本自身的含義，并且不考慮抽取結(jié)果的合理性，只要其符合抽取規(guī)則，就會(huì)被當(dāng)作目標(biāo)抽取出來(lái)[3].然而對(duì)于一些特殊領(lǐng)域的文本抽取，往往需要得到精確的抽取結(jié)果，因此鑒于上述情況，在抽取過(guò)程的最后階段引入實(shí)體驗(yàn)證環(huán)節(jié)尤為重要[4].

科技論文中著錄的文后參考文獻(xiàn)屬于半結(jié)構(gòu)化的應(yīng)用型文本，從眾多樣式的參考文獻(xiàn)中自動(dòng)提取出責(zé)任者、文獻(xiàn)題名、出版地等信息是文獻(xiàn)智能分析的重要內(nèi)容之一[5-6].采用基于規(guī)則的信息抽取方式不僅可以實(shí)現(xiàn)對(duì)參考文獻(xiàn)中責(zé)任者、文獻(xiàn)題名、期刊名、會(huì)議名、卷期、時(shí)間等命名實(shí)體的抽取，同時(shí)該方法操作簡(jiǎn)單,而且抽取的準(zhǔn)確率較高，是目前大部分信息抽取系統(tǒng)使用的主流抽取方式.例如CiteSeer系統(tǒng)就是采用啟發(fā)式規(guī)則實(shí)現(xiàn)參考文獻(xiàn)命名實(shí)體抽取的，并且該系統(tǒng)還能提供某一具體文獻(xiàn)的“引用”和“被引用”情況以及文獻(xiàn)的引用次數(shù)等信息[7].然而，這種僅按照啟發(fā)式規(guī)則抽取的方式，其準(zhǔn)確性仍依賴于被抽取文本自身的準(zhǔn)確性和完整性[8].為了擺脫這種依賴和提高抽取準(zhǔn)確率，本文在該抽取方法的最后階段加入了實(shí)體驗(yàn)證環(huán)節(jié)，同時(shí)將改進(jìn)的互激勵(lì)算法(mutual bootstrapping)應(yīng)用到該環(huán)節(jié)中，以進(jìn)一步提高命名實(shí)體的抽取準(zhǔn)確率.

1 互激勵(lì)算法與原激勵(lì)算法

互激勵(lì)法無(wú)須指出所有實(shí)例與目標(biāo)領(lǐng)域的相關(guān)性，但要給出一定量的種子詞(關(guān)鍵詞)進(jìn)行整個(gè)過(guò)程的初始化.初始化首先由種子詞獲取一定量的規(guī)則模式，由于規(guī)則具有一定的普遍性，因此規(guī)則中所隱含的種子詞一般要多于原來(lái)的種子詞，只要充分利用信息抽取的規(guī)則模式，即可得到更多的種子詞.在整個(gè)過(guò)程中，種子詞推動(dòng)規(guī)則模式的產(chǎn)生，而規(guī)則模式反過(guò)來(lái)又推動(dòng)種子詞的獲取，形成相互激勵(lì)的過(guò)程;反復(fù)該過(guò)程，直到?jīng)]有新的符合要求的種子詞或規(guī)則模式產(chǎn)生為止，即互激勵(lì)過(guò)程結(jié)束[9-10].

當(dāng)規(guī)則模式數(shù)量逐漸增多時(shí)，互激勵(lì)法有可能將一定量的非種子詞加入到種子詞集中，使得算法效率和準(zhǔn)確率降低，因此對(duì)新加入的種子詞需要進(jìn)行嚴(yán)格控制[11-12].多層激勵(lì)法(multilevel level bootstrapping)又稱為原激勵(lì)法(meta bootstrapping)，它在互激勵(lì)法的基礎(chǔ)上對(duì)種子詞進(jìn)行評(píng)分，通過(guò)分?jǐn)?shù)值控制其是否能夠加入到種子詞集中，從而保證所選種子詞的合法性，提高算法的效率.圖1為互激勵(lì)法與原激勵(lì)法的關(guān)系，圖2為改進(jìn)的互激勵(lì)法.

圖1 互激勵(lì)法與原激勵(lì)法的關(guān)系

圖2 改進(jìn)的互激勵(lì)法

2 互激勵(lì)實(shí)體驗(yàn)證算法

Step 1 建立初始期刊名關(guān)鍵詞庫(kù)，

D ictionary={w1,w2,…,wn-1,wn},

(1)

其中wi(i=1,2,…,n)為種子詞， n=|D ictionary|為種子個(gè)數(shù).

Step 2 將種子詞拆分得

wi={wi1,wi2,…,wimi} (i=1,2,…,n),

(2)

其中mi=|wi|為種子詞wi的長(zhǎng)度.

Step 3 將待驗(yàn)證的文獻(xiàn)題名R_name和期刊名R_type按照Step 2的方法進(jìn)行拆分得：

R_name={u1,u2,…,un},

(3)

R_type={v1,v2,…,vt},

(4)

其中n=|R_name|, t=|R_type|.

Step 4 按(5)式定義分別計(jì)算R_name和R_type與D ictionary的Jaccrad系數(shù)J(R_name,D ictionary)和J(R_type,D ictionary),

J(A,B)=|A∩B|/|A∪B|,

(5)

其中A和B為兩個(gè)集合.

Step 5 按下式計(jì)算文獻(xiàn)題名相似度SR_name和期刊名相似度SR_type:

SR_name=max(J(R_name,wk), 0≤k≤n);

(6)

SR_type=max(J(R_type,wk), 0≤k≤n).

(7)

Step 6 if (SR_name>SR_type), 判定文獻(xiàn)題名與期刊名順序書寫顛倒，調(diào)整抽取內(nèi)容，并將R_name加入到D ictionary中， R_type加入到文獻(xiàn)題名數(shù)據(jù)庫(kù)中.

Step 7 if (SR_name

Step 8 if (SR_name==SR_type), 無(wú)法確定抽取的內(nèi)容是否準(zhǔn)確，將R_name放入文獻(xiàn)題名臨時(shí)等待隊(duì)列, R_type放入期刊名臨時(shí)等待隊(duì)列.

Step 9 若文獻(xiàn)未全部驗(yàn)證結(jié)束，返回Step 3， 否則如果驗(yàn)證隊(duì)列空則轉(zhuǎn)Step 13.

Step 10 驗(yàn)證等待隊(duì)列中的文獻(xiàn)題名R_name和期刊名R_type， 返回Step 6.

Step 11 在驗(yàn)證等待隊(duì)列中的實(shí)體若出現(xiàn) if (SR_name==SR_type)， 這時(shí)不再放入等待隊(duì)列，而是利用文獻(xiàn)題名數(shù)據(jù)庫(kù)按(8)式和(9)式計(jì)算相似度，并記錄循環(huán)次數(shù)flag.

SR_name=max(J(R_name,w_nk),0≤k≤n)；

(8)

SR_type=max(J(R_type,w_nk),0≤k≤n).

(9)

式中w_nk是按照Step 2中的方法對(duì)文獻(xiàn)題名數(shù)據(jù)庫(kù)中已驗(yàn)證成功的文獻(xiàn)題名進(jìn)行拆分的結(jié)果.

Step 12 通過(guò)文獻(xiàn)題名數(shù)據(jù)庫(kù)驗(yàn)證時(shí)也出現(xiàn)SR_name==SR_type, 則說(shuō)明文獻(xiàn)題名和期刊名相同.

Step 13 結(jié)束.

因?yàn)槲墨I(xiàn)類型相對(duì)好確定，種子詞獲取相對(duì)容易，所以本文在Step 1中建立了一個(gè)初始文獻(xiàn)題名關(guān)鍵詞庫(kù)，種子詞wi(i=1,2,…,n)的選取是通過(guò)統(tǒng)計(jì)足夠多的學(xué)位論文文后參考文獻(xiàn)之后確定的出現(xiàn)最多的前n個(gè)關(guān)鍵詞.Step 2中中文種子詞拆分單位為漢字，而英文種子詞拆分單位為空格.

在Step 8中導(dǎo)致無(wú)法確定的原因可能有兩點(diǎn)：

1) D ictionary中的詞數(shù)量過(guò)少，導(dǎo)致計(jì)算后SR_name==SR_type==0；

2) R_name和R_type本身很相似，如R_name=“中文信息學(xué)報(bào)發(fā)展綜述”， R_type=“中文信息學(xué)報(bào)”，使得SR_name==SR_type≠0.

3 實(shí)驗(yàn)結(jié)果及分析

本文通過(guò)準(zhǔn)確率P、召回率R和F(measure)值這3個(gè)常用指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)，這樣可以較好地與SemreX和Para Tools系統(tǒng)所得結(jié)果進(jìn)行比較，其計(jì)算公式如下：

P=A/(A+C),

(10)

R=A/(A+B),

(11)

F=(α2+1)P*R/(α2P+R),

(12)

其中： A表示提取的樣本中抽取正確的文獻(xiàn)數(shù)； B表示未能正確提取的文獻(xiàn)數(shù)； C表示提取的樣本中抽取錯(cuò)誤的文獻(xiàn)數(shù)； F為綜合評(píng)價(jià)指標(biāo)； α越大， R對(duì)F的影響越大,本文中取α=1.

實(shí)驗(yàn)數(shù)據(jù)由某高校計(jì)算機(jī)類碩士學(xué)位論文中著錄的文后參考文獻(xiàn)構(gòu)成，共計(jì)741條，其中中文參考文獻(xiàn)582條，英文參考文獻(xiàn)159條.對(duì)每一條參考文獻(xiàn)，根據(jù)參考文獻(xiàn)信息抽取規(guī)則進(jìn)行命名實(shí)體抽取，并計(jì)算出P，R，F(xiàn)值，然后與SemreX系統(tǒng)和Para Tools系統(tǒng)進(jìn)行比較，對(duì)比結(jié)果見(jiàn)表1.由表1可以看出，本文抽取的各項(xiàng)指標(biāo)的平均值要高于SemreX系統(tǒng)約15%，高于Para Tools系統(tǒng)約40%.另外，SemreX系統(tǒng)和Para Tools系統(tǒng)中所用的抽取方法只適用于英文文獻(xiàn)的抽取，而本文提出的方法可以適用于中/英文文獻(xiàn)的抽取，擴(kuò)大了抽取范圍.

4 結(jié)論

本文針對(duì)基于規(guī)則的信息抽取技術(shù)提出了一種互激勵(lì)實(shí)體驗(yàn)證算法，并將其應(yīng)用在參考文獻(xiàn)命名實(shí)體抽取中，實(shí)驗(yàn)結(jié)果表明：①在信息抽取中引入實(shí)體驗(yàn)證環(huán)節(jié)，能有效減少對(duì)抽取文本自身含義準(zhǔn)確性的依賴；②在實(shí)體驗(yàn)證環(huán)節(jié)，將規(guī)則學(xué)習(xí)階段的互激勵(lì)法進(jìn)行了改進(jìn)，引入了實(shí)體等待隊(duì)列，使得最終抽取的結(jié)果其P，R，F(xiàn)值3項(xiàng)指標(biāo)遠(yuǎn)高于SemreX和Para Tools系統(tǒng).由于本算法沒(méi)有對(duì)D ictionary進(jìn)行優(yōu)化，存在運(yùn)行時(shí)間較長(zhǎng)的不足，因此本文將在今后的研究中運(yùn)用組合數(shù)學(xué)原理和遺傳算法等對(duì)D ictionary進(jìn)行優(yōu)化，以提高抽取效率.

表1 實(shí)驗(yàn)結(jié)果對(duì)比

[1] 李洪亮,黃莉.基于規(guī)則的百科人物屬性抽取算法的研究[D].成都：西南交通大學(xué),2013:11-25.

[2] 李湘東,霍亞勇,黃莉.圖書網(wǎng)頁(yè)的自動(dòng)識(shí)別及書目信息抽取研究[J].現(xiàn)代圖書情報(bào)技術(shù),2014(4):71-74.

[3] 郭志鑫,金海,陳漢華.SemreX中基于語(yǔ)義的文檔參考文獻(xiàn)元數(shù)據(jù)信息抽取[J].計(jì)算機(jī)研究與發(fā)展，2006,43(8):1368-1374.

[4] Cheng Xianyi, Zhu Qian, Wang Jin. The Principle and Application of Chinese Information Extraction[M]. Beijing: Science Press, 2010:181-182.

[5] 孫明,陸春生,徐秀星,等.一種基于SVM和AdaBoost的Web實(shí)體信息抽取方法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(4):101-106.

[6] 張秀秀,馬建霞.PDF科技論文語(yǔ)義元數(shù)據(jù)的自動(dòng)抽取研究[J].現(xiàn)代圖書情報(bào)技術(shù),2009(2):102-106.[7] Li Chaoguang, Zhang Ming, Deng Zhihong, et al. Automatic metadata extraction for scientific documents[J]. Computer Engineering and Applications, 2002,21(10):189-191.

[8] Liu Wei, Yan Hualiang. A unified and automatic web news object extraction approach[J]. Computer Engineering, 2012,38(11):167-169.

[9] Zhang M, Yin P, Deng Z H, et al. SVM+BiHMM: a hybrid statistic model for metadata extraction[J]. Journal of Software, 2008,19(2):358-368.

[10] Wang Shuang. Research of web information extraction technology oriented to digital tourism website[D]. Xi’an: Xidian University, 2012.

[11] 龔立群,馬寶英,常曉榮.科技文獻(xiàn)元數(shù)據(jù)自動(dòng)抽取研究綜述[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(3):11-15.

[12] 楊春磊,邵堃基.基于模式匹配的結(jié)構(gòu)化信息抽取研究[D].合肥：合肥工業(yè)大學(xué),2013:11-30.

[13] 陳先軍.文后參考文獻(xiàn)引著質(zhì)量及其審查方法[J].中國(guó)科技期刊研究,2014,25(9):1145-1148.

Mutual incentive entity verification algorithm based on the max Jaccard similarity

LIU Baochao, CUI Rongyi*

(IntelligentInformationProcessingLab.,DepartmentofComputerScience&Technology,CollegeofEngineering,YanbianUniversity,Yanji133002,China)

The technology of information extraction rules is proposed based on a mutual incentive entity authentication algorithm. The algorithm has both advantages of information extraction in the process of incentive algorithm, and on the basis of introducing the entity waiting queue, used to store has not been successfully verified entity, with the max Jaccard similarity principle of entity authentication. The experimental results show that, if the algorithm is applied in the reference named entity extraction, the extraction precision is higher than SermeX system about 15%, and is higher than Para Tools system about 40%.

mutual incentive; information extraction; reference; entity verification

2014-12-07 基金項(xiàng)目： 吉林省科技發(fā)展計(jì)劃項(xiàng)目(20140101186JC)

1004-4353(2015)01-0042-04

TP391.1

A

*通信作者： 崔榮一(1962—)，男，博士，教授，研究方向?yàn)槟Ｊ阶R(shí)別、智能計(jì)算.