夏 威,黃廷磊,劉久云,華綠綠

(桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林 541004)

基于馬爾可夫模型的新聞事件抽取方法

夏 威,黃廷磊,劉久云,華綠綠

(桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林 541004)

針對(duì)目前事件抽取方法普遍存在正反例子不平衡的問題,提出一種基于實(shí)例驅(qū)動(dòng)的事件抽取方法。該方法采用二元分類器過濾非事件句子,通過聚類事件句子完成事件抽取過程,利用馬爾可夫模型對(duì)文檔句子的位置信息進(jìn)行描述。實(shí)驗(yàn)結(jié)果表明,該方法能有效解決正反例不平衡的問題,提高事件抽取的整體性能。

事件抽取;新聞文本;分類;事件序列;聚類

隨著Internet的發(fā)展,在線新聞數(shù)量呈指數(shù)增長,其中大部分為非結(jié)構(gòu)化的信息,結(jié)構(gòu)凌亂、松散、數(shù)據(jù)量大以及冗余量大是這類信息的共同特點(diǎn)。如何挖掘潛在有價(jià)值的信息,仍是一大難題。在這樣的背景下,事件抽取技術(shù)應(yīng)運(yùn)而生。一般認(rèn)為,事件是發(fā)生在特定時(shí)間和地點(diǎn)的具體事情。事件抽取作為信息抽取領(lǐng)域的一個(gè)重要分支,其目的是從非結(jié)構(gòu)化的信息中抽取用戶感興趣的事件,并以結(jié)構(gòu)化的形式呈現(xiàn)給用戶。事件抽取涉及自然語言處理、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域,在自動(dòng)摘要[1]、信息檢索[2]、情報(bào)學(xué)[3]等領(lǐng)域均有廣泛的應(yīng)用。

目前,事件抽取的方法主要有2種:1)基于模式匹配[4]的方法。該方法的主要思想是應(yīng)用已建立的模式指導(dǎo)事件的識(shí)別和抽取,即用待抽取的句子匹配已建立的模式,如系統(tǒng)Ex Disco[5]、Gen PAM[6]等均采用此類方法建立,但模式的創(chuàng)建通常需要工程師手工完成,工作量大且可移植性差。2)基于機(jī)器學(xué)習(xí)的方法。該方法借鑒文本分類的思想,利用分類器識(shí)別事件元素以及事件類別,其事件分類通常是句子級(jí)的,一般為短文本。如Llorens等[7]利用CRF模型對(duì)語義角色進(jìn)行標(biāo)注,并將其應(yīng)用于Time ML的事件抽取。

機(jī)器學(xué)習(xí)方法可分為3類[8]:基于事件元素驅(qū)動(dòng)方法、基于事件觸發(fā)詞驅(qū)動(dòng)方法以及基于事件實(shí)例驅(qū)動(dòng)的方法。目前,國內(nèi)外的研究大多基于前2類方法,需要對(duì)所有相關(guān)詞語進(jìn)行判定。然而,在實(shí)際應(yīng)用中,非事件元素在句子中占有很大比例,且目前仍無高效的算法來完成過濾工作,這就引入了大量的反例,使得正反例嚴(yán)重不平衡。為此,基于事件實(shí)例驅(qū)動(dòng)的事件抽取算法,將一個(gè)事件句子看作一個(gè)實(shí)例,很好地解決了正反例不平衡的問題,具有較好的抽取效果。

1 算法框架

算法的基本框架為:利用支持向量機(jī)(SVM)過濾非事件語句,對(duì)來自不同新聞文檔的句子集合進(jìn)行聚類,聚類階段利用馬爾可夫模型模擬事件在文檔中的順序結(jié)構(gòu),并使用輪廓系數(shù)[9](silhouette coefficient)確定聚類的最終簇個(gè)數(shù),作為聚類的終止條件。事件抽取流程如圖1所示,主要包括事件句子的識(shí)別和聚類2個(gè)過程。

圖1 新聞事件抽取流程圖Fig.1 The flow chart of news event extraction

1.1 事件句子的識(shí)別

新聞文檔一般包含大量的非事件句子,影響事件抽取的準(zhǔn)確率。要提高事件抽取的效率,需對(duì)事件句子進(jìn)行識(shí)別,過濾非事件句子。事件句子識(shí)別的具體步驟如下:

1)預(yù)處理。著重進(jìn)行句子切分、中文分詞、詞性標(biāo)注、停用詞過濾等工作,完成對(duì)文本語料的初步處理。

