（计算机软件与理论专业论文）基于词语网络的关键字提取策略研究.pdf

嘣南人学硕十学位论文 摘要 基于词语网络的关键字提取策略研究 计算机软件与理论专业硕士研究生阚洳沂 指导教师唐雁教授 摘要 关键字是表述文档中心内容的诃汇，是计算机系统标引论文内容特征的词汇，是便于信 息系统汇集以供读者检索的词汇。关键字提取是文本挖掘领域的一个分支，是文档检索、文 档比较、摘要生成、文档分类和聚类的基础性t 作。 关键字提取算法可分为两类：基于训练集的关键字提取策略和不需要训练集的关键字提 取策略。基于训练集的方法将关键字提取视为分类问题，通过将文档中出现的词语划分到关 键字类或非关键字类，再从关键字类中选择若干个词语作为关键字，该类算法由 p e t e r d t u r n e y 首次提出，其技术己日趋成熟。 不需要训练集的算法，可分为以下四类：基于统计的方法，如频率统计：基于词语图的 方法，如k e y g r a p h ：基于词语网络的方法，如中介性指标( b c ，b e t w e e n n e s sc e n t r a l i t y ) ； 基于s w n 的方法；上述四种方法都是建立在词频统计基础上。基于统计的方法简单快速，能 够提取高频词语，却忽略对文档具有重要意义但出现频率不高的词语，因此提取的关键字具 有片面性。基r 词语图的方法需要设定的参数过多，如顶点数、边数等，因而常造成边界上 的取舍问题，影响算法的稳定性和精度。基于s 1 ；l f n 的方法是以平均距离k 度为关键字提取依 据，而s w n 理论以连通图为基础，故对非连通的文档结构图，无法衡量顶点的重要性，也无 法正确地提取文档关键字。 本文主要研究基丁- 词语网络的关键字提取算法，在分析已有基丁词语网络的关键字提取 算法的基础上，针对存在问题，提出一个新的基于词语网络的英文文档关键字提取策略，采 用节点删除指标度量顶点( 词语) 的重要性。所提取的关键字不仅包括高频单词和短语，而 且包括对文档中心内容贡献大但出现频率不高的单词和短语。 实验数据来自k e a 乘le x t r a c t o r 算法中的测试数据集，及世界著名的科技出版集团之一 德国施普林格提供的学术期刊及电子图书的论文为测试数据。以论文作者提供的关键字 为基准，采用平均准确率和平均召同率作为衡量提取效果的依据，通过将本文算法的实验结 果与t f 和b c 算法的实验结果相比较，证明了本文算法的止确性和有效性。 关键字：词语网络共现分析节点删除指标关键字提取中介性指标 两南大学硕士学位论文 a b s t m c t r e s e a r c ha b o u tt e n nn e 似o r kb a s e d k e y w o r d s e x t r a c t io ns t r a t e g y m a jo r ：c o m p u t e rs o f 撕a r ea n d t h e o r i e s a u m o r ：k a nr u y i s u p e r v i s o r ：p r o ft a n g y a n a b s t r a c t w i t ht l l ea d v e n to fh l t e m e ts i n c el9 9 0 ，w eb a v es e e nat r e m e n d o u s 黟。叭hi nt l l ev 0 1 u m eo f o n l i n et e x td o c u m e n t sa v a i l a b l eo nt h ei n t e m e t ，s u c ha se l e c t r o n i ce r m i l s 、w e bp a g e s 、a n dd i 酉t a l b o o k se ta l ，t bm a l ( em o r ee 矗e c t i v eu s eo ft h e s ed o c u m e n t s ，t h e r ei si n c r e a s i n g l yn e e df o rt o o l st o d e a lw i t ht e x td o c u m e n t s t bm e e ts u c hi n c r e a s i n g l yn e e d s ，s o m ep r o d u c tf o ra n a l y z i n gt e x t d o c u m e n t sh a sb e e nd e v e l o p e d a l lt e c h n i q u e si n v o l v e di nd o c m l l e ma 1 1 a l y s i sh a v ef o n l l e dan e w e x c i t i n gr e s e a r c ha r e ao r e nc a l l e da st e x tm i i l i n g k e y w o r d se x 觚c t i o np l a y sav e d ri m p o r t a n tr 0 1 e i nm et e x tm i l l i n gd o m a i n ，b e c 孤s e k e y w o r d sa r e u s e 如lf o rav 撕e t yo fp u 叩o s e s ，i n c l u d i n gs u i i l l 【i l a r i z i n g ，i n d e x i n g ，l a b e l i n g ， c a t e g 耐z i n g ，c l u s t e d n g ，l l i g h l i g h t i n g ，b r o w s i i l g ，a n ds e a r c h i n g t h et a s ko fa u t o m a t i ck e y w o r d e x 仃a c t i o ni st 0s e l e c tk e y w o r d sf 硒mt h et e x to fa 百v e nd o c u m e n t a u t o m a t i ck e y w o r d se x t r a c t i o n m a k e si tf - e a s i b l et og e n e r a 把k e y i o r d sf o rm eh u g en u 倒b e ro fd o c u m e n t st i 斌d on o tt l a v e m a n u a l l ya s s i g n e dk e ) w o r l s t h e f ea r es o m ep r e v i o u sa p p r o a c h e so nk e y w o r d se x t r a c t i o n ：1s u p e n ，i s e dc l a s s i f i c a t i o n ， t ! 啪e yf i r s t l ya p p r o a c ht h ep r o b l e mo fa u t o m a t i c a l l ye x t m c t m gk e y w o r d sf b mt e x t 弱a s u p e r v i s e dl e 锄i n gt a s k ，h et r e a t sad o c u m e n ta sas e to fp h l a s e s ，w h i c hm el e a m i n ga l g o r i t i l m i 硼s tl e a mt oc l a s s i 母a sp o s i t i v eo rn e g a t i v ee x 锄p l e so fk e y w o t d s r h ep e r f o r m a n c eh a sb e e n s a t i s f a c t o d ，f o raw i d ev 撕e t yo fa p p l i c a t i o n s 2u n s u p e r v i s e dc l a s s i f i c a t i o n ，t h e s ek e y w o r d s e x t r a c t i o na l g o r i t st h a t 印p l i e st oas i n g l ed o c u m e n tw i t h o u tu s i n gac o 印u sa r ep r e s e n t e d ，s u c h a st e n nf 沱q u e n c y ，b a s e do ns w n ，t h et e 彻g r a p h ，t h et e r mn e t w o r k b a s e do nt h ea n a l y s i so fe x i s t i n gk e y w o r d se x t r a c t i o nu s i n gt e mn e t w o r k ，a ne 仃e c t i v c a l g o r i t h mi sp r o p o s e dt oe x t r a c tn o to n l yh i g hn q u e n tt e m l s ，b u ta l s oi m p o n a n tt e m sw i t hl o w 雠q u e n cy i tb a s e so nt h et e 彻n e t 、o r ka i l dd e l e t i n ga c t o ri n d e x t h ee x p e r i m e n tr e s u l t ss u p p o r t t h ec o n c l l ls i o n k e y w o r d s ：d e l e t i n ga c t o r ；c o o c c u r r e n c e ；k e y w o r de x t r a c t i o n ；t e r mn e t w o r k ； b e t w e e n n e s sc e n t r a l i 坶 独创性声明 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感谢。 学位论文作者：阑洳气 签字日期：参呻g 年5 月细日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名：1 鞫；如；弓 签字日期：舢g 年5 月弓。日 导师签名： ) 7 芬函 签字日期：加& 年r 月? 口日 曲南人学硕十学位论文 第一章绪论 第一章绪论 1 1 研究背景 随着信息技术的普遍应用，人类获得数据的能力不断增强；据有关统计，在 全世界的业务管理、政府管理、科学与二 程管理和其他应用领域存在大量数据， 并且其数量和规模不断地增加和扩大。然而，如何利用这些海量数据，如何从数 据中提取有用的信息，是经营管理者面临得一个共同难题。为解决这个难题，有 关人员提出一系列技术和方法，这些技术和方法就是数据库知识发现，又称为数 据挖掘技术 1 ，目的就是智能化和自动化地发现隐藏的信息和知识，发现先前 未知的模式，能从历史数据中预测未来发展趋势。它是一个交叉学科领域，受多 个学科影响，包括数据库系统、统计学、机器学习、可视化和信息科学。 数据挖掘的研究对象主要针对结构化数据，如关系的、事务的和数据仓库的 数据。然而，现实世界中大部分可获取的信息存储在文本数据库，文本数据库由 各种数据源( 如新闻文章、研究论文、书籍、数字图书馆、电子邮件消息和w e b 页面) 的大量文档组成。随着网络技术的发展，电子形式的文本信息量飞速增长， 如电子出版物、电子邮件和万维网资源( 它可被视为一个巨大的、互连的动态文 本数据库) 等，文本数据库被广泛地应用。当数据挖掘的对象是文本数据时，这 个过程被称为文本挖掘 2 ，3 。 文本是半结构化数据，既不是完全无结构也不是完全结构化，例如：一篇文 档可能包含结构化字段，如标题、作者、出版同期、长度等，也可能包含大量的 非结构化的文本成分，如摘要和内容。文本半结构化的特性使得常规数据挖掘的 挖掘效果不佳。因此，文本挖掘采用的方法与传统的数据挖掘不同，它的方法主 要来自于自然语言理解处理等领域。 关键字是表述文档中心内容的词汇，是计算机系统标引论文内容特征的词 汇，是便于信息系统汇集以供读者检索的词汇，由于它的出现和发展，使得计算 机检索成为可能。关键字提取是文本挖掘领域的一个分支，是文档检索、文档比 较、摘要生成、文档分类和聚类 4 的基础性工作 5 。 1 2 研究现状 随着信息技术的飞速发展和互联网的普及，文本数据库呈现出几何级数的增 长。除学术论文包含关键字外，大量的文档没有关键字，尤其是互联网上的众多 网页。语言专家手工提取关键字，其准确率较高，但对海量文档信息手工提取是 一个繁重并不可行的方法。如果能采用人工智能的方法提取关键字，会大大地提 高效率，为此国内外学者提出多种关键字自动提取算法。这些算法依据是否需要 f q 南人学硕f j 学位论文 第一章绪论 训练集，可分为两类：基于训练集的关键字提取策略 6 1 1 和不需要训练集的关 键字提取策略 1 1 一1 9 ，下面将概括地介绍这两类算法： 1 2 1 基于训练集的关键字提取策略 该类算法将关键字提取视为分类问题，通过将文档中出现的词语划分到关键 字类或非关键字类，从关键字类中选择若干个词语作为关键字。该类算法由 p e t e r d t u r n e y 8 首次提出，采用c 4 5 决策树作为分类器。稍后i a n i w i t t e n 1 0 等人采用n a x v eb a y e s 作为分类器。该类算法都是基于已有关键字 的训练集，选取适当的属性描述文档中的词语，由分类算法构造分类模型，在利 用分类模型提取关键字。该类算法提取的效果取决于所选训练集、分类算法和描 述属性。 1 2 2 不需要训练集的关键字提取策略 1 基于统计的算法 该类算法，如频率统计 1 2 】( t f ，t e r mf r e q u e n c y ) ，统计文档中每个词语出 现的频率( 停用词除外) ，选取频率超过一定阈值的词语为关键字。该类算法简 单快速，能够提取高频词语，却易忽略对文档具有重要意义但出现频率不高的诃 语，因此提取结果具有片面性。 2 基于词共现图的算法 该类算法 1 3 ，1 4 ，如k e y g r a p h 1 3 ，建立在词频统计基础上，将词语及其语 义关系映射到词共现图，n 个顶点的词共现图只能包含n l 条边。利用该图计算 每个顶点的k e y 值 1 3 ；k e y 值的大小代表顶点的重要性，选取若干个重要顶点， 即为该文档的关键字。该类算法旨在找出出现频率不高但对中心内容贡献大的词 语，但算法需要设定的参数过多，如顶点数、边数等，因而常造成边界上的取舍 问题，影响算法的稳定性和精度。 3 基于s w n ( s w n ，s m a l lw o r l dn e t w o r k ) 的算法 该类算法 1 5 ，1 6 ，如k e y w o r l d 1 5 ，建立在词频统计基础上，将词语及其语 义关系映射到文档结构图( 若边代表文档中词语之间的共现关系，则可称为文档 共现图) ，又称为词语网络。通过研究发现该结构图具有小世界特征，该类算法 认为文档关键字是对该文档结构图的小世界特性起关键作用的词语，小世界特性 的标准是网络平均路径长度 1 7 ( l ，a v e r a g ep a t hl e n g t h ) 。 4 基于词语网络的算法 该类算法，如基于b c 指标的词语网络关键字提取算法 1 8 ，建立在词频统计 基础上，将词语映射成为顶点，将其语义关系映射为边，包含n 个顶点的无向词 语网络，其边数的取值范围为 0 ，n ( n + 1 ) 2 。利用节点重要性的度量指标量化 2 曲南人学硕十学位论文第一章绪论 节点重要程度，如中介性指标( b c ，b e t w e e n n e s sc e n t r a lit y ) ，提取若干个重要 的顶点，即为文档关键字。 1 3 研究内容和创新点 概括起来，本文主要有以下两个方面的工作： l 、分析现有的词语网络关键字提取算法，针对其存在问题，提出一个新的 基于词语网络的英文文档关键字提取算法，采用节点删除指标【1 9 】度量节点( 词 语) 的重要性，该指标是考察删除顶点后网络连通的变化状况，从动态角度反映 顶点对保持整个网络的连通所起的作用。所提取的关键字不仅包括高频单词和短 语，而且包括对文档中心内容贡献大但出现频率不高的单词和短语。选取候选关 键字时考虑单词和短语的比例问题，从而提高关键字提取的准确率和召回率。 2 、为证明本文算法的正确性，将本文算法的实验结果与t f 和b c 算法的结 果相比较，以论文作者提供的关键字为基准，采用平均准确率和平均召回率 1 4 作为衡量提取效果的依据。 本文的创新点在于将节点删除指标运用到关键字提取策略，所提取的关键字 不仅包括高频单词和短语，而且包括对文档中心内容贡献大但出现频率不高的单 词和短语。选取候选关键字时，考虑单词和短语的比例问题；通过实验发现单词 和短语的比例为1 ：1 时提取的效果最佳。 1 。4 论文结构 本文一共分六个章节，下面分别说明各个章节的内容： 第一章：本章前半部分概括地阐述文本挖掘的重要性，及关键字提取在文本 挖掘中的重要作用，后半部分总结现有的关键字提取算法。 第二章：本章介绍基于词语网络关键字提取策略的两个重要阶段中所涉及的 相关概念：、文本预处理阶段中停用词、词根、短语、评估函数；二、词语网 络的定义及计算机中的存储结构。 第三章：本章详细地介绍相关理论：一、共现分析的理论依据，比较共现分 析与其它关系后明确其在文本挖掘中的作用；二、复杂网络的发展、网络可视化 方法、复杂网络的若干统计特性和小世界网络在自然语言中的应用；三、两个网 络顶点度量指标，从不同的角度度量网络中顶点的重要性。中介性指标从静态角 度反映顶点对其他顶点之间沟通的控制能力，以控制能力的强弱作为顶点重要程 度的标准；节点删除指标从动态角度考察删除顶点后网络连通的变化状况，以连 通性的强弱作为衡量标准。 第四章：从文本预处理、词语网络的构造、关键字的提取依据，分析已有的 三种基于词语网络关键字提取算法，发现其存在的不足。 西南大学硕士学位论文 第一章绪论 第五章：本章针对其中的三个问题，提出一个新的基于词语网络的关键字提 取策略基于节点删除指标的关键字提取算法。选取候选关键字时，考虑单词 和短语的比例问题。 第六章：为验证基于节点删除指标的关键字提取算法的有效性，搭建实验平 台。对比与t f 、b c 算法的实验结果，证明该提取算法的有效性。 4 晴南人学颂士学位论文 第二章相关概念 第二章相关概念 关键字提取算法可以分为以下两类：一、不需要训练集的关键字提取算法， 主要处理过程是文本预处理、衡量候选关键字的重要性、提取前m 个作为文档关 键字；二、基于训练集的关键字提取算法，主要处理过程为文本预处理、训练集 构造分类模型、分类模型进行关键字提取。上述两类方法都涉及关键字提取过程 的若干相关概念，如文本预处理中的停用词、词类、词根、短语概念，本文主要 研究基于词语网络的关键字提取策略，所以还涉及词语网络的表示、存储和可视 化技术等，本章将详细地介绍这些相关概念。 2 1 文本预处理相关概念 文档中的数据是半结构化数据，既不是完全无结构的也不是完全结构化的， 例如：一篇文档可能包含结构字段，如标题、作者、出版日期、长度等，也可能 包含非结构化的文本成分，如摘要和内容。文本预处理除处理结构化字段和非结 构化的文本成分，还需处理其中蕴涵的复杂语义，因此无法直接运用现有的数据 挖掘技术。为挖掘非结构化数据，提出以下两条解决途径：一、探索适用于非结 构化数据挖掘的新方法，；二、先将非结构化数据转换为结构化，再利用现有的 数据挖掘技术进行挖掘，已有的文本挖掘主要采用该途径。语义关系需运用计算 语言学和自然语言处理等领域的知识，或利用基于统计的共现分析获得词汇之间 的语义关系。 英文文档的预处理技术分为：去停用词、提取词根、识别短语、基于评估函 数的特征筛选、特征提取。去停用词和提取词根可以减少文章中的单词数量，从 而减少计算的复杂度。 2 1 1 停用词 停用词 1 被认为是一组“无关的”词，例如t h e 、a 、o f 、f o r 等都是停用 词。这些词在所有的文档中出现频率较高，却不能反应文档的主题，所以不易作 为关键字。执行关键字提取算法前需建立一个包含这些“无关词”的表，称为停 用词表。不同文档集的停用词表也不同，例如，报纸中“数据库系统”可能是一 个重要的关键字，而在数据库系统会议的研究论文中可能就是无用词。 2 1 2 词类 词类 2 0 ( p o s ，p a r to fs p e e c h ) 又称为词的分类、形态类或词汇标记。词 类对语吉信息处理的意义在于提供该单词邻近成分的大量信息；如知道一个词是 主有代词还是人称代词，就能知道什么词会出现在它的近邻，因为主有代词后面 会出现名词，人称代词后面会出现动词。词类还能提供单词发音的信息，例如单 曲南人学硕十学位论文第一二蕈相关概念 词c o n t e n t 为名词或形容词，其发音是有区别的：如果知道单词的词类，在语音 合成系统中就可以产生自然的声音。信息检索中提取词根，可提高信息检索的速 度。目前，己提出的词类标准有：t h r a x 的8 类、p e n n 树库的4 5 类、b r o w n 语 料库的8 7 类和c 7 标记集的1 4 6 类。本文采用t h r a x 的8 个词类 2 0 ：名词、动 词、代词、介词、副词、连接词、分词和冠词。 2 1 3 词根 英语形态学研究如何从较小的意义单位( 语素) 构成词，语素被定义为语言 中负荷意义的最小单位，例如f o x 只包含一个单独的语素，即语素f o x ，而c a t s 词包含两个语素：一个是语素c a t ，另一个是语素一s 。语素分为词根( s t e m ) 和 词缀( s u f f i x ) 两大类，词根是词的主要语素，提供主要的意义，而词缀提供“附 加”意义。 词缀分为前缀( p r e f i x ) 和后缀( s u f f i x ) ，前缀位于词根之前，后缀位于 词根之后，例如单词e a t s 由词根e a t 和后缀一s 组成，单词u n c l e a n 由词根cl e a n 和前缀u n 组成。一个单词可以同时有前缀和后缀，还可以有多个前缀和后缀， 例如单词r e w r i t e s 由前缀r e 一，词根w r i t e 和后缀一s 组成，单词u n b e l i e v a b l y 具有一个词根以及三个词缀( u n 一、一a b l e 和一l y ) ，英文中的词缀一般不超过5 个。 语素构成单词的方法可分为两大类：屈折 2 0 和派生 2 0 。屈折由词根和一 个语法语素构成，新单词与词根属于同一个词类。例如，英语的屈折语素一s 表 示名词的复数，屈折语素一e d 表示单词的过去时态。派生也由词根和一个语法语 素构成，但新单词与词根属于不同的词类，新单词的意义常常难以精确地预测， 例如动词c o m p u t e 加上后缀一a t i o n ，形成名词c o m p u t e r i z a t i o n 。 1 屈折形态 英语具有相对简单的屈折系统，只有名词、动词和部分形容词有屈折变化， 屈折词缀数较少。 英语名词的屈折词缀只有两个：一个表示复数，另一个表示所属。例如，英 语名词或者单独以词根的形式出现，或者带有一个复数后缀。表2 一l 是规则的复 数后缀一s 、变异的拼写形式一e s 以及不规则的复数形式： 表2 1 规则名词不规则名词 单数c a tb o xm 0 u s e0 xf i s h 复数 c a t sb 0 x e sm i c e0 x e nf i s h 大多数名词是规则复数，直接在名词后加一s ；以一s ，一z ，一s h ，一c h 和部 分一x 为结尾的名词后加一e s ，如表2 一l 所示；以一y 结尾的名词，若一y 前是辅音， 6 两南人学硕十。学位论文 第二章相关概念 贝0 一y 改一i ，然后力日一e s 。 所属后缀，规则单词名词和不以一s 结尾的复数名词直接加s ；规则复数名 词后以及部分以一s 或一z 结尾的人名加一个单独的省略符( ) 。 英语动词的屈折变化多于名词的屈折变化，因为英语有三类动词：主要动词 ( 如e a t 、w a l k 和t r y 等) 、情态动词( 如c a n 、w i l l 和s h o u l d ) 和基本动词( 如 b e 、h a v e 和d o ) 。对于主要动词，只要知道词根就能预见它的其他形式；先进行 有规律的拼写变化，再直接加上词缀一s 、一i n g 或一e d 。对于情态动词和基本动 词，屈折变化成特定的形式，新单词最多具有8 个不同形式( 例如，动词b e ) ， 最少具有3 个不同形式( 例如，c u t 或h i t ) 。 2 派生形态学 英语的派生相当复杂。因为派生的能产性比较低，如一a t i o n 名词化后缀只可 加在大部分以一i z e 结尾的动词后，其次名词化后的意义与词根意义有细微的差 别，例如s i n c e r i t y 和s i n c e r e n e s s 的意义之间就有细微的差别。 如何提取单词的词根呢? 为解决这个问题，已经提出许多词根提取算法。词 根提取时只考虑去掉单词的后缀，因为加前缀的新单词与词根的意义往往不同。 词根提取算法可归纳为以下两类：一、基于词典的方法，需要列举出该语言 的所有词汇；所以计算机词表除包括单独的词干和词缀，还需包括形态顺序规则， 即告诉怎样把词干和词缀组合起来，无论屈折形态学还是派生形态学都能提取正 确的词根；但面对不断出现的大量新词，需要及时地更新词典和规则，使得实现 较困难。二、基于规则方法，如p o r t e r 算法，简单有效；该方法建立在简单的 层叠式重写规则基础上，可正确提取屈折形态学的规则名词和屈折形态学的所属 后缀，但无法提取屈折形念学中不规则名词的复数形式，提取派生形态学中的部 分单词也会出错，如p o r t e r 算法提取o r g a n iz a t i o n 和o r g a n 的词根都为o r g a n ； 但该类提取算法简单有效，所以被广泛地使用在文本预处理阶段。 2 1 。4 短语 文档由句子构成。句子的意义表达文档的思想，句子的意义不仅仅依赖于句 中的词汇，还依赖于句中词汇的顺序、词汇所形成的群组和词汇之间的关系，所 以短语能更好地概括一篇文献的主题。从文档中识别哪些短语，以及如何识别短 语 2 1 。 短语可以分为名词短语 2 2 、动词短语和介词短语。名词短语作为句子的主 语和宾语，是动作的发出者和承受者；动词短语作为句子的谓语成分，表示发出 何种动作；介词短语作为句子的状语，表示发生事情的时间和地点等。名词短语 和动词短语是表达句子意义的重要部分；介词短语是对表达意义起修饰和辅助作 7 朗南人学颂十号：位论文第二苹相关概念 用，其重要性不如名词和动词短语，不能较好地概括文献的主题。所以提取的关 键字应该选择名词短语或动词短语。 短语的识别规则分为以下两类：一、词性标注的短语识别规则，是基于人工 书写或( 半) 自动获取的语法规则标注短语的边界和类型。手工书写规则费时费 力又无法覆盖所有语言现象；从语料库自动或半自动地获取规则，将面对如何获 取以及规则排序等问题。二、共现规则，由词语之间的共现关系反映其语义联系， 规则简单且提取效果好；但其只考虑词语之间是否存在某种语义关系，而不考虑 具体的语义关系，如e a tf i s h 是动宾关系，f i s he a t 是主谓关系。 2 1 5 评估函数 评估函数可以分为两类： 一、基于文档集，t f i d f 2 3 是基于文档集的评估函数，由两部分组成：一 个是词语i 在文档d 中的频数t f ；( d ) ；另一个是文档频率的倒函数i d f ；的对数， 目的是调整t f ；( d ) 的值。公式如下： t f i d f i ( d ) = t f i ( d ) i d f i i d f i = 一j o g2 ( d 砸) n ) 其中d f ( i ) 表示词语i 出现的文档总数，n 表示文档集中总文档数。 i d f i 调整权值的目的是突出主要词语，抑制次要词语。例如，“数据库系统 在报纸中是一个重要的关键字，但在数据库系统会议的研究论文中就是次要词。 i d f 在计算权值时都是以训练集中总文档数为基，所以当某类文档数相对较少时 分类结果便容易出错。 二、独立于文档集的方法，最简单的是t f 评估函数，t f ；( d ) 为词语i 在文档 d 中的频数。该权值只考虑高频率词语对文档主题的贡献，而忽略对文档具有重 要意义但出现频率不高的词语，因此提取的关键字具有片面性。为解决这个问题， 不少学者选用词语的位置调整权值，此改进方法对包含格式的文档提取效果较 好，例如h t m l 格式的网页，但是对于一般的t x t 格式的文档，由于无法准确地 分析文章的结构故不适用。 2 2 词语网络相关概念 k e y w o r l d 算法 1 5 首先提出由词语网络g 表示文档d 的主要内容，顶点表示 文档中的词语，边表示文档中词语间的关系。词语网络不仅能反映文档的内容， 还可反映文档的总体结构和语义结构。下面将介绍词语网络的定义及计算机中的 存储方式。 阳南人学硕十学位论文 第二章相关概念 2 2 1 词语网络的定义 k e y w o r l d 算法 1 5 首次提出由词语网络g 表示文档d 主题，因为文档主题 由一系列子主题组成，子主题的中心词语和连接两个子主题的词语就是文章的关 键词语，即关键字。词语网络建立在以下假设之上：如果在大规模语料中两个词 经常共同出现在同一窗e j 单元，则认为这两个词在语义上是相互关联的；共现频 率越高，相互问的关联越紧密。由词之问的关联性可构造文档的词语网络。 图论中图的定义g = v ，e ) 。文档d 对应的词语网络g ，顶点代表词语，边由 满足一定关联度的两顶点组成。 顶点集，是d 中词频高于指定阈值的词语。因为文档中的高频词语可反映作 者的主要思想，同时去除频率过低的词语可降低计算复杂度。 边集，是顶点集中满足一定关联度的两项点的连接。 词语网络可以选择有向图还是无向图，或带权图还是不带权图。计算权重主 要有以下两种方法：一、通过句法分析得到不同的句法关系，依据句法关系赋予 不同的权值；二、通过连续序列词计算词语共现的频率，该频率作为边的权值。 对于有向图，边的方向可表示词语之间的句法关系，例如：“e a tf i s h ”和“f i s h e a t ”将用两条有向边表示。对于无向图，只考虑两者之间是否存在某种语义关 系，而不考虑其具体关系，例如：“e a tf i s h 和“f i s he a t ”只用一条边表示。 2 2 2 词语网络的存储方式 数据的逻辑结构到计算机存储器的映像有多种不同的方式，最主要的两种 是：一种是顺序存储方式，另一种是链式存储方式。图的结构比较复杂，任意两 个顶点之间都可能存在联系，因此无法以数据元素在存储区的物理位置表示元素 之间的逻辑结构，即图没有顺序映像的存储结构，但可借助数组类型表示元素之 间的关系。多重链表是一种最简单的链式映像结构，即一个数据域和多个指针域 表示图中顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。 但图中各个顶点的度数不相同，最大度数和最小度数可能相差很多。若以度数最 大的顶点设计结点结构，会浪费很多存储单元；若以每个顶点的度数设计其结点 结构，又会给操作带来不便。因此实际应用中不宜采用多重链表结构，应根据具 体的图设计恰当的结点结构和表结构，下面给出两种常用存储图的数据结构：数 组表示法和邻接表法。 1 、数组表示法 两个数组分别存储数据元素( 顶点) 信息和顶点之间关系( 边或弧) 的信息。 数据元素信息可以存放于一维数组，顶点之问的关系信息存放于一个n 阶方阵， 9 p q 南人学硕十学位论文第二苹相犬概念 其中n 为顶点个数。对无权图，n 阶方阵的存储内容如下： 1 若( vv ) 或 是中的边，且i j 4 f 】 刀= foi = j 若( vv ) 或 不是e 中的池且i j 由邻接矩阵的定义可知无向图的邻接矩阵是对称的，有向图的邻接矩阵就不 一定对称了。借助于邻接矩阵，很容易判定任意两个顶点之问是否有边( 或弧) 相连。对于无向图的存储可以采用压缩存储的方式，只存储矩阵的下三角( 或上 三角) 元素。 对带权图，n 阶方阵的存储内容如下： w若( v ，v ) 或 是中的边，且i j 逍f 】 刀= foi = j 若( vv ) 或 不是e 中的迅且i j 构造一个具有n 个顶点和e 条边的无向图g 的时间复杂度为d ( 陀2 + 刀p ) ， 其中对邻接矩阵的初始化耗费了d ( 咒2 ) ，存储空间为d ( 刀2 ) 。可以随机地存取表 中任意一个顶点的信息以及边的信息。 2 、邻接表 邻接表是图的一种链式存储结构。邻接表为图的每个顶点建立个单链表， 第i 个单链表中的结点表示依附于顶点v ，的边( 对有向图是以结点v i 为尾的弧) 。 邻接链表中表结点和表头结点的结构，如下所示： 表结点 l 垒壁丝兰l 坚型竺i ! 生l r 。1 。r 。1 表头结点 叵正画习 其含义为： a d j v e x 指示与顶点v ；邻接的顶点序号； n e x t a r c 指示下一条边或弧的结点； i n f o 存储和边或弧有关的信息，如权值等； d a t a 存储顶点v 。的名或其他有关信息； f i r s t a r c 指示链表中的第一条边或弧。 表头结点( 可以链相连) 通常以顺序结构的形式存储，以便随机访问任意结 点的链表。建立邻接链表的时间复杂度为d ( ，l + p ) ，需要通过查找才能得到结点 在图中的位置，则时间复杂度为d ( 刀p ) 。 1 0 西南人学硕_ f 学位论文第二章相关理论 第三章相关理论 本章详细地介绍三个相关理论，它们是词语网络构建和分析的基础理论。3 1 节介绍共现分析的含义、理论基础及在文本挖掘中的作用，3 2 节介绍复杂网络 的发展、统计特性及网络可视化，3 3 节介绍两个网络顶点度量指标：b c 指标 和节点删除指标。 3 1 共现分析 由于文本的半结构化特性，现有的成熟的数据挖掘技术无法发现文本中蕴含 的大量信息；针对文本数据库内容的特殊性，提出许多文本挖掘方法。在众多文 本挖掘方法中，共现分析 2 4 ，2 5 ( c o o c c u r r e n c e ) 以科学的分析原理、简便 的操作流程和客观的分析结果，逐渐受到文本知识挖掘人员的青睐。该方法以文 本的最小内容单位词汇为分析对象，挖掘词汇语义，以此为基础实现文本内 容的有效表示；并能对大规模文本集合进行文本精练和知识提取，可完成文本总 结、文本分类、文本聚类、关联分析、分布分析及趋势预测等多种文本挖掘任务。 3 1 1 共现分析的含义 p r i n c e t o n 大学开发的w o r d n e t 语义词典对共现提出了两种定义 2 4 ：一、 作为一个抽象名词，可以理解为同时发生两个事物的当时属性；二、作为普通名 词，表示同时发生的事件或情形、相互关联的事件或情形。可见事物的相互关联 是共现发生的内在原因，而共现现象是事物相互联系的外在表现。所以，共现现 象可了解事物之间联系的强弱。 ： 实质上，共现分析是文档中词汇分布特征的统计，是对词汇语义的认识。提 取语义信息有何意义? 全信息理论认为，不仅要了解信息的形式，更重要的是理 解信息的含义( 语义信息) 和信息的效用( 语用信息) ，语法信息涉及词汇的语 法特征，语义信息描述词汇的语义内涵。通过分析作者选用的词汇及词汇在文档 中表达的概念，最终获得如何对词汇信息有效利用的知识，上升到全信息理论的 语用理解上。 共现分析建立在以下假设基础上：如果在大规模语料中两个词经常共同出现 ( 共现) 在同r 一窗口单元( 如一定词语间隔、一句话、一个自然段、一篇文档等) ， 则认为这两个词在语义上是相互关联的，而且共现的频率越高，其相互间的关联 越紧密。 3 1 2 共现分析的方法论基础 共现分析是挖掘词汇语义的有效方法之一。共现分析的提出和发展是一个不 断从相关的学科理沦和方法中吸收、演化和改进的过程。心理学中的邻近理论和 西南人。予：硕士学何论文第二章相关理论 社会学中的知识结构及映射原理是共现分析的两大理论基础 2 4 。 心理学邻近理论认为：曾经在一起感受过的对象往往在想象中也联系在一 起。以致想起它们中某一个的时候，另一个对象也会以曾经同时出现的顺序被想 起；换句话说，只有存在语义关联的词汇，才能被作者在相邻的位置记录下来。 以此理论为基础，统计文本中词汇的共现频率，即可衡量诃汇与词汇之间语义联 系的强弱。 社会学把科研人员描述为：将技术、概念、社会和经济等因素整合成一个整 体工作的参与者。为证明他们的某些发现、方法、程序等是可信的，他们发表文 章，并利用科学文献反映实验室中设计好的世界，并把这些文档作为研究工作的 一部分。文档成为科研人员表达观点、揭示知识的重要工具，词汇是表达文献内 容的最小单元，从事某一领域研究的科学家，虽然有不同的社会和知识背景，但 对同一研究课题和概念所使用的词汇总是趋于一致。从文档的词汇出发，以文档 中的词汇为研究对象，获得词汇之问的关联关系，构成“有意义的实体”。这些 “有意义的实体”作为子主题，或子主题之间的联系，构建一个描述文档内容的 文档结构图。 3 1 3 共现分析在文本挖掘中的作用 共现分析在文本挖掘中发挥的作用 2 6 包括三个方面：一、为文本知识挖掘 的一般处理过程提供语义支持：二、从词汇关联角度发现有趣的知识模式；三、 作为文本挖掘的有效手段。 获取和利用语义知识是提高文本挖掘准确率和处理效率的重要方式。从语言 学角度分析文本、获取语义需要构建完备的语义知识库，其实现过程比较复杂。 因此研究人员考虑利用共现分析获取语义的可行性，共现分析运用相对简单的统 计方法，分析文本中词汇的分布特征，根据共现词汇之间的关联性来把握词汇之 间的语义联系。原理科学，实现简单，并能够根据文本所属领域得到该领域内独 特的词汇语义关系，这种分析方法被广泛地运用于多种类型的文本处理过程。 3 1 4 共现分析与其它方法的比较 除利用共现分析分析词语之间的关系，还有其它方法 2 7 可以获得词语之间 的关系。例如：连续序列词 2 0 ，2 8 ( 如n g r 锄) 、句法关系 2 0 。下面将分别 介绍这两种方法，并将它们与共现分析相比较。 1 连续序列词 连续序列词的共现可以看成是n g r a m 的归纳。该方法采用如下公式来计算 一个完整单词串( 我们把单词串表示成w w n ，或者表示成w 。“) 的概率： p ( w ，”) = p ( w ，) p ( w ：1w ，) p ( w 。1w ，2 ) p ( w n l w ，”) 1 2 砷南入学硕十学何论文第二苹相关理论 当日i 面给定的单词序列较长时，为简便地计算概率p ( w nw 。”1 ) ，提出一个逼 近方法，该方法为：只需计算当前给定的单词是一个单独的单词时，连续序列单 词的概率是多少，用一个单词来逼近给定的所有单词的概率，这就是“二元语法 模型”( b i g r a mm o d e l ) 。通过前面一个单硼的条件概率p ( w n l w n 一1 ) 来逼近前 面给定的所有单词p ( w nw 。”1 ) ，即计算一个连续单词串出现概率，采用如下的 逼近公式： p ( w ，“) p ( w ，) p ( w ：lw ，) p ( w 。1w ：) p ( w n l w n - ，) 可把二元语法模型( 只看过去的一个单词) 推广到三元语法模型( 看过去的 两个单词) ，再推广到n 元语法模型( 看过去的n 一1 个单词) 。 统计模型中的概率来自训练它的语料库，该训练语料库需要精心设计。如果 训练语料库太偏向于某个任务或某个领域，概率可能太窄；如果训练语料库太泛， 概率不能充分地反映有关任务或领域的特点。 2 句法分析的词语共现 句法分析的词语共现是基于词性标注和句法分析的语料。词性标注( p o s t a g g i n g ，p a r t o f s p e e c ht a g g i n g ) ，是文档中每个单词指派一个词类或者标 记词类的过程。通过句法分析得到词语问的关系，如动词和宾语，形容词和名词 等。 词类标注是为每个单词指派一个词类，但英语中最常用的单词大部分是有歧 义的，例如：c a n 可作为助动词表示“能够”，也可作为名词表示“罐头”，还可 作为动词表示“把某个东西装进罐头”。那么如何根据具体情况，指定正确的词 类并消除歧义成为词类标注所要解决的问题，为此提出了很多算法，可以归纳为 以下两类：一类是基于规则的标注算法，手工制作歧义消解规则，这些