基于排序集成的自动术语识别方法_粟超.pdf

《基于排序集成的自动术语识别方法_粟超.pdf》由会员分享，可在线阅读，更多相关《基于排序集成的自动术语识别方法_粟超.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 29 卷第 1 期计算机应用与软件Vol.29 No 12012 年 1 月Computer Applications and SoftwareJan 2012基于排序集成的自动术语识别方法粟超(复旦大学计算机科学技术学院上海 201203)收稿日期:2011 03 23。粟超，硕士生，主研领域:文本挖掘，Web数据挖掘。摘要自动术语识别是信息抽取和文本挖掘等领域的关键步骤之一。基础自动术语识别算法采用某些方面的特征信息，有明显的局限性，引入局部 Kemeny 最优的方法来处理自动术语识别问题，并提出新的集成方法。实验结果表明该方法显著改善了自动术语识别的精准度。关键词排序集成自动术语识别

2、文本挖掘信息抽取中图分类号TP301文献标识码ARANK AGGREGATION-BASED AUTOMATIC TERM RECOGNITIONSu Chao(School of Computer Science，Fudan University，Shanghai 201203，China)AbstractAutomatic term recognition(ATR)is one of the key steps in the fields of information extraction and text mining As the basicATR algorithms use cha

3、racteristic information of certain aspects，they have noticeable limitations The paper introduces the local Kemenyoptimal method to deal with ATR issue，and presents a new rank aggregation method Experiment results show that the method has significantlyimproved the accuracy of automatic term recogniti

4、onKeywordsRank aggregationAutomatic term recognitionText miningInformation extraction0引言自动术语识别 ATR(Automatic term recognition)要解决的问题是如何从特定领域的文本语料库中自动提取出相关的术语。这里术语指的是能表示领域知识的关键名词性单词或词组。术语提取是进一步分析术语间关系的前提，可以为知识抽取、文本挖掘、链接分析等提供结构化知识单元。由于其重要性，自动术语识别问题已经得到了广泛的研究和关注。已有的自动术语识别方法通常包括两个步骤:第一步是预处理阶段，它利用词性标注器和名

5、词短语切分器等语言学工具来处理文本语料库，从而提取出候选术语的集合;而关于术语变体识别技术，可以根据一个术语的词根形态来得到与此相关的具体实现方式。第二步基于统计的术语识别，简言之，就是利用统计信息来赋予每个候选术语一个相应的权重，并输出具有最高权重的 k 个候选术语作为自动识别的结果。不同的 ATR 方法采用了不同的统计信息，常见的 ATR 算法包括有 TFIDF、C-Value、Weirdness 和 GlossEX 等。这些算法大多是关注于候选术语在领域语料库(或背景语料库)的某种统计信息，据此判断候选术语项作为术语的可能性，从而产生候选术语项的排序。然而，不同的 ATR 算法关注于术语

6、所应具备特性的不同方面，因此，它们对于来自特定领域的同一个语料库的术语候选项会计算得到不同的排序结果。本文关注和研究一种排序集成问题，即如何从多个不同的排序结果中产生一个全局的排序。为此，本文设计并实现了局部 Kemeny 最优方法，以及两个基础集成方法来解决问题。本文首先介绍了 7 种已有的用于解决 ATR 问题的基础算法;然后详细描述了使用局部 Kemeny 最优化方法来对这 7 种基础算法进行集成;最后在一个生物领域的 GENIA 语料库上进行了实验验证。1统计学的 ATR 算法ATR 算法的核心部分是对候选术语的排序，目前采用的特征指标大多基于术语的分布特征、结构特征和领域相关性信息等

7、，表 1 对 7 种 ATR 算法所采用的特征进行了归纳总结。表 17 种 ATR 算法所采用的特征算法名称术语的分布特征术语的构词特征术语的领域聚合度候选项是否预处理是否参考背景语料TF有无无有无TFIDF有无有有无C-value有有无有无GlossEX有有无有有Weirdness有无无有有RIDF有无有有无LR有无无有有(1)Term Frequency(TF)是一种单纯的词频统计算法。在第 1 期粟超:基于排序集成的自动术语识别方法197某领域经常出现的词组有更大的可能是该领域的术语。通常用于在语料库中统计候选词，在语义预处理之后，对候选词进行排序。(2)TfIdf 则在 TF 的基础上

