贝叶斯分类算法

2024-10-17

贝叶斯分类算法（共8篇）

贝叶斯分类算法篇1

1 引言

朴素贝叶斯算法是基于贝叶斯全概率公式的一种分类算法[1,2]。它以贝叶斯定理为理论基础,是一种在已知先验概率和条件概率的情况下计算后验概率的模式识别方法。朴素贝叶斯分类算法有一个基本限制:在给定特征条件下的属性值之间必须相互条件独立,即特征项独立性假设。尽管在现实世界中,这种独立性假设经常是不能满足的,但目前许多研究和应用都表明,即使违背这种假定,NB也表现出很强的健壮性[3],所以越来越受到机器学习研究人员的重视[4,5]。但是由于贝叶斯分类分类算法本身的特点,它不可避免地存在一些其他的限制和不足,如训练集永远没有变化或者更新训练集后需要重新学习分类器从而耗费大量时间等,增量学习方法能够弥补这些方面的不足。

增量学习(Incremental Learning)是一种得到广泛研究与应用的智能化数据挖掘与知识发现技术[1,6,7,8]。在这个信息不断增长的时代,一种机器学习方法是否具有良好的增量学习能力已经成为评价学习性能优劣的重要参考之一。但是传统的贝叶斯分类算法只是在分类时使用到先验概率与样本信息,很少涉及到对分类器进行增量学习,文章[6,8]中提到的增量学习都是基于文档型计算公式的朴素贝叶斯分类算法。这种使用文档型计算公式计算属性的类条件概率存在特征项对文本贡献不明显的弊端。Harry Zhang在文献[9]中提出了根据属性的重要性给不同属性赋不同权值的加权朴素贝叶斯(Weighted Naïve Bayes,简称WNB)模型并实验得出较理想的效果。但是Zhang的文章未涉及到增量学习修正分类器。

本文结合上述两种思想的优势,提出加权朴素贝叶斯分类增量学习算法。文章对加权贝叶斯分类增量学习算法思想以及实现过程进行了详细描述并对算法进行证明。通过算法分析,得到其相比无增量学习的贝叶斯分类,额外的空间复杂度与时间复杂度都在可接受范围。

2 朴素贝叶斯分类算法

2.1 朴素贝叶斯分类算法简述

朴素贝叶斯分类方法中,每个数据样本用一个m维向量:d=d(W1,…,Wi,…,Wm)表示,其中Wi表示文本特征项;训练集D={d1,d2,…,dN}中的每个文本属于类集C={c1,…,ck}中的一个类。利用贝叶斯公式通过类别ci的先验概率和文本的类条件概率P(d|ci)来计算未知文本d属于ci类的概率,并取后验概率最大的类为文本的类别。计算公式如下:

undefined

undefined

其中P(wj|ci)即特征项wj在类ci中出现的概率,也叫属性的类条件概率。

2.2 贝叶斯分类算法的缺陷

朴素贝叶斯分类算法具有简洁,高效和稳定等优势,但是也存在一定的弊端。其要求在给定特征条件下的属性值之间必须相互条件独立在现实文本中就难以满足。但目前许多研究和应用都表明,即使违背这种假定,朴素贝叶斯也能取得较好效果。除了这个独立性假设,目前研究的朴素贝叶斯分类算法还是存在一个比较明显的缺陷。

朴素贝叶斯分类算法就是根据训练样本的类先验概率和特征项的类条件概率(都从训练集D中得到)来预测后验概率,得出测试文档的类别标签。有限的训练文本集的文本分布很难完全代表总体文本的分布,所以计算得到的先验概率的可信度有待修正。如果训练集D没有良好的数据完备性,那么预测的测试文档类别标签就可能不准确。而真实的情况是,有限大小的训练集D不可能具有完备的数据,一些领域的分类文本也是一批一批得到。不学习新的文本的分类器的分类效果必然没有多学习新的文本的分类器的分类效果好。传统的贝叶斯分类要想学习新的文本所包含的信息,就需要重新学习全部文本,每这样学习一次,都需要耗费大量时间代价。

3 贝叶斯分类增量学习算法

3.1 增量学习思想

在原始条件下,训练集D是保持不变的。而有限的训练集要完全表示文本的分布情况是不现实的。为此需要通过一种方法来不断更新训练集,以期达到完备训练集从而使其分类效果更精确的目的。增量学习思想[3]就是将测试集Dt中没有类别标签的实例经过分类器分类后,经过一个严格判断过程,将判断确认正确分类的文本追加到训练集D中;以及将专家给出正确分类的文本和其他途径得到的批量已分类文本追加到训练文本集,使得训练文本信息能够得到扩充,信息量更加丰富。在分类器已有知识的基础上,结合新加入文本,再次训练分类器,利用新文本中含有的有用信息来修正当前的分类器,能够使得各类别的先验概率以及各特征项的类条件概率能够更加精确,从而使得分类器分类效果更好。

对于贝叶斯文本分类,增量学习的任务实质上是如何根据先验信息和新加入样本的信息来确定新的先验概率P(ci)和各个属性类条件概率P(wk|ci)。

对于属性类条件概率P(wk|ci),文献[6]与[8]中使用的是文档型计算公式:

undefined

其中P(Aj=aj|c=ci)为特征项aj属于类ci的概率,count(Aj=aj|c=ci)为在属于类ci的文本中出现了特征项aj的文本数, count(c=ci)为属于类ci为属于类的文本数。

此计算公式具体简洁易算的特点,能够使得分类方法在这个过程中计算速度很快。但是,依据此公式,多个对文本类别贡献不同的特征项,只要都同时在若干个文本中出现,其属性的类条件概率就相同。显然,这样的属性类条件概率公式完全不能凸显特征项在文本中的重要性。为克服此弊端,本文对属性的类概率P(wj|ci)计算采用能够体现特征项在文本中重要性的词频加权计算公式,公式如下:

undefined

式中|V|表示项表中总项数,TF(wj,ci)表示项wj在训练集中属于类ci的所有文本中出现的频次之和,即

undefined

式中fik为特征项wi在文本dk中的出现频率。为防止TF(wj,ci)为0从而引起P(wj|ci)为0的情况发生,可以在初始化时先给每个TF(wj,ci)赋初值0.01。赋小的初值能够解除前面的疑虑,同时又能避免淹没其他在类中少量出现但是分类能力强的特征项。

3.2 增量学习文本选择

并非所有测试文本都适合用来对系统进行增量学习,那些类别不太明确或者对类别表示贡献不大的文本,加入后可能反而使类别特征模糊化。所以对于哪些文本采取增量学习应有严格的限制。有两种情况的文本适合分类器增量学习,一种是有专家已经给予分类的文本,这在专题文本领域是很常见的;另一种是对未分类的文本,由分类系统自动判断其是否合适参与增量学习。本文主要论述第二种情况,第一种情况相比第二种情况少了判断过程,实际上是一个单纯的增量学习的过程。

对于没有类标签的文本dt,需要用现有的分类器为它分配类标签。为方便计算,本文定义给文本划分到某类的概率取一个名称为类置信度,用θ表示。依据上面的公式(4),文本dt属于类ci的类置信度为:

undefined

令θt=max{θi,1≤i≤k},则分类结果为,即dt属于类ct。

判断被分类文本dt是否满足加入训练集进行增量学习的条件是:如果θt满足:undefined,即θt不小于其他类置信度之和的某个系数倍,则系统相信文档dt属于类ci的划分确定可信。系数α设定越大,系统对于参与增量学习的文本要求越严格。根据经验得出α∈[1/2,1]系统都能得到比较好的效果。

3.3 算法描述

输入:训练集D={d1,d2,...,dN},测试集Dt={dN+1,dN+2,...,dK}

