基于支持向量机的文本分类算法的研究与实现

1、学号：2009030114哈尔滨师范大学学士学位论文题目基于支持向量机的文本分类算法研究与实现学生李慧颖指导教师李红宇副教授年级2009级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程哈尔滨师范大学学士学位论文开题报告论文题目：基于支持向量机的文本分类算法研究与实现学生姓名：李慧颖指导教师：李红宇级：2009级业：计算机科学与技术2013年3月1日课题来源:指导教师指导选题课题研究的目的和意义：随着计算机技术的飞速发展以及Internet的普及与应用，互联网上的电子文档信息急剧增加。如何从大量的信息中快速、准确地检索到所需的信息资料，是人们普遍关心的问题，也是计算机工作者急需

2、解决的问题。面对如此复杂的问题，分类技术在信息检索、信息过滤、数据挖掘等方面起着至关重要的作用。而网上的大部分信息以文本的形式存在，于是文本自动分类技术就成为网上信息检索和信息过滤的关键。另外，文本分类可以应用到垃圾邮件的判定(spamornotspam),类别spam,not-spam；新闻出版按照栏目分类，类别政治，体育，军事.;词性标注，类别名词，动词，形容词)；词义排歧，类别词义1,词义2.)，文本检索，文本过滤以及主题发现与跟踪等。而从Springer全文电子期刊与IEL(IEE,IEEE)数据库中，可以看到最近的期刊与国际会议论文，有大量的关于文本分类的文章，说明随着大量的网上的电

3、子信息，文本分类仍是人们研究的热点。面对网上的海量信息，传统的做法是对网上信息进行人工分类，并加以组织和整理，为人们提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做法存在着许多弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一致性不高的问题。这就要求我们探索计算机自动进行文本分类的有效方法，使得分类的正确率提高。只有这样才能保证检索的查全率和准确率都得到提高。文本自动分类是人工智能技术和信息检索技术相结合的研究领域，是进行基于内容的自动信息管理的核心技术。文本分类是指根据一些已经分配好类标签(这些类标签预先定义好)的训练文档集合，来对新文档分配类标签，其目的就是对文本集进行合

4、理处理和组织，使得这些文本能够按照类别区分开来。作为知识的组织工具，它为信息检索提供了更高效的搜索策略和更准确的查询结果，其中，高效性在于用户可以首先确定查询的可能类别，以减小需进一步匹配的文本数量：有效性在于相似的文本很可能与相同的查询相关，这样使得检索的查全率和准确率都得到了提高。国内外同类课题研究现状及发展趋势：1.国外文本自动分类主要经历了四个发展阶段：第一阶段(19581964):研究文本自动分类的可能性；第二阶段(19651974):进入文本自动分类的实验性阶段；第三阶段(19751998):文本自动分类的实用性阶段；第四阶段(1990至今)：因特网文本自动分类研究阶段。在20世纪

5、80年代术以前，基于知识工程的方法一直在文本分类方法中占主导地位。这种方法是由专业人员手工编写分类规则来表达领域专家所拥有的知识，将文档分到某个给定的类别体系中。这种方法需要有领域专家，还需要知识工程师手工编制大量的推理规则。其最典型的应用是卡内基集团为路透社开发的Construe系统。90年代以来，随着模式识别、机器学习、统计学习、数据挖掘等理论研究的发展，新型机器学习方法的不断涌现，基于机器学习的分类技术开始取代基于知识工程的方法，成为文本分类的主流技术。2国内文本自动分类研究起步较晚，始于20世纪80年代初期。1981年侯汉清对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管

6、理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，有越来越多的人借鉴国外的一些研究成果，结合中文的特点进行中文文本自动分类的研究。中科院计算所的李晓黎、史忠植等人应用概念推理网进行文本分类。复旦大学的周水庚等人用了N-gram方法对中文文本进行分类尝试，从文档中提取N-gram属性，然后用ON方法判别文本类别，摆脱了对词典和切词处理的依赖，实现文本分类的领域无关性和时间无关性。刁力力、石纯一等用Boosting来组合决策树(Stllnlps)的方法进行文本分类。卜东波从信息粒度的角度来剖析聚类和分类技术，试图使用信息粒度原理的框架来统一聚类和分类。庞剑峰等应用向量空

7、问模型进行了中文文本分类实验，并同时对文本分类所涉及的关键性技术，例如特征提取，不同机器学习方法等进行了研究和探讨，给出了评估方法和实验结果。之后他又验证了在文本分类系统中应用反馈方法的可行性，给出了结合反馈方法的文本分类算法。课题研究的主要内容和方法，研究过程中的主要问题和解决办法：本文在研究文本分类和支持向量机理论的基础上，针对支持向量机在样本数目较多时其训练速度较慢的问题，针对支持向量机在样本维数较高时其训练和分类速度较慢的问题，用哈尔小波变换对训练样本和分类样本向量进行降维处理，降低支持向量机在模型训练和分类测试阶段的运算量，有效提高训练和分类的时间效率。本文在分析实验数据的基础上对上

