（计算机应用技术专业论文）中文文本主题词抽取研究与应用.pdf

复旦大学硕士学位论文 中文文本主题词抽取研究与应用 摘要 本文对文本主题词抽取进行了系统的研究，介绍了一种利用关联规则挖掘 中文文本主题词的方法。其中文本主题词由关键词和相关词组成，用户可以根 据提供的关键词和相关词了解w e b 页面的主题，有助于用户快速浏览页面，了 解页面内容；另外，相关词可以帮助用户扩展思路，提示用户未曾考虑到或并 未掌握的相关内容，从而更广泛、更全面地获得自己所需的信息，提高信息检 索效率。 传统的主题词抽取主要是从文档正文中抽取关键词( k e y p 髓e x t r a c t i o n ) ， 文档经过规范化处理被分成一系列的候选词，最后用一种有监督的学习算法确 定候选词是否被选为关键词。在关键词抽取模块中，本文采用4 4 种词性匹配模 版对候选词进行组合，通过计算特征值优先抽取t r i g r a m 和b i g r a m 作为关键 词，使抽取结果能够同时兼顾信息量大和可读性好两种特点。 在关键词抽取的基础上，我们提出一种基于关联规则挖掘相关词的方法， 使相关词和从该话题文本正文中抽取的关键词一起，作为文本主题词。在相关 词抽取模块中，系统经过噪音过滤的关键词集作为关联规则学习的项目集，单 篇文档对应的关键词作为一个项目，a p r i o r i 算法首先通过用户给定的最小支持 度，寻找所有频繁项目集，然后由频繁项集产生强关联规则，这些规则必须满 足最小支持度和最小置信度。系统根据关联规则挖掘结果找出和关键词屯有关 的其它关键词 ，如，乇 作为关键词对应文档的相关词，并和该篇文档的关 键词共同组成文本主题词。实验表明，本文提出的利用关联规则挖掘文本主题 词方法较为准确和有效，取得了较高的用户满意度。 关键词：文本挖掘文本主题词抽取关联规则 中图分类号：t p 3 2 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 a b s t r a c t t h i sp a p e rp r e s e n t sat h e m a t i ct e r m se x t r a c t i o na p p r o a c ht h a ti s b a s e do na s s o c i a t i o nr u l e s t h e m a t i ct e r m sa r ec o n s i s to f k e y p h r a s e sa n d r e l a t e dt e r m s ，w h i c hc o u l dg r e a t l yh e l pu s e r sg r a s pt h e m e so f w e b p a g e s ， a sw e l la sa c c e l e r a t i n gt h e i rb r o w s i n gs p e e d a l s o ，r e l a t e dt e r m sc o u l d n o t i f yu s e r sw i t ht e r m sw h i c ha r ev e r yu s e f u la n dh i g h l yr e l a t e dt ot h e d o c u m e n tb u tn o tt h a tf a m i l i a rt ou s e i s t h u se f f e c t i v e l yi n c r e a s i n gt h e e m c i e n e yo fi n f o r m a t i o nr e t r i e v a l t r a d i t i o n a lt h e m a t i ct e r m se x t r a c t i o n a p p r o a c h e sl a r g e l y c o n c e n t r a t eo n e x t r a c t i n gk e y p h r a s e sf r o md o c u m e n t s ，w h i c ha r es p l i t - t e d i n t oa g r o u po fc a n d i d a t ew o r d sa f t e rs t a n d a r d i z a t i o n ，a n ds o m es p e c i f i c l e a m i n ga l g o r i t h ma r eu t i l i z e dt oc h o o s ea p p r o p r i a t ew o r d sa n dp h r a s e s a sk e y p h r a s e s i no u rm e t h o d ，w ea d o p t e d4 4k i n d so fp a r t - o f s p e e c h c o m b i n a t i o n t e m p l a t e s ，t r i g r a m s a n db i g r a m sa r es e l e c t e da s k e y p h r a s e sw i t hh i 曲p r i o r i t y , w h i c hi n s u r et h er e s u l t sw i t hg o o d i n f o m a t i v e n e s sa n dr e a d a b i l i t y m o r e o v e r ，w ep r o p o s ear e l a t e dt e r m se x t r a c t i o na p p r o a c hb a s e do n a s s o c i a t i o nr u l e s a n dr e l a t e dt e r m sa n dk e y p h r a s e sa r ec o m b i n e da s t h e m a t i ct e r m s i nr e l a t e dt e r m se x t r a c t i o nm o d u l e ，w eb u i l dt h ei t e ms e t b yc o m b i n i n ga l lk e y p h r a s e sf r o mt h ek e y p h r a s e se x t r a c t i o nm o d u l e ， a p r i o r ia l g o r i t h mi s u s e dt of i n dm a x i m a lf r e q u e n ti t e m s e t sa n d a s s o c i a t i o nr u l e sb a s e do nv a l u e so fs u p p o r ta n dc o n f i d e n c e 。w h i c ha r e s p e c i f i e db yu s e r s a f t e rt h a t , r e l a t e dt e r m sa r ec o l l e c t e da c c o r d i n gt o a s s o c i a t i o nr u l e s ，a n dt h e y t o g e t h e rc o n s t i t u t et h e m a t i ct e r m s o u r e x p e r i m e n t ss h o wt i l a t ，t h i sa p p r o a c hi sp r o m i s i n ga n ds a t i s f y i n g ，a n d c o u l db ea c c e p t e db ym o s tu s e r s k e yw o r d s ：t e x tm i n i n g ，t h e m a t i ct e r m se x t r a c t i o n ，a s s o c i a t i o nr u l e s 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：率 论文使用授权声明 日期翌2 垒，； 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：导师签名：二逝日期： 导师签名：童镫 日期： 多吩7 。占，多 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 第一章引言 1 1 本文所研究的内容和意义 互联网的迅速发展导致如何从互联网上智能获取信息成为一个亟待解决 的问题，人们在查找和利用信息时变得越来越困难。如何从浩瀚的互联网中查 找所需要的信息? 信息检索和搜索引擎可以为人们提供方便快捷的道路。但是， 信息检索和搜索引擎往往返回给用户大量和查询无关或者关联不大的w e b 页 面和文本，因此，人们在找到若干页面和文本之后，仍旧迫切需要一种工具进 行快速浏览。鉴于此，有人提出对文本主题进行自动提取，以提高用户浏览文 本的速度和信息访问效率。 好的文本主题词可以帮助读者决定是否需要查看文章全文【5 】。因此，提取 高质量的文本主题词可节约读者宝贵的时间和精力，从而大大提高信息检索和 处理的速度。文本主题词抽取是使用计算机从文本原文中选择最能代表文章主 旨的词句，或者从预定义的词表中选取合适的词语进行填充，从而生成主题。 其目标是，为给定的文本生成富含信息量和可读性好的主题描述，有助用户快 速浏览文档，找到自己需要的信息。 为了达到上述目的，人们提出了各种方法：从预定义的领域主题词表中选 择能够代表文章内容的词，也称为指定关键词( k e y p h r a s ea s s i g n m e n t ) ；从文档 正文中抽取关键词( k e y p h r a s ee x t r a c t i o n ) ，文档经过规范化处理被分成一系列的 候选词，最后用一种有监督的学习算法确定候选词是否为关键词【1 】；在这里， 我们提出一种基于关联规则挖掘相关词的方法，使相关词和从该话题文本正文 中抽取的关键词一起，作为文本主题词。用户可以根据提供的关键词和相关词 了解w e b 页面的主题，有助于用户快速浏览页面，了解页面内容。另外，相关 词可以帮助用户扩展思路，提示用户未曾考虑到或并未掌握的相关内容，从而 更广泛、更全面地获得自己所需的信息，提高信息检索效率。比如，用户在信 息检索时提交的查询有“w i n d o w s ”和“w i n d o w ”等关键词，大多数用户认为 “w i n d o w s ”是微软公司的操作系统，因此浏览的w e b 页面中包含“m i c r o s o f t c o r p o r a t i o n ”和“b i l lg a t e s ”等关键词，这样用户提交的检索词“w i n d o w s ”与 这些描述该操作系统的文章建立了紧密的联系【3 2 】，也即与这些文章的关键词， 如“m i c r o s o f t ”，“g a t e s ”或“o p e r a t i n gs y s t e m ”等建立了关联。当包含“w i n d o w s ” 的新查询出现时，这些与其高度关联的词自然就成为补充描述用户意图的最佳 选择，即我们提供的相关词。 2 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 利用关联规则挖掘文本主题词的方法主要分为关键词抽取和相关词抽取 两大模块。在关键词抽取模块中，由于不同的b i g r a m 和t r i g r a m 在反映文本主 题的能力和重要性方面有很大差别，我们引入词性匹配方法，使富含信息量和 可读性好的t r i g r a m 和b i g r a m 优先作为关键词写入数据库。在相关词抽取模块 中，我们提出一种基于关联规则挖掘相关词的方法。关联规则最初用于发现交 易数据库中不同商品之间的联系规则，这里我们把经过噪音过滤的关键词集作 为关联规则学习的项目集，单篇文档对应的关键词作为一个项目，通过a p r i o r i 算法【8 】由频繁项集产生强关联规则，系统根据关联规则挖掘结果找出和关键词 有关的其它关键词 ，之，) 作为关键词对应文档的相关词，并和该篇文 档的关键词共同组成文本主题词。 1 2 本文的组织结构 全文共分为六章。 第一章为引言，主要给出文本主题词抽取所研究的内容和意义。 第二章重点介绍文本主题词抽取的研究现状，把文本主题词抽取分为关键 词和相关词两部分，分别给出研究背景和相关工作。另外重点讨论了基于词典、 词义和统计学习的方法用于抽取文本主题词以及一些典型的抽取系统。 第三章开始描述本文作者提出的利用关联规则挖掘文本主题词的方法，首 先给出数据挖掘中利用a p r i o r i 算法挖掘频繁项集以及关联规则的过程，其后研 究如何把关联规则挖掘应用于中文信息处理。 第四章具体介绍利用关联规则挖掘文本主题词系统，并给出实验数据、实 验背景和各种方法的评价和结果分析。 第五章给出中文文本主题词抽取在互联网舆情分析跟踪项目上的应用。 第六章小结了本文的主要工作及对未来的展望。 复旦大学硕士学位论文中文文本主题词抽取研究与应用 第二章文本主题词抽取的研究现状 2 1 关键词的研究历史和现状 关键词被定义为表示文章主题内容、信息、款目的单词或术语，它可用于 多种目的，诸如文摘，索引，标记，分类，聚类，标识，浏览和检索等 5 】。对 于单个文档，关键词可以作为文本主题，对标题的内容进行补充，加速浏览。 对于一组文档集，关键词可以用作主题索引，分类，聚类，浏览和检索等。关 键词也可用于其他类型的文档如网页，e m a i l ，新闻，杂志上的文章等。关键词抽 取还和一系列数据挖掘相关的任务都有着紧密联系，诸如文档检索，网页信息 抽取，文本聚类和摘要，人机可读索引，互动查询优化等 2 1 1 3 1 。 对于给定文档提供关键词一般有两种方法：指定关键词( k e y p h r a s e a s s i g n m e n t ) 和关键词抽取( k e y p h r a s ee x t r a c t i o n ) 。 2 1 1 指定关键词( k e y p h r a s ea s s i g n m e n t ) 随着i n t e m e t 和企业内部互联网( i n t r a n e t ) 上信息量的不断增加，人们管理： 和利用这些信息源的需求也在逐步增长。指定关键词( k e y p h r a s ea s s i g n m e n t ) 成为信息组织和管理的重要步骤之一，它被定义为：根据内容把自然语言文本 分配到一些预定义的类别中，故而也称为文本分类( t e x tc a t e g o r i z a t i o n ) ，可应用 于文本检索、定位和过滤等很多方面。在该方法中，所有的关键词来自一个预 定义的受控词表，也称为分类目录( c a t e g o r i e s ) ，再应用机器学习算法，通过一 系列的训练文档找到一种文本和类别的对应关系。具体来说就是在训练过程中， 对每个类别训练一个分类器，用属于这个类别的文档作为正例，不属于这个类 别的文档作为负例进行训练。对于测试集中的某篇文档，如果该类别的分类器 将其分为正例，则认定它属于该类别【5 】。 文本分类技术可广泛用于一些灵活、动态和个性化的信息管理任务，如对 电子邮件或文件进行实时分类，对话题进行分类以便针对不同的话题进行不同 的操作，固定目标或更灵活的基于任务的文档匹配。分类技术支持灵活动态和 个性化的结构，同时也应该支持更加综合、相对静态的分类结构。一些典型的 分类系统包括： ( 1 ) y a h o o ! 分类目录 ( 2 ) 美国国立医学图书馆( n a t i o n a ll i b r a r yo f m e d i c i n e ，n l m ) 创立的生物 医学文献目录m e s h ( m e d i c a ls u b j e c th e a d i n g s ) 4 复旦大学硕士学位论文中文文本主题词抽取研究与应用 ( 3 ) 美国国会图书馆分类系统( l i b r a r yo f c o n g r e s sc l a s s i f i c a t i o ns y s t e m s ) 下面分别对这三种分类系统进行介绍： ( 1 ) y a h o o 分类目录由1 4 个基本大类组成，包括a r t & h u m a n i t i e s ( 艺术 与人文) 、b u s i n e s s & e c o n o m y ( 商业与经济) 、c o m p u t e r s & i n t e r a c t ( 电脑与网际网 路网络) 、e d u c a t i o n ( 教育) 、e n t e r t a i n m e n t ( 娱乐) 、g o v e r n m e n t ( 政府) 、h e a l t h ( 健 康与医药) 、n e w s m e d i a ( 新闻与媒体) 、r e c r e a t i o n s p o r t s ( 休闲与运动) 、 r e f e r e n c e ( 参考资料) 、r e g i o n a l ( 家与地区) ，s c i e n c e ( 科学) 、s o c i a l s c i e n c e ( 社 会科学) 、s o c i e t y & c u l t u r e ( 社会与文化) 。 根据其拥有的信息或网站的多寡及知识组织的需要程度，每一个基本类目 下细分不同层次的次类目或子类目，愈往下的子类目中的网站其主题愈特定。 它建立了一个由类目、子类目等构成的可供浏览的相当详尽的目录等级结构。 其类目设计合理，结构完整、全面，类目等级层次鲜明，各级详略、宽泛程度 不一，从而为网上丰富的信息资源的归类，尤其是确切归类提供了基础。 ( 2 ) m e s h 是专门应用于检索系统的手工构建的分类目录，由美国国立 医学图书馆( n a t i o n a ll i b r a r yo fm e d i c i n e ，n l m ) 于1 9 7 1 年创立，是当今世界上 最大也是最权威的生物医学文献数据库。其中t h e s a u r u s m e s h ( m e d i c a ls u b j e c t h e a d i n g s ) 是一个大型的受控词表，它以标准的术语描述生物医学概念，它提供 词表中每个词的定义、注释，并体现学科体系的分类树状结构。m e s h 指引检 索者使用规范化的生物医学术语进行有效检索。 m e s h 的维护和更新由美国国立医学图书馆( n l m ) 的专家负责，他们根据 检索者提议，从大量新兴领域的科学文献中中收集未登录的主题词，为这些新 词在m e s h 中选取合适的类别，然后报告给m e s h 的专家组进行讨论。 ( 3 ) 美国国会图书馆分类系统( l c ) 由美国国会图书馆在馆长gh 普特 南主持下根据本馆藏书编制的综合性等级列举式分类法，共分2 0 个大类，其中 历史占3 个大类，军事占2 个大类，包括a 总论b 哲学、心理学、宗教c 历 史辅助科学d 历史；世界史及世界古代史e ，f 历史；美洲史g 地理、地图、 人类学、娱乐h 社会科学j 政治学k 法律l 教育m 音乐n 美术p 语言、 文学q 【自然】科学r 医学s 农业t 技术u 军事科学v 海军科学z 目录学、 图书馆学 美国国会图书馆分类系统( l c ) 类目详尽，多达2 0 多万个，使世界上类目 复旦大学硕士学位论文中文文本主题词抽取研究与应用 最多、篇幅最大的分类法，不仅可适用于综合性图书馆，而且也适用于相应的 专业图书馆。该分类法能够及时反映新学科和新主题。美国国会图书馆设有专 门部门管理l c ，根据馆藏变化及时修订类表，并按季编印发行l c 的补充和 修改，及时报道l c 类号的修订信息。 这些大型的分类系统的维护和更新需要大量的领域专家来为新的信息进 行收集和分类，作用相对有限，于是发展自动文本分类技术的需求越来越强烈， 具体可分为两类：基于规则的分类方法和基于归纳学习的分类方法。前者比较 常见，但需要人工创建规则，定义类别成员，而且改动起来比较困难；后者则 使用归纳学习技术来自动构建分类器。由于词汇的特征项超过数百万，相应地 对归纳学习方法提出了许多新的要求。最后得到的分类器应易于构建和更新， 能根据个人的要求被归入特殊的种类中，并且允许用户根据他们的任务权衡精 度和取消输入。常用的统计分类和机器学习方法包括多变量衰退模型、最近邻 分类器、贝叶斯模型、决策树和神经网络等等。 2 1 2 关键词抽取( k e y p h r a s ee x t r a c t i o n ) 关键词抽取( k e y p h r a s ee x t r a c t i o n ) q b 不存在预定义的词汇表，关键词是从文 档正文中抽取的，文档经过规范化处理被分成一系列的候选词，最后用一种有 监督的学习算法确定候选词是否为关键词。目前关键词抽取的方法主要分为以 下三种：基于词典的方法、基于词义方法、以及基于统计学习的方法。 2 1 2 1 基于词典的方法 基于词典的方法的基本思想是：将文档的种类可以按不同的领域进行划 分，一般而言，有相当一部分词它们表达文档主题特征的能力受到文档类型的 限制，针对不同类型的文档，各抽取一定量文本样本，采用一定的训练算法提 取特征词，建立针对该领域的特征词词典，以此作为文档的背景词典。在进行 关键词抽取时，根据特征词词典，并综合考虑词频、词长等信息，对文档中出 现的词进行加权，最终按照权重抽取关键词。 如下图所示： 6 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 i j 这种方法在文本自动分类、主题词提取、主题标引时经常被用到，而且效 果显著。其主要特点为：提取准确率较高，但由于受到背景词典的限制，该方 法查全率较低，而且抽取范围仅限于出现在特征词词典中的关键词，其抽取结 果直接收到背景词典的限制。 2 1 2 2 基于词义的方法 基于词义的方法的基本思想是：给定的文档是按照一定意义对词汇进行排 列组合的符号串，是围绕文献主题有关方面所做的判断、推理、结论等等，一 个词如果是关键词的话，就不可能是孤立的，围绕着它必然会展开论述，主题 关键词之间构成一个语义结构图，词语按照所讨论的关键词形成意义聚类。将 这些语义聚类划分出来，深入挖掘文献中所包含的语义信息，就可以提高关键 词的提取准确率。如下图所示： _ - - - - - - - _ - - - _ - _ - - - _ - - - - - - - - - - - - - - - - - - - - - - - i 7 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 基于词义的方法虽然在一定程度上代表了自然语言理解的发展方向，但是 这种方法实现结果直接受到用户所建立“规则库”性能的影响，还需要进行大 量的词义排歧、同义词识别工作，目前计算机在处理这些技术方面还存在着一 定的局限性。同时对于未登录词，也缺乏相应的处理机制，因此这种方法还只 能处于试验阶段。 2 1 2 3 基于统计学习的方法 基于统计学习方法的基本思想是：在表达文章主题时，起主要作用的是名 词、动词等实词，这部分词中出现频率越高，出现位置越特殊( 如标题，首段等 等) 标记、特殊提示的词，对表达文章的主题越有意义。在进行关键词提取时， 综合考虑这些特征进行加权。 下表归纳了基于统计学习方法抽取关键词中重要人物的工作： 人物代表文章 a 删 s p r i n g s y m p o s i u mo nm a c h i n e k r u l w i c h & b u r k e y l e a r n i n gi ni n f o r m a t i o n a c c e s s ，1 9 9 6 m u n o z f r a n ke t a l i n t e l l i g e n t d a t a a n a l y s i s ，1 9 9 6 i n t e r n a t i o n a lj o i n t c o n f e r e n c e o n a r t i f i c i a l i n t e l l i g e n c e ， 1 9 9 9 8 主要贡献 用启发式算法从文档中 抽取关键词，用到的特征包括 斜体字、文章段落标题、首字 母缩写词等。他们的目的是抽 取关键词用作文档分类，算法 精度较低。 用非监督的学习算法抽 取t w o - w o r d 关键词，算法基 于a d a p t i v er e s o n a n c et h e o r y 神经网络，而且只限于 抽取二元的关键词。 实现系统k e a ，把关键 词抽取作为一个有监督的学 习过程。在训练和抽取过程中 对每个候选词计算连个特征 值：t f i d f 和词语文档中的 首次出现位置，最后用b a y e s 分类算法确定候选词是否为 关键词。 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 e ta 1 i n f o r m a t i o n p e t e rd t u m e y r e t r i e v a l ，1 9 9 9 t a k a s h it o m o k i y o j i a - l o n gw ua n d a l i c em a g o g i n o a c l w o r k s h o p o nm u l t i w o r d e x p r e s s i o n s ，2 0 0 3 i e e ei n t e r n a t i o n a l c o n f e r e n c e o n s y s t e ms c i e n c e s ，2 0 0 4 2 1 2 4 特征的选取 给出关键词抽取系统 g e n e x ，该系统基于一套确定 参数的启发式规则，这些参数 通过一个基因算法来调整，基 因算法通过这些规则的参数 优化了在训练文档集中被正 确指定的关键词的数量。 t u m e y 比较了g e n e x 和标准 机器学习技术如b a g g e d d e c i s i o nt r e e s ，g e n e x 具有更 好的性能。 提出用统计语言模型抽 取关键词的方法，通过计算模 型间的k l 距离来给关键词的 p h r a s e n e s s 和i n f o r m a t i v e n e s s 程度打分，并将两个分数整合 排序。 把对整个语料集抽取关 键词作为全局最优问题进行 处理，目标是找出用于描述该 语料集的关键词的最优集合。 由于最优条件本身通常是多 面的，故而考虑采用用多目标 基因算法( m o g a s ) 。 在机器学习算法中，特征选取是极其重要的一步，好的特征能够更加正确 的代表单词本身，还能建立更好的映射。一些重要的特征包括：( 1 ) t f i d f 函 数( 2 ) 词语在文档中首次出现位置( 3 ) 词语上下文信息 ( 1 ) t f i d f 函数 首先根据向量空间模型将文档映射为一个特征向量： v ( d ) = “，w i ( d ) ；，q ) ) 9 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 其中o = 1 ，2 ，疗) 为一列互不相同的词条项，m ( d ) 为在d 中的权值，一 般被定义为在d 中出现频率斫( d ) 的函数，即) “矿( 斫( d ) ) 。在信息检索中 常用的词条权值计算方法为z f i d f 函数： 妒：绣( d ) 。l o g ( 马 啊 其中为所有文档的数目，嘶为含有词条的文档数目，下面是一个常用 的t f i d f 公式： m ( d ) = 根据z f 一仞f 公式，文档集中包含某一词条的文档越多，说明它区分文档 类别属性的能力越低，其权值越小；另一方面，某一文档中某一词条出现的频 率越高，说明它区分文档内容属性的能力越强，其权值越大。 ( 2 ) 词语在文档中首次出现位置 即被计算为在候选次第一次出现前的词的个数，用它除以该文档词的总 数。这个值是一个界于0 和1 之间的实数。 ( 3 ) 词语的上下文权值 经验分析表明，词语的上下文对关键词的抽取也有很大的作用。词的上下 文被定义为在这个词前后指定个数的词。实验一般指定次的个数为2 0 个单词， 包括其之前的十个词之后十个词。计算词的上下文的公式如下： w ：至翌 。 s i z e ( c i ) 其中是上下文中词的z f 一，d f 权值总和，s 切( q ) 是上下文中词的数 量。实验分析表明，关键词上下文总是包含具有高t f i d f 值的词。 ( 4 ) 针对w e b 页面的视觉修正系数 与纯文本数据不同，w e b 页面是一种半结构化的数据，由标记和文本构成。 在w e b 页面中对任意一个特征而言，有两个因素影响权值。从内容上分析，是 词在单个标记、h t m l 文档和整个文档集中出现的频率；另一个是该词的视觉 效果，即给人留下印象的醒目程度，这是从h t m l 的格式上分析的。 1 0 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 仔细分析h t m l 文件的格式，可以发现某些标记对网页的主题表现有突出 的贡献。例如，标题是对一篇文章的全面概括，因此其中的词作为主题词或关 键词的可能性就很大，另外一些标注为黑体或高亮的文本也往往是文章作者想 要表达的重点。因此需要引入网页结构的影响，对h t m l 标记进行分类，分别 是： 标题c l = t i t l e ) ； 段落标题c 2 = h 1 ，日2 ，h 6 ) ； 局部修饰，如字体的改变：粗体、斜体、下划线等等c 3 = b ，u ，i ， 相应地可以将一个网页中的词划分成四个集合： s = w j l w c 1 足= i m c 2 ) 墨= i c ：) 最= 叫i 嵋芒c l u c 2 uc 3 则每个词只在文档d ，中的视觉修正系数w 嘎用如下公式计算： 鹏 w a = j ，一 f r e q ( p , ，d ，) 其中f r e q ( p , ，乃) 表示词词b 在文档t 中的出现频率，w s i 为该词在各种标 记中出现时的权重，取值按如下规定： 如果f s ，则= 1 ； 如果i & ，则= 0 8 ： 如果i & ，贝0 w j = 0 7 ； 如果f 蜀，则w j = 0 5 ； 从公式可以看出，该修正系数就是该词在标记中出现的权重的平均值。 2 1 3 目前的关键词抽取系统及性能比较 ( 1 ) k e a 系统 k e a h 关键词抽取系统主要分为训练和抽取两部分。其中训练过程是用作 者指定关键词的文档作为训练语料建模，在抽取过程中用训练好的模型对于给 定的文档提取关键词，这两部分都需要先从文档中抽取候选关键词，计算特征 值。 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 候选关键词抽取主要分三步完成，首先对于输入文档进行清洗，也就是分 词，去除停用词，然后确定候选词，最后对这些候选词进行词干抽取。在训练 和抽取过程中主要对每个候选词计算两个特征：t f i d f 和单词在文档中的首 次出现位置。 前者利用向量空间模型将文档映射为一个特征向量，根据t f i d f 公式， 文档集中包含某一词条的文档越多，说明它区分文档类别属性的能力越低，其 权值越小，而某一文档中某一词条出现的频率越高，说明它区分文档内容属性 的能力越强，其权值越大。后者计算了在该文档中候选词第一次出现前词的个 数，除以文档中词的总数，得到一个介于0 和1 之间的数，用以表示该词的第 一次出现在文档中的相对位置。最后由于计算的两个特征值都是实数，在机器 学习前还需要一个离散化的过程。k e a 算法对于测试集和训练集都来自同一领 域的情况有较好的性能，但它没有考虑到抽取关键词时的语义一致性问题，如 果训练语料和测试预料分别来自不同的领域，性能会有所下降。 ( 2 ) 改进的k e a 系统 p e t e rd t u m e y 5 针对这个问题对k e a 算法进行了改进，加入了一致性特 征集。首先计算用t f i d f 和单词在文档中的首次出现位置这两个特征计算候 选关键词，对于前l 个候选关键词，分别计算它们和前k ( k ，t k ( k = l ，2 ，功称为事务( t r a n s a c t i o n s ) ，厶( 珈l - l ， 2 ，力称为项目( i t e m ) 。 设1 = i t ，f 2 ，稿是d 中全体项目组成的集合，的任何子集x 称为d 中 的项目集( 1 t e m s e t ) ，闳k 称为集合z 为k 项目集( 七一i t e m s e t ) 。设t k 和x 分别为 d 中的事务和项目集，如果x c _ t k ，称事务t k 包含项目集兄每一个事务都有一 个唯一的标志符，称为t i d 。 支持度： 设乃l 项目集厶在数据集d 上的支持度( s u p p o r t ) 是包含乃的事务在d 中所占的百分比，即 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 她吣) = 皆 频繁项目集： 对于项目集，和事务数据库d ，t 中所有满足用户指定的最小支持度 ( m i n s u p p o r t ) 的项目集，即大于或等于m i n s u p p o r t 的，的非空子集，称为频繁 项目集( f r e q u e n tl w m s e t s ) 或者大项目集( l a r g e i t e m s e t s ) 。在频繁项目集中挑选 出所有不被其他元素包含的频繁项目集称为最大频繁项目集 ( m a x i m u mf r e q u e n ti t e m s e t s ) 或者最大大项目集( m a x i m u ml a r g el t e m s e t s ) 。 置信度： 一个定义在，和d 上的形如乃j 乃的关联规则通过满足一定的可信度、信 任度或置信度( c o n f i d e n c e ) 来给出。所谓规则的置信度是指包含乃和2 的事务数 与包含厶的事务数之比，即 c o n f i d e 玎c e ( 1 ij 1 2 ) = 错 其中i i t1 2 c _ i i l n l 2 o 一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小 支持度和最小置信度来寻找关联规则的过程。关联规则挖掘问题可以划分成两 个子问题。 ( 1 ) 发现频繁项目集 通过用户给定的最小支持度，寻找所有频繁项目集，即满足s u p p o r t 不小 于m i n s u p p o r t 的所有项目子集。事实上，这些频繁项目集可能具有包含关系。 一般地，只考虑那些不被其他频繁项目及所包含的所谓最大频繁项目集的集合。 发现所有的频繁项目集是形成关联规则的基础。 ( 2 ) 生成关联规则 通过用户给定的最小置信度，在每个最大频繁项目集中，寻找c o n f i d e n c e 不 小于m i n c o n f i d e n c e 的关联规则。 3 2 核心思想 为了生成所有频集，使用了递推的方法。其核心思想如下： 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 厂核心思想 、 ( 1 ) l l = o _ a r g el - i t e m s e t s ；所有支持度不小于m i n s u p p o r t 的l - 项目集 ( 2 )f o r ( k = 2 ；l k - - f ；k + + ) d ob e g i n ( 3 ) c k = a p r i o r i - g e n ( l k o ；c k 是k + 元素的候选集 ( 4 ) f o ra l lt r a n s a c t i o n st edd 0b e g i n ( 5 )c i = s u b s e t ( c k ，0 c t 是所有t 包含的候选集元素 ( 6 )f o r a l l c a n d i d a t e s c c t d o ( 7 )巳c o u n t + + ； ( 8 ) e n d ( 9 ) l k = e eq le e o u n t r n i n s u p _ e o u n t ( 1 0 ) e n d 、 ( 1 1 ) l = u l k ； ， a p r i o r i 算法是通过项目集元素数目不断增长来逐步完成频繁项目集发现 的，首先产生1 频繁项集工j ，然后是2 频繁项集厶，直到有某个r 值使得厶 为空，这时算法停止。这里在第k 次循环中，过程先产生k 候选项目集的集合 q ，q 中的每一个项目集是对两个只有一个项不同的属于厶j 的频集做一个 ( k - 2 ) 连接来产生的。g 中的项集是用来产生频集的候选集，最后的频集厶必 须是g 的一个子集。g 中的每个元素需在事务数据库中进行验证来决定其是否 加入三i ，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能 很大的交易数据库，即如果频集最多包含l o 个项，那么就需要扫描交易数据库 1 0 遍，这需要很大的1 1 0 负载。 3 3 a p r i o r i 算法的性能瓶颈及优化 a p r i o r i 作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作 用。但是随着研究的深入，它的缺点也暴露出来。a p r i o r i 算法有两个致命的性 能瓶颈： ( 1 ) 多次扫描事务数据库，需要很大的i o 负载 对于每次k 循环，候选集q 中的每个元素都必须通过扫描数据库一次来 验证其是否加入厶。假如一个频繁大项目集包含l o 个项，那么就至少需要扫描 事务数据库l o 遍。 ( 2 ) 可能产生庞大的候选集 由l k - t 产生k - 候选集g 是指数增长的，例如1 0 4 个l 频繁项目集就有可能 产生接近1 0 7 个元素的2 候选集。如此大的候选集对事件和主存空间都是一种 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 挑战。 为了提高算法的效率，m a n n i l a 等引入了修剪技术来减小候选集g 的大小 m t v 9 4 ，由此可以显著地改进生成所有频集算法的性能。 算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的 所有子集都是频集。那么，如果g 中某个候选项集有一个o 【- 1 ) 一子集不属于厶。， 则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选 集的支持度的代价。 复旦大学硕士学位论文中文文本主题词抽取研究与应用 第四章基于关联规则挖掘文本主题 4 1 关键词抽取流程及算法 通过对输入文档进行一系列的语言学处理从而抽取所需的关键词。系统运 行分为两阶段，首先对于给定的文档，考虑它的一些语言学特征，据此抽取合 适的候选关键词，然后构造系统框架，使富含信息量和可读性好的t r i g r a m 和 b i g r a m 候选词优先作为关键词写入数据库。 具体来说，候选关键词是一些符合事先指定的语言学模型的词或词组，这 些词组可以是名词性词组，也可以是动词性词组，对于出现在文章标题和副标 题的词组相应的加大权重，然后根据计算出来的特征值对这些候选关键词或词 组进行打分，最后输出适合该篇文档的关键词。 关键词抽取流程如下图所示： 复旦大学硕士学位论文中文文本主题词抽取研究与应用 是 否 复旦大学硕士学位论文 中文文本主题词抽取研究与应用 关键函数： ( 1 ) v o i dg e n e r a t e k e y p h r a s e ( s t d ：s t d n gs t r c o 蚯g ，c s u p p o r t e r + s u p p o r t e r ) ； 与主程序的接口，对数据库中所有应该处理的类进行处理 w h i l e 话题循环( 所有新生成的话题，和有新文章加入的话题) w h i l e 文章循环属于这个话题的所有文章 i f ( ! w h e t h e r i s e n g l i s h a r t i c l e ) g e t b i g r a m ( ) ，得到符合要求的b i g r a m ，并保存b i g r a m 的出现次数词性标注与语言相 关，使用中科学分词系统 ) w 1 l i l eb i g r a m 循环 i f 这个b i g r a m 出现在t i t l e 中 出现次数+ 2 i f 这个b i g r a m 出现在r e l a t e t i t l e 中 出现次数1 5 t o p 3 k e y p h r a s e 情到出现次数最多的3 个关键词 保存数据库 ( 2 ) v o i d g e t b i g r a m ( s t d ：m a p & m s b i g r a m , s t d ：v e c t o r & v s t d g r a m , c s u p p o r t e r s u