2)特征提取?；陬A(yù)處理結(jié)果選取相關(guān)事件特征:詞語數(shù)量、句子位置、句子長度、停用詞頻率、實(shí)體數(shù)量、時(shí)間數(shù)量、數(shù)值數(shù)量等,利用向量空間模型(VSM)對(duì)預(yù)處理結(jié)果中的所有句子進(jìn)行向量表示。

3)事件識(shí)別。識(shí)別事件句子的實(shí)質(zhì)為一個(gè)二分類問題,支持向量機(jī)[10]分類器具有良好的可移植性、較高分類精度以及分類速度快等特點(diǎn),因此,采用SVM作為分類器進(jìn)行事件句子識(shí)別。

1.2 事件抽取

目前,聚類算法的研究已相當(dāng)成熟,主要分為層次聚類和非層次聚類,其中層次聚類方法應(yīng)用較為廣泛。凝聚的層次聚類應(yīng)用一種自底向上的方法,首先把每個(gè)數(shù)據(jù)點(diǎn)看作是一個(gè)簇,然后每次迭代合并最相似的2個(gè)簇形成更大的簇,直到滿足指定的終止條件為止。這一過程涉及簇之間的相似度度量,傳統(tǒng)相似度計(jì)算一般采用基于向量空間模型(VSM模型)的文本表示方法,將特征詞的TFIDF值應(yīng)用到VSM模型中,特征詞權(quán)重為

其中:ωij為特征項(xiàng)ti在句子sj中的權(quán)值;fij為特征詞ti在句子sj中出現(xiàn)的頻數(shù);∑fkj為句子sj中所有特

k∈sj征詞出現(xiàn)次數(shù)之和;nk為含有特征詞tk的句子數(shù);N為句子總數(shù)。

利用標(biāo)準(zhǔn)余弦結(jié)合特征項(xiàng)權(quán)值計(jì)算句子之間的相似度。傳統(tǒng)方法雖然簡單,但沒有很好地利用文檔內(nèi)部結(jié)構(gòu)信息,因而效果不佳。為此,將句子在文本中的位置信息以及句子包含的時(shí)間信息加入到相似度度量中。

1.2.1 輪廓系數(shù)

輪廓系數(shù)實(shí)際上是對(duì)凝聚度和分離度的改進(jìn),它將數(shù)據(jù)集中的任一對(duì)象與本簇中其他對(duì)象以及其他簇中對(duì)象的相似性分別進(jìn)行量化,然后將2種相似性量化后的結(jié)果以一定的形式組合起來,從而獲得聚類方法優(yōu)劣的綜合評(píng)價(jià)標(biāo)準(zhǔn)。對(duì)于簇中第i個(gè)對(duì)象,其輪廓系數(shù)為

其中:ai為數(shù)據(jù)點(diǎn)i與其所屬簇內(nèi)所有其他點(diǎn)距離的平均值;bi為數(shù)據(jù)點(diǎn)i距離其他簇中任意點(diǎn)的最小距離。對(duì)所有點(diǎn)輪廓系數(shù)進(jìn)行計(jì)算,然后求平均值,得到聚類結(jié)果的總體輪廓系數(shù)S,取值范圍為[―1,1],負(fù)值表示類的半徑比2個(gè)簇之間的距離大,即簇是重疊的,表明這個(gè)聚類結(jié)果不理想。S的值越大,聚類結(jié)果的效果越好。

1.2.2 事件位置信息

馬爾可夫模型描述了一個(gè)狀態(tài)序列。假設(shè)隨機(jī)過程中指定狀態(tài)qt的概率分布只與前一個(gè)狀態(tài)qt―1有關(guān),即p(qtq1,q2,…,qt―1)=p(qt qt―1),且不同狀態(tài)之間以一定的概率相互轉(zhuǎn)換。

文檔一般可認(rèn)為是一系列線性排列的句子,文獻(xiàn)[11]論證了位置相近的句子描述同一事件的可能性更大,后來的句子更可能引入新的事件。因此,包含不同事件的句子間一般存在一種先后順序關(guān)系,這種鏈?zhǔn)疥P(guān)系可使用馬爾可夫模型[12]進(jìn)行描述。將文檔中所有事件句子作為狀態(tài)集合,利用狀態(tài)集合對(duì)馬爾可夫模型進(jìn)行訓(xùn)練,得到某個(gè)狀態(tài)qi的出現(xiàn)次數(shù)以及qi轉(zhuǎn)移到qj的次數(shù),從而得到qi到qj的轉(zhuǎn)移概率。測試過程中,定義第一個(gè)包含事件的句子為初始狀態(tài),最后一個(gè)包含事件的句子為最終狀態(tài),不同的狀態(tài)根據(jù)一定的概率相互轉(zhuǎn)化。