8、述方法的应用效果做了总结。小波变换是对支持向量机用向量表示的样本进行加工处理。从应用的出发点来看，其目的是为了提高训练和分类的时间效率，小波变换使用的策略则是降低向量的维数：从应用的效果来看，小波变换的效果较好，且都在一定程度上降低了训练和分类时间，能够更好的保证分类的准确率。课题研究起止时间和进度安排：1.起止时间：2013年1月2013年5月2进度安排：12-292013-2-28确定论文题目，查找资料，撰写开题报告根据课题研究的内容，收集资料。3-22013-3-20深入探讨该算法中的几个经典问题。2013-3-212013-4-10整理研究内容，并作进一步的修改。2013-4-1120

9、13-5-4归纳总结，形成一份完整的课题论文。2013-5-8交论文，答辩。学士学位论文题目基于支持向量机的文本分类算法研究与实现学生李慧颖指导教师李红宇副教授年级2009级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程哈尔滨师范大学2013年5月摘要：随着计算机与通讯技术的飞速发展，互联网上的电子文档信息急剧增加。这就使得文本的自动分类越来越受人们的重视，而支持向量机和文本分类问题有着良好的结合点从而使得基于支持向量机的文本分类成为这个领域的研究热点。支持向量机是一种基于结构风险最小化准则的分类学习机模型，它的应用十分广泛。虽然支持向量机算法的性能在许多实际问题的应用中得到

10、了验证，但是还存在着一些需要改进的地方，如：训练算法速度慢测试阶段运算量大等。关键词：支持向量机；文本分类；学习机模型目录TOC o 1-5 h z HYPERLINK l bookmark10 第一章引言1 HYPERLINK l bookmark12 研究背景及意义1 HYPERLINK l bookmark14 国内外研究现状1 HYPERLINK l bookmark16 文本分类研究现状1 HYPERLINK l bookmark18 SVM研究现状2 HYPERLINK l bookmark20 文本内容研究3 HYPERLINK l bookmark22 第二章文本分类4 HYP

11、ERLINK l bookmark24 文本自动分类概述4 HYPERLINK l bookmark26 文本分类所涉及的技术领域4文本分类与自然语言处理4 HYPERLINK l bookmark28 文本分类与文本挖掘5 HYPERLINK l bookmark30 文本分类与机器学习5 HYPERLINK l bookmark32 文本分类与模式识别5 HYPERLINK l bookmark34 文本分类的关键技术6文本表示6 HYPERLINK l bookmark36 特征选择7 HYPERLINK l bookmark38 权重计算9 HYPERLINK l bookmark40

12、 常用的文本分类算法9 HYPERLINK l bookmark42 文本分类的应用11 HYPERLINK l bookmark44 第三章支持向量机13 HYPERLINK l bookmark46 支持向量机简介13 HYPERLINK l bookmark48 支持向量分类机14 HYPERLINK l bookmark50 线性可分问题14 HYPERLINK l bookmark52 近似线性可分问题15线性不可分问题15 HYPERLINK l bookmark56 支持向量机的应用步骤16 HYPERLINK l bookmark58 基于支持向量机文本分类方法的优势17 HY

13、PERLINK l bookmark60 基于支持向量机文本分类方法中存在的问题17 HYPERLINK l bookmark62 第四章小波变换在支持向量机分类中的应用19 HYPERLINK l bookmark64 问题的提出19 HYPERLINK l bookmark66 降维相关的研究工作19 HYPERLINK l bookmark68 小波分析20 HYPERLINK l bookmark70 离散小波变换20 HYPERLINK l bookmark72 小波的定义21 HYPERLINK l bookmark74 一维哈尔小波变换21 HYPERLINK l bookmar

14、k76 哈尔基函数22哈尔小波函数22 HYPERLINK l bookmark78 函数的规范化23 HYPERLINK l bookmark80 哈尔基的结构24 HYPERLINK l bookmark82 哈尔小波变换的应用24 HYPERLINK l bookmark84 哈尔小波变换的过程24 HYPERLINK l bookmark86 哈尔小波变换的应用24 HYPERLINK l bookmark88 哈尔小波变换在本文中的应用26小波变换的应用27 HYPERLINK l bookmark90 实验及结果分析28实验平台及环境28 HYPERLINK l bookmark9

15、2 实验步骤28 HYPERLINK l bookmark94 实验目的29 HYPERLINK l bookmark96 结果分析29 HYPERLINK l bookmark98 第五章总结33 HYPERLINK l bookmark100 文本总结33 HYPERLINK l bookmark102 工作展望33 HYPERLINK l bookmark104 参考文献：34Absatrct:.35 第一章引言研究背景及意义所谓的文本自动分类，最初是应信息检索(InformationRetrieval,IR)系统的要求出现的。信息检索系统要操纵许多的数据，而文本信息库可能是相当庞大的，

16、并且，用来表示文本内容的词汇数量又是成千上万的。因此，在这种情况下，如果能够提供文本集良好的组织与结构，就能一定程度上简化文本的操纵。文本自动分类系统的目的就是对文本集进行有序组织，把相似的、文本组织在一起。它作为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确的查询结果。其中，高效性来自于用户可以首先确定查询的可能类别，以减小需进一步匹配的文本数量。有效性在于相似的文本很可能与相同的查询相关。这样，检索的查全率和准确率都得到了提高。随着全球计算机与通讯技术的飞速发展、互联网络的普及与应用，文本自动分类对于信息处理的意义变得更加重要。在互联网中，电子文档信息每天都在急剧的增加，通过网络