8、增加对于术语分布的考量。频率一定的情况下，候选术语在某些文档中集中出现，而在其它文档中没有，说明这个候选术语更有区分性，适合用来分类。Idf反文档频率是指文档的总数除以候选术语在语料库出现的文档个数。Tf 词频(Term Frequency)是候选术语在语料库中出现的次数。表达式为:TfIdf(i)=Tf(i)Idf(i)(1)候选术语的 Tf 越高，那么它越可能分布在语料库里，但 Idf反而会减少，这样就对于分值有所抑制，希望候选术语频率高的情况下能够集中于少量的文档，可以推断这很可能是对于领域语料库的介绍和描述。(3)C-value 算法3 同样基于 TF 的思想。但它同时参考了术语的长度

9、和嵌套词的影响。它认为长度愈长的术语更难以出现，对于比较长的候选术语在其频率上会有相应的加权。因为一些候选术语是被嵌套词，这样它的嵌套词会多次累计频率，而很可能它自身并没有实际意义，所以需要进行相应的罚分来得到最终的分数。具体的计算公式是基于三个方面的因子:提取频率更高的术语，对于作为更长候选术语子串的嵌入术语进行罚分，以及考虑候选术语的长度。(4)RIdf 是对 Idf 方法的调整，Idf 因子受频率影响较大。频率较低的候选术语所存在的文档个数往往比频率高的更少，更有可能获取更高的 Idf，因此单纯考虑反转频率有明显的缺点。RIdf 根据候选术语的频率来估算出该项在语料库中的泊松分布1，从而

