劉寶超， 崔榮一

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

基于最大Jaccard相似度的互激勵實體驗證算法

劉寶超， 崔榮一*

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

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

互激勵； 信息抽??； 參考文獻； 實體驗證

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

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

1 互激勵算法與原激勵算法

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

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

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

圖2 改進的互激勵法

2 互激勵實體驗證算法

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

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

(1)

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

Step 2 將種子詞拆分得

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

(2)

其中mi=|wi|為種子詞wi的長度.

Step 3 將待驗證的文獻題名R_name和期刊名R_type按照Step 2的方法進行拆分得：

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

(3)

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

(4)

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

Step 4 按(5)式定義分別計算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為兩個集合.

Step 5 按下式計算文獻題名相似度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), 判定文獻題名與期刊名順序書寫顛倒，調(diào)整抽取內(nèi)容，并將R_name加入到D ictionary中， R_type加入到文獻題名數(shù)據(jù)庫中.

Step 7 if (SR_name

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

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

Step 10 驗證等待隊列中的文獻題名R_name和期刊名R_type， 返回Step 6.

Step 11 在驗證等待隊列中的實體若出現(xiàn) if (SR_name==SR_type)， 這時不再放入等待隊列，而是利用文獻題名數(shù)據(jù)庫按(8)式和(9)式計算相似度，并記錄循環(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中的方法對文獻題名數(shù)據(jù)庫中已驗證成功的文獻題名進行拆分的結(jié)果.

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

Step 13 結(jié)束.

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

在Step 8中導致無法確定的原因可能有兩點：

1) D ictionary中的詞數(shù)量過少，導致計算后SR_name==SR_type==0；

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

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

本文通過準確率P、召回率R和F(measure)值這3個常用指標對實驗結(jié)果進行評價，這樣可以較好地與SemreX和Para Tools系統(tǒng)所得結(jié)果進行比較，其計算公式如下：

P=A/(A+C),

(10)

R=A/(A+B),

(11)

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

(12)

其中： A表示提取的樣本中抽取正確的文獻數(shù)； B表示未能正確提取的文獻數(shù)； C表示提取的樣本中抽取錯誤的文獻數(shù)； F為綜合評價指標； α越大， R對F的影響越大,本文中取α=1.

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

4 結(jié)論

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

表1 實驗結(jié)果對比

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

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

[3] 郭志鑫,金海,陳漢華.SemreX中基于語義的文檔參考文獻元數(shù)據(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實體信息抽取方法[J].計算機應用與軟件,2013,30(4):101-106.

[6] 張秀秀,馬建霞.PDF科技論文語義元數(shù)據(jù)的自動抽取研究[J].現(xiàn)代圖書情報技術(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] 龔立群,馬寶英,常曉榮.科技文獻元數(shù)據(jù)自動抽取研究綜述[J].計算機系統(tǒng)應用,2013,22(3):11-15.

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

[13] 陳先軍.文后參考文獻引著質(zhì)量及其審查方法[J].中國科技期刊研究,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 基金項目： 吉林省科技發(fā)展計劃項目(20140101186JC)

1004-4353(2015)01-0042-04

TP391.1

A

*通信作者： 崔榮一(1962—)，男，博士，教授，研究方向為模式識別、智能計算.