17、，人们可以很方便地共享巨大的信息资源。但网络信息的快速膨胀使得给人们进行信息查找的信息资源无法很有效的加以利用。面对网上的海量信息，传统的做法是对网上信息进行人工分类，并加以组织和整理，为人们提供一种相对有效的信息获取手段。但是，这种人工分类的做法存在着许多弊端：一是耗费大量的时间和精力。二是存在分类结果不精准。即使分类人的语言素质较高，但其分类结果仍然不尽相同。网络信息的激增不仅增加了对于快速、自动文本分类的迫切需求，而且又为基于机器学习的文本分类方法准备了充分的准备。支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1995年提出的一种新的非常有潜力的分类技术，SVM是一种基

18、于统计学习理论的模式识别方法，主要应用于模式识别领域。由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究一直没有得到充分的重视。直到90年代，统计学习理论(StatisticalLearningTheory，SLT)的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。从此迅速的发展起来，现在已经在许多领域(生物信息学，文本和手写识别等)都取得

19、了成功的应用。SVM的主要思想可以概括为两点：它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。对学习算法的研究和改进是目前SVM研究的主要内容，在过去的十多年里，出现了很多SVM算法的改进算法，从算法实现中优化理论的改进、核函数的构造到算法参数的选择等国内外研究现状文本分类研究现状文本分类一般包括了文

20、本的表达、分类器的选择与训练、分类结果的评价与反馈等过程，其中文本的表达又可细分为文本预处理、索引和统计、特征抽取等步骤。美国IBM公司的H.P.Luhn在20世纪50年代末对文本分类进行研究，他提出了词频统计思想，后来被应用在文本分类领域。60年代初，Maron在利用概率模型进行文本分类方面做出了开创性的研究工作。Salton等人在70年代初提出了向量空间模型，由于该模型在良好的统计学方法基础上简明地实现了对文本特性的抽象描述，从而成为文本分类处理的一种经典模型。其后许多学者在这一领域进行了卓有成效的研究。国外文本自动分类主要经历了四个发展阶段：第一阶段(1958-1964)：研究文本自动分

21、类的可能性；第二阶段(1965-1974)：进入文本自动分类的实验性阶段；第三阶段(1975-1998)：文本自动分类的实用性阶段；第四阶段(1990-至今)：因特网文本自动分类研究阶段。国内文本自动分类研究起步较晚，始于20世纪80年代初期。1981年侯汉清对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，有越来越多的人借鉴国外的一些研究成果，结合中文的特点进行中文文本自动分类的研究。中科院计算所的李晓黎、史忠植等人应用概念推理网进行文本分类。复旦大学的周水庚等人用了N-gram方法对中文文本进行分类尝

22、试，从文档中提取N-gram属性，然后用ON方法判别文本类别，摆脱了对词典和切词处理的依赖，实现文本分类的领域无关性和时间无关性。刁力力、石纯一等用Boosting来组合决策树(Stumps)的方法进行文本分类。卜东波从信息粒度的角度来剖析聚类和分类技术，试图使用信息粒度原理的框架来统一聚类和分类。庞剑峰等应用向量空问模型进行了中文文本分类实验，并同时对文本分类所涉及的关键性技术，例如特征提取、不同机器学习方法等进行了研究和探讨，给出了评估方法和实验结果。之后他又验证了在文本分类系统中应用反馈方法的可行性，给出了结合反馈方法的文本分类算法。SVM研究现状SVM由于分类效果比较好成为近几年人们研

23、究的热点SVM是建立在SLT的VC维理论和结构风险最小化原理基础上，根据有限样本信息在模型复杂性(对特定样本的学习精度)和学习能力(无错误地识别样本的能力)之间寻求一种折中，以期达到最佳的推广性能。1995年，Vapnik在“TheNatureofStatisticalLearningTheory，一书中提出支持向量机的概念，并在“SupportVectorNetworks，一文中进行了详细的介绍。从那以后，关于支持向量机方面的文章如雨后春笋，逐渐成为国际上机器学习领域的研究热点，吸引了国内外众多知名的专家Daniel和Gabriele提出了基于小波的核函数构造方法：Atari和Wu设计了一种

24、算法，他们通过对核函数的黎曼几何分析，提出利用实验数据逐步修正己有的核函数，使之能更好地与实际问题相吻合；Cauwenberghs和Poggio研究了基于SVM的增量和减量学习问题；Diehl和Cauwenberghs提出了一个精确增量学习和自适应SVM分类器的框架;Opper和Urban-czik对SVM学习带噪声的多项式规则进行了研究，在核函数阶数足够高或者为超越函数时，渐近线和学习曲线由目标规则决定而不是核函数，在这种情况下研究了训练误差核推广误差的收敛性；Bordes等提出一种在线SVM算法LASVM，通过对样本的主动选择提高了学习速度；Serifini等研究了基于梯度方法的SVM分解

25、算法中起作用集的选择问题；此外，还有很多学者对SVM的算法进行了研究，这里就不一一列举了。Joachims和Dumais例等人于1998年开创了SVM在文本分类中应用的先河。他们各自在不同语料库中做了大量试验，结果表明SVM在文本分类的应用中特别有效，并有很好的泛化性，克服了高维表示中的困难。此后，很多学者开始了这方面的研究，并取得了很多研究成果。目前，SVM己被越来越多地应用到模式识别领域，如手写体文字识别、人脸识别等在图像压缩和数据分类的应用中，SVM也显示出了较好的性能。而SVM在文本分类中的应用，主要关注以下几个方面：(1)提高支持向量机的计算速度，以便处理更大规模的文本分类问题；利用

