（计算机软件与理论专业论文）基于词频统计的文本分类模型研究.pdf

基于词频统计的文本分类模型研究上海师范大学硕士学位论文 摘要 在数据挖掘中，分类是一种重要的技术，它能对大量有关数据进 行分析、学习，并建立相应问题领域中的分类模型。该技术在科学、 工程、金融等领域均有广泛的应用。本文介绍了文本分类中文档的表 示方法，对高频词表示文档的词频统计算法进行了深入的研究，分析 了目前算法存在的问题，提出了一种树结构词频统计方法，实现了多 关键词的高效匹配，并在此基础上实现了一个词频统计器，利用它可 以快捷的将文本表示为高频词的集合，方便实现文本分类。在对各种 经典的分类算法研究的基础上，着重对贝叶斯网络分类算法进行了研 究，详细阐述了朴素贝叶斯分类算法的相关理论，并在其基础上提出 了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝叶 斯分类器，较好的解决了朴素贝叶斯分类中属性独立性假设所带来的 弊端。利用树结构词频统计算法得到的实验数据，对决策树、向量空 间模型、朴素贝叶斯分类和属性依赖贝叶斯分类进行了实验比对，分 析了各个方法的优缺点。实验结果表明，属性依赖贝叶斯方法有较好 的分类性能。 关键词：词频统计，文本分类，决策树，i d 3 算法，属性依赖贝叶斯 第1 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 a b s t r a c t c l a s s i f i c a t i o n ，w h i c hi sa b l et oa n a l y z ea n dl e a r nm a s so fr e l a t i v ed a t a , e s t a b l i s h c o r r e s p o n d i n g c l a s s i f i c a t i o nm o d e li ns o m ef i e l d s i sa n i m p o r t a n tt e c h n i q u ef o rd a t am i n i n g t e c h n i q u eo fc l a s s i f i c a t i o ni sw i d e l y a p p l i e di ns o m ed o m a i n so fs c i e n t i f i cr e s e a r c h ，e n g i n e e r i n g ，f i n a n c ea n d s oo n t h em e t h o do fh o wt oe x p r e s sf i l e si nt e x tc l a s s i f i c a t i o ni s i n t r o d u c e d ，a n di n d e p t hr e s e a r c hi sm a d ea b o u ts t a t i s t i c a lm e t h o do f w o r df r e q u e n c ye x p r e s s e db yh i g h - f r e q u e n c yw o r d si nt h i st h e s i s t h e t h e s i sa n a l y z e st h ee x i s t i n gp r o b l e m si nc u r r e n ta l g o r i t h m s ；p u tf o r w a r da t r e es t r u c t u r es t a t i s t i c a lm e t h o do fw o r df r e q u e n c y ，w h i c he n a b l e sk e y w o r d st om a t c ho n ea n o t h e rh i g h l y - e f f i c i e n t l y b a s e do i lt h i ss t a t i s t i c a l m e t h o d ，w ed e s i g na s t a t i s t i c a la f i t h m o m e t e rf o rw o r d f r e q u e n c yc o u n t i n g ， b yw h i c hw e c a nr a p i d l ye x p r e s st e x t sa st h es e to fh i g h f r e q u e n c yw o r d s ， s ot h ec l a s s i f i c a t i o no ft e x t si sc o n v e n i e n t l yr e a c h e d b a s e do na l ls o r t so f r e s e a r c h e so fc l a s s i c a la r i t h m o m e t e r s ，t h i st h e s i sm a k e se m p h a t i c a l l y r e s e a r c ho nb a y e s - b a s e dc l a s s i f i c a t i o n a l g o r i t h mf o rw e bt e x t ；a n d s p e c i f i c a l l y i l l u s t r a t e sr e l e v a n tt h e o r i e so ft h en a i v e b a y e s b a s e d c l a s s i f i c a t i o na l g o r i t h m b a s e do nt h eb a y e st h e o r i e so fc l a s s i f i c a t i o n a l g o r i t h m ，w eb r i n gf o r w a r d ap r o j e c tt oe s t a b l i s hi n t e r - a t t r i b u t e s d e p e n d e n c yr e l a t i o n s h i p ，w h i c ha c h i e v e sab a y e sc a t e g o r i z e rb a s e do i l a t t r i b u t e sd e p e n d e n c ya n dg e t sr i do ft h ed i s a d v a n t a g eb r o u g h tb yt h e a s s u m p t i o no fa t t r i b u t e si n d e p e n d e n c yi nn a i v eb a y e sc l a s s i f i c a t i o n 第1 i 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 u t i l i z i n gt h ee x p e r i m e n t a ld a t a a t t a i n e df r o mt r e es t r u c t u r es t a t i s t i c a l m e t h o do fw o r df r e q u e n c y ，w ee x p e r i m e n t a l l yc o m p a r ed e c i s i o nt r e e s ， v e c t o r s p a c e m o d e l ， n a i v e b a y e s c l a s s i f i c a t i o nw i t h b a y e s a t t r i b u t e s d e p e n d i n gc l a s s i f i c a t i o n ，a n da n a l y z e t h e a d v a n t a g e s a n d d i s a d v a n t a g e so ft h ea b o v em e n t i o n e dm e t h o d s t h ee x p e r i m e n t a lr e s u l t s s h o wt h a t b a y e sa t t r i b u t e s d e p e n d i n g c l a s s i f i c a t i o nh a sab e t t e r p e r f o r m a n c eo fc l a s s i f i c a t i o n k e y w o r d s ：w o r d - f r e q u e n c yc o u n t i n g ，t e x tc l a s s i f i c a t i o n ，d e c i s i o n t r e e s ，i d 3a l g o r i t h m ，a t t r i b u t e - a s s o c i a t e db a y e s 第n i 页 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构己经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者虢磋仰期：嘞r 】j 诊2 j l 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：毖呜铲师签名：拦降陀日期：砌汁叫万日 基于词频统计的文本分类模型研究 上海师范大学硕士学位论文 1 1 研究背景 第一章绪论 随着互联网的不断普及和发展，信息技术已经渗透到人们社会生活的方方 面面，并且正以惊人的速度和能力改变着人们的生活和工作方式，人们真正处 于一个“信息爆炸”的时代。在这种情况下，如何自动处理这些海量信息成为 目前重要的研究课题。自动处理信息的主要环节包括信息抽取、信息分类和信 息检索。信息分类处于中间环节，主要将抽取到的信息自动有效地分成一定的 类别，以便于信息的检索。 在数据挖掘领域中，分类作为一种重要的技术，能对大量有关数据进行 分析、学习，并建立相应问题领域中的分类模型。该技术在科学、工程、金融 等领域均有广泛的应用。随着全球计算机与通讯技术的飞速发展、互联网的普 及与应用，信息爆炸的现实使人们越来越注重对分类的研究，文本分类及其相 关技术的研究也日益成为一项研究热点。 从目前的情况来看，虽然互联网上的信息载体呈多样化趋势，但仍以文本 为主，文本仍是互联网上信息的主要来源。文本分类己成为一项具有较大实用 价值的关键技术，是组织和管理数据的有力手段，可被用于抽取符号知识“1 、 新闻分发、排序电子邮件、学习用户兴趣以及信息过滤等等。目前研究者们 已提出了许多统计方法和机器学习方法，在试验中也有很好的表现。但是，在 这个领域还是有很大的空间值得我们继续去研究和探索。 1 2 国内外研究现状 2 0 世纪8 0 年代，自动文本分类技术的研究在国外兴起。早期的技术主要以 基于知识工程的方法为主，卡内基集团为路透社开发的基于规则的c o n s t r u e 系 统是较早的实用化自动文本分类系统。进入9 0 年代以后，基于统计的自动文本 分类方法日益受到重视；系统评价也有了重大进展，建立了r e u t e r s ( v 2 1 5 7 8 ) 、 o h s u m e d 、n e w s g r o u p 、t r e c 等标准的英文语料库。目前主要的分类算法有朴素 贝叶斯( n a i v eb a y e s ) 、k 近邻( k - n e a r e s tn e i g h b o u r s ) 、支持向量机( s u p p o r t v e c t o rm a c h i n e ) 等基于统计的方法。 国内从9 0 年代中期开始进行中文文本自动分类的研究。复旦大学、中科院 计算所、清华大学、北京大学等单位较早开展了这方面的研究，取得了一定成果。 第1 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 国家8 6 3 计划中文信息处理与智能人机接口技术组也于2 0 0 3 年开始进行文本分 类评测，并且给出了评价准则，目前该标准已成为中文文本分类测试的标准。 在进行文本分类前，通常要对文本进行特征表示，而表示的结果应该具有 简单、准确等特点。目前大部分系统所采用的表示方法是6 0 年代末s a l t o n 等 人提出来的向量空间模型( v s m ：v e c t o rs p a c em o d e l ) 。但对中文而言，这个模 型有先天不足由于中文分词技术的局限性，v s m 表示文本的过程中割裂了 特征项( 字、词、短语、概念等) 之问的相关性，做了独立性假设( 如l s i 等模型 研究) ；而且高维向量很容易淹没重要的特征。所以该模型的文本表示质量受到 特征维数、特征质量等诸多因素的影响。 在目前分类模型的研究热点中，贝叶斯网络是被广为研究的对象之一。在 国外，许多学者和研究机构都对应用贝叶斯网络技术检索信息进行了深入的研 究。贝叶斯网络被用在信息检索中始于h o w a r dr t u r t l e 的博士论文。c o o p e r g r e gf 叫，p a u ld a g u m 嘲，s k m w o n g 嘲，s u c h e t an a d k a r n i ”等人在文献中详 细介绍了如何构造贝叶斯网络，并利用其迸行概率推理。d a v i dh e c k e r m a n 嘲， m a nl e u n gw o n g 等人详细研究了运用贝叶斯网络进行数据挖掘的方法。m a r c o a n t o n i op i n h e i r od ec r i s t 0 9 3 等人对原有的贝叶斯网络模型进行改进，实现 了一种基于贝叶斯网络模型的信息检索系统，利用其可处理不确定性信息的特 性，设计了两层、多层网络来检索信息，改进网络结构和参数学习方法，大大 提高了信息检索的性能。f r a n zp e r n k o p f 等人设计了一种贝叶斯网络分类器来 对文档进行分类，并介绍了一种分类器的结构学习算法。j i ec h e n g “”，r o b e r t av a ne n g e l e n “”，w a il a m 等人对贝叶斯网络的构建及其参数的学习进行了探 讨和研究，有分布学习算法、删除边的方法等。贝叶斯网络的学习一直是人们 研究的热点，还有一些问题亟待解决。h o n g l a nj i n ，j ih e 等人对中文文本分 类方法进行了比较研究，提出了一种中文字典的算法来进行信息检索。 国内，清华大学计算机科学与技术系的石纯一、陆玉昌、林士敏等通过剖 析贝叶斯网络的结构和建造步骤“”，研究贝叶斯网络的学习方法“”，对具有不 完整数据的问题分析“，和概率推理技术进行了研究“”，并引入模块化和面向 对象思想，提出多模块贝叶斯网络推理“”；北京工业大学计算机学院的刘椿年 提出并实现了一种以贝叶斯网为学生模型的智能教学系统“”，该方法以贝叶斯 网为学生模型，根据学生模型上提供的启发信息，对解图空间进行搜索，以获 取最佳教学决策；哈尔滨工业大学信息检索研究室的刘挺、秦兵、卢志茂等“” 在信息检索方面对句法分析、词义消歧等作了研究，成功的引入贝叶斯网络对 中文词义消歧，并取得了良好的效果；中国科学院计算技术研究所白硕、程学 第2 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 旗、王斌等对文档中词语权重的计算方法进行了改进“”，并提出了基于向量空 间模型的文本分类系统的结构，改进了多关键词匹配算法，在处理大规模数 据时有较好的效率；复旦大学吴立德、黄萱菁等设计了基于向量空间模型的文 本过滤系统乜1 】，并在文本检索会议的评测中取得了很好的成绩；上海交通大学 的王永成等偏重对关键词的匹配技术的研究，尤其是对多中文关键词匹配技术， 在前人( a c 算法和q s 算法) 的基础上，结合两者的优点，引入连续跳跃的思想， 提出了一个快速的多关键词匹配算法，大大缩短了匹配时间。其他人在这方面 也有研究嘲，基本相似，这里不再一一赘述。 总之，在文本分类领域，由于贝叶斯网的预测能力以及它具有显示领域变 量间最重要的直接关联关系和阐明领域结构的优势，贝叶斯网理论已成为2 1 世 纪计算机软件的理论基础。 1 3 研究目的和意义 本文的研究主要包括了以下几个方面： 1 ) 针对中文文档特有的特点，在研究以往文本表示方法的基础上，通过 分析中文分词和词频算法目前存在的不足，设计了一种树结构词频统计方法来 进行多关键词的词频统计。通过词频查找树，方便的完成了对中文进行分词和 词频统计的工作。 2 ) 实现了目前比较流行的两种中文文本分类方法：决策树分类和向量空 问模型分类。围绕查准率和查全率两个主要技术指标，使用大量的训练数据和 测试数据对它们进行了实验比对，分析了各自的优缺点。 3 ) 详细地论述贝叶斯分类模型的结构、关键技术和理论；在分析朴素贝叶 斯分类器存在的不足的基础上，适当的放宽属性间独立的约束，提出并实现了 一种建立属性间依赖关系的属性依赖分类器。对几种分类模型进行了较详尽地 实验分析，实验表明，属性依赖贝叶斯具有较好的分类效果。 本课题的项目依托是上海师范大学网络中心所承接的上海市教委教育高地 系统，是该系统的前期调研阶段。教育高地系统是为上海市中小学教师提供交 流教学经验的一个平台，其中包含了大量的中文教案资料，为方便老师定制感 兴趣的教育信息，排除其他非相关资料，有必要进行中文信息过滤，而过滤中 最主要解决的问题就是对各种文档的分类问题，本课题从高维词库表示文本的 角度出发，对相关算法和理论进行研究探讨，通过实验来比较分析各种分类模 第3 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 型的特点，旨在提出一种针对特定领域、性能较好的智能分类模型，并应用于该 系统当中，本课题较好的完成了这一目标。 1 4 论文的组织结构 本论文内容的组织结构如下： 第1 章绪论，介绍本论文的背景、文本分类的相关知识、国内外研究现状和 课题研究的目的。 第2 章分析了文本分类的基本问题：文本表示。为了得到最终实现本文对多 种分类模型比较的实验数据，对文本表示中词频统计方法尤其是多关键词的词频 统计进行了研究，在学习以往词频统计方法的基础上，提出了一种有效的多关键 词词频统计算法一利用查找树来进行词频统计。在该算法中，充分考虑了关键 词之间的冗余信息，扫描一次文档就可统计出全部关键词词频信息，实现了多关 键词的高效匹配，在此基础上可以方便快捷的将文本表示为高频词的集合，便于 实现文本分类。 第3 章经典分类算法实现，学习分析决策树算法的原理和建树的步骤、拓展 测试属性过程中所要考虑的情况，实现了一个基于i d 3 算法的决策树分类器，利 用该分类器对中文信息进行了分类处理实验，并对实验结果进行了分析比较。此 外，对另一种比较流行的分类算法一一向量空间模型( v s m ) 进行了深入的研究，并 通过实验检验该分类器的分类效果。 第4 章介绍了贝叶斯网络的基本原理、分类网络的建造方法和贝叶斯分类 器。在朴素贝叶斯模型的基础上，对关键词集合进行分析，根据关键词频率出现 的规律，提出了一种建立属性间依赖关系的方案，实现了一个基于属性依赖的贝 叶斯分类器。并将其与决策树、朴素贝叶斯、向量空间模型进行了对比，分析了 各个方法的优缺点。实验结果表明属性依赖贝叶斯方法有较好的性能。 第5 章结束语，对本文所做工作进行总结，并提出下一步的研究工作，同时 对文本分类的前景进行展望。 第4 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 第二章文本表示方法研究 2 1 引言 在信息处理研究的过程中，需要适当的预处理信息样本，这样才可能进一步 用模型来准确表达信息样本，其中最重要的处理就是对属性进行选择，而属性选 择的算法大致可以分为两大类：一类是基于统计的算法，如“n - g r a m ”算法嘲， 另一类是基于字典的算法，这两类算法各有优缺点，基于统计的算法无需建立字 典，因而与领域无关，但是精度低；基于字典的算法比较准确，但是需要建立字 典，因为建立表达完全语义场的字典是不可能的，所以基于字典的属性选择算法 必然是与领域相关的。 基于统计的方法最主要是利用中文分词技术，即利用计算机自动识别文本中 的词边界，进而统计词频并按出现的频率排序，使用出现频率较高的词来表示文 本，它是中文信息处理最重要的预处理。中南大学信息科学与工程学院的费洪晓 教授介绍了一个基于词频统计的中文分词系统的设计和实现啪。通过这个系统， 可以将输入的连续汉字串进行分词处理，输出分割后的汉语词串，一般是二字词 串，并得到一个词典。词典中不重复地存储了每次处理中得到的词语，以及这些 词语出现的频率。但在实际的应用当中，由于汉语本身的特点，分词效果并不理 想，并且精度不高，所以多采用基于字典的方法。 对于基于字典的算法，则需要建立和具体领域相关的字典，然后用该字典对 文本进行多次扫描匹配，由于和某领域相关的单词一般比较多，所以对一篇文章 的处理往往要进行多次，极大的浪费了时间。这种匹配方法主要有b f ( b r u t e f o r c e ) 算法、k m p ( k n u t h - m o r r i s - p r a t t ) 算法、酬( b o y e r - m o o r e ) 算法“1 等，都 已基本上完善。 本课题在本章节重点讨论文本表示的主要实现方法，特别对使用多关键词表 示文本的方法进行了深入的研究，在学习研究以往算法的基础上，提出了一种新 型的多关键词匹配方法一树结构词频统计算法。在实现该算法的基础上对其性 能进行分析，结果显示该方法可实现一次扫描统计出所有词的信息，消耗的时间 大大减少。利用该匹配算法实现的词频统计器，可以实现文本集合中高频词的统 计，并且对于训练文本和待分类文本，也可以方便的利用该统计器进行特征提取， 从而实现用少量的高频特征词表示整个文本的目的。 第5 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 2 2 文本表示方法介绍 在进行文本分类的前期，需要对待处理文本进行预处理，抽取文本的特征， 使文本信息能够表示成计算机可以处理的结构化信息。本文讨论的文本表示方 法，是基于分类算法模型的，针对不同的分类模型采用不同的文本表示方法。 2 2 1 文本特征表示 文本表示成计算机可以处理的结构化信息的过程在文本分类嘲的整个过程 中称为文本预处理，现在最为广泛被采用的使用方法是向量空间模型表示。向量 空间模型( v e c t o rs p a c em o d e l ) 是由g s a l t o n 于1 9 8 8 年提出的。该模型在s m i r t 系统中得到了成功的应用，并且广泛应用于文本信息处理领域，是一个很成功的 模型。 所谓向量空间模型( v s m ) 就是用一个向量来表示一个文本的信息，使得文本 成为特征空间中的一个点。在向量空间模型中文本集合形成一个矩阵，也就是特 征空间中点的集合。 词频矩阵就是应用向量空间模型表示文本的一种形式，其表示方法如表2 - 1 所示： 表2 1 词频矩阵表示方法 在词频矩阵中，w o r d 。是向量空间模型中的特征项，a i ，是项的权重，通常是 指第i 个词在第j 篇文本中出现的频率。 在大规模文本分类系统中，文本的表示是一个基本的，而且非常重要的问题。 对训练文档、待分类文档要做的第一件事就是将它们从一个无结构的原始文本表 示为结构化的可处理的信息，然后才有可能对这些信息进行分析与处理。在英文 的分类、检索系统中，将文档及查询进行表示是件非常简单的事，因为通常选用 第6 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 词为基本单位，而英文中词与词之间存在分隔符( 如空格) 。对中文分类、检索系 统来说将文档及查询语句表示为结构化信息就复杂些。中文的文本表示通常选用 字、词、短语、句子以及句群等更高层次的单位。在实际应用中，到底选择哪种 单位来表示文本必须由处理速度、精度要求、存储空间等方面的具体要求来决定。 选择的单位越具有代表性，语言层次越高，它所包含的信息也就越丰富，但同时 进行分析时所付出的代价也就越大。 在本课题中，我们采用关键词作为表达文本的基本单位，通过统计文本中关 键词频并对其进行排序，使用出现频率最高的n 个单词来表示整个文档，n 就称为 该文本向量的维数，在后面的实验中通过对不同维数表示的实验数据进行对比实 验，来说明它对文本分类的影响。 1 ) 在决策树i d 3 算法中，由于向量属性只要表达出该关键词是否出现在 文档中，因此上述向量表示方法中的a 。表示第i 个词在第j 篇文章 中是否出现，用布尔值表示，但为了方便计算机识别，用“1 ”代表 在文章中出现，“0 ”代表未出现。这种模型被称为“布尔逻辑模型”。 2 ) v s m 分类算法模型主要采用的就是完整的向量空间模型表示。此时 a 。j = t f 。j * i d f 。，其中t f i j 采表示关键词k 。在文档d j 中出现的频度。i d f 。表示 倒文档频度：i d f 。= l o g ( n n 。) ，n 为数据全集中文档的总数，n i 为包含关 键词i 的文档总数。该方法能很好的表达出关键词对某类文章的重要 性，因此被广泛的采用。 2 2 2 词频统计基本原理 为了能精确的对实验文档进行表示，基于统计的方法需要对整篇文章进行分 词，进而对每个单词的出现频率进行统计。词是最小的、能独立活动的、有意义 的语言成分。计算机的所有语言知识都来自机器词典( 给出词的各项信息) 、句法 规则( 以词类的各种组合方式来描述词的聚合现象) 以及有关词和句子的语义、语 境知识库。 英文和汉字构词的特点不同，它们的分词方法也有根本的区别。英文分词一 般包含以下几步：利用各种分隔符切分出词；删除数字与分割符；所有 词转换为小写；删除停用词表中的词( 如助动词、代词、介词等) ；每个词 都用其同型词根代替。由于汉语本身的特点，中文分词是对一串连续的汉字字符 进行分词，在算法的实现上难度比较大。这主要是由于汉语分词存在切分歧义、 未登录词识别( 如：人名、地名、企业字号、商标号等和某些术语、缩略词、新词) 、 分词与理解的先后等问题的存在。 第7 页 基于词频统计的文本分类模型研究 上海师范大学硕士学位论文 在中文文档中，从形式上看，词是组合稳定的字而得到的，因此，在上下文 环境中，同时出现相邻的字次数越多，就表示该相邻字组合越有可能构成一个词。 因此相邻字的组合共现的频率或概率能够较好的反应组成词的可信度。这就是词 频统计的基本原理，这种技术发展至今已经有许多不同的统计原理。 i 互信息原理嘲 定义2 1 ：对有序汉字串a b 中汉字a b 之间的互信息定义如公式( 2 - i ) 所示： 姒功- l 0 9 2 高 互信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阈值 时，便可认为该字组合可能构成了一个词。其中，p ( a ，b ) 为汉字串a b 联合出现的 概率，p ( a ) 为出现汉字串a 的概率，p ( b ) 为汉字串b 出现的概率，它们在汉字字符 串中出现的次数分别计为n ( a ) 、n ( b ) 、n ( a b ) ，n 是词频总数，则有公式( 2 - 2 ) ： 删，口) 兰丝，p 似) 。型，即) 。盟( 2 - 2 ) 万一厅 互信息反映了汉字串a b 间相关的程度。 ( 1 ) 如果i ( a ，b ) = 0 ，即p ( a ，b ) = p ( a ) p ( b ) ，贝i j a b 间是正相关的，随着i ( a ，b ) 增加，相关度增加，如果i ( a ，b ) 大于给定的一个阈值，这时可以认为a b 是一个词j ( 2 ) 如果i ( a ，b ) o ，e p p ( a ，b ) m p ( a ) p ( b ) ，则a b 间是不相关的； ( 3 ) 如果i ( a ，b ) 0 ，即p ( a ，b ) p ( a ) p ( b ) ，则a b 间是互斥的，这时a b 间基本不 会结合成词。 2 n - g r a m 统计模型 n - g r a m 统计计算语言模型的思想是：一个单词的出现与其上下文环境中出现 的单词序列密切相关，第n 个词的出现只与前面n - 1 个词相关，而与其它任何词都 不相关，设w l w 2 w 3 w n 是长度为n 的字串，则字串w 的似然度用方程表示如公式 ( 2 - 3 ) 所示。 p ) 。l ：i 聊l 晰册2 ”肼一1 ) ( ) 不难看出，为了预测词w n 的出现概率，必须知道它前面所有词的出现概率。 从计算上来看，这种方法太复杂了。如果任意一个词w i 的出现概率只同它前面的 两个词有关，问题就可以得到极大的简化。这时的语言模型叫作三元模型 ( t r i g r a m ) ，如公式( 2 4 ) 所示。 第8 页 基于词频统计的文本分类模型研究 上海师范大学硕士学位论文 p o v ) - p o v o p o v ：1 w ，) n 吼。p 噼l 职一搋一- ) 符号兀。p ( 晰l 班一搋一t ) 表示概率的连乘。一般来说，n 元模型就是假设 当前词的出现概率只同它前面的n 一1 个词有关。重要的是这些概率参数都是可以 通过大规模语料库来计算的，比如三元概率如公式( 2 - 5 ) 所示。 册限册- 1 ) _ 竺c o u n 蜡t w i2 w i1 ( 2 1 5 ) 一 一j 式c o u n t ( ) 表示一个特定词序列在整个语料库中出现的累计次数。 3 t - 测试原理嘲 定义2 2 ：对有序汉字串x y z ，汉字y 相对于x 及z 的t 一测试定义如公式( 2 - 6 ) 所 示。 如( ) ，) 。万丽p ( z 丽i y ) - 露p o 荔 i x 丽) ( 撕) 其中p ( y i x ) ，p ( z l y ) 分别是关于y 关于x ，z 关于y 的条件概率，6 2 ( p ( z l 妫、 6 2 ( p o l x ”则代表各自的方差，公式( 2 - 6 ) 中各量可用公式( 2 7 ) 、( 2 8 ) 估计。 p o , i x ) - 等- 等，p ( zj y ) 一等一等c 拼， 职p 仲) ) 一等川) ，) ) 一筹 ( 2 勘 从t 一测试的定义，可知： ( 1 ) 厶，：( ) ，卜0 时，字y 有与后继字z 相连的趋势，值越大，相连趋势越强； ( 2 ) 厶，z ( y ) 一0 时，不反映任何趋势； ( 3 ) t r ，z ( y ) to 时，字y 有与前趋字x 相连的趋势，值越小，相连趋势越强。 虽然利用以上三种方法可以很好的识别字与字之间构成词的可能性，但在实 际的使用中，一篇文档通常由成千上万乃至几十万的汉字和符号组成，识别单词 时计算量非常大，因而人们通常使用基于字典的方法，利用字典对文档进行扫描， 进行匹配，有多少单词就对文档扫描多少遍，以便统计出所有单词出现的频率， 这就是基于匹配的词频统计方法。 第9 页 基于词频统计的文本分类模型研究 上海师范大学硕士学位论文 2 2 3 基于匹配的词频统计方法 在信息科学领域中，关键词匹配( 即模式匹配) 问题一直都是研究的焦点之 一。模式匹配是指在文本t e x t = t lt 2t 3 t n 中检索子串p a t = p l p 2 p m ( 模式) 的所有出现，其在信息检索、信息压缩、入侵检测、模式识别、防火墙乃至计算 机理论等诸多方面都有重要的理论价值和应用前景。模式匹配从方式上可分为精 确匹配、模糊匹配、并行匹配等，著名的匹配算法有b f 算法、k m p 算法、酬算法 及一些改进算法关键词匹配是我们进行词频统计的关键技术，一般可分为单关 键词匹配和多关键词匹配。 单关键词匹配算法在国内外都对其进行了深入的研究，主要有b f ( b r u t e f o r c e ) 算法、k m p ( k n u t h - m o r r i s p r a t t ) 算法、b m ( b o y e r m o o r e ) 算法等，都已基 本上完善。b f 算法直观、简单，但涉及多次回溯，算法效率低，时间复杂度为 0 ( m * n ) ；k m p 算法实现了无回溯匹配，避免了b f 算法中频繁的回溯，文本串中的 每个字符只匹配一次，普遍提高了模式匹配的工作效率，时间复杂度为o ( n + m ) ： 踟算法实现了跳跃式匹配，文本串中的部分字符不需要匹配，时间复杂度为 o ( m * n ) ，但其最优情况下的时间复杂度为o ( n m ) 。此后，又有一些新的算法 被提出，大多都是对k m p 算法或b m 算法的改进及其各种变形和简化算法，用于特 殊情况。 1 朴素模式匹配算法b f 方法 朴素模式匹配算法( b r u t e f o r c e 算法，简称为b f 算法) ，亦称蛮力算法，其基 本思路是：从目标串s = “s l s 2 s n ”的第一个字符开始和模式串t = “t l t 2 t m ” 中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串s 的第二 个字符开始重新与模式串t 的第一个字符进行比较。依次类推，若从模式串s 的第i 个字符开始，每个字符依次和目标串t 中的对应字符相等，则匹配成功，该算法返 回i ；否则，匹配失败，函数返回0 。 2 模式匹配改进算法一k m p 方法 胁p 算法是d e k n u t h 、j h m o r r i s 和v r p r a t t 共同提出的，简称k m p 算法。 该算法较b f 算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有 了某种程度的提高。其改进在于：每当一趟匹配过程中出现的字符比较不等时， 主串不需要回溯i 指针，而是利用已经得到的“部分匹配”的结果将模式串向右 “滑动”尽可能远的一段距离后，继续进行比较。数组n e x t j 来确定这一滑动 距离，表示当模式串中第j 个字符与主串中相应字符“失配”时，在模式串中需 重新和主串中该字符进行比较字符的位置。其值取决于模式串本身，而与主串无 关。 第1 0 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 3 删方法 在j ( m p 算法的启发下，b o y e r 和m o o r e 提出了一种新的字符串快速匹配算法 - - b m 算法。两者的差别在于阴算法将对模式串的扫描方式从前向后变成从后向 前，并且考虑主串中可能出现的字符在模式串中的位置。其特点是：采用从后向 前的方式进行匹配，在每次匹配完成后，使用好后缀启发函数与坏字符启发函数 计算得到的移动值中的最大值来向后移动匹配位置。根据启发式函数，主串的部 分字符可以直接跳过，不进行比较。 2 3 树结构词频统计算法 2 3 1 基本思想 在第二节详细介绍了基于匹配的词频统计方法后，我发现这些经典的匹配算 法往往存在这样一个问题，多个关键词要进行统计时，不可避免的对待处理文档 进行多次扫描。尤其是当待处理文档较大时这一代价会变的更高，以上模式匹配 算法均未解决该问题。针对词频统计的特点，提出了一种新型的多关键词匹配方 法一树结构词频统计算法。 该算法基本思想如下：首先根据已有的关键词字典集合构建一棵查找树，利 用该树对文档进行扫描，进行关键词的词频统计。查找树由构成关键词的基本元 素组成。例如：如果关键词是英文单词，则结点中只包含一个字母字符；如果关 键词是数值，则结点中只包含一个数位；若关键词是中文词组，则结点中只包含 一个汉字。为了提高查找结点的速度，实现快速查找，约定该树是一棵有序树， 同一层中兄弟结点之间按照所含字符的a s c i i 码值从小到大排序。在每个结点处 标识是否为一个词结束，如果结点处为词的结束标志则记录该词的信息。进行词 频统计时，每次从文档中读取一个字符到查找树中比较，只需要对文档扫描一遍， 就可以统计出所有关键词的信息。如果许多词都由相同的字开头，即所有词的前 缀的数目远远小于所有词的长度总和时，查找树将特别适用。 该方法将关键词集合中词与词之间的冗余信息充分利用起来，减少了一些不 必要的匹配过程，在词频统计时对关键词集合中的每个词同时进行处理，大大提 高了统计效率。比如“上海”、“上海师范大学”两词中“上海”只需比较一次。 并且可根据实际需要在树中查找、计算各个词及其前缀的相关信息，有助于信息 处理进行下一步工作。 2 3 3 数据结构 在本课题中，我采用了j a v a 陶1 语言实现树结构词频统计算法，在j b u i l d e r 第1 1 页 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 下调试运行成功，并基于该算法实现了一个词频统计器，利用该统计器，可以方 便的对字典库中的关键词建立查找树，并通过该查找树一次性扫描就可以统计出 所有关键词的出现次数，为文本预处理也就是表示文本提供了方便的手段，实验 证明该算法性能优越，大大节省了文本表示的时间。为实现查找树，快速进行词 频统计，在程序中我编写了两个单独的类加以实现，他们分别表示树中结点和统 计出的关键词。整个树的静态数据部分就由这两个类构成的两个数组来实现。 对于这两个类，对其属性部分分别描述如下： c l a s st m y t r e e n o d e 表示树结点的类 p u b l i cc h a rk e y l字符( 数字、字母或汉字) p u b l i ci n tc o u n t l 出现个数 b o o l e a ni s w o r d l 是否词尾 p u b li ct m y t r e e n o d er e f ； 和该字符关联的其他结点 l 对文档扫描后统计出的关键词出现频率可以存放在如下类组成的数组中。 c l a s st s u b e l e m e n t 关键词类 p u b li cs t r i n gk e y l关键词 p u b l i ci n tc o u n t l对应出现次数 具体实现过程中，用一个动态数组来存储树中每个结点及其兄弟结点。为方 便统计时对结点查找，按照结点所存储的字的a s c i i 码值的大小从小到大有序插 入到数组中去。因为对有序内容的查找我们可以利用折半查找来实现，这样可以 大大提高查找的效率。假设每个结点有n 个孩子结点，则查找匹配次数由原来的 最多n 次减少到最多l 0 9 2 i n 次。 在数据结构具有的基础上，查找树的构造过程如图2 1 所示。 第1 2 页 基于词频统计的文本分类模型研究 上海师范大学硕士学位论文 釉鳓 图2 1 查找树构造过程 ( a ) ：从关键词集合中读取关键词“信息过滤”将其插入到树中，由于初始 根指针为空，则依次将每个字以结点的形式逐层插入到树中，每次生成一个大小 为1 的数组来存储结点信息，在结点“滤”的信息中标识一个词插入结束( 图中用 灰色结点表示) 。 ( b ) ：从关键词集合中读取关键词“信息港”将其插入到树中，由于根不为 空，则查找该词是否在树中存在。依次处理词中的每个字，取第一个字“信”查 找存在，则当前指针指向“信”结点。处理下一个字“息”，查找存在则当前指 针指向该结点。处理下一个字“港”，查找不存在，则将存储“过”结点的数组 长度加1 ，则将其作为“过”的兄弟结点插入并标识一个词结束；“过”和“港” 两结点均为“息”结点的孩子结点，由于“港”的a s c i i 码值比“过”的小，插 入时将其插入到结点“过”的前面。 ( c ) ：从关键词集合中读取关键词“计算数学”将其插入到树中，根指针不 为空，查找字“计”在当前指针所指结点的兄弟结点中是否存在，不存在则将存 储“信”结点的数组长度加1 ，则将其作为“信”的兄弟结点插入到根指针下 面，当前指针指向新结点；由于“计”的a s c i i 码值比“信”的小，将其插入到 结点“信”的前面。按同样方法处理其余的3 个字。 ( d ) ：从关键词集合中读取关键词“遗传算法”将其插入到树中，根指针不 为空则进行查找插入。首先查找“遗”字是否在根指针所指结点的兄弟结点中存 在，查找不存在则存储“计”、“信”结点的数组长度加1 ，将其作为“计”、 “信”结点的兄弟结点插入，当前指针指向新结点；由于“遗”字的a s c i i 码值 比“计”、“信”的都大，则将其插入到结点“信”的后面。操作步骤同上依次 第1 3 页 掣上掣；回；回鳓 基于词频统计的文本分类模型研究上海师范大学硕士学位论文 插入剩余的3 个字。所需的查找树构造成功。 在进行词频统计时，依次读取待处理文档中的每个字，在查找树上查找并记 录对应的字词信息。根据实际需要，可对已构造好的查找树添加新的关键词。并 且在构造树时，按照每个字的a s c i i 码值有序插入，便于快速的查找。这样每篇 文档只需读取一遍就可统计出所有关键词的词频数，大大提高了程序执行效率。 2 3 4 算法描述 查找树的算法的核心问题主要两个：一是如何从关键词集合中构造查找树， 二是如何利用查找树进行词频统计。这里通过两个算法的实现来解决此问题。在 查找树的构造生成算法中，令a r r a y 表示关键词集合数组，w o r d 表示当前处理关 键词；p o s i t i o n 表示关键词中的当前待处理字的位置，初始p o s i t i o n = o ；l e n g t h 表示关键词的长度。 算法2 1查找树的构造生成 1 ：w h il e 关键词集合数组a r r a y 未处理完毕d o 2 ： 取出a r r a y 中关键词w o r d ，标志其己处理 3 ：w h i l ep o s i t i o n l e n g t h 4 ：i f 树为空树 5 ： 第p o s i t i o n 个字生成新结点插入 6 ：e l s e 6 ：