输出:分类器C,测试文档dt类别

Step1:利用训练集D,学习分类器C;

Step2:对于测试集Di中每个文本di,重复如下步骤:

Step3:利用分类器C,分类di,得到类标签〈di,ct〉;

Step4:依据式(6)判断类置信度θt,如果undefined,进行下一步,否则,转Step6;

Step5:undefined,修正分类器C,包括修正P(ci)、P(wk|ci)、D和|Dci|;

Step6:Dt=Dt-dt,判断Dt是否为空,为空,执行下一部,否则转Step2;

Step7:算法结束。

下面给出上述算法中的增量学习公式并在后文给出部分证明。

类先验概率修正公式:

undefined

属性的类条件概率修正公式:

undefined

文档数量修正公式:D=D+1;|Dci|=|Dci|+1,当ct=ci

其中:D表示文档总数;|Dct|表示属于ci类的文档数;|Wci|表示属于ci类的所有文本中的所有词频总和;fkt表示特征项wk在文dt中的频率;undefined表示文档dt中出现的所有词的词频总和。

对分类器进行修正的文本不仅仅限于系统判断保证准确分类的文本,还可以是专家分类结果文本和其他途径得到的批量带分类文本。对带分类的文本的增量学习,直接进行Step5。可以看出,依本算法得到的分类器除了拥有较好的自学习能力,还有良好的人机交互功能。其增量学习能力正是我们所期望的。

4 算法证明与分析

4.1 算法证明

下面对式(7)进行简单证明。为方便阅读,对新生成的变量P(ci),以P*(ci)表示以显示区别,其他变化变量同此。式(7)中ct=ci情况下对P(ci)增量学习公式证明如下:

undefined

证毕。

当ct≠ci时,P(ci)的增量学习公式undefined,可以看出它是ct=ci情况下对P(ci)增量学习公式的一部分,证明参照上式。

式(8)中当ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式证明如下:

undefined

证毕。

式(8)中当ct=ci并且wk∉dt情况下对P(wk|ci)增量公式证明如下:

undefined可以看出它是ct=ci并且wk∈dt情况下对P(wk|ci)增量学习公式的一部分,证明参照上式。

4.2 算法分析

对新加入一个文本到训练集,系统需要保存的内容包括:新文本的各特征项,各类的先验概率,各属性的类条件概率,为增量学习系统需额外保存与临时保存的内容有属于类ci的词频总和、|Wci|新加入文档dt中的词频总和undefined、新的类先验概率P(ci)以及新的属性的类条件概率P(wk|ci),不能分析得到,因增量学习而产生的额外空间开销为S(m),其中m为新文本中的特征项数;

在额外时间复杂度方面,对系统进行一个文本的增量学习,与不进行增量学习的差别主要在step4与step4,即需要对是否进行增量学习做判定以及需要重新计算被分类文档的词频总数、类先验概率、属性的类条件概率、文档总数与划入类的类文档总数。step4做判定的时间复杂度是O(k),计算总词频总数、文档总数与划入类的类文档总数是一个简单加法,复杂度为O(1),计算类先验概率的时间复杂度为O(k),计算属性的类条件概率的时间复杂度为O(km),不难得出额外时间开销为O(k)+O(1)+O(k)+O(km)=O(km),其中m为分类系统中所包含的总项数,k为文档类别总数。可以看出,贝叶斯分类增量学习算法在空间和时间复杂度上的额外开销都在可接受范围,所以该算法是可行的。

5 结束语

朴素贝叶斯分类方法以其高效率为广大研究人员接受,但是关于其增量学习方面得到的关注并不多,更多是关注到属性条件概率计算上面,以使特征项能更好的表现文本。本文研究属性类条件概率计算公式为TF加权法的加权朴素贝叶斯分类增量算法,对给出了算法思想,具体算法以及算法证明和分析。虽然采用TF加权比文档型计算公式对分类效果要好很多[9],但是采用的TF加权法,也存在如下弊端:一些在多种类型的文本中多次出现的词削弱了其他分类能力强的词的表现力。作者下一步目标是研究能够在时间复杂度可接受范围内进行的更理想的加权朴素贝叶斯分类增量学习算法。

参考文献

[1]史忠植.知识发现.北京:清华大学出版社,2002.169～220

[2]王玉玲.基于贝叶斯理论的分类模式挖掘方法研究.微计算机应用,2007,28(6):664～668

[3]Domingos P,Pazzani M.On the Optimality of the Simple Bayesian Classifier under Zero-One Loss.Machine Learning,1997,29(2-3):103～130

[4]Yager R.An extension of the naive Bayesian classifier.Information Sciences,2006,176:577～588

[5]Mc Callum A,Nigam K.A comparison of Event Models for Naive Bayes Text Classification.AAAI-98Workshop on Learning for Text Categorization,Madison,Wisconsim:AAAI Press,1998,509～5l6

[6]宫秀军,刘少辉,史忠植.一种增量贝叶斯分类模型.计算机学报,2002,25(6):645～650

[7]Nadeem Ahmed,Syed Huan.Incremental learning with support vector machines,IJCAI[c],Stockholm,Sweden,1999.

[8]姜卯生,王浩,姚宏亮.朴素贝叶斯分类器增量学习序列算法研究.计算机工程与应用,2004,14:57～59