26、最优化技术改进或改造SVM形式，简化计算过程；(3)利用结构风险最小化原则、核思想和J下则化技术等改造传统的线性算法，构造出相应的核形式，使之更适合文本分类等。但从现在研究来看，用于文本分类的核函数一经确定(如多项式核和高斯核等)，其参数的选择多是凭借经验，或是在试验中一步一步的修正。通常这个选择必须适用于具体的数据，在缺乏可靠的条件时，在应用中需要使用验证集或者是交叉验证来设置这些参数。文本内容研究本文主要研究基于支持向量机的文本分类算法，文中主要介绍了文本分类、支持向量机、聚类方法在支持向量机分类中的应用、小波变换在支持向量机分类中的应用等，结构安排如下：第一章，引言。主要介绍了课题的研究

27、背景、研究意义、国内外研究现状，概述本论文的主要工作以及结构安排。第二章，文本分类相关知识。由于基于支持向量机的文本分类是众多文本分类方法中的一种，它以文本分类为基础。因此本文对文本分类的相关知识做了详细的介绍，如文本表示、特征选择、权重计算、文本分类算法等文本分类的关键技术。第三章，支持向量机相关知识。支持向量机的应用领域十分广泛，文本分类只是其中一种比较典型的应用。本文研究的是基于支持向量机的文本分类算法，所以也有必要介绍支持向量机的相关知识。本章中主要介绍了支持向量机的基本原理、支持向量分类机、支持向量机的核函数、支持向量机的应用步骤以及支持向量机分类方法的优缺点。第四章，小波变换在支持

28、向量机分类中的应用。本章主要研究的是小波变换对支持向量机的输入向量进行降维，从而提高支持向量机的训练和分类的效率，在本章中首先对小波变换的基础知识做了详尽的介绍，其中包括：离散小波变换的基本原理、一维哈尔小波、哈尔小波变换的应用过程等。接着本文着重分析了用哈尔小波变换在支持向量机分类中应用，并在理论分析的基础上构造了实验系统。最后在分析实验数据的基础上讨论了小波变换应用的效果。第五章，总结和展望。本章总结了通过实验得出的结论，并叙述了本文中所用方法的不足，对将来的工作进行了展望第二章文本分类文本自动分类概述文本自动分类是对大量的非结构化的文字信息（文本文档、网页等）按照给定的分类体系，根据文字

29、信息内容分到指定的类别中去，是一种有指导的学习过程。文本自动分类的过程总体上可划分为训练和分类两部分。训练的目的是通过样本和类别之间的联系构造分类模型，使其用于分类。分类则是依据训练结果对未知样本进行分类，给出类别标识的过程。具体流程如图2.1所示，其中训练过程用实线表示，分类过程用虚线表示。图2.1文本自动分类过程文本分类所涉及的技术领域文本分类技术涉及到多个领域的知识，包括语言学中的自然语言处理、数据挖掘中的文本挖掘、计算机领域的机器学习和模式识别等。文本分类与自然语言处理自然语言处理是文本分类的基础，文本分类主要借助了其文本处理相关技术，如分词技术、N元模型等。中文自然信息处理发展至今可

30、以分为三个阶段，字处理阶段、词处理阶段和句处理阶段。字处理研究内容包括汉字编码、汉字识别、汉字输入法和字处理软件等。到目前为止，这些技术己经比较成熟，字处理继续研究的领域己经不多，大多数科学家将研究方向移至词处理和句处理的研究当中。目前，词处理阶段上最成功、最典型、也最引人瞩目的应用领域是Internet上的搜索引擎，如Google、Yahoo和百度等，对一般的检索都能返回不错的结果。其它正在研究的方向还包括文本过滤、个性化服务系统、语音识别等。在词处理上的其他应用还有文本自动校对、汉字简繁体自动转换、自动分词等领域引。句处理上的应用主要有两个方面：一是机器翻译，目前机器翻译的质量仍旧不能令人

31、满意。二是汉语语法分析，大家在使用微软字处理软件的时候都会发现它能够提示一些英文语法错误，但对中文语法的提示往往是不正确的。总的来说，在自然语言处理领域中字平台研究已快成为过去；句平台上的研究还很薄弱，离实用还有一段距离；而词平台上的研究，难度较句平台容易，已经出现了一些成果，也是现在继续研究的重点。文本分类与文本挖掘文本的知识发现最早是由Feldman和Dagan首先提出来的，又称为文本数据挖掘。文本数据挖掘不仅是在单独文本中提取所需信息，同时也包括分析文档集合的模式和趋势。文本挖掘不同于数据挖掘，数据挖掘面对的是结构化数据，采用的方法大多是非常明确的定量方法。而文本挖掘处理的是非结构化的文

32、本，由于语言本身的特点有其需要解决的特殊问题。因此，决定它采用的方法与数据挖掘不同，它经常使用的方法来自自然语言理解和文本处理领域。与信息检索(InformationRetrieval)、文本聚类(TextClustering)等一样，文本分类也属于文本挖掘(TextMining)的范畴，可以看成是文本挖掘中的一项基本任务。文本分类与机器学习文本分类是机器学习的应用领域。机器学习是计算机程序针对某一类问题T从经验E中学习，它的性能用P来衡量。很多的学者认为使机器具有推广性(具有小的测试错误率)的唯一因素是使它在训练集上的错误率最小。文本分类就是一个有指导的学习过程。它根据一个已经被标注了类别的

