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

張梅 程利偉

摘要：事件的識別對人們社會生活具有重要意義。本文借鑒Apriori方法進行事件規則挖掘，采用對擴展觸發詞進行規則約束的方式來完成事件識別任務，具體采用擴展觸發詞方式進行數據篩選，得到初步結果集；采用觸發詞方式獲得的語料結果作為規則挖掘集合，從中得到適合事件識別的規則。通過與擴展觸發詞方法結果的對比，結果表明采用機器學習方法進行規則挖掘對事件識別具有很好的適用性。

關鍵詞：Apriori算法 新聞語料 事件

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

1引言

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

近些年事件抽取的相關工作進展得如火如荼，國內外涌現出大量學者對其進行研究，研究的方法主要有兩種：模式匹配的方法和機器學習的方法。其中，模式匹配的方法通過將待抽取的事件和已知的模式進行匹配來完成抽取任務；機器學習的方法則是依賴于分類器的構建和事件特征的發現，選擇合適的事件特征并應用適當的分類器來完成。

本文介紹的內容試圖找到一種方法，以此方法可以在大量的新聞內容中篩選出事件[3]。此方法結合傳統分類方法與機器學習的分類方法且借鑒ACE中對于事件抽取的相關概念[4]，對其做出相應調整，并將其應用到新聞中事件的類型識別上。

2基于Apriori的事件識別算法

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

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

算法約定，事務的集合用D表示，X=>Y表示關聯規則，其中“=>”是關聯操作，X表示關聯規則的先決條件，Y表示關聯規則的結果。事務集合D中關聯規則X=>Y由支持度S和置信度C來約束。支持度表示在規則中出現的頻率，其公式表示為

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

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

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

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

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

其步驟如下：

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

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

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

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

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

實際應用過程中，應結合本身業務及數據特點將數據集合盡可能壓縮，從而縮小頻繁項目集合。

3實驗

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

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

4 結語

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

參考文獻

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

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

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

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