基于Apriori算法的事件識別方法研究

張梅 程利偉

摘要：事件的識別對人們社會生活具有重要意義。本文借鑒Apriori方法進行事件規(guī)則挖掘，采用對擴展觸發(fā)詞進行規(guī)則約束的方式來完成事件識別任務(wù)，具體采用擴展觸發(fā)詞方式進行數(shù)據(jù)篩選，得到初步結(jié)果集；采用觸發(fā)詞方式獲得的語料結(jié)果作為規(guī)則挖掘集合，從中得到適合事件識別的規(guī)則。通過與擴展觸發(fā)詞方法結(jié)果的對比，結(jié)果表明采用機器學(xué)習(xí)方法進行規(guī)則挖掘?qū)κ录R別具有很好的適用性。

關(guān)鍵詞：Apriori算法 新聞?wù)Z料 事件

中圖分類號：TP391.1 文獻標識碼：A 文章編號：1007-9416（2016）05-0000-00

1引言

事件抽取隸屬于信息抽取領(lǐng)域，旨在把非結(jié)構(gòu)化的信息用結(jié)構(gòu)化的自然語言表達出來，使用戶可以得到對感興趣的事件信息的直觀反應(yīng)，事件抽取的研究是科學(xué)發(fā)展的需要，具有深遠的理論意義和廣泛的應(yīng)用價值。它可以結(jié)合數(shù)據(jù)挖掘、機器學(xué)習(xí)、數(shù)據(jù)庫等多個學(xué)科的技術(shù)和方法，在自動文摘、自動問答、信息檢索等多個領(lǐng)域體現(xiàn)出廣泛的應(yīng)用價值[1，2]。

近些年事件抽取的相關(guān)工作進展得如火如荼，國內(nèi)外涌現(xiàn)出大量學(xué)者對其進行研究，研究的方法主要有兩種：模式匹配的方法和機器學(xué)習(xí)的方法。其中，模式匹配的方法通過將待抽取的事件和已知的模式進行匹配來完成抽取任務(wù)；機器學(xué)習(xí)的方法則是依賴于分類器的構(gòu)建和事件特征的發(fā)現(xiàn)，選擇合適的事件特征并應(yīng)用適當?shù)姆诸惼鱽硗瓿伞?/p>

本文介紹的內(nèi)容試圖找到一種方法，以此方法可以在大量的新聞內(nèi)容中篩選出事件[3]。此方法結(jié)合傳統(tǒng)分類方法與機器學(xué)習(xí)的分類方法且借鑒ACE中對于事件抽取的相關(guān)概念[4]，對其做出相應(yīng)調(diào)整，并將其應(yīng)用到新聞中事件的類型識別上。

2基于Apriori的事件識別算法

事件類型識別是事件抽取的一個子任務(wù)。目前處理事件抽取的方法一般分為兩個步驟：事件類型識別和事件元素識別。在事件類型識別的常用方法中，基于觸發(fā)詞的識別方法具有準確率高，抽取方法簡單易行等優(yōu)點。但是這種抽取方法往往得到的結(jié)果集比較小，可以使用《同義詞詞林（擴展版）》擴展事件觸發(fā)詞的方法雖然可以使得結(jié)果集增大，但是卻使得準確率有所下降。

本文采用Apriori算法進行事件識別。一般對于給定的項目集合，算法通常嘗試在項目集合中找出若干相同子集。該算法采用自底向上的處理方法，即頻繁子集每次只擴展一個對象（該步驟被成為候選集產(chǎn)生），并且候選集由數(shù)據(jù)進行檢驗。當不再產(chǎn)生符合條件的擴展對象時，算法終止。

算法約定，事務(wù)的集合用D表示，X=>Y表示關(guān)聯(lián)規(guī)則，其中“=>”是關(guān)聯(lián)操作，X表示關(guān)聯(lián)規(guī)則的先決條件，Y表示關(guān)聯(lián)規(guī)則的結(jié)果。事務(wù)集合D中關(guān)聯(lián)規(guī)則X=>Y由支持度S和置信度C來約束。支持度表示在規(guī)則中出現(xiàn)的頻率，其公式表示為

S（X∪Y）= Count（X∪Y）/Count（D），