33、训练文本集合，找到文本特征和文本类别之间的关系模型，然后利用这种学习得到的关系模型对新的文本进行类别判断。可以形式化的描述为：假设有一组文本概念类C和一组训练文本D。文本概念类和文本库中的文本可能满足某一概念层次关系h。客观上，存在着一个目标概念T,有：T:DC这里，T把一个文本实例映射为某一个类。对D中的文本d-T(d)是已知的。通过有指导地对训练文本集的学习，可以找到一个近似于T的模型H：H:D-C在某些情况下最优的目标函数是没有的，只能退而求其次。对于任何分类，最优的目标函数是指错误率最小。对于一个新文本d-H(d)表示对d的分类结果。一个分类系统的建立或者说分类学习的目的就是寻找一个和

34、T最相近的H。即给定一个评估函数f,学习的目标应使T和H满足：Min(ZD|)f(f(T(di)-H(di)imI机器学习中最重要的一些目标函数的逼近算法如LMS、贝叶斯方法也被用到文本分类中。文本分类与模式识别通常把通过对某具体的个别事物进行观测所得到的具有时间和空间分布的信息称为模式，而把模式所属的类别或同一类中模式的总体称为模式类(或简称为类)。也有人习惯于把模式类称为模式，而把具体的模式称为样本模式识别就是指用计算机实现人的模式识别能力，用机器去完成人类智能中通过视觉、听觉、触觉等感官去识别外界环境的自然信息的那些工作。模式识别的目的就是要寻找每一类的特殊的属性或建立类与类之间的边界，

35、使类与类之间可以很好的区分。在文本分类中，每一类文本可以看作一个模式，该类文本的总体构成一个模式类，一个个文本都是样本。模式识别有两种基本的方法统计模式识别方法和句法模式识别方法。文本分类中主要使用统计模式识别方法，一方面由于以语义分析(句法模式识别)为手段遇到空前的困难，另一方面统计模式识别实现简单，出现了巨大的进展。一般来讲，一个模式识别系统主要由三部分组成，如图2.2所示：预处理特征选择识别算法图2.2模式识别系统结构输入模式分类系统果描述T预处理指将现实世界的信息转换成计算机所能够接受的数字量。在中文文本分类过程中，则是将非结构化的文本转换为能够用来进行处理的结构化形式。特征选择指对满

36、足识别要求的样本根据识别方法，抽取其特征项作为识别的依据。这个过程的处理主要考虑两个问题：一是要求选择出来的特征能够足够代表这个样本；二是要求它们的数量要尽量少。这个方面的研究也称为“特征项降维”。现在的文本分类所使用的特征选择方法己经有许多，如信息增益、互信息、交叉嫡等。识别算法则是将抽取出来的样本特征创建一个用来区分类别的模型，文本分类中通常使用向量空间模型，通过识别算法得到的就是一个分类系统。模式识别研究的通常是一些通用的分类算法，其中许多算法都可以应用在文本分类中如：Rocchio(中心向量方法)、NaiveBayes(朴素贝叶斯方法)、KNN(KNearstNeigllborK近邻方

37、法)、DecisionTree(决策树方法)、SVM等等。文本分类的关键技术文本表示从本质上讲，文本是一个由众多字符构成的字符串，无法被学习算法直接用于训练或分类。要将机器学习运用于文本分类问题，首先需要将作为训练和分类对象的文本，转化为机器学习算法易于处理的形式，即运用各种文本特征表示方法，文本特征表示是指以一定特征项来代表文本，在文本分类时只需对这些特征项进行处理，从而实现对非结构化文本的处理。现有文本分类技术的前提假设是特征和文本类别概念密切相关，特征表示模型有多种，常用的有概率模型、潜在语义索引模型、向量空间模型等。向量空间模型是近年来应用较多且效果较好的方法之一。贝叶斯概率模型贝叶斯

38、概率模型是用概率架构来表示特征项，将训练实例1分解为特征向量X和决策类别C；该模型假定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作用于决策变量。尽管这个假定在一定程度上限制了贝叶斯模型的适用范围，然而在实际应用中，以指数级降低了贝叶斯网络构建的复杂性。在很多领域即使违背这种假定的条件下，贝叶斯概率模型也表现出相当的健壮性和高效性，已经成功地应用到分类、聚类中。潜在语义索引模型潜在语义索引模型LSI(LatentSemanticIndex)模型是由Dumais，Furnas，Landaver和Harshman于1990年提出，也用向量表示特征项，但是每一个向量代表一个“概

39、念”，就是通常所说的“概念空间模型”。LSI使用一种数学上的“奇异值分解即(Singular、ValueDecomposition,SVD)”技术，把文档投影到一个具有潜在语义的“特征.文本”多维空上,共现特征、同义特征投影在同一维上，非共现特征、非同义特征在不同的维上，这样就会出现没有共同的特征的文本间也会有较高的相似度。向量空间模型向量空间模型(VectorSpaceModel)是由GerardSalton和McGill于1969年提出的，并最早成功应用于信息检索领域，后来又在文本分类领域得到了广泛的运用。向量空间模型的基本思想是以向量来表示文本：(WWWn)，其中Wi为第i个特征项1,2

40、,的权重。那么选取什么作为特征项呢？一般可以选择字、词或词组。根据前人经验，普遍认为选取词作为特征项要优于字和词组。因此，要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本。最初的向量表示完全是0、1形式，即：如果文本中出现了该词，那么文本向量的该维为1,否则为0。这种方法无法体现这个词在文本中的作用程度，所以逐渐0、1被更精确的词频代替。词频分为绝对词频和相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词频，其计算方法主要运用TFIDF公式，它是一种文本的词集表示法，所有的词从文本中抽取出来，而不考虑词间的次序和文本的结构。目前

41、存在多种TF-IDF公式，一种比较普遍的TF-IDF公式：(2.1)f(t,d)*log(N：n+0.01)W(t,d)=匸斯工tf(t,d)*log(Nn)+0.01)ed其中，W(t,d)为词t在文本d中的权重，而tf(t,d)为词t在文本d中的词频，N为训练文本的总数，Nt训练文本集中出现t的文本数，分母为归一化因子。另外还存在其他的TF-IDF公式，例如:(2.2)(1+logtf(t,d)*log(Nn)W(t,d)=222迄(1+logtf(t,d)*log(Nn)2ed221该公式中参数的含义与式(2.1)相同。向量空间模型的一个基本假设是，一份文本所属的类别仅与某些特定的单词或

42、词组在该文档中出现的频数有关，而与这些单词或词组在该文本中出现的位置或顺序无关。也就是说，如果将构成文本的各种语义单位(如单词、词组)统称为“特征项”，以及特征项在文本中出现的次数称为“词频”，那么一份文本中蕴涵的各个特征项的频率信息足以用来对其进行正确的分类。这一假设对于文本的主题分类而言是恰当的，而对于其他方面的文本分类，如流派、作者等识别问题就不那么可靠了。向量空间模型中，一个文本表示为特征空间中的一个向量，这个向量也称为文本向量。文本向量中每一维对应于文本中的一个特征，它的权重为该向量维对应的特征在文本中的权重。特征选择目前主流的文档表示方法是向量空间模型。向量空间模型中，一篇文档表示

43、为特征空间中的一个向量，这个向量也称为文档向量。文档向量中每一维对应于文档中的一个特征，它的权值为该向量维对应的特征在文档库中的权值，一般采用TF-IDF方法计算。若使用词语作为文本特征，那么文本的特征向量会达到上万维甚至数十万维的大小，在此一个高维空间上对文本分类所使用的学习算法进行训练，显得既不经济又无必要，因此必须通过特征选择来进行维数压缩，特征选择经常会使用特征独立性假设来简化特征选择，以达到计算时间和计算质量的折衷。因此，目前在对文本的特征空间所采取的特征选择算法一般是构造一个评价函数，对特征集中的每个特征进行独立的评估。这样每个特征都获得一个评估分，然后对所有的特征按照其评估分的大

44、小进行排序，选取预定数目的最佳特征作为结果的特征子集在中文文本分类中，文本集经过分词后变成词集，然后经过去掉停用词粗降维得到特征集。但是特征集仍然是个高维的特征空间，对于所有的分类算法来说维数都太大。因此，我们面临寻求一种有效的特征抽取方法，以降低特征空间的维数，提高分类的效率和精度。特征选择的目的是除去特征集中不能较好表示有效信息的特征，以提高分类准确度和减少计算复杂度。常见的特征选择方法有以下四种：文档频率(DF)、信息增益(IG)、互信息(MI)、X2统计量(CHI)等。这些方法的基本思想都是对每一个特征即词条，计算它的某种统计的度量值，然后设定一个阈值T,把度量值小于T的那些特征过滤掉

45、，剩下的即认为是有效特征。下面分别介绍这几种特征选择算法。文档频率(DocumentFrequency，DF)2.3)单次出现的文档数DF(W)=-训练集的文档总数文档频数是最简单的评估函数，其值为训练集合中出现此词的文本数占总的文本数的概率。DF评估函数的理论假设是：稀有单词要么不含有用信息，要么太少而不足以对分类产生影响；要么是噪音，所以可以删去。虽然它在计算量上比其它的评估函数小得多，但是在实际运用中它的效果却是出奇地好。需要注意的是，在特征选择之前必须将停用词去掉，仅保留与主题相关的词汇。踯估函数也存在缺点，比如稀有单词可能在某一类文本中并不稀有，而且包含着重要的判断信息。在实际运用中

46、一般并不直接使用DF评估函数，常把它作为评判其它评估函数的标准。信息增益(informationGain，IG)信息增益通过统计某个特征项在一篇文档中出现或不出现的次数来预测文档的类别。它是一种基于熵的评估方法，涉及较多的数学理论和复杂的熵理论公式，定义为某特征项为整个分类所能提供的信息量，不考虑任何特征的熵与考虑该特征后的熵的差值。他根据训练数据，计算出各个特征项的信息增益，删除信息增益很小的项，其余的按照信息增益从大到小排序。其描述如下：；P(C.W)LP(C/W)小八IG(W)=P(W)P(C.W)logi+P(W)XP(C.-W)logi(2.4)iP(C)iP(C)iii其中P(Ci

47、/W)表示文本中出现词W时，文本属于类别Ci的概率，同样P(Ci/W)表示文中不出现词W时文本属于类别Ci的概率；P(Ci)表示类别出现的概率；P(W)表示词W在整个文本训练集中出现的概率。信息增益是一种在机器学习领域应用较为广泛的特征选择方法。它从信息论角度出发，用各个特征的取值情况来划分学习样本空间，然后根据所获信息增益的多寡来选择相应的特征。互信息(MutualInformation，MI)(2.5)P(WC)MI=XP(C)logiP(W)i词条和类别的互信息体现了词条与类别的相关程度，是一种广泛用于建立词关联统计模型的标准。如果词W在某个类别Ci中出现的概率高，而在其它类别中出现的概

48、率低，则W将获得较高的互信息，也就有可能被选取为类别Ci的特征。X2统计量(CHI)PPN(AD-BC)2(26)CHI(W)=XP(C)X2(W,C)=XP(C)(2.6)iii(A+C)(B+D)(A+B)(C+D)ii其中A表示词W在类别Ci中出现的频度；B表示词W在除Ci以外的其它类别中出现的频度,C表示除W以外的其它词在类别Ci中出现的频度；D表示除W外的其它词在除Ci以外的其它类别中出现的频数。该方法类似于互信息MI,词的X2(CHI)统计值比较了词对一个类别的贡献和对其余类别的贡献，以及词和其它词对分类的影响。当词矿与类别C,互相独立时，ADBC=O,X2(CHI)的值为O；若A

49、DBCO,说明词W与类别Ci正相关，即该词出现说明某个类别很可能出现;反之，若ADBC1i=1,m3.4)进一步，支持向量机方法首先求解该问题的对偶问题最小化形式，minmm乙乙yyaa(x,x)ijijijai=1j=1ms.t.Xya=0iii=1a0i=1,m(3.5)i然后根据对偶问题的解得到原问题的解，具体求解过程就是根据原始问题的Lagrange函数以及KKT条件可以计算得到：w=$yax:选择a的一个分量ao,iiii=1b=xa(、，从而来确定决策函数。算法具体的步骤如下:b=yy.(xx)jiiiji=1算法1线性可分支持向量分类机(1)构造并求解最优化问题minmm乙乙yy

50、aa(x,x)ijijijai=1j=1ms.t.Tya=0iii=1a0i=1mi(3.6)得最优解a=(a1a)T；n计算W=yax,选择a.的一个分量a.0,b=y一ya.(xx)iiijjjjjiji=1i=1构造分类超平面(wx)+b=O，由此得到决策函数f(x)=sgn(W*x)+b)(3.7)“支持向量”是指训练集中的某些训练点的输入x。事实上，最优化问题(3.6)的解ja的每一个分量a都与一个训练点相对应，显然算法1所构造的分类超平面，仅仅依赖于那些a；不为零的训练点(x,y),而与相应于a为零的训练点无关。所以我们特别关心相应ij于a不为零的训练点(x,y),并称这些训练点的

51、输入x为支持向量。显然，只有支持向量jiji对最终求得的分类超平面的法方向w有影响，而与非支持向量无关。近似线性可分问题用一条直线也能大体上(大体上意味着有某一个或者很少的几个点划分错误)把训练集正确分开，这类问题称为近似线性可分问题，这时仍可以考虑用线性分类学习机。具体求解方法类似线性可分问题，其步骤如下：算法2近似线性可分支持向量分类机选择适当的惩罚参数c0,构造并求解最优化问题mina12i=1j=1yyaa(xijijimx)一乙ajjj=1ms.t.乙ya=0ii3.8)i=10aci=1,mi得最优解a=(a1am)T1m计算W=Tya.xiiii=1选择a的一个分量0a1ii1g