[9]Harry Z,Sheng S.Learning Weighted Naive Bayes with Accurate Ranking.In:Fourth IEEE International Conference on Data Min-ing(ICDM'04),2004.567～570

贝叶斯分类算法篇2

【关键词】贝叶斯算法被动学习主动学习邮件过滤精度

1 主动学习贝叶斯的原理

传统的算法学习其实都是一些被动学习，用来学习的样本材料都是经过处理的，它们的选择往往是被动的，主要表现在所来学习的样本都会被做上一些标注的，而且并不是所有的样本都是真正独立的，有一些可能并不独立，只是被假定了独立，虽然这样也能达到学习的目的，但效果却不是很好。而相对于被动学习来说，主动学习是一种真正的学习，它有以下几个方面的特点：首先将使用很少量的带有标注的学习样本来训练如何使用过滤器，在这个过程中也可以得到一些关于选择怎样的样本对实验结果更好的策略；然后就可以依照之前所得到的选择策略从候选的样本集中选择出令人满意的目标样本；最后将这些认为最好的样本放入过滤器中，如此往复的测试，这样符合标准的样本就被选出来了。当然最初对于样本选择的多少将决定着学习的速度，同时好样本当然也意味着后来学习的质量。

2 基于最大最小熵的主动学习

熵有一个很明显的性质就是，要想获得最大值，就必须含有均匀分布的随机变量。取值的均匀分布是参数无信息分布的一个条件，而熵取得最大值也是在这种情之下，也就是先验分布。无信息意味着不确定性，意味着信息的空白，那是一种一无所知的感觉，是一种最不确定性情况的出现。而熵恰好就是这样一种来表示不确定的方法。在这里，用来衡量目前过滤器实例样本分类确定性的标准，就是关于类条件后验熵，公式如1-1所示。

公式（1-1）

由于在选择学习样本时，总是选择那些类条件概率相近的样本，达到了均匀分布的目的，但是这样的选择方式也暴露了很明显的两个缺陷，它们对分类效果是有影响的。这两个缺陷分别是单一的处理手段对于众多问题的无力性和分类误差的累积进而进行阻止的无效性。不确定样本的选择造成了一定的误差，而累积的误差将导致更大的误差，导致了分类的无效性。这些是不确定性抽样学习中产生的不可克服的问题，而要解决误差问题是很难得，但是可以尽量减少误差的产生，提高分类正确性，最大最小熵的处理办法就是这样的方法。那就是分别选出类条件熵最大和最小的候选样本并将这两个样本加到数据池选出的样本集中，然后加入过滤器，找出一些特别信息，同时可以确定的是类条件熵最小是一个较为确定的样本集，使分类更加准确同时阻止误差蔓延扩大。

3实现流程

最大最小熵主动学习的实现流程如下：

（1）从训练集中随机选择一组邮件作为候选样本集。

（2）对候选样本集中的每一个样本，利用公式1-1来计算样本熵值的大小。

（3）取熵值最大和最小的两个样本加入到分类模型。

（4）从候选集合中删去这两个样本。

4实验结果及分析

对主动学习过滤器本文进行在线和离线两个模式下的过滤实验。首先，在trec07p邮件集上进行在线及时反馈过滤，其过滤结果如表1-1所示。

在sewm 2008公开数据集上进行离线过滤，且取sewm 2008公开数据集前30000封进行训练，后40000封进行测试，其实验结果如表1-2所示：

从实验结果可以看到，在在线立即反馈模式下，主动学习过滤器在（1-ROCA）%参数，都取得了更小的值。但是在离线模式下，过滤器是先进行过滤器训练，再进行测试且这个过程没有反馈学习，所以主动学习算法并不能起作用。而且另一方面，加入主动学习的过滤器在算法中加入了候选集计算熵的过程，使得邮件过滤效率比未加入主动学习学习的算法要低。加入主动学习的过滤器相对于未加入主动学习的过滤器来说，ROCA参数虽然有所降低，但是过滤速度太慢，每封邮件的处理时间比未加入主动学习过滤器10倍还要大。

【参考文献】

[1]王辉.基于知识积累型的朴素贝叶斯垃圾邮件过滤算法研究 [D].湖南大学，2013

[2]刘建封，吕佳.融合主动学习的改进贝叶斯半监督分类算法研究[J]. 计算机测量与控制，2014（6）

（课题项目：吉首大学张家界学院重点科研课题项目资助。）

贝叶斯分类算法篇3

分类是数据挖掘中一项重要的核心技术,其目的就是通过学习得到一个目标函数f,把每个属性集映射到一个预先定义的类标号y,因此可以将分类看作是从数据库到一组类别的映射。这些类别是被预先定义的,没有重合的。数据库里的每一个元组都可以准确地分配到某个类中。朴素贝叶斯分类器是一种最简单、有效、具有坚实的理论基础并在实际应用中得到广泛使用的分类器。朴素贝叶斯分类方法基于条件独立性假设,即假设一个属性对给定类的影响独立于其他属性,而这在现实问题中往往并不成立,为此,许多学者做了大量的工作来放松独立性假设。Harry Zhang等根据条件属性对决策所起的作用给予它们不同的权值,提出了加权朴素贝叶斯分类模型。Zhou Jiyi等根据粗糙集权重确定方法提出了一种基于区分矩阵的属性权重确定法。程克非、张聪提出了一种基于特征加权的朴素贝叶斯分类器。秦锋、任诗流提出一种通过用加权调整的先验概念来代替原朴素贝叶斯的先验概率。白似雪,梅君提出一种计算每个属性对每个类的相关概率和不相关概率,并以此进行加权。本文提出另一种加权方法,将信息论里互信息知识与属性之间的相关性相结合,给予不同的条件属性赋予不同的权值,实验证明,这种方法能有效提高分类效果。

1 朴素贝叶斯分类器

每个元组用一个n维属性向量X={x1,x2,…xn}表示,描述由n个属性A1,A2,…,An对元组的n个测量。假定有m个类C1,C 2...,Cm。这样,给定一个未知的元组X,其P(Ci|X)最大的类iC称为最大后验假定。根据贝叶斯定理:

由于P(X)对于所有类为常数,只需要P(X|Ci)P(Ci)最大即可。如果类的先验概率未知,则通常假定这些类是等概率的,即P(C 1)=P(C 2)=...P(Cm)。并据此对P(Ci|X)最大化。否则,最大化P(X|Ci)P(C i)。注意,类的先验概率可以用P(C i)=si/s计算其中is是类iC中的训练样本数,而s是训练样本总数。

给定具有许多属性的数据集,计算P(X|Ci)的开销可能非常大。为降低计算P(X|Ci)的开销,可以做类条件独立的朴素假定。给定元组的类标号,假定属性值有条件地相互独立,即在属性间不存在依赖关系。这样,

先验概率p(x1|Ci),p(x2|Ci),……,p(xn|Ci)可以从训练数据集求得。

根据此方法,对一个未知类别的样本X,可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci),然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为:

2 属性加权朴素贝叶斯分类算法

在现实实际应用中不同的条件属性与决策属性之间的相关程度是不同的,当条件属性与决策属性的相关程度高,它对分类的影响就要更大些,反之,如果条件属性与决策属性的相关程度较小,那么它对分类的影响就会很小。条件属性与决策属性的相关关系可以用相关系数的求解公式求得。设条件属性为Xi,决策属性为Y,其相关系数可以通过Xi与Y的协方差与Xi与Y的方差的几何平均数求商得到,它反映了Xi与Y属性的线性相关紧密的程度,值越大表明属性之间的联系越紧密,反之则联系较差。

属性间的相关系数为:

由于权值的范围介于0和1之间,则设定权值为:

信息论里的互信息概念是描述某个随机变量关于其他随机变量变化时的信息量的大小,它可以用来反映条件属性提供的关于决策属性的信息量的大小。而相关系数是通过代数方法里的协方差与方差来求得的,它侧重与属性间的偏离程度,能够有效的改进分类能力,但是它对属性间的变化不敏感。因此希望通过结合相关系数与互信息的知识,从而使属性获得更好的权重,提高分类效果。

设条件属性C和决策属性D的互信息,记为:

因此可以得出条件属性iC的权值为:

综合相关系数与互信息的权值公式,定义两者的平均值作为新的权值公式:

基于属性加权的AWI-AUC算法的实现关键在于求出各条件属性与决策属性之间的相关系数和他们的互信息。具体算法步骤如下:

步骤1数据预处理:将训练样本和待分类样本进行补齐和离散化;

步骤2分类器的建构。

步骤2.1读入并搅乱数据集,对数据集里的条件属性,决策属性,以及训练样例进行统计,生成统计表。再将数据集划分为新的训练集和测试集。

步骤2.2生成分类器网络结构,并对其进行参数学习。

步骤2.3计算所有的先验概率值,即在决策属性Dj下各个条件属性Ci取值的概率p(Ci|D)。

步骤3计算权值。

步骤3.1权值Wc的计算。扫描所有的训练集,求出各条件属性与决策属性的协方差Cov(Ci,D)和方差D(Ci)和D(D),通过公式计算得到相关系数ρCi D,则权重Wc=|ρCi D|。

步骤3.2权值Wi的计算。先求出条件属性和决策属性的互信息I(Ci,D),再计算权重Wi。

步骤3.3综合权值Wc和Wi,求得所需的权值Wci,并生成属性权值列表。

步骤4分类评估。通过对属性给予不同的权值,得出分类结果。

该算法的性能在各多项式时间内完成,并且算法可行。

3 实验结果及分析

为了验证算法的可行性和有效性,用数据集对算法进行了测试。实验数据集选自UCI(University of California in Irvine)数据库,下载网址是http://www.ics.uci.edu/~mlearn/MLRepository.html。所有数据集中数据的连续属性值均进行离散化处理。实验在MBNC(Bayesian Networks Classifier using Matlab)平台下完成。首先对数据集进行随机搅乱,打乱数据之间原先的排列顺序,并对数据集采取5叠交叉验证。每个数据集轮流实验5次,取5次实验的平均值作为实验的测试结果。表1为经过预处理后的数据集情况。

