基于Markov的概念自动抽取算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Markov的概念自动抽取算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：提出了一种概念自动抽取算法，该算法的目的是从英文文本中抽取出由多个单词组成的概念。文中首先证明了概念的抽取过程是一个多个状态的齐次Markov链，然后给出了具体的抽取过程，即，如果多步转移概率达到所给定的阈值，则将这多个状态，即多个单词，看作是一个概念。为了对算法进行性能测试，借助网络爬虫，从网络中获取有关计算机领域的文本文档，采用本文算法进行概念抽取，结果显示该算法优于其他算法。
关键词：马尔克夫；概念；转移概率；概念抽取；规则
中图分类号：TP391.1 文献标识码：A
1 引言
概念在本体中处于重要位置。随着社会的发展，新的概念，尤其是多个单词组成的概念层出不穷，从领域文档、互联网中抽取出这些概念来丰富领域知识库是一项有意义的工作。人工获取概念是效率低，费时费力，而概念的自动抽取在信息处理等应用中扮演着重要角色。目前主要的抽取方法都是基于统计、规则和二者混合的方法，笔者于本文中提出markov的概念抽取方法，该方法可以从英文文本中抽取出包含多个英文单词的概念。
2 相关工作
本节将对目前采用的概念自动抽取算法进行讨论，分析其优缺点，在此基础上阐述本文算法。
基于规则的方法是建立一系列的模板，和模板相匹配的概念即为领域概念，如N（其中A为形容词，N为名词，P表示介词）[1]，符合这个形式则作为一个概念。还有一种改进的空间概念抽取算法，算法中通过一定的规则去获取两个义素之间的语义关系，通过两义素的相似度值来获取空间概念间的相似度，从而抽取出空间概念[2]。从金融领域资源中抽取出相关概念的方法，其中也用到规则模板的制定[3]。总之，该类方法中均根据一定的规则制定相应的模板，但是模板是人工建立，毕竟人们的知识有限，不可能制定出面向全部语法规则的模板，有必要建立一种适用某个领域概念抽取的完善的模板，但是这是一项非常困难的工作。
基于统计的方法有基于频率，基于统计，基于互信息（Mutual Information MI）或信息熵等技术，Damerau提出的是一种基于互信息的方法，要抽取的概念中包含了两个单词和，Damerau认为如果两个单词和的MI值大于某给定阈值，则该两单词可以被看作为一个概念。但是MI方法会把与看作是一个概念，这将影响到概念抽取的准确率。一种基于最大熵模型的本体概念获取方法，通过对领域文本进行挖掘得到名词性短语，再使用改进的TF-IDF公式从中抽取具有领域性的短语[4]。Dinh等人[5]在抽取生物医学概念时采用了纯统计向量空间模型，借助词袋概念以及单词在文本中的位置特征抽取相关概念。
统计和规则二者相结合的方法称之为混合法，该方法是通过制定规则，实现筛选，然后对筛选的数据进行统计，并从中抽取概念，对概念赋值并统计大小，根据值的大小，证明是否是领域概念。一种与领域无关，并且是半自动的概念抽取方法是Frantzi提出的[6]，在这个方法中对C-value和NC-value分别进行抽取，其中C-value的抽取用到了语言学知识（其中包含词性标注，语法过滤等），也用到了统计学知识，如表达式（1）：
这时C-value的表达式，其中，是概念频率，是包含的待抽取的概念集合；是集合中概念个数。因为C-value方法因为语法过滤器的选择会影响该算法的召回率和准确度。而将表达式（1）纳入概念抽取，就会形成C-value的扩展，也就是NC-value，如表达式（2）：
是待抽取概念，是作为的上下位单词所出现的频率，是单词的权值，是集合的单词，是单词的直接上下位单词的集合。
张新等人提出了一种基于规则与统计的本体概念自动共聚方法，从领域文本中通过语义串切分、规则匹配、领域归属度分析和概念约简算法自动获取领域概念[7]。但是其中的词性组合规则不易把握，如何将规则定义的完善是该方法需要解决的问题。
3 基于Markov的概念抽取算法
该算法是针对多个单词组成的概念，如campus violence，French riots，911 terrorist attack等。这就好比是马尔可夫链，多个单词的概念抽取可看作是多态的，并设定一个多步转移率的阈值，如果超过该阈值，就把这个多态链称为一个概念，这种方法从模型上看计算简单，准确率也高，相应的抽取概念的效率自然也会提高。[8]
3.1 概念的Markov性
要把领域文档看作一个概念集合，而且是自动抽取概念的过程，就必须以信息学的角度进行分析。这里的概念集合设为，其中，是概念集合当中的元素，而是元素的个数，也就是单词的个数，那么多个单词的抽取，就是从集合中抽取多个元素的概念。
下面证明概念抽取过程的Markov性。
证明：假设多；领域文档中的一个变量，这个变量代表一个单词，则就有多种状态，可以把它看作是一个随机，此时，可以把集合C看作是一个多态集合。当在已知的情况下，的分布概率只与有关，而和无关。其中是与相邻的单词。由此可以证明是符合抽取概念多态链，即Markov链。
3.2 概念的抽取过程
在抽取单词的过程中，设在时间n时，Markov链的状态是，即，在下一个时间n+1内，抽取单词，则。此时从抽取单词到的转移概念就可以计算出来了，其表达式为，，或者用表示，1表示T，就是抽取第一个单词和第二个单词的时间间隔。只和，和T有关，可以看出是稳定值，可以证明单词抽取是齐次Markov链。
在上述的过程中可以说Markov链是从一个状态转化到另外一个状态，其表达式为（3）所示：
其中，表示从状态到状态的一步转移概率。
概念抽取的步骤总结如下：
这里要有一个前提，就是假设我们已经具有了一个领域文档，那么具体的抽取过程分为四步：
（1）用空格将文档中的所有标点符号替换下来。
（2）计算两次抽取单词的一步转移概率，并建立一个对应的矩阵，如转移矩阵P。
（3）如果转移概率大于给定阈值，则将看作是一个待定概念。
（4）检索待定概念的集合，将形如“we， are”等通用概念从C中清除。
这四个步骤是抽取两个单词的过程，如果想抽取大于两个单词所形成的概念的话，就需要把第三步中的概率重新计算，并与阈值进行比较，如果大于阈值，就可以进行第四步。
4 性能比较
本节将基于Markov的概念抽取算法与基于频率，互信息，C-value及NC-value四种算法进行比较分析。利用五种算法在相同的文档中对单词进行抽取形成概念，然后对每种算法的召回率和准确率进行比较。
具体方法是：取得637个文档，这些文档从http：///wiki/computer_science上获取，然后创建一个小型的文档，该文档具有421532个单词。从这个文档中利用五种算法进行单词的抽取。
在第一种算法中采用基于频率的算法，阈值为1302，其结果如表1中所示，第二种算法是互信息的算法，阈值采用9.227，其结果如表1第三行所示，第三种算法是C-value算法，结果如表1第四行所示，采用的过滤器是Noun+Noun，第四种与第三种相同，见表第五行。第五种算法就是Markov算法了，其阈值为0.436，结果见表1第六行。
由表1可看出，采用C-value和NC-value算法，由于其采用语法过滤器，结果导致将有些本来是所需概念被滤掉，因此具有较低的召回率。基于频率和互信息的召回率和准确率相差不大是因为MI均基于频率。在这些数据中召回率最高的是基于Markov的算法，其根本原因在于：前面四种算法都是基于概念，而Markov是因为转移概率，也就是说出现频率低的概念也会被作为待定概念被抽取。另外该算法准确率也较高，这是因为该算法将单词的排列顺序考虑在内。另外，该算法模型简单，构建效率较高。
5 结束语
因为随着社会的发展，一些领域，尤其发展速度较快的领域，新的概念层出不穷，这些概念中的多数概念是由多个单词构成，所以本文提出了一种基于Markov的概念抽取方法。该方法可以从英文文献中抽取出来含有多个单词的概念，并且具有领域无关性。整个抽取过程基于多个状态的Markov链，可以通过每个概念中所包含单词的多步转移概率来判断，如果转移概率达到一个所设定的阈值，则将概念从资料中抽取出来。该方法计算简单，易于实现，效率高，通过与其它算法比较具有较好的性能。
参考文献：
[1] John S. Justeson and Slava M. Katz. Techincal terminology： some linguistic properties and an algorithm for identification in text[J]. Natural Language Engineering，1995，1（1）：9-27.
[2] Qing Yang， Kai-min Cai， Yan Li， Rui-qing Liu An Area Concept Extraction Algorithm Based on Association Rule[C].Proceedings of the 2010 International Conference of Information Science and Management Engineering ISME '10，2010，3：562-564.
[3] Mihaela Vela，Thierry Declerck Concept and relation extraction in the finance domain[C].Proceedings of the Eighth International Conference on Computational Semantics， Tilburg （Netherlands），2009：346-350.
[4] 韦小丽，等.基于最大熵模型的本体概念获取方法[J].计算机工程，2009（24）：114-116.
[5] Dinh，D.and Tamine，L.Biomedical concept extraction based
on combining the content-based and word order similarities[J]. In SAC，2011：1159-1163.
[6] K.Frantzi，S.Ananiadou，and H.Mima.Automatic Recognition of Multi-Word Terms： the C-value/NC-value Method[J].International Journal of Digital Libraries，2000，3（2）：117-132.
[7] 张新，党延忠.基于规则与统计的本体概念自动获取方法研究[J].情报学报， 2007，26（6）：813-820.
[8] 周子力.基于WordNet的本体构建及其在安全领域应用关键技术研究[J].华东师范大学，2009.
作者简介：
宋元海，男，高校讲师，兖州矿区职工大学计算机系任
教，擅长计算机软件设计.