52、0,i=1,m(3.10)i这里M=(x),是特征空间日中的输入向量。类似，引入它的对偶问题的极小化形式:1j1mmmmin乙乙yyaak(xx)一乙a(3.11)2ijijijjai=1j=1j=1ms.t.乙ya=0iii=1(3.12)0aci=1,m(3.13)i令矩阵H(i,j)=yyK(x,y)，其中i,j=1,2,.J,即称为核函数矩阵，它是一个ijij半正定的对称矩阵，第一个约束条件式(312)称为超线性约束条件，第二个约束条件式(313)称为超立方体约束条件。这里K(x,x)=(x)(x)(3.14)ijjj称为核函数，有关核函数的进一步讨论可参见本文后面的有关讨论。类似前面

53、的求解方法，通过求解对偶问题来确定最终的决策函数，这样得到标准支持向量分类机算法。算法3支持向量分类机(c-svc)选择核函数K(x,x)和惩罚参数C,构造并求解最优化问题ijmina丄2j=1i=1j=1ms.t.乙ya=0iii=10aci=1,mi(3.15)得最优解a=(a1am)T1m(2)选择a的一个分量0a.C;并据此计算b=y一工ya.K(xx)jjjjiji=1(3)求得决策函数：f(x)=sgn(工yaK(x,x)+b)。iiiji=1支持向量机的应用步骤在使用svM方法来解决实际问题时,首先要从具体问题获取训练数据并进行预处理,然后需要选择合适的核函数和相应的参数，最后用

