（计算机软件与理论专业论文）基于支持向量机的大规模文本分类研究与设计.pdf

山东师范大学硕上学位论文 摘要 随着通信技术和计算机技术、尤其是i n t e m e t 的飞速发展，各种各样的信息 成几何级数增长，作为传统的信息载体，文本信息更是如此。为了能在海量纷杂 的文本信息中及时准确地获得有效的知识和信息，文本表示技术以及文本自动分 类技术受到了广泛的关注。文本分类对于提高网上信息检索的效果和效率很有帮 助，是推进个性化服务，改进信息获取模式的重要方面，也是内容安全的基础。 因此好的分类性能是关注的焦点。基于支持向量机( s v m ) 的文本分类算法，更 是成为当前的一个研究热点。 本文首先研究分析了文本分类器的总体模型和文本表示及文本分类的关键 技术。在特征提取部分，结合了基于文档频率( d f ) ，z 2 分布( c h i ) ，信息增益( i g ) 以及互信息( m i ) 等几种不同的特征选择方法，通过实验结果的比较，证明在本 文的系统中基于i g 的特征选择方法要优于其他方法。在文本表示部分，采用了 t f i d f 权重计算方法，实现了向量空间模型。在多类分类算法中，采用对余类 方法实现多类分类问题，分类结果较为理想。 本文重点对统计学习理论进行了研究，深入探讨了建立在该理论基础上的支 持向量机算法，阐述了支持向量机研究和应用现状，以及所面临的问题。并且作 者就目前支持向量机的训练算法、分类算法、求解大型问题的算法等热点问题进 行了分析和讨论，针对海量纷杂的文本分类存在的瓶颈问题即计算时间和占用内 存，本文结合s v m q p 思想提出了一种并行化的s v m 分类算法一p c s m o k n n 算法。该算法把海量文本分到多个并行的从处理器上用c s m o 训练，再用k n n 算法在特征空间对所有s v 进行加权回归。该算法充分利用了组合分类器的优势 使大规模文本分类时训练速度和分类精度得到较好的折中。实验证明，该算法大 大提高了大规模文本分类的训练速度和精度，有效地解决了s v 较多时求解s v m 分类器的瓶颈问题。 此外，在对中文文本分类关键技术和支持向量机变形算法的的研究基础上， 本文作者设计了一个基于改进算法的中文文本分类系统，并在一定条件下对该系 统进行了实验仿真，通过训练集和测试集对分类器进行训练和测试，取得了较好 的分类效果，在一定程度上解决了基于s v m 的大规模文本分类的瓶颈问题。 关键词：支持向量机，k n n 算法，并行技术，加权回归，文本分类 中图分类号：t p 3 9 3 山东师范大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o n ，c o m p u t e r i n ga n do fe s p e c i a l l y i n t e m e t ，a l lk i n d so fi n f o r m a t i o nh a sg r o w ng e o m e t r i c a l l y s od o e st e x ta si n f o r m a t i o n c a r r i e r i no r d e rt op i c ku pv a l i di n f o r m a t i o nf r o mt h em a s s i v ea n dc o m p l i c a t e dt e x t ， t i m e l ya n da c c u r a t e l y ，t e x tp r e s e n t a t i o na n da u t o m a t i ct e x tc a t e g o r i z a t i o nt e c h n o l o g y h a v er e c e i v e dw i d e s p r e a da t t e n t i o n t e x tc a t e g o r i z a t i o ni s v e r yh e l p f u l f o r e f f e c t i v e n e s sa n de f f i c i e n c yo fi n f o r m a t i o nr e t r i e v a l ，w h i c hp r o m o t e sp e r s o n a l i z e d s e r v i c ea n di m p r o v e si n f o r m a t i o n a c q u i s i t i o n m o d e s o g o o d c l a s s i f i c a t i o n p e r f o r m a n c ei st h ef o c u s ，a n dt e x tc a t e g o r i z a t i o na l g o r i t h mb a s e do ns v m i sm o r e m o r er e s e a r c hf o c u s f i r s t ，t h ed i s s e r t a t i o na n a l y z e st h eo v e r a l lm o d e lf o rt e x tc l a s s i f i c a t i o n ，t e x t r e p r e s e n t a t i o na n dk e yt e c h n o l o g yf o rt e x tc a t e g o r i z a t i o n i nf e a t u r ee x t r a c t i o n ， s e v e r a ld i f f e r e n tm e t h o d so ff e a t u r es e l e c t i o na r ec o m p a r e ds u c ha sd o c u m e n t f r e q u e n c y ，c h id i s t r i b u t i o n ，i n f o r m a t i o ng a i na sw e l la s m u t u a li n f o r m a t i o n i ti s p r o v e dt h a tt h em e t h o do ff e a t u r es e l e c t i o nb a s e do ni gi sb e t t e rt h a no t h e rm e t h o d s i nt e x tr e p r e s e n t a t i o n ，v e c t o rs p a c em o d e li si m p l e m e n t e db yu s i n gt f i d f a n d a m o n gm u l t i - c l a s s i f i c a t i o na l g o r i t h m s ，o n ev e r s u so t h e r sa l g o r i t h mi su s e da n dt h e r e s u l t sa r eq u i t e s a t i s f a c t o r y t h ed i s s e r t a t i o nf o c u s e so nt h es t a t i s t i c a ll e a r n i n gt h e o r y ，p r o b e si ns u p p o r tv e c t o r m a c h i n ea l g o r i t h mb a s e do ni t ，a n de x p o u n d so nt h ec u r r e n ts t a t u so fr e s e a r c ha n d a p p l i c a t i o no fs u p p o r tv e c t o rm a c h i n e s ，a sw e l la st h ep r o b l e m sf a c e d f u r t h e r m o r e ， t h ea u t h o ra n a l y z e sm a dd i s s c u s so nt r a i n i n ga n dc l a s s i f i c a t i o na l g o r i t h mo fs v m ，a s w e l la sh o ti s s u e ss u c ha st h ea l g o r i t h m sf o rs o l v i n gl a r g ep r o b l e m s t h ed i s s e r t a t i o n p r o p o s e s ap a r a l l e ls v mc l a s s i f i c a t i o na l g o r i t h m p c s m o k n nc o u p l e dw i t h s v m q pi d e at oc o p ew i t hb o t t l e n e c k s n a m e l yt h ec o m p u t a t i o nt i m ea n dm e m o r ya s f o rt h em a s s i v ea n dc o n f u s e dt e x tc l a s s i f i c a t i o np r o b l e m s t h ea l g o r i t h ma s s i g n st h e m a s s i v et e x ti n t om a n yp a r a l l e lp r o c e s s o r s ，t r a i n st h e mb yc s m oa l g o r i t h m ，a n dt h e n w e i g h st h es vs e t si nf e a t u r es p a c eb yk n n t h ea l g o r i t h mm a k e sf u l lu s eo ft h e a d v a n t a g e so fc o m b i n e dc l a s s i f i e r st oc o m p r o m i s et r a i n i n gs p e e da n dp r e c i s i o ni n b e t t e rw a y a n di ti sp r o v e db ye x p e r i m e n tt h a tt h ea l g o r i t h mg r e a t l ye n h a n c e st h e t r a i n i n gs p e e da n da c c u r a c yo fm a s st e x tc l a s s i f i c a t i o n ，a n d s o l v e s e f f e c t i v e l y b o t t l e n e c kp r o b l e m sw h e nt h e r ea r em o r es v s i na d d i t i o n ，t h ea u t h o rd e s c r i b e st h ed e s i g no fac h i n e s ec l a s s i f i c a t i o ns y s t e m b a s e do nt h ei m p r o v e da l g o r i t h ma f t e rs t u d y i n gk e yt e c h n o l o g i e sf o rt e x t 山东师范人学硕士学位论立 c l a s s i f i c a t i o na n ds v md e f o r m m i o na l g o r i t h m a n dt h es y s t e mi ss i m u l a t e db y e x p e r i m e n tu n d e rc e r t a i nc o n d i t i o n s f i n a l l yt h eb e t t e rc l a s s i f i c a t i o ne f f e c ti sa c h i e v e d b yu s i n gt r a i n i n gs e t sa n dt e s ts e t st ot r a i na n dt e s tt h ec l a s s i f i e ra n dt h es y s t e mh a s s o l v e dt h eb o t t l e n e c kp r o b l e m so fm a s s i v et e x tc l a s s i f i c a t i o nb a s e do ns v mi na c e r t a i ne x t e n t k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e ，k n na l g o r i t h m ，p a r a l l e lt e c h n o l o g i e s ，w e i g h e d r e g r e s s i o n ，t e x tc l a s s i f i c a t i o n c l a s s i f i c a t i o n ：t p 3 9 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 靠确 翩繇牛 学位论文版权使用授权书 本学位论文作者完全了解生撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 墼可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作 签字日期：2 0 0 7 新繇一涉 签字目期：2 0 0 7 年胡相 山东师范大学硕士学位论文 第1 章绪论 1 1 课题的研究背景及意义 我们正处在一个信息爆炸的时代! 根据1 9 9 8 年的统计结果，全世界每年出 版大约1 5 6 0 0 0 种期刊，而且这一数字以每年1 2 0 0 0 种的速度递增。同时，仅美 国国内就有近1 4 0 万种图书付印，这一数据还以平均每年6 万种的速度增加。1 9 9 9 年，美国国会图书馆藏书约为1 7 0 0 万种，平均每天接受的新书多达7 0 0 0 种。另 一个增长更为惊人的信息渠道为i n t e m e t 。1 9 9 9 年的统计结果表明，i n t e r n e t 上 有约3 5 亿个静h t m l 页面，每天增加将近1 0 0 万。而且，在信息数据保持高速 增长的同时，我们的吸收能力却并没有随之增强。因而，我们一方面感觉自己淹 没在信息的海洋里，但另一方面又发现得不到最急需的信息。这就是我们经常所 说的“信息发达，知识贫乏”。面对如此庞大而且急剧膨胀的信息海洋，如何有 效地组织和管理这些信息，并快速、准确、全面地从中找到用户所需要的信息是 当前信息科学和技术领域面临的一大挑战，其中一个直接而成功的范例就是根据 信息的主题对信息进行归门别类。文档分类作为处理和组织大量文本数据的关键 技术，可以在较大程度上解决信息杂乱现象的问题，方便用户准确地定位所需的 信息和分流信息。因此，自动文本分类己作为一项具有较大实用价值的关键技术， 得到了广泛的关注，并取得了很大的进展。 鉴于因特网上的大部分信息都以文本的形式存在，因此，文本信息的分类就 显得更加迫切、更加与人们的上作与生活密切相关。同时，爆炸式增长的文本信 息给文本分类的精度与速度提出了新的标准与挑战。这要求文本分类在提高精度 的同时，还要进一步提升训练与分类速度。这就是高性能文本分类算法的基本要 求。 国外对于文本自动分类的研究开展得较早，2 0 世纪5 0 年代末，h pl u h n 对文本自动分类进行了开创性的研究，将词频统计思想应用于自动分类。文本分 类是一种确定文章所属类别的情报分析方法，是大型信息检索或文本挖掘系统中 的一个重要组成部分，也是文本挖掘的核心环节。由于文本分类可以应用于信息 检索、机器翻译、自动文摘、信息过滤、邮件过滤等诸多领域，因此文本的自动 分类是自然语言处理的一个十分重要的问题。在文本自动分类中，分类模型( 分 类器) 是决定分类效果好坏的一个关键部分，现有的文本分类模型主要有决策树 ( d e c i s i o n t r e e ，简称d t ) 、支持向量机( s u p p o r t v e c t o r m a c h i n e ，简称s v m ) 、贝 叶斯网络、k 一最邻近法( i n n ) 等。s v m 以其泛化能力强而得到人们的青睐。 1 9 9 5 年以来，以统计学习理论为基础的支持向量机成为新一代的学习机器， 山东师范大学硕士学位论文 与现有的各种机器学习相比如神经网络，参数估计方法等，由于其理论上的完备 性得到越来越多的研究，在解决小样本，非线性及高维模式识别中表现出许多特 有的优势，并能推广应用到函数拟合等其他机器学习问题中，成为近年来机器研 究领域的一个热点，而s 的优化算法更是备受关注。小波神经网络，遗传算 法的神经网络随和b p 算法的神经网络都过于依赖初值，存在过学习现象，训练 过程存在局部极小问题，s v m 克服了局部最优，随着其快速训练算法的出现， s v m 在手写体识别，人脸识别，文本分类等领域取得了很大的成功。目前，支 持向量机在模式识别、函数逼近、数据挖掘和文本自动分类中均有很好的应用。 传统支持向量机是针对两类分类问题，而在实际应用中，如数据挖掘、文本分类 等等，需要处理的数据是海量和多类别的。如何解决大规模多类别的问题，是近 几年来研究的重点之一。 s v m 基于结构风险最小化思想，在线性不可分问题上v a p n i k 等人成功地引 入核空间理论，将低维的输入空间数据通过非线性映射函数映射到高维特征空 间，从而把分类问题转化到高维特征空间进行，使s v m 分类器正式成为通用的 分类器之一。s v m 算法的实现有赖于解决一个二次规划问题，当样本较多时， 传统的二次规划方法及其软件在计算时间，占用内存和计算精度上都出现问题， 因此s v m 只限于小样本，不利于海量数据的挖掘，例如，对( 超) 大规模样本 集训练代价太高( 耗时太长，占用内存太大) ，以及在s v 很多时分类器反应速 度太慢，用户无法忍受，因此样本较多时计算时间和占用内存仍是求解s v m 优 化算法的瓶颈问题。 1 2 国内外发展动态 v a p n i k 等早在二十世纪六十年代就开始了统计学习理论的研究。1 9 7 1 年， v a p n i k 和c h e r v o n e n l d s 提出了支持向量机的重要的理论基础一v c 维理论l i j ； 1 9 8 2 年，v a p n i k 提出了具有划时代意义的结构风险最小化原理，堪称支持向量 机算法的基石；1 9 9 2 年，b o s e r 和v a p n i k 提出了最优边界分类器1 2 11 9 9 5 年， c o r t e s v a p n i k 等完整地提出了支持向量机分类器；1 9 9 7 年，v a p n i k 、o o k o w i c h 和s m o l a 介绍了基于支持向量机方法的回归算法和信号处理算法。自此之后，由 于s v m 算法的优良性质和潜在应用价值，吸引了国际上众多的知名学者，近几 年随着支持向量机理论上的深入研究，出现了许多发展和改进的s v m 算法。如 文献【3 5 】所述。另外，s m o l a 在他的博士论文中详细研究了s v m 算法中各种核 的机理和应用。s v m 方法在理论上具有突出的优势，贝尔实验室率先在美国邮 政手写数字库识别研究方面应用s v m 方法取得了较大的成功【6 】；w i l l i a m s o n 等 7 1 对于核函数的泛化误差给出了个更紧的界；s c h o l k o p f 对分类和回归问题提 山东师范大学硕士学位论文 出的v s v m 算法；s u y k e n s 提出的最4 , - 乘支持向量机；m a n g a s a x i a n l 8 1 等人提 出的广义支持向量机。 国内许众多学者也对支持向量机的推广和发展作出了许多贡献，如张学工在 文献驯中介绍了统计学 - j 理论与支持向量机，并于2 0 0 0 年翻译出版了v a p n i k 的 1 0 ；李国正，王猛等翻译了c d s t i a a i n i 等的 a ni n t r o d u c t i o nt os u p p o r tv e c t o rm a c h i n e sa n do t h e rk e r n e l - b a s e di x a m i n g m e t h o d ) ) 1 1 1 ；张铃研究了支持向量机理论与神经网络规划算法的关系【1 2 l 等。国 内外学者的积极研究极大地推进了支持向量机的快速发展，研究内容也非常广 泛，可将其中的主要内容分为两大部分：一是支持向量机模型及训练算法研究， 其中包括支持向量机训练算法研究、各种变形支持向量机模型研究等内容；二是 支持向量机的应用研究，支持向量机目前己经涉及很多应用领域，本章主要介绍 支持向量机在文本分类中的应用研究。在随后的几年内，有关s v m 的应用研究 得到了很多领域的学者的重视，在人脸检测、验证和识别、说话人语音识别、 文字手写体识别、图像处理及其它应用研究等方面取得了大量的研究成果。近 年来，s v m 在工程实践、化学化工等方面也取得了很多有益的应用研究成果， 其应用领域日趋广泛。 1 3 支持向量机在文本分类中存在的主要问题 支持向量机从被广泛重视到现在只有几年的时间，已经提出的很多关于 s v m 的训练算法，从训练时间和分类精度两种角度进行优化。其中还存在很多 尚未解决或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需 要，支持向量机在实际应用中、尤其在文本分类等类别和样本数目多、噪音多的 应用中存在的主要问题包括： ( 1 ) 对于需要求解二次规划问题的支持向量机模型，当样本数目较多时，其 训练速度较慢。尤其对于训练样本和支持向量数目多的分类问题，支持向量机的 分类速度过慢，这一点限制了支持向量机的应用，成为支持向量机方法进入大规 模实用化阶段的瓶颈。如何进一步改进和完善支持向量机模型及其训练算法，是 支持向量机研究中的热点问题。 ( 2 ) 支持向量机是针对两类分类问题提出的，用于多类分类必须将其推广。 对于类别数目较多的分类问题，目前仍缺乏有效的支持向量机多类分类方法。 ( 3 ) 支持向量机中核函数及参数的选择没有好的确定的方法，仍然凭经验寻 求。不同的核函数对应的支持向量集合有所不同，而支持向量的少量丢失都会引 起分类精度的下降，大规模文本分类中在减少样本数目时怎样保证不丢失支持向 量仍然是个难点。 山东师范大学硕士学位论文 1 4 本文组织结构 第一章简要介绍了国内外文本分类技术的研究现状和支持向量机在文本分类 中存在的主要问题。第二章论述了文本分类中的关键技术和文本表示模型。第三 章是本文的重点，对基于统计学习理论的支持向量机算法作了详细介绍，尤其深 入分析比较了支持向量机的各种变形算法，并结合并行技术提出了改进算法一 p c s m o k n n 算法，这是本文的创新点和主要贡献。第四章结合改进的算法设 计了一个针对大规模文本的分类系统，取得了较好的分类效果，在一定程度上解 决了基于s v m 的大规模文本分类的瓶颈问题。最后是总结和展望，并指出了近 一步的研究方向。 山东师范大学硕士学位论文 2 1 文本分类概述 第2 章文本分类系统的研究 文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过程。 2 0 世纪9 0 年代以前，占主导地位的文本分类方法一直是基于知识工程的分类方 法，即由专业人员手工进行分类。人工分类非常费时，效率过低。9 0 年代以来， 众多的统计方法和机器学习方法应用于自动文本分类。目前英文自动分类己经取 得了丰硕的成果，提出了多种成熟的分类方法，如最近邻分类、贝叶斯分类、神 经网络以及基于s v m ，v s m 、回归模型等方法。目前国内中文文本分类研究主要 集中在朴素贝叶斯( n a i v eb a y e s 简称n b ) 、v s m ，和s v m 等技术上。本章将 有重点地讨论各种文本分类技术。 2 2 文本表示 跟所有的机器学习一样，要想让计算机自动对文本进行分类，需要把一篇文 档文本表示成一个个特征，这种表示可以使文本的处理形式化，并且可以在文本 分类中取得较好的效果。作为语言的一种书面化或者电子化的文档也是开放的， 它的大小、结构、包含的语言元素和信息都是开放的，因此它的特征也是无限制 的。文本分类系统应该选择尽可能少而准确且与文档主题概念密切相关的文档特 征进行文档分类。 2 2 1 文本特征的选择和抽取 文本数据的两个难点就是特征的高维性与稀疏性。根据j o h np i e r r e 的理论 【1 3 】，用来表示文本的特征理论上应具有如下特点：数量上尽量少，出现频率适中， 含义尽量明确与其所属类别语义相关，此外冗余和噪音也要少。但就文本来说， 最方便采用的特征就是词或短语，它们往往具有如下一些特点；数量众多、出现 频率不等、噪音多、与其所属类别不一定相关。这就会对分类算法带来两个方面 的问题：其一，将会在训练与分类时间上带来很大的开销；其二，过多的特征往 往会导致人们常说的“维数灾难”问题。因此对文本数据进行维数压缩就变得极 为重要。 目前的特征维数压缩算法大体可以分为两类：特征选择1 1 4 1 ( f e a t u r es e l e c t i o n ) 与特征抽取( f e a t u r ee x t r a c t i o n ) i ”】。特征选择是根据某种准则从原始特征中选择 部分最有类别区分能力的特征，就是尽量保留有用特征，剔除无用特征；特征抽 山东师范大学硕士学位论文 取是依据某种原则构造从原始特征空间到低维空间的一个变换，从而将原始特征 空问所包含的分类信息转移到新的低维空间中来，便于分类器的构造。特征维数 压缩的好处有两点： ( 1 ) 提高分类精度，因为减少了无用特征对于分类结果的干扰。 ( 2 ) 提高分类效率，因为无用特征被剔除使得特征集得到压缩。 下面分析常见的几种特征维数压缩方法，这些方法的基本思想都是对每一个 特征即词条，计算它的某种统计的度量值，然后设定一个阈值t ，把度量值小于 t 的那些特征过滤掉，剩下的即认为是有效特征。它们相互间的不同之处主要在 于不同的特征重要性评价方法。 ( 1 ) 文档频率( d f ) 文档频率是最简单的特征抽取技术，不需要依赖类信息，所以是一种无监督 的特征选择方法。由于其相对于训练语料规模具有线性的计算复杂度，它能够很 容易被用于大规模语料统计。虽然计算量上比其他评估函数小得多，但d f 也有 缺点，因为稀有单词可能在某一类文本中并不稀有，而且包含着重要的标志信息。 而且在信息检索研究中通常却认为d f 值低的词条相对于d f 值高的词条具有较 多的信息量，不应该将它们完全移除。不同的应用将对d f 值的认识不同，应考 虑具体情况来使用该方法。 文献 1 7 】引进信息增益o g ) 因子对它进行了改进，提出词语在各个文档中的 分布比例对权重计算的影响，依靠训练数据集合的信息嫡和文档中词语的条件熵 之间的信息量的增益关系确定词语在文本分类中所能提供的信息量，定义为权重 的一个因子，得到方法t f i d f i g 的信息增益。改进了的方法不仅兼顾了词语在 文档集合中的分布情况，而且还考虑了词语在文档集合中的比例分布情况，使得 更好地表现了文本的内容。但是无论t f - i d f 方法还是t f - i d f i g 方法，特征选 择及权重计算都是基于频度这个因素来考虑，这样会“掩盖”些重要的特征， 在文本中，一般都存在中心语句，中心语句中的特征词语在表达文本内容时起到 关键性的作用，应该赋予最高的权重。 ( 2 ) 信息增益方法o g l 信息增益【1 6 1 ( i n f o r m a t i o ng a i n ，简记为i g ) 在机器学习领域被广泛使用。对于 词条t 和文档类别c ，用i g 考察文档类别c 中出现和不出现词条t 的文档频数来 衡量词条t 对于文档类别c 的信息增益。我们采用如下的定义式： mmm g a i n ( t ) = 一p ( c i ) i o g p ( c i ) + p ( t ) p ( c ii t ) l o g p ( c ii t ) + p ( _ ) p ( c ii t ) i o g p ( c ii ) i li i li = l 其中p ( c i ) 表示c i 类文档在语料中出现的概率，p ( 1 ) 表示语料中包含词条t 的文档 的概率，p ( c i l t ) 表示文档包含词条t 时属于c i 类的条件概率，p 国表示语料中不包 山东师范大学硕士学位论文 含词条t 的文档的概率，p ( c ；lt ) 表示文档不包含词条t 时属于c i 的条件概既率， m 表示类别数。i g 值越高表示该特征在训练集中的类别上分布越集中。i g 方法 提取i g 值较高的特征，其基本思想为分布越集中的特征越重要。 ( 3 ) 互信息( m i ) m i ( m u t u a li n f o r m a t i o n ) 互信息值，它通过计算特征和类别之间的相关性来完 成提取。计算公式为： i ( t ，c ) = l 。g 丽p r ( t a c ) 其中t 代表特征，c 代表类别，为方便计算，简化为： i ( t ，c ) = l o g 两丽a x 石n 面 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出 现而c 不出现的次数，c 为c 出现而t 不出现的次数。通过该公式就可以取得特 征与各类别间的互信息值。为了能取得特征在数据集上的整体评价有以下两种计 算方法： i 哪( t ) = p f ( c ；) i ( t ，c ， i 一( t ) = i ( t ，c ；) ) ( 4 ) z 2 统计量( c h d c h i 具有和m i 方法基本相似的思想，同样通过计算特征t 和类别c 间的依 赖程度来完成提取。但二者的计算细节不同，c h i 作了更多地考虑。有种看法认 为c h i 是一种正规化了的m i ，c h i 的计算公式如下： c i n ( t , c ) = 石面丽n 再x 面( a d 石- c 石b ) 2 丙i 瓦面 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出现而 c 未出现的次数，c 为c 出现而t 未出现的次数，d 为二者都未出现的次数。与 m i 相同，c h i 也有平均值和最大值两种方法来取得特征的整体评价： 7 m c 哪( t 1 = p r ( c i ) c h i ( t ，c i ) i = l 山东师范大学硕士学位论文 m c h i m x ( t ) = m a x c h i ( t ，c i ) ) i i c h i 方法的基本思想也是与类别关系越紧密的特征重要性越高。 2 2 2 特征项的权重计算 不同的特征项对文档的重要程度和区分度的影响是不同的，因此系统在对文 本进行形式化处理的时候，需要对特征项进行加权，下面只对最常用也是本文采 用的加权函数进行介绍。 t f - i d f 权重 t f 和i d f 参数是在文本检索中最常用的向量权重计算方法。它们刻画了特 征项表达文本内容属性的能力，t f 越大，此特征项在文档集中出现的范围越广， 说明它的重要程度越高：d f 越大，此特征项在文档中的的分布越集中，说明它 在区分该文档内容属性方面的能力越强。t f - i d f 权重计算公式如下： w ) ：；墅：些! 竺型! 呈i 兰! ! ”。砌【t f ( t ，d ) l o g ( n n i + a 】2 w ( t ，d ) 为特征t 在文本d 中的权重，其中t f ( t ，d ) 为特征t 在文本d 中的频数，n t 为文本集中含有t 的文本的数量，口为一个常量，l 0 9 2 ( n n t + a ) 为逆文本频率y 数，即n t 越大此值越小，4 i n i f ( t , d ) x l o g ( n n i + a 1 2 为归一化因子。为了消 减特征频率t f ( t ，d ) 的影响作用，可以得到公式： w ( t ，d ) ：j 垒! 竺曼墅：尘兰! 竺垒尘丝i ! ； ”。训【( 1 + l o g t 酏d ) ) l o g ( n n ；+ a 】2 i g 。( i ) = h ( d ) 一h ( dit e r m ( i ) ) 得到了改进方法t f i d f i g ： w i 。：毒堑丝丝坠竺些坠 “：爿k l o g ( n n 。+ o 0 1 ) i g 。】2 2 3 文本相似度计算模型 从本质上讲，文本是一个由众多字符构成的字符串，无法被学习算法直接用 于训练或分类。要将机器学习技术运用于文本分类问题，首先需要将作为训练和 山东师范大学硕士学位论文 分类的文档，转化为机器学习算法易于处理的向量形式，即，一般采用模型化的 方法表示信息空间，目前常用的文本表示模型有布尔模型( b o o l e a i l m o d e l ) ，概率 模型( p r o b a b i l i s t i em o d e l ，向量空间模型( v e c t o rs p a c em o d e l ) ，以及语言检索模型 和基于知识模型( k n o w l e d g e - b a s e dm o d e l ) 等。我们设计的系统中采用了向量空间 模型。 2 3 1 布尔逻辑模型 布尔逻辑模型【埔1 ( b o o l e a nl o g i c a lm o d e l ) 也称为完全匹配模型，是一种相对简 单的文本表示模型。在分类时，它以文档中是否包含关键词来作为取舍的标准。 利用布尔逻辑模型进行文本分类，就是给定一系列的具有二值逻辑的特征变量。 这些变量是从文档中抽取出来的，用来描述文档的特征。通过布尔操作符把表示 文档信息的特征变量构成布尔表达式，此即为一查询。基于布尔逻辑模型的文本 分类技术特点是实现容易、用户操作方便、易接受，而且查全率比较好。早期的 文献检索系统大都采用了布尔模型。布尔模型大体上可以分为两类：经典的布尔 模型与扩展的布尔模型。 经典的布尔模型建立于集合论与布尔代数的基础之上【1 9 1 ，主要应用于信息检 索中。在这种模型中，每篇文档表示成文档中出现的特征的集合，也可以表示为 特征空间上的一个向量，向量中每个分量权重为0 或者1 。经典布尔模型中查询 与文档的相关性只能是0 或者l ，满足查询q u e r y 中的所有逻辑表达式的文档被 判定相关，不满足的被判定为不相关。经典布尔模型通常只能用于信息检索中计 算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似 度，无法在更多的文本处理应用中使用，其查询结果非真即假，限制性过强会导 致漏判。 在经典布尔模型的基础上，研究人员重新定义了a n d 与0 r 操作符，使相关 性可以成为 o ，l 】之间的数。这便是通常所说的扩展布尔模型。到目前为止，学 者们已经提出了众多扩展布尔模型，其中p n o r m 模型【2 0 】具有相对更优秀的性 能。p - n o r m 模型定义如下： 。i i i l ( d ，q ) ：l 一障鱼垫z 业生生地业i 乃 、7 lq f + q ；+ + q ：l 其中，文档d = ( d 1 ，d 2 ，。d n ) ，用户查询q 一( q l ，q 2 ，q n ) ，d i 和q i 分别表示第i 个 特征词条对文档内容和查询内容的贡献程度，d i 和q l 在 o ，l 】上取值，此外 l p s0 0 ，实际中p 的取值由实验得出，范围一般在【2 ，5 】。 山东师范大学硕士学位论文 2 3 2 向量空间模型 向量空间模型v s m ( v e c t o rs p a c em o d e l ) 是由s a l t o n 教授最早在上1 9 6 8 年提 出的，它使用向量表示文本，把分类过程简化为空间向量的运算。向量空间模型 最早成功应用于信息检索领域，有较好的计算性和可操作性，v s m 一直以来都 是信息检索领域最为经典的计算模型。后来又在文本分类领域得到了广泛的运 用，并成功应用于著名的s m a r t 系统中。该模型现已成为最简便、最高效的文 本表示模型之一 向量空间模型的假设是：一份文档所属的类别仅与某些特定的词或词组在该 文档中出现的频数有关，而与这些单词或词组在该文档中出现的位置或顺序无 关，每篇文本和查询都包含一些用特征项表达的揭示其内容的独立属性，而每个 属性都可以看成是向量空间的一个维数，则文本和查询就可以表示为这些属性的 集合，从而忽略了文本的结构中段落、句子及词语之间的复杂关系。这样，文本 和查询可以分别用空间的一个向量表示，文本与查询之间的相似度可以用向量间 的距离来衡量。相似度的计算方法有很多种，常用的方法有内积、d i c e 系数、 j a c c a r d 系数和余弦系数 1 1 1 2 1 。最常用的是余弦系数法，即用两个向量之间的 夹角余弦来表示文本与查询问的相似度。夹角越小，说明文本和查询之间的相似 度越大。 向量空间的模型可以描述为： 假设文档集d - - - d i ， d i = s ( i d l 表示集合d 中元素的个数) ，特征项集t = 蚰， l t i = m 。定义特征项i 在文档d i 中的权重皑i 为： 肾鲁, l i s , 1 5 剐 向量空间模型把文档之间的相关度定义为它们之间的某种相似度。它认为一篇文 档与用户查询越相似，就认为此文档与用户查询越相关。v s m 把文档表示成高 维词空间的一个向量。向量中的每一维表示对应的词在文档中的权重。相似度的 度量采用夹角余弦，也就是通常所说的余弦距离。在此基础上，建立文档的向量 空间模型，把文档d i 表示为m 维的向量( 皑，一，) ，在m 维欧氏空间中 对于两个m 维向量d i = ( 如l ，) 和d j = ( w j i ，彩脚) 对应的夹角余弦 为； 山东师范大学硕士学位论文 一( d i , d j ) 一而旧 其中口是向量d i 和d j 之间的夹角，( d i ，d j ) 是向量d ；* 0 d j 的内积。那么，文档d i 和 d j 之间的相似度可以表示为： s i m ( d i , d j ) = c o s 8 = ”( d i d 阿j ) 向量d i * ad j 之间夹角的余弦值越大表明它们的相近度也就越大，反之则越小。 2 3 3 概率检索模型 在向量空间模型中，假设文档向量空间的基是相互正交的，没有考虑检索词 间的相互关系。并且控制向量操作的参数，如文档相似系数，并没有在模型中规 定，具有一定任意性。概率模型包括了检索词间的依赖关系以及主要参数，如检 索词权重计算，查询与文档相似度计算由模型自身决定。r o b e r t s o n 提出了基于 检索词和文档相关关系的概率检索模型，概率方法基于两个主要的参数，文档的 相关概率p r ( r e d 和不相关概率p r ( n o m e l ) ，以及两个系数a l 和a 2 。a 1 表示由于 检索不相关的文档造成的损失，a 2 表示错过检索相关文档所造成的损失。因为检 索不相关的文档产生的损失为a 。【1 一p r ( n o n r d ) ，错过相关文档所造成的损失为 a 2 1 一p r ( r e l ) 】，因此应该检索的文档应符合下式： a 2 + p r ( r e l ) sa 1 + p r ( n o n r d ) p r ( r e l )a 1 9 1 一p r ( r e l ) a 2 b 一- o g 翥器+ - o g 器 其中p r ( r e l ) 和为相关及不相关的先验概率，用p r ( x i l r e o 和p r ( x i l n o n - - e 1 ) 来表示。 对于文本分类来讲，由于具有学习过程，p r ( x i l r d ) 和p r ( x i l n o n r e l ) 可以通过学习获 得。 m 陶 = psoc 山东师范大学硕士学位论文 2 3 4 潜在语义索引模型 1 9 9 0 年，s c o t td e e r w e s t e r 提出了潜在语义索引( l a t e ns e m a n t i ci n d e x i n g ，l s i ) 的方法d l l ，并将它用在信息检索上，取得了很好的效果。潜在语义索引又称潜在 语义分析( l a t e ns e m a n t i c a n a l y s i s ，l s a ) ，是为了改善向量空间模型的效果而提 出的。潜在语义索引的基础是特征文本矩