实验结果如表2所示。O-AUC表示的是没有使用加权方法时得出的AUC值,CC-AUC表示的是使用相关系数作为加权方法得到的AUC值,I-AUC表示的是使用信息论中的互信息知识作为权重后得到的AUC值,AWI-AUC表示的是本文提出的AWI-AUC算法得到的AUC值。

由表2可知:

(1)当O-AUC与CC-AUC,I-AUC比较时,可以看出CC-AUC,I-AUC在各个数据集下得到的AUC值均大于O-AUC,可见通过把条件属性与决策属性的相关系数和互信息作为条件属性的权重,可以提高分类器的分类性能,使得分类更加准确。

(2)当CC-AUC与I-AUC比较时,CC-AUC的值比I-AUC的值大的有6个数据集,比I-AUC值小的有4个数据集,并且这4个数据集中的训练集个数均偏大,可见I-AUC更适合对数据集大的进行分类,会获得更好的分类效果,只是原样本集里填充和离散的数据会对原样本产生影响。CC-AUC在这种情况下可以有效地提高贝叶斯分类能力。但CC-AUC采用的权重是通过相关系数得到,相关系数由代数的计算方法求得,结合实验对数据规模偏小的数据集更加适合,因此将上述两种方法综合求均值,得到新的AWI-AUC方法,通过实验证明AWI-AUC在总体上要好于其他方法,并证明了通过挖掘属性之间的潜在关系,对属性赋予不同程度的权重,可以获得更好的分类效果。

4 结束语

本文基于研究条件属性与决策属性之间的关系,并结合信息论中互信息的相关知识,提出一种加权的AWI-AUC方法,根据条件属性对决策分类的重要性不同给予其不同的权重系数来对AUC方法进行优化评估。在MBNC实验平台上实现该方法,并在数据集上通过实验比较,表明该方法的有效性和可行性。今后,将进一步研究改进条件属性与决策属性相关性的方法,以及分析条件属性与条件属性之间的关系,是否能够更好地提高分类器的分类能力。

参考文献

[1]秦锋,杨波,程泽凯.分类器性能评价标准研究[J].计算机技术与发展.2006.

[2]Harry Zhang,Shengli Sheng.Learning Weighted Na?ve Bayes with Accurate Ranking.[C]//The 4th IEEE International Conference on Data Mining.Chicago:IEEE Computer Society,2004.

[3]ZHOU Jiyi,LV Yuejin.A New Method of Ascertaining Attribute Weight Based on Discernibility Matrix.CSIST.2010.

[4]程克非,张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真.2006.

[5]秦锋,任诗流等.基于属性加权的朴素贝叶斯分类算法[J].计算机工程与应用.2008.

[6]白似雪,梅君,吴穹.一种基于概率加权的朴素贝叶斯分类.2009.

[7]林士敏,王双成,陆玉昌.Bayesian方法的计算学习机制和问题求解[J].清华大学学报.2000.

[8]张明卫,王波,张斌.基于相关系数的加权朴素贝叶斯分类算法[J].东北大学学报(自然科学版).2008.

[9]C.Blake and C.Merz,UCI Repository of Machine Learning Databases.http://www.ics.uci.edu/~mlearn/MLRepository.html.1998.

贝叶斯分类算法篇4

许多人把数据挖掘视为另一个常用的术语:数据中的知识发现。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的, 但又是潜在的、有用的信息和知识的过程。

本文利用数据挖掘中的朴素贝叶斯分类技术来研究鸢尾花数据集中有关于鸢尾花分类问题。以鸢尾花数据集为对象, 尝试通过数据挖掘中的朴素贝叶斯分类技术对数据进行分析, 实现对鸢尾花所属分类进行预测, 发现鸢尾花所属分类与鸢尾花各项数据之间的联系, 有助于对鸢尾花的培养进行管理。

2朴素贝叶斯分类算法

假设每个数据样本用一个n维特征向量来描述n个属性的值, 即X={x1, x2, ..., xn}, 假设有m个类, 分别用C1, C2, ..., Cm表示。给定的一个未知的数据样本X (没有标明属于哪个类) , 根据贝叶斯定理得:

undefined

P (xn|Ci) 都可以从训练数据集求得。

根据此方法, 对于类别未知的样本X, 可以先分别计算X属于每一个类别ci的概率。

P (X|ci) *P (ci) , 然后选择概率最大的类别作为其类别。

若朴素贝叶斯分类算法将未知数的数据样本X分配给Ci, 则需要满足:

P (|X) > P (|X) , P (ci| X) >P (cj|X) , 1≤j≤m, i≠j

从理论上来讲, 朴素贝叶斯分类算法与其他算法相比有着最小的错误率, 在实践中朴素贝叶斯分类算法还可以和神经网络算法和判定树等分类算法相媲美, 并且它的适应性也很强, 执行效率高, 在给定的N个属性的M个训练集, 学习时间的复杂度为O (N*M) , 这使得它在现实中有着广泛的应用。

3实例

鸢尾花数据集中数据属性分为花萼长、花萼宽、花瓣长、花瓣宽和所属分类5项。为了编程方便, 使用calyx_length表示花萼长、calyx_width表示花萼宽、petal_length表示花瓣长、petal_width表示花瓣宽、category表示所属分类如表1所示。

鸢尾花的类别分为3种:Iris-setosa、Iris-versicolor、Iris-virginica, 我们从鸢尾花数据集中选取60个数据样本作为训练数据集 (可随机选取, 这里为了实验计算方便, 每种类别均选取了20个样本) , 预测一个未知的数据所在分类。

若从预测数据集中读出如下数据 (5.4, 3.7, 1.5, 0.2) , 其中对应的4个属性类别分别为花萼长 (calyx_length) 、花萼宽 (calyx_width) 、花瓣长 (petal_length) 、花瓣宽 (petal_width) 。3个分类类别分别为setosa (用C1表示) , versicolor (用C2表示) , virginica (用C3表示) 。

朴素贝叶斯分类算法的步骤如下:

(1) 计算训练数据集中每个种类所占的比例。

因为60个训练数据集中每个种类均选取了20个样本, 所以在训练数据集中对于鸢尾花的3个种类出现的概率为:

P (setosa) =P (versicolor) =P (virginica) =1/3。

(2) 计算每个属性在训练数据集中的条件概率P (X|ci) , (i=1, 2, 3)

从每个预测属性值可以得到如下数据:

(3) 求最大后验概率P (Ci|X) 。

根据贝叶斯定理后验概率可以通过求先验概率来得到, 即P (X|ci) *P (ci) , 这里可以得到如下数据:

(4) 判断P1, P2, P3的大小:Max (P1, P2, P3) 。

在这里Max (P1, P2, P3) =P1, 所以我们把预测数据分类在P1类, 即Iris-setosa类别。实际上预测数据的类别就是Iris-setosa。如果Max (P1, P2, P3) =P2, 那么分在versicolor类, 如果Max (P1, P2, P3) =P3那么分在virginical类。我们通过这个过程说明如何使用朴素贝叶斯分类算法对未知数据进行分类, 达到了数据挖掘的目的。

4结束语

随着计算机技术的发展, 数据挖掘越来越受到研究人员的关注, 而分类算法中的朴素贝叶斯分类算法以其简单的算法思想、较高的精确度等优点成为挖掘领域热门的研究方向。朴素贝叶斯分类算法是建立在各个属性之间的相互独立性假设的前提下进行的, 这种假设在现实中是很少出现的。朴素贝叶斯分类算法在属性之间没有那么严格的条件下也能发挥比较好的性能, 所以朴素贝叶斯分类算法在证券、消费、教育、银行等行业中占有一席之地。

参考文献

