（计算机应用技术专业论文）支持向量机及用于文本分类的研究.pdf

武汉理工大学硕士学位论文 中文摘要 近年来，随着网络的迅猛发展，如何对网络上大量的自然语言文本按照既 定的语义进行正确的归类，已经成为组织大量网络信息的一个关键问题。这就 是文本分类的任务。电子文本成几何级数增长，日常生活中海量信息的传播， 迫切的要求我们能对这些文章进行自动分类。使用文本自动分类系统可以帮助 人们自动检查文本，判断文本的类别。 本文采用最大间隔一支持向量机的关键技术。实现了文本的自动分类。学 习算法是通过对己给定类标记的训练文本的学习，自动产生分类规则，该规则 在今后预测未知的文本的类别时，有较高的精确性。本文主要工作及创新点在 于： 1 基于文本分类的技术的掌握，包括文本的表示方法，特征的选取以及文档 分类的评估指标等。我们讨论并实现了文本表示的全过程，包括提取词干， 去除高频率和低频率特征词，得到数据字典，然后经过权重计算，生成文 本向量空间，即训练样本和测试样本数据。并采用s v m 算法，设计出文本 分类实验系统。通过在r u t e r s 2 1 5 7 8 文档集上的实验，该系统证明了s v m 能切实有效的解决文本的自动分类问题。 2 在研究s v m 算法的过程中，我们发现算法本身易过学习，并且训练时问很 长。为了解决这些缺陷，我们提出了基于减法聚类的s v m 算法。减法聚类 是根据密度指标，选取聚类中心点，聚类中心点也为训练数据点本身。这 样就达到减少训练数据个数的目的。我们用选取的聚类点作为新的训练集 合，构建s v m 。在两类和多类的标准数据集上的实验表示，该算法较之传 统s v m 有好的分类准确性和泛化能力，但是用于优化计算的时阃却大大减 少。 关键词：文本分类，特征选择，支持向量机，减法聚类 i l 武汉理t 大学硕士学位论文 a b s t r a c t w i t ht h er a p i dg r o w t ho ft h ew o r dw i d ew 曲t h et a s ko fc l a s s i f y i n gn a t u r a l l a n g u a g ed o c u m e n ti n t oap r e d e f i n e ds e to fs e m a n t i cc a t e g o r i e sh a sb e c o m eo n eo f t h ek e ym e t h o d sf o ro r g a n i z i n go n l i n ei n f o r m a t i o n t h i st a s ki sc o m m o n l yr e f e r r e d t oa st e x tc l a s s i f i c a t i o n t h ee x p o n e n t i a lg r o w t ho ft h en u m b e ro fo n l i n ed o c u m e n t s a n dt h ei n c r e a s ep a c ew i t hw h i c hi n f o r m a t i o nn e e d st ob ed i s t r i b u t e dh a sc r e a t e dt h e n e e df o ra u t o m a t i cd o c u m e n tc l a s s i f i c a t i o n t h ea p p r o a c hp r e s e n t e di n t h i st h e s i si sb a s e do nt h ek e ys i g h tt h a tm a r g i n t h e c o m p l e x i t ym e a s u r eu s e di ns u p p o r tv e c t o rm a c h i n e ( s v m ) ，i si d e a lf o rt e x t c l a s s i f i c a t i o n t h el e a r n i n g a l g o r i t h mi sg i v e n a c c e s st ot h el a b e l e dt r a i n i n g d o c u m e n t sa n dp r o d u c e sac l a s s i f i c a t i o nr u l ea u t o m a t i c a l l y n em a i nw o r ki sa s f o l l o w s ： 1 b a s e do nt h ei n t r o d u c t i o n o fr e p r e s e n t a t i o n so ft e x t ，f e a t u r e s e l e c t i o n ，a n d c r i t e r i af o re v a l u a t i n gp r e d i c t i v ep e r f o r m a n c e ，w ei m p l e m e n tt h ep r o c e s s i n g s t e p sl i k es t e m m i n g ，h i 曲a n dl o wf r e q u e n c yw o r d sr e m o v a l ，a n dw e i g h r i n g s c h e m e st og e n e r a t eo u rf e a t u r ed i c t i o n a r ya n dt r a n s f o r mt r a i n i n ga n dt e s t i n g d o c u m e n t si n t on u m e r i c a lv e c t o r s t h c nt h et e x tc l a s s i f i c a t i o ne x p e r i m e n t a l s y s t e mb a s e do ns v m i sd e s i g n e d t e s t e do f fr u t e r s 一2 1 5 7 8c o r p u s t h es y s t e m d e m o n s t r a t e st h a ts v mc a ne m c i e n t l y , e f f e c t i v e l ya n dp r o v a b l ys o l v et h e c h a l l e n g eo fl e a r n i n gt e x tc l a s s i f i e r sf r o me x a m 【p l e sf o ral a r g ea n dw e l l d e f i n e d c l a s so fp r o b l e m s 2 i no r d e rt os o l v eo v e r f i t t i n ga n dt i m ec o n s u m i n gf o rt r a i n i n gi ns v m ，s v m c o m b i n i n gs u b t r a c t i v ec l u s t e r i n gm e t h o di sp r o p o s e di nt h i st h e s i s s u b t r a c t i v e c l u s t e r i n gm e t h o di su s e dt os e l e c tas e to fc l u s t e rc e n t e r sw h i c ha r et h ed a t a s a m i p l e st h e m s e l v e sa st h er e p r e s e n t a t i o no fo r i 酉h a lm a s s i v e s e to ft r a i n i n gd a t a t h en e wt r a i n i n gs e tt h e ni su s e dt oc o n s t r u c ts u i p p o f tv e c t o rm a c h i n e s t w o b e n c h m a r k so nt w o c l a s sr e c o g n i t i o na n dm u l t i c l a s sp r o b l e ma r et e s t e d ，a n d t h er e s u l t ss h o wt h a tt h es v mb a s e do ns u b t r a c t i v ec l u s t e r i n gh a v eb e t t e ro r e q u a 】c l a s s i f i c a t i o na c c u r a c ya n dg e n e r a l i z a t i o na b i l i t yw i t h s m a l l e rs e to f t r a i n i n gd a t aa n dc o s tl e s so p t i m i z a t i o nc o m p u t a t i o nt i m et h a nc o n v e n t i o n a l s u p p o r tv e c t o rm a c h i n e s k e yw o r d s ：t e x td a s s i f i c a t i o n ，f e a t u r es e l e c t i o n ，s u p p o r tv e c t o rm a c h i n e , s u b t r a c t i r ec l u s t e r i n g 1 1 i y8 g o b 7 3 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书荷使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：生卣盛日期盘。垒 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：圭尚滢； 导师签名 注：请将此声明装订在论文的目录前。 6 、p l 占 武汉理一【大学硕士学位论文 1 1 问题的提出 第1 章绪论 近年来，随着网络的迅猛发展，网上的网页，电子邮件，数据库，聊天室 和数字图书馆等电子文本成几何级数增长，处理这些海量数据的重要办法就是 对它进行分类。当处理这些海量数据文本的时候，手工分类往往费时费力，使 用文本自动分类系统可以帮助人们自动检查文本，判断文本属性的类别。比如 说，网络新闻过滤，每天大量的新闻出现在网络上，假如已知几篇读者喜欢的 文章，通过机器自动学习，可以把当天读者感兴趣的文章自动挑出来，供读者 阅览。s v m 是建立在v c 维和结构风险最小化( s r m ，s t r u c t u r a lr i s k m i n i m i z a t i o n ) 基础上的一种新的机器学习方法，广泛用于模式识别和回归领 域。它在有限训练样本基础上，构造一个具有较好推广能力的学习机，即在训 练复杂性与学习能力之间寻求折衷，以获得较好的推广能力。由于有较好的推 广能力，该方法广泛用于医疗诊断【1 】、图像识，n 2 i 、手写数字的识别等。因此 基于s v m 的研究及其文本分类的应用，是个非常有实际意义的课题。 1 2 国内外研究情况 长期以来，文本分类都是自然语言处理的一个重要的应用领域。但直到八 十年代末，在文本分类方面占主导地位的一直是基于知识工程的分类方法，即 由专业人员手工编写分类规则来指导分类，其中最著名的系统是为路透社开发 的c o n s t r u e 系统 3 。九十年代以来，随着信息技术的迅猛发展，以及大量计算 机可读形式的文字信息的急剧增加，为基于机器学习的文本分类方法准备了充 分的资源。在这种情况下，基于机器学习的文本分类逐渐取代了基于知识工程 的方法，成为文本分类的主流技术。近些年来文本分类技术取得了很大的进展， 提出了多种特征抽取方法和分类方法，如回归模型 4 、支持向量机 5 、最大 嫡模型 6 等，研究了一些相当成功的分类系统，建立了o h s u m e d ，r e u t e r s 等开 放的分类语料库。 武汉理1 ：大学硕士学位论文 但是，文本分类研究仍然缺乏一个大规模的、真实的、权威的语料库，缺 乏一种客观的评价机制，对不同方法和系统作出客观的比较。九十年代以后， 情况有了大的改善，著名的文本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，简称 t r e c ) 与主题检测和跟踪会议( t o p i cd e t e c t i o na n dt r a c k i n g ，简称t d t ) 都把 文本分类作为重要的评测内容，通过提供规范的大规模语料( g b 级) 对文本分类 系统性能进行客观、公正的评测，来促进技术的交流、发展和产业化。这就在 很大程度上促进了文本分类研究的发展。 从文本分类的方法来看，国外当前流行的文本分类方法有k 近邻法 ( k n n ) 7 、决策树 7 、朴素贝叶斯( n b ) 7 、支持向量机( s v m ) 7 、神经网络 ( n n e t ) 7 、线性最小平方拟合( l l s f ) 法 8 、最大墒模型【9 】、回归模型 1 0 、 遗传算法等方法。这些方法在英文文本自动分类上有广泛的研究，而且很多研 究表明k n n 和s v m 是英文文本分类的最好方法。国外很多研究人员对英文文本分 类领域的各个问题都有相当深入的研究，比如 5 ， 1 1 。 从文本分类使用的文档特征来看，不再仅仅限于词、短语或n g r a m ，词性、 标点符号h 2 等词法特征也被引入到了文本分类中。而且，随着研究的进一步 深入，人们发现词法特征携带的信息已经越来越无法满足文本分类技术的要求。 所以，基于文本语法层次的一些特征开始应用 1 3 ，但是这些特征的自动获取 还是一个悬而未决的问题。 国内文本分类的研究。起步相对较晚，研究中所使用的方法比较单一，主 要是基于向量模型的文档相似性比较，使用的文档特征主要为词或n - g r a m 1 4 。 1 5 使用概念推理网进行了文本分类的研究。f 1 6 1 q ，提出了一个基于机器学习 的、独立于语种的文本分类模型。1 7 1 提出了一种基于序列的文本自动分类算法。 该算法利用了文本中两个层次的语义相关性：句子( 子模式) 之间的相关性和句 子内代表特定含义的关键词( 概念节点) 之间的相关性，这样就实现了对关键词 的动态加权。对于不含有关键词的子模式，采用m a r k o v 模型来对其信号幅度进 行估计，从而生成一个待分类文本的特征序列。f 1 8 用b o o s t i n g 来组合决策树 ( s t u m p s ) 的方法进行文本分类。 1 9 1 从信息粒度的角度来剖析聚类和分类技术， 试图使用信息粒度原理的框架来统一聚类和分类。 2 0 1 利用多个分类器的有效组 合来提高分类的查准率。 s v m s 是建立在v c 维和结构风险最小化( s r m ，s t r u c t u r a lr i s km i n i m i z a t i o n ) 基础上的一种新的机器学习方法，尚处于发展阶段，许多方法和理论还需进一 武汉理上大学硕：亡学位论文 步完善。如许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而 有关s v m 算法某些理论解释也并非完美，j c b u r g e s 在 2 1 中就曾提到结构风 险最小原理并不能严格证明s v m 为什么有好的推广能力；对于一个实际的学习 机器的v c 维的分析尚没有通用的方法；s v m 方法中如何根掘具体问题选择适当 的核函数也没有理论依据。在这方面我们可做的事情是很多的。对于训练速度， 要依赖于核函数的计算时间和二次优化时间，这两方面都与训练样本的个数有 关。在研究中，我们发现训练集中的某些样本对于s v m s 性能没有大的影响 2 2 ， 2 3 ，因此提取一部分训练样本构造s v m s 既可减少核函数的计算时间，又可以 降低优化时闯。 s v m s 是针对两类问题的分类提出的学习算法。在应用过程中，必须注意一 些问题。一是如何克服过学习问题是；二是如何将两类问题推广到多类问题； 三是如何选择特征样本，减少训练时问。针对这前两个问题，h u a n g 等干 1 a b e 等 分别提出了两种类型的f s v m s 2 4 ， 2 5 。一类是为了克服过学习问题而提出的 f s v m s ，它主要根据训练样本在s v m s i j i i 练过程中的作用不同，将训练集模糊化，得 到模糊训练集用于构造支持向量机。 1 3 本文研究内容 本文就是在这样的背景下，主要针对基于s v m 的英文文本分类应用进行研 究。讨论并实现了文本表示的全过程，包括提取词干，去除高频率和低频率特 征词，得到数据字典，然后经过权重计算，生成文本向量空间，即训练样本和 测试样本数据。在深入研究s v m 算法的过程中，针对其算法对于大规模数据在 处理时核函数计算时间和二次优化时间过长的缺陷，提出基于减法聚类的s v m 算法。其目的是减少训练样本的个数，加速优化速度同时又不影响支持向量机 的推广能力。通过机器学习经典测试集验证了该算法有相同于或高于传统s v m 的推广能力。最后基于s v m 算法，实现了文本分类系统，该系统具有较好的 分类和预测效果。 1 4 本文的组织 本文后续章节组织如下：第二章概要介绍文本分类的技术，从特征词的表 示，特征的选取以及文档分类的评估指标均作了介绍，并给出本文的实验步骤。 武汉理工人学硕士学位论文 第三章介绍了支持向量机，支持向量机的基本思想、构造的基本方法以及多类 支持向量机的决策规则。第四章为提出了基于减法聚类的s v m 。其通过数据密 度的原理，选取聚类中心点，聚类中心点也为训练数据点本身。减少了训练样 本的个数，加快优化速度，并给出两类和多类的实验结果。第五章是基于s v m 文本分类系统设计和实现。 武汉理丁大学硕士学位论文 第2 章文本分类的技术 2 1 文本分类的定义 简而言之，文本自动分类的任务就是，在给定的分类体系下，根据文本的 内容自动地确定与文本关联的类别。从数学角度而言，分类的实质是一个映射 过程，它将未标明类别的文本映射到已有的类别中，该映射可以是映射， 也可以是一个一对多的映射。 文本分类的目标是从已知的文本训练集合中找到分类规则得到一个学习 器，并且使该学习器在对今后未知的新文本分类时，具有最好的预测精度。用 数学语言表示，该学习器由包含n 各训练样本的训练集合r 得到 t ：暖，m ) ，( 曼。，y 。) ( 2 1 ) 训练样本之间是独立同分布的，并遵循某一固定的但是未知的联合分布函数 p y ) 。这个分布决定了特定的学习任务。每个训练样本包含两个部分：文本 向量彭和其所属的类标记y 。文本向量f 是对文档的数学描述。通常，f 是个高 维向量，其各个分量由该文档的所包含的单词组成。而类标记y 的取值有不同 的分类结果决定。根据分类结果的不同，基于统计学习法的分类系统可以分为 三类：两类问题。多类问题和多标记问题。为了能度量学习效果，就需要度量 在给定训练样本岩下学习器响应 与实际值y 之间的损失或差异( ，y ) 。 考虑损失的数学期望 r ) - f z ( h ，y ) d p ( p x , y ) ( 2 2 ) ， 它就是风险泛函。学习的目标就是，在联合概率分布函数p ( z ) ，) 未知、所有可 用信息都包含在训练集合( 2 1 ) 的情况下，寻找分类规则k ( 妁，使它最小化 风险泛函。 下面就不同的文本分类系统来讨论损失函数( ( 均，_ ) ，) 。 武汉理工大学硕 ：学位论文 2 1 1 两类问题 两类问题事最简单的，但同时也是最重要的学习问题。很多复杂的学习问 题最终都可以归结到两类问题上来。所谓二类问题，就是给定一篇文章，分类 系统对该文档判断是否属于该类，要么属于，要么不属于，而不存在其它的结 果。举例来说邮件分类系统，对于每封邮件，系统就判断是属于正常邮件还是 垃圾邮件。它说明类标记y 只有两个可能的取值。为便于讨论，我们一般规定 为+ 1 或一1 。因此y 一1 ，+ 1 。 最常见二类问题的损失函数就是0 1 损失函数。如果对一篇文档的预测结果 ，l ( 蚧等于其实际类标记y 。损失函数的返回值为o 。如果不等，损失函数返回 值为1 。 l 叭帕棚= 仨：塞： ： s ， 该损失函数所对应的风险泛函( 2 2 ) 就叫做分类错误e ( ) 。 e ) ：f l 。n 圆，y ) a p ( g , y ) ( 2 4 ) 分类错误对任何类型的错误都一样对待，但是这和实际是不符。比如说， 一个邮件过滤系统如果把一封重要电子邮件当作垃圾邮件过滤掉，相比于把一 封垃圾邮件送给收信人查看，后果是不同的。显然第一种情况造成的后果严重 多了。通过引入代价因子c + 一和c 一+ ，对于第一种情况，损失函数值取c 一+ ；第 二种情况，损失函数返回c 一。 f c + 一 ( f ) ；+ 1 ，y = - 1 l o 1 ( i l 国，y ) ：j c 一+ ( 马：一l , y = + 1 ( 2 5 ) l o其他 虽然说任何学习算法都是为了从数量上减小分类错误，但是实际在评价一个文 本分类器的好坏时用的是其它的评判标准。这个将在后面2 6 中详细介绍。 许多学习算法得到的分类规则h s ( 马并不直接得到+ 1 或是- 1 的分类结果 值，而是输出一个实数值。该实数值反映了训练样本譬属于类y = + 1 的概率大 小。s v m 算法就是用到了这种方法。 武汉理工人学硕十学位论文 2 1 2 多类问题 有些分类任务并不单单仅限于两类问题。比如说，一个电子邮件服务器在 转发电子邮件时，需要把该邮件同时转发给整个局域网中的9 个员工，那么这 样y 的取值可能从1 到9 。更普通话，也许是从1 到n 的取值。这样y 1 i n 。 因为0 1 损失是多类问题的一个特例，所以先前定义的分类错误和代价因子都 可以直接应用到多类问题上来。 有部分文本分类算法可以直接解决多类问题，比如说决策树。有些分类算 法就只能解决两类问题。其实一个多类问题可以分为n 个二类问题来解决。如 果一个二类学习算法估计训练样本属于某类的概率值p ( y = fl 妁。对每类f ，就 有一个对应的二类学习问题。比如对第i 的二类学习问题，当且仪当y = f 时， 妒) = + 1 。如果y - f ，y u ) 一1 。现在对各个二类学习任务通过学习得到n 个 分类规f , f j h ( “， ( 。在预测新的未知文档量的类别时，计算每个分类规贝r j h ( 输 出的概率值e ( y f i 妁。通过分析n 个概率值的大小，新的文档就被分类到概 率值最大的那个类中去了。 这样的将一个多类问题分解为n 个二类问题的方法叫做“1 对多策略” ( o n e a g a i n s tt h er e s ts t r a t e g y ) 。另外还有一个用的比较少，但是也很有前景的 算法是p a i r - w i s e 测略【2 6 】。该策略是对n 类问题划分为n 伽一1 ) 2 个二类问题来 解决。一次比较就能计算出某个文档属于其中某两类的概率大小。最终判断该 文档的类别时，就基于n m 一1 ) 2 个分类器的投票原则。 2 1 3 多标记问题 还有许多文本分类属于多标记问题。和多分类不一样，并不是每个文档都 有一个与之相对应的文本类别。而是，对于r 1 个类别，每个文档可能属于一个， 多个，或o 个类别。比如说按文章的语义来分，一篇体育新闻报道既可以归为 足球类，也能归于德国类。这样，一篇文档的类别标记就用一个n 维的二值向 量y + 1 ，一1 ) ”来表示。其中每个分量表示该文本属于此类或则不属于此类。由 于分类标记是一个n 维向量，那么对应的分类规则它的输出也是一个n 为维的 二值向量。 现有的文本分类算法还不能直接处理多标记问题。而且，还有个问题是不 武汉理工大学硕士学位论文 清楚如何统计多标记问题中出现的分类错误。从严格的0 1 损失角度来看，分 类错误发生在当文档的预测值与实际值不相符时。但是这样定义的损失函数并 不能表示“临近错误”( c l o s em i s s e s ) 。多于多标记分类问题，一个好的损失函 数必须指明预测类别值和真实类别值在位置上的差异。在这个问题上，个可 行的距离矩阵是海明距离( h a m m i n gd i s t a n c e ) 。海明距离计算所有的分类错误 个数，进而得到损失函数。 l n 伪圆，易：多工0 1 ( h t 0 ( 马，) ，) ( 2 6 ) 面 损失函数就是这n 个二类问题的错误类型之和。 r ( 6 ) 4 荟e ( 2 7 ) 这样来说我们也可以把一个多标记问题分为一系列二类问题。每一类对应一个 独立的二类分类问题，要么文档属于此类，要么不属于。对于每一类f ，定义 二类问题如下：当且仅当y “) = + 1 时，该文档类标记为1 ；如果y ( j ) 一1 ，该文 档类标记为1 。现在一个分类器对每个二类问题产生n 个分类规则 m ，h o ) ， 在预测未知文档的过程中，如果h ( oz 1 ，未知文档的属于第i 类。 假设类和类之间相互独立，由贝叶斯定律，最小化每个类上的分类错误就 是降低整体的分类错误。但是该假设是否能提高分类精度在实践中还有待考证。 2 2 文档表示 如何表示一篇文档是某个学习算法的能够很好推广的关键所在。文档的表 示时常需要符合某个学习算法潜在的假设条件。比如说一些算法规则的形式， 文章排列的顺序等等要求。因此选择一个好的表示文档的方法是建模的关键。 尽管有些文本已经以一种机器可读的方式存储( 像h t m l ，p d f ，p o s t s c r i p t ) ， 但是这种结构不适合大多数的学习算法。所以它必须转化为一种既适合学习又 适合分类的表示方法。 自然语言处理过程中一个基本问题是篇文章的内容总是卜下文相关的。 比如说，同样的英语单词在不同的句子里面有不同的意思。举个例子来说，“b o x ” 武汉理：r ：大学硕士学位论文 可以指箱子，又可以指拳击的意思。同样的一旬话在不同的场合下对不同的听 众说又有不同的意思。各种学习算法采用的文本表示方法在上下文相关性的联 系上面，有松有紧。在表示一篇文章的时，可吐从下面5 个层次上着手： 1 语形学层次：研究构词方法 2 词汇学层次：研究整个单词 3 句法学层次：研究句子结构 4 语义学层次：研究整个文章的意思 5 实用学层次：研究上下文关系。 每个层次上基本元素称为索引项。在词汇学层次上，单词就是索引项，在句法 学层次上，整个句子就是索引项。 从语言学的角度上来说，这样的层次结构对自然语言处理很有作用。并且， 每个层次之间都是相互依赖的，当前层次的歧异可以由更高的层次解决。比如 说在词汇层上，光凭单词“b o x ”你不知道到底是名词还是动词。但是这个问题 可以在句法层上解决( p l e a s ep u l lt h a tb o x ) 。一般来说，层次越高，表示文章的 内容越详细。但是同时也会增大自动生成文本表示方法的复杂度。 下面介绍基于单词的文本表示方法。该方法在文本分类中最通用，并且本 文也是采用该方法来表示文本。 在不考虑上下文关系时，大部分单词都是表示意思的实体，很少具有二义 性。当文章中存在像“b o x ”这样的同义词时，通常认为它们对整个文章的内 容没有多大的影响。实际上，以单词为基础的文本表示方式在信息检索和文本 分类的实践过程中是非常有效的 2 7 1 。它是大多数文本分类的基本表示方式。 基于单词的文本表示另外一个好处就是简单，一篇文档也容易划分为一连串 的单词集合。在英文文章中，通过空格符号就能把一个一个的单词划分出来。 但是对于其它语言，比如说中文来说，需要借助于词典和使用专门的分词技术。 现有的中文分词系统一般比较复杂和庞大，分词速度慢，对人名、地名、组织 机构名的辨识率还不高。 不考虑到文章的逻辑结构和层次，光用单词作为索引项就能表示一篇文档。 此外，我们通常假设单词与单词之间的顺序排列对文本分类任务没有什么影响。 因此，我们用词袋法( b a g - o f w o r d s ) 来表示一篇文档：只记录每个单词在文章 中出现的频率，不考虑相互之间的顺序问题。 词袋表示方法适用于大部分的机器学习算法。该方法要求篇文档以固定 苎坚尘兰兰兰= = = 一 燮二策熏纛雾鬈鬣裳霎磊嚣霈鬻：篮黩 孽篙k ：鑫善墨；繁鬟蠢衰鑫愍鬟嘉翥葛藏翕嘉? 焉鬻q u e 篡 该属性在此文章中出现的次数。通常将出现的次数定义为阿揪q 削“c “ 卯( w ，d ) 。图2 1 说明如何将一篇文章用词袋法表示出来【5 。 图2 1 用一个属性向量表示一篇文章 一黧黧篡豢意溅兹篙赫嚣茹 竺登警兰髦茎蓁鬻鬈妻言荔；鋈譬篙蓉箬着嚣爵鼍嚣篙器 燃瓣雾慧慕篙鬟麓君篮翥翟茹羞囊 它们基础上的统计模型的质量。词袋法是在文蕈侣思阴衣巩7 。“”嫩偎2 “、 兰熊赫徽慧鬈嬲嚣篆麓罴燃然 詈望罩个姜兽要车嚣嚣墨妻篙誊了鍪差磊萎蔷是素嘉蒿嚣銮銮：篓雾粢墨凳 问太大，并且为了防止过学习问题，往往需饕间化原；f 百“。忖位。秉5 。1 、。1 “ 武汉理t 大学硕士学位论文 用或不相关的信息，就叫做特征提取。常用的两种技术包括：特征子集的提取 和特征重构。下面的介绍主要以词袋表示法为基础，但是这些方法也可以用到 其它文本表示方法上去。 2 3 1 特征子集提取 特征子集提取就是用原始文档的部分信息来表示整个文档，去掉信息量少 的项以提高分类的效率并降低计算的复杂性。在英文文章中常用的去除无关特 征量的方法是去掉停顿词( s t o p w o r de l i m i n a t i o n ) 。比如说像“t h e ”，“a n d ”，“b u t ” 等等毫无信息量的单词，我们就把它们从文档中去掉。 去掉停顿词是从文档中去掉了高频率的单词。d o c u m e n tf r e q u e n c y t h r e s h o l d i n g 2 8 方法主要是去掉低频词。这是基于假设低频词由于其出现的频 率低所以包含的信息量也很少。所以当某个单词在整个文档集合中出现的频率 低于某个阀值的时候，就把其去除掉。 本文中采用的去掉高频词和低频词的方法是z i p f 定理。z i p f 是哈佛语言学 教授g e o r g ek i n g s l e yz i p f ( 1 9 0 2 - 1 9 5 0 ) 通过大量实际现象观察得到的，是个经 验理论。构成文本的单词集合w ； w 1 ，w 2 ，w a ，有不同的概率被选用，这些概 率反映了单词的分布规律。如果假定是文本中最高频率单词，频率为p ， m 是次高频的单词，频率为p ：，依次类推，是最低频单词，频率为以。z i p f 首先发现，单词的分布率近似符合规律：n c i ，此处c ，0 是个常数。这 就是所谓的z i p f 定律。 z i p f 定律告诉我们，如果词频t f ( w ，d ) 表示单词燃在一篇文档d 中出现的 次数，那么我们定义巩= yt f ( w j ，d ) 表示单词哗在整个文档集中出现的次数。 我们将所有的单词按出现频率的大小从大往小排列，p 1 ，p ：，p f ，以。则对 n = c i 两边取对数，得到表达式l o g ( 只) = l o g ( c ) 一l o g ( ) 。如果在坐标轴中，x 轴表示l o g ( ) ，y 轴表示l o g ( p i ) ，那么这些点近似为一条直线，遵循z i p f 定律。 如图2 2 所示1 2 9 1 。 武汉理工大学硕士学位论文 1 0 0 0 1 0 0 l o g ( 卑) 1 0 1 。 11 01 0 01 0 0 0 l o g ( i ) 图2 2z i p f 定理 下面给出来的文档特征选取方法和上述方法不一样。这些方法是基于信息 论和统计分析，目的是通过测试比较，找到比较好的文档特征。 互信息( m u t u a li n f o r m a t i o n ) ： 互信息可以度量特征项和类别的共现关系，特征项对于类别的互信息越大， 他们之问共现概率也越大。假设文档集合t 分为n 类，记为y l , y ：，y 。，项w 对于类别y ；的互信息，( w ，y ；) 的计算公式为 伽，) ，一) = l 。g 而p ( w , y i ) ( 2 8 ) 其中p ( w ，y ；) 为项w 出现在类y ，中的概率，p ( w ，t ) 为项w 出现在所有文档中的 概率。一个项如果它具有较高的互信息就被选作特征项。 x 2 统计 x 2 统计也是用于表征两个变量间的相互性，但是它比互信息更强，因为它 同时考虑了特征存在和不存在的情况。对于文档类别y 和项w ，其x 2 统计的计 算公式如下： 以曲= 盟篇勰嚣铲眩。， x 2 越大，则独立性越小，相关性就越大。 注意上述特征提取的方法在一定程度上都假设了单词与单词之间是相互独 武汉理j 二大学硕士学位论文 立。但是特征选择这一步并不是必不可少，因为一个好的学习算法必须具有一 定的分辨无关特征的能力。而不是靠经过特殊筛选的特征量去掩盖算法本身的 不足，因为这样的特征量所包含的信息既存在于训练集合也同样存在于测试集 合中。 2 3 2 特征重构 特征重构就是将原有的特征集加以合并和转化以重新建立新的特征集合， 以达到降低维数的目的。 词干抽取( s t e m m i n g ) 由于英文存在词形的变化，如：名词的单复数，动词时态变化，词的前缀和后 缀变化等，所以抽取词干也是在词的构成法的层次上分析该特征项。词干抽取 的前提在于我们假设具有相同词干的不同词形在文本分类任务中是一样的。那 么可以用一个词于来代替其所有其它的词形。比如说“c o m p u t i n g ”， “c o m p u t a b i l i t y ”，“c o m p u t e r ”都可以用“c o m p u t ”代替。一个著名的英语词干 抽取算法见【3 0 】，本文系统中就采用该算法对文章进行特征重构。 项聚类 项聚类就是试图将在语义方面具有高关联性的项分组，从而该分组的表示 将代替这些项成为向量空间中的维度。项聚类有别于特征子集的提取，前者试 图阐述项之间意义方面的关联性，而后者主要着眼于不提供信息的项。 l e w i s 是首次在文本分类中研究项聚类的学者。他采用的方法是相互近邻 聚类算法，该算法中形成聚类的方法是根据某种计算相似度的量度计算两项之 间的相似度而产生聚类。但其结果一般，当然其中原因可能是聚类方法效率不 高。 潜在语义标引( l s i ) 潜在语义标引是一种线形主成分分析法1 3 1 1 应用到文本分类上束。i s l 使用 奇异值分解法将特征向量由高维映射到低维子空间上。通过正交变换，在新的 坐标轴上产生新的特征向量。选取前m 个具有最大值奇异值相对应的特征向 量，它们的在保持大部分原始信息的同时，使得文本的维数降低。m 的取值事 先不知，可以通过交叉验证的方法得到。i s l 的思想是希望通过变换将相互关 联的特征项都用同一个主成分表示。基于i s l 的文本分类应用可以参考 3 2 1 。 武汉理_ j 大学硕士学位论文 2 4 特征项的权重 不同的特征项对文档的重要程度和区分度的影响是不同的，因此学习算法 在对文本进行形式化处理的时候，需要对特征项进行加权。 特征项的权重系统里面有3 个重要概念【3 3 】。项频率( t e r mf r e q u e n c y ) t f ( w i ，d 。) 表示特征项峙出现在文档d 。中的频率。关于项频率有两个经验性的 结论：一个项在某文档中出现的次数越多，它和该文档的主题就越相关；一个 项在选取的文档集合中出现的次数越多，用它来分辨文档之间的差异就越小。 第二个是文档频率( d o c u m e n tf e r q u e n c y ) d f ( 嵋) ，表示文档集合中包含特征 项m 的文档个数。如果某一特征项的文档频率很高，那么它的权重就减小。第 三个是归一化( n o r m a l i z a t i o nc o m p o n e n t ) ，通过调整特征项的权重值，使得长度 不一的文档能够在同一标准下相互比较。下面对常用的加权函数进行详细介绍。 布尔权重 布尔权重是最简单的一种加权方法，如果特征项出现次数为0 ，则其权重 为o ，如果特征词出现词数大于0 ，则其权重为1 。归一化后该特征项值为： 置：；丝堕堡! ( 2 1 0 ) 、f ( w j ，d ) 2 w ( w j ，d ) 表示特征项m 在文档d 中的权重，出现了为1 ，不出现为0 。 词频权重 该方法将特征项的词频作为权重。归一化后该特征项值为： 工：丝丝：堡!( 2 1 1 ) x j t f ( w j ，d ) 2 t f i d f 权重 该方法采用欧几里得归一化。 x = t f ( 叫) 1 0 9 ( 器) 其中lti 表示文档集中文档总数。更详细的介绍请看【3 3 】。 ( 2 1 2 ) 武汉理工大学硕士学位论文 2 5 传统学习方法 文本分类的方法大部分来自于模式分类，基本上可以分为三大类。一种是 基于统计的方法，如n a i v eb a y e s 【3 4 ，k n n 3 5 、支持向量机【5 】等方法：另一种 是基于连接的方法，即人工神经网络【3 6 】；还有一种是基于规则的方法，如决策 树【3 7 】、关联规n 3 8 等，这些方法的主要区别在于规则获取方法。 n a i v eb a y e s 分类方法 n a i v eb a y e s 分类方法( 以下简称n b 法) 是一种简单而又非常有效的分类方 法。n b 法的一个前提假设是：在给定的文档类语境下，文档属性是相互独立的。 假设d 为一任意文档，它属于文档类y ； y ，y ：，y 。 中的某一类y 。根据n b 分类法有： 驯妒掣 ( 2 1 3 ) 公式( 2 1 3 ) 中的分母在各个类中没有什么不同，可以忽略。则公式可以简化 为： p ( y 。i d ) * p ( y ；) p ( di y 。) ( 2 1 4 ) 在特殊情况下，训练集合中各类样本数相等，此时e ( y j ) 的先验概率相等，式 ( 2 1 4 ) 可以进一步简化为： e ( y ；l d ) o cp 似l y f ) ( 2 1 5 ) 对文档d 进行分类，就是按f 公式2 1 4 ) 计算所有文档类在给定d 情况下的概率， 概率值最大的那个类就是d 所在的类，即： p ( y i i d ) ；a r g m a x p ( d i y ，) p ( y ，) ，= 1 , 2 ，n ( 2 1 6 ) 由此可知，对于给定分类背景和训练文档，用n b 法分类的关键就是计算 尸( y 。) 和p q i y ；) 。计算p ( y ，) 和e ( d i y 。) 的过程就是建立分类模型( 或者说学习) 的过程。 关于n a i v eb a y e s 分类器的试验结果可以参考 3 9 】 r o c c h i o 算法 r o c c h i o 算法基于向量空间模型【4 0 】和最小距离法，其最大特色是具有良好 的反馈功能，能根据其公式对分类的向量空问进行修正。最早由r o c c h i o 提出 武汉理工人学硕士学位论文 【4 1 j a 该方法是一种基于向量空间模型的方法。在分类器的训练阶段，使用训练 文档集得到每一个类别所对应的中心向量。在分类阶段，对于某一给定的文档 d ，计算文档向量和每个类别中心向量的相似度，然后按相似度进行从大到小 排序。相似度最大值所对应的类别，就是文档的所属类别。如果希望文档可以 属于多个类别，可以设定一个阀值，文档属于相似度超过阀值的所有类。 对二类问题，训练集中包含正样本集和负样本集。首先计算中心向量彤： 一南髻，邓高鬣，( 2 1 7 ) p o sl 是正样本集的个数，l n e gl 是负样本集的个数。卢是调整正样本集和负 样本集所占权重的大小。一般口= 0 2 5 。 在分类一个新的样本d 时，计算文档d 和w 的c o s i n e 值。当c o s i n e 值超过 某一阀值，就可以划分新文档的类别。r o c c h i o 算法的试验结果可以见1 4 2 。 k n n 方法 k n n 法即k - n e a r e s tn e i g h b o r 分类方法，这是一种稳定而有效的文本分类 方法。采用k n n 方法进行文档分类的过程如下：对于某一给定的测试文档d ， 在训练文档集中，通过相似度找到与之最相似的k 个训练文档，而且这些文档 应当满足其与