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

摘要 摘要 文本分类是文本挖掘的重要分支，在当今的信息时代文本自动分类已成为一 项具有较大实用价值的关键技术，是组织和管理数据的有力手段，已经被应用于 抽取符号知识、新闻分发、排序电子邮件、学习用户兴趣以及信息过滤等许多方 面。 首先，本文着重介绍了自动文本分类技术中常用的基于向量空间模型的特征 选取方法和分类模型。基于对这些技术的分析，本文提出了一种基于正负权重的 m 1 分类方法，该方法采用m i 特征选取方法以局部特征选取方式进行特征选取， 每一个类别得到不同的特征子集，并利用得到的特征互信息值构造特征的正、负 权重并形成类别的正、负原型向量。这种方法训练效率高，实验结果也表明该方 法也有比较好的分类性能。 另外，利用自动文本分类系统中已经实现了多种分类模型的特点，本文对多 分类器的组合问题进行了研究，并实现了利用贝叶斯理论进行组合的多分类器， 将之应用于自动文本分类。从实验结果来看，这种多分类器在一定程度上能提高 分类的准确率和召回率。 最后，阐述了o n t o l o g y 对文本分类的重要作用，介绍了o n t o l o g y 在文本分 类中的一些应用。面对当前针对某个特定领域的o n t o l o g y 缺乏，而且领域 o n t o l o g y 必须依赖领域专家指导靠手动建立的现状，本文对o n t o l o g y 的自动构 建技术进行了研究，并且实现了一个o n t o l o g y 自动构建系统o n t o a g s 。本文 对自动构建的完整过程进行了介绍。 关键字文本分类；特征选取；o m o l o g y a b s t r a c t t e x tc a t e g o r i z a t i o ni sa ni m p o r t a n tb r a n c ho ft e x tm i n i n ga n dh a s b e c o m ea k e y t e c h n o l o g yw i t hh i g hv a l u eo fr e a lp r a c t i c e t e x t c a t e g o r i z a t i o ni sa l le f f e c t i v em e a n si nd a t aa r r a n g e m e n ta n dm a n a g e m e n t ， a n dh a sb e e na p p l i e di nm a n yf i e l d s ，s u c ha se x t r a c t i n gs y m b o l i ck n o w l e d g e i n f o r m a t i o np r o c e s s i n ga n dm a n a g e m e n t ，i n f o r m a t i o nf i i t e r i n g ，a n ds oo n f i r s to fa 1 1 ，t h et h e s i si n t r o d u c e st h ep o p u l a rf e a t u r es e l e c t i o n m e t h o d sa n dc a t e g o r i z a t i o nm o d e l s ，w h i c hb a s e do nv s m ( v e c t o rs p a c em o d e l ) m o d e l 0 nt h eb a s i so ft h ea n a l y s i so ft h e s et e c h n o l o g i e s ，w ep u tf o r w a r d an e wt e x tc a t e g o r i z a t i o nm e t h o dw h i c hi sb a s e do nm i ( m u t u a li n f o r m a t i o n ) f e a t u r es e l e c t i o n t h ee x p e r i m e n t sp r o v e dt h a tt h i sm e t h o dw o r k sf a i r l y w e l l b e s i d e s ，am u l t i c l a s s i f i e ri si m p l e m e n t e db yc o m b i n i n gn a v eb a y e s c l a s s i f i e ra n ds i m p l ev s he l a s s i f i e r t h ec o m b i n a t i o ni sb a s e do nb a y e s t h e o r y a sw ek n o w s e m a n t i cw e bi st h en e x tg e n e r a t i o nw e ba n do n t o l o g yi s o n ei m p o r t a n tl a y e ri nt h es e m a n t i cw e ba r c h i t e c t u r e s e m a n t i cw e ba n d o n t o l o g yc a np r o v i d et e x tc a t e g o r i z a t i o nw i t hp o w e r f u ls e m a n t i cs u p p o r t f a c i n gt h es i t u a t i o nt h a tt h e r ei sl a c ko fd o m a i no n t o l o g ya n d c o n s t r u c t i n gd o m a i no n t o l o g ym a n u a l l yi sv e r yt i m e c o n s u m i n g ，w et r yt o c o n s t r u c tap l a t f o r mo fa u t o m a t i co n t o l o g yc o n s t r u c t i o n k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，f e a t u r es e l e c t i o n ， o n t o l o g y i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特另l j j j t i 以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名 日期：查翌：垒：吣 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 魏f 导燧名桦臁一 眇 学 1 1 研究背景 第1 章绪论 人类的二十一世纪已经被深深地打上了“信息”的烙印。在八十年代后期以 前，由于人类加工信息的速度缓慢、储存信息的能力低下、输送信息迟缓，信息 的可用性很低。近二十年来，加工信息的能力已经有了大幅度的提高( 例如，1 9 8 5 年全世界只有几十万台中央处理机和不多几台p c 机，而仅仅在1 9 9 5 年p c 机达 到了两亿多台) ；同时，大量信息的数字化已成为可能，信息存储能力已增加了 许多数量级；信息的传输能力也在飞速发展，在最近的几年中世界性的计算机网 络也在快速发展。 这些信息存在于海量的数据之中。有研究表明，人类社会已经被波涛汹涌的 海量数据包围，全球数据存储量已从1 9 9 9 年的1 8 4 6 4 1 t b 增加到了2 0 0 3 年的 2 0 0 0 0 0 0 t b ，而且还在以年均8 0 的速度持续增长。但是，尽管存在着这么巨大 的数据资源，也尽管存在着对这些数据的大量需求，却不知道如何处理，使大量 信息闲置在一旁无人问滓。正如美国前副总统戈尔所形容的，一方面大量的粮食 堆积在仓库里霉烂变质，另一方面有众多的人在挨饿。 如何有效利用这些海量数据成了当务之急。有人将此比作“数据淘金”，实 在是恰如其分的比喻。“千淘万漉虽辛苦，吹尽黄沙始到金”，想从浩瀚的数据淘 到自己想要的信息，如果没有强大的工具支持，简直比淘金更加困难。因此，数 据挖掘成了数据时代的“香饽饽”。 文本分类是数据挖掘中一个重要的研究领域。以目前的情况来看，虽然互联 网上的信息载体呈多样化趋势，但仍以文本为主，文字仍是互联网上信息的主要 来源。文本自动分类已成为一项具有较大实用价值的关键技术，是组织和管理数 据的有力手段，可被用于抽取符号知识“1 、新闻分发“1 、排序电子邮件。1 、学习 用户兴趣“3 以及信息过滤等等。 目前研究者们已提出了许多统计方法和机器学习方法，在试验中也有很好的 北京工业大学工学硕士学位论文 表现。但是，在这个领域还是有很大的空间值得我们继续去研究和探索。 同时，北京市多媒体与智能软件技术重点实验室在这个领域有很好的研究能力和相关的 技术积累，为继续进一步的研究提供了强大的知识保障和良好的试验平台。 1 2 文本分类研究现状 文本分类是文本挖掘的核心。分类的概念是在已有数据的基础上学出一个分 类函数或构造一个分类模型，即所谓的分类器( c l a s s i f i e r ) 。它按照预先定义的 分类体系( 即分类模型) ，为文档集合中的每个文档确定一个类别( 即将文档集合 中的每个文档归纳入某个类别) ，使得用户不但能够方便地浏览文档，而且可以 通过限制搜索范围来使文档的查找更为容易。文本分类技术可以对大量文档进行 快速、有效地自动分类。文本自动分类就是用大量的带有类标志的文本，对分类 准则或模型参数进行训练，然后用训练得到的结果对未知类别的文本进行识别。 一般来说，一个完整的文本分类过程通常包括以下几个处理步骤： 一、文本信息的预处理 因为文本分类处理的是大量非结构化的用自然语言描述的无统一结构的文 本数据，在对文档进行特征提取前，需要先对这些文本数据进行相应的预处理( 这 是文本分类的首要步骤) ，它将直接影响文本分类的效率和准确度以及最终模式 的有效性。 预处理是指抽取代表文本特征的元数据( 特征项) ，对元数据进行标记、语形 学分析、词性标注、短语边界辨认等。主要包括英文文档( 用空格作为分隔符) 的 s t e m m i n g 处理( 从英文单词的多种形式中提取出其基本词干的过程) 和中文文 档的分词处理。因中文文档的句子中各词条间无固定的分隔符( 空格) ，进行中文 文档的词频统计前，需先对中文文档进行分词处理，即在词条间加入分隔符，使之 转换为分散的词流形式。中文单词切分方法主要有两大类方法：基于词典与规则 的方法和基于统计的方法。基于词典与规则的方法应用词典匹配、汉语词法或其 它汉语语言知识进行分词，如最大匹配法( m a x i m u mm a t c h i n g ) 、最小分词方法 等。这类方法简单、分词效率较高，但对词典的完备性、规则的一致性等要求比 较高。基于统计的分词方法则将汉语基于字和词的统计信息，如相邻字间互信息、 词频等应用于分词，由于这些信息是通过训练集动态获得，因而具有较好的鲁棒 第1 章绪论 性能，但完备性相对较差。分词的基本方法可归纳为如下，l 种：词典匹配法。 匹配策略有：最大匹配法、最小匹配法、逆向匹配法、增字或减字匹配法、双向 扫描法、二次扫描法、逐词遍历法、部件词典法、最佳匹配法。标志法。如切 分标志法、统计标引法、多层次列举法。词频统计法。如高频优先法、基于期 望法、最少分词词频法。联想词群法。如联想回溯a b 法、词链法、多遍扫描 联想法、联想树分析法、无词库法。语义语用法。如邻接约束法、扩充转移网 络法、综合匹配法、后缀分词法。目前使用最多的是基于词库的分词方法。由于 中文具有歧义性，如“搜索引擎”可切分成“搜索引擎”和“搜索引擎”， 因此必须结合其它分词方法，如基于语法和规则的分词法。1 、基于神经网络的分 词法”、基于专家系统分词法、基于朴素贝叶斯的分词法”1 、t f i d f 模型法、 k 2 近邻方法0 1 、综合分词法等。 二、文本的特征表示 文档特征是指关于文本的元数据，分为描述性特征( 如文本的名称、日期、 大小、类型等) 和语义性特征( 如文件的作者、机构、标题、内容等) 。描述性 特征较易获取，语义性特征获取较难。w 3 c ( 互联网联合组织) 制定的x m l ( e x t e n d a b l e m a r k u pl a n g u a g e ) ，r d f ( r e s o u r c ed e s c r i p t i o nf r a m e 2 w o r k ) 等规范提供了对w e b 文档资源进行描述的语言和框架。文档特征表示是文本挖 掘工作的基础，它是对从文本中抽取出的元数据( 特征项) 进行量化，以一定的特 征项表示目标信息。这些特征项作为文档的中间表示形式，在文档挖掘时用这些 特征项评价未知文档与用户目标的相关度，从而实现对非结构化文本的处理，这 是一个非结构化向结构化转换的处理步骤。目标表示的构造过程就是挖掘模型的 构造过程。特征表示模型有多种，常用的模型有向量空间模型( v e c t o rs p a c e m o d e l ，v s m ) 。v s m 把文档看作是由一组正交词条矢量所组成的矢量空间，每个文 档表示为其中的一个范化特征矢量) 、布尔逻辑模型( 是v s m 模型的一种简化， 是一种严格匹配向量模型，其实现简单，用于快速检索) 、概率模型、混合模型。 近年来，应用较多且效果较好的是v s m 。 三、特征选取 由于一个训练文档集中的候选特征项通常很多，可高达几十万个，即文本特 征往往是高维的，且文档的许多信息往往又是高冗余的，所以必须进行文本特征 的缩减( 选取) ，这往往决定了文本挖掘的效率。 北京工业大学i 学坝士学位论文 特征选取主要有两大类方法：独立评估方法和综合评估方法。独立评估方法 刺元数据的权值评价采用多种标准：文本权重、信息收益、期望交叉信息熵、文 本证据权、互信息、几率( o d d sr a d i o ) 、词频( w o r df r e q u e n c y ) 等。这些评价 标准来自：神经元网络法、决策树法、遗传算法、集合论法、统计法等。综合评 估方法将原始特征和主成分之间的映射关系解释为每个主成分是原始特征的线 性组合。 特征项选取的原则：特征项应具备完全性、区分性和独立性：词、词组、 短语适合作特征项：虚词不适合作特征项：稀有词不适合作特征项：词 频平均的词条不适合作特征项。一个有效的特征项集，须具备两个特征：完全性 ( 能够确实表示目标内容) 、区分性( 能够将目标同其它文档区分) 。 四、建立分类模型 这是分类系统的核心部分，由分类方法来完成。一般将分类方法划分为训练 和分类两个子过程。训练是通过对训练例进行学习建立分类器；然后使用该分类 器可以对未知文本进行分类。目前主要的分类方法有： 1 ) 向量空间模型( v e c t o rs p a c em o d e l ) “是g s a l t o n 等人在2 0 世纪 6 0 年代提出的一个理论，其基本思想是用向量来表示一个文本，之后的 分类过程就可以简化为空间向量的运算。v s m 只是提出了一个理论的框 架，对于特征的权重评价函数以及相似度计算方法并没有做出统一的规 定，所以可以采用不同的方法来适应不同的情况。几乎所有的分类方法 都和v s m 的思想有关，即首先将文档表示为一个n 维向量，进行特征评 价及抽取之后再进行后续的分类与训练。 2 ) k 近邻( k - n e a r e s tn e i g h b o r ) “”方法是一种基于类比的分类方法。它 生成所有的训练例的特征向量后，将其保存下来，给定一个未知文本之 后，k 近邻方法搜索所有的训练例，通过比较从中找出k 个最接近训练 例，然后将未知文本分到这k 个近邻中最普遍的类中去。 3 ) 朴素贝叶斯( b a y e s i a np r o b a b i l i s t i cm o d e l s ) 分类“”是一种统计学分 类方法，可以用来预测类成员关系的可能性，给出给定文本属于某特定 类的概率。目前的实验表明，即使在大型的数据集上，朴索贝叶斯分类 也表现出了很好的分类准确度与速度。从理论上讲，贝叶斯分类的出错 率最小，不过试验表明在训练例偏少的情况下，朴素贝叶斯的分类效果 4 第l 章绪论 并不理想。 4 ) r o c c h i o 分类算法“”是一种基于v s m 的分类算法，主要思想是在经过特 征选取之后将样本表示为特征的n 维( 经过特征选取保留了n 个特征属 性) 向量，根据训练算法，在训练后每个类将得到一个原型，这个原型 也是一个特征的n 维向量。对于新样本( 待分样本) ，首先将之转化为 特征空间上的n 维向量，然后通过某种相似性度量方法计算该新样本与 各类原型的相似度，将该样本归入与之最相似的类中。 5 ) s l e e p i n ge x p e r t s 分类“”的基本思想是：将文本中每一个关键词( 或者 词的序列) 视为一个“分类专家”( 最简单的分类器) 。它对于判定该文 本是否属于第n 类有两种贡献：属于第n 类和不属于第n 类( 分别用关 键词的正权重和负权重来表示) 。当训练样本为本类样本时，提升该样 本中关键词的正权重，降低负权重。当训练样本为非本类样本时，提升 该关键词中的负权重，降低正权重。这样经过大量的训练，获得每个词 的正负权重，最终形成分类专家库。文献 6 】的实验表明，当使用词的序 列( 该文献中采用4 个连续词) 作为最小的“分类专家”能取得很好的 分类效果。 6 ) 支持向量机( s u p p o r tv e c t o rm e c h a n i c s ) “”是种解决两类分类问 题的方法，即它只能判别未知样本属于某一特定类或不属于该类。它的 基本思想是将所有的训练文本( 包括正例与负例两部分) 表示为向量， 然后在向量空问中寻找一个决策面，能够“最好的”隔离正例与负例。 s v m 是近几年才被引入文本分类领域的。有实验结果表明，s v m 在小训 练集上的分类准确率最佳。 7 ) 神经网络( n e u r a ln e t w o r k s ) “”的学习结果为目标函数，根据这个目标 函数的输出来进行分类的依据。输入即为文本特征向量的各分量值。神 经网络实际上是一组连接的输入输出单元，其中每一个连接都具有一 定的权值。通过训练集来训练，即调整这些权值，使得神经网络可以正 确的预测类别。神经网络的训练是针对训练例逐个进行的，所以神经网 络的训练集可以随时添加来进行修正，但这也使得训练时间过长。同时 有实验结果表明，在训练例过少的情况下，神经网络的分类准确率较低。 神经网络也可以抵御噪音，而且可以很好的抵御文本的无关属性( 即非 北京工业大学工学硕士学位论文 决策属性) 的干扰。 8 ) 决策树( d e c i s i o nt r e e s ) “”的算法有c 4 5 ( 发展于i d 3 ) ，c a r t ，c h a i d 等，他们区别在于构造决策树与树枝剪除的算法细节不同。决策树可以 很好地抵抗噪声。最大的缺点在于不适应大规模的数据集，决策树的构 造可能变得效率低下。 9 ) 其它基于网页的结构信息( 比如超链接) 的算法“。 l o ) 基于本体( o n t o l o g y ) 的文本分类“”“。 五、分类模型的评价 对一个分类模型的评价主要从分类器的分类准确度和分类效率两个方面进 行度量。对于分类准确度的评价有一套比较好的评价标准，一般采用准确率 ( p r e c i s i o n ) 和查全率( r e c a l l ) 进行衡量。 1 3 本文的主要工作概述 本文对常用的自动文本分类算法和特征选取方法进行了研究，并实现了一个 文本分类系统，现将主要工作概括如下： 1 ) 对几种常用的自动文本分类算法( n a i v eb a y e s 、k n n kn e a r e s t n e i g h b o r 、s i m p l ev s m 、r o c c h i o ) 进行了比较系统的研究和实验，并在 此基础上利用贝叶斯理论构造了一个多分类器； 2 ) 通过对m i ( 互信息) 特征选取方法进行了研究，提出了一种基于正负权 重的m 1 分类算法； 3 ) 在对语义w e b 、o n t o l o g y 与文本分类的结合的现状进行了解的基础上， 对自动创建领域o n t o l o g y 进行了研究，并实现了一个自动构建o n t o l o g y 的系统。 1 4 本文的组织与内容概要 本文包括以下几个部分： i ) 绪论。介绍了本文的研究背景和相关研究现状： 2 ) 自动文本分类技术概述。着重介绍了本文涉及到的已有的几种特征选取 6 第l 章绪论 方法和分类方法。这些算法是文本分类的技术核心，通过对这些算法的 研究有助于深入地理解文本分类技术的理论基础和实现细节。同时这些 常用的技术也是本文进一步研究的基础和参照对象； 3 ) 基于正负权重的m 1 分类算法。介绍一种利用互信息构造特征的正负权 重、用正负两个向量作为类别原型的分类方法； 4 ) 多分类器组合的研究与实现。介绍一种多分类器组合的方法，以及在文 本分类中应用；并介绍了多分类器组合在自动分类器系统中的实现和实 验结果； 5 ) o n t o l o g y 与文本分类及o n t o l o g y 的自动构建。介绍了o n t o l o g y 的相关 知识以及在文本分类中的应用，以及本文实现的一个o n t o l o g y 自动构建 系统0 n t o a g s 。 6 ) 结论与展望。对本文的工作进行了总结，并对本文工作中存在的一些不 足提出了可能的改进思路和基于本文的工作将来可以继续开展的一些工 作。 北京工业大学工学项士学位论文 第2 章自动文本分类技术概述 2 1 自动文本分类的定义 自动文本分类问题一般可以定义为，对于给定的文本集合d o c 和类别集合 c a t ，设法找到以下未知分类函数： o ：d o c c a t - - b o o l e a n ( d o c , c a t ) o ( d o c , c a t ) = 篙尝蓍柏猢悯c a t 的近似表示： 口：d o c c a t 呻b o o l e a n ( d o c ，c a t ) b o ( d o c ，e a t ) ， 公式( 2 1 ) 公式( 2 2 ) 使得妒尽可能与巾相同。其中，函数o 描述了文本d o c 与类别c a t 之间的 真实关系。函数妒称为文本分类器。实际上，文本分类器p 由系列两类分类器 组成： 妒c a 【：d o c b o o l e a n d o eh 舻。a t ( d o c ) 公式( 2 3 ) 分类器p 。的任务是判定给定的文本是否属于类别c a t 。所以文本分类涉及 到多少个文本类别，就对应到多少个两类分类器。 为叙述方便，人们常常用整数1 代替逻辑值t r u e ，整数0 或者一1 代替逻辑 值f a l s e 。 另外，也有不少学者把文本分类函数： ：d o c x c a _ 删 公式( 2 4 ) ( d o c ，c a t ) p 哼v ( d d c ，c a t ) ， 。 作为文本分类器的定义。其中( 如c ，c a t ) 为文本d o c 属于类别c a t 的置信程 度。 对于任意给定的阈值0 ，通过规定所有置信度高于该闽值的文本属于某一类 别，所有置信度低于该阈值的文本不属于这一类别。这样，可以方便地将公式 第2 章自动文本分类技术概论 ( 2 4 ) 转化为公式( 2 2 ) 形式。 根据实际应用的需要，可以对分类任务附加不同的约束条件。例如，对于给 定的一个整数k ，对于文本集合d o c 中的每一个文本d ，我们需要从类别集合c a t 中选择k ( 或少于，或多于k ) 个类别赋予d 。如果一个文本样本只能属于一个 类别，我们称这样的分类情况为单类别分类( s i n g l e l a b e l ) ；反之，如果对于 文本集合d o c 中的每一个文本，我们可以赋予它0 到jc a t 个类别标签，那么我 们称之为多类别分类( m u l t i l a b e l ) ”。 单类别分类的一个特殊例子就是上面提到的两类分类。在两类分类中，一个 文本d 要么属于类别c ，要么属于c ，的补集( 不属于c 。) 。 从理论的角度说，两类分类( 因此单类别分类也是) 比多类别分类更具一般 性。因为，一个两类分类算法也能用于多类别分类：只需要将对于类别集合c a t 的一个多分类问题转化为i c a t 【个两类分类问题。但是，在这种转化过程中我们 人为地添加了一个假设：不同的类别之间相互独立。 可以将自动文本分类划分为两个阶段”“： 一、建立分类模型( 即分类器) ，描述预定的文本集合。通过分析具有类别 标号的样本来构造分类模型，这个过程就是学习的过程。我们称为建立分类模型 而被分析的文本集合为训练集。训练集中的单个文本称作训练样本。由于提供了 每个训练样本的类型标号，这一步也称作有指导的学习( 即模型的学习在被被告 知每个洲练样本属于哪个类的“指导”下进行) 。另外还有一种称之为无指导的 学习( 或聚类) ，在学习过程中训练样本的类别标号是未知的，要学习的集合或 数量也可能是未知的。 分类模型是文本分类的核心技术。大体上文本分类模型可以分为两种，即基 于规则的文本分类模型和基于统计的文本分类模型“”“。 在基于规则的分类技术中，首先需要根据某种假设建立起可用于分类的规 则，该规则包括了文本的表示方法，类别的表示方法，文本与类别的映射方式等 等。之后通过训练过程来完成规则的完善和调整。训练后则可以使用该规则来决 定文本的类别，完成分类。决策树( d e c i s i o nt r e e ) 、神经网络( n e u r a ln e t w o r k ) 、 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 等是属于基于规则的分类模型。基于规 则的分类模型理论基础强，合理性高，而且分类的规则易于为人们所理解，也易 于改写成其他形式。但基于规则的分类模型实用性很差，这是因为现实中的数据 9 北京工业大学工学硕士学位论文 集颇为庞大，在此种情况下，训练时规则的建立调整过程效率会很低。应用规则 完成分类的效率也较差。 在基于统计的分类方法中，或者依据某种统计后得到的客观规律，或者采用 某种统计学中的定律，来完成分类器的建立工作。该种方法中的训练过程多为训 练集上的某种统计和计算过程，得到某些可以代表文本与类别之间关系的数据。 朴素贝叶斯( n a i v eb a y e s ) 模型，向量空间模型( v e c t o rs p a c em o d e l ) ，k 近 邻方法( k - n e a r e s tn e i g h b o r ) ，r o c c h i o 等方法属于这种基于统计的分类模型。 二、使用学习得到的分类模型进行分类。首先评估得到的分类模型的性能 ( 在实验结果部分将做介绍) 。如果对分类模型的性能满意，就可以用它来对类 别标号未知的文本进行分类。 其中第一阶段可以细分为预处理、特征表示、特征选取和训练模型几个过程； 第二阶段包括评估模型和用模型分类。 2 2 文本预处理 文本预处理主要是进行结构处理( 比如网页) 和分词处理等。分词处理在处 理中文等没有明显的词语分隔符的文本时非常重要。而在英文文本中词与词之间 由空格等特殊字符隔开，具有非常明显的特征，处理起来比较简单。但在英文文 本预处理中一般要进行词干( s t e m m i n g ) 分析，将各种词的变形形式恢复成原型。 2 3 文本的特征表示 我们采用向量空间模型进行特征表示。在这个模型中，文本空间被看作是由 一组正交词条向量所组成的向量空间，每个文本d 被表示为其中一个范化特征向 量矿( d ) = ( ，。，0 3 l ( d ) ；，甜；( d ) ；f ，( d ) ) ，其中为词条项，q ( d ) 为r ，在d 中 的权值可以将d 中出现的所有单词作为，也可以要求是d 中出现的所有短 语，从而提高内容特征表示的准确性。吼( d ) 一般被定义为，在d 中出现频率 斫( d ) 的函数，即q ( d ) ：( 矿( d ) ) 。常用的y 函数有：布尔函数= ：墨曷三1 0 ； 平方根函数妒= 厕：对数函数= l o g ( t f ( d ) + 1 ) ；t f i d f 函数 1 0 第2 章自动文本分类技术概论 ；f ，：矿( d ) l o g ( 学) ，其中，n 为所有文本的数目，一为含有词条t 的文本数目。 胛 我们在试验中采用t f i d f 函数。 2 4 特征选取 自动文本分类阅题，本质上是一个统计模式识别问题。在运用统计模式识别 方法进行文本分类之前，需要将文本表示成特征向量。一般来说，不管采用什么 样的文本表示模型，一个文本分类问题所对应的文本特征空间通常都达到几万 维，甚至更高。如果直接在这样一个高维特征空间上进行分类器的训练和分类， 很可能会有两个问题：一是很多低维空间具有良好性能的统计分类器在计算上变 得不可行；二是训练样本( 训练文本集的个数) 一定的前提下，过多的特征使得 样本统计的估计变得非常困难，从而降低统计分类器的推广能力和泛化能力，呈 现所谓的“过学习”或“过训练”的现象。 为了避免上述“过学习”问题( 也称为“维数灾难”( c u r s eo fd i m e n s i o n a l i t y ) “7 ) 和提高分类器的训练和分类的效率以及推广能力。一般在分类器的训练之前， 对特征空间进行压缩，降低特征维数，使之与训练样本个数相适应的地步。因此， 如何降低原始特征维数，即如何进行维数削减( d i m e n s i o nr e d u c t i o n ) ，一直成 为统计模式识别的一个重要研究课题，受到众多研究者的密切关注。 根据维数削减是在局部( 每一个单独的类别) 还是在全局范围进行，可以将 维数削减分为局部( 1 0 c a l ) 维数削减和全局( g l o b a l ) 维数削减“”“。 维数削减的实现一般有两个基本途径：特征选取( f e a t u r es e l e c t i o n ) 和 特征抽取( f e a t u r ea b s t r a c t i o n ) 。特征选取是依据某个准则从原始特征空间中 选择部分最能反映模式类别统计特征的相关特征。特征抽取是指依据某原则构 造原始特征空间到新的低维特征空间的一个变换，从而将分散在众多原始特征空 间中的分类信息或鉴别信息集中到少量的新的特征上来。经过维数削减后的特征 空间称为削减特征集。其中，经过特征选取得到的削减特征集是原始特征集合的 一个子集；而经过特征抽取得到的削减特征集不是原始特征全集的子集。通常的 情况是，经过特征抽取得到的特征集中特征和原始特征全集中的特征甚至不属于 同一种类型；例如，原始特征空间中的特征是是单词，但经过特征抽取后的特征 北京工业大学工学硕士学位论文 可能根本不是单词。 在本文中，除非特别说明一般采用特征选取方法进行全局维数削减。常用的 特征选取方法有：信息赢取( i g ) 、互信息( m i ) 、c h i 、文档频率d f 等。 2 4 1i g 特征选取 i g ( i n f o r m a t i o ng a i n ) ，即信息赢取。它通过统计特征在各个类别中的出 现次数来计算，公式如下： g ( f ) = 一二j p ( c ，) l o g p , ( c ，) + 只( f ) ：。只( qi t ) l o g p a c 。i f ) + p ( ；) ：l p ( c ，i t ) l o g p , ( c ，1 i ) 公式( 2 5 ) 其中t 代表特征，c i 代表第i 个类别，m 为类别数，p r 代表概率，g ( t ) 代 表特征t 的信息赢取值。公式第一部分p ( q ) l o g p ，( c ) 是在没有任何实验情况 i = 1 下文本分类的熵( e n t r o p y ) ，表示文本的混乱( 不确定性) 程度；第二部分 只( f ) 尸，( q | t ) l o g p , ( c ，l f ) 是特征t 在文本中出现的情况下文本分类的熵：第三 i = l 部分p ( j ) ：，只( q1 ；) l o g p ，( c ，i ；) 是特征t 没有在文本中出现的情况下文本分类 的熵。所以信息赢取g ( t ) 反映了特征t 对分类混乱程度的降低，也就是对分类 的信息量。在实现中通过根据各个特征的信息赢取值排序，并根据设置的闽值选 择出合适规模的特征子集。 2 4 2m i 特征选取 m i ( m u t f i a li n f o r m a t i o n ) ，互信恳值，它通过计算特，仕t 和类别c1 日j 阴利 关性来完成提取。计算公式为： 坤，c ) = l 。g 而p a t c ) 公式( 2 6 ) 为方便计算，简化为： 坤，c ) l o g 面而a x n 公式( 2 7 ) 其中n 为训l 练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出 1 2 现而c 不出现的次数，c 为c 出现而t 不出现的次数。通过该公式就可以取得特 征与各类别间的互信息值。为了能取得特征在数据集上的整体评价，有以下两种 计算方法： k ( f ) = 只( q ) 坪，c i ) f _ l 。( f ) = m 公式( 2 9 ) 前者代表了特征和各类别的平均互信息值，后者则取特征与各类别互信息值 中的最大值。m i 方法提取互信息值较高的特征，其基本思想为与类别相关性越 高的特征越重要。 2 4 3c h i 特征选取 c h i 具有和m i 方法基本相似的愚想，同样通过计算特征t 和类别o 间的依 赖程度来完成提取。但二者的计算细节不同，c h i 作了更多地考虑，有种看法认 为c h i 是一种“正规化”了的m i 。c h i 的计算公式如下： c m o ，c ) = 两瓦面n x 丽( a d 石- c 面b ) 2 币丽公式( 2 1 。) 7 ( 4 + c ) ( b + d ) ( 爿+ b ) x ( c + d ) 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出 现而c 未出现的次数，c 为c 出现而t 未出现的次数，d 为二者都未出现的次数。 与m i 相同，c h i 也有平均值和最大值两种方法来取得特征的整体评价： e 。( r ) = p ( c ) c 册( ) 公式( 2 1 1 ) 删k ( r ) 2 喈 c 肼( f ，c f ) ) 公式( 2 1 2 ) c h i 方法的基本思想也是与类别关系越紧密的特征重要性越高。 2 4 4d f 特征选取 d f ( d o c u m e n tf r e q u e n c y ) ，即文档频率，指训练集中包含该特征的文本总 数。所谓文本包含特征是指这个特征在该文本中出现，忽略其在文本中的出现次 数。d f 方法提取d f 值较高的特征，它的目的是去掉在训练集上出现次数过少的 北京工业大学工学硕士学位论文 特征，保留出现达到一定次数、具有一定影响力的特征。 在各个特征选取方法中，d f 方法的计算是最简单的，同时也是最有效的文 本特征选取方法之一。然而，由于缺乏必要的理论基础，文档频率直被认为是 一种用来改善文本分类器效率的权宜之计，而不能算是严格意义熵的文本特征选 取方法。 2 4 5 特征选取方法之间的比较 文献。”中对文本分类中主要的特征选取算法做了比较系统的介绍、试验比较 和评价。根据该文献的对比实验得出的结论，这几种方法中i g 和c h i 效果最好， 在不损失分类准确率的情况下可以达到很高的压缩率( 只保留2 的特征) 。如 果保留1 0 左右的特征，d f 方法的效果可以和i o 、c h i 相比。在计算量太大的 情况下，可以用d f 方法代替i g 、c h i ，在准确率和效率之间达到一个很好的平 衡。 2 4 6 本文采用的特征选取方法 本文所有实验除非特别说明，一般采用单词作为特征，信息赢取作为特征选 取方法。将信息赢取特征选取算法描述如下： 步骤l 设置闽值。( 本文设置为2 ，表示提取特征全集的2 作为特征子 集) 步骤2 处理训练集中的每一个文本样本，得到所有在训练集中出现的单词， 形成特征全集；同时，针对每一个特征统计各个类别中包含该特征的样本数； 步骤3 计算文本集d o c 的熵： e n t r o p y ( d o e ) = 三只( q ) l o g p , ( c ) 公式( 2 1 3 ) 。 鼽驯= 器糕。 步骤4 对于每一个特征： 1 ) 计算两个条件熵： e n t r o p y ( d o c t ) = p a t ) z o ：1 只( c ，it ) l o g p , ( c 。l ，) 和 1 4 e n t r o p y ( d o c l7 ) 2 只( ；) ：，只( qi ) l o g p ，( qm 鼽舶，= 等鬻鬻； pr t 、= 型箜塞主至鱼鱼! 塑堂查塑旦 “7 训练集中样本总数目 pr c ：鲞型! ! 塑型箜塞垡鱼! 塑堂查塑旦 1 “、”7 训练集中包含t 的样本数目 。，r 、类别c ，的训练集中不包含t 的样本数目 1 “、” 训练集中不包含t 的样本数目 。 2 ) 计算特征t 的信息赢取； 步骤5 对特征全集中的所有特征根据其信息赢取值排序，根据设置的阈值 得到特秆子集 2 5 分类模型 在完成特征选取之后，我们就可以使用这些特征来表示一个文本。具体的表 示方法因分类方法而异，每种分类模型都会采用自己的方法来表示一个文本，并 将这种表示方法纳入到自己的体系中去。所有的分类模型大体上都可分为训练和 分类两个步骤。下面分别介绍本文实现的自动文本分类系统中使用的几种常用分 类模型：r o c c h i o 、朴素贝叶斯、k n n 、简单v s m 。 2 5 1r o c c h i o r o c c h i o 算法最早是由r o c c h i o 。4 3 在信息检索中用于计算“询问”( q u e r y ) 与文档之间关联程度提出来的，后来h u l l 。“63 把r o c c h i o 公式改造并引入到文 本分类之中。r o c c h i o 分类器是一种基于向量空间模型和最小距离的方法，非常 简单和直观，作为基准分类器以及组合分类器的成员分类器，它在文本分类领域 得到了广泛的应用。本文根据。”实现了r o c c h i 0 分类模型。 首先，将文本( 包括训练集和测试集) 表示成数字权重的向量。对于文本样 本d m ，我们将其对应的权重向量表示为v ”= ( v ? ，v ? ，) v ：，_ v ? ) ，其中，k ，是 使用的特征的索引号。这里，根据t f i d f 1 计算k 的权重： 1 5 北京工业大学丁二学硕十学位论文 。? ：毒塑型也止 公式( 2 1 4 ) 8 ：，芹l o g ( n 。n ， 其中，n ，是文本总数( 在本文实现中是训练集的文本总数) ，n 。是包含索 引号为k 的特征( 以下简称特征k ) 的文本的数目，f 定义如下： 疗= 1 0 l 。, g l ( = f ) 0 + 1 ，其它，其中，是特征k 在文本d m 中出现的数目a 然后，根据r o c c h i o 算法，为类别集中每一类c 构造一个原型，这个原型是 同原始权重向量v ( m _ l ，2 ，n 。) 相同向量空间上的一个权重向量v t 。对 于类别c ，其原型向量中特征k 的权重定义如下： oa e ， v t = m a x 公式( 2 1 5 ) 其中，r ，是训练集中属于类别c 的所有文本集合，r c 是训练集中所有不属 于类别c 的文本集合。系数口、，调节正例( 属于类别c 的文本) 和负例( 不属 于类别c 的文本) 对该类的原型向量的相对贡献。本文采用标准值卢= 1 6 ，y = 4 。 在建立了各个类别的原型向量后，就完成了分类器的训l 练，可以对类别标号 未知的文本进行分类。具体步骤如下： 首先，将待分类文本转换为特征空间上的权重向量； 其次，计算该向量与各个类别原型向量的相似度。相似度的度量一般采用向 量夹角或欧几里德距离。本文采用向量夹角c o s i n e 值来度量，公式如下： 一y ， “五力。丽i=lj f 。擂h 2 公式( 2 1 6 ) 该值越小表示两向量x ，y 之间相似度越高。 最后，取其原型向量与该文本向量相似度最高的类别作为该文本的类别。在 实际应用中可以设置一个闽值来判断是否拒识该文本，从而调节分类器的召回率 和准确率之间的平衡。 1 6 d 趣 上刚 一 町 呲卫 o 第2 章自动文奉分类技术概论 2 5 2 朴素贝叶斯模型 贝叶斯分类“”。2 1 是一种统计学分类方法，它基于贝叶斯定理，可以用来预测 类成员关系的可能性，给出文本属于某特定类别的概率。分类时根据预测结果将 该样本分到概率最高的类别中即可。假定有m 个类c ，c 。，c m ，给定未知文 本x ，贝叶斯分类将给出条件x 下具有最高后验概率的类别