学号：2009030114哈尔滨师范大学学士学位论文题目基于支持向量机的文本分类算法研究与实现学生李慧颖指导教师李红宇副教授年级2009级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程学士学位论文题目基于支持向量机的文本分类算法研究与实现学生李慧颖指导教师李红宇副教授年级2009级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程哈尔滨师范大学2013年5月摘要：随着计算机与通讯技术的飞速发展，互联网上的电子文档信息急剧增加。

这就使得文本的自动分类越来越受人们的重视，而支持向量机和文本分类问题有着良好的结合点，从而使得基于支持向量机的文本分类成为这个领域的研究热点。

支持向量机是一种基于结构风险最小化准则的分类学习机模型，它的应用十分广泛。

虽然支持向量机算法的性能在许多实际问题的应用中得到了验证，但是还存在着一些需要改进的地方，如：训练算法速度慢、测试阶段运算量大等。

关键词：支持向量机；文本分类；学习机模型目录第一章引言 (1)1.1研究背景及意义 (1)1.2 国内外研究现状 (1)1.2.1 文本分类研究现状 (1)1.2.2 SVM研究现状 (2)1.3 文本内容研究 (3)第二章文本分类 (4)2.1 文本自动分类概述 (4)2.2 文本分类所涉及的技术领域 (4)2.2.1 文本分类与自然语言处理 (4)2.2.2 文本分类与文本挖掘 (5)2.2.3 文本分类与机器学习 (5)2.2.4 文本分类与模式识别 (5)2.3 文本分类的关键技术 (6)2.3.1 文本表示 (6)2.3.2 特征选择 (7)2.3.3 权重计算 (9)2.3.4 常用的文本分类算法 (9)2.4 文本分类的应用 (11)第三章支持向量机 (13)3.1 支持向量机简介 (13)3.2 支持向量分类机 (14)3.2.1 线性可分问题 (14)3.2.2 近似线性可分问题 (15)3.2.3 线性不可分问题 (15)3.3 支持向量机的应用步骤 (16)3.4基于支持向量机文本分类方法的优势 (17)3.5基于支持向量机文本分类方法中存在的问题 (17)第四章小波变换在支持向量机分类中的应用 (19)4.1 问题的提出 (19)4.2降维相关的研究工作 (19)4.3 小波分析 (20)4.3.1 离散小波变换 (20)4.3.2 小波的定义 (21)4.4 一维哈尔小波变换 (21)4.4.1 哈尔基函数 (22)4.4.2 哈尔小波函数 (22)4.4.3 函数的规范化 (23)4.4.4 哈尔基的结构 (24)4.5 哈尔小波变换的应用 (24)4.5.1 哈尔小波变换的过程 (24)4.5.2 哈尔小波变换的应用 (24)4.6 哈尔小波变换在本文中的应用 (26)4.6.1 小波变换的应用 (27)4.7 实验及结果分析 (28)4.7.1 实验平台及环境 (28)4.7.2 实验步骤 (28)4.7.3 实验目的 (29)4.7.4 结果分析 (29)第五章总结 (33)5.1 文本总结 (33)5.2 工作展望 (33)参考文献： (34)Absatrct: . (35)第一章引言1.1研究背景及意义所谓的文本自动分类，最初是应信息检索(Information Retrieval，IR)系统的要求出现的。

信息检索系统要操纵许多的数据，而文本信息库可能是相当庞大的，并且，用来表示文本内容的词汇数量又是成千上万的。

因此，在这种情况下，如果能够提供文本集良好的组织与结构，就能一定程度上简化文本的操纵。

文本自动分类系统的目的就是对文本集进行有序组织，把相似的、文本组织在一起。

它作为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确的查询结果。

其中，高效性来自于用户可以首先确定查询的可能类别，以减小需进一步匹配的文本数量。

有效性在于相似的文本很可能与相同的查询相关。

这样，检索的查全率和准确率都得到了提高。

随着全球计算机与通讯技术的飞速发展、互联网络的普及与应用，文本自动分类对于信息处理的意义变得更加重要。

在互联网中，电子文档信息每天都在急剧的增加，通过网络，人们可以很方便地共享巨大的信息资源。

但网络信息的快速膨胀使得给人们进行信息查找的信息资源无法很有效的加以利用。

面对网上的海量信息，传统的做法是对网上信息进行人工分类，并加以组织和整理，为人们提供一种相对有效的信息获取手段。

但是，这种人工分类的做法存在着许多弊端：一是耗费大量的时间和精力。

二是存在分类结果不精准。

即使分类人的语言素质较高，但其分类结果仍然不尽相同。

网络信息的激增不仅增加了对于快速、自动文本分类的迫切需求，而且又为基于机器学习的文本分类方法准备了充分的准备。

支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1995年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。