即事務(wù)集D中包含X和Y的事務(wù)所占的比例；置信度表示規(guī)則的強度，其公式表示為

C（X=>Y）= S（X∪Y）/S（X）

即事務(wù)集D中包含X的事務(wù)中有多大可能性包含Y。

Apriori算法是一個基于兩階段頻繁集理論的遞推方法，算法設(shè)計分為兩部分：預(yù)設(shè)支持度，找出所有支持度大于該最小支持度的集合；根據(jù)支持度得到的集合進一步迭代得到最終結(jié)果。

其步驟如下：

（a）掃描：通過單趟掃描事務(wù)集合D計算出各個1項集的支持度，排除那些不符合預(yù)設(shè)支持度的項，得 到頻繁1項集的集合，記作L（1）；

（b）連接：假設(shè)集合L（k-1）已求得，現(xiàn)需要用L（k-1）求得L（K），L（k-1）中的每個項集與其他項集進行相互連接操作，可以得到候選集C（K）；

（c）剪枝：根據(jù)算法性質(zhì)，任何非頻繁項集合都不肯可能是頻繁項集合的子集，排除C（k）那些不包含在頻繁項集合中的集合，即刪除C（k）中所有其（k-1）項子集不包含在L（k-1）的項集；

（d）再次掃描：通過單趟掃描事務(wù)集合D計算C（k）中每項的支持度，排除那些不符合預(yù)設(shè)支持度的項，得到頻繁項k項集的集合，記作L（k）；

重復(fù)上述步驟直到L（k）為空，對L（1）到L（k）取并集即為最終結(jié)果。

實際應(yīng)用過程中，應(yīng)結(jié)合本身業(yè)務(wù)及數(shù)據(jù)特點將數(shù)據(jù)集合盡可能壓縮，從而縮小頻繁項目集合。

3實驗

本文實驗數(shù)據(jù)采用搜狐研發(fā)中心提供的2012年的全網(wǎng)新聞數(shù)據(jù)（SogouCA），該數(shù)據(jù)內(nèi)容來自若干新聞?wù)军c2012年6月到7月期間國內(nèi)、國際、體育、社會、娛樂等18個頻道的新聞數(shù)據(jù)。在事件的類型識別中，應(yīng)用Aprior方法對已知事件的語義角色及命名實體進行關(guān)聯(lián)規(guī)則的挖掘。將基于Apriori方法挖掘出的規(guī)則模板在7000條數(shù)據(jù)測試集上進行測試，部分結(jié)果如表1所示：

分析測試結(jié)果，除[V，N]規(guī)則外各規(guī)則均表現(xiàn)良好，[V，N]規(guī)則屬于不適用的規(guī)則，雖然其在開發(fā)集上的支持度比較高，但是測試結(jié)果其表現(xiàn)不佳。造成這種現(xiàn)象的原因可能是測試集數(shù)據(jù)分布不均衡，以致測試數(shù)據(jù)中符合[V，N]規(guī)則的數(shù)據(jù)稀少。

4 結(jié)語

本文借助規(guī)則模板的自動挖掘來縮小擴展觸發(fā)詞結(jié)果的范圍，排除掉很多反例，使得性能得到提高。本文中提出的方法會挖掘出普適性規(guī)則（謂詞規(guī)則）或是效率低下的規(guī)則（[謂詞，地名]規(guī)則），這些不適用規(guī)則的識別是需要進一步研究的工作。

參考文獻

[1]王偉，趙東巖，趙偉.中文新聞關(guān)鍵事件的主題句識別[J].北京大學(xué)學(xué)報（自然科學(xué)版），2011，47（5）.

[2]楊亮，林原，林鴻飛.基于情感分布的微博熱點事件發(fā)現(xiàn)[J].中文信息學(xué)報， 2012，26（1）.

[3]趙軍，劉康，周光有，蔡黎，開放式文本信息抽取[J].中文信息學(xué)報，2011，25（6）.

[4]涂新輝，張紅春，周琨峰，何婷婷.中文維基百科的結(jié)構(gòu)化信息抽取及詞語相關(guān)度計算方法[J].中文信息學(xué)報，2012，26（3）.