文本分类系统的设计与实现_高亚波

北京交通大学 硕士学位论文 文本分类系统的设计与实现 姓名：高亚波 申请学位级别：硕士 专业：软件工程 指导教师：范辉 20080601 中文摘要 摘要：随着计算机的普及以及互联网的不断发展，越来越多的电子文档堆积成了 海量的数据，如何对这些海量数据进行管理以为用户快速的检索信息提供方便成 为数据挖掘研究的一个核心。文本分类技术针对这个问题，提出了一系列解决方 案。文本分类是一项重要的智能信息处理技术，在信息过滤、信息检索、文本数 据库和数字图书馆等方面极具应用价值。本文介绍了文本分类技术及其相关算法， 利用软件工程的思想设计并实现了一个文本分类系统。系统分为六个模块：(1)文 本预处理模块，针对文档进行分词，停用词过滤；(2)词频统计模块，按照各种分 类算法以及特征选择算法的特点统计文档中特征词的出现频率；(3)特征选择模块， 实现了信息增益0G)、互信息(M1)、交叉熵(cE)、x|~2统计四种特征选择算法；(4) 权重计算模块，实现TF、TF．IDF算法；(5)分类器算法模块，实现了朴素贝叶斯 (NB)和K近邻文本分类(KNN)算法；(6)分类器评价模块，实现了对分类器 从查全率、查准率和Fl值三个方面进行评价的机制。结合软件测试理论利用该系 统进行了：KNN算法中k值对分类效果的影响，KNN算法下不同特征选择算法对 分类效果的影响，NB算法与KNN算法分类效果比较这三个实验；通过这些实验 对系统进行了测试，并从测试结果中得到了一些结论。 关键词：文本分类；空间向量模型；特征选择；权重计算；朴素贝叶斯；K最近 邻算法 分类号：TP311．5 ABSTRACT： ABSTRACT WiththepopularityofcomputersandthecontinualdevelopmentofInternet，more andmoreelectronicdocumentshavebecomeaccumulationofhugevolumesofdata． HowtomanagethesemassivedatainordertoprovidefacilitationforUSerStosearch quicklyhasbecomeacoreofknowledgediscoveryindatabases(KDD)．Addressingthis issue，textcategorizationtechnologyhasproposeda seriesofsolutions．Text categorizationisanimportantintelligenceinformationprocessingtechnology．This technologyhashighvalueininformationfiltering,informationretrieval，textdatabases， digitallibraries．andotheraspects．Thearticleintroducesthetextcategorization technologyanditsrelatedalgorithms．Atextcategorizationsystemisdesignedand implemented．ThisSystemisdividedintosixmodules：(1)Textpreprocessor,slicingthe wordsinthedocument，filteringthestop-word；(2)frequencystatisticsmodule，counting thefrequencyofcharacteristicWordsaccordingtovariousclassificationalgorithmsand characteristicsoffeatureselectionalgorithm；(3)Featureselectionmodule，achievingthe informationgain(IG)，mutualinformation(MI)，cross—entropy(CE)，andX一2statistics thesefourfeatureselectionalgorithm；(4)weightcalculation，achievingaTF'TF—IDF algorithm；(5)theclassificationalgorithm，achievingtheBayesianandKneighborstext classificationalgorithm；(6)classifierevaluationmodule，achievingtheclassification performance’Sevaluationmechanismfromtherecallrate，check-rateandvalueofF1． Threeexperimentshavebeendonebyusingthissystem：kvalue’Saffectsonthe classificationintheKNNalgorithm，differentfeatureselectionalgorithms’effectson theclassificationunderKNNalgorithm，thecomparisonofNBalgorithmandKNN classificationalgorithm．Someconclusionshavebeendrawfromtheexperiments． KEYWORDS：textcategorization；vectorspacemodel；featureselection；weight calculation；naiveBayesian；Knearestneighboralgorithm CI．ASSNO：TP311．5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 (保密的学位论文在解密后适用本授权说明) 学位论文作者签名：南生波 导师签名．兹老务 签字日期："i／I。‘年6月了日 签字日期：1刃g年6月；17t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：南欠设 签字日期： V口暑年6月多日 37 致谢 本论文的工作是在我的导师范辉副教授的悉心指导下完成的，范老师严谨的 治学态度和科学的工作 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 给了我极大的帮助和影响。在此衷心感谢两年来范老 师对我的关心和指导。 林永民老师对我的科研工作和论文提出了许多宝贵意见，在此表示衷心的感 谢。 在撰写论文期间，徐辉、李平等同学对我论文中的分类算法研究和实现工作 给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 1引言 近年来，随着电脑的普及和互联网的不断发展，大量的电子数据涌现出来。 如何在海量数据中检索到对用户有用的信息成为一个研究课题。在这样一个趋势 下，传统的靠人工的信息处理方式已经无法适应日益增加的大量数据处理的需求。 于是，一批新型的以数据挖掘为核心理论的技术，比如搜索引擎，垃圾邮件过滤 等等涌现出来。这些技术将传统的数据分析方法与处理大量数据的复杂算法结合 起来，在商务智能应用如：顾客分析、定向营销、工作流管理等以及医学、科学 与工程方面如：地球气候系统、蛋白质结构预测、多序列校准、生物化学路径建 模和种系发生学等方面发挥着重要的作用¨】。归纳一下：数据挖掘技术现在的应用 主要体现在分类、关联分析、聚类、异常检测这几个方面，文本分类技术正是数 据挖掘中分类算法的一个应用。 1．1项目背景及意义 2008年1月《中国互联网络发展状况统计报告》内容显示：互联网基础资源 增长迅猛，年增长率均超过38％，尤其是域名、网站和网页数量，年增长率均超 过了60％。中国域名总数是1193万个，年增长率达到190．4％。增长的主要拉动因 素来自CN域名，CN域名数量已达到900万个，比2006年同期增长了接近4倍。 中国网站数量已有150万。这些网站中增长最快的是．CN下的网站数，目前的数量 已经达到100．6万个，．CN下网站首次超过百万，占到中国网站数量的66．9％。中 国网页总数已经有84．7亿个，年增长率达到89．4％，是2007年互联网基础资源中 增长最快的一项，互联网上的信息资源数量日趋丰富。在这些信息中，大部分是 结构化或半结构化的文本信息。用户希望获得越来越多的信息，并能够准确地找 到自己所需要的信息。对信息进行有效的分类是迅速有效的获取信息的第一步工 作。文本分类是根据给定文本的内容将其判别为事先确定的若干个文本类别中的 某一类或者某几类的过程，为对文档按类别进行统一存储、检索打下基础。因此， 迅速地对文本进行分类己成为一项重要的研究课题。文本分类技术的研究目标就 是实现文本分类的自动化，以达到降低传统分类技术的人工费用，提高分类效率 和性能等目的。文本分类作为信息检索、信息过滤、文本数据库、数字化图书馆 等领域的技术基础，有着广阔的应用前景。 1．信息检索 文本分类最早应用在信息检索领域，把大量的文本信息按主题层次归类组织 极大地简化对信息的检索。如果按照类别对文本进行检索或对检索结果进行文本 分类，都可以提高检索的查准率。 2．信息过滤 网络的发展与普及，大大方便了我们获取信息。但信息量之大给人们对信息 的处理带来了很大困难，无法快速地得到用户所需的信息，同时还会带来一些反 面的信息。信息过滤技术可以解决这些问题。信息过滤本质上是一个两类分类问 题，既可以将用户反感的信息过滤掉，也可以将用户感兴趣的信息过滤出来，主 动地推送给用户。现在较典型的应用就是邮件过滤。 3．文本数据库 随着研究的深入，文本数据库的功能己经不再局限于存储、组织和查询文本 信息，而是要提供多层次的服务，如文本挖掘。文本分类技术不仅对文本数据库 如何存储、组织具有重要的意义，而且也是文本挖掘的重要内容。 4．数字图书馆 图书馆的数字化管理是大势所趋，图书期刊 全文 企业安全文化建设方案企业安全文化建设导则安全文明施工及保证措施创建安全文明校园实施方案创建安全文明工地监理工作情况 数字化的比重正日益增大。 对图书归类时，使用自动文本分类技术，可以正确地把图书资料进行迅速归类。 文本分类的研究历史可以追溯到20世纪50年代，美国的H．ELuhn提出了词 频统计思想，在这一领域进行了开创性的研究。肖明博士对此做了大量的分析和 总结，他把文本分类分为四个发展阶段：第一阶段(1958—1964)，研究文本自动分 类的可能性；第二阶段(1965．1974)，进入自动分类的试验性阶段；第三阶段 (1975．1989)，自动分类的实用性阶段；第四阶段(1990至今)，因特网自动分类 的研究阶段。长期以来，文本分类都是自然语言处理的一个重要应用领域。但直 到八十年代末，在文本分类方面占主导地位的一直是基于知识工程的分类方法， 即采用人工方式来构建分类器，需要专业人员手工编写分类规则指导分类。著名 的国际网站yahoo雇用了一百多名领域专家，即使满负荷的工作，也不能及时地 对每天像潮水般涌现在互联网上的新网页进行阅读、标注和分类。这一时期最著 名的系统是为路透社(Reuters)开发的Construe系统和Chureh95系统。九十年代以 后，随着电子文本的大量出现，基于机器学习的自动文本分类系统开始兴起，其 效果明显超过知识工程方法，成为信息系统学科最重要的研究领域之一。目前， 自动文本分类技术己经成为机器学习技术和信息检索技术的交汇点和结合点，成 为所有基于内容的自动文本管理技术的重要基础。相关学者已经提出了多种分类 方法，如KNN、回归模型、支持向量机、最大熵模型1等，研究了一些相当成功 的分类系统，建立了OHSUMED，Reuters等开放的分类语料库。 国内文本分类的研究起步相对较晚，开始于80年代初期，经历了可行性分析、 辅助分类系统和自动分类系统三个阶段。1981年，侯汉清首先对计算机在文献分 2 类工作中的应用作了探讨。目前，国内有包括清华大学、中国科学院、复旦大学、 上海交通大学、东北大学等多家单位从事该领域的研究，已经陆续研制出了一批 计算机辅助分类系统和自动分类系统，较好的是由中科院开发的智多星心】。 实现本系统的目的是提供一个开源的分类平台，为不同分类需求提供通用的 组件，核心为分类算法以及特征选择算法。 1．2基于本文进行的主要工作 ◆ ● ● ● 研究了数据挖掘理论，尤其研究了分类算法：简单有效的决策树归纳算法， 基于规则的分类技术，基于消极学习方法的K最邻近分类算法，基于对属性 集和类变量的概率关系进行建模的贝叶斯算法以及神经网络算法和支持向量 机。 研究了常用的特征选择算法，包括文档频率(DF)，互信息(MI)，信息增益 (IG)、开方统计(X~2)、交叉熵(CE)等。 设计并实现文本分类系统，利用python语言实现文本分类系统，该系统提供 了良好的用户接口，为用户提供了算法实验的平台，在利用router-21578语 料库进行的分类实验中表现出了良好的性能。系统分为预处理模块、词频统 计模块、特征选择模块、特征权重模块，分类器算法模块、结果评价模块。 其中特征选择模块实现了MI、IG、X～2、CE等算法，分类器算法模块实现 了K最邻近分类算法(1心烈)和朴素贝叶斯分类算法(NB)。 针对文本分类系统进行了三个测试： KNN算法中K值对分类效果的影响； KNN算法下不同特征选择算法对分类效果的影响；KNN算法与朴素贝叶斯 算法(NB)的比较；并对测试结果进行了分析，得到一些结论。 1．3本文的组织结构和内容概要 本文共分5章，具体章节安排如下： 第1章：引言，指出本文研究的背景和意义，给出文本分类的问题描述，介绍 国内外研究历史与现状，最后介绍了本文的主要工作。 第2章：文本分类技术及相关算法，分析了文本分类系统的工作原理，并根据 工作原理从文本预处理，文本表示、特征选择算法、特征权重算法、文本相似度 计算、常用分类算法、以及分类器的评估等几个方面进行阐述。 第3章：文本分类系统的设计与实现，根据第二章介绍的原理分模块讲解系统 的设计和实现。 3 第4章：测试与结果分析，对第三章设计的系统，进行了KNN算法中K值对 分类效果的影响，KNN算法下不同特征选择算法对分类效果的影响，NB算法与 KNN算法分类效果比较。 第5章：总结全文，指出本文研究的不足，确定将来的研究方向。 4 2文本分类技术及相关算法 2．1文本分类系统的工作原理 图2．卜l文本分类系统工作原理 Figure2．1—1theprincipleoftextcategorizesystem 如图2．1．1所示，文本分类过程宏观上分为文本表示过程、训练过程、分类过 程。首先，对文本进行预处理，将文本用模型表示，进行词频统计，然后进行特 征提取并构造训练分类器，最后对测试文档应用分类得到分类结果，第二章其余 节以及第三章将分别介绍这个过程的理论基础和实现方案。 2．2文本预处理 2．2．1 文本分类数据的特点 文本分类就是将大量文本划分为一个或一组类别，使得各个类别代表不同的 概念主题。文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以 应用到文本分类中。但文本分类同时又是模式分类和自然语言处理的一个交叉学 科，是和文本的语义紧密相关的，所以与普通的模式分类任务相比有许多独特之 处： 5 1．高维特征空间 在文档特征选择的时候，有大量的候选特征。如果使用词语作为文档特征， 一个接近2000篇的训练文档集，一般会产生两三万的候选特征。 2．特征语义问题 文本分类中很多特征之间是彼此相关的。人类语言中有很多的同义词，多 义词，动名词，也造成对特征与类别定位的困难。 3．特征分布稀疏 在一个大型语料库中统计一种语言中每个单词类型出现的次数、出现的文 本频率，然后进行特征选择，而特征选择的原则就是尽可能的使用类别区分度 大的文本预处理的特征选择算法，这样相对于整个语料集的特征向量，每篇文 档中的特征就很少了，从而造成特征分布稀疏。 2．2．2 停用词处理 掉。 停用词是指在文档中普遍存在的对文档分类没有帮助的词。主要有以下几类： · 助词中文中的“的，得，地”，英文中的“of，，等。 · 副词中文中的“尤其，特别”，英文中的“really”。 ●连词中文中的“是"，英文中的“anl，is，are"。 ·冠词中文中的“我"，英文中的“my，mine，you，your"。 ·指示词中文中的“这，那"，英文中的“the，these，those"。 ●介词中文中的“从，到，在”，英文中的“from，to，on，at”。 ·疑问词中文中的“为什么，哪里”，英文中的“which，what，how"。 这些词对分类没有贡献，反而增加了噪音，因此在文本预处理时就可以过滤 2．3文本表示(向量空间模型) 将文档进行合理的数学抽象建模是下一步运用传统的模式分类算法的基础。 文本是一个由众多字符构成的字符串，文本的类别是从语义上来说的，而文本对 语义的表达是通过句子，句子的含义是通过词语表达的，因此可以直接选择词语 作为文本类别的表示，这样就将文档的含义离散化为词，然而不同的词对文档类 别具有不同的贡献度，利用特征权重算法可以计算出词汇在文档的贡献度。文本 特征表示是指以一定特征项(词汇)来代表文本，在文本分类时只需对这些特征 项进行处理，从而实现对非结构化文本的处理。现有文本分类技术的前提假设是 6 特征和文本类别概念密切相关，特征表示模型有多种，常用的特征表示是向量空 间模型。 向量空间模型(VectorSpaceModel)是由GerardSalton和MeGill于1969年提 出，并最早成功应用于信息检索领域，后来又在文本分类领域得到了广泛的运用。 向量空间模型的一个基本假设是，一份文本所属的类别仅与某些特定的单词或词 组在该文档中出现的频数有关，而与这些单词或词组在该文本中出现的位置或顺 序无关。也就是说，如果将构成文本的各种语义单位(如单词、词组)统称为“特征 项”，以及特征项在文本中出现的次数称为“词频"，那么一份文本中蕴涵的各个 特征项的频率信息足以用来对其进行正确的分类。向量空间模型中，一个文本表 示为特征空间中的一个向量，这个向量也称为文本向量。文本向量中每一维对应 于文本中的一个特征，它的权重为该向量维对应的特征在文本中的权重，一般采 用TF．IDF方法计算。KNN、支持向量机(SVM)和NB都是基于向量空间模型的。 其中布尔模型是向量空间模型的一种特例，该模型根据特征是否在文本中出现， 特征的权重只能取1或0t61。 一个向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一 致，并可以通过向量空间进行描述。下面介绍一下文档向量空间相关基本概念： (1)特征：指出现在文档中并能表示该文档特点的基本语言单位(如英文等西方 语言中的单词，汉语、日语等语言中的字和词、词组)。在信息检索中，特征就相 当于检索词。向量空问模型中一般取词作为特征，也有研究者使用汉字、概念等 作为特征构造向量模型的。这样文档D就可以由该文档中的所有特征来表示： D(‘t：⋯乙)，其中，气是文档D中第k个特征词，n表示文档D中词的个数， 这样自然语言形式的文本文档就可以在向量空间中完全由特征来表示。 (2)文档：向量空间中的文档是指计算机中存储的文本文件或文件中的一个片段 (如文件中的标题、摘要、正文等)。 (3)特征项权重：指特征项代表文档D能力的大小，它体现了该特征项在文档 D中的重要程度。这样文档D就可以由一个n元的特征向量来表示，即表示为 (wlw2⋯wk)，其中w分别代表文档D特征项(‘f2⋯如)的特征项权重。 向量空间模型将每一个不同的词条都看成是特征空间中独立的一维，将每一个文 档看作为特征空间中的一个向量D((f。M)(t2w2)⋯(tk％))。 (4)文档相似度计算：对两个文档4，d，，相似度表征了这两个文档类别相近 程度的量化值。常用的相似度计算方法是建立在文档向量表示上，假设谚的文档 向量表示为(w。w：⋯‰)，嘭的文档向量表示为(w，。一：⋯喙)，则相似 度可以用如下两种方法量化： ● 向量内积： 7 k sim(d，，d,)--∑％·％(2．3-1) i=l ● 向量央角： 2．4特征选择算法 (2．3—2) 在文本分类系统中，在对文本进行分词、过滤停用词等处理后，得到的词仍 然很多，向量空间的维度和词空间的维度是一样的；这是一个高维度的空间。由 于文本的特点，每个文本中出现的词相对于整个语料集的词汇很少，所以每篇文 档的文本特征是稀疏的。这样的向量空间会在时间和空间上影响分类系统的性能。 因此需要对文本特征进行筛选，选择出能够很好代表文本类别的词作为特征向量， 这个过程就是特征选择的过程。好的特征选择算法可以通过降低向量空间的维度 提高分类系统的性能。特征选择的一般步骤如下： (1)利用特征选择算法为在预处理后得到的文档的词进行打分。 (2)把词按照特征选择算法得分由高到低排序 (3)从第二步中排序的词列表中提取前N个作为分类的特征向量，其中N 为提前设定的特征向量的维度。 2．4．1 文档频率(DF) 它是最简单的文本特征选择方法，其值为训练集合中此单词发生的文档数。 文档频率DF的理论假设是：稀有单词要么不含有用信息，要么太少而不足以对分 类产生影响，要么是噪音，所以可以删去。显然它在计算量上要比其他的特征选 择方法小得多，但是在实际运用中它的效果却出奇的好。DF也有缺点，因为稀有 单词可能在某一类文本中并不稀有，而且包含重要的判断信息。我们在实际运用 中一般并不直接使用DF，而常把它作为评判其它方法的准则。 2．4．2 信息增益(IG) 信息增益法是一种在机器学习领域应用较为广泛的特征选择方法，它从信息 沁i∞、，勰．，糯M＆黼既 论角度出发，根据各特征取值情况来划分学习样本空间时，所获得信息增益的多 少来选择相应的特征，特征F的信息增益InfGain(F)计算公式如下： 蛳郴Ⅳ(矿)莩粥㈣l092等 棚)；P(C：I嘶：等 (2．4二。) 其中F是对应于单词形的特征，P(，形)为单词形出现的概率，P化)为第 f类出现的概率，P鸺I∥)为单词形出现时属于i类的条件概率(pA-F含义同)‘31。 2．4．3 互信息(MI) 互信息用于表征特征词矿与类别Cf间的相关性，其公式为 胁加蚴砌(尸)=∑iP(C：f)log马幂≠(2-4．3-1) 互信息没有考虑单词W发生的频度，这是互信息一个很大的缺点，它导致互 信息评估函数经常倾向于选择稀有词[31。 2．4．4 X~2统计(X~2) x2cF，=军二!!二二三三三一c2．4．4， 2．4．5 交叉熵(CE) 它与信息增益唯一的不同之处在于没有考虑单词未发生时的情况，其公式 为[31： ㈣砂郴)．P(缈)∑i粥mg：等(2．4．5) 9 2．5特征权重算法 在文本向量空间模型中，词是文本的特征单位，利用特征选择算法从这些词中 选出最能代表文本特征的词，并按照特征权重算法赋予该特征相应的权重，以反 映该特征项对标识文本内容的贡献度和文本内容之间的区分能力。 确定特征项在文档中的权重，大多考虑了以下两个经验性的因素： (1)一个特征项(词)在某文档中出现的次数越多，那么它和该文档的主题越 相关，对文档的区分能力越强。 (2)一个特征项(词)在文档集中出现的次数越多，则它对各文档区分的能 力就越小。 基于以上两条经验，下面介绍三种加权策略，其中i表示特征项，K表示文 档K，娠表示特征项i在文档k中的频率，％表示特征项i在文档k中的权重，N 表示训练集中文档总数，M表示训练集中包含特征项i的文档数： (1)布尔加权法(Booleanweighting) 这种方法不考虑特征项出现的频率，只考虑特征项出现与否，数学抽象如 下： W玻={：)‰刈(2．5_1) (2)词频加权法 该方法利用特征项在文档中出现的频率作为特征权重，这种加权法的缺 点是没有考虑词的文档频率，容易导致噪音词汇权重过高： (3)TF—IDF加权法 基于以上两种加权法的缺点，TF-IDF加权法综合考虑了特征项在单独文 档中出现的频率和特征项在文档集中出现的频率。基本思想是认为，特 征项权重与特征项在文档i中出现的频率成正比，与特征项在文档集中出 现的频率成反比，进行归一化处理后得到如下权重公式： ％2 2．6基于统计的分类模型 2．6．1 中心向量算法 10 (2．5-2) 类中心向量最近距离判别算法的思想十分简单，它为每个类定义一个中心向 量。在分类系统中，类的含义就由该中心向量代替。中心向量的生成过程也非常 简单，为该类别中所有样本向量的集合中心，即该中心向量的每一维是训练集里 该类中该维权值的平均值。训练过程的任务是生成所有类别的中心向量，而在分 类阶段，系统利用最近距离判别法确定文档的类别，即把文档分到与其最相似的 类别中。 2．6．2 朴素贝叶斯算法(NB) NaiveBayes(朴素贝叶斯，NB)概率分类器在机器学习中很常用。朴素贝叶斯 分类的工作过程如下： (1)每个数据样本用一个n维特征向量X=(‘，而，⋯，吒)表示，分别描述对n 个属性彳。，么：，⋯，以的度量。 (2)假定有m个类c。，c2，⋯，巴，给定一个未知的数据样本X(即没有类标 号)，分类法将预测x属于具有最高后验概率(条件x下)的类。即是说，朴素 贝叶斯分类将未知的样本分配给类C，当且仅当 P(ex)>P(cjx)，1≤J≤m，J≠i (2．6．2—1) 其中P(C，IX)最大的类G称为最大后验假定。根据贝叶斯定理有 P(c旧=警 (3)由于e(x)对所有类为常数，只需要P(xl G)P(C：『)最大即可。如果类的先 验概率未知，则通常假定这些类是等概率的，即P(cJ)=尸(c2)=⋯=P(C。)。并据 此对P(CiIx)最大化，否则，最大化尸(qIX)P(Ci)。注意，类的先验概率可以用 P(q)=岛肛计算，其中s，是类G中的训练样本的总词频，而5是所有训练样本的 词频。 (4)给定具有许多属性的数据集，计算P(XIC)的开销可能非常大。为降低计 算P(XIC：f)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属 性值相互条件独立，即在属性间，不存在依赖关系。这样， 月 e(xct)=ll P(xkI C：) (2．6．2—3) k=l 概率以一IC：)，P(x：IG)，⋯，P(吒Iq)可以从训练样本估值，其中： 如果4是分类属性，贝tJP(xkICf)=Sik／S，其中钆是在属性4上具有值xk的 类C中的训练样本数，而毋是e中的训练样本数。 (5)对未知样本x分类，对每个类G，计算P(xIG)尸(q)。样本x被指派 到类e，当且仅当 P(Xl e)P(C：『)>P(Xq)P(q)，l≤／≤朋，／≠‘(2．6．2-4) 换言之，X被指派到使P(xIc：)P(Ci)最大的类G。 NB分类算法具有以下特点【11： 1．面对孤立的噪声点，NB是健壮的。因为在从数据中估计条件概率时，这 些点被平均。 2．面对无关属性，NB是健壮的。如果xi是无关属性，那么尸(薯IC)几乎变 成了平均分布。 3．相关属性可能会降低NB的性能，因为对这些属性，条件独立的假设已经 不成立。 越来越多使用NB方法在Reuters语料上的实验结果被发表。NB的基本思想 是利用单词和类之间的联合概率来估计给定文档属于类的概率。NB方法的朴素 (Naive)部分在于它的单词独立性假设，即不同单词在给定类别下的条件概率分布 是互相独立的。该假设使得NB分类器不需要计算单词之间的联合分布概率，使得 其速度远快于那些非朴素贝叶斯方法(达到指数复杂度)。 2．6．3 K最邻近算法(KNN) KNN全称是k．nearestneighbor，它是最著名的模式识别统计学方法之一，已 经有四十多年的历史，很早就被用于文本分类研究。它是在Reuters语料(包括21450 版本和Apte给出的集合)上取得最好结果的文本分类算法之一。 KNN算法相当简单：给定一个待分类的测试文档，系统在训练集中查找最相 似的k个文档(称为邻居)，并根据这些邻居的类别所属情况来给该文档的候选类别 评分。 通过对候选类评分的排序，然后进行多数表决，测试文档就根据最近邻中的 多数类进行分类 Y=argmax∑，(1，=cf)(2⋯631) c (工，c1)∈见 其中Y表示文档面的分类结果，c代表类标号，q代表最邻近的类标号，，(．)表 示指示函数，如果其参数为真，返回l，否则返回0。在多数表决方法中，每个近 邻对分类的影响是一样的，这使得算法对k值很敏感。降低k值影响的一种途径 就是根据每个最近邻i的距离不同对其作用加权，使远离测试文档的样例对分类 的影响比那些靠近测试文档的样例弱一些。 12 2．6．4 支持向量机算法 支持向量机(SupportVectorMachine，简称SVM)是Cortes与Vapnik于1995 年首先提出的，在解决小样本、非线性及高维模式识别中表现出许多特有的优势， 并能够推广应用到函数拟合等其他机器学习问题中。传统统计模式识别的方法都 是在样本数目足够多的前提下进行研究，所提出的各种方法只有在样本数趋于无 穷大时其性能才有理论上的保证，而在多数实际应用中，样本数目通常是有限的， 很多传统方法都难以取得理想的效果。VladimirN．Vapnik等人早在20世纪60年 代就开始研究有限样本情况下的机器学习问题，到90年代，有限样本情况下的机 器学习理论研究逐渐成熟起来，形成了一个较完善的理论体系一统计学习理论 (StatisticalLeamingTheory)。1992年一1995年，在统计学习理论的基础上发展出 了一种新的模式识别方法一支持向量机【2l】。 支持向量机是从线性可分情况下的最优分类面提出的。它在向量空间中找到 一个决策面(decisionsurface)，这个面能“最好"地分割两个分类中的数据点。 为了定义“最好”分割，我们引入两个分类的分类间隔(margin)的定义：即两个 决策面之间的距离。为简单起见，我们只举了线性可分的例子，SVM可以推广到 高维空间。通过图2．6．4-1和图2．6．4-2予以说明。 a o詈骘 oo 图2．6．4．1一条具有较小分类间隔的决策线(实线) Figure2．6．4—1Adecisionline(solid)谢masmallermargin 12 ●- C， 8鼋 。 图2．6．4-2具有最大分类间隔的决策线(虚线上的数据点为支持向量) Figure2．6．4-2Thedecisionline(solid)、析tllthemaximalmargin 图2．6．4—1和图2．6．4—2中的实线显示了两个可能的决策平面，每个面都可 以正确分割两组数据。与实线平行的虚线表示决策平面平移后得到的平面，这种 平移不会造成数据的分割错误。平行线间的距离称为分类间隔。SVM就是要在训 练集中找到具有最大分类间隔的决策平面。 设线性可分样本集D={(Yi，墨))，Yl∈{±l}是对墨的分类(+l表示它是个正 例，．1为反例)， i=l，⋯，，z，线性判别函数的一般形式为g(工)=w．x-b，分类面 方程为： 泓元一6=0 (2．6．4．3) 将判别函数进行归一化，使两类所有样本都满足Ig(x)障1，即使离分类面最近 的样本的Ig(功I-1，这样分类间隔就等于2／J|w|I，因此使间隔最大等价于使||wIl最小； 而要求分类线对于所有样本正确分类，就是要求： 访．委一6≥+1 for ”=+1 1跏霹一6≤-1 for n=-1 因此，满足上述条件且使11wII最小的分类面就是最优分类面。 可以通过在SVM中引入软分类间隔(softmargin)或者将原来的数据空间映射 到更高维空间(该空间中的新特征包含原空间中特征的交互作用，该新空间中线性 可分)的方法将解决线性可分情况推广到解决线性不可分的情况。如果用内积 K(x，五)代替最优分类面中的点积，就相当于把原特征空间变换到了某一新的特征 空间。采用不同的内积函数将导致不同的支持向量机算法，目前得到研究的内积 函数形式主要有三类，它们都与已有的方法有对应关系： (1)采用多项式形式的内积函数，即 K(x，薯)=[(石‘薯)+1】9， (2．6．4．4) 此时得到的支持向量机是一个g阶多项式分类器。 (2)采用核函数型内积 14 K(x,xj)_exp{_学)， (2．6．4-5) 得到的支持向量机是一种径向基函数分类器，它与传统径向基函数(RBF) 的基本区别是，这里每一个基函数的中心对应于一个支持向量，它们以及输出权 值都是由算法自动确定的。 (3)采用s形函数(双曲正切函数sigmoid)作为内积 K(x，‘)=tanh(o(x，‘)+c)， (2．6．4．6) 支持向量机实现的就是一个两层的多层感知器神经网络，只是在这里不但网 络的权值，而且网络的隐层节点数目也是由算法自动确定的。 比较有效的SVM实现方法包括Joachims的SVMlight系统和Platt的序列最小 优化算法(SequentialMinimalOptimization，SMO)。SVM的一个有趣特性是决策平 1 面只是由那些刚好和决策面距离为志的数据点来决定，这些点称为支持向量 ． 州I (supportvectors)，它们是训练集合中仅有的有效数据点，删除其它数据点不会影响 算法的结果(即产生的决策函数不变)。这个特性是SVM与其它分类方法(包括 KNN,LLSF和NNet都要使用所有的训练数据点来得到分类决策函数)相比而言， 理论上的独特之处，它是否会造成SVM的性能与其他方法发生显著不同尚未可知。 随着WWW的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。 SVM是继肛近邻、神经网络、朴素贝叶斯等方法之后被用于文本分类，并且是在 Reuter语料上取得非常好结果的文本分类算法之一。 2．7分类器评估算法 文本分类中一个很重要的问题就是对分类的结果进行评价。有很多种评估方 法，每种方法都只评估了分类系统的某些方面。对某个类和某个文本而言，用户 决定这个文本是否属于该类。当评价分类的结果时，每一类中的下面4个量是非 常重要的： a为被正确地分入该类的文本数量 b为被错误地划入该类的文本数量 C为被错误地划出该类的文本数量 d为被正确地划出该类的文本数量 口类别i查全率砚=_(2．7．1) 15 类别i查准率吼 口+6 (2．7—2) k ∑mi 宏观查全率m=上!}一其中k为类别总数(2．7．3)彤 、 7 k ∑q， 宏观查准率q=￡o_其中k为类别总数(2．7．4)尼 。。一‘。 、 7 Fl值肛等m (2．7-5)+口 ‘ ’ F1值是结合查全率查准率对分类器性能的综合评价。 16 3文本分类系统的设计与实现 3．1文本分类系统的功能性需求分析 系统设计需要综合考虑文本分类各方面的因素，主要有： 1．时间因素 文本分类面对的是海量的数据，如何快速通过训练文本找到合适的特征词， 如何对测试文本快速的应用分类算法，都是文本分类的关键问题，因此采用合适 的数据结构来提高运算的速度是系统设计中值得深思的一个问题。 2．空间因素 文本分类涉及的文本数量很大，需要采用合理的数据结构存储方案来应对可 能出现的内存溢出。 3．通用性 随着数据挖掘理论的不断发展，如何利用已有系统验证新的算法，以及如何 方便的改进已有算法，都对分类系统提出了更高的要求。因此一个通用的文本分 类系统应该注意对各种具体实现的抽象，代码的重用，模块之间的有效解耦。 4．数据的重用性和可理解性 文本分类系统在以大量数据为基础的训练过程中，积累了丰富的数字特征， 这些特征有必要进行保存，为其他类似的系统提供有价值的参考，并能在实验结 束时，对训练情况进行分析，并及时进行可能的修正。也就是说，系统应该提供 合适的方法，保存训练等运算的中间结果，为自身的完善和其他类似系统的构造 提供方便。 5．用户界面 文本分类系统需要设置许多参数，有些参数需要不断的测试才能找到一个最 佳值，所以系统需要一个友好的操作界面来方便用户进行参数设置。 3．2指导设计、实现的软件工程思想 从设计的角度来分析，因为本系统的目的是为信息过滤、数字化图书馆等上 层应用提供分类组件，所以从设计上特别考虑到如下几点： 0做到模块之间充分解耦，使用户可以从系统中抽取自己想要的模块，主要是将 分类算法模块和特征选择模块解耦。 ◆充分简化对外接口，方便二次开发。 为达到设计中的要求在实现时考虑到了如下几点： 17 1．面向接口编程，充分考虑需求，分析出不同实现的共同点，提取接口，模 块之间通过接口调用。 2．利用常用的设计模式，提高代码的重用性。 3．在编码阶段，通过充分的单元测试确保单元代码的质量。 4． 充分重视重构代码，并确保每次重构后的代码通过单元测试，以及当时阶 段的集成测试。 3．3系统简介 系统编程环境如下： ●采用python实现，python版本为：2．5．2 ●编程工具gvim 程序抽象系统共分为以下6个模块： 文档预处理模块、词频统计模块、特征 选择模块、特征权重模块、分类器算法模块、结果评价模块。 3．4文档预处理模块 文档预处理模块的主要的功能是对文档进行分词，去除标点符号、停用词等， 为对文档转化为空间向量模型做准备。预处理流程如图3．3．1所示。 上 I 1 分词 1 ． 上 l 删除停用词 图3．3—1文档预处理模块 Figure3．3-1Documentpreprocessingmodule 18 具体流程描述： 1．读取文件。 2．利用正则表达式删除空格、标点、数字等，正则表达式如下： [．⋯．f＼＼9⋯＼dlI＼nl>l 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ，应提交集成测试计划、集成测试规格说明和集成测试分析报告。 确认测试：验证软件的功能和性能及其它特性是否与用户的要求一致。 系统测试：将软件放在整个计算机环境下，包括软硬件平台、某些支持软件、 数据和人员等，在实际运行环境下进行一系列的测试。[261 基于以上理论，本章中所进行的测试目的是为了测试分类系统的性能，包括 查全率、查准率、F1值、运行效率；从类型上来划分，属于黑盒测试；在过程上 属于确认测试、系统测试(单元测试、集成测试在系统的实现阶段完成)。为了使 测试能够反应系统的主要的真实性能，测试的材料选用了国际 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的文本分类语 料集Reuters．21578。通过对比分类系统分类结果和语料集中给出的真实结果，分 别计算查全率、查准率、F1值，并统计运行时间，为了使测试的结果更加精确， 从该语料库中选取了5817个文档作为训练集，2726个作为测试集。 4．2测试环境 本文的实验是基于windowsvista系统