多类支持向量机方法的研究及其在文本分类中的应用

多类支持向量机方法的研究及其在文本分类中的应用目录1绪论.............................................................................................................................11.1引言.................................................................................................................11.2国内外研究现状............................................................................................11.2.1支持向量机研究进展.........................................................................11.2.2文本挖掘研究进展.............................................................................32支持向量机与多类支持向量机.................................................................................42.1支持向量机....................................................................................................42.2多类支持向量机............................................................................................63改进的多类支持向量机.............................................................................................93.1基于二叉树的多类支持向量机原理及算法描述........................................93.2基于二叉树多类支持向量机改进..............................................................113.2.1几种改进策略..................................................................................113.2.2算法设计与分析..............................................................................144多类支持向量机在文本分类中的应用...................................................................164.1文本分类过程及常见方法..........................................................................164.1.1KNN法...............................................................................................164.1.2NativeBayes法...............................................................................174.1.3Rocchio法.......................................................................................194.1.4SVM法...............................................................................................194.2基于多类支持向量机的文本分类器设计..................................................204.2.1传统SVM文本分类器......................................................................204.2.2两类问题改进介绍..........................................................................204.2.3多分类问题改进介绍......................................................................225总结..........................................................................................................................2411绪论1.1引言1992-1995年，Vapnik在统计学习理论的基础上发展出了一种新的模式识别方法——支持向量机（supportvectormachine，SVM），它采用结构风险最小化原则代替了传统机器学习方法中的经验风险最小化原则，能有效地解决过学习问题，具有良好的推广性能，即是由有限的训练样本集得到小的误差能够确保对独立的测试样本集仍保持较小的误差。不过，SVM是一种两类分类器，而实际需要解决的一般是多类问题，因此如何有效地将其推广到多类问题已成为人们研究的热点。随着时代的进入，生活中的信息量成指数增加，文本挖掘日益成为一个流行而重要的研究领域。其中文本分类是文本挖掘中最关键也是最重要的一类任务。文本分类时的类往往表示内容的，比如经济、政治、体育可以成为类。也有根据其它特点的，比如正面意见、反面意见。也可以是根据应用要求的，比如垃圾邮件和非垃圾邮件等。支持向量机（SVM）应用于文本分类的研究十分广泛，比如用于垃圾邮件过滤，错误文本识别等。由于传统的SVM是针对两类分类问题设计的，不能直接用于多类分类问题，因此需要改进多类支持向量机使其能在文本分类中应用。1.2国内外研究现状1.2.1支持向量机研究进展支持向量机（SVM）是Vapnik于1995年首先提出来。其早在20世纪60年代就开始研究有限样本情况下的机器学习问题，但直到90年代以前，也没有提出能够将其理论付诸实现的较好办法,到90年代,有限样本情况下的机器学习理论研究才逐渐成熟起来,形成了一个较为完善的理论体系——统计学习理论(Statisticallearningtheory,SLT)。它能将很多现有方法纳入其中,可望解决许多原来难以解决的问题,如学习能力和推广能力的统一。直到1995年,Vapnik等人又在统计学习理论的基础上,发展出了一种新的通用的学习方法——支持向2量机,其在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并且能够推广到函数逼近和概率密度估计等其他机器学习问题中。由于支持向量机坚实的理论基础和它在很多领域表现出的良好的推广性能，已经成为国际上机器学习领域新的研究热点。目前，国际上对这一理论的讨论和进一步研究逐渐广泛，而我国国内在此领域开展的很多研究只是对国外一些现有研究成果的翻译和修补，或者只是直接搬过来进行应用，鲜有自己的理论和实际应用创新。因此我们需要及时学习掌握有关理论，开展有效的研究工作，使我们在这一有着重要意义的领域中能够尽快赶上国际先进水平。由于SLT理论和SVM方法尚处在发展阶段，很多方面尚不完善，比如：许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而有关SVM算法某些理论解释也并非完美；此外，对于一个实际的学习机器的VC维的分析尚没有通用的方法；SVM方法中如何根据具体问题选择适当的内积函数也没有理论依据；许多的实际运用中(如：遥感影像分类，客户分类，文本分类等)都需要解决大类别的分类问题，随着支持向量机在这些领域的深入运用，如何有效地将该方法推广到多类分类问题中已经引起了人们广泛的兴趣。现有的多分类支持向量机主要通过如下两种方式进行扩展：①通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类；②将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”地实现多类分类很多学者和研究人员(比如Chih-WeiHsu，Chih-JenLin)在他们的论文中总结了现有主要的支持向量机多类分类算法，系统地比较了各算法的性能，并分析了它们的不足和有待解决的问题，但在这方面国内并没有提出好的解决办法，只是在国外现有多分类支持向量机基础上做些改进或者应用。由于其在模式识别领域(如字符识别、语音识别、人脸检测)和函数逼近、数据挖掘、线性系统控制中均有很好的应用。目前国内对支持向量机可以说也进行了初步的理论研究，取得了不错的进展。比较遗憾的是,虽然SVM方法在理论上具有很突出的优势,但与其理论研究相比,国内应用研究尚相对比较滞后,目前只有较有限的实验研究3报道,且多属仿真和对比实验。SVM应用研究和多分类扩展研究都是比较重要的研究方向。1.2.2文本挖掘研究进展文本挖掘属于数据挖掘这一交叉学科的一个具体领域，文本挖掘的主要任务是分析文档数据库的内容，发现文档数据集中概念、文档之间的相互关系和相互作用，为用户提供相关知识和信息；此外，文本挖掘处理的是非结构化的文本信息，而不是数据挖掘中采用的结构化数据信息。文本挖掘技术就成为处理大量的文本信息的必然选择。文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终可用的信息或知识的过程。直观地说，当数据挖掘的对象完全由文本数据类型组成时，这个过程就称为文本挖掘。它超出了基于关键字和相似度的信息检索范畴，对文本信息的挖掘主要是发现某些文字出现的规律以及文字与语义、语法间的联系，用于自然语言的处理，如机器翻译、信息检索、信息过滤等，通常采用信息提取、文本分类、文本聚类、自动文摘和文本可视化等技术从非结构化文本数据中发现知识。文本挖掘属于新兴的前沿领域,国内对此研究相对较少,目前国内外学者主要在文本结构分析、文本摘要、文本分类、文本聚类、文本关联分析、分布分析和趋势预测等方面进行了研究,中国学者在中文分词等领域取得了一些进展。文本挖掘可以对大量文档集合的内容进行总结、分类、聚类、关联分析，以及利用文档进行趋势预测等。可以说关于文本挖掘的研究只是刚刚开始，诸多问题等待研究、解决。还需要面临的一些具有挑战性的问题，主要涉及到以下几个方面。①很多文本数据挖掘技术是基于有指导学习的，所以往往需要利用大量的有标注的数据。现实当中标注数据所需的代价往往是很高的。怎样以少量的标注数据学习达到用大量的标注数据学习时所能达到的效果是需要解决的问题。主动学习(ActiveLearning)、自助学习(Bootstrapping)等许多方法被提出，但这个问题有待进一步的研究。②怎样进行领域适应(DomainAdaptation)也是亟待解决的问题。数据挖掘常常能够建立一个领域的模型，进行有效的处理，但这个模型不容易运用到其它领域。如何解决这个问题是数据挖掘能否推广的关键。4③怎样用更丰富的知识表现来描述文本也是需要考虑的。把文本看作是“词包”是有局限性的，但在很多应用中，现在还只能做到这步。更丰富的知识表现用起来往往并不是更有效。其原因是有待探讨