上述過程可形式化描述為:設(shè)Q={q1,q2,…,qn}為n個(gè)事件的標(biāo)簽序列,p(S(q1))為以事件標(biāo)簽q1開始的文檔的概率,p(E(qn))為以事件標(biāo)簽qn結(jié)束的文檔的概率,p(qi|qi―1)為事件標(biāo)簽qi標(biāo)記的句子跟隨事件標(biāo)簽qi―1標(biāo)記的句子的概率,p(Q)為由馬爾可夫模型生成指定事件序列Q的概率,

根據(jù)式(3)可計(jì)算期望序列的概率,此過程假設(shè)每個(gè)句子最多提到一個(gè)事件。

1.2.3 事件時(shí)間信息

新聞文檔中的時(shí)間表示通常比較模糊,如:10月12日上午、上周五、去年、昨天等,文檔定位不夠精確,因此將時(shí)間與文檔發(fā)布時(shí)間進(jìn)行對(duì)比,以得到標(biāo)準(zhǔn)時(shí)間。對(duì)于不含時(shí)間信息的事件句子默認(rèn)其時(shí)間與報(bào)道時(shí)間相同,且假定時(shí)間接近的事件句子更可能描述同一事件。時(shí)間相似度

其中λ為系數(shù),實(shí)驗(yàn)中取值為10。

1.2.4 事件抽取

設(shè)Q(C1,C2)為通過合并2個(gè)簇C1、C2而產(chǎn)生的標(biāo)簽的序列,p(Q(C1,C2))為生成序列Q(C1,C2)的概率。C1、C2之間的相似度其中α為可變參數(shù),實(shí)驗(yàn)中取值為0.7。

假設(shè)剩余簇的個(gè)數(shù)為d,則有d(d―1)/2對(duì)簇。在每次迭代中,對(duì)每對(duì)簇(Ci,Cj)進(jìn)行預(yù)合并,得到結(jié)果標(biāo)簽序列,利用經(jīng)訓(xùn)練的馬爾可夫模型計(jì)算結(jié)果序列的概率。根據(jù)式(5)計(jì)算簇之間的相似度,合并相似度最大的一對(duì)簇,直到剩余簇個(gè)數(shù)為k時(shí)聚類結(jié)束,此時(shí)數(shù)據(jù)集獲得最大的輪廓系數(shù)。圖2為聚類過程,其中概率p為生成結(jié)果序列的概率。

圖2 聚類過程Fig.2 Clustering process

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)方案

2.1.1 數(shù)據(jù)準(zhǔn)備

實(shí)驗(yàn)以昆明“3·01”暴恐案相關(guān)新聞為例,將來自6個(gè)不同來源的約300篇新聞報(bào)道作為信息集合對(duì)算法進(jìn)行評(píng)估。這些新聞文檔大小不同、包含事件量也不同。每篇文檔所含事件平均量為3.02,每個(gè)句子所含事件平均量為1.03。首先對(duì)文檔進(jìn)行句子切分得到句子集合,然后利用SVM對(duì)其進(jìn)行過濾,獲得事件句子集合。對(duì)于集合中的每一個(gè)事件句子,依次手動(dòng)分配唯一整數(shù)標(biāo)簽。對(duì)于來自同一篇文檔且描述同一事件的句子,分配相同的標(biāo)簽。句子可涉及多個(gè)事件,例如“昆明暴案一審三人獲無期,二審高院駁回上訴”,這句話需分配2個(gè)標(biāo)簽,每次審判分配1個(gè)標(biāo)簽。

2.1.2 評(píng)價(jià)指標(biāo)

采用準(zhǔn)確率P、召回率R和綜合指標(biāo)F值對(duì)算法的性能進(jìn)行評(píng)估:

其中:a為屬于該類且被正確歸為該類的事件個(gè)數(shù);b為不屬于該類但錯(cuò)誤歸為該類的事件個(gè)數(shù);c為屬于該類但被錯(cuò)誤歸為其他類的事件個(gè)數(shù)。

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

利用不同的k值對(duì)上述實(shí)驗(yàn)數(shù)據(jù)集多次運(yùn)行k均值算法,計(jì)算每次聚類結(jié)果的整體輪廓系數(shù),當(dāng)輪廓系數(shù)最大時(shí),對(duì)應(yīng)的k值即為最佳簇個(gè)數(shù)。不同k值所對(duì)應(yīng)的輪廓系數(shù)如圖3所示。從圖3可看出,在k值取7時(shí),可獲得最大的輪廓系數(shù),則最佳簇個(gè)數(shù)為7。

圖3 不同k值對(duì)應(yīng)的輪廓系數(shù)Fig.3 Silhouette coefficient in the different k

