基于词频统计的文本分类模型研究

基于词频统计的文本分类模型研究上海师范大学硕士学位论文摘要在数据挖掘中，分类是一种重要的技术，它能对大量有关数据进行分析、学习，并建立相应问题领域中的分类模型。该技术在科学、工程、金融等领域均有广泛的应用。本文介绍了文本分类中文档的表示方法，对高频词表示文档的词频统计算法进行了深入的研究，分析了目前算法存在的问题，提出了一种树结构词频统计方法，实现了多关键词的高效匹配，并在此基础上实现了一个词频统计器，利用它可以快捷的将文本表示为高频词的集合，方便实现文本分类。在对各种经典的分类算法研究的基础上，着重对贝叶斯网络分类算法进行了研究，详细阐述了朴素贝叶斯分类算法的相关理论，并在其基础上提出了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝叶斯分类器，较好的解决了朴素贝叶斯分类中属性独立性假设所带来的弊端。利用树结构词频统计算法得到的实验数据，对决策树、向量空间模型、朴素贝叶斯分类和属性依赖贝叶斯分类进行了实验比对，分析了各个方法的优缺点。实验结果表明，属性依赖贝叶斯方法有较好的分类性能。关键词：词频统计，文本分类，决策树，ＩＤ３算法，属性依赖贝叶斯第１页基于词频统计的文本分类模型研究上海师范大学硕士学位论文ＡＢＳＴＲＡＣＴＣｌａｓｓｉｆｉｃａｔｉｏｎ，ｗｈｉｃｈｉｓａｂｌｅｅｓｔａｂｌｉｓｈｔｏａｎａｌｙｚｅａｎｄｌｅａｒｎｍａｓｓｏｆｒｅｌａｔｉｖｅｄａｔａ，ｓｏｍｅｆｉｅｌｄｓ．ｉｓａｎｃｏｒｒｅｓｐｏｎｄｉｎｇｃｌａｓｓｉｆｉｃａｔｉｏｎｍｏｄｅｌｉｎｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｑｕｅｆｏｒｄａｔａｍｉｎｉｎｇ．Ｔｅｃｈｎｉｑｕｅｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｓｏｍｅｄｏｍａｉｎｓｏｆｓｃｉｅｎｔｉｆｉｃｒｅｓｅａｒｃｈ，ｅｎｇｉｎｅｅｒｉｎｇ，ｆｉｎａｎｃｅａｎｄＳＯｏｎ．Ｔｈｅｍｅｔｈｏｄｏｆｈｏｗｔｏｅｘｐｒｅｓｓｆｉｌｅｓｉｎｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓｉｎｔｒｏｄｕｃｅｄ，ａｎｄｉｎ—ｄｅｐｔｈｒｅｓｅａｒｃｈｉｓｍａｄｅａｂｏｕｔｓｔａｔｉｓｔｉｃａｌｍｅｔｈｏｄｏｆｗｏｒｄｆｒｅｑｕｅｎｃｙｅｘｐｒｅｓｓｅｄｂｙｈｉｇｈ－ｆｒｅｑｕｅｎｃｙｗｏｒｄｓｉｎｔｈｉｓｔｈｅｓｉｓ．Ｔｈｅｔｈｅｓｉｓａｎａｌｙｚｅｓｔｈｅｅｘｉｓｔｉｎｇｐｒｏｂｌｅｍｓｉｎｃｕｒｒｅｎｔｔｒｅｅｓｔｒｕｃｔｕｒｅｓｔａｔｉｓｔｉｃａｌａｌｇｏｒｉｔｈｍｓ；ｐｕｔｆｏｒｗａｒｄａｍｅｔｈｏｄｏｆｗｏｒｄｆｒｅｑｕｅｎｃｙ，ｗｈｉｃｈｅｎａｂｌｅｓｋｅｙｗｏｒｄｓｔｏｍａｔｃｈｏｎｅａｎｏｔｈｅｒｈｉｇｈｌｙ－ｅｆｆｉｃｉｅｎｔｌｙ．ＢａｓｅｄＯｉｌｔｈｉｓｓｔａｔｉｓｔｉｃａｌｍｅｔｈｏｄ，ｗｅｄｅｓｉｇｎｂｙｗｈｉｃｈｗｅＳＯｃａｎａｓｔａｔｉｓｔｉｃａｌａｆｉｔｈｍｏｍｅｔｅｒｆｏｒｓｅｔｗｏｒｄ—ｆｒｅｑｕｅｎｃｙｃｏｕｎｔｉｎｇ，ｏｆｈｉｇｈ—ｆｒｅｑｕｅｎｃｙｗｏｒｄｓ，ｏｎｒａｐｉｄｌｙｅｘｐｒｅｓｓｔｅｘｔｓａｓｔｈｅｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｅｘｔｓｉｓｃｏｎｖｅｎｉｅｎｔｌｙｒｅａｃｈｅｄ．Ｂａｓｅｄａｌｌｓｏｒｔｓｏｆｒｅｓｅａｒｃｈｅｓｏｆｃｌａｓｓｉｃａｌａｒｉｔｈｍｏｍｅｔｅｒｓ，ｔｈｉｓｔｈｅｓｉｓｍａｋｅｓｅｍｐｈａｔｉｃａｌｌｙｒｅｓｅａｒｃｈｏｎＢａｙｅｓ－ｂａｓｅｄｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｗｅｂｔｅｘｔ；ａｎｄｉｌｌｕｓｔｒａｔｅｓｒｅｌｅｖａｎｔｓｐｅｃｉｆｉｃａｌｌｙｔｈｅｏｒｉｅｓｏｎｏｆｔｈｅｎａｉｖｅＢａｙｅｓ—ｂａｓｅｄｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｂａｓｅｄａｌｇｏｒｉｔｈｍ，ｗｅｂｒｉｎｇｔｈｅＢａｙｅｓｔｈｅｏｒｉｅｓｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎｆｏｒｗａｒｄａｐｒｏｊｅｃｔａｔｏｅｓｔａｂｌｉｓｈｉｎｔｅｒ－ａｔｔｒｉｂｕｔｅｓｄｅｐｅｎｄｅｎｃｙｒｅｌａｔｉｏｎｓｈｉｐ，ｗｈｉｃｈａｃｈｉｅｖｅｓａｔｔｒｉｂｕｔｅｓＢａｙｅｓｃａｔｅｇｏｒｉｚｅｒｂａｓｅｄＯｉｌｔｈｅｄｅｐｅｎｄｅｎｃｙａｎｄｇｅｔｓｒｉｄｏｆｔｈｅｄｉｓａｄｖａｎｔａｇｅｂｒｏｕｇｈｔｂｙｎａｉｖｅａｓｓｕｍｐｔｉｏｎｏｆａｔｔｒｉｂｕｔｅｓｉｎｄｅｐｅｎｄｅｎｃｙｉｎ第１Ｉ页Ｂａｙｅｓｃｌａｓｓｉｆｉｃａｔｉｏｎ．基于词频统计的文本分类模型研究上海师范大学硕士学位论文Ｕｔｉｌｉｚｉｎｇｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｄａｔａａｔｔａｉｎｅｄｆｒｏｍｔｒｅｅｓｔｒｕｃｔｕｒｅｓｔａｔｉｓｔｉｃａｌｍｅｔｈｏｄｏｆｗｏｒｄｆｒｅｑｕｅｎｃｙ，ｗｅｅｘｐｅｒｉｍｅｎｔａｌｌｙｃｏｍｐａｒｅｄｅｃｉｓｉｏｎｖｅｃｔｏｒｔｒｅｅｓ，ｓｐａｃｅｍｏｄｅｌ，ｎａｉｖｅＢａｙｅｓｃｌａｓｓｉｆｉｃａｔｉｏｎｗｉｔｈＢａｙｅｓａｔｔｒｉｂｕｔｅｓ·ｄｅｐｅｎｄｉｎｇｃｌａｓｓｉｆｉｃａｔｉｏｎ，ａｎｄａｎａｌｙｚｅｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅａｂｏｖｅｍｅｎｔｉｏｎｅｄｍｅｔｈｏｄｓ．ＴｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔＢａｙｅｓａｔｔｒｉｂｕｔｅｓ—ｄｅｐｅｎｄｉｎｇｃｌａｓｓｉｆｉｃａｔｉｏｎｈａｓａｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎ．ＫＥＹＷＯＲＤＳ：Ｗｏｒｄ－ｆｒｅｑｕｅｎｃｙＣｏｕｎｔｉｎｇ，ＴｅｘｔＣｌａｓｓｉｆｉｃａｔｉｏｎ，ＤｅｃｉｓｉｏｎＴｒｅｅｓ，ＩＤ３Ａｌｇｏｒｉｔｈｍ，Ａｔｔｒｉｂｕｔｅ－ａｓｓｏｃｉａｔｅｄＢａｙｅｓ第ｎＩ页论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或机构己经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表示了谢意。作者虢磋仰期：嘞ｒ】ｊ诊２ｊｌ论文使用授权声明本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此规定。作者签名：毖呜铲师签名：拦降陀日期：砌汁叫万日基于词频统计的文本分类模型研究上海师范大学硕士学位论文第一章绪论１．１研究背景随着互联网的不断普及和发展，信息技术已经渗透到人们社会生活的方方面面，并且正以惊人的速度和能力改变着人们的生活和工作方式，人们真正处于一个“信息爆炸”的时代。在这种情况下，如何自动处理这些海量信息成为目前重要的研究课题。自动处理信息的主要环节包括信息抽取、信息分类和信息检索。信息分类处于中间环节，主要将抽取到的信息自动有效地分成一定的类别，以便于信息的检索。在数据挖掘领域…中，分类作为一种重要的技术，能对大量有关数据进行分析、学习，并建立相应问题领域中的分类模型。该技术在科学、工程、金融等领域均有广泛的应用。随着全球计算机与通讯技术的飞速发展、互联网的普及与应用，信息爆炸的现实使人们越来越注重对分类的研究，文本分类及其相关技术的研究也日益成为一项研究热点。从目前的情况来看，虽然互联网上的信息载体呈多样化趋势，但仍以文本为主，文本仍是互联网上信息的主要来源。文本分类己成为一项具有较大实用价值的关键技术，是组织和管理数据的有力手段，可被用于抽取符号知识“１、新闻分发…、排序电子邮件、学习用户兴趣以及信息过滤等等。目前研究者们已提出了许多统计方法和机器学习方法，在试验中也有很好的表现。但是，在这个领域还是有很大的空间值得我们继续去研究和探索。１．２国内外研究现状２０世纪８０年代，自动文本分类技术的研究在国外兴起。早期的技术主要以基于知识工程的方法为主，卡内基集团为路透社开发的基于规则的Ｃｏｎｓｔｒｕｅ系统是较早的实用化自动文本分类系统。进入９０年代以后，基于统计的自动文本分类方法日益受到重视；系统评价也有了重大进展，建立了Ｒｅｕｔｅｒｓ（Ｖ２１５７８）、ＯＨＳＵＭＥＤ、Ｎｅｗｓｇｒｏｕｐ、ＴＲＥＣ等标准的英文语料库。目前主要的分类算法有朴素贝叶斯（ＮａｉｖｅＢａｙｅｓ）、Ｋ近邻（Ｋ－ＮｅａｒｅｓｔＮｅｉｇｈｂｏｕｒｓ）、支持向量机（ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅ）等基于统计的方法。国内从９０年代中期开始进行中文文本自动分类的研究。复旦大学、中科院计算所、清华大学、北京大学等单位较早开展了这方面的研究，取得了一定成果。第１页基于词频统计的文本分类模型研究上海师范大学硕士学位论文国家８６３计划中文信息处理与智能人机接口技术组也于２００３年开始进行文本分类评测，并且给出了评价准则，目前该标准已成为中文文本分类测试的标准。在进行文本分类前，通常要对文本进行特征表示，而表示的结果应该具有简单、准确等特点。目前大部分系统所采用的表示方法是６０年代末Ｓａｌｔｏｎ等人提出来的向量空间模型（ＶＳＭ：ＶｅｃｔｏｒＳｐａｃｅＭｏｄｅｌ）。但对中文而言，这个模型有先天不足——由于中文分词技术的局限性，ＶＳＭ表示文本的过程中割裂了特征项（字、词、短语、概念等）之问的相关性，做了独立性假设（如ＬｓＩ等模型研究）；而且高维向量很容易淹没重要的特征。所以该模型的文本表示质量受到特征维数、特征质量等诸多因素的影响。在目前分类模型的研究热点中，贝叶斯网络是被广为研究的对象之一。在国外，许多学者和研究机构都对应用贝叶斯网络技术检索信息进行了深入的研究。贝叶斯网络被用在信息检索中始于ＨｏｗａｒｄＲ．Ｔｕｒｔｌｅ的博士论文。ＣｏｏｐｅｒＧｒｅｇＦ叫，ＰａｕｌＤａｇｕｍ嘲，Ｓ．Ｋ．Ｍ．Ｗｏｎｇ嘲，ＳｕｃｈｅｔａＮａｄｋａｒｎｉ‘”等人在文献中详Ｈｅｃｋｅｒｍａｎ嘲，细介绍了如何构造贝叶斯网络，并利用其迸行概率推理。ＤａｖｉｄＭａｎＬｅｕｎｇＷｏｎｇ等人详细研究了运用贝叶斯网络进行数据挖掘的方法。ＭａｒｃｏＣｒｉｓｔ０９３等人对原有的贝叶斯网络模型进行改进，实现ＡｎｔｏｎｉｏＰｉｎｈｅｉｒｏｄｅ了一种基于贝叶斯网络模型的信息检索系统，利用其可处理不确定性信息的特性，设计了两层、多层网络来检索信息，改进网络结构和参数学习方法，大大提高了信息检索的性能。ＦｒａｎｚＰｅｒｎｋｏｐｆ等人设计了一种贝叶斯网络分类器来对文档进行分类，并介绍了一种分类器的结构学习算法。ＪｉｅＡｖａｎＣｈｅｎｇ“”，ＲｏｂｅｒｔＥｎｇｅｌｅｎ“”，ＷａｉＬａｍ等人对贝叶斯网络的构建及其参数的学习进行了探讨和研究，有分布学习算法、删除边的方法等。贝叶斯网络的学习一直是人们研究的热点，还有一些问题亟待解决。ＨｏｎｇＬａｎＪｉｎ，ＪｉＨｅ等人对中文文本分类方法进行了比较研究，提出了一种中文字典的算法来进行信息检索。国内，清华大学计算机科学与技术系的石纯一、陆玉昌、林士敏等通过剖析贝叶斯网络的结构和建造步骤“”，研究贝叶斯网络的学习方法“”，对具有不完整数据的问题分析““，和概率推理技术进行了研究“”，并引入模块化和面向对象思想，提出多模块贝叶斯网络推理“”；北京工业大学计算机学院的刘椿年提出并实现了一种以贝叶斯网为学生模型的智能教学系统“”，该方法以贝叶斯网为学生模型，根据学生模型上提供的启发信息，对解图空间进行搜索，以获取最佳教学决策；哈尔滨工业大学信息检索研究室的刘挺、秦兵、卢志茂等“”在信息检索方面对句法分析、词义消歧等作了研究，成功的引入贝叶斯网络对中文词义消歧，并取得了良好的效果；中国科学院计算技术研究所白硕、程学第２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文旗、王斌等对文档中词语权重的计算方法进行了改进“”，并提出了基于向量空间模型的文本分类系统的结构…，改进了多关键词匹配算法，在处理大规模数据时有较好的效率；复旦大学吴立德、黄萱菁等设计了基于向量空间模型的文本过滤系统乜１】，并在文本检索会议的评测中取得了很好的成绩；上海交通大学的王永成等偏重对关键词的匹配技术的研究，尤其是对多中文关键词匹配技术，在前人（Ａｃ算法和ＱＳ算法）的基础上，结合两者的优点，引入连续跳跃的思想，提出了一个快速的多关键词匹配算法，大大缩短了匹配时间。其他人在这方面也有研究嘲，基本相似，这里不再一一赘述。总之，在文本分类领域，由于贝叶斯网的预测能力以及它具有显示领域变量间最重要的直接关联关系和阐明领域结构的优势，贝叶斯网理论已成为２１世纪计算机软件的理论基础。１．３研究目的和意义本文的研究主要包括了以下几个方面：１）针对中文文档特有的特点，在研究以往文本表示方法的基础上，通过分析中文分词和词频算法目前存在的不足，设计了一种树结构词频统计方法来进行多关键词的词频统计。通过词频查找树，方便的完成了对中文进行分词和词频统计的工作。２）实现了目前比较流行的两种中文文本分类方法：决策树分类和向量空问模型分类。围绕查准率和查全率两个主要技术指标，使用大量的训练数据和测试数据对它们进行了实验比对，分析了各自的优缺点。３）详细地论述贝叶斯分类模型的结构、关键技术和理论；在分析朴素贝叶斯分类器存在的不足的基础上，适当的放宽属性间独立的约束，提出并实现了一种建立属性间依赖关系的属性依赖分类器。对几种分类模型进行了较详尽地实验分析，实验表明，属性依赖贝叶斯具有较好的分类效果。本课题的项目依托是上海师范大学网络中心所承接的上海市教委教育高地系统，是该系统的前期调研阶段。教育高地系统是为上海市中小学教师提供交流教学经验的一个平台，其中包含了大量的中文教案资料，为方便老师定制感兴趣的教育信息，排除其他非相关资料，有必要进行中文信息过滤，而过滤中最主要解决的问题就是对各种文档的分类问题，本课题从高维词库表示文本的角度出发，对相关算法和理论进行研究探讨，通过实验来比较分析各种分类模第３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文型的特点，旨在提出一种针对特定领域、性能较好的智能分类模型，并应用于该系统当中，本课题较好的完成了这一目标。１．４论文的组织结构本论文内容的组织结构如下：第１章绪论，介绍本论文的背景、文本分类的相关知识、国内外研究现状和课题研究的目的。第２章分析了文本分类的基本问题：文本表示。为了得到最终实现本文对多种分类模型比较的实验数据，对文本表示中词频统计方法尤其是多关键词的词频统计进行了研究，在学习以往词频统计方法的基础上，提出了一种有效的多关键词词频统计算法一利用查找树来进行词频统计。在该算法中，充分考虑了关键词之间的冗余信息，扫描一次文档就可统计出全部关键词词频信息，实现了多关键词的高效匹配，在此基础上可以方便快捷的将文本表示为高频词的集合，便于实现文本分类。第３章经典分类算法实现，学习分析决策树算法的原理和建树的步骤、拓展测试属性过程中所要考虑的情况，实现了一个基于ＩＤ３算法的决策树分类器，利用该分类器对中文信息进行了分类处理实验，并对实验结果进行了分析比较。此外，对另一种比较流行的分类算法一一向量空间模型（ＶＳＭ）进行了深入的研究，并通过实验检验该分类器的分类效果。第４章介绍了贝叶斯网络的基本原理、分类网络的建造方法和贝叶斯分类器。在朴素贝叶斯模型的基础上，对关键词集合进行分析，根据关键词频率出现的规律，提出了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝叶斯分类器。并将其与决策树、朴素贝叶斯、向量空间模型进行了对比，分析了各个方法的优缺点。实验结果表明属性依赖贝叶斯方法有较好的性能。第５章结束语，对本文所做工作进行总结，并提出下一步的研究工作，同时对文本分类的前景进行展望。第４页基于词频统计的文本分类模型研究上海师范大学硕士学位论文第二章文本表示方法研究２．１引言在信息处理研究的过程中，需要适当的预处理信息样本，这样才可能进一步用模型来准确表达信息样本，其中最重要的处理就是对属性进行选择，而属性选择的算法大致可以分为两大类：一类是基于统计的算法，如“Ｎ－ｇｒａｍ”算法嘲，另一类是基于字典的算法，这两类算法各有优缺点，基于统计的算法无需建立字典，因而与领域无关，但是精度低；基于字典的算法比较准确，但是需要建立字典，因为建立表达完全语义场的字典是不可能的，所以基于字典的属性选择算法必然是与领域相关的。基于统计的方法最主要是利用中文分词技术，即利用计算机自动识别文本中的词边界，进而统计词频并按出现的频率排序，使用出现频率较高的词来表示文本，它是中文信息处理最重要的预处理。中南大学信息科学与工程学院的费洪晓教授介绍了一个基于词频统计的中文分词系统的设计和实现啪’。通过这个系统，可以将输入的连续汉字串进行分词处理，输出分割后的汉语词串，一般是二字词串，并得到一个词典。词典中不重复地存储了每次处理中得到的词语，以及这些词语出现的频率。但在实际的应用当中，由于汉语本身的特点，分词效果并不理想，并且精度不高，所以多采用基于字典的方法。对于基于字典的算法，则需要建立和具体领域相关的字典，然后用该字典对文本进行多次扫描匹配，由于和某领域相关的单词一般比较多，所以对一篇文章的处理往往要进行多次，极大的浪费了时间。这种匹配方法主要有ＢＦ（ＢｒｕｔｅＦｏｒｃｅ）算法Ⅲ’、ＫＭＰ（Ｋｎｕｔｈ－Ｍｏｒｒｉｓ－Ｐｒａｔｔ）算法、酬（Ｂｏｙｅｒ－Ｍｏｏｒｅ）算法“１等，都已基本上完善。本课题在本章节重点讨论文本表示的主要实现方法，特别对使用多关键词表示文本的方法进行了深入的研究，在学习研究以往算法的基础上，提出了一种新型的多关键词匹配方法一树结构词频统计算法。在实现该算法的基础上对其性能进行分析，结果显示该方法可实现一次扫描统计出所有词的信息，消耗的时间大大减少。利用该匹配算法实现的词频统计器，可以实现文本集合中高频词的统计，并且对于训练文本和待分类文本，也可以方便的利用该统计器进行特征提取，从而实现用少量的高频特征词表示整个文本的目的。第５页基于词频统计的文本分类模型研究上海师范大学硕士学位论文２．２文本表示方法介绍在进行文本分类的前期，需要对待处理文本进行预处理，抽取文本的特征，使文本信息能够表示成计算机可以处理的结构化信息。本文讨论的文本表示方法，是基于分类算法模型的，针对不同的分类模型采用不同的文本表示方法。２．２．１文本特征表示文本表示成计算机可以处理的结构化信息的过程在文本分类嘲的整个过程中称为文本预处理，现在最为广泛被采用的使用方法是向量空间模型表示。向量空间模型（Ｖｅｃｔｏｒ模型。所谓向量空间模型（ＶＳＭ）就是用一个向量来表示一个文本的信息，使得文本成为特征空间中的一个点。在向量空间模型中文本集合形成一个矩阵，也就是特征空间中点的集合。词频矩阵就是应用向量空间模型表示文本的一种形式，其表示方法如表２－１所示：ＳｐａｃｅＭｏｄｅｌ）是由Ｇ．Ｓａｌｔｏｎ于１９８８年提出的。该模型在ＳＭ／ＩＲＴ系统中得到了成功的应用，并且广泛应用于文本信息处理领域，是一个很成功的表２—１词频矩阵表示方法在词频矩阵中，ｗｏｒｄ。是向量空间模型中的特征项，ａｉ，是项的权重，通常是指第ｉ个词在第ｊ篇文本中出现的频率。在大规模文本分类系统中，文本的表示是一个基本的，而且非常重要的问题。对训练文档、待分类文档要做的第一件事就是将它们从一个无结构的原始文本表示为结构化的可处理的信息，然后才有可能对这些信息进行分析与处理。在英文的分类、检索系统中，将文档及查询进行表示是件非常简单的事，因为通常选用第６页基于词频统计的文本分类模型研究上海师范大学硕士学位论文词为基本单位，而英文中词与词之间存在分隔符（如空格）。对中文分类、检索系统来说将文档及查询语句表示为结构化信息就复杂些。中文的文本表示通常选用字、词、短语、句子以及句群等更高层次的单位。在实际应用中，到底选择哪种单位来表示文本必须由处理速度、精度要求、存储空间等方面的具体要求来决定。选择的单位越具有代表性，语言层次越高，它所包含的信息也就越丰富，但同时进行分析时所付出的代价也就越大。在本课题中，我们采用关键词作为表达文本的基本单位，通过统计文本中关键词频并对其进行排序，使用出现频率最高的Ｎ个单词来表示整个文档，Ｎ就称为该文本向量的维数，在后面的实验中通过对不同维数表示的实验数据进行对比实验，来说明它对文本分类的影响。１）在决策树ＩＤ３算法中，由于向量属性只要表达出该关键词是否出现在文档中，因此上述向量表示方法中的ａ。表示第ｉ个词在第Ｊ篇文章中是否出现，用布尔值表示，但为了方便计算机识别，用“１”代表在文章中出现，“０”代表未出现。这种模型被称为“布尔逻辑模型”。２）ＶＳＭ分类算法模型主要采用的就是完整的向量空间模型表示。此时ａ。Ｊ＝ｔｆ。ｊ＊ｉｄｆ。，其中ｔｆｉｊ采表示关键词ｋ。在文档ｄＪ中出现的频度。ｉｄｆ。表示倒文档频度：ｉｄｆ。＝ｌｏｇ（ｎ／ｎ。），ｎ为数据全集中文档的总数，ｎｉ为包含关键词ｉ的文档总数。该方法能很好的表达出关键词对某类文章的重要性，因此被广泛的采用。２．２．２词频统计基本原理为了能精确的对实验文档进行表示，基于统计的方法需要对整篇文章进行分词，进而对每个单词的出现频率进行统计。词是最小的、能独立活动的、有意义的语言成分。计算机的所有语言知识都来自机器词典（给出词的各项信息）、句法规则（以词类的各种组合方式来描述词的聚合现象）以及有关词和句子的语义、语境知识库。英文和汉字构词的特点不同，它们的分词方法也有根本的区别。英文分词一般包含以下几步：①利用各种分隔符切分出词；②删除数字与分割符；③所有词转换为小写；④删除停用词表中的词（如助动词、代词、介词等）；⑤每个词都用其同型词根代替。由于汉语本身的特点，中文分词是对一串连续的汉字字符进行分词，在算法的实现上难度比较大。这主要是由于汉语分词存在切分歧义、未登录词识别（如：人名、地名、企业字号、商标号等和某些术语、缩略词、新词）、分词与理解的先后等问题的存在。第７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文在中文文档中，从形式上看，词是组合稳定的字而得到的，因此，在上下文环境中，同时出现相邻的字次数越多，就表示该相邻字组合越有可能构成一个词。因此相邻字的组合共现的频率或概率能够较好的反应组成词的可信度。这就是词频统计的基本原理，这种技术发展至今已经有许多不同的统计原理。Ｉ．互信息原理嘲定义２．１：对有序汉字串ＡＢ中汉字ＡＢ之间的互信息定义如公式（２－Ｉ）所示：姒功－ｌ０９２高％㈤互信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阈值时，便可认为该字组合可能构成了一个词。其中，Ｐ（Ａ，Ｂ）为汉字串ＡＢ联合出现的概率，Ｐ（Ａ）为出现汉字串Ａ的概率，Ｐ（Ｂ）为汉字串Ｂ出现的概率，它们在汉字字符串中出现的次数分别计为ｎ（Ａ）、ｎ（Ｂ）、ｎ（ＡＢ），ｎ是词频总数，则有公式（２－２）：删，口）．兰丝，Ｐ似）。型，即）。盟（２－２）万一厅互信息反映了汉字串ＡＢ间相关的程度。（１）如果Ｉ（Ａ，Ｂ）＞＝０，即Ｐ（Ａ，Ｂ）＞＝Ｐ（Ａ）Ｐ（Ｂ），贝ＩＪＡＢ间是正相关的，随着Ｉ（Ａ，Ｂ）增加，相关度增加，如果Ｉ（Ａ，Ｂ）大于给定的一个阈值，这时可以认为ＡＢ是一个词ｊ（２）如果Ｉ（Ａ，Ｂ）≈Ｏ，ＥＰＰ（Ａ，Ｂ）ｍＰ（Ａ）Ｐ（Ｂ），则ＡＢ间是不相关的；（３）如果Ｉ（Ａ，Ｂ）＜０，即Ｐ（Ａ，Ｂ）＜Ｐ（Ａ）Ｐ（Ｂ），则ＡＢ间是互斥的，这时ＡＢ间基本不会结合成词。２．Ｎ－Ｇｒａｍ统计模型Ｎ－Ｇｒａｍ统计计算语言模型的思想是：一个单词的出现与其上下文环境中出现的单词序列密切相关，第ｎ个词的出现只与前面ｎ－１个词相关，而与其它任何词都不相关，设ＷｌＷ２Ｗ３…ｗｎ是长度为ｎ的字串，则字串Ｗ的似然度用方程表示如公式（２－３）所示。Ｐ∥）。ｌ：Ｉ聊ｌ晰…册…２”肼一１）（＂）不难看出，为了预测词ｗｎ的出现概率，必须知道它前面所有词的出现概率。从计算上来看，这种方法太复杂了。如果任意一个词ｗｉ的出现概率只同它前面的两个词有关，问题就可以得到极大的简化。这时的语言模型叫作三元模型（ｔｒｉ—ｇｒａｍ），如公式（２—４）所示。第８页基于词频统计的文本分类模型研究上海师范大学硕士学位论文㈤ｐＯｖ）－ＰＯｖＯｐＯｖ：１ｗ，）ｎ吼。Ｐ噼ｌ职一搋一－）符号兀。。。Ｐ（晰ｌ班一搋一ｔ）表示概率的连乘。一般来说，Ｎ元模型就是假设当前词的出现概率只同它前面的Ｎ一１个词有关。重要的是这些概率参数都是可以通过大规模语料库来计算的，比如三元概率如公式（２－５）所示。册限册－１）＿竺ｃｏｕｎ蜡ｔ｛Ｗｉ（２１５）２Ｗｉ１一Ｊ式ｃｏｕｎｔ（…）表示一个特定词序列在整个语料库中出现的累计次数。３．ｔ－测试原理嘲定义２．２：对有序汉字串ｘｙｚ，汉字Ｙ相对于Ｘ及ｚ的ｔ一测试定义如公式（２－６）所示。如（），）。万丽ｐ（ｚ丽Ｉｙ）－露ｐＯ荔＇Ｉｘ丽）（撕）其中ｐ（ｙＩｘ），ｐ（ｚｌｙ）分别是．关于ｙ关于ｘ，ｚ关于ｙ的条件概率，６２（ｐ（ｚｌ妫、６２（ｐｏｌｘ”则代表各自的方差，公式（２－６）中各量可用公式（２—７）、（２—８）估计。ｐＯ，Ｉｘ）－等－等，ｐ（ｚＪｙ）一等一等ｃ拼，职ｐ仲））一等∥川），））一筹（２勘从ｔ一测试的定义，可知：（１）厶，：（），卜０时，字Ｙ有与后继字ｚ相连的趋势，值越大，相连趋势越强；（２）厶，ｚ（ｙ）一０时，不反映任何趋势；（３）ｔｒ，ｚ（ｙ）ｔＯ时，字ｙ有与前趋字Ｘ相连的趋势，值越小，相连趋势越强。虽然利用以上三种方法可以很好的识别字与字之间构成词的可能性，但在实际的使用中，一篇文档通常由成千上万乃至几十万的汉字和符号组成，识别单词时计算量非常大，因而人们通常使用基于字典的方法，利用字典对文档进行扫描，进行匹配，有多少单词就对文档扫描多少遍，以便统计出所有单词出现的频率，这就是基于匹配的词频统计方法。第９页基于词频统计的文本分类模型研究上海师范大学硕士学位论文２．２．３基于匹配的词频统计方法在信息科学领域中，关键词匹配（即模式匹配）问题一直都是研究的焦点之一。模式匹配是指在文本Ｔｅｘｔ＝ｔｌｔ２ｔ３…ｔｎ中检索子串Ｐａｔ＝ｐｌｐ２…ｐｍ（模式）的所有出现，其在信息检索、信息压缩、入侵检测、模式识别、防火墙乃至计算机理论等诸多方面都有重要的理论价值和应用前景。模式匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有ＢＦ算法、ＫＭＰ算法、酬算法及一些改进算法．关键词匹配是我们进行词频统计的关键技术，一般可分为单关键词匹配和多关键词匹配。单关键词匹配算法在国内外都对其进行了深入的研究，主要有ＢＦ（ＢｒｕｔｅＦｏｒｃｅ）算法、ＫＭＰ（Ｋｎｕｔｈ－Ｍｏｒｒｉｓ—Ｐｒａｔｔ）算法、ＢＭ（Ｂｏｙｅｒ—Ｍｏｏｒｅ）算法等，都已基本上完善。ＢＦ算法直观、简单，但涉及多次回溯，算法效率低，时间复杂度为０（ｍ＊ｎ）；ＫＭＰ算法实现了无回溯匹配，避免了ＢＦ算法中频繁的回溯，文本串中的每个字符只匹配一次，普遍提高了模式匹配的工作效率，时间复杂度为Ｏ（ｎ＋ｍ）：踟算法实现了跳跃式匹配，文本串中的部分字符不需要匹配，时间复杂度为Ｏ（ｍ＊ｎ），但其最优情况下的时间复杂度为Ｏ（ｎ／ｍ）。此后，又有一些新的算法㈨被提出，大多都是对ＫＭＰ算法或ＢＭ算法的改进及其各种变形和简化算法，用于特殊情况。１．朴素模式匹配算法—ＢＦ方法朴素模式匹配算法（Ｂｒｕｔｅ—Ｆｏｒｃｅ算法，简称为ＢＦ算法），亦称蛮力算法，其基本思路是：从目标串ｓ＝“ｓｌｓ２…ｓｎ”的第一个字符开始和模式串ｔ＝“ｔｌｔ２…ｔｍ”中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串Ｓ的第二个字符开始重新与模式串ｔ的第一个字符进行比较。依次类推，若从模式串Ｓ的第ｉ个字符开始，每个字符依次和目标串ｔ中的对应字符相等，则匹配成功，该算法返回ｉ；否则，匹配失败，函数返回０。２．模式匹配改进算法一ＫＭＰ方法胁Ｐ算法是Ｄ．Ｅ．Ｋｎｕｔｈ、Ｊ．Ｈ．Ｍｏｒｒｉｓ和Ｖ．Ｒ．Ｐｒａｔｔ共同提出的，简称ＫＭＰ算法。该算法较ＢＦ算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。其改进在于：每当一趟匹配过程中出现的字符比较不等时，主串不需要回溯ｉ指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。数组ｎｅｘｔ［ｊ］来确定这一滑动距离，表示当模式串中第ｊ个字符与主串中相应字符“失配”时，在模式串中需重新和主串中该字符进行比较字符的位置。其值取决于模式串本身，而与主串无关。第１０页基于词频统计的文本分类模型研究上海师范大学硕士学位论文３．删方法－－ＢＭ算法。两者的差别在于阴算法将对模式串的扫描方式从前向后变成从后向在Ｊ（ＭＰ算法的启发下，Ｂｏｙｅｒ和Ｍｏｏｒｅ提出了一种新的字符串快速匹配算法前，并且考虑主串中可能出现的字符在模式串中的位置。其特点是：采用从后向前的方式进行匹配，在每次匹配完成后，使用好后缀启发函数与坏字符启发函数计算得到的移动值中的最大值来向后移动匹配位置。根据启发式函数，主串的部分字符可以直接跳过，不进行比较。２．３树结构词频统计算法２．３．１基本思想在第二节详细介绍了基于匹配的词频统计方法后，我发现这些经典的匹配算法往往存在这样一个问题，多个关键词要进行统计时，不可避免的对待处理文档进行多次扫描。尤其是当待处理文档较大时这一代价会变的更高，以上模式匹配算法均未解决该问题。针对词频统计的特点，提出了一种新型的多关键词匹配方法一～树结构词频统计算法。该算法基本思想如下：首先根据已有的关键词字典集合构建一棵查找树，利用该树对文档进行扫描，进行关键词的词频统计。查找树由构成关键词的基本元素组成。例如：如果关键词是英文单词，则结点中只包含一个字母字符；如果关键词是数值，则结点中只包含一个数位；若关键词是中文词组，则结点中只包含一个汉字。为了提高查找结点的速度，实现快速查找，约定该树是一棵有序树，同一层中兄弟结点之间按照所含字符的ＡＳＣＩＩ码值从小到大排序。在每个结点处标识是否为一个词结束，如果结点处为词的结束标志则记录该词的信息。进行词频统计时，每次从文档中读取一个字符到查找树中比较，只需要对文档扫描一遍，就可以统计出所有关键词的信息。如果许多词都由相同的字开头，即所有词的前缀的数目远远小于所有词的长度总和时，查找树将特别适用。该方法将关键词集合中词与词之间的冗余信息充分利用起来，减少了一些不必要的匹配过程，在词频统计时对关键词集合中的每个词同时进行处理，大大提高了统计效率。比如“上海”、“上海师范大学”两词中“上海”只需比较一次。并且可根据实际需要在树中查找、计算各个词及其前缀的相关信息，有助于信息处理进行下一步工作。２．３．３数据结构在本课题中，我采用了ＪＡｖＡ陶１语言实现树结构词频统计算法，在ＪＢＵＩＬＤＥＲ第１１页基于词频统计的文本分类模型研究上海师范大学硕士学位论文下调试运行成功，并基于该算法实现了一个词频统计器，利用该统计器，可以方便的对字典库中的关键词建立查找树，并通过该查找树一次性扫描就可以统计出所有关键词的出现次数，为文本预处理也就是表示文本提供了方便的手段，实验证明该算法性能优越，大大节省了文本表示的时间。为实现查找树，快速进行词频统计，在程序中我编写了两个单独的类加以实现，他们分别表示树中结点和统计出的关键词。整个树的静态数据部分就由这两个类构成的两个数组来实现。对于这两个类，对其属性部分分别描述如下：ｃｌａｓｓＴｍｙｔｒｅｅｎｏｄｅ｛ｃｈａｒｋｅｙｌｉｎｔ／／表示树结点的类ｐｕｂｌｉｃ／／字符（数字、字母或汉字）／／出现个数／／是否词尾ｒｅｆ［］；ｐｕｂｌｉｃｂｏｏｌｅａｎｐｕｂｌｉｃｃｏｕｎｔｌｉｓｗｏｒｄｌＴｍｙｔｒｅｅｎｏｄｅ／／和该字符关联的其他结点ｌ对文档扫描后统计出的关键词出现频率可以存放在如下类组成的数组中。ｃｌａｓｓＴｓｕｂｅｌｅｍｅｎｔ｛／／关键词类／／关键词／／对应出现次数ｐｕｂｌｉｃＳｔｒｉｎｇｋｅｙｌｉｎｔｐｕｂｌｉｃｃｏｕｎｔｌ｝具体实现过程中，用一个动态数组来存储树中每个结点及其兄弟结点。为方便统计时对结点查找，按照结点所存储的字的ＡＳＣＩＩ码值的大小从小到大有序插入到数组中去。因为对有序内容的查找我们可以利用折半查找来实现，这样可以大大提高查找的效率。假设每个结点有Ｎ个孩子结点，则查找匹配次数由原来的最多Ｎ次减少到最多ｌ０９２ＩＮ次。在数据结构具有的基础上，查找树的构造过程如图２—１所示。第１２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文＜掣上掣；回；回鳓釉图２·１查找树构造过程鳓（ａ）：从关键词集合中读取关键词“信息过滤”将其插入到树中，由于初始根指针为空，则依次将每个字以结点的形式逐层插入到树中，每次生成一个大小为１的数组来存储结点信息，在结点“滤”的信息中标识一个词插入结束（图中用灰色结点表示）。（ｂ）：从关键词集合中读取关键词“信息港”将其插入到树中，由于根不为空，则查找该词是否在树中存在。依次处理词中的每个字，取第一个字“信”查找存在，则当前指针指向“信”结点。处理下一个字“息”，查找存在则当前指针指向该结点。处理下一个字“港”，查找不存在，则将存储“过”结点的数组长度加１，则将其作为“过”的兄弟结点插入并标识一个词结束；“过”和“港”两结点均为“息”结点的孩子结点，由于“港”的ＡＳＣＩＩ码值比“过”的小，插入时将其插入到结点“过”的前面。（ｃ）：从关键词集合中读取关键词“计算数学”将其插入到树中，根指针不为空，查找字“计”在当前指针所指结点的兄弟结点中是否存在，不存在则将存储“信”结点的数组长度加１，则将其作为“信”的兄弟结点插入到根指针下面，当前指针指向新结点；由于“计”的ＡＳＣＩＩ码值比“信”的小，将其插入到结点“信”的前面。按同样方法处理其余的３个字。（ｄ）：从关键词集合中读取关键词“遗传算法”将其插入到树中，根指针不为空则进行查找插入。首先查找“遗”字是否在根指针所指结点的兄弟结点中存在，查找不存在则存储“计”、“信”结点的数组长度加１，将其作为“计”、“信”结点的兄弟结点插入，当前指针指向新结点；由于“遗”字的ＡＳＣＩＩ码值比“计”、“信”的都大，则将其插入到结点“信”的后面。操作步骤同上依次第１３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文插入剩余的３个字。所需的查找树构造成功。在进行词频统计时，依次读取待处理文档中的每个字，在查找树上查找并记录对应的字词信息。根据实际需要，可对已构造好的查找树添加新的关键词。并且在构造树时，按照每个字的ＡＳＣＩＩ码值有序插入，便于快速的查找。这样每篇文档只需读取一遍就可统计出所有关键词的词频数，大大提高了程序执行效率。２．３．４算法描述查找树的算法的核心问题主要两个：一是如何从关键词集合中构造查找树，二是如何利用查找树进行词频统计。这里通过两个算法的实现来解决此问题。在查找树的构造生成算法中，令Ａｒｒａｙ表示关键词集合数组，Ｗｏｒｄ表示当前处理关键词；ｐｏｓｉｔｉｏｎ表示关键词中的当前待处理字的位置，初始ｐｏｓｉｔｉｏｎ＝Ｏ；ｌｅｎｇｔｈ表示关键词的长度。算法２．１查找树的构造生成１：Ｗｈｉｌｅ关键词集合数组Ａｒｒａｙ未处理完毕ｄｏ２：３：４：５：６：６：７：８：９：１０：１１：取出Ａｒｒａｙ中关键词Ｗｏｒｄ，标志其己处理Ｗｈｉｌｅｐｏｓｉｔｉｏｎ＜ｌｅｎｇｔｈｉｆ树为空树第ｐｏｓｉｔｉｏｎ个字生成新结点插入ｅｌｓｅｉｆ第ｐｏｓｉｔｉｏｎ个字在当前结点的兄弟中不存在第ｐｏｓｉｔｉｏｎ个字生成结点插入ｅｌｓｅ该结点变成当前结点ｅｎｄｉｆｅｎｄｉｆ１２：ｐｏｓｉｔｉｏｎ＝ｐｏｓｉｔｉｏｎ＋１１３：１４：ｅｎｄＷｈｉｌｅ当前结点标识一个词结束，该关键词插入成功１５：ｅｎｄＷｈｉｌｅ算法２．２：查找树的查找统计Ｓｔｅｐｌ：按照检索树的构造算法步骤将待处理关键词集合构造成一棵检索树。第１４页基于词频统计的文本分类模型研究上海师范大学硕士学位论文Ｓｔｅｐ２：读取待处理的文档，令ｌｅｎｇｔｈ表示文档长度，ｐｏｓｉｔｉｏｎ表示文档当前处理的字符位置，初始ｐｏｓｉｔｉｏｎ＝０，检索树的当前指针指向根结点。Ｓｔｅｐ３：取文档的第ｐｏｓｉｔｉｏｎ个字与检索树的当前指针所指的结点的兄弟结点进行查找匹配。Ｓｔｅｐ４：如果该字存在，则当前指针指向该结点的孩子结点，若该结点有词的结束标识则对该关键词的频率加１，跳转到ＳｔｅｐＳ；如果该字不存在，则当前指针指向根结点，ｐｏｓｉｔｉｏｎ回退最短非关键词匹配长度，跳转到Ｓｔｅｐ３。Ｓｔｅｐ５：ｐｏｓｉｔｉｏｎ＝ｐｏｓｉｔｉｏｎ＋１。Ｓｔｅｐ６：如果ｐｏｓｉｔｉｏｎ＜１ｅｎｇｔｈ，则转到Ｓｔｅｐ３；如果ｐｏｓｉｔｉｏｎ＞＝１ｅｎｇｔｈ，则指针指向根结点。Ｓｔｅｐ７：对检索树进行一次遍历，输出树中每个结点的信息，即集合中每个词及其前缀的词频信息。Ｓｔｅｐ８：算法结束。２．３．５性能分析该算法是以空间消耗来换取时间效率。假设文本长度为ｎ，关键词有ｋ个，长度分别为ｍ。，ｍ２，…，腿，平均长度为ｍ。为了讨论方便，这里假设每个关键词出现的频率都相等。假设关键词为随机的，则查找每一位的平均查找长度为（１＋ｋ）／２。在查找树中进行查找的平均长度为ｍ（１＋ｋ）／２。考虑查找树的两个极端，一是所有关键词相互之间都没有公共的前缀，一是所有关键词都有公共的前缀。情况ｈ查找树的第一层结点匹配时需ｌ０９２ｋ次，而剩余层仅需匹配１次。情况２：查找树的最后一层结点匹配时需１０９盛次，而其余层匹配时仅需１次。假设匹配每层结点的概率都相等，每从文档读取一个字符需匹配的平均次数为１／ｒｅｘ（１０９＋肌－１）。假设关键词均匀分布，则每个结点下最多有个『ｋ／ｍ１孩子结点ａ每次从文档中读取一个字符需匹配的次数为ｌｏｇ：卜／所１。ｒ０，七）一ｎｘｌ０９２ｌｋ／ｍＩ第１５页基于词频统计的文本分类模型研究上海师范大学硕士学位论文其中Ｔ（ｎ，ｋ）表示文本长度为ｎ，关键词个数为ｋ，统计所消耗的时间。设查找树中每个结点的孩子结点个数均匀分布。则每个结点的平均比较匹配次数为（１０９：ｌ＋ｌｏｇ：２＋．．·＋ｌ０９２ｋ）／ｋ＝ｌ０９２ｋ！／ｋ。Ｔ（ｎ，ｋ）＝ｎ×ｌｏｇｚｋ！／ｋ。在最坏情况下，该算法的时间复杂度为Ｏ（ｎ＊ｌｏｇ：ｋ）。在运算过程中需要存储整个查找树，其空间复杂度为Ｏ（ｍｌ＋ｍ２＋…＋ｉｎｋ）。在进行词频统计时，消耗的时间与测试文档的长度有关，与关键词集合的大小关系不大。２．４树结构词频统计器在完成了树结构词频统计算法的基础上，实现了词频统计器，利用它可以对关键词库建立查找树，并能一次性处理目标目录中的多篇文档，形成适合模型使用的文本向量，在本课题中根据ＩＤ３算法和向量空间模型算法的需要，向量的各项用布尔值表示关键词是否出现，或者表示对应关键词的出现频率。２．４．１统计器界面及菜单介绍在实现了树结构词频统计算法的基础上，实现了词频统计器，运行后主要包括两大部分：菜单栏和数据结果显示区域。具体界面如图２—２所示：图２－２树结构词频统计器运行界面对于词库的操作菜单，主要包括读入词库（在这个阶段建立查找树）、存储词库、清除内存词库和将数据区域中的数据内容存盘四个内容。用以实现对关键词库的读取和保存。具体菜单项如下：第１６页基于词频统计的文本分类模型研究上海师范大学硕士学位论文图２－３词库操作菜单选项图２．４统计词频菜单选项统计词频菜单中主要是对当前词库或待处理原文件进行词频统计的选项：处理源数据文件可以对指定的目标文件夹中的所有文件用查找树进行词频统计，统计结果可以直接写入文件，成为分类模型直接使用的数据文件；可以按照升序或降序对词频统计的结果进行排序显示；对于数据区域显示的统计结果可以方便的存储在硬盘上备份，并且可以恢复以前的统计结果。通过这些菜单的利用，可以方便的实现对文本中关键词频的统计，从而形成我们可以直接使用的实验数据。２．４．２词频统计器应用实例本课题后半部分的实验数据均来源于中国期刊全文数据库，选取和神经网络相关的文章９００篇和非神经网络文章５００篇进行处理，最终形成适合分类模型使用的数据文件。由于进行中文分词进行统计效率低并且分词界限不容易把握，本课题首先对９００篇神经网络类文章的关键词进行词频统计形成一个词库，词库中允许重复的关键词存在，然后直接按照由大Ｎ４，进行词频统计排序，可以得到如图２．５的结果：第１７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文图２－５对神经网络类关键词库统计结果显示在得到了该类文章的关键词频率统计结果后，我们就可以使用前Ｎ个出现最多的词定义文本表示的维数，对待处理的实验数据，也就是文本集合进行词频统计，将结果存储到指定的文件中，对于第三章中实现的ＩＤ３分类模型，它需要的数据只需要表示出某个关键词是否出现在文本中，得到的文件向量表示形式如下所示：１，ｏ，０，０，０，０，０，０，１，０，０，０，１，１，１，１，１，０…００１１，０，０，０，１，１，０，１，１，０，０，０，１，０，１，０，１，０，０，１，１０，０，０，０，０，０，０，０…１００，０’ｏ，０，１，０，１，０，１，１，００，０，０，０，０…０００，０，０，０，０，０，０，０，０…１００，１，０１，０，０，０，１，０，０，１，０…００１，１，０，１，０，１，１，０，１，１这是５篇文档２０维向量表示文本的结果数据，共２１列，最后一列表示该文档是否是属于神经网络类的文章，“１”表示是，“０”表示非该类文章。２．５小结本章节介绍了文本分类中一个非常重要的环节：文本表示。为了更好的实现第１８页基于词频统计的文本分类模型研究上海师范大学硕士学位论文文本分类的文档预处理工作，需要对关键词进行统计，以便用词频出现较高的若干关键词来表示文本。本课题介绍了几种常用分词方法和几种模式匹配方法：ＢＦ方法、眺Ｐ方法、咖方法来对文本文档进行词频统计。但这些算法都不能很好的解决在进行多关键词词频统计时多次扫描的问题。为了解决常用的匹配方法在多关键词词频统计中目标文本需要多次扫描这一问题。在检索中文信息的应用背景上，以降低时间复杂度为主要目的，提出了一种适用于检索中文信息的快速多关键词匹配算法来进行词频统计，即应用查找树来进行词频统计。该算法在匹配过程中充分利用了关键词间的冗余信息，可以在只对目标文本进行一遍扫描的情况下完成所有关键词的词频统计工作，达到了高效搜索的目的。在实现方式上，本课题采用动态数组为存储结构来构造查找树。构造时，把查找树建成一棵有序树。在查找匹配过程中，引入折半查找方法来查找某一结点下的孩子结点。数组型查找树中每层结点都是有序的，在插入和查找时采用折半查找算法，当关键词达到一定数量时，其构造和检索时间使用较小，而且消耗时间起伏不大。通过对实验数据的处理，验证了该算法可通过扫描一次文档统计出所有关键词的信息。利用查找树进行词频统计，可以间接的实现利用词库进行对文本文档中诃的切分，消除了在统计过程中出现的误统计现象，并且在统计过程中可以得出每个词的前缀的相关信息。本章算法由于很好地利用了关键词的前缀信息，因此对关键词集合中关键词数目的增加不敏感，并且在关键词较长和较短时都具有很好的性能。在实现该算法的基础上，实现了一个树结构词频统计器，可以方便的对待处理文档进行预处理，将其转化为词频较多的关键词构成的向量。为以后章节模型比对的实验方便的提供了数据，实践证明，该统计器很好的完成了这一功能。第１９页基于词频统计的文本分类模型研究上海师范大学硕士学位论文第三章经典分类算法实现３．１分类基础知识３．１．１分类概述我们可以这样理解一个分类的定义：分类（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）就是通过学习得到一个目标函数（ｔａｒｇｅｔｆｕｎｃｔｉｏｎ）ｆ，把每个属性集ｘ映射到一个预先定义的类标号Ｙ。非正式地，目标函数也称为分类模型（ｃｌ髂ｓｉ触ｔｉ伽ｍｏｄｅｌ）㈨，图形描述如图３．１所示：图３－１分类器的任务是根据输入属性集ｘ确定类标号Ｙ形式化表示分类问题为：给定一组训练实例Ａｌ，屯，…Ａｋ，其中九（ｋ＝ｌ，２…ｎ）是变量组Ｂ＝｛Ｄ，，Ｄｚ，…Ｏ。，Ｃ）中的一组描述。给定一个新的具有属性ａ，，ａ２，．－－，ａ．的实例，判别这个新的实例的类别ｃ。这里的训练实例也称为训练集，是由为建立分类数据模型而被分析的数据元组成的，就是我们刚才提到的集合Ｂ，其中Ｄｉ表示属性值，Ｃ表示类别。对于新的具有属性的实例的集合，我们称之为测试集，它被用来检验分类模型的准确率。一个完整的分类过程一般包括模型构造、模型测试和模型应用州这三步：１）模型构造分析样本的类别和其具备的一些特征之间的依赖关系，并将这种关系用特定的模型表示出来。例如，分析以往的病例，根据病人的症状和诊断结果，得到疾病诊断模型。２）模型测试检测模型的准确度，最终得到描述每个类别的分类模型。这就需要将第一阶段得到的模型运用到测试集上，对该模型进行评测。模型的准确度定义为测试集中结果正确的样本的比例。为了评价的客观性，测试数据集与训练数据集一般不包含相同的样本。例如，得到诊断模型后，用另一组病例测试模型的准确度。３）模型应用第２０页基于词频统计的文本分类模型研究上海师范大学硕士学位论文利用得到的分类模型，预测在类别未知的情况下样本所属的类别。这个过程与模型评价基本相同，只是输入数据的类别是未知的。例如，医生利用已经得到的疾病诊断模型，为新的病人做出诊断。对于模型构造阶段分类模型的构造方法，最主要有以下几种：①机器学习的方法：主要包括我们本章节中要重点介绍的决策树分类方法。②基于统计的方法：包括贝叶斯方法（下一章节重点介绍）、非参数法（最近邻法或基于事例的学习）。⑨神经网络的方法：比如ＢＰ算法，其模型的表示是前向反馈神经网络模型。这些技术都使用一种学习算法（１ｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍ）确定分类模型，该模型能够很好地拟合输入数据中类标号和属性之问的联系。学习算法得到的模型不仅要很好的拟合输入数据，还用能够正确地预测未知样本的类标号。本章节中我们重点介绍性能较好，广为使用的两种分类模型：决策树和向量空间模型。３．１．２分类性能评价指标文本分类的实质是根据分类的条件进行检索符合条件的文本信息的一个过程，所以评价分类好坏的标准本课题沿用信息检索中的评价标准ｍ１：查全率和查准率。查准率（Ｐｒｅｃｉｓｉｏｎ）表示在系统得到的全部答案中，正确的答案所占的比值。查全率（Ｒｅｃａｌｌ）指在所有答案中（包括系统得到的和系统不应该忽略的），正确答案所占的比值。查准率描述系统检索或抽取的信息中，有用的是多少。查全率表示应该得到的信息中，已查出了多少。如果查全率用Ｒ表示，查准率用Ｐ表示，分类结果中符合用户兴趣的信息条数为ａ，不符合用户兴趣的信息条数为ｂ，系统中未检出符合用户兴趣的信息条数为ｃ，那么可用公式表示如下：①查全率Ｒ＝［ａ／（ａ＋ｃ）］Ｘ１００９６查全率的互补数就是漏检率，即漏检率（ｏｍｉｓｓｉｏｎｆａｃｔｏｒ）＝ｌ一查全率而查准率的互补数就是误检率。误检率（ｎｏｉｓｅｆａｃｔｏｒ）＝１一查准率如果一个分类系统中与某一需求有关的信息共２００条，实际检出３００条，其中相关信息为１５０条，则分类结果各项可表示为：查全率＝［１５０／２００］Ｘ１００％：７５％第２１页②查准率Ｐ＝［ａ／（ａ＋ｂ）］Ｘ１００９６漏检率＝１－－７５％＝２５％基于词频统计的文本分类模型研究上海师范大学硕士学位论文查准率＝［１５０／３００］Ｘ１００％＝５０％误检率＝１－－５０１９６＝５０％由此可见，查全率与漏检率，查准率与误检率为互补关系，在实际检索过程中，必须同时兼顾查全和查准率，不可片面追求某一方面。这是因为，若要增大查全率，必须使需求表达尽量全面，以确保获得所有可能相关的信息，因此，用户最终得到的信息量要比实际需求的信息量大，这就造成了相对低的查准率；若要增大查准率，必须准确表达用户需求，从而保证用户获得的信息肯定是需要的信息，这就造成一些相关信息不可避免地会被漏掉，降低了查全率。３．２决策树分类３．２．１决策树工作原理决策树啪１，又称判定树，是一种类似二叉树或多叉树的树结构。树中包含三种结点：①根结点（ｒｏｏｔｎｏｄｅ），它没有入边，但有零条或多条出边。②内部结点（ｉｎｎｅｒｎｏｄｅ），恰有一条入边和两条或多条出边。③叶结点（１ｅａｆｎｏｄｅ）或终结点（ｔｅｒｍｉｎａｌｎｏｄｅ），恰有一条入边，但没有出边。树中的每个非叶结点（包括根结点）对应于训练样本集合一个非类别属性的测试，非叶结点的每一个分枝对应属性的一个测试结果，每个叶子结点则代表一个类或类分布。从根结点到叶子结点的一条路径形成一条分类规则。决策树可以很方便地转化为分类规则，是一种非常直观的分类模式表示形式。图３—２哺乳动物分类问题的决策树决策树的构建是一种自上而下、分而治之的归纳过程，本质是贪心算法。从根结点开始，对每个非叶结点，找出其对应样本集中的一个属性（本文中称为测试属性，例如上例中的体温属性）对样本集进行测试，根据不同的测试结果将训练样本集划分成若干个子样本集，每个子样本集构成一个新的结点，对新结点再第２２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文重复上述划分过程，这样不断循环，直至达到特定的终止条件。测试属性的选择和如何划分样本集是构建决策树的关键环节。３．２．２构造及规则生成决策树的构造通常包括两个步骤：利用训练集生成决策树；再对决策树进行剪枝。下面我们就分别加以介绍：（一）决策树生成阶段决策树的生成算法的流程图如下所示：是图３—３决策树算法流程图第２３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文相应的实现过程可以分为以下几个步骤：１．表示分类的依据属性。决策树必须为不同类型的属性提供表示属性测试条件和其对应输出的方法。这就需要用户根据实际需求以及所处理数据的特性，对训练样本数据做进一步的处理，从而得到分类的依据属性（称为类别标识属性），并将其合理的表示出来。２．选择优势划分属性。根据适当的算法进行计算，在决策属性集中选择最有分类标识能力的属性作为当前决策结点，例如本课题采用的信息增益作为衡量属性优劣。３．划分当前结点对应记录集。根据当前决策结点属性取值的不同，将训练样本数据集划分为若干子集（每个取值形成一个子集）。４．针对上一步中得到的每一个子集，重复进行上述的２、３两个步骤，直到最后的子集中的所有元组都属于同一类；或者所有的记录都具有相同的属性值。５．生成叶子结点。通过上述步骤，我们就得到了对数据元组进行分类的决策树。由决策树的每一个从根结点到叶子结点的分枝都可以得到一条用于判断数据元组类别归属的初步规则，但得到的初步规则中，有一些预测规则准确性较低，因此需要对上述得到的决策树进一步处理，这个进一步处理的过程可由下一阶段，即称为“剪枝”的过程完成。（－－）剪枝在决策树算法实施的过程中，由于训练样本中往往存在着一些异常和噪声，它们的存在造成了在决策树异常分枝的产生；另外，训练样本集如果规模较大，也会导致分枝的数目和层数较多，这两方面都会影响生成有效的决策树。剪枝正是对上一阶段所生成的决策树进行检验、校正和修正的过程，主要是采用新的训练样本数据集（称为检验数据集）中的数据检验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。按照其实施的时间不同，剪枝分为两种：先剪枝和后剪枝。先剪枝是指在决策树完全生成前就停止决策树的生长，这就需要采用更具限制性的结束条件。虽然速度快，但是容易遗漏有价值的子树。后剪枝是指，首先生成与训练数据完全拟合的决策树，然后按照自底向上的方式逐层开始剪枝。如果删除某个结点的子第２４页基于词频统计的文本分类模型研究上海师范大学硕士学位论文结点后，决策树的准确度没有降低，那么就将该结点变为叶子结点。决策树越小就越容易理解，存储与传输的代价也较小，但结点过少会造成准确度下降，因此要在树的规模与准确度之间做出权衡，防止过度剪枝（ｏｖｅｒ—ｐｒｕｎｉｎｇ）。决策树生成之后，可以从中推导出分类规则，这个步骤称为规则抽取。每个叶结点表示一条规则，规则的左部（条件）是从根结点出发到达该叶结点路径上的所有中间结点构成的一个“与”判断，规则的右部（结论）是叶子结点的类别。在对新样本进行分类时，如果样本满足某条分类规则的条件判断，那么它的类别就是规则右边的值。如果分类规则太多，还需要对规则进行处理，合并成更简单的形式。以决策树方式表示的知识可以用“ＩＦ—ＴＨＥＮ”的形式表示。对于图３－２表示的决策树，它的分类规则如下：ＩＦ体温＝冷血ＴＨＥＮ非哺乳动物；ＩＦ体温＝恒温ＡＮＤ是否胎生＝否ＴＨＥＮ非哺乳动物；ＩＦ体温＝恒温ＡＮＤ是否胎生＝是ＴＨＥＮ哺乳动物。’ＩＦ—ＴＨＥＮ”规则形式对于人们来说是一种易于理解的方式，尤其是在决策树很大的情况下其优势更为明显。３．２．３ＩＤ３算法ＩＤ３算法。２１是决策树生成中一种具体实现算法，其基本思想是采用信息论中互信息。”的概念，用信息增益作为决策属性分类判别能力的度量，进行决策结点属性的选择。１９４８年香农提出并发展了信息论，研究以数学的方法度量并研究信息。通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量的大小。他提出了一系列的概念“１：１、若存在ｎ个相同概率的消息（ｍｅｓｓａｇｅ），则每个消息的概率Ｐ是１／ｎ，一个消息的传递信息量为一ｌｏｇ：（Ｐ）＝ｌｏｇｚ（ｎ）。例如：８个事件，则ｌｏｇ。（８）＝３，需要３个比特来表示一个消息。２、若给定的概率分布Ｐ：（Ｐ。，Ｐ２，…Ｒ），则由该分布传递的信息量成为Ｐ的熵，即Ｉ（Ｐ）＝一（Ｐｌ＊ｌｏｇ：（ＰＩ）＋Ｐ芦ｌｏｇ：（Ｐｊ）＋…Ｐ３＊ｌ０９２（Ｐｎ））（３－１）例如：若Ｐ是（０．５，０．５），则Ｉ（Ｐ）是１；若Ｐ是（０．６７，０．３３），则Ｉ（Ｐ）是０．９２；若Ｐ是（１，０），则Ｉ（Ｐ）是０。由该例子我们可以发现：概率分布越均匀，其信息量越大。第２５页基于词频统计的文本分类模型研究上海师范大学硕士学位论文３、若一个记录的集合Ｔ根据类别属性的值被分为互相独立的类Ｃ。，Ｃ：，…Ｃ。则识别Ｔ的一个元素所属哪个类所需要的信息量是ｉｎｆｏ（Ｔ）＝Ｉ（Ｐ），其中Ｐ是（Ｃ。，ｃ２，…Ｃ。）的概率分布，即Ｐ·恻，饼，．．．，钟为：ｃｓ哪４、若我们先根据非类别属性ｘ的值将Ｔ分成集合ＴＩ，Ｔ２，…Ｌ，则确定Ｔ中一个元素类的信息量可通过确定Ｔ；的加权平均值来得到，即Ｉｎｆｏ（Ｔ。）的加权平均值ｌｎｆｏ（Ｘ，Ｔ）－喜留×Ｉｎｆｏ（Ｔｉ）５、将信息增益Ｇａｉｎ（ｘ，Ｔ）定义为：（３－３）Ｇａｉｎ倦，ｒ）一ｌｎｆｏ（Ｔ）－Ｉｎｆｏ（Ｘ，ｒ）（３－４）ＩＤ３算法流程为：首先，依据测试属性取值进行样本集划分，有几个不同的测试属性取值就将样本集划分为几个样本集：然后，决策树在相应于该样本集结点上长出新的叶子结点。由于决策树的结构越简单越能从本质的层次上概括事物的规律，我们期望非叶结点到达后代结点的平均路径总是最短，即生成的决策树的平均深度最小，这就要求在每个结点选择好的划分。香农的信息论表明：系统的不确定性越小，信息的传递就越充分。给出伪代码如下，其中列表Ｌｉｓｔ表示待处理结点存放的列表；Ｎ为当前处理结点；结点ａ表示树中的结点的数据结构，用于保存已用属性集和训练例子集，该子集是整个训练集的一个子集。算法３．ＩＩＤ３算法：１：使用包含所有记录的集合创建新结点ａ２：对ａ结点实施递归扩展Ｒｅｃｕｒｓｉｏｎ（ａ）３：４；５：６：７：８：９：ｗｈｉｌｅ树结点列表Ｌｉｓｔ非空ｄｏ取出Ｌｉｓｔ歹Ｏ表的头元素放入Ｎ中从Ｌｉｓｔ中删除该头元素ｉｆ赋给ａ的所有例子不属于同一类别Ｒｅｃｕｒｓｉｏｎ（ａ）ｅｎｄｉｆｅｎｄｗｈｉｌｅ第２６页基于词频统计的文本分类模型研究上海师范大学硕士学位论文Ｒｅｃｕｒｓｉｏｎ递归程序１：ｉｆ２：３：ａ中所有属性均已使用Ｒｅｔｕｒｎｅｎｄｉｆ４：计算信息增益，选择最优属性Ｘ５：将Ｘ插入到ａ的已用属性列表中，以确保同一路径上该属性不会被再用６：ｆｏｒ７：８：ｘ的每一个取值给结点ａ增加新的子结点将该子结点压入Ｌｉｓｔ中９：ｅｎｄｆｏｒ１０：ｆｏｒ赋给ａ的每一训练例子ｔ１１：按照属性ａ的取值，将ｔ赋给相应的子结点１２：ｅｎｄｆｏｒ下面通过简单的示例说明ＩＤ３算法中最佳测试属性选择的具体操作及决策树的生成过程步骤。这里的数据取于我们实验数据的一个子集。如下的“神经网络类基本属性信息”表的结构及数据，见表３－１所示。表３—１神经网络类基本属性信息取属性“类（神经网络）”作为类别标识属性，其值为“１”时表示此元组属于神经网络类文档，其值为“０”时表示此元组不属于神经网络类。属性“ＢＰ”、“故障诊断”、“模式识别”、“神经网络”，“预测”、“遗传算法”作为决第２７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文策属性集，这里我举一个简单的例子，所有属性都是离散的属性。根据示例中的类别标识属性（类（神经网络））的取值，将该示例分为２类（即ｍ＝２，一类是属于神经网络类，一类是不属于神经网络类），分别是Ｃ。，ｃＤ。训练样本数据集Ｓ中，共有９个元组，其中，Ｃ。，Ｃｏ所对应的子集Ｒ。，凡中元组的个数分别为ｒＩ＝５，ｒｏ＝４。为了计算每一个决策属性的信息增益，首先利用公式３－１计算得到集合ｓ的关于分类的期望信息量：ｌ（ｒｌ，ｒｏ）一１（５’４）Ｉ弓ｌｏｇ：若１０９：石４－０．９９，对每一个决策属性计算其期望信息量（即熵值）：对属性“ＢＰ”有：当“ＢＰ”＝‘１’时：ｓｌｌ＝２，￥２１＝４，Ｉ（ｓｌＩ，ｓ２．）＝Ｏ．９１８当“ＢＰ”＝…０时：ｓ１２：３，ｓ２２＝Ｏ，Ｉ（ｓ１２，Ｓ≈）＝Ｏ由此得出属性“ＢＰ”的熵值：Ｅ（ＢＰ）＝吾ｘＩ（Ｓ蚶：１）＋吾×№：，ｓ国一０．６４８因此属性“ＢＰ”的信息增益为：Ｇａｉｎ（ＢＰ）＝Ｉ（ｒｌ’ｒｏ）一Ｅ（ＢＰ）＝Ｏ．９９１—０．６４８＝０．３４３同理，可以分别得到属性“故障诊断”、“模式识别”、“神经网络”、“预测”、“遗传算法”的信息增益：Ｇａｉｎ（故障诊断）＝０．９９１—０．９８４＝０．００７Ｇａｉｎ（模式识别）＝０．９９１－０．６７１＝０．３２Ｇａｉｎ（神经网络）＝０．９９１－０．４０１＝０．５９Ｇａｉｎ（预测）＝０．９９１－０．７６６＝０．２２５Ｇａｉｎ（遗传算法）＝０．９９１—０．９１８＝０．０７３由于属性“神经网络９具有最大信息增益值，故而选择该属性为最佳测试属性而作为决策树的根结点。由此属性“神经网络”把训练集分为两个分支（即两个子集），如表３—２所示为神经网络＝“１”的元组信息表，表３－３所示为神经网络＝“０”的元组信息表。第２８页基于词频统计的文本分类模型研究上海师范大学硕士学位论文ＢＰ故障诊断模式识别神经网络预测遗传算法类（神经网络）表３—２神经网络＝“１”的元组信息表ＢＰ故障诊断模式识别神经网络预测遗传算法类（神经网络）表３—３神经网络＝“０”的元组信息表对应每一个分枝，重复上述步骤，例如，对于分枝属性“神经网络”＝“１”的子集来说，即表３－２给出的子集，其所有的实例都属于同一类，所以不必对这个子集再进行处理。对表３—３中的子集重复上述属性选择操作，只是在进行最佳测试属性选择时，属性“神经网络”己被排除，也就是考虑的属性个数减少了１。同样，依次对其它分枝属性进行相同操作，可得到一个完整的决策树（见图３—４所示）．图３—４由ＩＤ３算法生成的决策树分类规则：第２９页基于词频统计的文本分类模型研究上海师范大学硕士学位论文对生成的决策树进行遍历，从根结点到叶子结点上的每一条路径对应一条规则。在上述实例中，由决策树的三个分支生成三条分类规则如下：ＩＦ神经网络＝ＯＩＦ神经网络＝ＯＩＦ神经网络＝１ＡＮＤＢＰ＝ｌＴＨＥＮ０ＡＮＤＢＰ＝０ＴＨＥＮＴＨＥＮ１１从上面的示例不难看出，ＩＤ３算法利用信息增益原理进行分类属性选择的思想，保证了每次选择新的测试属性时，决策树沿着信息量最大的方向生长，以最快的方式完成信息的分类，减小决策树拓展的层数，这样就可以保证生成深度最小，规模最小的决策树。决策树规模的大小与规则提取的数量和难易程度相关，规则是基于决策树生成的，所以树的规模大，产生的规则数量就会大，树的规模小，产生的规则数量就会相应的小，所以从产生的规则数量我们就可以知道决策树的规模程度，分类规则的条数通常小于或等于决策树的分支数，所以分类规则简洁。这个例子只是对本课题所有实验数据中的非常少的个别数据进行处理得到的，仅仅希望说明算法如何是产生作用形成决策树的，形成的分类规则和决策树并不代表真实的分类规则，而要得到相对正确的结果必须通过大量的训练数据。３．２．４ＩＤ３决策树分类器介绍在该节中讲述本课题基于Ⅲ３算法实现的一个分类器，交互界面如图３．５所示。通常的决策树构建算法都是一个深度优先树增长的过程，因此，在扩展新的决策属性结点时，我们把每一个需要考虑扩展的结点都放到一个列表里，按后进先出（ＬＩＦＯ）的方式实现深度优先的决策树，并可以根据训练集产生的决策树得到相应的分类规则。图３－５ＩＤ３决策树分类器界面第３０页基于词频统计的文本分类模型研究上海师范大学硕士学位论文在程序界面上，我们可以看到这样的交互按钮，它们的作用如下：“输入模式文件”：即定义属性域的文件，文件里有文件类型、字符集及属性域的定义等信息。“输入训练数据”：从文件中输入训练实例数据。“输入测试数据”：从文件中输入测试实例数据。“生成决策树”：在输入了模式文件和训练数据后，点击此按钮便会生成一棵基于训练集数据的决策树。“生成分类规则”：根据生成的决策树产生分类规则。“决策树测试”：实现对测试数据测试，验证决策树分类效果。３．２．５ＩＤ３算法分类实验为了更好的测试ＩＤ３算法进行分类的性能优劣，我设计了如下的工作实验模型：首先选择一个实验数据的集合，在本实验中数据均下载自中国期刊全文数据库，该集合中包含了神经网络类的论文和非相关论文，分别作为分类的训练集和测试集；然后对训练集运用ＩＤ３算法，得到对应的决策树；最后使用该决策树对不同规模随机选择的测试集进行重复的测试。如果该实验中产生的决策树能够很好地对测试集中的实例进行分类预测，那么认为该算法就是一个好算法。依据该实验模型，我选取１０００篇文档作为训练集（其中９００篇为神经网络类文章，另外１００篇为其它类文章），２００篇作为测试集（１００篇为神经网络类文章，另外１００篇为其它类文章）。训练的规模ｓ分别为１０、２０、４０、６０、踟、１００、１２０、１４０来进行测试，在训练集的每一种规模下，采用随机的选择Ｓ／２规模的神经网络类文章，Ｓ／２规模的其他类文章两次来进行实验，对每种规模下的测试性能采用两次测试的平均值。实验结果数据如下表３４，图形显示如图３－６所示ｌ训练集规模１０７０．２９２０７２．７６４０６０８０８４．２２１００８９．２８１２０８７．７３１加８８．３９Ｉ准确率（％）７９．８９７６．５５表３＿４不同训练集规模下的测试平均准确率第３１页基于词频统计的文本分类模型研究上海师范大学硕士学位论文嘲曩纛氘图３＿６不同规模训练集下的ＩＤ３算法学习曲线由图３－６可以注意到，随着训练样本的增加，预测的准确度也在提高（图中所示的曲线也称为快乐图）。这是一个好现象，证实在数据中确实存在某种模式，通过ＩＤ３学习算法能够很好的将它提取出来。对训练集提取关键词、统计词频并按频率大小递减排序，选取不同维数的特征向量进行研究。对排序后的关键词分别取１０、２０、４０、６０、∞、１００、１２０作为文档的特征向量维数。实验结果数据如表３－．５所示。向量维数查全率（％）查准率（％）１０２０４０６０８０１００１２０９６９６９８９７９６９８９７８１．９６９４．９３９６．３１９０．９３８９．２９９６．１９９８．５７表３－５决策树的查全率和查准率依据表３－５中的实验结果数据，分别以向量维数为横坐标和查全率为纵坐标，以向量维数为横坐标和查准率为纵坐标分别作图３—７和图３．８。第３２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文鸯垒率鐾向纛雅致图３—７查全率赢准摹罂图３－８查准率通过上面的图表信息，我们可以看出：（１）对于查全率（图３－７），可以看到随着向量维数的增加，查全率波动幅度变化比较小，测试曲线非常平稳，也就是其性能是稳定的。（２）对于查准率（图３－８），由图得知，在向量维数增加的过程中，其准确率也随着增加。由上述的实验分析可以得出，基于ＩＤ３算法实现的决策树分类模型，可以相对较好的完成分类工作。３．３向量空间模型３．３．１工作原理向量空间模型（ＶｅｃｔｏｒＳｐａｃｅＭｏｄｅｌ，ＶＳＭ）㈨是由Ｇ．Ｓａｌｔｏｎ等人在２０世纪６０年代提出的。它把文档简化为以项的权重为分量的向量表示，把分类过程简第３３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文化为空间向量的运算，使得问题的复杂性大大降低。在向量空间模型中，令Ｎ表示整个文本分类系统中的一个类别的关键词的总数，文档被表示为由关键词的权重构成的Ｎ维向量：力－（Ｍ，，ｗ２ｌ，。．ＷＮＩ），Ｗ。，为特征词ｉ在文档ｄｊ中的权重，如果为０，表示该词在ｄｊ中不出现。待分类文档也表示为由每个类别的关键词的权重构成的Ｎ维向量：ｄ一（呐一，Ｗ２ｄ，．．ｏＷＮｄ），ｗ。。为用户给定的关键词ｉ的权重嘲。权重的具体定义如下：假设文档集Ｄ＝｛ｄｉ），ＩＤｌ＿Ｓ，（ＩＤＩ表示集合Ｄ中元素的个数），特征项集Ｔ＝｛≈），闻＝Ｍ。定义特征项ｑ在文档ｄｉ中的权重ｗⅡ为：％ｔ孵×嘲，ｌｓｉ‘ｓ，ｌｓ，‘Ｍ其中ｔｆｉｊ为特征项ｔ，在文档ｄ。中出现的频率，称为项频；ｉｄｆＪ是文档集Ｄ中出现特征项ｔ，的文档数量，称为文档频率。如果特征项ｔ，在文档ｄ。中的作用较大，必然有较高的项频和相对较低的文档频率，故其权重Ｗ。，也较大。ｉｄｆｊ的计算可以用如下的公式表示，其中ｎ表示数据全集中文档的总数，ｎ。表示包含关键词ｉ的文档的总数：狮一ｌｏｇ（＇－－＇）在此基础上，建立文档的向量空间模型，以ｔ。，ｔ。…，ｔ。为坐标轴，把文档ｄｔ表示为Ｍ维向量（霄ｍＷｍ…，Ｗ－－）。文档ｄｔ和ｄ，之间的相似程度Ｓｉｍ（ｄ，，ｄ，）可以表示为：Ⅳ厂ｉ—————面——一Ｓｉｍ（ｄｌ，ｄｓ）ＩＣｏ￥０－荟％‘～／Ｊ（荟％２）（荟％２）’１“√“（４－８）采用向量空间模型表示文档的特征后，用户的需求信息就可以看成是一个文档，也就可以表示为一个向量ｕ。文档与用户兴趣的相似程度就可以用文档向量Ｖ与用户兴趣向量Ｕ的余弦相似度Ｓｉｍ（Ｖ，Ｕ）来表示。由上述可以看出，向量空间模型的关键在于特征向量的选取和特征向量的权值计算两个部分。在选择特征项时，应当选取包含语义信息较多，对文本的表示能力较强的语言单位作为特征项，我们在实现时是对文档进行词频统计，根据词频进行排序，选择词频较高的部分作为特征项。较好的查询表达式通常包含能够将一些特定文档与文档集合中其它文档区别开来的特征项，这种特征项不仅要有较高的出现频率，还要在文档集合中较第３４页基于词频统计的文本分类模型研究上海师范大学硕士学位论文少的文档中出现。将频率因子和文档集因子相乘就可以实现此目的，这就是文本检索模型中最常用的ＴＦＩＤＦ赋权因子。当文档较长时，查询式与文档进行匹配的可能性较大，所以长文档比短文档更有可能被提出来，因此引入规格化因子来消除文档长度对匹配结果的影响。假定Ｗ代表特征项的权重，最后的规格化因子定义为：—只—一Ⅳ√荟啊２在分类过程中，通过计算出每个文档与查询模板间的相似度与设定的阈值来进行对比，将相似度大于某特定阈值的所有文档或者具有较高相似度的前ｒ１个文档类别作为分类结果输出。３．３．２分类器实现及实验分析向量空间分类模型相对比较简单，在实现的时候没有具体的运行界面，只是通过设定表示实验数据和实验结果的三个文件来实现。这三个文件所代表的含义如下：ｋｅｙｗｏｒｄＦｒｅｑｕｅｎｃｙ．ｔｘｔ文件：存放关键词及其对应的出现频率，该文件共有Ｎ行，Ｎ表示向量空间的维数，即用多少个关键词来表示一篇文档。ｔｒａｉｎｉｎｇＤａｔａ．ｔｘｔ文件：存放训练数据集合的文件，该文件共有Ｍ行，Ｍ表示训练集合中文档的篇数，由该文件可以计算出ｉｄｆ的值。ｔｅｓｔＤａｔａ．ｔｘｔ文件：存放测试数据集合的文件，该文件的格式和ｔｒａｉｎｉｎｇＤａｔａ．ｔｘｔ文件的格式一致，但其中的数值表示该词出现了多少次。通过程序运行，可以将所有的测试文档向量和由训练文档得到的类平均文档向量进行相似度计算，将计算的结果排序后由大到小输入到保存结果的文件ｒｅｓｕｌｔＤａｔａ．ｔｘｔ中。在实现ＶＳＭ分类器的基础上，我设计了如下的实验模型，选取１０００篇文档作为训练集（其ｑ，９００篇为神经网络类文章，另夕ｂ１００篇为其它类文章），２００篇作为测试集（１００篇为神经网络类文章，另外１００篇为其它类文章）。向量维数分别选取１０、２０、４０、６０、８０、１００、１２０。由于向量空间模型需要进行特征向量间的相似度计算，并且分类的效果跟设定的阈值是直接相关的，而相似度阈值的确定是十分困难的，一般采用预定初始值，然后给出测试文本进行文本分类，再根据分类的准确程度调整阈值。此处的实验采用ＴＦＩＤＦ赋权因子方法，并设定阈值分别为０．２５、０．３５、０．４５、０．５５来进行查全率和查准率的实验。第３５页基于词频统计的文本分类模型研究上海师范大学硕士学位论文实验结果数据：表３—６、３—７为向量空间模型在阈值分别为Ｏ．２５、０．３５、０．４５、０．５５的情况下的实验数据。父１０２００．２５Ｏ．３５吣ＦＴＦＴ０５５ＴＦＴＦ１∞１∞１∞１∞９８２０ｌ∞１∞１００２０ｌｏｏ２０１００２０２０２０１００２０１∞９９２０４０１９１６１∞９９１５１５６０１６９９１５８１４９９１３８０１０９８９６８９２８１∞１２０９６８９１８８９６８６６６４２５０２３５１２６ｌ表３—６不同阈值对应实验数据向量维数０．２５查全率（％）０．３５０．４５０．５５０．２５查准率（％）Ｏ．３５０．４５Ｏ．５５１０１００１００１００１００８３．３３８３．３３８３．３３８３．３３２０１００１００１００１００８３．３３８３．３３８３．３３８３．３３４０１００１００１００９９８４．０３８６．２ｌ８６．９６８６．８４６０１００９９９９９９８６．２０８６．８４８７．６ｌ８８．３９８０９８９８９６９２９０．７４９２．４５９２．３ｌ９２．００１００９６９１８９８６９２．３１９１．９２９３．６８９３．４８１２０６４５０３５２６９６．９７９６．１５９７．２２９６．３０表３—７查全率、查准率依据上述实验结果数据，分别以向量维数为横坐标，查准率为纵坐标；以向量维数为横坐标，查全率为纵坐标作图，比较向量空间模型在阈值分别为０．２５、０．３５、０．４５、０．５５下的查全率和查准率。分析阈值对查全率和查准率的影响，如第３６页基于词频统计的文本分类模型研究上海师范大学硕士学位论文下列图所示。鸯难事求翔璧维数图３－９不同阈值与查准率鲞金率亲向量维数图３一１０不同阅值与查全率从上述的向量空间模型的数据可以看出，向量空间模型的查准率和查全率对阈值是相当敏感的。闽值对模型的过滤性能的影响是直接的，阙值越大，对过滤的文档的相似度要求也越高，漏检的文档就越多，这样就相应的提高了查准率，但查全率却大大降低，查全率和查准率之间相互制约的现象非常明显，即提高查全率会使查准率下降，提高查准率会使查全率下降。所以使用适当的方法确定阙值是必要的，同时兼顾查全率和查准率。通过实验验证了阈值为０．４５是一个合适的阈值选择。在本课题最后章节中的模型比对部分都是取阈值为０．４５。第３７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文３．４小结（１）详细介绍了文本分类的基础知识，阐述了文本分类所包含的三个步骤：模型构造、模型测试和模型应用。借鉴了信息检索中的查全率和查准率作为评定分类性能优劣，并对两者的关系做了简单的分析。（２）介绍了决策树的原理及构造过程。并在此基础上详细阐述了决策树中属性选择方法较好的ＩＤ３算法。实现了一个基于ＩＤ３算法的决策树分类程序，以深度优先方式生成决策树，对中文信息进行有效的分类，通过实验表明决策树分类器确实是一种有效的分类技术。（３）介绍了文本分类算法中的向量空间模型算法的工作原理。向量空间模型可以实现文档的自动分类和对查询结果的相似度排序，能够有效提高检索效率；它的缺点是相似度的计算量大，当有新文档加入时，则必须重新计算词的权值。详细给出了模型中表示文档向量的特征项权值的计算方法，实现了一个基于特征向量权值的分类器，以作为和其它分类器进行分类比较的参照算法。第嚣页基于词频统计的文本分类模型研究上海师范大学硕士学位论文第四章贝叶斯分类方法改进贝叶斯网络也被称为贝叶斯网，因果概率网络。它结合了图论和概率论的知识，提供了一种紧凑的图形方法，用于表达随机变量之间复杂的概率不确定性，从而发现数据间的潜在关系。在这个网络中，用结点表示变量，有向边表示变量间的依赖关系。随着近年来数据库规模的不断扩大，贝叶斯网络逐渐开始应用于大规模数据库的数据挖掘和知识发现，从而为决策支持提供了有力手段，它独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性，使其成为数据库知识发现和决策支持系统的有效方法㈨。４．１贝叶斯网络４．１．１贝叶斯理论基础贝叶斯方法是一种研究不确定性的推理方法。不确定性常用贝叶斯概率表示，它是一种主观概率。通常的经典概率代表事件的物理特性，是不随人意识变化的客观存在。而贝叶斯概率则是人的认识，是个人的估计，随个人的主观认识的变化而变化，即事件的贝叶斯概率是对该事件的置信程度，因此是一种主观概率。本课题要介绍的贝叶斯网络分类模型正是基于这个理论基础实现的，它是一种基于概率推理的图形化网络，以贝叶斯公式作为这个概率网络的基础。为了更清楚的了解贝叶斯网络分类的原理，有必要了解下贝叶斯的相关理论知识ｏ”：１、先验概率（ｐｒｉｏｒｐｒｏｂａｂｉｌｉｔｙ）：先验概率是根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。先验概率一般分为两类，一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。２、后验概率（ｐｏｓｔｅｒｉｏｒｐｒｏｂａｂｉｌｉｔｙ）：后验概率一般是利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后的更符合实际的概率。比如我们有ｘ表示属性集，Ｙ表示类变量。如果类变量和属性之间的关系不确定，那么我们可以将ｘ和Ｙ看作随机变量，用Ｐ（Ｙｌｘ）以概率的方式捕捉二者之间的关系。这个概率就称为Ｙ的后验概率，因为它利用了以往的属性概率Ｐ（ｘ），在ｘ发生的概率已知的情况下得到Ｙ的概率，而与之相对应地，Ｐ（Ｙ）称为Ｙ的先验概率，这个概率没有经过实验的证明。第３９页基于词频统计的文本分类模型研究３、上海师范大学硕士学位论文条件概率：我们把事件Ｘ已经出现的情况下，事件Ｙ发生的概率记作Ｐ（ＹＩｘ），并称之为在ｘ出现的条件下Ｙ出现的条件概率，而称Ｐ（Ｙ）为无条件概率。设Ｘ、Ｙ是两个事ｆ牛，且Ｐ（珍０，称Ｐ（ＹＩＸ）一器为在事件ｘ发生的条件下事件Ｙ发生的条件概率。４、联合概率：设ｘ、Ｙ是两个事件，Ｒｅ（ｘ），０，它们的联合概率为：Ｐ（ｘＤ—Ｐ０１Ｉｘ）Ｐ皤）－Ｐ（工ＩＹ）ｅ００·５、全概率公式：设实验肭样本空间为Ｓ肋确事件，Ｘ，Ｋ，…，ｌ二为Ｅ的一组事件，满足：①艺×一ｓ；②Ｋ，Ｋ，…，Ｋ互不相容；③刚，ｏ），ｆ一１＇２，…，ｎ。则有全概率公式：Ｐ（ｚ）一艺Ｐ佴朋Ｉｘ）·６、贝叶斯公式嘲：根据３、４和５中提到的内容，很容易推得众所周知的贝叶斯公式：确㈣。篇加坛…ｍＢｅｌｉｅｆａｃｙｃｌｉｃｐｒｏｂａｂｉｉｉｔｙ㈣，４．１．２贝叶斯网络模型贝叶斯信念网络（ＢａｙｅｓｉａｎＮｅｔｗｏｒｋｓ，ＢＢＮ）嘲１，又简称贝叶斯网络，用图形表示一组随机变量之间的概率关系。贝叶斯网络有两个主要成分：（１）一个有向无环图（ｄｉｒｅｃｔｅｄｇｒａｐｈ，ＤＡＧ），表示变量之间的依赖关系。（２）一ｔａｂｌｅｓ，ＣＰＴｓ），把各结点和它的直接个条件概率表（ｃｏｎｄｉｔｉｏｎａｌ父结点关联起来。在深入了解贝叶斯网络模型之前，我们先了解条件独立性假设的概念，它是贝叶斯网络进行定量推理的理论基础。有了这个假设，就可以减少先验概率的数目，简化计算和推理过程。在贝叶斯网络中给定父结点，一个结点与它的非后代结点是条件独立的。如果下面的条件成立：Ｐ（ＸＩＹ，ｚ）一Ｐ（Ｘ，ｚ）睁２）我们就说在给定ｚ的条件下，ｘ和Ｙ是条件独立的，利用上一节我们提到的相基于词频统计的文本分类模型研究上海师范大学硕士学位论文关概念，ｘ和Ｙ之间的条件独立也可以写成如下的形式，以便于我们理解条件独立性：Ｐ（Ｘ，Ｙ跏Ｚ等笋－等箸ｘ等一Ｐ（ＸＩＹ，ｚ）×尸彤ｌｚ）一Ｐ伍ｌｚ）×Ｐ（１，ｌｚ）（４－３）其中，（４—２）用于得到公式（４—３）的最后一行。可将ｎ元随机变量工；｛两，工：，…，ｘＡ的贝叶斯网络模型形式化表示为一个二元组曰－慨，砟）。Ｂ一僻，Ｅ）表示有向无环图，其中ｘ－“，屯，…，‘｝为结点集合，每个结点可看成取离散或连续值的变量（本课题限定其只取离散值，连续值需做离散化处理）；Ｅ是有向边的集合，每条边表示两结点问依赖关系，依赖程度由条件概率参数决定。称乓为ＢＮ模型网络结构。耳－｛ｐ“Ｉ％。）：‘ｅｘ｝是贝叶斯网络模型的一组条件概率分布的集合。在各结点取离散值的情况下，毋为一组条件概率表的集合。％是在岛中ｔ所有父结点的集合（若没有父结点则７‰＝由），ｐ＠Ｉ刀ｚ）表示结点工，在其父结点某一取值组合状态下的条件概率分布，这说明，在贝叶斯网络模型中，结点的取值依赖于其父结点的取值状态。有了我们给出的条件独立假设的基础，借助公式（４—３），我们可以得出这样的结论：对于适当顺序的结点集ｘ一缸。，工：，…，工。｝，其贝叶斯网络模型的网络结构决定于如下一组条件独立性假设：，纯Ｉ五，屯，…，玉一。）－ｐ＠ｌ石墨）工的联合概率分别为：ｉ一１，２，…，以·（４．４）ｐ暖）。Ｉ：ｌｐ“Ｉ～）‘＂’公式（４—５）表明联合概率分布可由各个局部相互作用模型的积的因式形式来表示。贝叶斯网络的一个关键特征是它提供了一种把联合概率分布分解为局部分布的方法：即它的图形结构表示了变量间概率依赖关系，具有清晰的语义特征，这种独立性的语义指明如何组合这些局部分布来计算变量间联合分布的方法。网第４１页基于词频统计的文本分类模型研究上海师范大学硕士学位论文络的定量部分给出变量间不确定性的数值度量。这里我们引入一个具体的贝叶斯网络的例子：Ｐ忸ｌａ）－ｏ．７５ｐ（ＢＩａ）·０．２Ｐ（ｃ１４）－Ｏ．８５ｅ（ｃｌａ）－０３Ｃ、－０．８Ｃ１－０．６Ｐ（ＤｌＢ，ｃ）－０．４Ｐ（ＤｌＢ，ｃ）－０．１图４—１贝叶斯网络简单模型可以发现，贝叶斯网络提供了一种表示因果信息的方法，用来发现数据间的潜在关系。当网络结构确定之后，就可以用梯度下降法训练网络，每次迭代修改权系数，最终收敛到一个局部最优解。４．１．３贝叶斯网络的构建方法构建贝叶斯网络包含两个步骤：（１）创建网络结构；（２）估计每一个结点的概率表中的概率值。网络拓扑结构可以通过对主观的领域专家知识编码获得。算法４．１给出了归纳贝叶斯网络拓扑结构的一个系统的过程。算法４．１１：贝叶斯拓扑结构生成算法设Ｔ＝（ｘ１，）【２，…Ｘｄ）表示变量的一个总体次序ｊ＝ｌｔｏ２：ｆｏｒ３：４：５：６：７：ｄｄｏ令ｘＴ（Ｊ）表示中第ｊ个次序最高的变量令丌（ｘｔｏ））＝｛ｘＴ（１＇，ｘｔｍ，…，Ｘ”ｍ）表示排在前面的变量的集合从Ⅱ（ｘＴｏ，）中去掉对ｘ，没有影响的变量（使用先验知识）在ｘＴ（ｊ）和Ⅱ（ｘＴａ，）中剩余的变量之间画弧ｅｎｄｆｏｒ该算法保证生成的拓扑结构中不包含环，这一点的证明也很简单。如果存在环，那么至少有一条弧从低序结点指向高序结点，并且至少存在另一条弧从高序第４２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文指向低序结点。由于算法中我们不允许从低序到高序结点的弧存在，因此拓扑结构中不存在环。然而，如果我们对变量采用不同的排序方案，得到的网络拓扑结构可能会有变化。某些拓扑结构可能质量很差，因为它在不同的结点之间产生了很多条弧。从理论上讲，可能需要检查所有ｄ！种可能的排序才能确定最佳的拓扑结构，这是一项计算开销很大的任务。一种替代的方法是把变量分为原因变量和结果变量，然后从各原因变量向其对应的结果变量画弧。这种方法简化了贝叶斯网络结构的建立。一旦找到了合适的拓扑结构，与各结点关联的概率表就确定了。在贝叶斯网络构造过程中一般需要在下面两个方面作折衷：一方面为了达到足够的精度，需要构建一个足够大的、丰富的网络模型；另一方面，要考虑构建、维护模型的费用和考虑概率推理的复杂性。一般来讲，复杂的模型结构，它的概率推理的复杂性也较高，而这往往是影响贝叶斯网络效率的一个重要方面。实际上建立一个贝叶斯网络往往是上述各步迭代地、反复地交互过程。４．２贝叶斯分类器及其分类原理４．２．１分类原理及分类器介绍贝叶斯分类的原理最主要利用了贝叶斯定理和最大后验假设，分别介绍如下：贝叶斯定理：在观察到数据之前，根据背景知识或经验确定某个假设空间Ｈ中的假设ｈ成立的概率为Ｐ（ｈ），称ｈ为先验概率。Ｄ－＠，ｄ２，－－．，以）是一个训练数据集合，在没有关于哪个假设成立的知识而观察到Ｄ的概率，称为Ｄ的先验概率，记Ｐ（Ｄ）。在假设ｈ成立的条件下，观察到Ｄ的概率记为Ｐ（ＤＩｈ）。在观察至，ＪｉＪｉｌ练数据Ｄ的条件下，假设ｈ成立的概率Ｐ（ｈｌＤ）称为ｈ的后验概率。后验概率反应ＴｉＪＩＩ练数据对假设成立概率的影响，它是依赖于Ｄ的。在已知Ｐ（ｈ）、Ｐ（ＤＩｈ）和Ｐ（Ｄ）时，贝叶斯定理提供了计算一个假设ｈ的后验概率方法，因而成为贝叶斯理论的基石：ｐ（ｈｌＤ）＝Ｐ（Ｄ…Ｉｈ…）Ｐ（ｈ）（４－６）ｒＩＵ）最大后验假设：对于给定的观察数据Ｄ，在Ｈ中发现最可能的假设ｈＥＨ。任何这样的具有最大可能的假设称为最大后验，可以记为＾脚：ＪＩｌＭ。ａｒｇ学Ｐ（ｈＩＤ）－ａｒｇｍａｘＰ（ＤＩｈ）Ｐ（ｈ）／Ｐ（Ｄ）第４３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文，·ａｒｇｍａｘＰ（Ｄｌｈ）ｐ（ｈ）（＂）在分类系统中，就是计算文档在各个类中的最大后验概率的过程。贝叶斯方法是一种通过已知的先验概率和条件概率来得到后验概率的方法，可以确定一个给定样本属于一个特定类的概率。在本课题中，为了对实验数据进行测试，使用了开源的基于ｊａｖａ语言的ＪａｖａＢａｙｅｓ软件，这是一个非常方便的贝叶斯分类器，为用户提供了图形化的操作界面，在建立好网络后，网络图形就展现在用户面前。对于该网络图形对应的文件，也可以方便的进行读写，从而可以快捷的对各结点的概率信息以及结点间的关系进行设置，大大提高了实验的效率。图形化显示界面如图４—２所示：图４－２ＪａｖａＢａｙｅｓ编辑器图４．２展示了具有一个类结点，并且带有１０个子结点的贝叶斯网络图形。利用界面上已有的功能按钮，很容易生成该贝叶斯网络并进行相应的设置。各按钮功能如下：Ｃｒｅａｔｅ：生成信息结点，画出点问关系。Ｍｏｖｅ：移动结点，改变结点的位置，可同时对多个结点同时操作。Ｄｅｌｅｔｅ：删除结点，可以一次性删除多个结点。第“页基于词频统计的文本分类模型研究上海师范大学硕士学位论文Ｑｕｅｒｙ：对结点进行概率查询，可以很方便的查询后验概率。Ｏｂｓｅｒｖｅ：设置网络观察结点。下面的三个按钮可帮助用户对网络中结点的名字、位置、参数、属性值等信息进行操作。总而言之，ＪａｖａＢａｙｅｓ是一个功能强大且操作方便的工具，图形化的编辑网络形式极大的方便了我们的实验处理。４．２．２朴素贝叶斯分类器朴素贝叶斯分类又称为简单贝叶斯分类。它将训练样本分解成特征向量和决策变量。假定一个特征向量的各分量相对于决策变量是独立的，也就是说各分量独立地作用于决策变量，这一假定称为类条件独立。作此假定是为了简化计算，所以称为“朴素的”。一般认为，只有在满足该条件独立的情况下，朴素贝叶斯分类才能获得精确最优的分类效果：在属性相关性较小的情况下，能获得近似最优的分类效果。这种假定不仅以指数级降低了贝叶斯网络的复杂性，而且在许多实际领域，即使违背这种假定，朴素贝叶斯分类也表现出相当的健壮性和高效性。它已经成功地应用到分类、过滤等数据挖掘的任务中。朴素贝叶斯分类的过程如下：（１）假定有变量集Ｕ一｛４，４，…，４ｌ，ｃ），其中４，以…，４是实例的属性变量，Ｃ是可以取ｍ个值（用于文本分类时，Ｃ是取１个值）的类变量。给定一个未知类标号的数据样本ｘ，朴素贝叶斯分类将其分类到类ｃｉ，当且仅当ｐ（ａＩｘ）＞Ｐ（ｑＩｘ），１主ｆ，，譬肼，，＿ｉｐ（ｃｉＩ工）最大的类ｃｉ称为最大后验假定。由贝叶斯式可知（２）由于ｐ俘）对于所有类都为常数，只需要ｐ（ｘＩＣＯｐ（ＣＯ最大即可。如果类的先验概率未知，通常取ｐ（Ｃ１）＝ｐ（Ｃ２）－．．．＿ｐ（Ｃｍ），从而只需ｐ（ｘＩｃｉ）最大化。类的先验概率也可以用Ｐ（Ｃｉ）＝ｓ。／ｓ计算，其中，Ｓ。是类ｃｉ中的训练样本数，Ｓ是训练样本总数。ｐ（ｃｉＩｘ）一警（ａｌ，ａ２，…ａｎ）表示各属性，则有其中口是正规化常数。以后验概率作为分类指标，即输出具有最大后验概率的类ｐ（Ｃｉｌａｌ，ａ２，．＊．ａ）－血篆掣唧（ｃｆ）ｎｐ（ａ｛Ｉｏ）ａ（３）假定属性值相互条件独立，即属性之间不存在依赖关系，设Ｘ由ｐ【口ｌ，４２，…。Ｊ㈤乞ｆ基于词频统计的文本分类模型研究上海师范大学硕士学位论文标签Ｃ：ｃ＿ａｒｇ带ｐ（ｃＪ）珥ｐ＠Ｉｑ）（４．９）其中Ｃ表示朴素贝叶斯分类器嗍㈣“”输出的目标值，常数ａ可以省略。（４－９）式可作为朴素的贝叶斯分类器的定义，其拓扑结构如图４—３所示。在实际计算时，上式中的项Ｐ（ｃ』）可以通过计算训练实例中ｑ出现的频率来估计·ｐ（ａ。ＩＣＪ）可以通过计算训练实例中Ｃｊ属于的属性ｎ，出现的频率来估计。ａ图４－３朴素贝叶斯分类器拓扑结构朴素贝叶斯分类器在文本分类中很常用。其基本思想是利用单词和类之间的联合概率来估计给定文本属于类的概率。朴素贝叶斯方法假设不同单词在给定类别下的条件概率分布是互相独立的。该假设使得朴素贝叶斯分类器不需要计算单词之间的联合分布概率，因此其速度远快于非朴素贝叶斯模型（达到指数复杂度）。实验过程中使用的中文文档来源于中国期刊全文数据库，选取神经网络类文章９００篇和其它类文章１００篇作为训练集；选取贝叶斯类文章１００和其它类文章１００篇作为测试集。对训练集提取关键词、统计词频并按频率大小递减排序，选取不同维数的特征向量进行研究。对排序后的关键词分别取１０、２０、４０、６０、８０、１００、１２０作为文档的特征向量维数，采用查准率和查全率作为性能的评价标准。朴素贝叶斯模型测试实验的结果数据：第４６页基于词频统计的文本分类模型研究上海师范大学硕士学位论文向量维数查全率（％）查准率（％）１０２０４０６０８０１００１２０９４９２９３９０８９８８８９８０．１８８６．５７８７．３１８８．７３８５．５９８５．１９８７．２９表４．１朴素贝叶斯测试结果数据４．２．３属性依赖贝叶斯分类器朴素贝叶斯分类器是一种基于Ｂａｙｅｓ理＿论的简单分类方法，它在很多领域都表现出优秀的性能。然而，朴素贝叶斯分类方法中的“独立性假设”在大多数现实世界中不成立，特别在文本分类中，文档中的某些特征词本身所具有的特性决定了其他属性必然会依赖于它。因此，我们希望通过对由属性结点组成的属性空间进行统计分析，找出一些对其他属性具有较强影响的属性。为了改进朴素贝叶斯分类器的性能，人们提出了许多方法和技术，如Ｋｏｎｏｎｅｎｋｏ的ｓｅｍｉ－ｎａｉｖｅ贝叶斯分类器…１将属性集分割成若干个不相交的属性组，假设在不同组中的属性之间是相互独立的，而同一属性组内的各属性相互关联。而这些结构的学习是不容易的。针对中文文档中的特征词之间可能存在依赖关系，在朴素贝叶斯方法的基础上，通过放松朴素贝叶斯中的独立性假设，我们把特征属性间的依赖关系加入网络结构中，成为属性依赖的贝叶斯网络，其结构如图４—４所示：图４－４属性依赖的贝叶斯分类器结构在图４—４所示网络结构中，某些属性结点除了类父结点，还可能有一个或多第４７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文个属性父结点。表示为下式：ｅ（ｃ』Ｉ口ｌ’口２，…＾）－口×尸（ｃ』）×Ｉ＝【Ｐ（口ｔ｜４ｌ，口２＇…，‰ｃ，）＿口ｘＰ（ｃＪ）×ＵＰ（４ｔＩＰａＭｆ（口ｔ）一）其中，Ｐａｒｅｎｔ（ａ；）为属性集合Ｋ一｛口。，ａ：，…，ｎ。，中是属性吩的父结点的集合，这样通过放松朴素贝叶斯中不现实的独立性假设，从而提高分类器的性能。属性间的依赖关系的确定所采用的策略如下：首先，对训练集进行关键词的文档频率（出现某个关键词的文档数）统计，并对这些关键词按文档频率进行降序排序。从第一个关键词开始，寻找其后的关键词的文档频率跟第一个关键词的文档频率进行比较，如果后面的某关键词的文档频率与第一个关键词的文档频率的比值大于某个值（本文中取值为０．７）则我们认为这个关键词依赖于第一个关键词。处理完第一个关键词后，接着处理第二个关键词的文档频率与其后续关键词的文档频率进行比较来确定依赖关系，以此类推。由于贝叶斯网络是有向无环网，网络中不能出现回路，因此在处理到某个关键词时，只对其后的关键词与其进行比较，而不再理会其前面的关键词。属性依赖贝叶斯模型测试实验的结果数据：向量维数查全率（％）查准率（％）１０２０４０６０８０１００１２０９５９３９１９０８９８７８８７９．０６８７．５２８８．９９８８．７３８７．３９８６．１６８９．１４表４．２属性依赖贝叶斯测试结果数据根据表４－１和表４－２中的测试结果数据，分别以向量维数为横坐标和查准率为纵坐标，以向量维数为横坐标和查全率为纵坐标分别作图４—５和图４—６，如下所示。第４８页基于词频统计的文本分类模型研究上海师范大学硕士学位论文查准奉鐾阳爨壤教图４－５查准率图４－６查全翠朴素贝叶斯分类器的训练过程其实就是统计每一个特征在各类中出现规律的过程。就实验结果来看，有比较高的查全率和查准率，且查全率和查准率在关键词数增加过程中波动不大，很好的兼顾了查准率和查全率，朴素贝叶斯具有较好的综合性能，体现了学习效率与查全率和查准率之间的一种适当的折中。在朴素贝叶斯分类方法中，有一个“特征独立性假设”：给定一个实例的类标签，实例中每个属性的出现独立于实例中其它属性的出现。这个独立性假设，使朴素贝叶斯方法特别适合处理属性个数很多的任务，而文本分类恰恰就是这种多属性的分类任务。但是朴素贝叶斯分类模型中的独立性假设同时也是它的先天不足所在：独立性假设在许多实际问题中并不成立，如果在这些问题中忽视这一点，理应会引起分类的误差。在属性依赖贝叶斯分类模型中，由于放弃了独立性假设条件，找出属性变量第４９页基于词频统计的文本分类模型研究上海师范大学硕士学位论文间的可能存在的依赖关系，其查准率与查全率较之朴素贝叶斯模型性能的提高虽不很明显，但可以看出查全率和查准率还是提高了，并且更加明确查询者的意图，也就是在文本文档分类中放宽属性的条件独立性假设，考虑了属性间的依赖关系后，更能体现出用户的直接的需求，这是今后信息检索的研究方向。４．３分类模型实验分析本章节对本课题实现和提出的分类模型进行分析比对，实验数据依然使用中国期刊全文数据库中的文档，实验方案同前面章节中的实验方案。下面是向量空间模型、决策树分类模型、贝叶斯模型、属性依赖贝叶斯模型四种分类方法的实验比较，图４—７为率准率，图４—８为查全率。向量维数图舢７查准率壹念宰季向量维数图４．８查全率第５０页基于词频统计的文本分类模型研究上海师范大学硕士学位论文从图４—７、图４—８可以看出：对于向量空间模型，当特征向量维数增加时，即用更多的关键词表示文档时，查准率会很快提高并达到较高水平，但查全率大大降低，向量空间模型是信息检索中最基本的方法，计算快捷，便于实现。对于基于归纳学习的决策树方法。它能够兼顾查全率和查准率，随着向量维数的增加，保持较高的查全率并波动很小，又能够一定程度地兼顾查准率。且决策树速度快，计算量相对较小。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一个分类；并且便于理解，可以清晰的显示哪些字段比较重要。但决策树算法在分类的时候，只是根据一个属性来分类的，这就导致不能很好的兼顾用户的偏好。基于统计方法的贝叶斯模型在图形上看不如决策树方法。但我们可以看到贝叶斯分类的出错率相对较小，查准率和查全率相对于其它两种模型表现出让人满意的稳定性，尽管在我所研究的几种模型中查准率不是最高的。贝叶斯方法是一种概率方法，分类的概率受各个属性的影响，所以能很好的处理数据缺失的情况。贝叶斯网络的因果关系有利于对领域知识的理解；在于扰较多时，便于做出精确的预测，并且对信息处理方式易于理解及表达，可以明确查询者的意图。４．４小结本章详细阐述了贝叶斯理论的基础知识和网络的构造方法，在实现朴素贝叶斯模型的基础上，通过放松属性间的独立性假设，把属性间可能存在的依赖关系加入到网络中，实现了属性依赖的贝叶斯网络分类模型，通过计算用户查询和文档闻的概率，能很好地处理信息检索中的不确定性，并存储术语间的条件概率和概念语义。通过对贝叶斯理论的学习研究，实现朴素贝叶斯与属性依赖贝叶斯分类模型。虽然朴素贝叶斯网是一种简单而有效的分类模型，但它的属性独立性假设使其无法表达属性变量间存在的依赖关系，影响了它的分类性能。通过对关键词集合进行分析，根据关键词出现的规律，提出了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝叶斯分类器，并和ＩＤ３决策树、向量空间模型、朴素贝叶斯分类器进行实验比较，分析了各个方法的优缺点。实验结果表明，属性依赖贝叶斯方法有较好的性能。虽然不同检索模型使用的方法不同，但所要达到的目标是相同的，即按照用户要求，提供用户所需的信息。实际上，大多数检索系统往往将上述各种模型混第５ｌ页基于词频统计的文本分类模型研究上海师范大学硕士学位论文合在一起，以达到最佳的检索效果。第５２页基于词频统计的文本分类模型研究上海师范大学硕士学位论文五章结束语５．１本课题主要内容介绍了文本分类中文本表示的相关知识，对文本表示中词频统计方法尤其是多关键词的词频统计进行了深入的研究，提出了一种有效的多关键词词频统计算法一利用查找树来进行词频统计。该算法充分考虑了关键词之间的冗余信息，扫描一次文档就可统计出全部关键词词频信息，实现了多关键词的高效匹配。在深入学习决策树分类模型的基础上，实现了一个基于ＩＤ３算法的决策树分类程序，并对不同规模训练集合产生的决策树进行了实验比对，结果表明决策树可以对中文信息进行有效的分类。此外，实现了一个基于向量空间模型的分类程序，以作为和其它模型进行比对的分类工具，该分类模型也能很好的实现文本分类的工作。从两个方面对贝叶斯分类模型进行了研究和程序实现：朴素贝叶斯分类与属性依赖贝叶斯分类。虽然朴素贝叶斯网是一种简单而有效的分类模型，但它的属性独立性假设使其无法表达属性变量间存在的依赖关系，影响了它的分类性能。通过对关键词集合进行分析，根据关键词出现的规律，提出了一种建立属性问依赖关系的方案，实现了一个基于属性依赖的贝叶斯分类器，并和决策树、向量空间模型、朴素贝叶斯分类器进行实验比较，分析了各个方法的优缺点。实验结果表明，属性依赖贝叶斯方法有较好的性能。５．２本课题创新点对文本表示中词频统计方法尤其是多关键词的词频统计进行了研究，提出一种有效的多关键词词频统计算法——雨ｌ用查找树来进行词频统计，该算法较好的实现了多关键词的高效匹配。（２）对朴素贝叶斯网分类模型进行了研究，放宽了属性独立性假设，使其更接近现实生活中的实际情况，提出了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝叶斯分类器。通过实验结果表明，该分类器具有较好的分类效果。５．３前景与展望虽然在研究课题的过程中，对某些问题比以往有了更为深入的了解，并努力第５３页基于词频统计的文本分类模型研究上海师范大学硕士学位论文实现了树结构词频查找树和属性依赖的贝叶斯算法，但由于时间关系，本课题仍存在许多有待进一步研究的问题，主要归结为以下几个方面：１１树结构词频统计算法虽然很好的解决了多关键词的查找匹配问题，但从本质上讲它还是利用了已有的关键词库，如果没有词库的情况下，它就难以发挥效果，因此，如何对现有文档分词，确定合适的界限形成合适的词库还有待于进一步的深入研究。∞分类的对象停留在已有文档的基础上，但现实生活中Ｉｎｔｅｍｅｔ上的主要信息载体是网页，所以网页分类是目前的主要发展趋势。网页是半结构化信息，包括格式信息和其它媒介信息，如何利用他们提高纯文本分类的准确率或效率是下一步分类研究中的主要任务。应当认真仔细地研究分析网页中这些信息的特点和本质含义，寻找利用他们的有效方法。３）对于某些分类模型算法，其最终处理的数据已经被转化为向量的形式，如何将分类较优的结果向量和数据库中相应的文档建立对应关系，还有待进一步研究。因此，整体而言，对于文本分类，还有许多尚未涉足的领域，如其它分类算法、过学习问题等，有待下～步继续研究。由于本人水平有限，对一些问题的理解还不够全面和深入，错误与不妥之处在所难免，敬请各位老师批评指正。第５４页参考文献参考文献［１３范明盂小峰，数据挖掘概念与技术，机械工业出版社，２００５年６月第１版【２】ＣｒａｖｅｎＭ，ＤｉｐａｓｑｕｏＡ，ＦｒｅｉｔａｇＡｅｔａ１．ＬｅａｒｎｉｎｇｔｏＥｘｔｒａｃｔＳｙｍｂｏｌｉｃＫｎｏｗｌｅｄｇｅｏｆｔｈｅＦｉｆｔｅｅｎｔｈｆｒｏｍｔｈｅＷｏｒｌｄＷｉｄｅＷｅｂ．Ｉｎ：ＰｒｏｃＮａｔｉｏｎａｌＣｏｎｆｏｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ（ＡＡＡ１２９８）．Ｗｉｓｃｏｎｓｉｎ，１９９８ｆ３】ＪｏａｃｈｉｍｓＴｅｘｔ．ＩＴ．ＡＰｒｏｂａｂｉｌｉｓｔｉｃＡｎａｌｙｓｉｓＣｏｎｆｏｎＭａｃｈｉｎｅｏｆｔｈｅＲｏｃｃｈｉｏＡｌｇｏｒｉｔｈｍｗｉｔｈＴＦＩＤＦｆｏｒｎ：Ｉｎｔ’１ｌｅａｒｎｉｎｇ（ＩＣｌ儿）．Ｔｅｎｎｅｓｓｅｅ．１９９７［４］ＣｏｏｐｅｒＧｒｅｇＦ，ＨｅｒｓｋｏｖｉｔｓＥ．ＡＢａｙｅｓｉａｎｍｅｔｈｏｄｆｏｒｔｈｅｉｎｄｕｃｔｉｏｎｏｆｐｒｏｂａｂｉｌｉｓｔｉｃｎｅｔｗｏｒｋｓｆｒｏｍｄａｔ＆ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ。１９９２。（９）：３０９－３４７．ＩＳ］ＰａｕｌＢａｇｕｍ，Ｒ．Ｍａｒｔｉｎ１９９３，１５（３）：２４６—２５５Ｃｈａｖｅｚ．ＡｐｐｒｏｘｉｍａｔｉｎｇＰｒｏｂａｂｉｌｉｓｔｉｃＩｎｆｅｒｅｎｃｅｉｎＢａｙｅｓｉａｎｏｎＢｅｌｉｅｆＮｅｔｗｏｒｋｓ．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，［６］Ｓ．Ｋ．Ｍ．Ｗｏｎｇ，Ｔ．Ｌｉｎ，ＡｎＩｎｔｅｒｎａｔｉｏｎａｌａｌｔｅｒｎａｔｉｖｅｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆａＢａｙｅｓｉａｎｎｅｔｗｏｒｋ。ＪｏｕｒｎａｌｏｆＡｐｐｒｏｘｉｍａｔｅＲｅａｓｏｎｉｎｇ，２００３。（３３）：２２１—２３４ｔｏ［７】ＳｕｃｈｅｔａＮａｄｋａｒｎｉ。ＰｒａｋａｓｈＰ．Ｓｈｅｎｏｙ。ＡＢａｙｅｓｉａｎｎｅｔｗｏｒｋａｐｐｒｏａｃｈｍａｋｉｎｇｉｎｆｅｒｅｎｃｅｓｉｎｃａｕｓａｌｍａｐｓ，Ｅｕｒｏｐｅａｎ４７９—４９８ＪｏｕｒｎａｌｏｆｏｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，２００１，（１２８）：［８］ＤａｖｉｄＨｅｃｋｅｒｍａｎ．ＢａｙｅｓｉａｎＮｅｔｗｏｒｋｓｆｏｒＤａｔａＭｉｎｉｎｇ．ＤａｔａＭｉｎｉｎｇａｎｄＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ，１９９７，（１）：７９—１１９［９］ＭａｒｃｏＡｎｔｏｎｉｏＰｉｎｈｅｉｒｏｄｅＣｒｉｓｔｏ，ＰａｖｅｌＰｅｒｅｉｒａＣａｌａｄｏ。ＭａｒｉａｄｅＬｏｕｒｄｅｓｄａＳｉＩｖｅｉｒａ，ＩＩｍｅｒｉｏＳｉｉｖａ，ＲｉｃｈａｒｄＭｕｎｔｚ，ＢｅｒｔｈｉｅｒＲｉｂｅｉｒ旷Ｎｅｔｏ。ＢａｙｅｓｉａｎｂｅｌｉｅｆｎｅｔｗｏｒｋｓｆｏｒＩＲ，ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＡｐｐｒｏｘｉｍａｔｅＲｅａｓｏｎｉｎｇ，２００３，（３４）：１６３—１７９【１０］ＪｉｅＣｈｅｎｇ，ＲｕｓｓｅｌｌＧｒｅｉｎｅｒ，ＪｏｎａｔｈａｎＫｅｌｌｙ，ＤａｖｉｄＢｅｌｌ，ＷｅｉｒｕｆｒｏｍＬｉｕ，ＬｅａｒｎｉｎｇＢａｙｅｓｉａｎｎｅｔｗｏｒｋｓｄａｔａ：Ａｎｉｎｆｏｒｍａｔｉｏｎ－ｔｈｅｏｒｙｂａｓｅｄａｐｐｒｏａｃｈ，ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，２００２。（１３７）：４３—９０［１１］ＲｏｂｅｒｔＡｖａｎＥｎｇｅｌｅｎ，ＡｐｐｒｏｘｉｍａｔｉｎｇＢａｙｅｓｉａｎＢｅｌｉｅｆＮｅｔｗｏｒｋｓｂｙＡｒｃＲｅｍｏｖａｌ，ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，１９９７，１９（８）：９１６－９２０［１２］陆小艺程泽凯林士敏，用Ｍａｔｌａｂ语言建构贝叶斯分类器，微机发展，２００４，１４（９）：３３－３６【１３】冀俊忠刘椿年沙志强，贝叶斯网模型的学习、推理和应用，计算机工程与应用，２００３，（５）：２４－２７【１４】张宏伟田风占陆玉昌，对一种贝叶斯网络学习算法的改进及试验分析，计算机科学，２００２。２９（５）：９７—１００［１５］王双成林士敏陆玉昌，用贝叶斯网络进行因果分析，计算机科学，２０００，２７（１０）：８０－８２第５５页参考文献【１６】田凤占张宏伟陆玉昌石纯一，多模块贝叶斯网络中推理的简化，计算机研究与发展，２００３，加蛹）：１２３０－１２３７【１７］冀俊忠刘椿年沙志强，贝叶斯网模型的学习、推理和应用，计算机工程与应用，２００３，；（５）：２４－２７【１８】卢志茂刘挺朗君李生。神经网络和贝叶斯网络在汉语词义消歧上的对比研究，高技术通讯，２００４，（８）：１５—１９【１９】鲁松李晓黎白硕王实，文档中词语权重计算方法的改进，中文信息学报，２０００，１郇６）：８．１３［２０】庞剑锋ｈ东波白硕，基于向量空间模型的文本自动分类系统的研究与实现，计算机应用研究，２００１，（９）：２３－２６【２１】黄萱菁夏迎炬吴立德，基于向量空间模型的文本过滤系统，软件学报，２００３，１４（３）：４３５—４４２［２２】张鑫谭建龙程学旗，一种改进的Ｗｕ－Ｍａｎｂｅｒ多关键词匹配算法，计算机应用，２００３，２３（７）：２９－３１【２３】费洪晓康松林，基于词频统计的中文分词的研究，计算机工程与应用，２００５，（７）６７－６８【２４】严蔚敏吴传民，数据结构，北京清华大学出版社，１９８８，７２－９３【２５】ＳａｒａＢａａｓｅ，ＡｌｌｅｎＶａｎ教育出版社，２００１：４８３－５１３Ｇｅｌｄｅｒ计算机算法一设计与分析导论（第三版影印版）高等Ｊ．Ｃｏｒａｓｉｃｋ．ＥｆｆｉｃｉｅｎｔＳｔｒｉｎｇＭａｔｃｈｉｎｇ：ＡｎＡｉｄｏｆｔｏ【２６］Ｔｏ删．Ｍｉｔｃｈｅｌｌ著，曾华军张银奎等译．机器学习，机械工业出版社，２００３年［２７］ＡｌｆｒｅｄＶ．Ａｈｏ，ＭａｒｇａｒｅｔＢｉｂｌｉｏｇｒａｐｈｉｃＳｅａｒｃｈ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓｔｈｅ＾ＣＭ，１９７５，１８（６）：３３３—３４０［２８】张思民梁维娜，Ｊａｙａ程序设计实践教程，清华大学出版社，２００６年８月第ｌ版【２９】范明范宏建，数据挖掘导论，人民邮电出版社，２０噼５月第１版，８９［３０】陈安陈宁，数据挖掘技术及应用，科学出版社，２００６年３月第１版，１１２ｐｌ】姚天顺朱靖波张利杨莹，自然语言理解一一种能让机器懂得人类语言的研究（第２版），清华大学出版社，２００２：３７５－３７６［３２］Ｊ．Ｒ．ＱＩＩｉｎｌａｎ．ＩｎｄｕｃｔｉｏｎｏｆＤｅｃｉｓｉｏｎＴｒｅｅｓ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，１９８６，（１）：８１一１０６［３３］姜丹信息理论与编码，中国科学技术大学出版社，２００４年８月第２版［３４］Ｃ．Ｅ．Ｓｈａｎｎｏｎ．ＭａｔｈｅｍａｔｉｃａｌＴｈｅｏｒｙｏｆＣｏｍｍｕｎｉｃａｔｉｏｎＥＭ］．ＢｅｌｌＳｙｓｔｅｍＴｅｃｈｎｉｃａｌＪｏｕｒｎａｌ，Ｖ０１２７，３７９—４２３，６２３—６５６，１９４８．［３５］Ｇ．Ｓａｌｔｏｎ，九Ｗｏｎｇ，Ｃ．Ｙａｎｇ．ＡＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅｖｅｃｔｏｒｓｐａｃｅｍｏｄｅｌｆｏｒａｕｔｏｍａｔｉｃｉｎｄｅｘｉｎｇ．ＡＣＭ，１８（１１）：６１３－６２０，１９７５．Ｅ３６］陈治纲何丕廉，基于向量空间模型的文本分类方法的研究与实现，计算机应用，２００４．６。２７７－２７９第５６页参考文献［３７］史忠植，知识发现，清华大学出版社，２００２年１月第ｌ版，１６９—２０２．［３８］张云涛龚玲，数据挖掘原理与技术，电子工业出版社，２００４年４月第１版［３９］ＭｉａＫ．Ｓｔｅｒｎ，ＪｏｓｅｐｈＭｏｄｅｌｉｎｇＥ．ＢｅｖｅｒｌｙＰａｒｋＷｏｏｆ．ＮａｔｉｖｅＢａｙｅｓＣｌａｓｓｉｆｉｅｒｓｆｏｒＵｓｅｒ［４０］ＰｅｄｒｏＤｏｍｉｎｇｏｓ，Ｍｉｃｈａｅｌｚｅｒｏ－ｏｎｅＰａｚｚｚａｎｉ．ＯｎｔｈｅＯｐｔｉｍａｌｉｔｙｏｆｔｈｅＳｉｍｐｌｅＢａｙｅｓｉａｎＣｌａｓｓｉｆｉｅｒｕｎｄｅｒＬｏｓｓ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．２９，１０３—１３０，１９９７．Ｌｅａｒｎｉｎｇ．ＩｎＴｅｃｈｎｉｃａｌＲｅｐｏｒｔＣＳ９７。Ｄｅｐｔ．ｏｆＳａｎＤｉｅｇｏ，Ｓｅｐｔ．１９９７．ｔｈｅ［４１］Ｃ．Ｅ１ｋａＩＬＢｏｏｓｔｉｎｇａｎｄＮａｉｖｅＢａｙｅｓｉａｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖ．Ｃａｌｉｆａｔ［４２］ＫｏｎｏｎｅｎｋｏＩ．ＳｅｍｉｎａｉｖｅＢａｙｅｓｉａｎｃｌａｓｓｉｆｉｅｒ．Ｉｎ：ＫｏｄｒａｔｏｆｆＹ，ｅｄ．Ｐｒｏｃ．ｏｆｏｎ６ｔｈＥｕｒｏｐｅａｎＷｏｒｋｉｎｇＳｅｓｓｉｏｎＬｅａｒｎｉｎｇ．ＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ－Ｖａｒｌａｇ．１９９１．２０６—２１９．第５７页基于词频统计的文本分类模型研究上海师范大学硕士学位论文攻读硕士学位期间发表的论文１．炎士涛。基于决策树的分类算法研究，计算机科学与实践，己录用。２．炎士涛。基于ＳＴＬ的图遍历问题解决，计算机科学与实践，已发表。３．炎士涛，徐铮。基于父个体更新的自适应遗传算法，微计算机信息，已发表。ｚ炎士涛，费涨。实时快速３Ｄ绘制空气中水滴反射效果，计算机工程与应用，已录用。第５８页基于词频统计的文本分类模型研究上海师范大学硕士学位论文致谢研究生课程学习阶段伴随着论文的完成就要结束了，在这里我要向我的导师及所有关心、帮助我的老师、同学及亲友致以衷心的感谢！首先，要对我的导师迟洪钦教授表示深深的谢意和崇高的敬意，他严谨的治学态度，刻苦忘我的工作精神，严以律己、宽以待人的处事原则使我受益匪浅，终生受用。在近三年的读研生活中，无论在生活上还是学业上，自始至终都得到了迟老师的深切关怀和热情指导。感谢迟老师在学习上给予我的无私的指导和帮助，使我丰富了知识，提高了学习和工作的能力。另外，还要感谢上海师范大学网络中心的潘以风老师，在我做课题的过程中，无论从实验环境和实验数据方面，都给我提供了相当的便利，在他的悉心指导下，我的实验部分才能顺利完成，他勤奋严谨的治学态度，时时刻刻的影响着我，为我以后的个人发展树立了明确的榜样。在三年的研究生学习生活中，陈仪香、陈操宇、郭善良、陆黎明、王海源等老师都给予了我悉心细致的指导，使我的知识面和科研能力得到很大的提高，在此对这几位老师致以衷心的感谢。同时，我还要感谢费涨，罗海林，宋成明、翟琳琳及其他同学，在我攻读学位的这些年里，大家互相学习、互相帮助。我要感谢他们的关心和帮助陪伴我度过研究生的生活，向他们表示诚挚的谢意！最后，感谢我的家人，他们无论从物质上还是从精神上都给了我极大的关怀与帮助。第５９页