[1]李志刚, 马刚.数据仓库与数据挖掘的原理及应用[M].北京:高等教育出版社, 2008.

[2][美]PANG-NING TAN, MICHAEL STEINBACH, VIPIN KU-MAR.Introduction to Data Mining[M]北京:人民邮电出版社, 2006.

[3][美]WALTER SAVITCH, Absolute Java[M], 北京:清华大学出版社, 2008.

[4]李艳, 刘信杰, 胡学刚.数据挖掘中朴素贝叶斯分类的应用[J].潍坊学院学报, 2007 (4) .

贝叶斯分类算法篇5

1 中文文本预处理

1.1 分词预处理

在文本的组织上, 中文与以英语为代表的欧美语言有着很大的不同, 在西方语言中, 词与词是使用空格隔开的, 因此不需要进行分词处理, 而在中文文本中, 字、词是连在一起的。因此, 分词的难度较大。中文分词技术面临的两个最大问题是歧义切分和未登录词识别[1]。本文采用中科院的汉语词法分析系统ICTCLAS完成这项工作。该系统采用统计方法和规则方法相结合的方式, 基于N- 最短路径的方法对中文文本进行无歧义文本初切分, 然后通过多层隐马尔可夫模型算法进行未登陆词识别, 取得了非常好的分词效果。系统分词正确率高达97% 以上, 未登陆词识别召回率高达90%。

1.2 数据清洗

经过分词处理的文本, 并不是所有的特征都对构造向量空间模型和分类有帮助, 相反, 将对文本分类没有帮助的词作为特征项, 会对分类的精度造成很大的影响。另外, 去停用词可以很大程度上减小特征项的数量, 对文本降维具有很大帮助, 所以在构造向量空间模型前, 要对分类无帮助的词进行尽可能彻底的清理。本系统是在词性标注的基础上进行数据清洗的。经过分词处理后, 对于标点w、助词u、连词c、介词p和量词q等进行清洗。

1.3 去停用词

停用词主要是指文本中存在的助词、副词、连词、代词、介词、叹词、量词和数词等。例如:助词中的“的, 得, 地, 吧, 呢”;副词中的“非常, 很, 十分, 都”。

去停用词在技术上实现并不复杂, 只需建立一个停用词词典, 将在分词后每个词与停用词词典内的词条进行匹配, 如果匹配成功, 则将该词去掉。

2 文本特征选择

特征选择是为了提高文本分类的效率, 减少计算复杂度。文本特征选择通常通过判断特征词进行。常用的方法有:文档频率、信息增益、互信息、统计量和期望交叉熵等[3]。本文采用信息增益和文档频率方法进行特征词判断。

2.1 信息增益

信息增益是一个基于熵的评估方法, 定义为某特征项在文本中出现的前后信息熵之差。对于特征项w和文档类别c, IG考虑c中出现和不出现w的文档频率来衡量w对于c的信息增益。w对于c的信息增益越大, 说明特征项w对于类别c越重要, 贡献越大。信息增益评估函数定义如式 (1) 所示。

式 (1) 中, m表示类别数, P (ci) 表示ci类文档在语料中出现的概率, P (w ) 表示语料中包含特征项w的文档频率, P (ci|w) 表示文档包含特征项w时属于ci类的条件概率, P () 表示语料中不包含特征项w的文档频率, 率P (。ci|) 表示文档不包含特征项w时属于ci类的条件概

2.2 文档频率

文档频率 (document frequency, DF) 是含特征项的文本数目。其思想是:DF值低于某个阈值的词条是低频词, 它们不含或含有较少的类别信息。并从特征空间中去掉这些低频词, 从而降低空间维数提高分类的精度。

3 文本分类

文本分类用一个已标记类别的文本数据集来训练分类器, 这个文本数据集称为训练集, 然后用训练好的分类器对未标记类别的文本进行分类。比较常用的文本分类算法有, KNN算法、SVM算法和贝叶斯算法等。

在许多场合, 朴素贝叶斯 (Naïve Bayes, NB) 分类算法可以与决策树和神经网络分类算法相媲美, 该算法能运用到大型数据库中, 且方法简单、分类准确率高、速度快。从理论上讲, 与其他所有的分类算法相比, 贝叶斯分类具有最小的出错率, 在其类条件独立的假定成立的前提下, 它是最佳的分类算法。然而在很多情况下, 其类条件独立的朴素假定并不能成立, 但实践证明, 即便如此, 它在很多领域中仍然能够获得较好的分类结果。

朴素贝叶斯方法 (Naïve Bayesian) 将训练文档分解成特征向量和决策类别变量, 假定特征向量的各分量间相对于决策变量是相对独立的, 也就是说各个分量独立地作用于决策变量。朴素贝叶斯的属性间条件独立假设使得对联合概率的计算大大简化, 公式如 (2) 所示。

构造分类器模块是训练过程的关键模块, 应用贝叶斯分类算法, 构造具体的分类器。训练过程一般比较耗时, 系统将所有文本训练一次后, 把特征项的相关信息等存入文件中。在训练一次后, 测试时直接从配置文件中读入相关信息而不需要再次训练。从而节省时间。

假设训练语料包含N个文本D={D1, D2, Dn}, 这些文本分属于M个文本类别C={C1, C2, Cm}, 训练语料集共有L个文本特征词W={W1, W2, WL}。

当文本Di属于类别Cj时, 则有P (Cj|Di) =1, 否则P (Cj|Di) =0。如果给定文本类别变量, 则文本类别Cj的先验概率估计按公式 (3) 计算。

若用F (Wk, Di) 表示特征词Wk在文本Di中出现的次数, 则特征词Wk在类别Cj中的概率估计按公式 (4) 计算。

任何文本都可视为一系列有序排列的特征词的集合, 在朴素贝叶斯模型中假定特征向量的各分量间相对于决策变量是相对独立的, 则类别Cj中产生文本Di的概率按公式 (5) 计算。

根据测试文本特征数据计算测试文本属于每个类别的概率, 然后按照最大概率给测试文本分类。测试文本Di属于类别Cj的概率按公式 (6) 计算。

摘要：本文针对中文文本分类的特点, 采用中科院汉语词法分析系统ICTCLAS对文档进行分词, 并进行数据清洗和过滤停用词, 运用信息增益和文档频率特征选择算法对文档进行特征选取。

关键词：中文分词,本文分类,信息增益,朴素贝叶斯算法

参考文献

[1]陈平.基于SVM的中文文本分类相关算法的研究与实现[D].西安:西北大学, 2008

[2]余芳.一个基于朴素贝叶斯方法的Web文本分类系统:web CAT[J].计算机工程与应用, 2004 (7) .

贝叶斯分类算法篇6

在数据挖掘领域中,分类是一个非常重要的问题,是当前研究的热门。针对分类的问题,国内外都有比较深入的研究。其中成熟的分类算法有如决策树、基于向量空间模型的K-近邻分类、关联规则分类、神经网络、遗传算法、朴素贝叶斯等。在众多的分类算法中,朴素贝叶斯算法由于有着深厚的数学理论研究基础,以及其计算高效简单、有效而在众多应用中所运用。朴素贝叶斯算法是基于这样一个简单的假定:即分类特征属性之间都是条件独立的。用权值的概念表示就是各个属性之间的权值都是相等的,不存在差异。但是在应用环境中,特征类属性之间的关系很少是独立的,不满足实际的需求。针对这种情况,国际上很多学者都对此提出了各自的解决方案,比如,学者Zhang Harry提出了根据属性的重要性给不同属性赋不同权值的加权贝叶斯WNB(Weighted Native Bayesian),他给出了爬山算法和Monte Carlo技术确定权值的加权朴素贝叶斯算法,这些算法确实有了很大的改进,但是对于大数据集,朴素贝叶斯在整个训练集上,分类性能并不能得到很大的提高。我们期望能在局部的数据集上得到一定的释放。