10、得出候选术语在某个文档中出现的泊松概率。当二项分布的 n 很大而 p 很小时，泊松分布可作为二项分布的近似，其中 在这里就是 f(i)/D，那么可以得到文档没有该术语的泊松概率为 1/e，即上式 k=0。候选术语的 Idf 和其泊松概率的对数之和就是 RIdf 的值，表示为:RIdf(i)=Idf(i)+log(1 p(0;(i)(2)其中 p 是参数为(i)=f(i)/D(候选术语在每个文档中的平均数)的泊松分布，f(i)是候选术语 i 在语料库中的数量，而 1 p(0;(i)是指文档中出现单词 i 的泊松概率。(5)Weirdness 方法则利用术语在语料库和背景语料库的比率来得到最终的分

11、值。它认为候选术语在语料库中出现的频率比在普通的文本里面出现的频率明显要高。假设一个候选术语在语料库中出现频率和在背景语料库中出现的频率一样，那么它很可能不是术语。这种算法表现的是一种差异化的思想，它认为术语应当是在该领域语料库中有大量的描述。它以单词为基本处理单位，候选术语会有 t 个单词，那么对候选术语中的每一个单词求出其比率，其几何平均值就是候选术语的分值。(6)Likelihood Ratio(LR)1 是反应术语真实性的一种指标。这种算法的设计思想和 Weirdness 比较相似，但是与 Weird-ness 不同的是，它使用似然比来进行一种平滑2。对于候选术语的二项式分布的表达式为

12、:LR=logL(fs，ns，p)+logL(fg，ng，p)logL(fs，ns，ps)logL(fg，ng，pg)(3)候选术语在领域语料库和背景语料库的出现次数分别是 fs和 fg，其概率分别是 ps和 pg，ns是语料库中候选术语的总频率，而 ng是背景语料库里候选术语的频率之和。其中 p=(fs+fg)/(ns+ng)，L(k，n，x)=xk(1 x)n k。(7)GlossEX4 结合了两个方面的思想。一种是用域相关性息的度量 TD 来进行评估的;TD 与 Weirdness 方法类似。另一种度量方法是使用了术语凝聚度 TC 来进行评测的。当一个术语出现的频率越高组成它的单词频率也

13、就越高。在此基础上提出假设，如果这些单词更集中于形成某个候选术语而不是组合成其它的项，那么说明这个候选术语有更高的组成凝聚度，可以推断具有明显的特征含义。术语凝聚度 TC 的具体实现可以参考文献 4。这两种度量方法可以用参数来进行线形的结合，表达式为:GlossEx(t)=TD(t)+TC(t)(4)其中 t 为候选术语，和 是两个常量参数。2排序集成的方法为了能够较好地融合基础的 ATR 算法，进一步提高识别的精准度，本文引入排序集成的方法进行研究，主要采用了局部Kemeny 最优方法8 来解决 ATR 问题。下面先引入几个相关的定义，再给出一种新的基础集成方法。定义 1K-distance

14、 和 是基于同一候选术语集合(1，n)的两个排序序列，和 的 K-distance 标记为 K(，)。对于候选术语对 i，j(1，n)，如果有 (i)(j)但是 (i)(j)，则为一个逆序对。两个序列的逆序对之和就是 K(，)的值。定义 2SK，Kemeny 最优有 m 个已经生成的排序序列(1，2，m)，序列 是根据这 m 个序列的重新排序，式(5)为 SK 的计算公式:Sk(，1，2，m)=mi=1K(，i)(5)如果有序列 使得 SK(，1，2，m)达到最小值，那么序列 为序列集(1，2，m)的 Kemeny 最优。定义 3孔多塞标准将每个候选术语与所有其它候选项成对比较，一次一个。只要

15、一个候选术语在大多数投票上的得分高于另一个候选项，那么它便击败了那个候选项。击败所有其它候选项的便是孔多塞赢家。这方法被称为孔多塞标准。Kemeny 最优满足孔多塞标准。然而当序列个数达到 4 时，Kemeny 最优就是一个 NP 难问题。因此本文使用局部 Kemeny最优方法来进行自动术语识别。局部 Kemeny 最优方法最初是由 Cynthia Dwork 等人提出的，应用于元搜索引擎的开发，生成的结果序列既符合扩展的孔多塞标准，又能够高效地运行。局部 Kemeny 最优方法包括两个步骤:(1)利用基础的排序集成方法来得到一个初始的排序序列，这里可以使用波达计数方法，也可以使用本文提出的

16、Kicker 方法。(2)基于序列(1，2，m)，对排序序列 进行局部Kemeny 最优化，生成序列 使得与序列 保持一致，并且满足扩展的孔多塞标准。2 1基础的集成方法波达计数5 是一种投票机制方法。先通过各个 ATR 算法根据自己的判别标准对于各个候选术语进行排列。如果候选者在选票中排第一位，它就得最高分值;排第二位得一个稍小的分值依此类推。通过候选术语在序列中的位置来确定分值，最后的投票积分之和越高，说明该候选术语表现越好。为一198计算机应用与软件2012 年个 ATR 算法所产生的候选术语序列，如果候选术语 i，则(i)表示候选术语 i 在 中的位置。计分公式为:w(i)=1(i)1

17、|(6)Kicker 方法是在波达计数上的改进。在 ATR 算法生成的m 个序列中，该方法认为术语应该尽量出现排序序列前 n 的位置(本文通过大量的实验，表明不论提取术语量 k 为何值，阈值n 设置为 k 的 2 倍时效果最好)。需要记录候选术语 i 在序列 的前 n 项中出现的总次数 c(i)。候选术语 i 遍历所有的序列。如果在序列 的前 n 项中出现过，那么 c(i)加 1，若没有则扫描下一个序列直到所有的序列都进行了扫描。计分表达式为:Kicker(i)=t(i)log(c(i)(7)t(i)指算法的波达计数公式 t(i)=R(1，2，m)，也可以使用其它递增函数(递增函数满足当任意序

18、列 k都有 k(i)k(j)时，必然有 t(i)t(j)。Kicker 方法是在波达计数的基础上，增加对于候选术语在单个序列 中的考量。波达计数是对于候选术语整体分布的评估，而每个 ATR 算法代表一个独有的特征抽取和判别标准。本文引入单个 ATR 算法置信度的概念来进行术语的识别，即候选术语 i 在所有序列前 n 项出现的总次数 c(i)。若候选术语 i 在序列 的前 n 项中出现过，那么序列 所属的 ATR 方法信任该候选项是术语。可以推理，在波达计数分值相同的情况下，若该候选术语被更多的 ATR 方法确信，那它更有可能是术语。2 2局部 Kemeny 最优定义 4若通过任意转换一个相邻候

19、选术语对的位置，不存在序列 使得 SK(，1，2，m)SK(，1，2，m)，那么序列 是序列集(1，2，m)的局部 Kemeny 最优。定义 5已知序列 是在序列集(1，2，m)上，通过基础集成方法生成的初始序列。对于序列 上的任意候选术语对 i 和 j，如果 (i)(j)，必然有 (i)(j)或者候选术语 i 在大多数序列中的排位比候选术语 j 靠前，那么序列 与序列 保持一致。定义 6当序列 与序列 保持一致，而且对于 的前 k项(1kn)的集合 S，在集合 S 上的投影序列与 在 S 上的投影序列保持一致，那么序列 是序列 的局部 Kemeny 最优。根据上述的定义，对于任意数 k，序列

20、 的前 k 项与序列 的前 k 项保持一致。执行步骤为:(1)初始状态置序列 为空，将序列 的首项加入到序列 中，把序列 的第二项加入到序列 的末尾。(2)在序列 中进行从末项往前的比较，即在序列 中有相邻的两个候选术语对 i 和 j(i 位于 j 之前)，若候选术语 i 在序列集(1，2，m)的多数序列中比候选术语 j 位置靠前，那么保持原来的序列;若候选术语 j 在其多数序列中的位置在 i 之前，交换候选术语对 i，j 的位置，交换向前的该项需要继续与在序列 中的前一项进行比较，以此类推，直到不需要发生位置改变。这样，对于序列 完成了一次从末项向前的扫描(使孔多塞赢家能够保持在序列的前面)

21、。(3)把序列 中的下一项加入序列 的尾部，在序列 中重复上述的步骤(2)。这样，将序列 中的项全部加入进去形成了完整的序列。在满足扩展的孔多塞标准的前提下，序列 尽可能与序列 保持一致。通过文献 8的证明还可以发现，序列 必然是唯一的。3实验结果与分析本文使用 Java 编程语言实现了上述集成方法，并在 GENIA语料库6 上进行了实验。GENIA 语料库包含了 3000 条取自MEDLINE 数据库的摘要，其中与蛋白质反应相关的物质和生物位置已经进行了手工标注。经过语义预处理和词性模板，本文一共提取了32073 个候选术语。不同的 ATR 算法可以对它们进行排序。设定待识别的术语数目为 k

22、，ATR 算法所产生排序 的前k 个候选术语将作为该算法的识别结果，该结果的精度表示为:precision=ki=1|ti reference|k(8)这里 reference 是从 GENIA 语料库中根据标注信息抽取出来的术语集合。当 tireference 的时候，|ti|等于 1，否则等于 0。精度所表示的就是该 ATR 算法所识别的具有最高排序的 k 个候选术语中属于 reference 的比例。为了评估排序集成方法的有效性，本文首先对 7 种基础分类算法进行参照实验，给出所得到的精度结果(k 值分别取 20、200 和 2000 三个数量级)作为比较的基准，如表 2 所示。表 2基

23、础 ATR 算法的精准度术语数目TFTFIDFRIDFLRWeirdness GlossExC-Value200900900 750950750 900 902000750790 760840520 830 8520000670680630520390 700 59使用 3 种排序集成算法对上述全部 7 种 ATR 基础算法的结果进行了集成，其中 Fagin 方法7 被应用于 IBM 中间件系统中。取得的精度结果如表 3 所示。表 3排序集成方法的精准度术语数目BordaFaginLocal Kemeny201001001002000880870922000063062072从表 3 可以看出

24、，这 3 种集成方法在只需提取 20 个术语的时候，其精度都为 100%。当需要识别 200 个术语时，它们都取得相当好的效果，所取得的精度都显著高于所使用的 7 种 ATR基础算法。当术语识别量为 2000 时，局部 Kemeny 最优方法表现出最高的识别精准度。图 1 的横轴上为各个方法，可以看到基础的 ATR 算法表现比集成方法差些。通过多特征、多算法的有机融合，基础的集成方法 Borda 和 Fagin 在一定程度上提高了识别的精准度。但是这两种集成方法并不满足扩展的孔多塞标准，因此生成序列的SK 值并不能保证较好地逼近 Kemeny 最优化值，相比局部Kemeny 最优方法稍显不足，

25、在提取大量术语时更加明显。图 1集成方法与基础 ATR 算法实验比较(下转第 223 页)第 1 期廖政等:红外光谱仪摆臂在线实时监控系统的设计与实现223监控系统上位机软件顶层数据流图如图 6 所示。图 6系统顶层数据流上行数据在经过主线程的校验、打包等预处理后存入链表中，然后触发相应数据处理事件，使得挂起的数据处理线程开始动作。数据处理时，依次读取链表节点，进行相应数据与图形显示，数据存储以及相应系统关键性能指标的计算与显示。(1)过程曲线显示实现过程曲线的显示通过编写相应绘图类实现。绘图时采用双缓冲方法，把要显示的图形先在内存中绘制好，然后再一次性的将内存中的图形覆盖到屏幕上，这样可以防

26、止屏幕闪烁。其中，使用失效矩形方法使相应区域失效，并对界面进行定时刷新。另外，绘图类基于系统实时显示的要求设计了多种显示周期，对于需要看细节的，在界面上显示每一个数据点;而对于要求看整体的，则采取多个数据中取一个数据进行显示。这样既保证了数据的准确性，又保证了系统的实时响应速度(2)数据显示实现在监视界面编辑框上显示相应数据，每显示完一屏数据立即清除，重新开始显示。(3)数据储存相关实现数据处理线程将接收到的原始数据以文件形式存储在上位机 PC 中，存储时以数据类型加存储起始时间为文件名进行追加存储，可以通过监视界面上相应复选框来选择是否要进行数据的存储。3 3监控系统下位机串口通信实现监控系

27、统下位机采用 TI 公司提供的 CCS 编译器对主控芯片 TMS320LF2407 进行汇编编程。程序实现时首先在主循环内判断是否接收完一帧数据，从而确定程序是否进入数据校验与解析分支;接着判断发送缓冲区中数据是否发送完成，决定是否进入数据发送打包分支。而接收与发送则由 SCI 中断处理，每次处理一个字节。数据接收通过接收中断实现，当接收到帧头时，复位接收缓冲区指针和数据接收计数器，并存储数据值至接收缓冲区;接着每接收一个字节数据，接收缓冲区指针和数据接收计数器值自动加 1;当接收到帧尾时，接收缓冲区指针和数据接收计数器不再自加，完成一帧数据的接收，此时，置相应标志并复位接收缓冲区指针。数据发

28、送通过发送中断实现，在主循环中循环判断发送缓冲区中的数据是否发送完成，一旦发送完，根据发送标志值的不同，从不同的数据源读取相应数据经格式转换后计算相应校验和并进行打包，同时初始化要发送的数据长度，触发发送中断进行逐个字节循环发送。4结语本文针对红外光谱仪摆臂系统调试中遇到的各种困难以及控制系统实时性对实时性及大量数据处理的相关要求，设计并实现了一种摆臂系统的在线实时监控系统，并重点介绍了在Win32 环境下使用多线程串口类实现的上位机监视软件。该系统很好地满足了控制系统的监控与调试要求并且已经成功地应用于摆臂控制系统的调试，同时，上位机监控部分各模块具有很强的通用性，可方便地移植到其他系统。参

29、考文献1 顾聚兴 用于大气化学实验的傅里叶变换光谱仪的设计(上)J 红外月刊，2004(10):40-452 龚建伟，熊光明 Visual C+/Turbo C 串口通信编程实践M 2版 北京:电子工业出版社，2007:16-173 姚国春，陈寿孙，杨卫列，等 多线程串口类在微型涡轮机控制中应用 J 计算机应用与软件，2007，24(12):67-684 龙飞，李晓帆，蔡志开，等 一个利用多线程及重叠 I/O 实现的串口通信类 J 微机发展，2004，14(3):50-515 王超，王少林，李志斌，等 Win32 环境下的实时监控程序 J 计算机应用，2001，21(12):86-88(上接第

30、 198 页)4结语通过局部 Kemeny 最优方法进行自动术语识别，使得在领域语料库中提取少量术语、中等数量的术语和大规模的术语都能取得很好的精准度，并有效抑制了较弱的 ATR 算法对于集成效果的干扰。在实际的系统中，结合多个 ATR 算法，确定所需的术语提取量来进行识别。本文的术语识别精准度已经能够满足绝大多数应用的需求，如何提高术语识别的自动化程度将是未来重要的研究方向。参考文献1 Manning C D，Schutze H Foundations of Statistical Natural LanguageProcessing M The MIT Press，19992 Ahmad

31、K，Gillam L，Tostevin L University of surrey participation intrec8:Weirdness indexing for logical document extrapolation and re-rieval(wilder)C/Proceedings of the Eight Text Retrieval Confer-ence(TREC-8)，20073 Frantzi K，Ananiadou S，Mima H Automatic recognition of multi-wordterms:The C-value/NC-value m

32、ethodJ International Journal onDigital Libraries，2000，3(2):115-1304 Kozakov L，Park Y，Cofino T，et al Glossary extraction and utilizationin the information search and delivery system for ibm technical support J IBM Syst J，2004，43(3):546-5635 Dwork C，Kumar R，Naor M，et al Rank aggregation methods for th

33、ewebC/Proceedings of the 10th International World Wide Web Con-ference，2001:613-6226 Collier N，Park H S，Ogata N，et al The GENIA project:corpus-basedknowledge acquisition and information extraction from genome researchpapersC/Proceedings of the Annual Meeting of the EuropeanChapter of the Association

34、 for Computational Linguistics(EACL 99)，1999 067 Fagin R，Lotem A，Naor M Optimal aggregation algotithms for middle-wareJ Journal of Computer and System Sciences，2003，66:614-6568 Dwork C，Kumary R，Naor M，et al Rank aggregation revisited OL Manuscript 2001 http:/www eecs harvard edu/michaelm/CS222/rank2 pdf