基于改進K—means算法的時間和地點識別

張鵬　廖濤

摘要：事件要素識別主要包括時間要素和地點要素的識別。目前，時間和地點要素的識別主要是利用機器學習的方法，但是基于機器學習的方法容易受到語料稀疏性的影響。提出了基于改進K-means算法的時間和地點識別。該方法主要是對K-means算法進行改進，先利用Canopy算法求出聚類的K值，再根據改進的算法進行聚類分析，最后利用詞性進行優化處理，并得到實驗結果。

關鍵詞：事件要素識別；Canopy算法；K-means算法；詞性優化

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2017）36-0182-03

Abstract： Event element identification mainly includes the identification of time elements and location elements. At present， the recognition of time and place elements mainly uses the method of machine learning， but the method Based on machine learning is vulnerable to the sparseness of corpora. Proposed time and place recognition Based on improved K-means algorithm. The method is mainly to improve the K-means algorithm. Firstly， the K value of the clustering algorithm is calculated by Canopy algorithm. Then the clustering analysis is carried out according to the improved algorithm. Finally， part-of-speech is used to optimize the K-means algorithm and the experimental results are obtained.

Key words： Event element recognition； Canopy algorithm； K-means algorithm； Part of speech optimization

1 概述

隨著互聯網的蓬勃發展，人們每天都會從互聯網上接觸到海量的信息，為了能夠從海量的事件信息中獲得自己所關心的信息，因此，對事件信息的抽取任務正引起人們的廣泛關注。

事件抽取主要包括兩個方面，即事件識別和事件要素識別。事件識別[1]要判斷一個包含事件觸發詞的句子是否是現實世界中發生的事件。事件要素識別主要是把事件中的時間、地點、人物等要素識別出來。本文主要對事件時間和地點要素的識別進行研究。

目前，事件要素的識別主要采用機器學習的方法，這種學習需要大規模人工標注的熟語料庫作為訓練集，以獲取事件要素的相關知識，學習的效果依賴于語料的質量和規模[2]。如果語料不夠充分，往往使得識別效果不理想。因此，本文提出了基于改進K-means算法的時間和地點識別。

2 研究現狀

在國外，2006年，Ahn[3]提出把事件要素識別當做多元分類問題，采用基于分類學習的方法在ACE英文語料上實現事件識別和事件要素識別。Tan[4]等人先采用局部特征選擇和正反特征融合的方法識別事件，然后使用多層模式匹配再ACE中文語料上識別事件要素。Lin[5]等人采用動態方法來處理隱式時間表達式，用新的計分模型來確定網頁的關注時間并設計了基于時間和文本相關度的時間—文本檢索排序方法。國內趙妍妍[6]等人在Ahn的基礎上進行改進，提出對觸發詞進行擴展，并且采用多元分類模型的方法進行事件要素的識別。實驗效果有明顯提高。丁效等人[7]采用基于關鍵詞與觸發詞相結合的過濾方法進行事件類型的識別，進而采用基于最大熵分類方法對事件元素進行識別。付劍鋒[8]根據各個特征對聚類的貢獻不同分配不同權值的方法對事件要素進行識別。

3 時間和地點要素識別

3.1 K-means算法改進

傳統的K-means算法有很多的缺點[9]，例如：對離群點的敏感度，容易導致中心點偏移；無法確定K的個數。針對上面無法確定K的個數問題，本文引入了Canopy算法，有效地解決了K值問題。

Canopy聚類它能夠有效地降低K-means算法中計算點之間距離的復雜度。

其中T1和T2和Canopy算法中的兩個距離閾值，一般地T1>T2。當距離大于T1時，這些點就不會被歸入到中心所在的這個canopy類中，當距離小于T1大于T2時，這些點會被歸入到該中心所在的canopy中，但是它們并不會從data中被移除，也就是說，它們將會參與到下一輪的聚類過程中，成為新的canopy類的中心或者成員而當距離小于T2的時候，這些點就會被歸入到該中心的canopy類中，而且會從data中被移除，也就是不會參加下一次的聚類過程。

3.2 識別流程

本文主要分為三個步驟，第一步：對獲得的生語料進行預處理生成標注語料庫，并對標注語料庫進行構造數據集。第二步：對獲得的實驗數據集進行一次聚類。第三步：對聚類結果進行優化處理，并識別出時間、地點要素。

3.2.1 預處理

本文采用CEC（Chinese Emergency Corpus）[10]語料庫，并去除其標注作為本文實驗所用的生語料。CEC語料庫的規模雖然偏小，但是對事件和事件要素的標注卻很全面。在預處理過程中本文采用哈工大的語言技術平臺（Language Technology Platform，LTP）對生語料進行預處理得到實驗數據集。數據集主要由詞性特征、依存句法特征和語義依存分析經過量化組成。其中詞性特征主要對句子進行詞性標注。依存句法分析主要是分析句子中詞與詞之間的依存關系，揭示其句法結構的特點。語義依存分析主要是分析各個詞之間的語義關聯，并將語義關聯以依存結構呈現。基于這三種特征的作用，并且經過量化處理，我們得到了實驗數據集。