本文通过对K-近邻法的深度研究,综合考察了朴素贝叶斯的分类算法的特点,通过K-近邻法先对测试样本分类,然后在测试的实例领域内构建贝叶斯分类器。提出了基于K-近邻法的局部加权朴素贝叶斯分类算法,并通过实验数据证明了该算法的合理性、可靠性,最终提高了分类的准确率。

1 K-近邻法的相关概念

K-近邻法是一种常用的基于距离的度量方法。训练样本是n维的数值属性描述。每个样本是n维数值空间中的一个点。所有的训练样本都存放在n维模式空间中。当给定一个未知样本时,K-近邻法搜索整个模式空间,找出最近接近未知样本空间的k个训练样本。这k个训练样本就是未知样本的k个“近邻”。“近邻”之间的定义是用欧几里德距离定义,欧几里德距离定义是这样定义如下:若空间中存在两个点x={x1,x2,…,xn},y={y1,y2,…,yn},那么这两个点的距离是:

$d (x, y) = \sqrt{\sum_{i = 1}^{n} (x_{i} - y_{i})^{2}} (1)$

在比较距离时,我们不必计算平方根,直接使用平方和来比较就可以。在使用该欧几里德距离函数来判断训练集中的哪个实例与一个未知的测试实例最靠近时,我们一旦找到最靠近的训练实例时,那么最靠近实例所属的类就被预测为测试实例的类,未知样本被分配到k个最邻近者中的最公共的类。当k=1时,未知样本被指定到模式空间中与之最邻近的训练样本类。

2 朴素贝叶斯分类器

贝叶斯分类是基于贝叶斯公式的,即:

P(HX)=P(XH)P(H)/P(X) (2)

其中P(XH)代表假设H成立的情况下,观察到X条件概率。P(H)是先验概率,或称H的先验概率,表示在任何数据样本出现证明之前假设H的概率。P(HX)是后验概率,或称条件下H的后验概率。朴素贝叶斯的分类说明步骤如下:

(1) 把每个数据样本数值化,用一个n维特征向量X={x1,x2,…,xn}表示样本属性的n个度量。

(2) 假定有m个类C1,C2,…,Cm。给定一个待分类的样本X,根据贝叶斯定理可得样本X的概率为:

P(Ci $X) = \frac{Ρ (X | C_{i}) Ρ (C_{i})}{Ρ (X)} (3)$

(3) 由于P(X)对所有类都是常数,即只需P(XCi)P(Ci)最大。如果类的先验概率未知,则通常这些类是等概率的。即P(C1)=P(C2)=…=P(Cm)所以只需P(XCi)为最大。

(4) 为了计算P(XCi),我们通常做类条件独立的朴素假定。给定类的标号,假定属性值条件相互独立,则:

P(X $C_{i}) = \prod_{k = 1}^{n} Ρ (X_{k}$ Ci) (4)

即概率P(X1Ci),P(X2Ci),…,P(XnCi)由训练样本估计,其中:

a) 如果Ak是分类属性,则:

P(XkCi)=Sik/Si (5)

其中Sik是在属性Ak上具有值Xk的类Ci的训练样本数,而Si是Ci中的训练样本数;

b) 如果是连续属性,则通常假定该属性服从高斯分布。因而:

P(Xk $C_{i}) = g (x_{k}, u_{c i}, σ_{c i}) = \frac{1}{\sqrt{2 π} σ_{c i}} e^{\frac{(x - u_{c i})^{2}}{2 σ_{c i}^{2}}} (6)$

其中给定类样本的Ci的训练样本属性值Ak的值,g(xk,uci,σci)是属性Ak的高斯密度函数,而uci,σci分别为平均值和密度差。

(5) 对未知样本X分类,计算P(XCi)P(Ci),比较P(XCi)P(Ci)与P(XCj)P(Cj),如果P(XCi)P(Ci)>P(XCj)P(Cj),则X被分到Ci类中,反之则分到Cj类中。

3 K-近邻局部加权朴素贝叶斯分类算法

K-近邻局部加权的朴素贝叶斯K-LWNB(K-Locally Weighted Naive Bayes)。它首先应用k-近邻算法找到测试实例的k个邻居,然后应用线性方法来给每个邻居加权,最后在加权后的邻域内构建朴素贝叶斯分类器。K-LWNB算法于K-近邻算法一样是一种k相关的学习算法,要求用户在使用的时候自己认为地输入学习参数k,并且k的取值在一定程度上影响了它的分类性能。所以对于k的选择是相当重要的。本文提出了一种选择邻域大小的朴素贝叶斯模型,该模型为每一个测试实例在具有不同大小k值的数值邻域上学习一组朴素贝叶斯分类器,然后在其中选择一个最高分类准确度的朴素贝叶斯器来分类测试实例。在设计具体算法的时候,我们输入的数据包括有:领域的最大值Kmax、领域最小值Kmin以及训练实例集T;算法输出的数据就是Kbest;

具体算法伪代码描述如下:

4 实验结果

为了验证该算法的有效性,对该算法进行了实例的有效测试,实验中所选用的所有数据都来自于UCI公共数据库。本实验从UCI公共数据库中挑选了十个数据集作为测试数据。这些数据集的基本信息如表1所示,在这些数据中,为了达到更为准确的结果,使用的所有数据的连续属性值都进行了离散化处理,并且实验采用的十次交叉验证法。实验所采用的软件平台是:Windows XP操作系统,weka3.5.8版本数据挖掘工具,硬件平台是:双核T2060 1.6G Hz CPU,2GB内存。

在本实验所用的数据实例中,实验结果表明K-LWNB算法的分类准确率要优于NB算法,在十个实例中,八个实例运行后的精度都要高于NB算法。算法通过计算每个数据集的不同属性值与类别之间的相关性,然后使用K-近邻法得出K个最优邻居,最后用线性的方法给这些邻居加权,即各个相关属性获得了加权系数。最后分类的时候对后验概率计算公式中的每个概率项进行加权修正并最终得出分类结果。从实验结果可以看出,使用K-LWNB算法对属性进行加权分类,更加有效地利用了样本数据信息和属性与类别间的关联性。但值得注意的是在十个实例数据分类中,有两个实例数据分类的准确率小于NB算法,分析发现,这两例实例数据条件属性比较多,K-LWNB算法分类能力与NB算法相比略有下降。可能是因为属性值过多,导致每个属性值所得的加权系数都比较小,而不能真正发挥出自己的作用,但这与理论分析是一致的,在一定的误差范围之内。另一方面就是在算法的运行时间上,K-LWNB算法由于要计算找K个领域,因此要高于NB算法,但不影响分类结果。综上所述,K-LWNB算法是有效的。

5 结语

条件独立性假设在很大程度上影响了朴素贝叶斯的分类性能,实际上,在现实的生产环境中,对于属性之间条件独立是很少的。但是,由于朴素贝叶斯对于条件独立性的属性分类又是极其优秀的。所以,针对这种情况,本文进行了算法的改进。从局部来释放这种条件独立性的假设,最后从实验得出的数据可以看出,该算法确实提高了分类性能。但是,由于无关属性在多数机器学习方案中存在负面影响,通常在学习之前先进行属性选择,只保留一些最为相关的属性,而将其他属性都去掉,选择相关属性最好的方法是人工选择,通过去除不适当的属性以降低数据的维数,能改善学习算法的性能。还能提高速度,即使属性选择可能会带来很多计算。更重要的是,维数降低形成一个更为紧凑、更易理解的目标概念表达式,使用户的注意力集中在最为相关的变量上。在这个算法中,前期实验准备也进行了人工属性选择,这样对整个算法的执行效率就更为准确有效。最后,论文中用UCI数据库中的10数据集作为测试数据,通过实验比较了朴素贝叶斯分类算法与K-近邻局部加权的朴素贝叶斯分类算法的分类性能,实验结果表明,使用K-近邻局部加权的朴素贝叶斯算法在一定的条件下,分类性能有了明显的提高。