將改進(jìn)方法與基于事件元素驅(qū)動(dòng)方法、基于觸發(fā)詞驅(qū)動(dòng)方法以及基線方法進(jìn)行對(duì)比,其中基線方法在聚類過程中僅使用傳統(tǒng)相似度度量,實(shí)驗(yàn)結(jié)果如表1所示。

表1 實(shí)驗(yàn)結(jié)果Tab.1 The experimental results%

從表1可看出,改進(jìn)方法取得了較好的結(jié)果,準(zhǔn)確率有了一定的提升,特別是召回率有了較大的提高,說明改進(jìn)方法能較好地完成事件抽取任務(wù)。最重要的是改進(jìn)方法解決了傳統(tǒng)基于觸發(fā)詞驅(qū)動(dòng)、事件元素驅(qū)動(dòng)模型在訓(xùn)練過程中引入太多反例以及造成數(shù)據(jù)稀疏問題,從而在召回率方面有了一定的突破。此外,由于改進(jìn)方法引入了對(duì)句子在文檔中位置的描述,使得抽取結(jié)果的整體性能高于基線方法。

3 結(jié)束語

在分析事件抽取現(xiàn)狀的基礎(chǔ)上,提出一種基于事件實(shí)例的事件抽取模型,完成了非事件過濾的任務(wù),有效解決了非事件句子對(duì)事件抽取過程的干擾,通過聚類事件實(shí)例完成事件抽取任務(wù),解決了傳統(tǒng)方法必須預(yù)定義抽取的事件類型問題。實(shí)驗(yàn)結(jié)果表明,改進(jìn)方法較好地解決了正反例不平衡的問題,提高了事件抽取的整體性能。

[1] Fattah M A.A hybrid machine learning model for multidocument summarization[J].Applied Intelligence,2014, 40(4):592-600.

[2] Janowicz K,Raubal M,Kuhn W.The semantics of similarity in geographic information retrieval[J].Journal of Spatial Information Science,2014,33(2):29-57.

[3] 高強(qiáng),游宏梁.事件抽取技術(shù)研究綜述[J].情報(bào)理論與實(shí)踐,2013,36(4):114-117,128.

[4] 韓敏,唐常杰,段磊,等.基于TF-IDF相似度的標(biāo)簽聚類方法[J].計(jì)算機(jī)科學(xué)與探索,2010,4(3):240-246.

[5] Yangarber R.Scenario customization for information extracrion[D].New York:New York University,2001:30-33.

[6] 姜吉發(fā).自由文本的信息抽取模式獲取的研究[D].北京:中國科學(xué)院,2004:27-29.

[7] Llorens H,Saquete E,Navarro-Colorado B.TimeML events recognition and classification:learning CRF models with semantic roles[C]//Proceedings of the 23rd International Conference on Computational Linguistics. Association for Computational Linguistics,2010:725-733.

[8] 許旭陽,韓永峰,宋文政.事件抽取技術(shù)的回顧與展望[J].信息工程大學(xué)學(xué)報(bào),2011,3(1):113-118.

[9] Aranganayagi S,Thangavel K.Clustering categorical data using silhouette coefficient as a relocating measure [C]//Conference on Computational Intelligence and Multimedia Applications,2007:13-17.

[10] 丁世飛,齊丙娟,譚紅艷.支持向量機(jī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報(bào),2011,40(1):2-10.

[11] Zha Hongyuan.Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering[C]//Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2002:113-120.

[12] Singh R S,Patel C,Yadav M K,et al.Weekly rainfall analysis and Markov chain model probability of dry and wet weeks at Varanasi in Uttar Pradesh[J].Environment and Ecology,2014,32(3):885-890.

編輯:梁王歡

News event extraction based on Markov model

Xia Wei,Huang Tinglei,Liu Jiuyun,Hua Lülü
(School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

Due to most of the existing approaches for event extraction generally cause an imbalance between positive and negative samples,a new extraction method driven by event instance is presented.The method removes the non-event sentences with support vector machine,and then a novel distance metric is presented which uses Markov model to describe the location of the sentences in documents.Experimental results indicate that the imbalance problem can be solved and the overall performance of event extraction is improved.

event extraction;news text;classify;event sequence;cluster

TP391

:A

:1673-808X(2015)04-0325-04

2015-03-26

國家863計(jì)劃(2012AA011005)

黃廷磊(1971―),男,安徽肥東人,教授,博士,研究方向?yàn)閿?shù)據(jù)挖掘、無線Mesh網(wǎng)絡(luò)等。E-mail:tlhuang@guet.edu.cn

夏威,黃廷磊,劉久云,等.基于馬爾可夫模型的新聞事件抽取方法[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(4):325-328.