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

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

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

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

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

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

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

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

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

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

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

1 算法框架

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

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

1.1 事件句子的識別

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

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

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

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

1.2 事件抽取

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

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

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

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

1.2.1 輪廓系數(shù)

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

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

1.2.2 事件位置信息

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

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

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

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

1.2.3 事件時間信息

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

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

1.2.4 事件抽取

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

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

圖2 聚類過程Fig.2 Clustering process

2 實驗分析

2.1 實驗方案

2.1.1 數(shù)據(jù)準備

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

2.1.2 評價指標

采用準確率P、召回率R和綜合指標F值對算法的性能進行評估:

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

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

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

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

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

表1 實驗結(jié)果Tab.1 The experimental results%

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

3 結(jié)束語

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

[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] 高強,游宏梁.事件抽取技術(shù)研究綜述[J].情報理論與實踐,2013,36(4):114-117,128.

[4] 韓敏,唐常杰,段磊,等.基于TF-IDF相似度的標簽聚類方法[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é)報,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].電子科技大學(xué)學(xué)報,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計劃(2012AA011005)

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

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