参考文献

[1]Hall M.A decision tree-based attribute weighting filter for Nave Bayes[J].Knowledge-Based Systems,2007,20(1):120-126.

[2]Zheng Z,Webb G I.Lazy learning of Bayesian rules[J].MachineLearning,2000,41(1):53-84.

[3]Kelly D,Tangney 13.Adapting to Intelligence Profile in an AdaptiveEducational Aystem[J].Interacting with Computers,2006,18(3):385-409.

[4]Harry Z,Sheng S.Learning Weighted Naive Bayes with Accurate Rank-ing[C]//Fourth IEEE International Conference on Data Mining(IC-DM’04),2004:567-570.

[5]Chickering DM.Learning Bayes networks is NP-complete[M]//Learn-ing from Data:AI and Statistics V.New York:Springer,1996:121-130.

[6]韩家炜.数据挖掘:概念与技术[M].北京:机械工业出版社,2001.

[7]蒋良孝.朴素贝叶斯分类器及其改进算法研究[D].中国地质大学,2009.

[8]秦锋,任诗流,罗慧.基于属性加权的朴素贝叶斯分类算法[J].计算机工程与应用,2008,44(6):107-110.

[9]邓维斌,王国胤,王燕.基于Rough Set的加权朴素贝叶斯分类算法[J].计算机科学,2007(2):204-206.

[10]程克非,张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真,2006,23(10):92-94.

[11]王双成,苑森淼.具有丢失数据的贝叶斯网络结构学习研究[J].软件学报,2004,15(7):1042-1048.

贝叶斯分类算法篇7

文本自动分类作为一项具有重大实用价值的关键技术,是信息检索、信息过滤、文本数据库、数字化图书馆等领域的技术基础。目前绝大多数搜索引擎及在线网络数据包甄别系统都是基于全文关键词检索的技术,尽管性能较高但准确度很低。

近年来,研究人员提出许多统计学习的方法和机器学习的方法进行文本分类,包括决策树、决策规则、最近邻方法、贝叶斯概率方法、感知机模型、神经网络、支持向童机方法等,并被广泛应用到许多领域中,比如专利的组织和归类、垃圾邮件的过滤、多义词的辨别、超文本分类等。基于自然语义分析的文本处理技术则不仅仅是一个全文检索的技术,还包括对构词、词法、语义的分析,这是文本分析甄别技术的发展方向。

本文在分析和总结文本分类中各个关键技术的基础上,着重研究了几个不同的特征选择方法,讨论了贝叶斯分类方法的原理、特点和性能后,根据文本分类的需要,提出了一个基于贝叶斯方法的层次自动文本分类方法,并与改进的特征选择方法相结合,用Java语言实现一个文本分类系统。

1 特征选择贝叶斯文本分类算法设计

该系统将文本分类的工作周期分为离线训练(offline training)和在线分类(online classification)两大部分,其系统工作原理如图1所示。

离线训练过程实际之给定一些已分类的文本,经过中文分词等预处理和特征选择处理后以特征向量形式表示,由多个特征向量组成的特征向量集;再由特征选择,将选取的特征输入训练器得到分类器的参数的过程。在线分类过程实际输入一个新的文本Doc,应用分类算法模式同训练过程(贝叶斯分类器)得到的类别模式逐一比较,输出该文本的分类结果。

2 特征选择及提取

2.1 预处理

为减少冗余数据和噪声,改善文本表示的质量,通常在把文本表示为向量之前,要做好一些必要的文本预处理工作,将文本进行结构化处理、分词处理以及去除停用词处理等。

(1)中文分词

首先处理文本中的标点符号、数字和大小,把文本转换为一个只由词条和空格组成的小写(或者大写)字符串,通过分词技术将文本分成便于进一步处理的基本分析单位。

(2)取词根

将文本(或文本表征词典)中具有相同或相近含义的词合并成一个语义单位。在英文中指有着公共的词根,中文中同义词或者近义词。通过把它们看成是同一个词的不同表示形式,就能够在很大程度上减少文本向量的维数。

通常取词根有两种实现途径:基于规则的方法和基于词典的方法。基于规则的方法按照一定的规则逐个剥离各个单词的后缀,直到得到表明其基本含义的词根;基于词典的方法则是将所有含义相同的单词归为一类,然后编制成专门的同义词词典,供取词根时使用。

(3)将样本存入词典

样本是指剔除Stop-words,即那些没有语意贡献的词。将每个文档以BoG格式存储(BoG即将词以一定顺序排列),并对文档中每个词的频率进行统计。

通过以上几项的预处理工作,我们就可以把文本集合中的文本表示成特征向量的形式,使文本数据结构化,从而满足各种文本分类方法在文本表示形式方面的需要。

2.2 初步特征选取

对文本进行预处理结束后会产生原始特征集合,我们需要从中获得对分类有用的特征,组成新的特征集合,同时滤掉对分类效果不大的特征。对词典和表示成Bag of Words的文档进行预处理,共有两种类似的预处理策略可供选择。

(1)策略一,将词典中仅在1～3个文档中出现的词删除。策略二,将所有样本中出现总次数为1～5次的词从词典中删除。

(2)将BoG表示中对应的词和词频删除。

2.3 特征选择

选择那些对分类最有帮助的最优特征(词),即按照每一个词在分类中的贡献大小排序,那些在正样本和负样本中分布差异较大的词排在前面。选择排序后前N个特征(词),其余的词在词典(Vocabulary)和BoG表达式中删除。

特征空间的高维性和稀疏性是文本分类面对的最大困难,通过该函数从原始特征集合中选出与类别相关性较大的一部分特征,降低文本特征向量空间的维数和稀疏度,同时过滤文本特征空间中的噪声,从而提升文本分类算法的准确率和运行速度。

3 贝叶斯文本分类模型

3.1 分类模型

如何根据文本集合构造一个分类模型(也称为分类器),并利用此分类模型将未知类别文本映射到指定的类别空间是文本分类研究的核心内容。目前常用的文本分类方法有kNN、朴素贝叶斯、支持向量机、最大熵模型、决策树、粗糙集和人工神经网络等分类方法。贝叶斯模型是一种基于概率统计的分类方法,Bayes概率是观察者根据先验知识和现有信息,用概率的方法预测未知事件发生的可能性。

3.2 算法设计

算法如图2、图3所示。

4 小结

本文介绍了特征选择贝叶斯文本分类系统设计,在分析和总结文本分类中文本表示模型、文本预处理、特征选择、分类方法和分类性能评价的基础上,从特征选择和分类方法两个途径出发,将朴素贝叶斯文本分类方法与改进的特征选择方法有效结合起来,建立了一个分类模型,实现了一个文本分类系统。着重体现了贝叶斯分类算法设计思想和特征选择设计思想,并给出了数据库表结构的设计格式和训练算法、特征选择算法以及分类算法。

随着科学技术的发展,文本信息的存储结构越来越丰富,对文本表示模型和分类性能评价标准等问题的深入研究,能够使文本分类的应用领域更加的广泛。

参考文献

[1]LARKEY,L.S,"A patent search and classification system",[A]In Proceedings of DL-99,4th ACM Conference on Digital Libraries,Berkeley,CA,1999,pp.179-187.

