（计算机应用技术专业论文）基于优化类中心分类算法的文本分类系统设计与实现.pdf

桂林理工大学硕士学位论文 摘要 面对如今信息技术的飞快发展，各种电子文档和电子邮件都爆炸式的增长， 为了从海量文本中及时准确的获得有效的知识和信息，就需要处理大量的文本。 由于互联网上大部分信息都是以文本的形式存在，文本的识别就构成了高效信息 获取的基础。利用文本分类识别技术可以把数量巨大但缺乏结构的文本数据组织 成规范的文本数据，帮助人们提高检索信息、利用信息的效率。文本分类已经成 为组织和管理文本数据的重要形式。传统的人工分类已经不能满足如今的需要， 它耗费大量的人力、物力和精力，并且分类结果一致性不高。为了能在海量的文 本中及时准确地获得有效的知识和信息，文本表示技术以及文本自动分类技术受 到了广泛的关注。 本文详细介绍了文本分类的过程和相关的技术，利用向量空间模型构建文本 表示模型，研究现有的特征抽取和特征权重算法，介绍了常用的文本分类算法， 并针对传统类中心分类算法由于训练文档分散，不能准确的表示各类别的中心向 量，提出了优化算法，从而提高了分类准确度。主要研究如下： 首先，阐述了文本分类的理论基础：分词、文本表示、特征提取、特征权重 算法。 其次，介绍了文本分类常用的分类算法：贝叶斯方法，k n n 方法、类中心 分类方法、支持向量机方法、决策树方法，并对它们进行对比研究，最后提出了 改进的类中心分类算法。 最后，在文本分类的相关技术的支持下，利用改进的类中心分类算法设计一 个文本分类系统，并得到了良好的效果。 关键词：文本分类；向量空间模型；特征项；分类算法 桂林理工大学硕士学位论文 a b s t r a c t w i t hr a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n de x p l o s i v eg r o w t ho f e l e c t r o n i cd o c u m e n t sa n de - m a i l s ，p e o p l eh a v et od e a lw i t hal o to ft e x t si no r d e rt o g e ti n f o r m a t i o nt i m e l ya n dc o r r e c t l yw i t h i nm a s st e x t s b e c a u s em o s ti n f o r m a t i o n e x i s t si nf o r mo ft e x t s ，t e x ti d e n t i f i c a t i o nc o n s i s t so ft h eb a s i so fa c c e s s i n gt o i n f o r m a t i o ne f f i c i e n t l y t e x ti d e n t i f i c a t i o nt e c h n o l o g yc a nh e l pp e o p l ed e a lh u g et e x t d a t aw h i c hi sl a c ko fs t r u c t u r ew i t hs t a n d a r dt e x td a t ai no r d e rt oh e l pi m p r o v e e f f i c i e n c yo fr e t r i e v a la n du s eo fi n f o r m a t i o n t e x tc l a s s i f i c a t i o nh a sb e c o m eo n eo f t h em o s ti m p o r t a n tf o r m si no r g a n i z i n ga n dm a n a g i n gt e x td a t a t r a d i t i o n a lm a n u a l c l a s s i f i c a t i o nc a nn ol o n g e rm e e tt h en e e d si nt h e s ed a y s ，w h i c hc o s tal o to f m a n p o w e r , m a t e r i a la n de n e r g y a n df u r t h e rm o r ew i t h o u tc o n s i s t e n c yo fr e s u l t s t ob e a b l et og e tk n o w l e d g ea n di n f o r m a t i o nt i m e l ya n de f f e c t i v e l yw i t h i nm a s st e x t s ，t e x t r e p r e s e n t a t i o nt e c h n o l o g ya n dt e x ta u t o m a t i cc l a s s i f i c a t i o nt e c h n o l o g i e sh a v eb e e n w i d e s p r e a dc o n c e r n e d t h i sp a p e ri n t r o d u c e st h ep r o c e s so ft e x tc l a s s i f i c a t i o na n dr e t a i lt e c h n o l o g i e si n d e t a i l ，t h eu s eo fv e c t o rs p a c et ob u i l dm o d e l s ，t h er e s e a r c ho ff e a t u r e se x t r a c t i o na n d f e a t u r e sw e i g h ta l g o r i t h m ，c o m m o n l yu s e dt e x tc l a s s i f i c a t i o na l g o r i t h m t h i sp a p e r a l s op r o p o s e so p t i m i z e da l g o r i t h mi ni t sn o te x p r e s s i n gv e c t o rc a t e g o r i e sa c c u r a t e l y , r e s u l t i n gi ni m p r o v e dc l a s s i f i c a t i o na c c u r a c y t h em a i nr e s e a r c h e sa r ea sf o l l o w s ： f i r s t ，i tp u tf o r w a r dat h e o r e t i c a lb a s i sf o rt e x tc l a s s i f i c a t i o n ，w h i c hi sf o r m e db y s u b w o r d s ，t e x te x p r e s s i o n ，f e a t u r ee x t r a c t i o n ，f e a t u r ew e i g h t i n ga l g o r i t h m s e c o n d ，i ti n t r o d u c e sc o m m o n l yu s e dt e x tc l a s s i f i c a t i o na l g o r i t h m s ：b a y e s i a n m e t h o d s ，k n nm e t h o d ，t y p eo fc e n t e rc l a s s i f i c a t i o n ，s u p p o r tv e c t o rm a c h i n e ，d e c i s i o n t r e em e t h o d ，a n dt h e i rc o m p a r a t i v es t u d y , w h i c ha r ec o m p a r e di nt h i sp a p e r a tl a s t ， t h i sa r t i c l ep r o p o s e si m p r o v e dc l a s s - c e n t r ec l a s s i f i c a t i o na l g o r i t h m a tl a s t ，w i t ht h ea s s i s to fr e l a t e dt e c h n o l o g yo ft e x tc l a s s i f i c a t i o n ，t h ep a p e ru s e s c l a s s c e n t r ec l a s s i f i c a t i o na l g o r i t h mt od e s i g nat e x tc l a s s i f i c a t i o ns y s t e ma n dg e t s g o o dr e s u l t s k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；v e c t o rs p a c em o d e l ；f e a t u r ei t e m ；c l a s s i f i c a t i o n a l g o r i t h m i i 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已 经发表或撰写过的研究成果，也不包含为获得其它教育机构的学位或证书而使用 过的材料。对论文的完成提供过帮助的有关人员已在论文中作了明确的说明并表 示谢意。 学位论文作者( 签字) ：童：! 握 签字日期：型翌名笸：星 学位论文版权使用授权书 本学位论文作者完全了解( 学校) 有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的印刷本和电子版本，允许论文被查阅和借 阅。本人授权( 学校) 可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国 科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过 网络向社会公众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：当l 振 签字日期：枷口7 年石月留日 导师签字：多、1 ：3 签字日期。例诈6 月孑日 桂林理工大学硕士学位论文 1 1 课题的意义和背景 第1 章绪论 随着信息技术尤其是i n t e m e t 相关技术的发展与成熟，i n t e m e t 、企业内部 网和电子图书馆中可获得的信息越来越多并且还在不断增长。因此，从海量信息 中如何快速有效的获得有用的信息已经成为一个非常重要的研究课题。人们已经 不能简单地靠人工来处理所有的信息，需要有更好的方法来帮助人们更好地发 现、过滤和管理这些信息资源。对资源进行管理的最常用的方法就是对它们进行 分类。文本分类系统的目的就是对文本集进行有序组织，把相似的、相关的文本 组织在一起，为信息检索提供了更高效的搜索策略和更准确的查询结果。传统的 文本分类是有人工完成的，它要耗费大量的人力、物力和精力，并且文分类结果 一致性不高。文本自动分类不仅方便用户准确定位所需的信息，很大程度上解决 了目前网上信息杂乱问题，而且很好的解决了人工分类周期长、费用高、效率低 的缺点，已成为一项具有较大使用价值的关键技术。文本自动分类技术已经广泛 的应用到i n t e m e t 上资源的搜索，电子图书的分类，网络安全中在防火墙技术上 的应用以及电子邮件分类的应用等等，通过文本分类技术可以弥补传统搜索引擎 的不足，过滤用户不需要的文章，并将检索结果分门别类，使用户能够清晰地发 现自己感兴趣的内容。一些机构可以通过文本分类，将不同类别的材料发送到不 同的部门，从而提高工作效率。 自动文本分类是机器学习的一种，它是通过给定的训练文本学习分类模型， 新的待分类文本到来时，通过该分类模型进行分类。也就是说根据给定的训练样 本求出某系统输入输出之间的依赖关系的估计，使得它能够对未知分类做出准确 的预测。自动文本分类的相关研究早在上个世纪六十年代已经展开，现在已经成 为信息科学的主要分支。由于文本分类处理的对象是真实的自然文本，由于语言 的复杂性，所以它涉及的学科知识比较多，技术也比较复杂，包括语言学、认知 科学、信息论、人工智能、统计学、计算机科学等。 由于中文的特殊复杂性，中文文本分类的相关技术还落后于国外。目前信息 的爆炸性增长，以及文本分类的应用领域也很广泛，文本分类以及相关技术的研 究也成为一项研究重点和热点。 桂林理工大学硕士学位论文 1 2 国内外研究现状 文本分类就是对一篇文本，根据其内容，从预先定义好的标记集中找出一个 或者多个最适合与该文本的标记。文本分类技术从开始出现到现在，经历了从基 于规则到基于统计分类，再到规则和统计相结合的一个过程。简单的说，文本分 类系统的任务是：在给定的分类体系下，根据文本的内容自动地确定文本关联的 类别。从数学角度来看，该影射可以是一映射，也可以是一对多的映射，因为 通常一篇文本可以与多个类别相关联。用数学公式表示如下： f ：a b 其中，a 为待分类的文本集合，b 为分类体系中的类别集合，f 是建立a 和 b 映射的函数或模型。文本分类的映射规则是系统根据己经掌握的每类若干样本 的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新 文本时，根据判别规则，确定文本相关的类别。 文本自动分类的方法分为两大类：一是基于规则的分类方法；二是基于统计 的分类方法。基于规则的分类方法多应用于某一具体领域，需要该领域的知识和 规则库作为支撑。但是，对知识和规则的制定、更新、维护以及自我学习等方面 存在种种问题，使得应用面比较窄。基于统计的方法采用纯粹的数学运算，不苛 求复杂的语言学知识和领域知识，同时具有较高的准确率，因而日益受到人们的 重视。 文本分类的研究在国外开始的比较早，2 0 世纪5 0 年代末，h p l u h n 在 这一领域进行了开创性的研究，提出了词频统计思想用于文本分类。1 9 6 0 年 m a r o n 在j o u r n a lo f a s m 上发表自动分类的第一篇论文o nr e l e v a n c ep r o b a b i l t i c i n d e x i n ga n di n f o r m a r i o nr e t r i r a l ) ) ，提出了自动关键词分类技术，正式宣告了自动 分类技术的诞生。1 9 6 2 年博科( h b o r k o ) 等人提出了利用因子分析法进行文献的 自动分类，其后许多学者在这一领域进行了卓有成效的研究。从2 0 世纪6 0 年代 起步至8 0 年代末，文本分类主要是以专家人工构建的知识工程技术为支撑，基 于知识工程的分类系统具有较好的分类效果，但无法移植，需要大量领域专家的 参与。从2 0 世纪9 0 年代开始的自动文本分类，从预先经人工正确分类的训练文 本集合中学习类别的特征信息，根据算法生成分类器。这种分类方法适应性强， 方便移植，不需要行业专家的介入。现在文本自动分类技术已经在邮件分类、电 子会议、信息过滤等方面取得了较为广泛的应用，其中较为成功的系统有麻省理 工学院( m i t ) 为白宫开发的邮件分类系统、卡内基集团为路透社开发c o n s t r u e 系 统等。 国外对文本分类技术以及相关的信息检索、信息抽取等领域进行了较为深入 2 桂林理工大学硕士学位论文 的研究，对文本分类算法的研究开展的也较早，取得了不少令人注目的研究成果， 并产生了一些可用的分类系统。国内在文本分类方向上起步较晚【l 捌，自从自动 文本分类概念在国内出现以后，相关技术有了长足的发展，但和国外的发展状况 相比，发展水平仍然相对滞后。1 9 8 1 年南京林业大学的候汉清教授首次对自动 分类进行探讨，从计算机管理分类表、计算机分类检索、计算机自动分类、机编 分类表等四个方面介绍了国外的发展概况。随后，国内的研究者在英文文本分类 研究的基础上采取相应策略，结合中文文本的特定知识，然后应用于中文之上， 继而形成中文文本自动分类研究体系，并陆续研制出一批计算机辅助分类系统和 自动分类系统。例如中国科学院、清华大学、北京大学、北京信息工程学院、上 海交通大学、复旦大学、东北大学、山西大学、同济大学、南京大学、浙江大学 以及西安电子科技大学等单位都有相应的研究成果，也研制出不少的实验系统。 由于中文与英文存在较大的差异，也不能照搬国外的技术，并且中文有着比英文 更大的处理难度，所以我国的自动分类系统研究离社会化、商品化还有一定的距 离。 1 3 本文的结构 文本分类时，在训练集中，对于各个类别，其文档往往有可能很分散，在空 间上很可能与其它类有重叠的区域，这样，如果直接用这些文档来计算各个类别 的中心向量，往往会有模型偏差，以至于不能得到很好的分类效果。本文针对这 些问题，提出了优化的类中心分类算法，应用向量空间模型的文本表示方法，其 中特征选择应用文档频率方法，特征的权重采用t f x i d f 方法计算。 全文共分六章。 第l 章绪论，主要介绍了文本分类相关技术与应用，研究选题的目的和意义， 介绍了国内外的研究现状，最后给出了本论文的组织结构。 第2 章文本分类的相关理论和技术，介绍了汉语自动分词、向量空间模型、 特征词的抽取以及特征权重的算法。 第3 章文本分类算法的介绍，主要介绍了类中心分类算法、州( k 近邻) 算法、朴素贝叶斯算法、以及本系统应用的优化的类中心分类算法。 第4 章系统设计与实现，针对本文提出的优化算法，完成系统的设计与实现。 第5 章系统测试，对文本分类系统的性能进行测试。 第6 章总结与展望，对本论文的研究工作做了总结并对下一步工作进行展 望。 桂林理工大学硕士学位论文 第2 章相关理论及技术 文本自动分类技术的基本任务就是对篇文档，根据其内容，从预先定义好 的标记集中，找出一个或者多个最合适于该文档的标记。文本自动分类技术从开 始到现在，经历了从基于规贝, i j n 基于统计分类，再到规则和统计相结合的一个过 程。 计算机不具有人的智能，人可通过阅读文章，根据自己的理解能力产生对文 章内容的认识，而计算机却不能轻易的“读懂”文章。所以要对文本进行处理， 转化为计算机可以识别的形式。文本自动分类涉及的技术比较多，要想设计一个 较好的分类系统，必须对这些技术进行深入的了解。 2 1 文本分类概念 分类指把具有共同特点的个体对象归入一类，并把具有共同特点的类集合成 类的过程和方法。文本分类是信息处理的重要研究方向，主要研究如何将具有共 同特点的文本归入一类。分类问题是自然语言处理的一个基本问题，很多相关的 研究都可以归结为分类问题。中文文本自动分类是自然语言处理的经典研究方 向，有着极其重要的应用价值。中文文本分类在信息检索、信息过滤和文本管理 等领域中有着广泛的应用。 一个完整的文本分类过程主要包括以下几部分：首先是预处理，根据采用的 分类模型将文档集表示成易于计算机处理的形式；其次是项权重的计算，根据适 宜的权重计算方法表示文档中各项的重要性；再次是根据预处理的训练集( 己预 知类别的文档) 学习建模，构建出分类器；最后利用测试集文档按一定的测试方 法测试建立好的分类器的性能，并不断反馈、学习提高该分类器性能，直至达到 预定的目标。文本分类的核心技术为构建个具有高准确度和较高速度的分类 器，高效率的分类器才能具有实用性。 文本分类的问题可以这样描述：给定一个决策矩阵，为决策矩阵中的每个元 素赋值，赋值范围为( o ，1 ) ，如表2 1 所示。 4 桂林理工大学硕士学位论文 袁2 1 文本分类决策矩阵 d l d j “ c l a l i a i j a l n c ia i l a u a m c na m a i i n 表2 1 中，c = c i 一，e ，e ) 是预先定义好的类别集合或者标记集合； d = d l ，- 一，d j ，以) 是待分类的文档集合；a 。是一个文档和类别标记的隶属度， 口 0 1 】。 其中，类别标记是一组符号。例如，大多少搜索引擎使用的类别体系，包括 科学技术、社会文化、政治军事、医疗健康、体育健康等。文档对类别的隶属度 应该是基于文档的内容，而不是基于描述文档的元数据( m e t a d a t a ) 。a ，为一条 件概率口。= 尸( c jjd ，) ，如果a 。，= l ，表示第j 个文档完全属于第i 个类别；a 。，= 0 ， 表示文档j 和类别i 完全无关。 文本自动分类存在两个基本假设，即：类名仅仅是标识符号而己，在分类器 的构造过程中它不能提供额外的知识；自动分类所使用的知识必须是内源性的 ( 即从文档中抽取出来的知识) ，而不是外源性的，即必须根据文档语义方面的特 征进行分类，而不能根据元数据( 例如日期、类型、出版物等) 完成分类任务。 2 2 分类预处理 文本分类目的是将未知类别的文本归为预先定义若干类别中的一类或若干 个类。文本分类的系统设计如图2 1 所示。 图2 1 文本分类系统 桂林理工大学硕士学位论文 文本预处理是文本分类的第一个阶段，也是非常重要的阶段，它直接影响以 后的处理工作。通常情况下，需要分类系统处理的文档，不能直接交由分类模型 进行分类，必须经过一定的处理，使文档符合分类模型处理的要求。文本预处理 过程视具体的文档来源不同而有所区别，而且中文和英文的处理方法也有所不 同。对中文文本而言，最常用的文本源就是l q t c m e t 上的h t m l 页面和常见的一 些的文本格式( 如：t x t ) 。 1 去除文档中的格式标记 实际分类系统的待处理文档，有很大一部分是以网页形式存在的。网页文件 的存储格式采用的是超文本标记语言( h y p e rt e x tm a r k u pl a n g u a g e ，h t m l ) ，而 h t m l 文件中都存在大量表示格式信息的标记( t a g ) 。文本分类是基于对文档内 容信息的统计知识，文档中的格式标记是无用的信息，在做分类处理前，一般是 需要滤去的。目前国际公开发布的语料库大多数是以标准通用标记语言( s t a n d a r d g e n e r a l i z e dm a r kl a n g u a g e ：s g m l ) 和扩展标识语言( e x t e n s i b l em a r k u p l a n g u a g e ：x m l ) 表示文档。文档中的格式标记去除主要是指去除语料库中的一 些格式，提取文档里的部分内容，转换为文本分类系统需要处理的格式和内容。 2 过滤停用词和稀有词 目前，在文本信息处理过程中，一般可以选择字、词或词组作为文本的特征 项，分词后的文本成为词的一个集合，有些词和文本的内容不相关，在文本中只 是起辅助作用，不表示实际意义，而且在几乎所有的文本中出现，我们把这些词 称为停用词。停用词携带的信息量少，过滤掉这些词一方面可以对特征项进行粗 降维，从而提高分类器的效率和速度，另一方面，过滤掉停用词后，可以更加准 确地表示文本。因为由于停用词的存在，分散了特征的权重分布，降低了与文本 内容相关的词的权重，使得特征项的集合不能准确地反应文本的本质。文档集中 出现的副词、代词、冠词、介词和连词等不表示实际语义的虚词，都是属于停用 词的范畴。例如：了，啊，吗等。另外，文档集中的一些出现频率极低 的稀有词，也可以考虑滤去。因为这些词数量非常多，而且很有可能是由于拼写 错误而造成的噪音信息。 3 词干化处理 词干化处理是英文文本处理所特有的操作。英文的单词常由前缀、词根、后 缀等部分组成。具体到句子中，单词还有性、数、格以及时态引起的词形变化。 但实际上，一个单词的不同词形，还是可以认为是在表示同一个意思。词干化主 要是去除英文单词中的前缀、后缀，保留单词中的词干部分。例如，词r u l l n e r7 ， r u n n i n g 和r u n s ，这几个单词可以认为都是表述同一个概念，经词干处理 化后提取这几个单词的共同词干，都将被简化成r u n 。这样处理的目的也是为 6 桂林理5 - 大学硕士学位论文 了便于计算机处理，减少文本处理中的特征维数。 词干化处理常常采用基于自动机的规则方法，即将词形变化的规律总结成规 则，然后通过自动机的方法对词形进行转换。转换的过程当中可使用或者不使用 词典。简单而有效的p o r t e r 词干处理器( p o r t e rs t e m m e r , 1 9 8 0 ) 3 】是使用得最为 广泛的词干处理算法之一。 2 3 汉语自动分词技术 英文分词技术已经比较成熟，并且已经展现了很好的发展前景，无论是信息 检索还是主题分析的研究都强于中文，究其根本原因就是中文没有通过分词这到 难关。词是自然语言中最小的有意义的结构单位。汉语文本是基本单字的文本， 汉语的书面表达方式以汉字作为最小单位，词与词之间没有明显的界限标志，因 此，分词是汉语文本分析处理中首先要解决的问题之一。分词技术的相关研究始 于2 0 世纪8 0 年代初，迄今已有2 0 多年的发展历史，研究出了很多各具特色的 方法，从简单的模式匹配、基于规则的方法【4 。1 到基于统计的方法”。虽然这些 方法大大推动了汉语分词研究的发展，但在实际应用中仍然存在汉语词定义模 糊、构词模式自由、汉语词典覆盖能力有限，以及汉语语料库资源缺乏等诸多制 约因素。 当前主要的中文词语分析系统主要有哈工大统计分词系统，自动化所三元统 计模型，清华大学s e g t a g 系统，m i c r o s o f tr e s e a r c h 多国语言处理平台n l p w i n 中的中文词语分析词系统( 双向的c h a r tp a r s i n g ，使用了语法规则并以概率模型作 导向；切词句法分析一体化) ，北大计算语言所分词和词类标注系统( 分词和词类 标注结合起来) 等。 2 3 1 汉语分词常用方法 目前常用的分词方法有：基于字符串匹配的分词算法、基于统计的分词算法、 基于理解的分词算法。 2 3 1 1 基于字符串匹配的分词算法 常用的基于字符串匹配的分词算法有：正向最大匹配分词和反向最大匹配分词。 正向最大匹配分词方法( f o r w a r dm a x i m u mm a t c h i n gm e t h o d ，f m m ) 的基本思 想是：假设自动分词词典的最长词条所含汉字数为n ，则取被处理材料当前字符 串序数中的n 个字作为匹配字段，查找分词词典。若词典中有这样一个n 字词， 7 桂林理工大学硕士学位论文 则匹配成功，匹配字段作为一个词被切分出来；如果词典中找不到这样一个n 字词，则匹配失败。若失败，匹配字段去掉最后一个汉字，剩余的字符作为新的 匹配字段，进行新的匹配，如此进行下去，直至切分成功为止。完成一轮匹配切 分出一个词，然后再按上面步骤进行下去，直到切分出所有的词为止。 例如短语“计算机科学和工程 ，假设词典中最长的词为7 个字，则选取“计 算机科学和工为匹配字段，查找分词词典以匹配这个字段。由于词典中没有该 词，故匹配失败。去掉最后一个字成为“计算机科学和”作为新的匹配字段，查 找分词词典以匹配这个字段，同样匹配失败。再取“计算机科学”作为新的匹配 字段进行查找，假定词典中有“计算机科学”这个词，则匹配成功，切分出第一 个词“计算机科学”。用同样的方法取切分其余的字段。 据统计，f m m 方法的错误切分率为1 1 6 9 1 4 】。因为这种方法在进行切分的 时候对汉语词语边界歧义包括组合歧义和交叉歧异没什么好的办法。因为对组合 歧义来说，通常它都会作为一个分词单位，如“市场中国有企业才能发展”这个 例句，按正向最大匹配分词方法。切分结果为“市场中国有企业才能发展 ， 可以看到，在这个例句中，有两个分词错误，分别为“中国有 这个交叉歧义 和“才能 这个分词的组合歧义。f m m 方法作为一种基本方法由于错误切分率 较大，故一般不单独使用，而是与其他方法配合使用。 反向最大匹配分词方法( b a c k w a r dm a x i m u mm a t c h i n gm e t h o d ，b m m ) 的分词 过程与f m m 方法相同，不过它是从句子或文章的末尾开始处理，每次匹配不成 功时去掉的是前面的汉字。b m m 方法的精度要高一些，它的错误切分率为1 2 4 5 。 在“市场中国有企业才能发展”这个例句中，按照反向最大匹配分词方法， 切分结果为“市场中国有企业才能发展”，可以看到在这个例句中有一个分词 错误，那就是“才能”这个分词组合歧义，应该切分为“才f i l 。 从正向最大匹配分词方法和反向最大匹配分词方法可以看出，配合使用正向 最大匹配分词方法和方向最大匹配分词方法可以识别出分词中的交叉歧义，但是 对组合歧义用两种方法却不能切分出来。 2 3 。1 2 基于统计的分词算法 词网格分词方法是常用的基于统计的分词算法，它具有比较高的分词正确率 和较好的可扩展性。可以通过加入相应的统计信息来扩展不同的功能。 词网格分词的第一步是选择词网格构造。利用词典匹配，列举输入句子所有 可能的切分词语，并以词网格形式保存。词网格实际上是一个有向无 不 ( d i r e c t l y a c y c l i cg r a p h ，d a g ) ，它蕴含了输入句子所有可能的切分，其中每一条路径代表 8 桂林理工大学硕士学位论文 一种切分。图2 2 表示的是字符串“中国人民生活 的切分词网格【1 5 l 。 图2 2 字符串“中国人民生活”的切分词网格 第二步，选择计算网格中的每一条路径的权值。权值通过计算图中每一个节 点的一元统计概率和节点之间的二元统计概率的相关信息得到，然后根据图搜索 算法在图中找到一条权值最优的路径，对应的路径即位最后的分词结果。 2 3 1 3 基于语义的分词算法 基于语义的分词的基本思想是在进行分词的同时进行句法和语义分析。是让 计算机模仿人对句子进行理解，从而达到正确识别词的效果。该算法一般包括分 词子系统、句法语义子系统和总控系统。在总控部分的协调下，在分词的同时增 加对上下文语义信息的处理，从而对分词歧义进行判断。目前基于语义的分词算 法还处于初级实验阶段。 各种中文分词系统都有各自的特点，目前那种分词算法精度更高尚无定论。 对于一个成熟的分词系统，都需要综合不同的算法。 2 3 2 汉语分词中的常见问题 中文是一种非常复杂的语言，要让计算机理解中文十分困难。在中文分词过 程中会遇见一些很难解决问题，例如：歧义和新词识别。 2 3 2 1 歧义识别 歧义是指同样一句话，具有两种或多种不同的分词方法，而根据不同的语义 9 桂林理工大学硕士学位论文 环境很难选择一种最优的方法。歧义切分现象上自动分词中不可避免的现象，是 自动分词中一个比较棘手的问题。对歧义切分字段的处理能力，严重影响到汉语 自动分词系统的分词精度。 分词歧义分为组合歧义和交叉起义【幡1 7 】两种。例如：“以我个人的名义” 和“他一个人在家”中的“个人 就是一个组合歧义字段。句子“从j 、学到 中学”和“从d , 学计算机”中，字串“从小学 则存在交叉歧义。 交叉歧义相对于组合歧义还是比较容易处理的，组合歧义通常要根据整个句 子来判断。目前已经有针对交叉歧义和组合歧义的歧义抽取和消歧的算法，但还 还存在一种“真歧义”，它本身就是汉语言中的歧义问题，例如：“乒乓球拍卖完 了”，我们可以理解为“乒乓球拍卖完了 还可以理解为“乒乓球拍卖完了”。 要想解决这类歧义必须依据上下文语义信息，这无疑对自动分词的效率有很大的 影i l l f i 1 ( 时间上和空间上) ，但目前还无法实现。 2 3 2 2 新词识别 新词的识别就是对未登录词的识别，所谓未登录词是指系统词典中没有收录 的词。例如，汉语中的数量词( 3 4 5 ) ，时间词( 2 0 0 0 年1 月) ，人名( 张三) ，地名( 北 京) ，机构名( 百货大楼) 等，没办法把这些词全部收录到词典中去，但这些词经常 会在局部文本中大量出现，所以识别这些新词也是分词系统的一个重要任务和评 价分词系统的重要指标。 中文人名通常是由姓氏和名字两部分构成。姓氏是相对封闭的，可以作为人 名识别的一个明显的左开端。人名通常可以通过基于统计的方法来识别。方法就 是通过计算一个候选人名的概率值。如果该概率值大于某个值，那么就是一个人 名，反之就不是一个人名。 地名的识别和人名的识别有些不同。有些地名有明显的右边界，例如，北京 市、云台山等。通常通过地名的特点、用字规律、构词规律和地名的上下文规律 等，实现真实文本中地名的自动识别。 2 4 文本表示方法 由于文本分类时，计算机处理的是大规模的真实自然文本，要想使计算机高 效率、高性能的处理自然文本，就必须找到一种理想的自然文本表示方法，使计 算机能够容易的处理。 文本表示最理想的境界就是模拟人所理解的语义，一旦找到了合适的函数来 l o 桂林理工大学硕士学位论文 表示人所理解的语义，那么整个问题就变得简单了。但精确反映人所理解语义的 函数是很难定义的，或者极端一点说，也许根本就不存在。对于形式语言而言， 语义还可以通过机器状态的改变来描述，我们也正是通过这种方式来学习和掌握 机器语言的；可是对于自然语言而言，由于涉及到人这个认知主体的思维活动， 不同的认知主体往往会有不同的理解，自然语言的形式及其意义之间是一种多对 多的关系，很难合理地定义一个反映语义的函数。 既然反映人所理解语义的表示方法很难或根本找不到，那么我们就寻求一种 能够量化、能够形式化、最终可以计算和操作的表示方法。根据“贝叶斯假设”， 假设组成文本的字或词在确定文本类别的作用上相互独立，这样就可以用文本中 出现的字或词来代替文本。虽然这样表示丢失了文本的大量内容信息，但这样可 以使文本的表示和处理形式化，并且在文本分类中取得较好的效果。我们用一个 高度概括的向量表示一篇文本，将文本集表示为一个向量集，这个向量集就等同 于一个二维表格，然后通过对文本集对应的二维向量集进行处理，从而达到文本 分类的目的。 文本表示模型是文本自动分类的一个重要技术问题。文本表示所采用的模型 有很多种，目前通常采用的有布尔模型、概率模型和向量空间模型。 2 4 1 布尔模型 布尔模型是基于集合论和布尔代数的一种简单检索模型，布尔模型在信息检 索中应用比较广泛。应用布尔模型表示文本时，如果一个特征项在文本中出现， 则为“l ”，否则为“0 ”。在布尔模型中，文本的表示形式如下： d f = ( 彬，彬2 ，既) ，k = 1 , 2 ，n 其中，n 为特征项的个数，为0 或l ，表示第k 个特征项在文本i 中是否 出现。布尔模型清楚、简单并且易于实现，但在文本分类中，它的准确率和召回 率较差。 2 4 2 概率模型 概率模型考虑词与词的相关性，把文本集中的文本分为相关文本和无关文 本。以数学理论中的概率论为原理，通过赋予特征词某种概率值来表示这些词在 相关文本和无关文本之间出现的概率，然后计算文本间相关的概率，系统据此概 率做出决策。 概率模型有多种形式，常见的一种是贝叶斯概率模型。贝叶斯概率模型是用 桂林理工大学硕士学位论文 概率架构来表示特征项，将训练实例分解为特征向量和决策类别变量；该模型假 定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作 用于决策变量。尽管这个假定在一定程度上限制了贝叶斯模型的适用范围，然而 在实际应用中，以指数级降低了贝叶斯网络构建的复杂性。在很多领域即使违背 这种假定的条件下，贝叶斯概率模型也表现出相当的健壮性和高效性，己经成功 地应用到分类、聚类中。 2 4 3 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 【1 8 】是目前主要的文本表示方法。 v s m 模型最早由g e r a r ds a l t o n 等人提出。向量空间模型的基本思想是用向量来 表示文本：d = d ( t l ，w i ；1 2 ，w 2 ；：t n ，w n ) ，其中t i ( i _ 1 n ) 为。 系列互不雷同的文本的特征项，w i 为第i 个特征项的权重。 首先我们介绍几个概念： 文本：泛指一般的文献或文献中的片段( 段落、句子或句子组) ，一般指一 篇文章。本文假设文本中不包含除文字以外的其他多媒体信息。 特征项：文本的内容特征常常用它所含有的基本语言单位( 字、词、词组或 短语) 来表示，这些基本的语言单位被统称为文本的特征项，即文本可以用特征 项集表示为d ( t i ，t 2 ，t n ) ，其中t i 是特征项，l f n 。 特征项的权重：对于含有n 个特征项的文本d ( t l ，t 2 ，t n ) ，常用一 定的权重w i 表示特征项t i 在文本d 中的重要程度，即d = d ( t l ，w l ；1 2 ，w 2 ； t n ，w n ) 。我们随后会介绍特征向的抽取和特征项权重算法。 向量空间模型假设一篇文本所属的类别仅于某些词或词组在文本中出现的 频数有关，而与这些词或词组在文本中出现的位置或顺序无关。将文本d 抽象成 以特征项权重为分量的特征向量，d = d ( w l ，w 2 w n ) 。即把t l ，t 2 ，t n 看成一个n 维的坐标系，而w l ，w 2 ，w n 为相应的坐标值，因而d ( w l ，w 2 ， w n ) 被看成是n 维空间中的一个向量。表2 2 显示了一个三维向量空间模型， 空1 1 自j 中每篇文本( d o c l ，d o c 2 ) 都有三个不同的特征项的权值( w l ，w 2 ，w 3 ) 所 组成，此三维向量空间模型可以延伸到n 维。 表2 2 三维向量空间模型 w l w 2w 3 d o c l l 32 d o c 2 2l3 1 2 桂林理工大学硕士学位论文 两个文本d i 和d j 之间内容的相关程度的度量称为相似度s i m ( d i ，吗) 。对于 文本d i ( w i l ，w i 2 ，w i n ) 和d j ( w j l ，w j 2 ，w j 。) 我们可以借助向量之间的某 种距离来量化它们的相似度，常用的方法有向量的内积： s i m ( d 叫d ) = k = l 或用夹角余弦来表示： s i m ( d f ，d ，) = t 尘兰一 ( 暇) ( 吆) 式中n 为特征向量的维数，既，形洼分别为文本d i 和d j 的特征项对应的特 征权值。 向量空间模型具有很多的优越性。文本内容被形式化到多维空间中的一个 点，通过向量形式给出，将文本以向量的形式定义到了实数域中，提高了自然语 言文本的可计算性和可操作性；为词引进权值，通过调节词对应权值的大小来反 映词与所在文本的相关程度，克服了传统布尔模型的缺陷；通过计算文本之间的 相似度，使属性相似的文本尽量聚拢在一起，以提高匹配效率。所以本文中应用 向量空间模型来表示文本。 2 5 类别特征抽取 在向量空闻模型中，通常采用词作为特征项，然而，构成文本的词汇量是相 当大的，因此，表示文本的向量空间的维数也相当大，可能达到几万维。分类时 如果将全部这些向量信息进行统计，那么算法的时效性将会很差。特征空间的高 维性以及文本表示向量的稀疏性时文本分类的最大难点之一。 特征抽取是文本分类的一个非常重要的环节。所有词汇对文本分类的意义是 不一样的，一些通用的、各个类别都普遍存在的词对分类的贡献小，在某一类别 中出现的比重大而在其他类别中出现比重小的词汇对分类的贡献大，为了提高程 序的效率和运行速度，增强分类精度，每一类应该去除那些表现力不强的词，抽 取出针对该类的具有该类特点的特征项集合。经过抽取后，虽然文本向量中的特 征项少了，有些文本信息丢失了，但抽取出的特征项都是有比较强的类区分能力 的，它们能更好的去除各类别的共性，更好的突出类别的特性，因此好的抽取算 法，不但不会降低分类系统的准确性，反而能使系统的精度提高。 在文本处理中，目前主要的特征抽取算法有：文档频率( d o c u m e n t 1 3 桂林理工大学硕士学位论文 f r e q u e n c y ，d f ) 、互信息( m u t u a li n f o r m a t i o n ，m i ) 、期望交叉熵( e x p e c t e d c r o s s e n t r o p y ，e c e ) 、信息增益( i n f o r m a t i o ng a i n ，i g ) 、c h i 概率统计和基于矩阵 分解的特征选择。 2 5 1 文档频率 文档频率( d f ) 是指训练集中包含特征项的文本总数。所谓文本包含特征 项是指，特征项在该文本中出现，它忽略了特征项在文本中出现的次数。通常用 包含特征项的文本数与文本总数的比值来表示文档频率： d f ( t ) = 絮黧篙 它是最简单的评价函数，计算量小是它最大的特点。d f 评价函数的理论假 设是出现频率小的特征所含信息量小，但这一假设显然是不全面的。因此，在实 际运用中一般并不直接使用d f ，而是把它作为评判其它评估函数的一个标准。 2 5 2 互信息 互信息( m i ) 这个概念来源于信息论，用于度量一个消息中两个信号之间 的相互依赖程度。现在，互信息已经被广泛应用于相关词统计语言模型中，在文 本分类中它主要用于衡量特征项与类别之间的统计关联程度。特征项t 与类别g 的互信息计算公式如下： m i ( t ，c ：)，一丛! ：鱼