本站原创这是一篇概念方面专科毕业论文范文,与基于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：//en.wikipedia./wiki/puter_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链,可以通过每个概念中所包含单词的多步转移概率来判断,如果转移概率达到一个所设定的阈值,则将概念从资料中抽取出来.该方法计算简单,易于实现,效率高,通过与其它算法比较具有较好的性能.