（计算机软件与理论专业论文）智能化公务辅助检索系统iad的研究与实现.pdf

论文题目：智能化政府公文辅助检索系统坳的研究与实现 指导老师：姜云飞教授 硕士生：颜军 摘要 当前我国许多政府部门都开展了电子政务工程，办公自动化已成为提高政府 办公效率的手段之一。目前的办公自动化系统主要基于工作流的方式，对政府部 门中的公文进行电子流转，体现了办公的自动化。本文应用中文自然语言处理提 出了智能化政府公文辅助检索系统，用于对办公自动化中相关公文的智能检索， 在办公自动化系统中加入智能化的元素。 本文首先介绍了i _ a d 系统的背景。并提出了系统核心功能实现所需的分词和 分类技术。对于分词技术，本文采用一种基于n 一最短路径和h m m 模型的一体化算 法，利用统计和规则相结合的方法对未登录词进行识别。 对于文本分类方法，提出一种基于最大熵的文本分类模型，利用文本互信息 量进行特征提取，采用g i s 算法生成参数，对文本分类器进行训练，最后对训练 集外的文本采用最大熵算法进行识别分类。 最后对系统地实现作了详细的设计，提出了主要的数据结构和函数及关系， 并设计了一个系统对整个过程送行模拟。对系统的不足之处也进行了分析。 关键词：公文检索n 一最短路径隐马尔可夫模型最大熵文本分类 t i t l e ：r e s e a r c ha n d d e s i g n o f i n t e l l i g e n t i z ei n f o r m a t i o nr e s e a r c hf o rg o v e r m e n t d o e u m e n t s g u i d et e a c h e r ：j i a n gy u n f e n g p r o f e s s o r m a s t e r ：y a nj u n a b s t r a c t al o to fg o v e r n m e n t d e p a r t m e n t si no u rc o u n t r yl a u n c ht h ee g o v e r n m e n t p r o j e c ta tp r e s e n t ；t h eo f f i c ea u t o m a t i o nh a sa l r e a d yb e c o m ea n di m p r o v e d o n eo fg o v e r n m e n t so f f i c e e f f i c i e n c ym e a n s t h ew a yi n w h i c ht h ep r e s e n t o f f i c ea u t o m a t e ds y s t e mf l o w so nt h eb a s i so ft h ew o r km a i n l y ，c i r c u l a t e e l e c t r o n st ot h eo f f i c i a ld o c u m e n ti nt h e g o v e r n m e n td e p a r t m e n t h a v e r e t i e c t e dt h ea u t o m a t i o no f h a n d l i n go f f i c i a lb u s i n e s s t h i sp a p e ru s e sc h i n e s e n a t u r a l l a n g u a g ep r o c e s s i n g t o p u t f o r w a r dt h e i n t e l l i g e n tg o v e r n m e n t d o c u m e n ta i ds e a r c hs y s t e m ，f o rt ot h ei n t e l l i g e n tr e t r i e v a lo ft h er e l e v a n t o f f i c i a ld o c u m e n ti nt h eo f f i c ea u t o m a t i o n ，p u tt h e i n t e l l i g e n te l e m e n ti n t h e o f f i c ea u t o m a t e d s y s t e m t h i s p a p e r i n t r o d u c e dt h e b a c k g r o u n d o f i a ds y s t e m a n d h a sp u t f o r w a r dt h ek e yf u n c t i o no ft h es y s t e ma n dr e a l i z e dt h en e c e s s a r yp a r t i c i p l e a n dc a t e g o r i z e dt e c h n o l o g y a st o p a r t i c i p l et e c h n o l o g y ，l i t e r a r yg r a c et h i s b e c a u s eo fn s h o r tp a t h sa n dh m ma l g o r i t h m t h em e t h o do fu t i l i z i n g s t a t i s t i c sa n dr u l et oc o m b i n e t o g e t h e r , t on o tl o g g i n gi nt ot h e w o r dt od i s c e r n t ot h ec a t e g o r i z e dm e t h o do ft h et e x t ，p u tf o r w a r dak i n do fc a t e g o r i z e d m o d e io ft e ) ( tb a s e do nm a x i m u me n t r o p y u t i l i z e m u t u a l l y a m o u n to f i n f o r m a t i o no ft h et e x t t od r a wt h ec h a r a c t e r i s t i c 。a d o p tg i sa l g o r i t h mt o p r o d u c et h ep a r a m e t e r , i si t t r a i nt og oo nt ot e x tp e r s o nw h oc l a s s i f y ，c o l l e c t t e x to fo u t s i d ea d o p tb i ge n t r o p ya l g o r i t h mi si ti si tc l a s s i f yt od i s c e r nt og oo n m o s t t r a i n i n gf i n a l l y t or e a l i z i n gd o i n gt h ed e t a i l e dd e s i g ns y s t e m a t i c a l l yf i n a l l y p u tf o r w a r d m a i nd a t as t r u c t u r ea n df u n c t i o na n dr e l a t i o n ，a n dh a sd e s i g n e das y s t e ma n d i m i t a t e dt h ew h o l ec o u r s e h a v ea n a l y z e dt o oa b o u tt h ew e a kp o i n to ft h e s y s t e m k e y w o r d s ：o f f i c i a l d o c u m e n ts e a r c h n s h o r t e s tp a t h s h i d em a r k o v m o d e lm a x i m u me n t r o p y t e x tc a t e g o r i z a t i o n i i 智能化政府公文辅助检索系统i _ a d 的研究与实现 1 1 背景描述 第一章引言 目前，随着信息技术的发展，政府办公也由低效率的传统办公方式转向高效 快捷的自动化办公模式。这一自动化办公模式主要是将政府办公和计算机应用功 能结合起来，通过网络，组织机构内部的人员跨越时间、地点协同工作，充分地 利用信息资源，提高工作效率和质量、辅助决策、求取更好的效果。 计算机技术的进步带来的政府办公自动化的功能、应用领域和概念外延不断 衍生、扩大与提高造就了以工作流为中心的办公自动化系统概念。这种系统概念 已成为了当前政府办公自动化的主流。在以工作流为中心的政府办公系统中，公 文流转和管理是主要的核心功能模块。公文的流转过程体现了办公的自动化，而 公文的管理，目前大部分的政府办公自动化系统仅停留在信息的存储归档和简单 查询上，在后续处理中对这些信息资源不能很好的利用，难以实现办公自动化的 智能辅助决策功能。 在实际应用中，办公人员在处理当前公文时，经常需要对历史公文进行奄阅， 达到辅助决策的目的。当前的做法是采取一种被动的方式，由办公人员手工在电 子公文库中输入关键字后，采用某种检索算法进行检索。这样的模式，从理论上 来说，只要电子公文库中的文件包含了某个关键词，就能够把该文件查出来，但 是这又导致了它的缺陷：耗费时间长，由于受输入关键词的影晌，返回的信息存 在过多或过少的现象。这种现象随着公文数量的增加将越来越明显。 1 2ia d 系统的提出 随着中文自然语言处理的深入发展，基于统计和规则的中文智能化处理的研 究也备受重视，其应用也越来越广泛。 1 1 1中文自然语言处理应用的现状 中文自然语言理解技术有着广阔应用空间，目前已经广泛应用在机器翻译、 堡壁些墼宣竺奎塑墅堕鲞至竺l 竺塑竺塞量塞翌 电话翻译、人机对话、智能检索、自动文摘等方面。特别是在智能检索方面，随 着i n t e r n e t 技术的不断发展，网络信息数量日渐增多，对信息检索的要求也随 之提高。许多搜索网站( o o o g l e 、百度等) 加入了中文自然语言处理技术，大大 提高了网上信息检索的效率。 从目前的理论和技术现状看，通用的、高质量的自然语言处理系统，仍然是 较长期的努力目标，但是针对一定应用，具有相当自然语言处理能力的实用系统 是可以实现的。典型的例子有：数据库和专家系统的自然语言接口、各种机器翻 译系统、全文信息检索系统、自动文摘系统等。从应用领域划分，典型的系统有： 图书馆检索系统、w w w 搜索引擎等。 本文主要的研究领域是基于文本的信息检索，目前，信息检索已经发展到网 络化和智能化的阶段。信息检索的对象从相对封闭、稳定一致、由独立数据库集 中管理的信息内容扩展到开放、动态、更新快、分布广泛、管理松散的内容；信 息检索的用户也由原来的情报专业人员扩展到包括商务人员、管理人员、教师学 生、各专业人士等在内的普通大众，他们对信息检索从结果到方式提出了更高、 更多样化的要求。适应网络化、智能化以及个性化的需要是目前信息检索技术发 展的新趋势。 1 1 2 i _ a d 系统的提出 在政府办公自动化系统中，工作流中所包含的文档大部分为中文文档，我们 可以考虑将中文自然语言处理方法应用到其中，在政府办公自动化中加入智能化 处理元素，提高办公自动化系统的辅助决策作用。为此，本文设计了一个智能化 公文辅助检索系统( ia d ) ，在改变传统的办公自动化系统公文管理和检索功能 方面做一个新的尝试。 这个系统的主要目的是针对政府办公自动化系统中对历史公文检索存在的 弊端，提出一种智能化的公文分类机制和检索机制，建立智能文档库，在办公人 员处理公文时，能快速在文档库中查找到与当前公文内容相关的历史公文，并按 照一定算法计算它们的相关度后按序列出供办公人员参考，智能的提供辅助决策 支持。这一系统的主要优点是：针对特殊的应用领域，可以尽量回避一些中文自 然语言处理的瓶颈，如：人名识别、未登录词识别等；所有的处理过程都在后台 2 塑堂些堕堕坌奎塑塾丝室墨竺二竺塑里塞皇塞翌 完成，对用户来说是透明的，不影响用户的工作效率；利用成熟的中文自然语言 处理技术，通过系统的自我学习提高检索的实用性和智能性。 1 3 论文的组织结构 本文主要讨论政府办公自动化系统中公文智能检索的问题。利用中文自然语 言处理中的词语切分、文本分类等实现一个智能系统，主要内容包括： 一ia d 的总体架构和设计思路，从政府办公简化模型出发，提出了系统的 目的和架构： _ 建立了基于隐马尔可夫模型和n - 最短路径的中文分词一体化方法，并对未 登录词识别，词性标注等作了详细阐述； 一采用基于最大熵的中文文本分类方法，利用分词结果对文本进行训练和分 类，并用文档的特征项进行检索得出结果： _ 最后补充说明i _ a d 系统的实现细节和试验结果，并提出一些不足之处， 以供将来改进。 智能化政府公文辅助检索系统i _ a d 的研究与实现 第二章系统总体架构和设计思路 2 1i a d 系统功能描述 i a d 系统主要目的是为了在政府办公自动化系统公文处理过程中为办公人 员正在处理的当前公文提供智能化的决策辅助。为此需要结合政府办公公文处理 的实际流程来定义i d 系统的功能。 图2 卜1 描述了一个简化的政府办公公文处理流程模型： 图2 i - i 政府办公简化模型 在这个简单的处理模型中，办公人员处理这一环节是最能体现提高工作效率 和辅助决策目标的，i a d 系统是针对这一个环节而设计。相关人员在处理当前 公文时需要有许多额外的辅助信息来帮助决策，而大量的历史文档以简单的排序 方法杂乱无章的存储在文档库中，办公人员必须花大量的时间和精力用于查找相 关信息，这无疑对工作效率产生了消极的影响。为了克服这一弊端，需要一个工 具来智能化的帮助办公人员提取历史文档中的有用信息。i _ a d 系统的主要功能 就是实现这一智能化过程。其两个主要的功能如图2 卜2 所示： 图2 卜2 la d 系统功能描述 4 智能化政府公文辅助检索系统i _ a d 的研究与实现 2 2 c a d 系统设计思路 要实现i - a d 的功能，可以采用几种策略。一种策略是对当前文档和历史文 档不做任何预处理，为当前文档附加历史文档信息集合时采取全文对全文的机械 匹配，同时根据一定算法计算文档的相关度，排序输出。这种方法能检索到所有 有关的历史信息，对于基于关键词的检索是一种可行的方案，但是对于基于文档 的检索存在着严重的不足，假设历史文档数为，平均每个文档字数为m ，这 种方法的时间复杂度为o ( n ”) 。 另外一种策略是对当前文档进行定的预处理，提取文档的部分信息形成关 键词，检索时，利用这些关键词对文档库中的每篇文档进行检索得出结果。这种 方法能快速的检索出结果，但是结果文档集合中可能存在漏查或多查的现象，对 办公人员有真正参考价值的文档可能被排除在外，一些无关的信息反而包含在 内。例如：当前文档是关于科技三项经费使用的通知，它的关键词为 科技”、 “经费”、“通知”) ，通过检索，其结果会包含如关于科技局购买车辆所需 经费的请示这样的对当前文档无用的信息。 第三种策略是采用当前比较成熟的一些中文自然语言处理方法，首先对所有 的文档进行文本特征提取，形成基于这些特征的文本类集合，并以词为单位为每 个文档建立关键内容索引集合。对于当前文档，在从其登记环节进入办公人员实 际处理的过程中，调用文档处理机制进行预处理，附加上历史文档信息集合，这 样做可以避免在办公人员处理文档时再花费大量时间等待检索；在当前文档完成 最后处理环节进入文档库前，在对当前文档进行特征分类处理，加入相应的分类 集合中形成历史文档，如图2 2 1 。 智能化政府公文辅助检索系统i _ a d 的研究与实现 图2 2 1 文本分类检索方法 这种做法体现了政府办公自动化和智能化的有机结合，对办公人员来说，文 档检索在后台处理完成，无需等待：另一方面采用了文本分类的方法，检索的速 度能得到了很大的提高，基于中文分词处理的文档特征提取技术可以保证检索具 有好的查全率和查准率。 根据上述分析，i a d 系统采用第三种策略来实现。 2 3i _ a d 系统总体架构 i a d 系统其核心必须包含一个行之有效的特征提取和文本分类机制，对输入 的文件流处理得出文档的类别属性和关键信息集合。其整个核心处理流程如图 2 3 - l 所示： 一一一- 一一一- ，一一- 特 l 征 1 分 ；类 ；模 ：块 特征提取 1 6 - 一文档分词模块 智能化政府公文辅助检索系统i _ a d 的研究与实现 图2 3 - li a d 核心处理流程 从上面的图可以看出，要实现该系统，关键技术在于实现文档分词模块和特 征分类模块。 2 4 小结 本章主要描述了la d 系统的功能及其在政府办公自动化系统中所处的位置。 通过对系统功能的分析和对几种策略的比较，给出了i a d 系统的核心处理流程 和实施所涉及的知识和领域。 7 智能化政府公文辅助检索系统i _ a d 的研究与实现 第三章文档分词处理模块 3 1 中文分词介绍 “词是最小的能够独立活动的有意义的语言成分。” 】 ，但汉语是以字为 基本的书写单位，词语之间没有明显的区分标记，因此，中文分词是中文信息处 理的基础与关键。当前中文分词主要分为两个步骤：在词库中采用一定的查询算 法，按照一定的规则，得到一个粗分结果集，粗切分结果是后续过程的处理对象， 粗分结果的准确性与包容性( 即必须涵盖正确结果) ，直接影响系统最终的准确 率、召回率。预处理得到的粗分结果一旦不能成功召回正确的结果，后续处理一 般很难补救，最终的词语分析结果必然会导致错误，粗分结果的召回率往往是整 个词语分析召回率的上限。同时，粗分结果集的大小也决定了后续处理的搜索空 间与时间效率，最终也会影响整个系统的运行效率。因此，词语粗分是后续处理 的基础和前提，其关键在于如何以尽量高的效率寻找数量极少、涵盖最终结果的 粗分结果集。 目前国内公开报道过的分词系统采用的分词方法主要有三种类型 2 ：基于 字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。 一、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一 个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配 成功，识别出一个词。按照扫描方向的不同，串匹配分词方法可以分为正向匹配 和逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小 ( 最短) 匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分 词与标注相结合的一体化方法。常用的几种机械分词方法如下：正向最大匹配、 逆向最大匹配、最少切分( 使每一句中切出的词数最小) 。还可以将上述各种方 法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成 双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少 使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。 统计结果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最大匹 配的错误率为1 2 4 5 。但这种精度还远远不能满足实际的需要。由于分词是一个 智能化政府公文辅助检索系统l a d 的研究与实现 智能检索过程，机械分词方法无法解决分词阶段的两大基本问题：歧义切分问题 和未登录词识别问题。汉语文本中的歧义切分字段有交集型和组合型两个基本类 型： 交集型歧义：假设a b c 分别代表由一个或多个字符组成的字串，如果在a b c 字 段中，a 、a b 、b c 、c 又分别都是词表中的词，那么a b c 和a b c 都是合理的切分 结果。例如：“这糖果真好吃”与“这糖果真好吃”都是符合切分规则的 结果。 组合型歧义：在字段a b 中，若a 、b 、a b 均是词表中的词，则称a b 为组合型歧 义字段。如“茶杯”和“茶杯”，“明天”和“明天”，“痛恨”和“痛恨” 等。 缺乏自学习的智能性是机械分词法的一大弱点 3 。 二、基于理解的分词方法 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则 在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的- - b 部 分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信 息来处理歧义现象。如扩充转移网络法、知识分词语义分析法、邻接约束法、综 合匹配法、后缀分词法等。这些方法通常包括三个部分：分词子系统、句法语义 子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等 的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这 种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性， 难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系 统还处在试验阶段。 三、基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现 的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较 好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统 计，计算它们的互现信息。定义两个字的互现信息为m i ( x ：_ y ) = l 0 9 2 兹：告。 其中p ( x ，y ) 是汉字x 、v 的相邻共现概率， p ( x ) ，p ( y ) 分别是x 、y 在语料中出 9 智能化政府公文辅助检索系统i a d 的研究与实现 现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一 个闽值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频 度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这 种方法也有定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组， 例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精 度差，时空开销大。实际应用的统计分词系统都要使用部基本的分词词典( 常 用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计 和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词 典分词结合上下文识别生词、自动消除歧义的优点。 本文中描述的ia d 系统主要用于信息提取和检索。信息检索是找出包含了 指定的一类特征( 关键字、检索表达式) 的文档供用户阅读的过程。而信息提取 则是从一段文本中抽取指定的一类信息( 事件、事实) 并将其填入个库中供用 户和系统使用的过程，即信息提取不仅找出文档，而且进一步给出文档的特征， 或者说它在信息检索之后进行文本的分析和理解。 针对于ia d 系统而言，分词技术的关键是能稳定、快速的对大文本进行切 分和排歧。另外本系统主要是针对政府领域，检索具有高度的领域化、专有性和 高度的不确定性，系统会遇到大量的未登录词，这就要求系统必须具备生词的识 别能力。综合考虑这些因素，本系统选取n 一最短路径 4 结合隐马尔可夫模型的 分词方法 5 。对于文本d ，采用n 一最短路径的方法得到n 个粗分结果，下一步 引入规则以及优化函数，对数量不多的、高召回率的粗分结果进行未登录词的识 别和其他的相应处理，集中地提高准确率。最终采取一体化方法，利用隐马模型 选取切分及标注的最佳结果。 3 2 基于n 一最短路径中文词语粗分 基于n 一最短路径中文词语粗分算法的基本思想是：根据词典，找出字串中 所有可能的词，构造词语切分有向无环图。每个词对应图中的一条有向边，并赋 给相应的边长( 权值) d 然后针对该切分图，在起点到终点的所有路径中，求出 长度值按严格升序排列( 任何两个不同位置上的值一定不等) 依次为第1 ， 第 2 ，第i ，第n 的路径集合作为相应的粗分结果集。如果两条或两条以 1 0 智能化政府公文辅助检索系统l a d 的研究与实现 上路径长度相等，那么他们的长度并列第i ，都要列入粗分结果集，而且不影响 其他路径的排列序号，最后的粗分结果集合大小大于或等于n 。 设待分字串s = t i c 2 矗，其中c j ( i = 1 2 行) 为单个的字，h 为串的长 度，胛1 。建立一个节点数为n + l 的切分有向无环图g ，各节点编号依次为k ， k 吒圪。 通过以下两种方法建立g 所有可能的词边。 ( 1 ) 相邻节点圪- l ，圪之间建立有向边 ，边的长度值为丘，边对 应的词默认为q ( k = 1 2 埘) ； ( 2 ) 若w = c i c i 。q 是一个词，则节点k + 巧之间建立有向边 ， 边的长度值为工。，边对应的词为w ( 0 i j n ) ： 这样，待分字串s 中包含的所有词与切分有向无环图g 中的边一一对应。如 图3 2 - l 所示： ( 强l c i 继：p o 图3 2 - 1 切分有向无环图 有了基本的模型，现在要确定有向无环图的边长。如果假定所有的词都是对 等的，给每个词的对应边长度赋值为l 。随着字串长度n 和最短路径数n 的增大， 长度相同的路径数急剧增加，同时粗切分结果数量必然上升。大量的切分结果对 后期的处理，以及整个性能的提高是非常不利的。为此引入词频p ( w ) 并假定词 与词之间是相互独立的，对于有向无环图，选取使得概率p ( m l c ) 的值是最大n 条路径。得到一个基于n 一最短路径的统计模型。 求解p ( ic ) 采用如下方法： 咿i c ) = 等 ( 公式3 2 1 ) 智能化政府公文辅助检索系统ia d 的研究与实现 其中，p ( c ) 是汉字串的概率，它是一个常数，不必考虑。从词串恢复到汉 字串的概率p ( c 1 ) = 1 ( 只有唯一的一种方式) 。 因此，求解的目标就是确定户( ) 最大n 种的切分结果集合。 w = w l w 2 是字串s = v i e 2 矗的一种切分结果。w l 是一个词，p ( w ) 表 示w i 的出现的概率。在语料库训练的基础上，根据大数定理，在大样本统计的 前提下，样本的频率接近于其概率值。所以p ( w ) 的极大似然估计值等于词频， 公式3 2 2 其中t 为词在训练样本中出现的次数。 粗切分阶段，为了简单处理，仅仅采取了概率上下文无关文法 6 】，即假设上 下文无关，词与词之间相互独立。因此，根据公式3 2 1 和公式3 2 2 ，可以得到 w 的联合概率： 一咖，尊轰 赋3 2 3 为了编程处理的方便，令 n 啥山一扣删芝i i o 一磋_ ， ，= o，肛 = 瞰1 ) 山毛】 公式3 2 4 这样就可以将公式3 2 3 极大值的问题转化为求解公式3 2 4 极小值的问 题。此时切分有向无环图g 边的长度( 加l 主要是为了数据的简单平滑处理) ： ( 1 ) 的长度值厶= 一l n ( o + 1 ) ， ( k = 1 ，2 ，n ) ( 2 ) w = c l c 2 。，对应的有向边为 ， 其长度值 1 2 丢乳 )m( p 有 智能化政府公文辅助检索系统i _ a d 的研究与实现 工。= i n ( 2 j k j + m ) 一i n ( k , + 1 ) ； 7 = 0 下面的问题就是求解切分有向无环图g 中的n 个最短路径集合。本文中采用 基于d i j k s t r a 7 算法的一种简单扩展来求解。d i j k s t r a 算法思想：设置一个顶 点集合s 并不断地作贪心选择来扩大这个集合。一个顶点属于集合s 当且仅当从 源到该顶点的最短路径长度已知。初始时，s 中仅含有源。设u 是g 的某一个顶 点，把从源到u 且中间只经过s 中顶点的路称为从源到u 的特殊路径，并用数组 d i s t 记录当前每个顶点所对应的最短特殊路径长度。d i j k s t r a 算法每次从v s 中取出具有最短特殊路长度的顶点u ，将u 添加到s 中，同时对数组d i s t 做必 要的修改。一旦s 包含了所有v 中的顶点，d i s t 就记录了从源到所有其他顶点 之间的最短路径长度。为了通过回溯求出包含n 个结果的粗分集合，每个节点处 记录n 个最短路径值，并记录相应路径上当前节点的前驱。如果同一长度对应多 条路径，必须同时记录这些路径上当前节点的前驱。 d i j k s t r a 算法的时间复杂度为0 ( n 2 ) ，它求的是图中所有点到单源点的最短 路径，而在切分有向图中的应用，有两个区别：首先有向边的源点编号均小于终 点编号，即所有边的方向一致：其次，我们求的是有向图首尾节点的n 一最短路 径。所以我们使用的算法中，运行时间与n ( 字串长度) 、n ( 最短路径数) 以及 某个字作为末字的平均次数k ( 该平均数等于总词数除以末字总数，对应的是切 分图中结点入度的平均值) 成正比。整个算法的时间复杂度是0 ( n * n * k ) 。 3 3 隐马尔可夫模型( h m m ) h m m 是一种随机的有限状态自动机，已成功应用于许多领域。h m m 最近 几年被引入到自然语言处理中，已经得到了成功的应用。h m m 有非常适合自然 语言处理的统计基础，对于新数据的处理有良好的鲁棒性，并且有成熟的学习算 法 8 ，是一个成功的模型a 对于一个随机事件，有一个观察值序列： 该事件隐含着一个状态序列 d l ，0 2 ，0 r 智能化政府公文辅助检索系统l a d 的研究与实现 x 1 ，x 2 ，x r 假设l ：马尔可夫假设( 状态构成阶马尔可夫链) p ( 置i 置。彳。) = p ( 工i 置一。) 假设2 ：不动性假设( 状态与具体时间无关) p ( 置+ 一j 五) = p ( 乃+ 。j 一) ，对任意f ，成立 假设3 ：输出独立性假设( 输出仅与当前状态有关) p ( 0 1 0 2 ，q1 五五，墨) = 兀p ( 0 ，i 置) 一个隐马尔可夫模型( h m m ) 是一个五元组： ，a ，b ，) 其中： q 。= 锄，q ：，q 。) ：状态的有限集合； q 。= v 。，v 2 ，v 卅) ：观察值的有限集合； a = d f ，= p ( 置+ l = q ，i 五= q i ) ：转移概率： b = ，= p ( q = 咋f 置= q i ) ：输出概率； 1 7 = 兀。) ，n 。= p ( 五= 吼) ：初始状态分布 h m m 所要解决的问题是： 令兄= a ，b ，r i ) 为给定h m m 的参数， 令仃= d i ，q 为观察值序列， 隐马尔可夫模型( h m m ) 的三个基本问题： 1 评估问题：对于给定模型，求某个观察值序列的概率p p l 旯) ； 2 解码问题：对于给定模型和观察值序列，求可能性最大的状态序列； 3 学习问题：对于给定的一个观察值序列，调整参数 ，使得观察值出现的 概率p p i 五) 最大t 隐马尔可夫模型在自然语言处理方面有着很好的应用，例如： 己知单词序列w l w 2 w n ，求词性序列c l c 2 o n 1 4 智能化政府公文辅助检索系统l a d 的研究与实现 利用删m 模型，可以将词性为理解为状态，将单词为理解为输出值。使用统 计词性转移矩阵 和词性到单词的输出矩阵【k 】对其进行训练，最终达到对词 性标注的目的。 3 4 基于隐马尔可夫模型( 删) 和n 一最短路径一体化方法 通过上面的分析，我们可以建立一个基于隐马尔可夫模型( h m m ) 和n 一最短 路径中文分词一体化方法。图3 4 1 给出了这一方法的框架。 切分为不可再分 的汉字 i汉字集合 n 最短路径粗切 分 一1 、租竹靖米 简单的未登录词 呻 按词类别生成 识别 基于类别的有 向无环图 基于h m m 的词类 校正租分结果 分析 图3 4 1 基于h m m 的分词模型 甲 篁登垡塾堕竺苎塑墅丝鲞至垫l 竺塑竺塞量壅翌 在3 2 节中已经采用n 一最短路径方法得到了中文串的n 个粗分结果，下面的 工作就需要对n 个结果进行简单的未登录词识别。 3 4 1 未登录词的简单识别 所谓未登录词是指，句子中存在的切分词，但是无法在系统自带词典中找到 的。本文所描述的系统是针对政府公文的，政府公文一般行文都比较正规，用词 比较正式，大部分出现的未登录词都是人名和地名，如表3 4 卜1 所示。 i文档数汉字数 未登录词数人名+ 地名 1 0 06 3 2 1 52 3 62 0 4 表3 , 4 1 - 1 未登录词分析结果 因此在本文中对未登录词的处理，主要是指对未登录的人名和地名的处理。 目前采用的人名和地名的识别方法主要有三种：基于统计的方法 1 1 1 2 ，基于 规则的方法 1 4 1 5 ，概率统计和规则相结合的方法 1 3 。本文采用种规则和 统计相结合的方法来实现人名和地名的识别 1 6 。首先来看人名的识别。 人名在中文文本中按组成结构的不同，主要可以分为以下四类： 1 、姓氏+ 人名用字，例如：王小明、张三； 2 、姓氏+ 人名后缀( 称谓) 或修饰词+ 姓氏，例如：李教授、王某、老王、 赵总等； 3 、省略姓氏的人名，及只有人名用字组成的人名，例如：小明、小华等； 4 、外国人名 中文文本中人名的识别主要是针对“姓氏+ 人名用字”格式的人名即通常 所说的姓名的识别。在前面的处理中，未登录词已被切分为单个的字，以便后续 的处理。引入一些定义： 设“姓氏+ 人名用字”格式的人名的通用表达形式为： n a m e = s w , ( 双名) 或s 嗽( 单名) s ：表示是姓氏； 形：表示人名用字首字； 职：表示人名用字尾字； 1 6 智能化政府公文辅助检索系统l a d 的研究与实现 但在具体文本中，可能很多中文人名没姓氏，即人名只有嘶或者彬或者 是只是：姓氏+ 人名后缀( 称谓) 。 ( 1 ) 姓氏使用概率计算公式 f ( s ) = s 在语料中作为姓氏的次数s 在语料中单开出现的次数； ( 2 ) 人名用字使用概率计算公式 f ( ) = 暇在语料中作为人名用字出现的次数噬单开出现的次数； f ( ) = 在语料中作为人名用字出现的次数单开出现的次数； ( 3 ) 姓名的概率计算公式 双名的概率为：f ( n a m e ) = f ( s ) x f ( 嘶) f ( 吸) ； 单名的概率为：f ( n a m e ) = f ( s ) xf ( 彬) ； ( 4 ) 人名前缀和人名前缀使用概率 人名前缀：指处于人名之前的，表示称谓的词，如：“珠海特区报记者纳家 华”中的“记者”； 人名前缀使用概率= 语料中人名前缀在人名之后出现的次数语料中人名前 缀出现的总次数； ( 5 ) 人名前导词和人名前导词使用概率 人名前导词：指处于人名之前的，引出人名的词，如：“会议昨天决定任命 张高丽为山东省副省长”中的“任命”； 人名前导词使用概率= 语料中人名前导词在人名之后出现的次数语料中人 名前导词出现的总次数； ( 6 ) 人名后缀和人名后缀使用概率 人名后缀：指处于人名之后的，表示人名称谓的词，如：“黄丽满副书记任 深圳市委书记”中的“副书记”； 人名后缀使用概率= 语料中人名后缀在人名之后出现的次数语料中人名后 缀出现的总次数； ( 7 ) 人名后导词 人名后导词：指处于人名之后的，引出动作的词，如：前两个例子中的“为” 智能化政府公文辅助检索系统ia d 的研究与实现 和“任”： 人名后导词使用概率= 语料中人名后导词在人名之后出现的次数语料中 人名后导词出现的总次数： 有了以上的定义和假设，可以使用统计的方法对中文人名进行识别，如果统 计方法无法识别的，我们采用简单的规则方法：若姓氏前面的一个词是人名前导 词或者是人名前缀，并且姓氏后的第二个或者第三个词是人名后缀或后导词，则 认为该字符串是中文姓名。具体的算法如下： ( 1 ) 判断是否是姓氏，若是姓氏，则转到第( 2 ) 步，若不是，则转到( 4 ) ； ( 2 ) 先假定该可能的姓名为三字人名，用统计的方法进行识别，若系统认为不 是人名，再用规则的方法进行识别。如果用规则和统计的方法都认为不是三字人 名，则假定该可能的人名为2 字人名。先用统计的方法对这个可能的2 字人名进行 识别，若不是，再用规则的方法进行识别。若不是，则转到( 3 ) ； ( 3 ) 进行“( 修饰词+ ) 姓氏( + 人名后缀) ”这类人名的识别，若不是，则 转到( 4 ) ： ( 4 ) “不带姓氏”的人名的识别，若不是，则转到( 5 ) ； ( 5 ) 输出结果； 在计算出f ( n a m e ) 后，需要设定一个阀值，当f ( n a m e l ) 大于该值时，则认为 是人名，否则判定不是。经过实验比较，当阀值为0 0 0 1 时能达到较好的效果。 对地名的识别方法也采用上述方法，不同的是地名识别的触发不是首字的姓 氏，而是在后面的区域描述字，如：“省”、“市”、“街”、“镇”等。由于处理方 法类似，在此就不再赘述了。 在经过了简单的未登录词识别后，之前粗分得到的结果集也发生了变化，我 们下一步的处理就是要在这些粗分结果中选择一个较优的解并为其标注词性作 为最终的输出结果。 3 4 2 基于h m m 的词类分析 为了得到最终的结桌，引入词类的概念 5 。对于给定的词w ，它所属词类c 的定义如图3 4 2 一i ： 1 8 塑丝些璺堕竺苎翌壁丝墨至堑! = 些箜堕窒量壅塑 w p e r 工d c t l m e n u m 5 豫 b e g e n d o t h e r 图3 4 2 1 词的类别定义 说明：c i = w 当且仅当是在词典中已经识别出的词； q = p 瑚当且仅当是识别出的中文人名 c l = l o c 当且仅当是识别出的地名； c = t i m e 当且仅当w ，表示时间日期 c = n u m 当且仅当是表示数字 c = s t r 当且仅当是未知的标记； q = b e g 当且仅当m 是句子的开始 c ，= e n d 当且仅当是句子的结尾 c = o t h e r 其他； 上述类别中，系统在前期的处理中已经能够标识出来，人名和地名在未登录 词识别中可以得出；时间、日期和数字的标识也是比较简单的；句子的开始和结 束标识是在粗切分时就已经确定了( 采用识别标点符号的方法) 。 对于任意一个字串a = ( q ，吼) ，令w = ( w i ，w 卅) 是a 的粗分结果集合， c = ( c 1 ，c 。) 是相应的类别序列，w 4 是粗分集合中的最优解。可以得到： w 4 = a r g m a x p ( j a ) = a r g m a x p ( w ，a ) p ( a ) 公式3 4 2 1 w 对于一个指定的字串a ，p ( a ) 是一个常数，p ( ，a ) = 尸( 矿) ，因此 1 9 笪i ! 些堕壁坌苎塑壁垒室墨竺! ：苎里塑堕壅量塞墨 w ”= a r g m a x p ( w ) w 根据贝叶斯理论可以得到： w 4 = a r g m a x p ( w f c ) p ( c ) 舻 公式3 4 2 - 2 根据h 删模型，把c 作为状态集，m 作为输出，可以得出 4 = a r g m a x 兀p ( f q ) p ( c ，f c i 1 ) ”l ”2 1 为了编程计算的方便，令： w 4z a r g m a x 乏 - i n p ( w , i q ) 一i n p ( c , f c , - l ) 公式3 4 2 - 5 ，7 i ll 根据q 的定义，如果_ 是在字典中的词，则q 为，p ( w l 旧) = l 。否则 p ( w l q ) 表示w 在语料库中属于的概率，在大规模语料库下，可以认为 p ( w flc ，) = w i 属于q 的次数w 出现的总次数。 通过基于h m m 的词类分析后，词的切分转化为求解唯一的条最短路径问题， 本文中使用d i j k s t r a 算法( 已在前面章节中介绍) 求解矽4 。形。为最终分词的 结果。 3 5 实验结果 我们对一体化方法采用不同的n 值进行测试，得到如表3 5 - l 的结果( 句子 总数约为8 0 ，0 0 0 ) 。 n粗分结果数 正确切分的句子数句子切分正确率 117 4 8 0 09 3 5 0 227 6 1 7 69 5 2 2 337 7 8 0 89 7 2 6 44 7 8 5 0 49 8 1 3 557 9 2 4 09 9 0 5 667 9 6 9 69 9 6 2 表3 5 1 分词测试结果 智能化政府公文辅助检索系统ia z ) 的研究与实现 3 6 小结 本章主要讲解了对中文字串的分词处理。参考大量分词算法，采用n 一最短路 径粗分和基于h 模型的一体化分词方法，并设计了规则和统计相结合的未登录 词识别方法，为后续的文本分类打下了良好的基础。在实验中，我们没有和其他 的分词方法进行比较，但是从系统的实际需要出发，这种分词方法已能达到很好 的效果，并且在编写系统过程中，实现也没有太大的复杂性。 智能化政府公文辅助检索系统l a d 的研究与实现 第四章中文文本分类 4 1 文本分类介绍 简单地说，中文文本分类就是：在给定的分类体系下，根据文本的内容自动 地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未 标明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多 的映射，因为通常一篇文