《基于Web的文本分类挖掘的研究学士学位论文.doc》由会员分享，可在线阅读，更多相关《基于Web的文本分类挖掘的研究学士学位论文.doc（28页珍藏版）》请在三一办公上搜索。
1、首都师范大学学士学位论文基于Web的文本分类挖掘的研究学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检
2、索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日中文提要文本分类最初是应文本信息检索的要求出现的，但是随着文本数据的激增，传统的研究方法己经不适合大规模文本分类，文本数据挖掘应运而生。作为文本数据挖掘的一个重要功能，文本分类技术日益成为研究热点。文本分类目的是对文本集有序组织，便于文本信息高效管理，为人的决策提供支持。但是传统的人工分类的做法存在许多弊端，不仅是耗费大量人力、物和精力，而且受人为因素影响较大，分类结果一致性不高。与之相比，文本自动分类具有快速、高效的特点，且分类准确率较高。对文本分类技
3、术进行研究，介绍文本分类的基本过程，论述文本特征提取方法，讨论朴素贝叶斯、K近邻、支持向量机、投票等常用的文本分类原理与方法，探讨中文文本分类技术。采用支持向量机技术，设计并实现了一个开放的中文文档自动分类系统。实验表明，它不仅具有较高的训练效率，同时能得到很高的分类准确率和查全率。关键词：文本挖掘 文本分类 支持向量机 向量空间模型外文提要Text categorization appears initially for text information retrieval system; however text data increases so fast that traditiona
4、l research methods have been improper for large-scale text categorization. So text data mining emerges, and text categorization becomes more and more important as a major research field of it.The purpose of text categorization is to organize text by order,so as to manage text information efficiently
5、 and support decisions of human being. However categorization by hand not only consumes plenty of manpower, material resources and energy, but also makes categorization accuracy inconsistent. Compared with categorization by hand, automatic text categorization classifies texts faster and its categori
6、zation accuracy rates higher.Introduces the techniques of text categorization, including its basic process ,the algorithms of text feature extraction ,the theories and technologies such as Nave bayes, KNN, SVM, Voted and so on. Chinese text classification is discussed. An open Chinese document class
7、ification system using support is designed and implemented.The experiment shows that it not only improves training efficiency, but also has good precision and recall.Key wordtext mining Text categorization Support Vector Machine(SVM) vector space model目 录中文提要外文提要目 录第一章 绪 论1.1文本自动分类研究的背景和意义1.2问题的描述1.
8、3国内外文本自动分类研究动态第二章 中文文本分类技术研究2.1文本预处理2.1.1文本半结构化2.1.2自动分词2.1.3特征选择122.2分类模型2.2.1贝叶斯（Naive Bayes）方法142.2.2K-近邻（KNN）方法2.2.3决策树（Decision Tree）分类2.2.4基于投票的方法2.2.5支持向量机（SVM）方法172.3分类性能评价第三章 基于支持向量机的中文文本分类3.1统计学习理论3.2支持向量机原理3.3支持向量机的特点第四章基于支持向量机的中文文本分类器的实现4.1系统体系结构4.1.1文本训练模块设计4.1.2文本分类模块设计第五章 系统的性能测试5.1开发
9、环境和数据集5.2测试结果及分析第六章 总结与展望6.1全文总结6.2进一步工作及展望附录（附图）参考文献致 谢第一章 绪 论1.1文本自动分类研究的背景和意义分类最初是应信息检索(Information Retrieval,简称IR)系统的要求而出现的，也是数据挖掘应用领域的重要技术之一1.随着全球计算机与通讯技术的飞速发展、互联网的普及与应用，信息爆炸的现实使人们越来越注重对自动分类的研究，文本自动分类及其相关技术的研究也日益成为一项研究热点。信息检索系统必须操纵大量的文本数据，其文本信息库可能相当庞大。如何在海量文本信息中获取潜在的、有价值的知识，模型或规则,这就需要引入文本数据挖掘概念
10、。数据挖掘是从大量的文本数据中提取出事先未知的、可理解的、可应用的信息和知识的过程。数据挖掘融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术，能够对将来的趋势和行为进行预测，从而很好地支持人们的决策。文本数据挖掘（Textual Data Mining），亦称文本挖掘（Textual Mining），或者从文本数据库中发现知识，以文本数据为特定挖掘对象的数据挖掘，是数据挖掘的扩展。文本挖掘抽取有效、新颖、有用、可理解的、散布在文本文件中的有价值知识，并且利用这些知识更好地组织信息的过程。1998年底，国家重点研究发展规划首批实施项目中明确指出，文本挖掘是“图像、语言、自然语言理解
11、与知识挖掘”中的重要内容。文本挖掘利用智能算法，如神经网络、基于案例的推理、可能性推理等，并结合文字处理技术，分析大量的非结构化文本源（如文档、电子表格、客户电子邮件、问题查询、网页等），抽取或标记关键字概念、文字间的关系，并按照内容对文档进行分类，获取有用的知识和信息。 从目前文本挖掘技术的研究和应用状况来看，从语义的角度来实现文本挖掘的很多，目前研究和应用最多的几种文本挖掘技术有：文档聚类、文档分类和摘要抽取2。（1）文档聚类首先，文档聚类可以发现与某文档相似的一批文档，帮助知识工作者发现相关知识；其次，文档聚类可以将一个文档聚类成若干个类，提供一种组织文档集合的方法；再次，文档聚类还可以
12、生成分类器以对文档进行分类。文本挖掘中的聚类可用于：提供大规模文档集内容的总括；识别隐藏的文档间的相似度；减轻浏览相关、相似信息的过程。聚类方法通常有：层次聚类法、平面划分法、简单贝叶斯聚类法、K-最近邻参照聚类法、分级聚类法、基于概念的文本聚类等。（2）文档分类分类和聚类的区别在于：分类是基于已有的分类体系表的，而聚类则没有分类表，只是基于文档之间的相似度。由于分类体系表一般比较准确、科学地反映了某一个领域的划分情况，所以在信息系统中使用分类的方法，能够让用户手工遍历一个等级分类体系来找到自己需要的信息，达到发现知识的目的，这对于用户刚开始接触一个领域想了解其中的情况，或者用户不能够准确地表
13、达自己的信息需求时特别有用。传统搜索引擎中目录式搜索引擎属于分类的范畴，但是许多目录式搜索引擎都采用人工分类的方法，不仅工作量巨大，而且准确度不高，大大限制了起作用的发挥。另外，用户在检索时往往能得到成千上万篇文档，这让他们在决定哪些是与自己需求相关时会遇到麻烦，如果系统能够将检索结果分门别类地呈现给用户，则显然会减少用户分析检索结果的工作量，这是自动分类的另一个重要应用。文档自动分类一般采用统计方法345678或神经网络91011以及机器学习来实现。常用的方法有：简单贝叶斯分类法， K-最近邻参照分类算法以及支持向量机分类方法等。（3）自动文摘互联网上的文本信息、机构内部的文档及数据库的内容
14、都在成指数级的速度增长，用户在检索信息的时候，可以得到成千上万篇的返回结果，其中许多是与其信息需求无关或关系不大的，如果要剔除这些文档，则必须阅读完全文，这要求用户付出很多劳动，而且效果不好。自动文摘能够生成简短的关于文档内容的指示性信息，将文档的主要内容呈现给用户，以决定是否要阅读文档的原文，这样能够节省大量的浏览时间。简单地说自动文摘就是利用计算机自动地从原始文档中提取全面准确地反映该文档中心内容的简单连贯的短文。自动文摘具有以下特点：1) 自动文摘应能将原文的主题思想或中心内容自动提取出来。2) 文摘应具有概况性、客观性、可理解性和可读性。3) 可适用于任意领域。 按照生成文摘的句子来源
15、，自动文摘方法可以分成两类，一类是完全使用原文中的句子来生成文摘，另一类是可以自动生成句子来表达文档的内容。后者的功能更强大，但在实现的时候，自动生成句子是一个比较复杂的问题，经常出现产生的新句子不能被理解的情况，因此目前大多用的是抽取生成法。利用文本挖掘技术处理大量的文本数据，无疑将给企业带来巨大的商业价值。因此，目前对于文本挖掘的需求非常强烈，文本挖掘技术应用前景广阔。1.2问题的描述文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判别规则，确定文本相关的类别。自动分类的一般做法是，根据文本数据集的
16、特点构造一个分类器，利用分类器对未知类别的文本赋予类别。构造分类器的过程一般分为训练和测试两个步骤。在训练阶段，分析训练数据集的特点，为每一个类别产生一个相应数据集的准确描述或者模型。在测试阶段，利用类别的描述或者模型对测试集合进行分类，测试其分类的准确度。一般来说，测试阶段的代价远远低于训练阶段。文本数据的来源多种多样，可以是报告、单据、新闻、邮件等。文本的类别和数量可以是预订好的，这需要相关专家知识;也可以是不确定的，要经过文本的自组织、聚类后才能得到。需要预先定义类别体系的文本分类为有指导的学习(supervised learning)的分类，也称文本自动分类:类别体系不确定的文本分类为
17、无指导的(unsupervised learning)的分类，也称文本自动聚类(Clustering)。自动聚类系统不需要训练文本，划分出的文本类别也是不确定的。1.3国内外文本自动分类研究动态国外对于文本自动分类的研究开始较早，50年代末，H. P. huhn在这一领域进行了开创性的研究，提出了词频统计思想用于自动分类。1960年，Maron发表了关于自动分类的第一篇论文。随后众多学者在这一领域进行了卓有成效的研究工作，到目前为止，国外的自动分类研究己经从最初的可行性基础研究经历的实验性研究进入到了实用阶段，并在邮件分类、电子会议、信息过滤方面取得了比较广泛的应用，其中比较成功的例子有麻省理
18、工学院为白宫开发的邮件分类系统、卡内基集团为路透社开发的Construe系统等。国内对于文本自动分类的研究起步比较晚，1981年，侯汉清教授对于计算机在文本分类工作中的应用作了探讨，并介绍了国外计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，我国陆续研究出一批计算机辅助分类系统和自动分类系统。例如，广东省中山图书馆的莫少强开发的计算机辅助图书分类系统(C-ABC)、清华大学吴军研制的自动分类系统、山西大学刘开瑛等人开发的金融自动分类系统、东北大学图书馆的图书馆分类专家系统，上海交通大学王永成等研制的基于神经网络优化算法的中文文本自动分类系统。近期研究中比较
19、突出的是中科院的中文文本智多星分类器，它采用多种分类方法。虽然中英文之间存在较大差异，无法直接参照国外的研究成果，但是，随着中文信息处理技术特别是中文自动分词技术的日渐成熟，以此为基础的中文文本分类技术的研究得到了飞速发展，在短短20多年中完成了从可行性探索到实用化阶段的转变。根据分类知识的获取方法不同，可将文本分类系统划分为两种类型:一个是基知识工程的分类系统，一个基于机器学习分类系统。基于知识工程的方法主要依赖语言学知识，一般由知识库和推理机两大基础部分组成。知识库储存了从专家那里获得的关于某领域的专门知识，推理机具有推理的能力，即根据知识推导出结论，而不仅仅是简单搜索现成的答案。由于需要
20、由知识工程师手工编制大量的推理规则作为分类知识，实现相当复杂，因此开发费用相当昂贵。一个典型例子是卡内基集团为路透社开发的Construe系统。该系统的开发工作量达到了10个人年。由此可见，知识工程的方法不适用较为复杂的系统。基于机器学习方法，研究从观测样本出发，寻找规律(即利用一些做好标识的训练数据自动地构造分类器)，利用这些对未来样本进行预测。现有机器学习的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于大数定律的结论。一般情况下，用户对分类要求的准确程度在95%以上，但是因为分类词表和分词算法的不足、分类法的不足、分类算法的不足以及知识库
21、的规模不够大等原因，目前的自动分类系统的准确率主要在80%左右，只有限制在一定的范围内，这些系统才能取得相对好一些的效果，通用的、能够满足大规模商品化应用要求的系统还需要进一步的研究。第二章 中文文本分类技术研究2.1文本预处理2.1.1文本半结构化文本数据与常见的结构化关系数据不同，它是非结构化的，没有属性一值对的结构，称为无结构或者半结构化数据。对于非结构化的文本数据进行挖掘，目前有两种处理途径:一是采用全新的算法，直接对非结构化文本数据进行挖掘;二是将非结构化文本数据进行转化，将其转化为结构化文本数据，再进行挖掘。由于直接构造新算法难度较大，而且开发造价高，实现难度较大，所以目前通常采用
22、人工处理的方法，把非结构化的文本数据转化为结构化的文本数据。2.1.2自动分词自动分词是针对与中文的一种自然语言处理技术。西方语言体系中，句子中各个词汇之间有固定的空格作为分隔，计算机处理时可以非常容易地从文本中识别出一个一个的单词。而在汉语体系中，书写以句子为单位，句间用标点隔开，句内字词则是连续排列的，之间没有任何分隔。因此，如果要对中文文本进行分类、检索等基于词的处理，需要首先对中文文本进行词条切分处理(简称分词)，才能正确识别每个词。中文文本的分词处理就是指在中文文本中连续的能够代表语义单元的词或者n一元词条间加入分隔符，将中文文本的连续字节流形式转化为离散单词流形式的过程。自动分词技
23、术是各种中文信息处理技术的基础，也是中西文研究文本自动分类的主要差别所在，中文文本分类要在自动分词的基础上进行，对中文文本进行分词的过程也是文本特征集的确定过程。2.1.3特征选择12它是指去除不能表示信息的词，以提高分类效率和减少计算复杂度。特征选择有以下几种方法：1根据词的文档频度（DF）来判断：当词的DF小于或者大于某个阈值时都要去掉；2根据信息增益（IG）来判断：信息增益是指词为整个分类所能提供的信息量，当信息增益小于某个预定的值时，就要去掉这个词；3根据2 统计来判断：2 越大，词和类之间的独立性越小，相关性越大，所以去掉2小的词；4根据互信息（MI）来判断：互信息越大，两个词之间的
24、共现性就越大；5根据词的强度（TS）来判断。通过试验证明，前三种更加有效。特征选择可以在两个方面提高系统性能:一是分类速度，通过特征选择，可以大大减少特征集合中的特征数，降低文本向量的特征数，提高系统运行速度。二是准确度，通过适当的特征选择，不但不会降低系统准确性，反而会使统精确度提高132.2分类模型2.2.1贝叶斯（Naive Bayes）方法14 朴素贝叶斯分类器利用下列贝叶斯公式通过类别的先验概率和词的分布来计算未知文本属于某一类别的概率：P(CjD)=其中，P(CjD)为样本D 属于类Cj的概率，P(DCj)为类Cj中含有样本D 的概率。在所有P(CjD)(j=1,2,m)中，若P（
25、CKD）值最大，则文本D 归为CK类。由于P（D）是常数，因此将要求解P(CjD)的问题转换为只要求解P(Cj)P(DCj)。假设文本中词的分布是条件独立的，则P(CjD)= P(Cj)P(DCj). 其中，P(Cj)= ；P(diCj)= 尽管词的分布是条件独立的这个假设在实际文本中是不成立的，但在实际应用中NP分类器一般都能取得相对较好的结果。从理论上讲，贝叶斯分类的出错率最小，就试验结果来看，朴素贝叶斯在大型的数据集上表现出来难得的速度和准确度。152.2.2K-近邻（KNN）方法KNN方法是一种基于实例的文本分类方法。首先，对于一个待分类文本，计算它与训练样本集中每个文本的文本相似度，
26、根据文本相似度找出K 个最相似的训练文本。这最相似的K个文本按其和待分类文本的相似度高低对类别予以加权平均，从而预测待分类文本的类别。其中最重要的是参数K的选择，K 过小，不能充分体现待分类文本的特点；而K 过大，会造成噪声增加而导致分类效果降低。文本向量D 属于类别Ci的权值W(CiD)由下式计算，权值越高，认为文本向量D属于类别Ci 的概率越高：W(CiD)=其中，S(D,Dj)是向量之间的余弦相似度；D1 Dk是训练集中与D余弦相似度最大的K个文本向量；而P(CiDj)当Dj属于类别Ci时为1，否则为0。通过上面的分析可知，KNN 的实质就是以特征属性权值作为特征空间的坐标系测度，先计算
27、测试集与训练集之间在该坐标系中的余弦距离，然后根据测试集与训练集的距离远近来确定类别。显然，它没有考虑特征属性关联及共现等因素对文本相似度的影响，如果加以恰当地考虑，KNN 的效果会更好。KNN16是一种懒散的方法，即它没有学习过程，只是存放所有的训练例，直到接到未知文本的时候刁建立分类。KNN的训练过程较快，而且可以随时添加或更新训练例来调整。但因为需要很大的空间来保存训练例，因此其分类的开销会很大。 2.2.3决策树（Decision Tree）分类决策树是一种常用数据分类技术，同样适用于文本分类。决策树的核心算法是一种贪心算法，它以自顶向下的方式在训练集的基础上构造决策树，之后取未知文本
28、的属性在决策树上测试，路径由根结点到叶结点，从而得到该文本的所属类别。决策树的建立算法有多种，其中包括：基于信息增益的启发式算法ID3；基于信息增益率的解决连续属性分类的算法C4.5；基于Gini数的算法CART；针对大样本集的可伸缩算法SLIQ；可并行化算法SPRINT；将建树和剪枝集成到一起的算法PBULIC。他们的区别在于构造决策树与树枝剪除的算法细节不同。决策树可以很好的抵抗噪声。最大的缺点在于不适应大规模的数据集，此种情况下决策树的构造会变得效率低下。2.2.4基于投票的方法在研究多分类器组合时提出了投票算法，其核心思想是：n个专家判断的有效组合应该优于某个专家个人的判断。投票算法主
29、要有两种：Bagging 算法和Boosting 算法。1) Bagging 算法。训练R 个分类器=f.i，i=1,2,R分类器之间只是参数不同。其中fi是通过从训练集（N 篇文档）中随机取（取后放回）N 次文档构成的训练集合训练得到的。对于新文档D，用这R 个分类器去分类，得到的最多的那个类别作为D的最终类别。2) Boosting 算法。类似Bagging 算法，但分类器的组合方式是级联的，前一级分类器为后一级分类器提供分类信息，指导下一级分类器的训练和分类过程。下面介绍一种Boosting算法AdaBoosting。R次循环，每次循环训练K 个分类器。设第r次循环中类标签为Ck的样本D
30、i权重为P.ikr，所有权重的初始值都是相等的。每一次循环，AdaBoost 算法估计K个分类器fr（ D,k），k=1,2,K，并对分类错误的样本加大权重。fr（ D,k）反映训练样本Di的类标签是否是Ck，而它的大小被认为是衡量预测的信度。用以下公式来更新权重：pik(r+1)=pikrexp(-yikfr(Di,k)如果Ck是样本Di的可能类标签中的一个，那么yik=1，否则yik=-1,。将权重重整，使得pik(r+1)=1。这个过程循环R 次之后，得到R*K 个fr（ D,K）。然后用这所有的分类器对样本集D 进行分类，D的最终分类器f（D，K）为： f(D,k)= 2.2.5支持向
31、量机（SVM）方法17支持向量机（SVM）是一种建立在统计学习理论基础上的机器学习方法。通过学习，SVM 可以自动寻找那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类之间的间隔， 因而有较好的推广性能和较高的分类精确率。SVM 已被用于文本分类、孤立的手写体识别、语音识别、人脸识别、三维物体识别、遥感图像分析等。2.3分类性能评价文本分类效果可以从准确率、查全率、遗漏率、正确率、错误率五个方面评估。假设:a表示判为C类且确实属于C类的文本数目;b表示判为C类且但实际不属于C类的文本数目;c表示判为非C类且确实不属于C类的文本数目;d表示判为非C类且但实际上却属于C类的文本数目
32、;a+d表示实际属于C类的文本数目:b+c表示实际不属于C类的文本数目;可以定义:准确率=a/(a+b)查全率=a/(a+d)遗漏率=b/(b+c)正确率= (a+c)/n， n=a+b+c+d错误率= (b+d)/n， n=a+b+c+d因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是映射的准确程度和映射的速度。所以，文本分类系统的最重要的两个指标是:准确率(precise)和查全率(recall)。准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废，因此，存在一种新的评估指标，F1测试值，其数学公式如下:F1测试值=另外有微平均和宏平均两种计算准确率、
33、查全率和F1测试值的方法。微平均:计算每一类的准确率、查全率和F1测试值。宏平均:计算全部类的准确率、查全率和F1测试值第三章 基于支持向量机的中文文本分类3.1 统计学习理论机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。可以一般地表示为:变量Y与x之间存在一定的未知依赖关系，即遵循某一未知的联合概率F(x,y)，则机器学习问题就是根据n个独立同分布的观测样本（x1,y1）,(x2,y2),，(xn,yn)在一组函数f(x,w)中求一个最优的函数f(x,w0)对依赖关系进行估计，使期望风险：R(w)=L(y,f(x, w)dF(
34、x,y)（3-1）最小。其中， f(x,w)称作预测函数集，w为函数的广义参数，L(y,f(x,w)为由于用f(x,w)对y进行预测而造成的损失。预测函数也称作学习函数、学习模型或学习机器。由于期望风险是预测函数在整个样本空间上的出错率的数学期望，因此要使式(3-1)最小化必须依赖于联合概率F(x,y)的信息。但是，在实际的机器学习问题中这一要求太强，样本集的分布函数往往难以预知，这使得期望风险无法直接计算和最小化。因此传统的学习方法采用了所谓经验风险最小化(Empirical Risk Minimization,简称ERM)准则，即定义经验风险:Remp(w)= L(yi f (xi, w)
35、 (3-2)来作为对期望风险的估计，并设计学习算法使它最小化。ERM准则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均出错率，用于对整个样本集的期望风险进行估计。它建立在样本数目足够多的前提下，所提出的各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的效果18 Vapnik的研究指出，使用经验风险最小化方法得到的学习结果，其风险与期望风险之间至少以概率1-满足如下关系19 :R(w)Remp(w)+,(3-3)其中h是函数集的VC维(VC维是Vapnik-Chervonenkis维的缩写)，n是样
36、本数。VC维概念是统计学习理论的一个核心概念，它是描述函数集的复杂性或学习能力的一个重要指标。这一结论从理论上说明了学习机器的实际风险是由两部分组成的:一是经验风险(即训练误差)，另一部分称作置信范围，它和学习机器的VC维及训练样本数有关。式(3-3)可以简单地表示为:R(w) Remp (w) +(h/n)， (3-4)它表明，如果对于一个给定数目的训练集，我们设计了一个过于复杂的学习机，则置信范围(h/n)将会很大。这时，即使我们可以把经验风险最小化为零，在测试集上的错误数目仍可能很大。这就是为什么会出现“过学习”现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽可能小以缩小置信
37、范围，才能取得较小的实际风险，即对未来样本有较好的推广性。从上面的结论可以看到，ERM 原则在样本有限时是不合理的，我们需要同时最小化经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如果模型比较适合现有的训练样本(相当于h/n的值适当)，则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用者“技巧”的过分依赖。为此，统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照VC维的大小(亦即的大小)排列。在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，以取得实际风
38、险的最小值，这种思想称作结构风险最小化准则(SRM )，如图2-1所示20统计学习理论还给出了合理的函数子集结构应满足的条件，以及在SRM准则下实际风险收敛的性质21 置信风险经验风险真实风险的界 S3 S2S1风险h欠学习过学习函数集子集：维：图3-1结构风险最小化示意图实现SRM原则可以有两种思路，一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。因此有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0)，然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小
39、的函数就是最优函数。支持向量机方法实际上就是这种思想的具体体现。3.2支持向量机原理-margin图3-2 特征空间中的最优分割平面如图3-2，考虑一个用某特征空间的超平面对给定训练数据集做二值分类的问题。对于给定样本点： （1）其中向量可能是从对象样本集抽取某些特征直接构造的向量，也可能是原始向量通过某个核函数映射到核空间中的映射向量。在特征空间中构造分割平面: （2）使得：（3）可以计算出，训练数据集到一给定的分割平面的最小距离为：（4）根据SVM对优化分割平面的定义，可以看出对该平面的求解问题可以简化为：在满足条件式（3）的情况下，计算能最大化的分割平面的法向量和偏移量。Vapnik等人
40、证明：分割超平面的法向量是所有训练集向量的线性组合。即可以描述为： （5）定义判别函数（6）则测试集的分类函数可以描述为： （7）由（3）式可知，在线性可分的情形下，对所有的训练样本都应该满足，在下文中，我们把满足的区域称为分割超平面所对应的边界区域。在多数情况下（5）式的展开式中，系数为零值，而非零值的对应的就称为支持向量SV。这些向量充分描述了整个训练数据集数据的特征，使得对SV集的线性划分等价于对整个数据集的分割。由（4）式可见，最优分割平面的求解等价于在（3）式约束下最大化下面的（8）式（8）引入拉格朗日乘子，并定义（9）使用Wolfe对偶定理把上述问题转化为其对偶问题：（10）对于线
41、性不可分的训练集，可以引入松弛变量，把（8）式改写为下面的求解问题3。 (11)类似的可以得到相应的对偶问题：（12）形如式（10）、（12）的求解是一个典型的有约束的二次型优化问题，已经有了很多成熟的求解算法，近年来，V. Vapnik, C. Burges, E. Osuna, T. Joachims, J. Platt等人的一系列工作使得对大规模训练集的支持向量机算法实现成为可能。3.3支持向量机的特点从统计学习理论和支持向量机算法原理不难看出，支持向量机具有以下特点：1)支持向量算法是基于统计学习理论的结构风险最小化原则的，与传统的算法不同，它不仅优化经验风险，而且通过最大化分界面来控
42、制模型的复杂度，从而有效地避免了过学习现象，为模型选择问题提供了很好的思路。2)它是专门针对有限样本情况的，不仅仅是样本数趋于无穷大时的最优值其目标是得到现有信息下的最优解而3)训练算法最终将转化成为一个二次型寻优间题，从理论上说，得到的将是全局最优解，解决了在神经网络方法中存在的局部极值问题。4)算法将输入空间中的训练样本通过非线性变换转换到高维的特征空间中，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，并能保证机器有较好的泛化能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关第四章基于支持向量机的中文文本分类器的实现本章根据上述文本分类器模型实现了一个中文文本自动分
43、类系统，下面，本文将以该系统为基础对在前几章中所讨论的问题进行试验测试。 4.1 系统体系结构图4-1给出了本文研究的文本自动分类系统模型。该分类系统主要由训练模块和分类模块组成，分别对应文本分类的训练和识别这2个阶段。训练模块是对训练样本进行预处理、特征选择和提取、参数训练，生成分类知识库;分类模块首先对要分类的样本进行预处理、特征提取，然后用训练得到的分类知识库通过分类算法对样本进行自动分类。训练文本集分词处理器向量及其权重计算规范化文本特征向量分类器分词处理器规范化文本特征向量向量及其权重计算测试文本集词典词典分类结果训练模块分类模块图4-1 基于支持向量机的文本分类系统 4.1.1文本
44、训练模块设计在训练模块中，首先对训练文本进行分词处理，然后进入训练分类器的过程,把训练文本集中的文本由连续的字符流转换成带有分隔符的原始文本特征集;然后对原始文本特征集计算其特征的权重，并规范化类别特征，得到规范化训练集的向量空间模型。文件train.mdl和train.txt为训练文档的向量形式。同样，前一个为二进制格式，分类时会读入此文件，后一个为文本格式，只是为类让用户看到文档的向量形式，分类程序不会用到此文件。如： 1 23:0.074294 35:0.018632 50:0.073530 第一列代表文档所属类别，注意它的类别编号从1开始，而0代表文档的类别未知。剩余部分长度不定，格式
45、为XX:YY，XX代表向量的第XX维(维的编码从1开始)，YY代表这一维的权重(0-1之间)。4.1.2文本分类模块设计在分类模块中，同样先对测试文本进行分词处理和特征值提取，将测试文本进行向量表示，将文本特征向量输入分类器，利用已充分学习的支持向量机和类别特征向量，对待分类文本进行分类。通过上面的学习过程，我们己经得到了支持向量机判别函数的参数，可以用判别函数对文本进行分类。分类步骤如下所示:(1)读取一个待分类文本。(2)对该文本进行分词，得到特征词的出现频率。(3)利用特征词抽取模块，过滤停用词和出现频率低的词，得到粗特征。(4)采用公式对特征词的权值进行计算。(5)对特征值进行归一化(6)计算所有类别w的判别函数(7)如果还有待
