（计算机软件与理论专业论文）文本分类相关技术研究.pdf

摘要 文本分词和特征表示是文本处理领域的两个重要问题。本文在这两个问题上 提出了新的见解，并且在文本分类的应用环境中对提出的方法进行了探讨。 大部分文本分词系统都是基于词典的，词典的存储机制对于分词的效率有决 定性的影响。本文调整了互关联后继树的索引结构，用来存储中文词表。文中详 细介绍了这种词表结构，并描述了建立在这一词表上的分词算法。此算法利用词 语的词性信息，用匹配句模的方式排除切分歧义，取得了不错的效果。 传统的文本表示方法以词语作为表示文本特征的单位，这种方法有一定的局 限性。本文提出文本的概念特征表示，用概念取代词语作为文本的特征，以更简 洁的方式表现原文。我们介绍了知网语义词典，提出了一种对其中的概念进行归 结的算法。将归结后的概念信息附加在词表上，就建立了词语和概念之间的映射。 这样，在分词过程中，就可以同时产生文本的概念特征表示。 我们将概念特征表示模型应用于文本分类中，以验证其有效性。我们选取了 k n n 分类方法和带词频的关联规则分类法，将它们移植到概念表示模型上，给 出详细的算法描述，并通过实验证明概念表示模型具有更好的分类效果。 关键字： 文本分类分词算法互关联后继树概念特征表示知网 中图分类号： t p 3 9 1 a b s t r a c t s e g m e n t a t i o na n dt e x tf e a t u r er e p r e s e n t a t i o na r et w oc r u c i a lp r o b l e m si nt e x t p r o c e s s i n gr e s e a r c h t h i st h e s i sp r o v i d e sn e wp e r s p e c t i v e so nb o t h ，a n d d i s c u s s e s t h e mi nt h ec o n t e x to ft e x tc l a s s i f i c a t i o n m o s tt e x ts e g m e n t a t i o ns y s t e m sa r eb a s e do nad i c t i o n a r y ，w h o s ew o r k i n g m e c h a n i s mh a sac o n c l u s i v ei n f l u e n c eo nt h ee f f i c i e n c yo fs e g m e n t i n gat e x t i nt h i s p a p e r ，w ea d j u s tt h ei n t e r r e l a t e ds u f f i xt r e e ( r e s t ) i n d e x s t r u c t u r et os t o r eac h i n e s e w o r dl i s t w ed e s c r i b et h i ss t r u c t u r ei nd e t a i la n de l a b o r a t eo nt h ea l g o r i t h mo f s e g m e n t i n gt e x tu s i n gt h i ss t r u c t u r e i tu t i l i z e dt h ep a r t - o f - s p e e c hi n f o r m a t i o no ft h e w o r d st om a t c hs e n t e n c em o d e s ，t h u sa v o i d i n gs e g m e n t a t i o na m b i g u i t i e s ，t h i sm e t h o d w o r k sn i c e l yi ne x p e r i m e n t t r a d i t i o n a lt e x tr e p r e s e n t a t i o nm e t h o d su s ew o r da st h eu n i to ft e x tf e a t u r e ；t h i s s c h e m ed o e s n tw o r kw e l li nc e r t a i nc i r c u m s t a n c e s w eb r i n gf o r w a r da c o n c e p t - b a s e dr e p r e s e n t a t i o nm o d e l ，w h i c hu s ec o n c e p t si n s t e a do f w o r d sa st e x t f e a t u r e s i ti sam u c hm o r ec o n c i s es t r u c t u r e w ed e s c r i b eh o w - n e td i c t i o n a r y ，a n d p r o v i d ea na l g o r i t h mt or e d u c et h en u m b e ro fc o n c e p t si ni t b ya t t a c h i n gt h ec o n c e p t i n f o r m a t i o no n t ot h ew o r dl i s t ，w ee s t a b l i s ht h em a p p i n gb e t w e e nw o r d sa n dc o n c e p t s t h u s ，w ec a ns e g m e n tat e x ta n dp r o d u c ei t sc o n c e p t - b a s e dr e p r e s e n t a t i o ni nas i n g l e s t e p w ea p p l yt h en e w r e p r e s e n t a t i o nm o d e lt ot e x tc l a s s i f i c a t i o nt ot e s ti t s e f f e c t i v e n e s s i np a r t i c u l a r ，w ec h o o s ek n nc l a s s i f i e ra n da s s o c i a t i o nr o l ec l a s s i f i e r , a n dp o r tt h e mo n t ot h ec o n c e p t - b a s e dr e p r e s e n t a t i o nm o d e l t h ea l g o r i t h m sa l e r e f o r m u l a t e d ；e x p e r i m e n t ss h o wt h a tt h en e wm o d e li sab e t t e ra l t e r n a t i v et h a n w o r d - b a s e dr e p r e s e n t a t i o nm o d e l k e y w o r d s ： t e x tc l a s s i f i c a t i o nt e x ts e g m e n t a t i o n i n t e r r e l a t e ds u f f i xt r e e ( i r s t ) c o n c e p t - b a s e dr e p r e s e n t a t i o nm o d e l h o w n e t c l a s s i f i c a t i o ni d ： t p 3 9 1 2 引言 信息时代，人类的知识以惊人的速度增长，如何组织和管理这些知识成为亟 待解决的问题。随着知识的电子化表示逐渐取代传统的书籍和文档，电子文本的 计算机自动处理也形成了一个重要的研究领域。本文关注的文本分类问题就是这 个领域的一个重要分支，其目标是使计算机代替人根据内容判断文本所属的类 别。在研究中，采用机器学习的方法来达到目标。 文本分类在信息处理的各个领域都发挥着重要作用：它可以为文本检索提供 支持，在检索之前确定类别可以减小搜索空间；可以用于过滤信息，比如，区分 垃圾邮件，封锁网络上的不良信息等；可以为动态增长的文档系统提供自动归档 功能。人们对于文本信息提出越来越多的处理需求，因此文本分类有着广泛的应 用前景。 本文的主要贡献在于提出了种新的文本表示模型，并基于这一模型，改进 了两种常见的文本分类算法，来检验模型的有效性。具体而言： 1 本文采用互关联后继树表示词表的结构，并提出了在这个词表结构上分词的 算法。互关联后继树原本是文本索引的结构，和传统的索引结构相比具有更 小的膨胀比，提供更多的检索功能。本文对互关联后继树作出了一定的改动 以存储词表，利用它可以高效率地匹配词语。我们采用了全切分的策略来分 词，并用词语的词性信息和中文旬模排除错误的切分方案。 2 本文以概念作为文本的特征，提出了文本的概念表示模型。它形式上和向量 空间模型类似，但是向量的维度是概念而不是词语。我们选用了“知网”语 义词典，但是其中的概念太过细化而不能用于文本分类的应用。因此本文提 出了概念的归结算法，把归结后的概念附加在互关联后继树词表上，来确立 词语和概念之间的映射关系。 3 。本文将传统的文本分类算法迁移到概念表示模型上。我们选取了具有代表性 的k n n 算法和关联规则分类法，根据概念表示模型的特点，对它们进行了 一定的调整。本文详细描述了由文本转化为概念表示的方法，对调整后的算 法，包括训练算法和分类算法给出了形式化的描述。 第一章文本分类领域综述 1 1 研究背景 伴随着关系数据库的理论不断成熟，结构化数据的存储和检索技术也日趋完 善。现今，大量的数据存在于各种商业数据库中，在办公自动化、电子商务等各 个领域中发挥着巨大作用，也为人们的日常的工作生活带来便利。同时，非结构 化的数据，如文本、图像等，在人们所接触的信息中仍然占据很大的比重。非结 构化的特征使其不利于计算机加工处理，因此至今为止，关于这些数据的处理仍 然是研究的热点，在非结构化数据的每一个研究领域中都存在着多种不同的方法 和手段。虽然已经出现商业上非常成功的应用，如g o o g l e 等搜索引擎，但是总体 来说，这一领域的研究还没有达到非常成熟的阶段。 文本是非结构化数据中的一种。近年来，个人计算机不断普及，因特网迅猛 发展，文本数据充斥着人们的数字生活。网页、电子书籍、电子文档浩如烟海， 人们急需一种方式来管理、操纵、检索这些数据，文本处理领域的研究目的就是 解决这些问题。 文本处理领域包括很多研究方向，如文本索引，文本检索，文本分类，自动 摘要，机器翻译等等，他们对文本的存储、查找、理解、翻译等各种实际需求提 供了解决途径。在每个研究方向，都不断涌现着新的方法和尝试。多种学术期刊、 学术会议，使得最新的研究成果得以展示。如文本检索领域的t r e c 会议，采用 竞赛的形式，以一个公共的文本集作为基准，对各检索系统的准确性、效率等各 个方面作出综合的评价，以判断一种检索方法的优劣。d u c 是文本理解方面重要 的学术会议，每年世界范围内各高校和研究机构都会在这个会议上公布最新的研 究进展。 文本分类是文本处理领域的重要研究方向之一。在大多数情况下，文本本身 不包含分类信息，往往需要人阅读文章内容才能判定其类别，在需要对海量文档 进行分类的应用中，这种人工方式显然是不可行的，自动文本分类可以在一定程 度上解决这一问题。借助于计算机的自动分类系统，使用者可以方便准确地定位 所需的信息或分流信息。作为信息过滤、信息检索、搜索引擎、文本数据库、数 字化图书馆等领域的技术基础，文本分类技术有着广泛的应用前景。 1 2 文本分类理论基础 文本分类本质上是一个机器学习的问题，具体来说，就是训练一个文本分类 器( 软件) ，应用它来完成分类操作。文本从机器表示的角度讲，就是一个字符 4 串，所以任意两篇文本都具有不同的机器表示，要达到分类的目的，必须采用能 够体现不同文本2 _ 1 u 7 共性的一种表示方法，一种基于文本特征的表示方法。然后， 分类器必须建立文本的特征和类别之间的映射。这种映射的建立依赖于一定数量 的由专家手工标定类别的文本，我们把它们称为训练文本，不同的分类方法以不 同的手段学习这些文本的特征和它们所属类别之间的对应关系，并且记录这种对 应关系，用来在实际分类过程中确定待分类文本的类别。这就是文本分类的大致 过程。大体上，可以分成三个阶段：生成文本表示，分类器的训练过程和实际分 类过程。如下图所示： 文本表示 分类过程 训练过程 下面分别讲述文本分类的三个方面： 1 2 1 文本表示和特征选择 文本的特征表示要尽量反映其语意内涵。这个问题可以从两个方面考虑，一 方面是特征的定位，即文本包含的哪些信息可以作为特征，另一方面是这些特征 的组织方式。 一篇文本在语法层次上可以按词语、短语、句子或者段落来划分，他们都可 以作为文本的特征，但是，随着这些要素所处的语法层次逐渐增高，要素的数量 呈指数型增长，所以一般的分类系统不会以句子或段落作为特征。大多数选择短 语和词语作为特征，也有一些将n g r a m ( 文章中相邻的n 个字) ，词性，语义模 式等作为特征的做法。 在以词语作为文档特征的分类系统中，并不是所有的词语都可以作为特征。 首先必须排除一些和原文语义完全无关的词语，比如“的”、“地”、“得”， 语气助词，连词等，我们把它们称为停用词，在扫描文档时应该忽略。对于其他 词语，它们反映语义特征也有程度的差别，因此应尽量选取携带更多关键信息的 词语，具体方法将在下面特征选择的部分详细讨论。 在确定了文本的特征之后，要把这些特征以结构化的方式组织起来。一种较 为常见的方式是把每个文档表示成一个向量，向量的每个维度代表它的一个特 征，这种表示模型称为向量空间模型。具体又可以分为布尔型和非布尔型两种。 布尔向量模型中，每个特征值只能取1 或0 ，代表此特征在文本中是否出现；非布 尔模型则考虑了特征在文本中的出现频度，特征值一般用t f * i d f 的计算公式，在 这个模型中，文档之间的相似度由它们对应向量之间的夹角反映。 对于如何选择文本特征的问题，存在多种方法。大体上可以分成两类：基于 信息论和统计分析的方法，以及基于字典的方法。基于字典的方法准确性较高， 但字典往往是领域相关的，而且其建立过程需要大量的时间精力，因此大多数现 有的特征选择算法都是基于信息论和统计分析的。特征选择的具体步骤如下： 1 从训练文档库中提取得所有特征项，构成文档特征集合f ； 2 对集合f 中的每一项用下列某一种方法进行打分，然后按分值由高到低进 行排序； 3 假设需要选取n 个文档分类属性，则从f 中选取分值最高的n 个项，构成 最终的分类属性集f s 。f s 将用于文档分类的训练与测试。 特征选择方法有如下几种： a 信息增量( i n f o r m a t i o ng a i n ) 信息增量表示文档中包含某一特征值时文档类的平均信息量。它定义为某一 特征在文档中出现前后的信息熵之差。假定c 为文档类变量，c 为文档类的集合， d 为文档，伪特征( 以下各节同此) 。对于特征f 其信息增量记为i g ( f ) ，计算 公式如下： a ( f ) = h ( c ) 一日( c i 厂) = 一罗p ( c ) l o g ( p ( c ) ) 葱 + p ( f ) x p ( cif ) l o g ( e ( cl ，) + p ( 于) p ( ci ) l o g ( e ( cl 于) j 一 _ 2 荟川昭c 焉舄嘶厕吲蒜静 在只考虑单个类的时候，则有： i c ( c ，) | p 川。g ( 揣) + p ) l o g ( 揣) b 互信息( m u t u a li n f o r m a t i o n ) 互信息是用于表征两个变量间相关性的。对于文档类别c 和特征f ，其互信息 记蔓j m i ( c ，f ) ，计算公式如下： 龇舻。篇， 显然，当f 独立于c 时，m i ( c ，f ) 为0 。在应用时一般取平均值： 埘n m ( ，) 。荟p p ) m j ( c ，) c x 2 统计 x 2 统计也是用于表征两个变量问的相关性，但它比互信息更强，因为它同时 考虑了特征存在与不存在时的情况。对于文档类别c 和特征f ，其x 2 统计的计算公 式如下： 施= 致篙瑞铲 当c 与f 相互独立时，x 2 ( c ，f ) 为o 。和互信息类似，取平均值： 盔( 舻善p ( c ) z 2 ( c ，) d 交叉熵( c r o s se n t r o p y ) 交叉熵和信息增量相似，不同之处在于信息增量中同时考虑到了特征在文本 中发生与不发生时的两种情况，而交叉熵只考虑特征在文本中发生一种情况。对 于特征f ，其交叉熵记a c e ( f ) ，计算公式如下： c e ( d = 荟p ( c ，) l o g ( 嵩舄 在只考虑单个类的时候，则有： c e ( c ，) 卵。g ( 器) - e 证据权值( w e i g h to f e v i d e n c e ) 证据权值反映的是类概率与在给定某一特征值下的类概率的差。对于特征f ， 其证据权值记为w e ( f ) ，计算公式如下： w e ( f ) = 荟p ( c 以肿g ( 絮者) l 这里，n 是训练文档实例数目，且有 o d d s ( x f ) = e ( x ；) 一0 p ( z 。) ；1 p ( x f ) 0a e ( x 。) 1 在只考虑单个类的时候，则有： ：一矿矿0一墨 丝蜀丽塑填 坩一一彬一一 腮( c i ，) _ p ( c ) p ( ，o g ( 毫者) i f f i s h e r 判别式 f i s h e r 判别式是一种基于统计的方法，表示某一特征在类间分布和类内分布 之比： 黝砌；兰掣堕塑竺! 竺生 。高( 荟，) _ 肿，) ) 2 ) 这里， 绯，) 2 高似j ) x 似，) 一n ( d ，1 ) n ) 上面，n ( d ，f ) 和n ( d ) 分别表示特征f 在文档d 中的频数和文档d 中总的特征频数。 1 2 2 文本分类方法 文本分类算法实质上就是建立文本特征到类别的映射关系，不同的算法在训 练和测试阶段都有着显著的区别。从方法学的角度划分，文本分类的方法大致上 有三种：基于统计的分类方法，人工神经网络和基于规则的方法。下面分别讲述 这些方法： ( 一) 基于统计的方法： a n a i v eb a y e s 方法 这种方法根据一个概率确定文档d 的分类情况：p ( c ，l d ) ，即对于文档d 来说 类别q 的条件概率。这个概率越高，d 越有可能属于q 文档类。 根据贝叶斯公式：p ( a ) p ( c l d ) - p ( c ) p ( d l c j ) ；p ( c 一) 眦p ( c j = 掣肌删) 一和删h ) 对于一定的训练文档集，假设它能够真实反映文本类别的分布，则很容易获 得一个类别的概率：p ( c ，) 霉鬻，问题集中于尸 h ) 的计算。 如果我们假设文本的特征相互独立，贝t j p ( d i c j ) ；p ( m l c j ) ，其中峨是文 档d 中的特征词，这种模型称b i n a r yi n d e p e n d e n c em o d e l 。p l c ，) 还有一些不 同的计算模型，如最大似然模型( m a x i m u ml i k e l i h o o dm o d e l ) 、多项式模型 ( m u l t i n o m i a lm o d e l ) 、泊松模型( p o i s o nm o d e l ) 等。 b k n n ( kn e a r e s tn e i g h b o r s ) 方法 k p d 哟训练过程保存每一个训练文档向量和它所属的类别，分类时，在向量 空间中找到待分类文档向量的k 个最近邻。在此基础上，给每一个文档类打分， 分值为k 个训练文档中属于该类的文档和测试文档之间的相似度之和。然后按照 分值对文档类排序，若最高分值大于一定的闽值籼，则可以确定它为待分类文档 所属的类别。 文档d 属于一个类别q 的分值为： 配0 r e d , c 1 ) 盈i 薹，m ( 州加( 啪一b ；，其中y ( a 产弘惦鼍 d ，t wi ” 一j 广1 c 类中心向量法( r o c c h i o 方法) 这种方法用训练文档向量求出每一个类别的中心向量，来代表整个类别。在 分类阶段，对于某一给定的文档d ，计算文档向量和每个类别中心向量的相似度， 然后按相似度进行从大到小排序。相似度最大值所对应的类别，就是文档的所属 类别。如果希望文档可以属于多个类别，可以设定一个阙值，文档属于相似度超 过阈值的所有类。 中心向量的计算公式如下，其中c f j 是类f 的中心向量的莉维。初始时，中心向 量的每一维都为0 ，然后，对训练文本进行批处理，每次都对各个中心向量产生 影响。 旷c 一声瞀叫揣一般御洳q 阻同 a 支持向量机s v m 支持向量机( s u p p o r tv e c t o rm a c h i n e 或s v m ) 是在统计学习理论的基础上发 展而来的一种机器学习方法，它基于结构风险最小化原理，将原始数据集合压缩 到支持向量集合( 通常为前者的3 5 ) ，学习得到分类决策函数。其基本思 想是构造一个超平面作为决策平面，使正负模式之间的空白最大。支持向量机在 解决小样本、非线性及高维模式识别问题中表现出了许多特有的优势，并能够推 广应用到函数拟合等其它机器学习问题中。s v m 已初步表现出很多优于已有方 法的性能，并在很多领域得到了成功的应用，如：人脸识别、手写体识别、文本 分类等。在文本分类方面s v m 的表现尤为突出，其分类的查全率和查准率几乎 超过了现有的所有方法。 9 h 线性可分情况下的最优分类线 s v m 的基本思想可用上图的两维情况说明：实心点和空心点代表两类样本， h 为分类线，h i 、h 2 分别为过各类中离分类线最近的样本且平行于分类线的直 线，它们之间的距离叫做分类间隔。所谓最优分类线就是要求分类线不但能将两 类正确分开d ) l l 练错误率为0 ) ，而且使分类间隔最大。分类线方程为z w + 6 。0 ， 我们可以对它进行归一化，使得对线性可分的样本集 i ，y i ) ，f = 1 ，n ，x e r 4 ，y + 1 一1 ) ，满足 y i 【( w 。t ) + b 卜1 0 ，i = 1 ，一，n 此时分类间隔等于2 川叫i ，使间隔最大等价于使m 1 2 最小。满足以上公式且 翱。i i z 使2 ”“最小的分类面就叫做最优分类面，h 1 和h 2 上的训练样本点就称作支持向 量。 基本的s v m 是针对两类分类问题的，为了实现对多个类别的识别，需要对 s v m 进行扩展。常用的s v m 多类分类方法有o n e v s r e s t 、o n e v s - o n e 、e c o c ( e r r o r c o r r e c t i n go u t p u tc o d i n g ) 【b e t 9 9 ，g h a 0 0 、d a g s v m 【p c s o o 】和二叉树 等方法。文献 h l 0 2 对o n e v s r e s t 、o n e v s o n e 和d a g s v m 三种方法进行了比 较，实验结果表明d a g s v m 方法要优于其它两种方法。w e s t o n 和w a t k i n s 【w w 9 9 1 对s v m 的理论进行了扩充，使其一次就可以完成多类分类，但是实验结果显示 其分类查准率要低于o n e - v s r e s t 和o n e - v s o n e 方法。 ( 二) 人工神经网络a n n 人工神经网络是对人类大脑的一种模拟。它由一组处理单元和它们之间的联 接组成：处理单元包括输入单元，隐藏单元和输出单元，它们具有局部内存，并 可以完成局部操作，可以接受多个输入信号，产生一个输出信号，这个信号可以 传播到多个联接上：联接能够以一定的权值传送信号，这些权值在神经网络的训 练过程中可以动态调整；各处理单元可以并行运行。它适于学习复杂的非线性映 射，主要应用于语音、视觉、知识处理、辅助决策等方面。根据网络结构和学习 算法的不同，人工神经网络分为多层感知器、自组织映射和h o p f i e l d l 网络等。一 个典型的三层人工神经网络如图所示： 文本分类问题的输入可以用“属性值”对的向量表示，因此很适于用人工神 经网络解决。下面以一个三层的反向传播( b a c kp m p a g a t i o n ) 人工神经i 网络为例来 说明a p i n 在文本分类中的应用。该网络具有一个输入层，一个输出层和一个隐 藏层。b p 算法是非循环多级网络的训练算法，其学习过程由正向传播和反向传 播组成，输入值经过非线性变换从输入层经隐单元逐层处理，并传向输出层，每 一层神经元的状态将影响到下一层神经元状态，如果在输出层不能得到期望的输 出，则转入反向传播，通过修改各联接的权值，使误差信号最小。 对于三层b p 神经网络，其输入向量为d o ，f ：，f 。) ，输出向量为 c = ( c i ，c ：，) ，输入层为n 个神经元，隐藏层为h 个神经元，输出层为m 个神经 元。n 即为输入向量维数，m 即为输出向量维数，隐藏层的神经元个数h 可认为与 问题相关，目前的研究还难以确定h 与问题的类型和规模之间的函数关系。输入 层和隐藏层之间、隐藏层和输出层之间的联接权重在神经网络的训练阶段，根据 训练样本学习得到。 给定一段文本及其特征集，输入层神经元的个数设定为特征集的大小，输出 层神经元的个数设定为类别集的大小，定义该神经网络的输入向量第i 个分量的 值为： 阻文本中存在特征集中的第i 个特征词 1 1 0 ，反之 在训练神经网络的时候，定义输出向量第j 个输出值： f 1 ，文本属于类别集中的第，类 1o ，反之 使用b p 算法进行训练，当网络稳定下来后，联接的权值就作为文本分类时的 知识。利用这个神经网络就可以完成文本分类的任务。 ( 三) 基于规则的分类方法 a 决策树分类法 决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数 1 i 被表示为一棵决策树。一般来说，一个决策树由个根节点n l 、一组非终止节点 n i 和一些终止节点t j 组成，可对t i 标以各种类别标签。不同的终止节点上可以出现 相同的类别标签。一个决策树对应于特征空间的一种划分，在每个划分区域中， 某个类别的样本占优势，因此，可以标以该类样本的类别标签。在文本分类的应 用中，决策树的每个节点对应于一个文本特征。对于一个待分类的文本，从决策 树树根开始，测试每个节点的文本特征值，然后延相应的树枝向下移动，当到达 终止节点时，就确定了该文本的分类。 现在已经存在很多广为应用的决策树算法，如i d 3 、a s s i s t a n t 干 i c 4 5 等等。 b 基于关联规则的分类法 关联规则( a s s o c i a t i o nr u l e ) 是数据挖掘领域的一个重要概念，它可以反映 给定数据集中项之间的潜在联系。一般的算法会找到所有支持度和置信度大于一 定阈值的规则。当应用到文本分类领域中，需要挖掘的规则就非常有针对性，即 规则头只包含类别标号的规则，我们把他们称作分类规则。文本分类领域的规则 挖掘还有着不同于关系数据库的一些特点：首先，不同于关系数据库中的模式， 文本的特征表示包含大量的属性，为避免组合爆炸，必须对挖掘算法作出一定调 整。其次，文本的特征属性往往不是离散的，包含连续属性的关联规则挖掘问题 仍然是研究热点，至今尚没有确切有效的方法。 基于关联规则的分类有三种流行的方法：a r c s 、关联性分类和c a e p 。 a r c s ( a s s o c i a t i o nr u l ec l u s t e r i n gs y s t e m ) 方法首先使用聚类技术获得关联 规则，然后使用这些规则进行分类。a r c s 中挖掘的规则的形式为： a q n 1 aa q n 2 竺争a t 其中，。1 和山。2 是连续属性的区间上的测试，a 。是类别标签。其准确 性可以与c 4 5 媲美。 关联分类方法，首先采用迭代方法( 女r l a p r i o r i ) 找到所有频繁的、精确的可 能规则，然后对这些规则按照一定的优先次序排列，当处理一个样本的时候，满 足的第一条规则用于对其分类。这种方法挖掘的规则形如：c o n d s e t y ，其中 c o n d s e t 是项的集合，v 是类标号。 c a e p ( c l a s s i f i c a t i o n b y a g g r e g a t i n g e m e r g i n g p a t t e r n s ) 方法用到了显露模式 的概念。显露模式( e m e r g i n gp a t t e r n s ) 简而言之就是在不同类别的样本集中支持度 相差很显著的项集，其中的项可能是属性的相等测试，或区间测试。e p 对不同 的类别具有很强的区分能力，这体现于它在不同类别中支持度的比例，这个比例 称为增长率。c a p e 挖掘满足给定支持度和增长率阈值的e p 。对一个待分类的样 本，根据其满足的e p 所代表的类别计算样本的得分，以决定它的类标号。 1 2 3 性能评估 对于分类系统的评估可以考察很多指标。如空间、时问效率，其中时间效率 又包括训练时间和分类时间；分类系统要成为一个通用系统，还要有一定的领域 独立性：其他指标如可扩展性、时间无关性等也同样重要。但是，这些指标尚没 有定量测量的标准，因此，在实践中更多采用的是信息检索领域中的查全率和查 准率作为系统性能的度量标准。 文本分类的应用可以分为两种：单类赋值和多类排序。单类赋值对一个文本 只赋予一个类标签；而多类排序可以将一个文本针对多个类别评分排序，文本更 有可能属于评分较高的类别。 f 一) 单类赋值 文档分类中普遍使用的性能评估指标有查全率( r e c a l l ，简记为r ) 、查准率 ( p r e c i s i o n ，简记为p ) 。这两个指标一般是针对单个文档类别计算的，见下表： 真正属于该类的文档数真正不属于该类的文档数 i 判断为属于该类的文档数 ab l 判断不属于该类的文档数 c d 这时，r 和p 分别定义为： ，= 一口- 一a+c a + 6 还有其他一些评价指标如： a c c u m c v ：j 型! 一 e r f o f ；1 a c c u r a c v ：坠坚l 一 。 a + b + c + d 。 a + b + c + d 如果要对分类的整体性能进行评价，通常使用宏平均( m a c r o a v e r a g i n g ) 和 微平均( m i c r o a v e r a g i n g ) 。 宏平均是先对每一个类统计r 、p 值，然后对所有的类求r 、p 的平均值，即 f 一( 。r o ) i c l歹一( 。p 。) i c l 微平均则是先在全局建立类似上表的统计表，然后根据这个表进行计算，即： 一墨a p 了蔫 意台 显然，宏平均是对类的平均，所以容易受小类的影响，而微平均则是对文档 的平均，容易受到大类的影响。 查全率r 和查准率p 各自独立反映了分类系统性能的一个方面，使用者当然希 望两者都尽量高。但是，r 丰叻值是互相影响的，提高，会引起p 的减小，反之亦然。 为方便系统问性能的相互比较，需要将二者综合考量，有两种做法： 一种方法是选取r 和p 相等时的值来表征系统性能，这个值叫做平衡点 ( b r e a k 州e np o i n t ，简称b e p ) 值。当然，有时通过测试可能得不到r 和p 相等的 值。这时取最接近的r 和p 值的平均值作为b e p 值，称为插值b e p 。实验表明，b e p 在0 5 至j l o 6 之间可以获得较好的用户满意度。 另一种常用的方法是f 钡0 量 l a 9 4 ，其计算公式为： = 锵= 8 + 1 壁三 r p 其中，卢是一个用来调节查全率和查准率权重的参数。卢一般取值为1 ，这 时上式转化为： e 一2 r p ( r + p ) 显然，b e p 是_ _ f 1 的特殊形式，因为当r = - p 时，有，1 = b e p 。 ( 二) 多类排序 对于多类排序问题，首先应给类的评分确定一个阂值，以确立文档和类之间 的所属关系。对每一个输入的测试文档，都会返回一个排序后的文档类列表。这 时，两个指标分别定义为： 找到的该文档所属的正确类别数目 判断为该文档所属类的类别数目 找到的该文档所属的正确类别数目 该文档所属的所有类别数目 整个分类器的评估应该是对所有测试文档的这两个指标的统计平均。通常使 用的统计平均为1 1 点插值平均查准率( i n t e r p o l a t e d1 1 - p o i n ta v e r a g ep r e c i s i o n ) 。 第二章中文分词问题的研究 汉语文本有着与英语、法语、德语等印欧语言显著不同的特点。英语在书写 时，词与词之间用空格隔开，因此空格就成为英语文本中词的自然分界，而汉语 文本就是由汉字组成的字符串，词与词之间没有明显的界限；英语中存在动词的 时态变化，名词的单复数变化，而汉语中不存在这些问题。这就决定了针对英文 语料和中文语料，在预处理文本的阶段需要做不同的工作。 将英文文本转化为以词语为特征的表示，要从词语的不同时态和复数形式中 提取词根，这个过程称为s t e m m i n g 。对于中文文本，要将其转化成特征表示，必 须将原文本进行词语的切分。汉语文本分词技术不但是文本分类的基础，在机器 1 4 翻译、自然语言理解等很多文本处理的领域中都有广泛的应用。人们提出过很多 解决分词问题的方法，但是哪种方法可以达到最优的效果，还没有确切的结论。 因此可以说，分词仍然是汉语文本处理中的重点和难点问题。 2 1 分词的手段与方法 中文分词在总体上可以分为两种手段：基于词表的切分和基于统计的方法。 f 一1 基于词表的切分 这种方法切分文本时，要参照一个固定的词表，若字串存在于词表中，可以 将它作为一个词切分出来。采用这种方式，可以保证每个切分好的字串都是一个 中文词语，但是切分的结果仍然有可能是错误的，有两种情况： 一种情况是，切分的词语组合在一起可能没有意义，甚至不符合基本的语法 规范，比如：“他的确认为是这样”，这样一句话有两种切分方式： 他的确认为是这样( 正确) 他的确认为是这样( 错误) 对于第二种方式，虽然所有词语在词表中可以找到，但是显然整个句子是无 意义的。 另一种情况，虽然词语的组合有意义，但是并不是原文的含义，这是一种带 有歧义的切分：比如，“你的车锁好了么”这样一句话，至少有以下两种切分方 法： 你的车锁好了么 你的车锁好了么 哪种切分方式正确完全取决于原文的上下文和作者的意图。我认为，在自然 语言的机器理解发展到一定程度之前，这种切分歧义是难于避免的。因此现在的 排歧方法往往针对于第一种歧义切分。 切分的歧义基本上有两种类型。一类是交集型歧义字段，比如在a b c 这个字 符串中，a ，a b ，b c ，c 都在词表中，贝i j a i b c ，a b i c n 种切分都是可能的。据 统计，这种歧义字段占全部歧义字段的8 5 以上。另一种是组合型歧义字段，比 如在a b 这个字符串中，a ，b ，a b 都是词表中的词，这时候我们面临是否对a b 进一步切分的选择。 排歧有很多种方法，下面列举几种： a ) j f 向最大匹配法( 由左到右的方向) ； b ) 逆向最大匹配法( 由右到左的方向) ； c ) 最少切分( 使每一句中切出的词数最小) 。 采用最大匹配是由汉语本身的特点决定的。由于汉语单字成词，所以最小匹 配往往产生无意义的单字切分，而且，汉语中很多长词都是由较短的词构成的。 一般来说，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少：统计 结果表明，单纯使用正向最大匹配的错误率1 1 6 9 ，单纯使用逆向最大匹配的 错误率为1 2 4 5 。但是这样的精度还远远不能满足实际的需要。实际的分词系统 往往以一种切分方式作为基础，用其他调整方式提高分词的准确度。比如，先用 正向最大匹配做初步的切分，在切分的边界做歧义探测，再利用词语相关性的信 息来确定采用那一种切分方案。 在词语切分的过程中可以同时标定词性等语法要素。这种标定也可以为分词 决策提供帮助，因为正确切分方式一定遵循汉语的语法规则，而错误的切分往往 违反相应的语法规则。本文提出的分词算法里利用词性信息和汉语句模排歧，取 得了不错的效果。 词语切分往往是以句子为单位进行的，因为标点符号是自然的语句分隔符。 但较长的语句中产生切分歧义的概率仍然很大。文本中有一些词语带有较少的语 义信息，仅仅发挥标示语句结构的作用，可以把这些特殊词语作为分隔符，发挥 切分标志的作用。引入切分标志以后，切分单位的长度减小，有利于减少切分歧 义，加快分词的速度。 对于基于词表的切分方法，其准确程度完全依赖于词表的质量。但是词表的 选择是一个棘手的问题。一方面，我们希望采用全面的词表，因为它能识别出更 多的词语，但是，大量相近的词语也可能带来更多的切分歧义。另一方面，词表 不可能囊括汉语中所有的词汇，首先，汉语是不断发展和变化的，新的词汇不断 出现；其次，汉语中存在大量的专有名词和衍生词，这些词没有办法完全登录到 词表中。因此，词表应该包括使用频度较高的重要词汇，但是在不同的领域的文 本中，词汇出现的频度迥然不同。以上种种因素导致至今没有一个较完善的词语 收录标准，分词系统也仍然没有一个统一、的具有权威性的词表作为分词依据。 当前分词系统难以取得令人满意的效果，这也是原因之一。 f 二) 基于统计的切分 这种切分方法不需要词表，因此又称为无词典分词法。它完全基于对字串的 频率统计。从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时 出现的次数越多，就越有可能构成一个词。这种方法首先对字串进行全切分，然 后运用统计语言模型和决策算法决定最优的切分结果，它可以发现所有的切分歧 义，但是解决歧义的精度取决于所使用的统计模型和决策算法。 一种基于统计的切分算法叫做n g r a m 算法。它将一个字串进行一字，两字， 三字的切分，得到的子串称作n g r a m ，对于一个长度为l 的字串，可以切分出 共l + ( l - 1 ) 2 个n g r a m 。 对于中文，词语长度大部分不超过四个字，因此可以只考虑1 g r a m 、2 一g r a m 、 3 - g r a m 和1 4 一g r a m ，这就大大减少t n g r a m 的数量。对这些n - g r a m 的出现频度进行 统计，可得n g r a m 的频度表。为了减少切分歧义，需要进一步消除冗余的n g r a m 。 对一个n g r a m ，可以肯定它的所有子串都是n g r a m ，并且子串的频度大于等 于其频度。若一个子串的频度与其父串相等，则肯定此子串只可能作为父串的一 部分出现，根据汉语的构词特点，父串可以被判定为一个词。它所有的子串都是 冗余的。这就是以下规则： n g r a m 的削减规则： 若有两个n g r a m 项t f 和，满足tj 3t i 和p 一p 缈，n t j 是冗余的，只取。 这一规则进一步削减t n g r a m 的数量。对于余下的n g r a m ，可以依据n g r a m 的频度和一定的规则对字串选择切分策略。具体算法略。 基于统计的切分方法存在着一些局限性：首先，和基于词典的切分方法相比， 这种方法的精确度不高。容易产生一些并不存在的词，比如，例如“这一”、“之 一”、“有的”、“我的”、“许多的”等字组合，由于共现的频度大，被误认 为词；一些常用词反而不能被识别。其次，由于需要搜索的空间大，统计频度也 要消耗一定的时间，因此这种方法时间效率较差。 实际应用的统计分词系统都结合了词表切词，以发挥两者各自的长处。用词 典可以快速切分出常用词，对于词典中不存在的生词，可以采用频度统计的方法 来排除歧义切分。即将串匹配和串频统计结合起来，既发挥匹配分词切分速度快、 效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 海量科技的分词算法，“复方分词法”，就是采用多种算法来处理不同的问题。 2 2 常用分词词表结构 对于用词表切词的方法，词表的结构表示对于切词的性能影响很大。在对文 本的切分过程中，要反复访问词表结构匹配词语，因此词表访问部分很可能成为 系统瓶颈，也同时成为性能提升的关键。这一部分介绍常用的词表组织结构，分 析每种结构的优缺点。在后面的章节中，将讲解一种新的互关联后继树结构，详 细描述应用互关联后继树表示词表并进行文本分词的算法。 我们从词表最直观的结构开始讨论。词表可以组织为一个简单的线性表，其 中的每个元素是一个词。当我们需要匹配一个字串的时候，我们可以将它与词表 中的每个词顺序比较。如果匹配成功，则证明此字串是一个词，否则，我们将遍 历整个词表至表尾，得到词表中不存在这个词的结论。 很显然，这种做法的效率太低。假设词表的大小为l ，则成功的匹配一个词 平均需要i 2 个词的比较，失败的匹配必定需要l 个词的比较，因此每个词表内的 匹配操作需要0 ( l ) 的时间复杂度，在存在大量失败匹配的情形中，性能是无法接 受的。当然，整个词表可以按照词语的词典序排序，这