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

武汉理工大学硕士学位论文 摘要 信息化的飞速发展使各种文本信息呈现爆炸式增长，这给人们的工作、学 习和生活提供了极大便利，但淹没于大量无用、重复信息之中的有用信息很难 通过人工的方法被全面准确地提取出来，文本分类作为处理和组织大量文本数 据的关键技术，可以在较大程度上解决信息杂乱现象的问题，方便用户准确地 定位所需的信息和分流信息，因此具有广泛的应用前景。 支持向量机是在统计学习理论的基础上发展而来的一种新的机器学习方 法，在求解小样本、非线性、高维空间等问题上，它己表现出很多优于己有方 法( 神经网络，遗传算法等) 的性能。目前支持向量机己成为机器学习界的研究熟 点，并在很多领域都得到了成功的应用，如人脸识别、文本自动分类、生物信 息处理等。本文对基于支持向量机的中文文本自动分类应用进行了研究，主要 工作如下： 1 首先对文本分类过程中的各项关键技术进行了研究，这其中主要包括中 文分词、特征选择、权重计算以及各种文本分类算法。特别对几种不同的特征 选择方法进行了研究，通过实验结果分析和比较了它们各自的优缺点。 2 分类器是文本分类的另一个重要环节，本文使用支持向量机作为分类 器，从机器学习的基本模型出发，对支持向量机的基本理论、工作原理以及各 种不同的实现算法进行了全面的阐述，特别对线性可分问题、近似线性可分问 题以及非线性问题等不同支持向量机模型的工作原理进行了介绍。比较了不同 核函数以及相关核参数对文本分类效果的影响。 3 针对支持向量机算法进行中文文本分类时参数选择困难的问题，本文使 用进化支持向量机算法g a - s v m ，结合遗传算法的智能搜索特性和支持向量机 的优良分类性能，对中文文本分类进行了研究。本文对g a s v m 算法的思想、 实现流程以及相关实现技术进行了介绍，实验表明该算法对于中文文本分类具 有良好的学习能力和分类效果。 4 结合各项中文文本分类技术，设计并实现了一个基于支持向量机的中文 文本自动分类系统。实验表明该系统具有较好的分类效果，有一定的实用价值。 关键词：文本分类，特征选择，参数选择，进化支持向量机 武汉理工大学硕士学位论文 a b s t r a c t a st h er a p i dd e v e l o p m e n to fi n f o r m a t i o ns o c i e t y , e s p e c i a l l yw i t hg l o b a l p o p u l a r i z a t i o n o ft h ew b r l dw i d ew e b t h ei n f o r m a t i o nc o n t i n u e st oi n c r e a s e e x p l o s i v e l y o no n eh a n d ，p e o p l et a k ea d v a n t a g e so ft h el a r g ea m o u n to fi n f o r m a t i o n ； 0 1 1t h eo t h e rh a n o , t h e r ei sa g r o w i n g n e e df o rt o o l st oh e l pp c o p l eb e t t e rt of i n du s e f u l i n f o r m a t i o ni nt h o s et r e m e n d o u sa n l o u n t so fi n f o r m a t i o nf o rt h er e a s o nt h a ti ti s d i f f i c u l tt og e tt h eu s e f u li n f o r m a t i o nf r o mt h er e d u n d a n tp a r t sm a n u a l l y 舡t h ek e y t e c h n o l o g y i n o r g a n i z i n g a n dp r o c e s s i n g l a r g em o u n to fd o c u m e n td a t a , t e x t c l a s s i f i c a t i o nc a l ls o l v et h ep r o b l e mo fi n f o r m a t i o nd i s o r d e rt oag r e a te x t e n t ，a n di s c o n v e n i e n tf o ru s e rt of i n dt h er e q u k e di n f o r m a t i o nq u i c k l y s ot e x tc l a s s i f i c a t i o nc a n b ea p p l i e db r o a d l yi nf u t u r e s u p p o r tv e c t o rm a c h i n e 侣v m ) i san e wm a c h i n el e a r n i n gm e t h o dd e v e l o p e di n r e c e n ty e a r sb a s e do ns t a t i s t i c a ll e a r n i n gt h e o r y c o m p a r e dw i t ht r a d i t i o n a lm e t h o d s s u c h 弱a r t i f i c i a ln e u r a ln e t w o r k s ( a n n ) a n dg e n e t i ca l g o r i t h m s ( g a ) ，i th a s s h o w nm a n yg o o dp e r f o r m a n c e si ns o l v i n gp r o b l e m so fs m a l ls a m p l e s ，n o n l i n e a ra n d h i g hd i m e n s i o n a lp a t t e r nr e c o g n i t i o n a tp r e s e n t , s v mb e c o m e st h en e wr e s e a r c h f o c u si nt h ef i e l do fm a c h i n el e a r n i n ga n db ea p p l i e ds u c c e s s f u l l yi nm a n yf i e l d ss u c h a sf a c er e c o g n i t i o n , t e x tc l a s s i f i c a t i o na n db i o l o g i c a li n f o r m a t i o np r o c e s s i n g c h i n e s e t e x tc l a s s i f i c a t i o nb a s e do rs v mi ss t u d i e di nt h i st h e s i s t h em a i nr e s e a r c hw o r k so f t h i st h e s i sa r el i s t e da sb e l o w ： 1 t h ek e yt e c h n o l o g i e so ft e x tc l a s s i f i c a t i o n s u c ha sc h i n e s ew o r d s e g m e n t a t i o n ，f e a t u r es e l e c t i o n , w e i g h tc o m p u t a t i o na n dd i f f e r e n tc l a s s i f i c a t i o n a l g o r i t h m sa r ea n a l y z e di nt h i st h e s i s f e a t u r es e l e c t i o ni so n eo ft h em o s ti m p o r t a n t s e c t i o n si nt e x tc l a s s i f i c a t i o n ，s oe m p h a s e sa r ep u to ni t c l a s s i f i c a t i o np e r f o r m a n c e w i t hd i f f e r e n tf e a t u r es e l e c t i o na r ec o m p a r e da n dd i s c u s s e di nt h i st h e s i s 2 c l a s s i f i e ri sh n p o r t a n ti nt e x tc l a s s i f i c a t i o na n ds v mi su s e da st h ec l a s s i f i e r i nt h i st h e s i s s v mi si n t r o d u c e dd e t a i l e d l yi nt h i st h e s i sf r o mt h eb a s i cm o d e lo f m a c h i n el e a r n i n gt oi t se l e m e n t a r yp r i n c i p l ea n dd i f f e r e n ta l g o r i t h m s 甜圮 c l a s s i f i c a t i o nr e s u l t sw i t hd i f f e r e n tk e r n e lf u n c t i o n sa r cc o m p a r e da n dd i s c u s s e d n 武汉理工大学硕士学位论文 3 c h o o s i n gp a r a m e t e r si sd i f f i c u l tw h e ns v m i su s e da sc l a s s i f i e ri nc h i n e s e t e x tc l a s s i f i c a t i o n s og a - s v ma l g o r i t h mi sp u tf o r w a r dt os o l v et h i sp r o b l e m ，w h i c h i su s e di nc h i n e s et e x tc l a s s i f i c a t i o n c o m b i n i n gw i t h t h ei n t e l l i g e n ts e a r c h c h a r a c t e r i s t i co fg e n e t i ca l g o r i t h m s ( g a ) a n dg o o dc l a s s i f i e dp e r f o r m a n c eo fs v mi n t h i st h e s i s t h ee l e m e n t a r yt h e o r y , w o r kf l o w sa n dt h ek e yt e c h n o l o g i e so fg a s v m a r ea l s oi n t r o d u c e di nt h i st h e s i s t h ee x p e r i m e n ts h o w st h a ti th a sag o o dl e a r n i n g a b i l i t ya n dc l a s s i f i e dp e r f o r m a n c e 4 ac h i n e s et e x tc l a s s i f i c a t i o ns y s t e mi sd e s i g n e da n di m p l e m e n t e db ys v m c l a s s i f i e r e x p e r i m e n tr e s u l t ss h o wt h a ti th a sag o o dc l a s s i f i e dp e r f o r m a n c ea n dc a n a p p l i e dp r a c t i c a l l y k e yw o r d s ：t e x tc l 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 ，p a r a m e t e rs e l e c t i o n , g a - s v m i n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取 导的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汲理工大学或其它教育机构的学位或证书而使用过的材斟。与我一 同工作的同志对本研究所傲的任何贡献均已在论文中作了明确的说 明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留、送交论文的复印件，允许论文被查阅和借阿；学校可 以公布论文的全鄢或部分内容，, - i 以采用影印、缩印或其他复制手段 保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：丝导师签名：牲日期：碰立丝? 矿 武汉理工大学硕士学位论文 第1 章绪论 1 1 论文研究的背景和意义 随着i n t e r n e t 的普及，信息技术的发展一日千里，网络上的信息正以几何级 数的方式不断增长，特别是以网页、电子邮件、数据库、聊天室和数字图书馆 等为代表的电子文本信息尤为如此。面对如此巨大的文本信息，如何有效地组 织和管理这些信息，并快速、准确、全面地从中找到用户所需的信息是摆在计 算机工作者面前的一大挑战，基于人工智能和信息检索相结合的文本自动分类 技术应运而生。近二十多年来计算机软、硬件技术的发展和自然语言处理、人 工智能等领域的研究进展为文本自动分类提供了技术条件和理论基础。文本自 动分类作为组织和整理文本数据的关键技术，可以在较大程度上解决信息杂乱 现象的问题，方便用户准确地定位所需的信息和分流信息。 传统的文本分类工作是由特定领域的专家人工完成的，这种人工分类方法 存在着许多弊端：一是耗费大量的人力，物力和精力。二是存在分类结果一致 性不高的问题。特别是随着文本信息量的增加，人工方法己经很难满足分类的 需求，因此利用计算机对文本进行自动分类的自动文本分类日益受到重视。自 动文本分类是对大量用自然语言写成的文本按照预先定义的主题类别进行自动 分类，它是人工智能技术和信息获取技术相结合的研究领域，是进行基于内容 的自动信息管理的核心技术。文本自动分类技术现己广泛应用于以下几个方面： ( 1 ) 信息检索 信息检索系统必须操纵大量的文本信息，因此将这些文本信息按主题层次 归类组织可以极大地简化对信息的检索。通过对文本集进行自动化文本分类可 以对文本进行有序的组织，把相关主题的文本组织在一起，从而提高信息检索 的查准率【1 1 。 ( 2 ) 信息过滤 信息技术的发展是一个双刃剑，在给入们带来大量有益信息的同时，也带 来了大量无用信息，甚至是一些有害的信息，如黄色、淫秽、反动信息等。信 息过滤技术可以通过文本分类技术来解决这些问题，信息过滤本质是一个两类 分类问题，既可以用来将用户反感的信息滤掉，也可以用来将用户感兴趣的信 武汉理工大学硕士学位论文 息过滤出来，主动地推送给用户，方便了用户快速准确地获取信息。垃圾邮件 的过滤就是其中一个很好的应用。 ( 3 ) 文档组织 一般来说，同文档组织相关的任何事务，都可以用自动文本分类技术来处 理。例如，就报社的编辑而言，在对报纸进行排版之前，必须将有关新闻稿件 进行必要的分类，如分成时事、财经、体育、文艺等几大类以刊登到合适的栏 目中去。虽然目前大多数报社仍然依赖人工来完成这些广告分类工作，但是对 于那些每天需要处理大量广告的大型新闻单位，自动广告分类系统将有助于大 大提高它们的工作效率。 ( 4 ) 数字图书馆 图书馆的数字化建设正在如火如茶的进行之中，图书期刊全文数字化的比 重越来越大，因此使用自动文本分类技术，可以对这些数字期刊进行有效的分 类，从而便于图书的管理。 1 2 国内外研究现状 1 2 1 文本分类研究现状 文本分类研究开始于2 0 世纪5 0 年代末，美国i b m 公司的h e l u h n 在这一 领域进行了开创性的研究【2 l ，他提出了词频统计思想，后来被应用在文本分类领 域。6 0 年代初，m a r o n 在利用概率模型进行文本分类方面做出了开创性的研究 工作【3 j 。s a l t o n 等人在7 0 年代初提出了向量空间模型，由于该模型在良好的统 计学方法基础上简明地实现了对文本特性的抽象描述，从而成为文本分类处理 的一种经典模 4 1 。其后许多学者在这一领域进行了卓有成效的研究。 文本自动分类主要经历了四个发展阶段： 第一阶段( 1 9 5 8 - 1 9 6 4 ) ：研究文本自动分类的可能性； 第二阶段( 1 9 6 5 1 9 7 4 ) ：进入文本自动分类的实验性阶段； 第三阶段( 1 9 7 5 1 9 9 8 ) ：文本自动分类的实用性阶段； 第四阶段( 1 9 9 0 至今) ：因特网文本自动分类研究阶段。 在2 0 世纪8 0 年代末以前，基于知识工程的方法一直在文本分类方法中占 主导地位。这种方法是由专业人员手工编写分类规则来表达领域专家所拥有的 知识，将文档分到某个给定的类别体系中。这种方法需要有领域专家，还需要 武汉理工大学硕士学位论文 知识工程师手工编制大量的推理规则。其最典型的应用是卡内基集团为路透社 开发的c o n s t r u e 系统。9 0 年代以来，随着模式识别、机器学习、统计学习、数 据挖掘等理论研究的发展，新型机器学习方法的不断涌现，基于机器学习的分 类技术开始取代基于知识工程的方法，成为文本分类的主流技术( 5 1 。 国内文本自动分类研究起步较晚，始于2 0 世纪8 0 年代初期。1 9 8 1 年侯汉 清对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分 类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。 此后，有越来越多的人借鉴国外的一些研究成果，结合中文的特点进行中文文 本自动分类的研究。中科院计算所的李晓黎、史忠植等人应用概念推理网进行 文本分类 6 1 。复旦大学的周水庚等人用了n g r a m 方法对中文文本进行分类尝试， 从文档中提取n g r a m 属性，然后用o n 方法判别文本类别，摆脱了对词典和切 词处理的依赖，实现文本分类的领域无关性和时间无关性阴。刁力力、石纯一等 用b o o s t i n g 来组合决策树( s t u m p s ) 的方法进行文本分类【8 l 。卜东波从信息粒度的 角度来剖析聚类和分类技术，试图使用信息粒度原理的框架来统一聚类和分类 【9 1 。庞剑峰等应用向量空间模型进行了中文文本分类实验，并同时对文本分类所 涉及的关键性技术，例如特征提取、不同机器学习方法等进行了研究和探讨， 给出了评估方法和实验结果。之后他又验证了在文本分类系统中应用反馈方法 的可行性，给出了结合反馈方法的文本分类算法【l o l 。 1 ，2 2 支持向量机研究现状 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s e t ) 是由v a p n i k 等人提出的有限样 本下的统计学习理论i u l ，针对小样本建立了一套新的体系，在该体系中统计推 理规则不仅考虑了对渐进性能的要求，而且力求在现有样本下达到最优结果。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是s l t 的一种成功实现，它建立在s l t 的v c 维理论和结构风险最小化原理基础上，根据有限样本信息在模型复杂性( 对 特定样本的学习精度) 和学习能力( 无错误地识别样本的能力) 之间寻求一种折 中，以期达到最佳的推广性能。1 9 9 5 年，v a p n i k 在”t h en a t u r eo fs t a t i s t i c a l l e a r n i n g t h e o r y 一一书中提出支持向量机的概念，并在“s u p p o r t v e c t o r n e t w o r k s ” 一文中进行了详细的介绍”2 1 。从那以后，关于支持向量机方面的文章如雨后春 笋，逐渐成为国际上机器学习领域的研究热点，吸引了国内外众多知名的专家 学者。目前对支持向量机的研究主要包括以下两个方面： 3 武汉理工大学硕士学位论文 ( 1 ) 支持向量机算法研究 对学习算法的研究和改进是目前支持向量机研究的主要内容，在过去的十 多年里，出现了很多支持向量机算法的改进算法，从算法实现中优化理论的改 进、核函数的构造到算法参数的选择等等。在核函数的构造方面，吴涛提出了 采用插值构造核函数的方法【1 3 1 ；d a n i e l 和o a b d e l e 提出了基于小波的核函数构造 方、法【1 4 l ；a t a r i 和w u 设计了一种算法，他们通过对核函数的黎曼几何分析，提 出利用实验数据逐步修正已有的核函数，使之能更好地与实际问题相吻合m i ； c a u w e n b e r g h s 和p o g g i o 研究了基于支持向量机的增量和减量学习问题【1 6 j ；d i e m 和c a u w e n b e r g h s 提出了一个精确增量学习和自适应支持向量机分类器的框架； o p p e r 和u r b a n c z i k 对支持向量机学习带噪声的多项式规则进行了研刭1 7 1 ，在核 函数阶数足够高或者为超越函数时，渐近线和学习曲线由目标规则决定而不是 核函数，在这种情况下研究t i j , i 练误差核推广误差的收敛性；b o r d e s 等提出一 种在线支持向量机算法l a s v m 1 s l ，通过对样本的主动选择提高了学习速度； s e r i f i n i 等研究了基于梯度方法的支持向量机分解算法中起作用集的选择问题 【1 9 l ；j o a c h i m s 对大规模支持向量机算法的实现进行了研究唧l 。此外，还有很多 学者对支持向量机的算法进行了研究，这里就不一一列举了。 ( 2 ) 支持向量机应用研究 支持向量机算法的优良性能使得它在短短十几年时间内得到了广泛的应 用，从最初的线性分类，到各种模式分类问题，以及在回归分析方面都有出色 的表现。在文本自动分类【2 l j 、图像分类( 2 2 1 、d n a 和蛋白质序列检测【2 3 1 等众多领 域都能找到支持向量机算法的影子。 在这些应用中，最为著名的应该是贝尔实验室对美国邮政手写数字库进行 的实验。这是一个可识别性差的数据库，人工识别平均错误率是2 5 ，用决策 树方法识别错误率是1 6 2 ，两层神经网络中错误率最小的是5 9 ，专门针对 该特定问题设计的五层神经网络错误率为5 1 ( 其中利用了大量的先验知识) ， 而用三种s v m 方法( 采用3 种核函数) 得到的错误率分别是4 0 ，4 1 和4 2 ， 且其中直接采用了1 6 x 1 6 的字符点阵作为s v m 的输入，并没有进行专门的特征 提取。通过这个例子s v m 的分类性能可见一斑。 4 武汉理工大学硕士学位论文 1 ，3 本文研究内容与组织结构 1 3 1 研究内容 本文主要针对基于支持向量机技术的中文文本分类进行了研究。讨论了中 文文本分类应用中的主要实现技术，包括中文分词、特征选择、各种文本分类 方法和对分类效果进行评价的各种指标。通过实验我们比较了各种特征选择方 法的分类效果并对其作了分析。针对以径向基作为核函数的支持向量机算法中 参数选择的难题，包括惩罚因子c 和核参数y ，本文研究了g a s v m 算法，结 合遗传算法的搜索特性和支持向量分类器的优良性能，旨在进一步提高其在文 本分类中的学习能力和分类能力。通过实验表明同传统的选参方法进行比较， 该方法具有相同或较高的推广能力和分类性能。最后基于s v m 算法，实现了中 文文本分类系统，该系统具有较好的分类和预测效果。 1 3 2 组织结构 本文共分七章，文章结构及各章主要内容组织如下： 第1 章序论，介绍了中文文本分类的研究背景及研究意义，分析了国内外 文本分类以及支持向量机的研究现状，最后给出了本文的主要研究内容和整体 组织结构。 第2 章中文文本分类的相关技术，介绍了中文文本分类的相关实现技术， 这其中包括中文分词、特征选取、权重计算以及文本分类方法等关键技术，最 后给出了文本分类效果的相关评价指标，为后面章节的讨论作概念和技术上的 准备。 第3 章支持向量机理论，介绍了支持向量机理论所蕴含的统计学习思想、 理论模型以及一些精典的实现算法，比较了几种经典支持向量机算法( 不同核函 数1 在文本分类中的分类结果。 第4 章基于g a - s v m 算法的文本分类，介绍了g a - s v m 算法的思想、步骤， 以及相关实现技术。 第5 章文本分类系统的设计与实现，设计并实现了一个基于支持向量机的 中文文本分类系统。对系统结构和主要功能进行了说明。 第6 章总结与展望。对全文的研究工作做出了简要总结，并展望了今后的 5 武汉理工大学硕士学位论文 研究工作。 6 武汉理工大学硕士学位论文 第2 章中文文本分类的相关技术 2 1 文本分类的形式化描述 文本分类( t e x tc l a s s i f i c a t i o n ，t c ) 是为每个元组对( d j , c t ) e d x c 赋以一个布 尔值的过程，其中d 是文本域，c c 】，e i c l 是预定义的类别集。若文本d ；被 分到q 类，那么( d ，q ) 就为1 ，否则为0 。进而，分类任务可以形式化地表示为 寻求未知的目标函数h ：d c 一亿o 1 2 4 1 ，h 说明待分类文档该如何被分类，该 函数被称为分类器( c l a s s i f i e r ) ，有时也称为分类规则( 砌把) 、分类假设 ( h y p o t h e s i s ) 或分类模型( m o d e l ) 。函数h 与实际的分类模型_ i l ：d x c 一伪0 应 该尽可能一致，这种一致性可以通过具体的分类模型评估指标来确定，我们将 在2 5 节详细讨论这一问题。 2 2 中文分词 在多数的西方语言体系中，句子中各个词汇之间有固定的空格作为分隔， 计算机处理时可以非常容易地识别出每个单词。而在汉语体系中，书写以句子 为单位，句间用标点隔开，句内字词则是连续排列的，之间没有任何分隔。因 此，如果要对文本信息进行识别、分类处理，就需要对其进行分词处理。中文 分词是中文文本分类的基础，分词不当必会影响后续的工作，因此中文分词在 中文文本分类的工作中占有重要的地位。 现有的中文分词方法从应用的角度基本可以分为如下几种：基于词典的方 法，基于语法和规则的方法，基于统计的方法，或者上述几种方法相结合的方 法。 ( 1 ) 基于词典的方法 基于词典分词是一种按照一定策略将待分析汉字串与分词词典中的词条进 行匹配的分词方法。该方法按扫描方向可分为正向扫描、反向扫描、双向扫描 三种；按匹配原则又可分为最大匹配和最小匹配，这两种匹配按增字或减字又 可将其分为两种类型。 ( 2 ) 基于语法和规则的方法 基于语法和规则的分词法的基本思想就是在分词的同时进行句法、语义分 7 武汉理工大学硕士学位论文 析，它模拟人对句子的理解过程，利用句法信息和语义信息来进行词性标注， 以解决分词歧义现象。 ( 3 ) 基于统计的方法 基于统计的方法是当前研究的主流，n - g r a m 模型是一种常用的统计语言模 型。它基于如下假设：假定在词串中，每一个词的出现概率只与前面n 一1 个 词有关，而与其它的任何词都无关。它反映了连续个词之间的相关信息。 考虑字符串w - 嵋，w 2 ，m 为文本中顺序排列的撵个词，根据条件概率的定 义和最大似然准则，有： p ( ) 一p ( m 屹) 一p ( w 1 ) p ( m ) p ( w 1 ) e ( w , w , 一+ l 嵋。) 。p ( 嵋w 一) ( 2 - 1 ) 其中，p ( 嵋w f + ，心一。) 表示在给定历史信息的条件m + 。m 。下，选取 词m 的概率。这就是n g r a m 模型，它实际上是一个n 一1 阶的马尔可夫过程。 n g r a m 模型中，n 值越大约束力越强，但由于计算机容量和速度的限制及数据 的稀疏，很难进行大n 值的统计。在实际应用中，往往只考虑几个历史信息， 形成了如= 元( b i g r a m ) 模型和三元0 r i 乎a m ) 模型等模型。可以看出n - g r a m 模型需 要在有大量训练语料保证的前提下，通过统计得到的大量数据来估计模型的参 数。 2 3 特征选择 目前主流的文档表示方法是向量空间模型。向量空间模型中，一篇文档表 示为特征空间中的一个向量，这个向量也称为文档向量。文档向量中每一维对 应于文档中的一个特征，它的权值为该向量维对应的特征在文档库中的权值， 一般采用t f i d f 方法计算。若使用词语作为文本特征，那么文本的特征向量会 达到上万维甚至数十万维的大小，在这样一个高维空间上对文本分类所使用的 学习算法进行训练，显得既不经济又无必要，因此必须通过特征选择来进行维 数压缩。 特征选择经常会使用特征独立性假设来简化特征选择，以达到计算时间和 计算质量的折衷。因此，目前在对文本的特征空间所采取的特征选择算法一般 8 武汉理工大学硕士学位论文 是构造一个评价函数，对特征集中的每个特征进行独立的评估。这样每个特征 都获得一个评估分，然后对所有的特征按照其评估分的大小进行排序，选取预 定数目的最佳特征作为结果的特征子集。 在文本的特征选择中，各种评估函数包括：文档频数( d o c u m e n tf r e q u e n c y ) ， 信息增益( i n f o r m a t i o ng a i n ) ，期望交叉熵( e x p e c t e dc r o s se n t r o p y ) ，互信息 ( m u r a li n f o r m a t i o n ) ，z 2 统计法和f i s h e r 判别式等，以下分别对它们的效果和 原因进行分析： ( 1 ) 文档频数( d f ，d o c u m e n tf r e q u e n c y ) 泖阶勰燃 p z ， 文档频数是最简单的评估函数，其值为训练集合中出现此词的文本数占总 的文本数的概率。d f 评估函数的理论假设是：稀有单词要么不含有用信息，要 么太少而不足以对分类产生影响；要么是噪音，所以可以删去。虽然它在计算 量上比其它的评估函数小得多，但是在实际运用中它的效果却是出奇地好。需 要注意的是，在特征选择之前必须将停用词去掉，仅保留与主题相关的词汇。 d f 评估函数也存在缺点，比如稀有单词可能在某一类文本中并不稀有，而且包 含着重要的判断信息。在实际运用中一般并不直接使用d f 评估函数，常把它作 为评判其它评估函数的标准。 ( 2 ) 信息增益( ，g ，i n f o r m a t i o ng a i n ) i g 阶醐i r v ) l o g 等 + 厕；粥厕1 0 8 1 e ( c , 万w ) 一 其中p ( c l w ) 表示文本中出现词时，文本属于类别c 的概率，同样 p ( c w ) 表示文中不出现词w 时文本属于类别c 的概率；p ( g ) 表示类别出现的 概率；p ( ) 表示词在整个文本劫1 j 练集中出现的概率。 信息增益是一种在机器学习领域应用较为广泛的特征选择方法。它从信息 论角度出发，用各个特征的取值情况来划分学习样本空间，然后根据所获信息 增益的多寡来选择相应的特征。 ( 3 ) 期望交叉熵( e c e ，e x p e c t e dc r o s se n t r o p y ) 脚一删) 艺p ( c ；w ) l o g 笔磬( 2 - 4 ) 9 武汉理工大学硕士学位论文 期望交叉熵没有考虑单词未出现的情况，如果词条和类别强相关，p ( c w ) 就大，若p ( e ) 又很小的话，则说明该词条对分类的影响大，其对应的函数值就 大，就有可能被选中作为特征值。交叉熵反映了文本类别的概率分布和出现了 某种特定词的条件下文本类别的概率分布之间的距离。词的交叉熵越大，那么 它对文本类别分布的影响也就越大。 ( 4 ) 互信息( m i ，m u m a li n f o r m a t i o n ) m i - 摹删l o g 帮( 2 - 5 ) 词条和类别的互信息体现了词条与类别的相关程度，是一种广泛用于建立 词关联统计模型的标准。如果词形在某个类别e 中出现的概率高，而在其它类 别中出现的概率低，则形将获得较高的互信息，也就有可能被选取为类别e 的 特征。 ( 5 ) z 2 统计法( c h ，) c h i ) t 罗p ( c f 耽2 ，e ) 。军聪，而嚣 p 6 其中a 表示词在类别e 中出现的频度；口表示词形在除c 以外的其它类 别中出现的频度，c 表示除以外的其它词在类别e 中出现的频度；d 表示除 矿外的其它词在除e 以外的其它类别中出现的频数。 该方法类似于互信息加瞵1 ，词的z 2 ( 伽) 统计值比较了词对一个类别的贡 献和对其余类别的贡献，以及词和其它词对分类的影响。当词彤与类别e 互相 独立时，, 4 1 9 一b c - 0 ，z 2 ( c h i ) 的值为0 ；若仰一b c 0 ，说明词彬与类别c j 正相关，即该词出现说明某个类剐很可能出现；反之，若a d b cc0 ，说明词 矿与类别e 负相关，即该词出现说明某个类别很可能不出现。在进行特征选择 时，选择z 2 ( c h i ) 统计值高，同时满足a d b c ，0 的词w 作为特征值。 ( 6 ) f i s h e r 判别式 借用f i s h e r 鉴别分析的思想，我们希望所选择的特征使得f i s h e r 判别式的 值达到最大。f i s h e r 判别式是一种基于统计的方法，表示某一特征在类间分布 和类内分布之比： 武汉理工大学硕士学位论文 这里， 黝盯( 叻。善。生! 竺坠：兰! 坠：堕( 2 - 7 ) 。南( 。o ( d ，w ) 一( c ，呦2 ) 鹏w ) t 南。嘏r ) x ( d ，w ) 一n ( d ，w ) n ( d ) ( 2 8 ) ( 2 9 ) 上面，n ( d ，叻和”p ) 分别表示特征w 在文档d 中的频数和文档d 中总的特征频 数。 综合各种特征选择方法可以发现，信息增益方法的不足之处在于它考虑了 词未发生的情况体现在式中的p 而； 厕l o g 马系竿部分。在类分布和特 征值分布高度不平衡的情况下，绝大多数类都是负类，绝大多数特征值都是“不 出现”的，即p o 矿) 芑p ( ) ，此时得到信息增益大的特征，主要因为信息增益公 式中后一部分( 代表单词不出现情况) 计算结果大，而非前一部分( 代表单词出 现情况) 计算结果大，信息增益的效果就会大大降低了。恰恰相反的是期望交叉 熵没有考虑单词未出现的情况，在大多数的实验结果中，不管在哪种数据集中， 期望交叉熵的特征选择都要优于信息增益。互信息( m o 与期望交叉熵本质的不 同在于它没有考虑单词发生的频度，这是它的弱点，会导致互信息评估函数不 选择高频的有用单词丽有可能选择稀有词作为文本的最佳特征。 2 4 权重计算 不同的特征项对于文档的重要程度和区分度是不同的，因此系统在对文本 进行形式化处理的时候，需要对特征项进行赋权，下面对常用的几类权重计算 方法进行详细介绍。 ( 1 ) 布尔权重( b i n a r yw e i g h t i n g ) 布尔权重也叫二值权重或二元权重( b i n a r yw e i g h t i n g ) ，是最简单的权重计 算方法，如公式( 2 1 0 ) 所示。在这种方法中，特征权重只有“0 ”、“1 ”两个值， 描述很粗糙，丢失了文本中大量的信息。布尔权重主要用在特征只有二个状态 武汉理工大学硕士学位论文 的分类器中，例如：决策树分类器，概率分类器等。用布尔权重表示的特征向 量被称为布尔向量( b o o l e a n v e c t o r ) 或二元向量( b i n a r y v e c t o r ) 。 - 如果特征气嚣柳岘 但) 文档频率 用文档频度作为权重是最直观的方法，如公式( 2 1 1 ) 所示。这种方法基于的 思想是：特征在文本中出现次数越多，它就越重要。文档频次的计算复杂度较 低，能够适用于任何语料，因此是特征赋权的常用方法。 h k d 0 ( 2 - 1 1 ) 0 ) t f ，i d f 型权重 z f z d f 是在文本处理领域使用最广泛的权重计算方法，它最初用在信息 检索中。丁f f 型权重的基本思想是：特征项在文本中出现次数越多越重要； 特征项在越多的文本中出现越不重要。z f 和i d f 正是这种思想的体现，! f 越 大，此特征项在文档集中出现的范围越广，说明它的重要程度越高；i d f 越大， 此特征项在文档中的分布越集中，说明它在区分该文档内容属性方面的能力越 强。t f * i d f 型权重计算公式如公式( 2 1 2 ) 所示： ( f ，动。愿r f 蓊( t , d ) 萧xl o g ( 菰n n , 雨+ 0 0 1 丽) ( 2 - 1 2 ) 其中，w ( t ，孑) 为词f 在文本孑中的权重，而矿( f ，孑) 为词f 在文本孑中的词频， 为训练文本的总数，札为训练文本集中出现t 的文本数，分母为归一化因子。 ( 4 ) 基于熵的权重( e n t r o p y w e i g h t i n g ) 熵权重来源于信息论，如公式( 2 1 3 ) 所示。 叫。蛾“叭 t + 高雅k g 鼽去辩b s 剀表示讹懈如果特征均匀地分布在文 本中，则熵值为1 ，否则为0 。使用时应该进行规格化。 武汉理工大学硕士学位论文 2 5 文本分类方法 文本分类的方法大部分来自于模式分类，基本上可以分为三大类。一种是 基于统计的方法，如贝叶斯、k n n 、类中心向量、回归模型、支持向量机、最 大嫡模型等方法；另一种是基于连接的方法，即入工神经网络；还有一种是基 于规则的方法，如决策树、关联规则等。这里主要对基于统计的分类方法进行 介绍。 2 5 1 贝叶斯方法 贝叶斯分类方法是一种简单而又非常有效的分类方法1 2 6 , z t i 。它的一个前提假 设是：在给定的文档类语境下，文档属性是相互独立的。假设嚷为一任意文档， 它属于文档类c c 1 ，c ：q 中的某一类c j 。根据贝叶斯分类方法有： 他一p ( c j 矿) e ( d , i c a 聪) 再p ( c ，) p ( 2 1 4 ) ( 2 一t s ) 对文档d ；进行分类，就是按( 公式2 - 1 6 ) 计算所有文档类在给定吐情况下的概 率，概率值最大的那个类就是吐所在的类，即： t 或。，矿p ( c ，i 吐) - 珊野 p ( c f i 唾) )( 2 - 1 6 ) 由公式( 2 1 4 ) 一( 2 - 1 6 ) 可知，对于给定分类背景和测试文档，用贝叶斯方法分 类的关键就是计算，( c ，) 和p 旺i f j ) 计算c j ) 和p ( ti f j ) 的过程就是建立分类 模型( 或者说学习) 的过程。 2 5 2k n n 方法 叮n 方法即k - n e a r e s tn e i g h b o r 分类方法，这是一种稳定而有效的文本分类 方法。采用k n n 方法进行文档分类的过程如下：对于某一给定的测试文档d ， 在训练文档集中，通过相似度找到与之最相似的k 个训练文档。在此基础上，给 每一个文档类打分，分值为k 个训练文档中属于该类的文档与测试文档之间的相 似度之和。也就是说，如果在这k 个文档中，有多个文档同属于一个类，则该类 的分值为这些文档与测试文档之自j 的相似度之和。对这k 个文档所属类的分值统 计完毕后，即按分值进行排序。还应当选定一个阀值，只有分值超过阀值的类 武汉理工大学硕士学位论文 才予以考虑。测试文档属于超过阀值的所有类。形式化表示为l 篮】： 黝即“，q ) 。主s 锄q ，d ，抄( d ，q ) 一岛( 2 - 1 7 ) 其中， y ，q ) 。t od r 隹c l ( 2 d 8 ) 岛为阀值，s i m ( d ，d ，) 为文档d 和d ，的相似度，s c o r e ( d ，q ) 为测试文档d 属于q 类 的分值。 对于某一特定类来说，6 i 是一个有待优化的值。一般，觑可以通过一个验证 文档集来进行调整。验证文档集是训练文档集的一部分。根据( 公式2 - 1 8 ) 的结果， 可以确定测试文档的类别。很显然，对于每一个测试文档，必须求解它和训练 文档库中所有文档的相似度。因此，k n n 方法的时间复杂度为o ( i o l n , ) 。其中， i d i 和啊分别为训练文档总数和测试文档总数。 2 5 3 类中心向量方法 类中心向量方法是一种基于向量空间模型的方法。在分类器的训练阶段，