基于改进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.