54、求得的最佳参数来训练SVM,其基本步骤简述如下：将实际问题数据化 一般来说SVM只能处理数值类型的数据，从实际问题中提取的样本如果含有像字符串类型、类别类型、范围类型等非数值属性，都需要先通过某些方式转换为数值类型来表达。进行数据规格化对数据集进行规格化(Scaling)是很重要的。它的主要作用是避免数值范围较大的属性的影响力过大以致数值范围较小的属性可能根本不起作用。另一方面，规格化也可以降低数值运算的复杂性，通常将每个属性值按比例缩放到-1,1或者0,1范围内。训练样本数据和测试样本数据需要进行同样比例的缩放。选择核函数常用的核函数有线性核、多项式核、RBF核和Sigmoid核等很多种，各

55、有不同的优点和适用场合。在这几种核函数中，计算最快的是线性核，在训练集特别大或属性特别多的情况下也可以快速地训练出结果，但它只有在近似线性可分的情况下才能取得满意的效果。多项式核计算也较快，其函数值可能趋向无穷大或者零，跨度非常大，在一些情况下有可能造成计算困难：Sigmoid核不是正定核，在有些情况下通用性不够。RBF核函数具有良好的性能，在缺乏问题先验知识时其适应性是最好的，它能够处理非线性的情况，而在参数取某些特定值时，又和线性核或Sigmoid核具有相似的性能。RBF核的另一个优点是它只有一个核参数，比多项式核和Sigmoid核少，在选择参数时的比较方便。寻找最优参数训练SVM时要考虑