[2]Androutsopoulos,I.,Koutsias,J.,Chandrinos,K v,et al.,"An experimental comparison of nave Bayesian and keyword based anti-spam filtering with personal e-mail messages",[A]In Proceedings of SIGIR-00,23rd ACM International Conference on Research and Development In Information Retrieval,Athens,Greece,2000,pp.160-167.

[3]Escudem,G,M'arquez,L.,and Rigau,Q,"Boosting applied to word sense disambiguation"??[A]In Proceedings of ECML-00,11th Euorpean Conference on Machine Leanring,Barcelona,Spain,2000,pp.129-141.

[4]Yang,Y.,Slattery S.,AND Ghani,R."A study of approaches to hypertext categorization",[J]In-tell,Inform.Syst.2002,18,2/3(March-May),pp.219-241.

[5]T.R.Bayes.An essay toward solving a Problem in the doctrine of chances[M].PhilosoPhical Transactions of the Royal Society(London),1763,53:370-418.(Reprinted in Biometrika,1958,45:293-315).

贝叶斯分类算法篇8

垃圾邮件存在于互联网中占用大量的传输、存储和运算资源, 造成巨大的资源浪费;对信息安全系统也构成了一定程度的威胁;浪费用户的时间、精力和金钱, 损害了用户的利益。因此正确识别垃圾邮件显得尤其重要。常见的垃圾邮件过滤技术:邮件发送认证技术仅仅保证了合法用户发送邮件;黑白名单技术, 邮件特征过滤技术, 关键字过滤技术仍然具有一定的实用价值, 但是误判率都较高。

贝叶斯算法具有学习功能, 其准确程度能够随着学习次数的增加而不断提高。但传统的贝叶斯分类算法实现过于复杂, 把基于贝叶斯分类算法的垃圾邮件识别过程移植到云计算平台上, 通过Map Reduce编程模型实现, 充分利用云计算平台的高效的数据存储能力和处理能力, 实现对垃圾邮件的智能、高效过滤。

2. Hadoop框架

2.1 HDFS简介

Hadoop分布式文件系统 (HDFS) 适合部署在廉价的机器上应用于大规模数据集上, 具有高容错性, 高吞吐量的特点。HDFS放宽了可移植操作系统接口的要求, 实现以流的形式访问文件系统中的数据, HDFS框架如图1所示。

Name Node维护名字空间, Data Node存储数据块。一个数据块在多个Data Node中有备份;而一个Data Node对于一个块最多只包含一个备份。Data Node定时和Name Node通信, 接受Name Node的指令。Data Node和Name Node建立连接以后, 就会不断地和Name Node保持心跳。Data Node可作为服务器接受来自客户端的访问, 处理数据块读/写请求。Data Node之间还会相互通信, 执行数据块复制任务, 同时, 在客户端做写操作的时候, Data Node需要相互配合, 保证写操作的一致性。

2.2 Map Reduce简介

Map Reduce是一种编程模型, 适用于大规模数据集的并行运算。Map Reduce任务过程被分成两个处理阶段:map阶段和reduce阶段, 每个阶段都以键/值对作为输入和输出, 可选择他们的类型。但reduce阶段的输入类型必须与map阶段的输出类型相匹配。控制作业执行过程的是两类节点:Job Tracker和Task Tracker。Task Tracker运行自己的任务, 并且将运行的进度报告给Job Tracker。Job Tracker负责调度, 记录各个任务的进度情况, 若发现有任务失败的, 在其他的Task Tracker节点上重新调度该任务。一个Map Reduce job (作业) 通常把输入的数据集切分为若干个独立的数据块, 由map任务 (task) 以完全并行的方式处理。框架会对map的输出先进行排序, 然后把结果输入给reduce任务。作业的输入和输出都会被存储在文件系统中, 原理如图2所示。在Hadoop平台上, Map Reduce框架和HDFS是运行在相同节点上的, 即存储节点和计算节点在一起, 降低了网络传输量、网络延迟, 提高了整体的网络带宽利用率。

3. 贝叶斯分类算法在垃圾邮件过滤中的应用

3.1 数据准备

本文使用向量空间模型表示法将文本转换为计算机可识别的特征。可将文本Mail分词后表示为如下向量形式:M= (w1, w2, …wk…wn) M= (w1, w2, …wk…wn) (wkwk为第k个特征项的权值, 本文使用权值函数为TFIDF函数) 。为了提高过滤的准确率和效率, 在将文本表示成向量前, 可采用停用词表、稀有词处理、单词归并、同根词处理等方法去除噪声。

3.2 朴素贝叶斯分类模型

3.3 朴素贝叶斯算法的Map Reduce实现

邮件分类器的设计分为两部分:训练过滤部分和实时过滤部分, 如图3所示。

本文采用两轮Map Reduce的方法, 如图4所示。第一轮Mapper对邮件进行分词和去除噪声。每个map接收一个邮件数据块, 以作为输入键值对, 对每个数据块进行分词, 映射到键值对, 并作为中间结果输出。每个Reduce函数接收具有相同Key值的中间结果, 合并value值, 得到各词条的数量统计, 分别计算各词条的概率, 输出结果为键值对。产生相应分词的计数结果文件。

第二轮Map阶段主要转换格式为:。拆分输入信息Key得到邮件的标识, 并以此做输出的Key, 在系统对Key操作过程结束后, 一条邮件的各个分词便会集中一块, 然后使用第二轮Reduce过程中进行规约操作。Reduce阶段运算相应的结果, 输出格式为, 如果Value值为T则表示是正常邮件, 否则为垃圾邮件。

4. 结果分析

本文所用样本部分来自CCERT (中国教育和科研计算机网紧急响应组) Data Sets of Chinese Emails, 该样本集邮件均只保留了邮件的纯文本部分, 并将邮件头也以文本形式保留。另外包含个人收集的邮件, 包括私人邮件, 各种公司、产品、广告、服务、营销邮件, 及一些论坛上的垃圾邮件等。

实验评价标准:垃圾邮件查准率, 垃圾邮件召回率, 全部邮件判对率。由表1可以看出贝叶斯邮件过滤算法在传统分布式并行计算模型和基于Hadoop的Map Reduce模型上的实现在邮件过滤准确性上的效果相当。

另外, 单机环境的加速比:1.075, 云计算环境的加速比为:1.306。其加速比方面云计算环境有一定的优势。但云计算在编程实现和系统扩展上优势更为明显, 不用考虑线程之间的同步、互斥、并发等问题;且系统扩展仅需增加新的机器, 而传统并行系统扩展则相对麻烦。

5. 总结

经实验验证, 垃圾邮件过滤系统中应用贝叶斯分类算法具有较高的性能与准确率;另外实验还证明了贝叶斯分类算法在云计算环境中的实现相比传统式的实现方式有编程实现简单和系统扩展容易的优势。

摘要：为了抵制垃圾邮件对互联网及其用户造成的严重不良影响, 本文采用高效的贝叶斯分类算法, 基于hadoop平台实现垃圾邮件的过滤系统, 克服了传统并行系统在编程实现和系统扩展上的不足, 充分利用云计算环境优势, 使系统实现简单, 扩展容易, 性能提高;并做了相关的试验, 验证了设计理论。

关键词：垃圾邮件,云计算,贝叶斯分类,MapReduce,HDFS

参考文献

[1]Jiawei Han.Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2006.

[2]Tom Wbite.Hadoop权威指南[M].北京:清华大学出版社, 2011.

[3]朱杰.基于云计算及贝叶斯算法的垃圾短信过滤技术研究与实现[D].电子科技大学, 2010.

[4]曾青华.面向海量邮件过滤的云计算技术研究[D].南京航空航天大学, 2012.

[5]杨际祥.并行与分布计算负载均衡问题研究[D].大连理工大学, 2012.