3.2.2 一次聚類

在聚類之前，可以把Canopy算法得到的K值結果添加到K-means算法中。這樣，改進的K-means聚類算法的基本步驟為：

輸入：原始數據（u1，u2，…，uk），Canopy算法得到的K值初始化隨機數據（x1，x2，…，xn）。uk和xn都是向量。

輸出：得到聚類類別

經過算法不斷重復計算，最終得到K個聚類。經發現聚類后時間和地點要素基本被集中在一個類中。但是類中還存在大量的“雜質數據”，影響時間和地點的識別工作，因此我們要對這些“雜質數據”進行進一步處理。

3.2.3 優化處理

在突發事件文本中，事件的時間，地點，對象等要素非常重要，所以時間和地點名詞在文本中最為重要。事件中的其他詞性，如形容詞和副詞的重要性次之，功能詞或虛詞如感嘆詞、代詞和連詞等，幾乎沒什么作用，可以像停用詞一樣被去掉。

例：綜合媒體報道，當地時間9月19日，墨西哥中部莫雷洛斯州發生7.1級地震，目前已造成至少248人死亡。該國首都墨西哥城震感強烈，部分街區停電，機場一度暫停全部航班。

4 實驗結果和分析

4.1 實驗準備

本文實驗數據采用了去除標注的CEC語料庫，并且分詞和句法分析采用了哈工大LTP模塊。為實現實驗結果本文使用Matlab軟件平臺進行相關實驗。并采用準確率P（Precision）、召回率R（Recall）和F值作為評價事件要素識別的標準。

4.2 實驗結果分析

我們將本文中的算法與文獻[3]、文獻[6]、文獻[8]以及傳統的K-means算法識別事件要素進行比較。這里利用準確率、召回率和F值進行參考。實驗結果如表1所示。

從表2可以看出，文獻[3]中準確率和召回率不是太高主要原因是語料規模較小，造成數據較為稀疏，文獻[6]中的召回率比文獻[3]中明顯高了一些，但準確率不是太高，原因主要是特征提取時不夠全面，觸發詞擴展不夠充分。文獻[8]中的準確率比前兩個都要高，它提出了特征加權的方式利用聚類算法進行要素識別，根據特征的不同分配不同的權值，最后進行聚類，在結果上有較好的結果，但論文中沒有給出召回率，所以對于文獻[8]我們只比較準確率。本文在機器學習的基礎上利用詞性特征來對事件要素進行識別，準確率和召回率都有所改觀。

5 結束語

本文分析了事件要素研究的現狀。針對目前研究情況，對傳統的K-means算法進行了適當改進，加入了Canopy算法，解決了聚類K值的問題，然后在聚類結果中利用詞性對結果進行篩選，最后，再次利用聚類算法，把時間地點識別出來。下一步研究方向是利用全監督聚類算法通過標記對象自動識別事件要素，同時語料庫的建設也是非常關鍵的重要一步。

參考文獻：

[1] 付劍鋒，劉宗田，付雪峰，等.基于依存分析的事件識別[J].計算機科學，2009，（11）：217-219.

[2] 劉煒，劉菲京，王東，等.一種基于事件本體的文本事件要素提取方法[J].中文信息學報，2016，30（4）：167-175.

[3] Ahn D. The stages of event extraction[C]//Proceedings of the COLING-ACL 2006 Workshop on Annotating and Reasoning About Time and Events.2006：1-8.

[4] Tan H， Zhao T， Zheng J.Identification of Chinese Event and Their Argument Roles[C]//Computer and Information Tech-nology Workshops， 2008 CIT Workshops 2008 IEEE 8th Inter-national Conference on.2008：14-19.

[5] GUREVV，PATHMANATHANP，FATYEBERT J L.A high一resolution computational model of the deforming human heart[J].Biomechanics and model- ing in mechanobiology，2015，14（4）：829-849.

[6] 趙妍妍，秦兵，車萬翔，等.中文事件抽取技術研究[J].中文信息學報，2008，22（1）：3-8.

[7] 丁效，宋凡，秦兵，等.音樂領域典型事件抽取方法研究[J].中文信息學報，2011，25（2）：15-20.

[8] 付劍鋒，劉宗田，劉煒，單建芳.基于特征加權的事件要素識別[J].計算機科學，2010（3）：239-241.

[9] 施侃晟，劉海濤，宋文濤.基于詞性和中心點改進的文本聚類方法[J].模式識別與人工智能，2012（6）：996-1001.

[10] 廖濤.面向事件的文本表示及其應用研究[D].上海大學，2014.