56、两种参数：核参数和惩罚参数C。参数的选择并没有通用的先验知识，需要在一定范围内进行搜索以找到好的参数组合。由统计学习理论可知，得到高的训练正确率并不能保证在未来的测试中具有高的预测精度，因此对不同参数组合训练所得的SVM需要进行模型选择，以取得推广能力最强的SVM模型。用最优参数来训练SVM模型经过测试确认学习精度较好的SVM模型将被用于解决实际问题。3.4基于支持向量机文本分类方法的优势文本分类的特点有：文本分类所需要处理的样本空间非常庞大，即便通过简化，仅考虑词，而不考虑词的次序不同、断句等的不同所表达的含义的不同，样本的维数也很咼；文本向量非常稀疏;文本特征之间存在较大的相关性;文本训练

57、样本集中存在较多噪音；不同文本类别的训练样本数目往往存在较大差别。文本分类的这些特点，使得很多分类算法的效果不好。与其它文本分类算法相比，支持向量机主要具有如下优势：文本数据向量维数很咼，对于咼维问题，支持向量机具有其它机器学习方法不可比拟的优势；文本向量特征相关性大，许多文本分类算法建立在特征独立性假设基础上，受特征相关性的影响较大，而支持向量机对于特征相关性不敏感；文本向量存在咼维稀疏问题，一些文本分类算法不同时适合于稠密特征矢量与稀疏特征矢量的情况，但支持向量机对此不敏感；文本分类样本收集困难、内容变化迅速，支持向量机能够找出包含重要分类信息的支持向量，是强有力的增量学习和主动学习工具，

58、在文本分类中具有很大的应用潜力。3.5基于支持向量机文本分类方法中存在的问题支持向量机从被广泛重视到现在只有十多年的时间，已经提出的很多关于支持向量机的训练算法，从训练时间和分类精度两种角度进行优化。其中还存在很多尚未解决或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需要，支持向量机在实际应用中、尤其在文本分类等类别和样本数目多、噪音多的应用中存在的主要问题包括：(1)对于需要求解二次规划问题的支持向量机模型，当样本数目较多时，其训练速度较慢。尤其对于训练样本和支持向量数目多的分类问题，支持向量机的分类和训练速度过慢，这一点限制了支持向量机的应用，成为支持向量机方法进入大规模实用化

59、阶段的瓶颈。如何进一步改进和完善支持向量机模型及其训练算法，是支持向量机研究中的热点问题。向量维数较高时其训练和分类速度较慢。支持向量机中核函数及参数的选择没有好的确定的方法，仍然凭经验寻求。不同的核函数对应的支持向量集合有所不同，而支持向量的少量丢失都会引起分类精度的下降，大规模文本分类中在减少样本数目时怎样保证不丢失支持向量仍然是个难点。第四章小波变换在支持向量机分类中的应用问题的提出在机器学习中，对于一个学习任务，待学习的目标函数的复杂程度取决于特征的表示形式和特征空间的维数。另一方面，特征空问的大小除了影响计算复杂度以外，还影响着学习机器的泛化能力。据我们所知，一个学习机的泛化能力与所

60、使用的函数有关，也与特征的维数有密切关系的。过高的特征维数是产生过度拟合问题的一个重要因素。通常来讲，计算复杂度和对数据过度拟合的问题是一般分类器都无可避免和必须解决的问题，但支持向量机模型则完美地解决这两个问题：通过引入核函数，从原始空间向高维特征空间作隐式映射，解决了计算复杂度与文本表示需要高维特征的矛盾；另一方面，根据统计学习理论，支持向量机的泛化能力只取决于实例的个数，包含所有实例的球体半径，最小边界的最大值等几个因素决定，而与特征空间的维数无关。同时，人们也对文本分类任务中，以向量空间模型表示文本时的性质进行了深入的研究。这些性质包括：向量空间的高维性、文档向量的稀疏性，特征之间的实