基于决策树的关键短语抽取

1、第9卷第1期2010年2月vo 1. 9 no. 1feb. 2010江南大学学报(自然科学版丿journa 1 of j ian gnan un iver sity( na tura 1 sc ien ce ed it ion)基于决策树的关键短语抽取12 11(1苏州大学计算机学院，江苏苏州215006; 2.江苏省现代企业信息化应用支撑软件工程技术研 究开发中心，江苏苏州215104)摘 要：针対关键短语抽取工作可以转化为某种分类问题，利用决策树构造分类器解决关键短语 的抽取。计分析表明，将文档中词的词频因子、首位置和词性作为决策树分类特征，并考虑词在 文档中出现的位置信息，对词的特征值

2、进行一定的调整，采用b agging重采样技术进一步提高了决 策树的抽取性能，使其完全匹配和部分匹配的f_检测率分别达到21.50%和54.49%。关键词：关键短语；抽取；特征；决策树中图分类号：tp18文献标识码：a文章编号:1671 -7147(2010)01 -0071 -04key p hr a se s ex tra c t ion ba sed on the d ec ision tree(1. schoo 1 of comp uter sc ience and techno logy, soochow u niversity, suzhou 215006, china; 2. j

3、 iangsu provincesuppo n softwa re enginee ring r and d cente r fo r mode rn info rm a tion techno logy app lica tion in enterp rise, suzhou 215104, china)a b stra c t: in the p ap e r, we u se dec ision tree to so lve the keyp h ra se s extrac tion p rob lem fo r it can be though t a s a k ind of c

4、la ssifica tion p rob lem. b a sed on ana lyzing the sc ien tific and techn ica 1 lite ra tu re, the fea tu re s wha t we se lec ted a re the fac to r of frequency , the first po sition and the po s, wh ich m ake a ce rta in ad ju stm en t to the fea tu re s of the wo rd th rough the po sition info

5、rm a tion whe re the wo rd app ea rs in the docum en ts. f ina lly, it m ake s the extrac tion p e rfo rm ance fu rthe r imp roved by m ean s of the b agging re samp ling techn ique, wh ich ge ts 21. 50% and 54. 49% sep a ra te ly fo r thef_m ea su re s of fu 11 m a tche s and p a rtic ia i m a tche

6、 s key word s: keyp h ra se s, extrac tion, fea tu re, dec ision tree抽取的、对表述该文档主题有实质意义的词。文档从国内外研究现状岀发，关键短语抽取方而己 关键短语抽取在自动分类、自动摘要等方面有着广有显著性工作。世纪70年代中期，机器学习技术 泛的应用，它不仅是进行这些工作不可缺少的基础引入关键短语自动抽取中。这种方法通过对训练数 和前提，也是互联网上信息建库的一项重要据进行训练获得统计参数，得到模型，最后对文档收稿日期:2009-08 - 12;修订日期:2009 - 10 - 20o作者简介：刘玲玲(1987-)汝，贵州

7、贵阳人，计算机科学与技术专业木科生。 主em ail: jyao suda edu cn刘玲玲，梁颖红，张永刚，韩艳，姚建民关键短语是从文档的标题、摘要和止文中自动工作。上3172进行关键短语抽取。到1999年，tumey将决策树应 用于英文关键短语的抽取中1 。决策树是一种基于 机器学习的算法，为此，文中将决策树c4.5算法 用于中文关键短语的抽取。文中所谓关键短语抽取问题是经过分词示进行的，即将文档中作者拟定的关键短语经分词后所 得的单个词看为正例，用1表示，否则为反例，用0 表示，从而把候选词看作是否关键短语的部分。刘华讨论了短语所具有的优势，他认为在汉语 信息处理中，短语具有结构稳沱、

8、语义完整和强统 计意义的特点，比词和其他特征项更适合作为文木【5进行短语识别，将识别出来的短语作为候选关键短 语合并为短语的判断依据；最后选择了简单的b agging算法获得了较好的分类效果。1关键短语抽取特征的确定特征选収是规则半成系统中非常巫要的一部(6|述出词对彖的特性，都将对决策树的训练过程及片 期的预测过程产生直接影响。在关键短语抽取系统屮，判断i个词是否是关 键短语，影响因素很多，如词频(fre)、首位置(d istance)以及这个词是否在文章标题、摘要等特 姝位置出现。文中从这些角度出发，根据对科技.文 档的统计分析选取特征。1. 1文本预处理对文本进行必耍的处理：(1)调用海

9、量分词进行分词、性标注；(2)去除停用词；(3)将文本中作者拟定的关键短语提取出来并从文本中丈掉；(4)去除作者信息、构名称。构造决策树的关键是如何选取决策树的属性， 即确定关键短语抽取所采取的特征。1.2文本候选词特征分析特征的选取将玄接影响到关键短语抽取的质 fflo验采用笫三届全国信息检索与内容安全学术 会议(nc ircs2007)收到的论文(246篇)文档进行 (含有949个关键短语)。1. 2. 1词频 文木中的高频词与低频词相比而言 更能表示文本主题大意，是作者着重阐述的対象或可能成为关键短语。采用词频作为一个特征。词频计算采用参考文者对象特征。中首先对会议论文中作者拟定的关 键

10、短语与非关键短语的词频进行统计分析，分析表 明随着词频的増大，关键短语的比例远大于非关键 短语的比例。因此，如果一个词的词频越爲，它越冇江南大学学报(自然科学版)献1 提供的词频因子计算方法：/fre< =( 1)1 +fi其中j为词i在该篇文档中出现的词频。该方法也/ u键短语摘黯词而不讎繊漑息对文本实际。12 2首位置特征分析 首位置即词w第1次出现在文章"1的位置。文中对词首次在文档中出现的位置(以所在的行讨论)进行统计分析，结果得到苗 次出现在标题的关键短语占46%,出现在文档中前7行的山到76%。于一行中并非所育的词都是关除以该文档所有词的个数作为首位宜特征值： 11

11、d itance =( 2)n其中，"为该文档预处理后词w第1次出现时之前所 出现词的个数为该文档预处理后所有词的个数。1.2.3特定位迸信息l的分析 在文木中不同位叫非线性隊i数方法，比线性方法更符合语言由度量。欄文献，将词w首次出现所在词的个数置的句子其重要程度有着较大差异。为了强调和通第小最参突出丈章福主曲祥昵姻fe聯購b衢棘确地描 短的旬子概括丄耍内容，这些句子含关键短语的可 能性就越大。过对会议论文某些特定位置出现的 平均关键短语个数的统计，得到在文章的大标题、 摘要、1段、标题、后1段、考文献中关键短 语平均出现的个数分别为1.8,2. 45, 0. 82, 1.7, 1

12、.85,1.31c根据对各位置的长度计算所得长度的 比值，将大标题的值乘3,小标题乘1.8。上述因素对关键短语抽取存在重大影响，文中 将这些因素作为决策树抽取关键短语的特征。词2基于决策树的关轡豆语抽取决策树描述加性的确立，便可利用c4.5算法构 造决策模型。用十折交叉验证來评估决策树抽取 关键短语性能。语料平均分为1()份，取具中9份 进行训练，1份作开放测试，循环进行10次实验。rh于文”汝终想获得的是更具有表现意义的 短语作为关键短语，于是将经决策树分类得到的候 选关键短语进行合并。并依据为：如果在文档中2 个或者儿个候选关键短语相邻出现，那它们相结合 所得短语可能是关键短谱，而不是将这

13、些候选关键 短语分别作为文档的关礙短语。因此，下一步是判1811。据表1进行关键短语抽取，实验结果如表2 所示。断候选关键短语是否在相邻出现，若是，则将其合 并，并把合并后所得的短语一一与经过短语识别以 后所得短语进行匹配，即判断通过候选关键短语合 成的短语是否为一个符合意义上的短语；若匹配， 则将其作为关键短语输出，否则将候选关键短语分 别作为关键短语输岀。综上所述，基于决策树学习的关键短语抽収过 程主要包括3个阶段：（1 ）训练阶段：对语料进行训 练，获取预测模型；（2）测试阶段：利用训练模型对 测试语料进行评测，得到候选关键短语；（3）合并 候选关键短语获取关键短语。3实验结果与分析实验

14、分别采用十折交叉验证和b agging重釆样 技术进行决策树关键短语的抽取，利用准确率、召 回率和f_检测率评价实验结果。均准确率为所有 文档准确率的平均值，平均召冋率为所有文档召回 率的平均值，平均已检测率则为所有文档已检测 率的平均值。3.1实验1:十折交叉验证采用表1列出的特征建立决策树进行关键短语 抽取。用两种匹配规则：完全匹配和部分匹配。完 全匹配是指自动抽取的关键短语和作者拟定的关 键矩语完全相冋；部分匹配是指自动抽取的关键短 语是作者拟泄的关键短语的部分，或者作者拟定的 关键短语是口动抽取关键短语的部分。表1关键短语抽取的特征描述tabl 1 fea ture s de scr

15、iption of key phra se extrac tion序号特征解释c4. 5类型1frc词频因子con tinuou s2distance文档中首次出现位置con (inuou s3p r（）p词是否为名词0, 14injitlc是否出现在标题(x 15in.abstrac t是否出现在摘要0, 16in_head i ng是否出现在小标题0, 17in_firstp是否出现在第一段0. 18in_la stp是否出现在最后一段0. 19in_refe re nee是否出现在参考文档0, 110class是否作者拟定关键短语0, 13.1.1特征的直接选取及决策树特征的描述 通的准

16、确率等都得到了一定的提高。表2十折交叉验证结果序号 匹配 准确率/%召冋率/% f_检测率/% 完全24.0518.7821.09部分64.2147.8754.85结杲分析表明，由于关键短语经分词后人部分 都出现在标题屮，injitle这个属性对决策树分类贡 献很人，从而导致该实验抽取出來的关键短语都來 自于标题。所以，文中通过统计词在文档中出现的 位置信息，对词的首位置特征值进行适当调整，抽 出文档屮英他部分出现的关键短语；再讨论如何対 不同位置的词进行适当加权，并希望找出一个最 佳值。3.1.2词位置信息对部分特征值的加权根据统 计分析屮关键短语在各位置屮出现的比例，通过加 权对首位置和词

17、频进行适当调整。特征加州卯表3 所示（其中0.54,0.245,0.3等数值都是通il统计分 析获得的2为首位置；f为词频因子）。表3特征加权表tab. 3 fea ture we igh ted ta ble序号加权特征解释1 fre, distancef,d采2 hijitlc3 ln_abstract4in lille. in abstrac t 小八、一0. 245 )4 injitle,in.abstract,in_head ing5 iii.title,in_abstracttln_head ing,ta b. 2 resu its of 102fo id cross2va lid

18、a tionin.firstp,( 1 - 0. 082 )ina sip,in.refe re nee表4表明，以第1组实验为基准，第2组实验只这笫第考虑了是否在大标题这一因素，准确率得到了-定 的提高，召回率却保持不变；笫3组实验考虑是否在 摘要中，其止确率和冇回率都相对第2组减少了。是山于摘要中存在大呈的非关键短语，容易将一部 分非关键短语误判为关键短语。4组、5组实验 的结果相对在逐渐提高，但其完全匹配准确率和召 冋率却比第2组客验的洽.这兄由丁亦村摘薯和小 标题的位逬信息进行调整的过程中引进了 一部分 垃圾申，is!肘林颌瀚釦功加忧加题对僦缙tumey 特征和其仙©mhkk

19、'j的備潼®磁 嗣越勒結的特征见农 这些位置信抵对词频因子的影响。表4看出，抽取表5 ba gg in g实验结果tab. 5 rc suits of bagg ing表4特征加权后实验结果tab. 4 re suits a ftcr the wc ight of fea ture匹卸删完完部签部准确率/%召回率/%f_检测率/%21. 9217. 8619. 6860. 4346. 4352. 5122. 7617. 8620. 0162. 9946. 4353. 4621.6717. 6019. 4261. 3346. 4352. 8522. 5417. 6219. 78

20、63. 8846. 4353. 7722. 5617. 1119. 4664.4445. 2053. 1324.4417. 9820. 7267. 5547.4155. 72方法no b agging匹配完全部分准确率/%召回率/%f_检测率/%24. 4467. 5517. 9847.4120. 7255. 72b agging 3完全22. 2418. 8320. 39部分61.4350. 1155. 20b agging 5完全24. 1218. 3220. 82部分67. 474& 4956. 43b agging 7完全26. 9915. 7519. 89部分72. 9541

21、.4052. 83b agging 9完全26. 661& 0221. 50部分69. 0045. 0254. 49由于文本中存在一些意思相近的词，例如作者 拟定的关键短语“图书管理"和“图书管理系统"、 “pager ank”秋tager ank算法”等，在进行匹配时 只能作为非关键短语来处理；同时由于文中短语识 别存在一定的缺陷，短语识别后所得短语中并没有 完全包括作者拟定的关键短语，而且冇的文本中并 没冇出现作者拟定的关键短语，例如点对点网络 等。据统计，949个作者拟定的关键短语中有46个 关键短语在文本中并没有出现，从而对实验结果造 成一定影响。3. 2实验2: ba gg in g重采样技术选取表4十折交叉验证中实验结果相对较好的 笫6组所选取的特征作为bagging算法中决策树的 特征，分别将训练预料随机的分为3, 5, 7, 9份(即 b agging3, b agging5, b agging7, b agging9)进行训练, 测试、票以及与文档经过短语识别后的短语进行 匹配即得到