由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究一直没有得到充分的重视。

直到90年代，统计学习理论 (Statistical Learning Theory，SLT)的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等，使得SVM迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

从此迅速的发展起来，现在已经在许多领域(生物信息学，文本和手写识别等)都取得了成功的应用。

SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。

⑵它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。

对学习算法的研究和改进是目前SVM研究的主要内容，在过去的十多年里，出现了很多SVM算法的改进算法，从算法实现中优化理论的改进、核函数的构造到算法参数的选择等1.2 国内外研究现状1.2.1 文本分类研究现状文本分类一般包括了文本的表达、分类器的选择与训练、分类结果的评价与反馈等过程，其中文本的表达又可细分为文本预处理、索引和统计、特征抽取等步骤。

美国IBM公司的H.P.Luhn在20世纪50年代末对文本分类进行研究，他提出了词频统计思想，后来被应用在文本分类领域。

60年代初，Maron在利用概率模型进行文本分类方面做出了开创性的研究工作。

Salton等人在70年代初提出了向量空间模型，由于该模型在良好的统计学方法基础上简明地实现了对文本特性的抽象描述，从而成为文本分类处理的一种经典模型。

其后许多学者在这一领域进行了卓有成效的研究。

国外文本自动分类主要经历了四个发展阶段：第一阶段(1958-1964)：研究文本自动分类的可能性；第二阶段(1965-1974)：进入文本自动分类的实验性阶段；第三阶段(1975-1998)：文本自动分类的实用性阶段；第四阶段(1990-至今)：因特网文本自动分类研究阶段。

国内文本自动分类研究起步较晚，始于20世纪80年代初期。

1981年侯汉清对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。

此后，有越来越多的人借鉴国外的一些研究成果，结合中文的特点进行中文文本自动分类的研究。

中科院计算所的李晓黎、史忠植等人应用概念推理网进行文本分类。

复旦大学的周水庚等人用了N-gram方法对中文文本进行分类尝试，从文档中提取N-gram属性，然后用ON方法判别文本类别，摆脱了对词典和切词处理的依赖，实现文本分类的领域无关性和时间无关性。

刁力力、石纯一等用Boosting 来组合决策树(Stumps)的方法进行文本分类。

卜东波从信息粒度的角度来剖析聚类和分类技术，试图使用信息粒度原理的框架来统一聚类和分类。

庞剑峰等应用向量空问模型进行了中文文本分类实验，并同时对文本分类所涉及的关键性技术，例如特征提取、不同机器学习方法等进行了研究和探讨，给出了评估方法和实验结果。

之后他又验证了在文本分类系统中应用反馈方法的可行性，给出了结合反馈方法的文本分类算法。

1.2.2 SVM研究现状SVM由于分类效果比较好成为近几年人们研究的热点。

SVM是建立在SLT的VC维理论和结构风险最小化原理基础上，根据有限样本信息在模型复杂性(对特定样本的学习精度)和学习能力(无错误地识别样本的能力)之间寻求一种折中，以期达到最佳的推广性能。

1995年，Vapnik在“The Nature of Statistical Learning Theory”一书中提出支持向量机的概念，并在“Support Vector Networks”一文中进行了详细的介绍。

从那以后，关于支持向量机方面的文章如雨后春笋，逐渐成为国际上机器学习领域的研究热点，吸引了国内外众多知名的专家Daniel和Gabriele提出了基于小波的核函数构造方法：Atari和Wu设计了一种算法，他们通过对核函数的黎曼几何分析，提出利用实验数据逐步修正己有的核函数，使之能更好地与实际问题相吻合；Cauwenberghs 和Poggio研究了基于SVM的增量和减量学习问题；Diehl 和Cauwenberghs提出了一个精确增量学习和自适应SVM分类器的框架；Opper和Urban-czik 对SVM学习带噪声的多项式规则进行了研究，在核函数阶数足够高或者为超越函数时，渐近线和学习曲线由目标规则决定而不是核函数，在这种情况下研究了训练误差核推广误差的收敛性；Bordes等提出一种在线SVM算法LASVM，通过对样本的主动选择提高了学习速度；Serifini等研究了基于梯度方法的SVM分解算法中起作用集的选择问题；此外，还有很多学者对SVM的算法进行了研究，这里就不一一列举了。

Joachims和Dumais例等人于1998年开创了SVM在文本分类中应用的先河。

他们各自在不同语料库中做了大量试验，结果表明SVM在文本分类的应用中特别有效，并有很好的泛化性，克服了高维表示中的困难。

此后，很多学者开始了这方面的研究，并取得了很多研究成果。

目前，SVM己被越来越多地应用到模式识别领域，如手写体文字识别、人脸识别等在图像压缩和数据分类的应用中，SVM也显示出了较好的性能。