基于泊松分布的加权朴素贝叶斯文本分类算法

赵博文,王灵矫,郭 华

(湘潭大学 信息工程学院,湖南 湘潭 411105)

0 概述

朴素贝叶斯(Naive Bayes,NB)算法作为目前研究者较为关注的一种机器学习算法[1-2],具有简易和高效的特点,应用于文本分类[3-4]、文字识别和图像识别等诸多领域时表现出优越的性能。但该算法以各个属性独立作为假设,其在文本分类中的运算精确度不及K-最近邻(K-Nearest Neighbor,KNN)[5]算法和支持向量机(Support Vector Machine,SVM)[6]算法,因此,许多研究者尝试改进朴素贝叶斯算法,实现其在文本分类领域的成功应用。

文献[7]提出多项式朴素贝叶斯和贝叶斯网络相结合的算法模型,通过考虑特征词之间的属性关联提升了分类效果。文献[8]提出一种基于全局特征提取的文本分类策略,通过新颖的特征提取方式改善了算法性能。文献[9]提出在决策树中每个叶节点加入朴素贝叶斯算法的一种构建朴素贝叶斯树的方法,提高了分类精确度,但同时增加了算法时间开销。文献[10]提出一种利用特征权重对朴素贝叶斯算法中的条件概率进行相关评估的深度特征权重朴素贝叶斯算法,改善了分类器性能。文献[11]提出了一种基于属性频率的朴素贝叶斯算法,利用可辨识矩阵对不同属性赋予权值,取得了良好的分类效果。文献[12]同样依据特征提取的原则设计一种基于属性删除方法的选择贝叶斯分类器。

综合分析现有的研究成果可知,上述改进的朴素贝叶斯算法可完成文本分类任务,然而仍然有很多改进方式未被挖掘,如泊松分布是一种具有良好预测效果的随机过程,但目前较少有将其结合传统朴素贝叶斯算法应用于文本分类的研究。

由于泊松随机变量对文本特征词具有很好的兼容性,因此本文提出一种新型朴素贝叶斯文本分类算法。将泊松分布的概率函数引入朴素贝叶斯算法的推导过程中,达到对特征词进行加权的效果,同时应用信息增益率作为特征词权重,消除属性重要程度相等的假设对最终分类效果的影响,从而实现文本分类精确度、召回率和F1值性能的提升。

1 朴素贝叶斯分类器

朴素贝叶斯分类器是一种基于概率统计的学习方法,应用于文本分类需符合贝叶斯假设,且假设各特征之间相互独立[13]。在已知类别的先验概率和该类中每个特征取值条件概率的情况下,以贝叶斯全概率公式为基础,计算出待分类文本属于某个类别的条件概率,并选择条件概率最大的类别作为该文本的分类[14]。

假设共有m个类,类别集为C={C1,C2,…,Cm},根据贝叶斯理论,文本di的最佳类别属于具有最大后验概率的类别Cmax:

(1)

(2)

则式(1)可表示为:

(3)

通过zjc的推导策略实现朴素贝叶斯文本分类,将每篇文本定义为一个|V|维向量{w1,w2,…,w|V|},其中,wk(k=1,2,…,|V|)表示文本的特征项。基于属性独立性假设,zjc可以表示为:

(4)

在式(4)中,p(wk|Cj)可以通过下式得到:

(5)

(6)

为避免式(5)、式(6)计算中出现零概率问题,进行如下拉普拉斯平滑处理[15]:

(7)

(8)

其中,参数θ值取0.01,|V|为特征项个数。

在对朴素贝叶斯分类算法的改进方面,文献[16]提出一种基于卡方统计的属性加权贝叶斯分类算法RW,C-MNB。通过引入RW,C进行属性评估,RW,C表示属性和类别之间的正负依赖性,当RW,C>1时,属性W和类别C为正依赖关系,否则为负依赖。同时只将具有正依赖关系的RW,C,作为该属性条件概率的权重,否则权重为1。由此,正依赖属性和负依赖属性的分类贡献拉开了差距,在一定程度上优化了分类模型。

在对分类模型的改进方面,文献[17]提出一种基于CFS属性加权的贝叶斯分类模型CFSNB,该文设计基于相关性的属性选择方法CFS,并认为一个优良的属性子集S应具备以下特点:在属性之间具有低相关性的同时,属性与类别之间具有高相关性。文献[17]的设计思想是保留训练数据集的所有属性,对于CFS选中的属性集合赋予较大的权重,其余的属性集合赋予较小的权重,将选中的属性权重设为2,未被选中的属性权重设为1。为充分利用权重信息,该文不仅将权重用于预测文本的类别公式中,同时还将权重运用到条件概率的评估中,可以看出,将CFS属性选择方法变为CFS属性加权方法,可保证数据完整性,提升分类性能。

尽管上述朴素贝叶斯分类器较传统分类器性能有所改善,但仍然不能满足目前文本分类任务的需求。本文将泊松分布和信息增益率加权的方法应用到朴素贝叶斯模型的推导过程中,使朴素贝叶斯算法性能得到进一步提升。

2 改进的朴素贝叶斯文本分类算法

泊松分布被广泛应用于较多领域[18-19],但较少应用于文本分类,鉴于文档中特定词语的出现频率可以用泊松模型来描述,本文提出基于泊松分布的特征加权朴素贝叶斯算法PWNB,将泊松分布与传统朴素贝叶斯结合应用于文本分类,根据泊松随机变量k的物理意义,将k作为特征词权值引入算法推导过程,并通过信息增益率对特征词加权,增强了算法的灵活性,一定程度上消除了属性独立性假设带来的影响。

泊松分布的概率函数为:

(9)

其中,参数λ、k分别表示随机事件单位时间(空间)内的平均发生率和事件特定时间(空间)内发生的次数。

假设文本di由多元泊松分布模型生成,表示为一个随机分布的词向量,则向量元素对应于泊松分布中的随机变量Xki,即将文本特征词作为泊松随机变量Xki,文档中特定词频仅局限于某一文本,不能达到全局优化的效果,由于将权重代入k值可避免文本特征词属性重要性一致的假设,因此将文本di表示为如下泊松分布模型:

p(di)=p(X1i=f1i,X2i=f2i,…,X|V|i=f|V|i)

(10)

式(10)中各个变量Xki之间相互独立,则文本di的先验概率可表示为:

(11)

根据式(10),p(Xki=fki)可表示为:

(12)

因此,式(2)中函数zjc可由式(11)、式(12)计算得到:

(13)

其中,λkc、μkc分别对应于Cj类的泊松参数和除Cj类之外其他类别的泊松参数。根据泊松参数的定义,λkc、μkc分别表示Cj类别的文本中特征词wk和其他类别的文本中特征词wk出现的平均次数。

朴素贝叶斯文本分类算法认为所有特征词对文本分类的重要性相同,但每个特征词的重要性实际上是不一致的。如果一个特征词在某一类文本中频繁出现而在其他类别中很少出现,则认为该特征词区分度较高,对该类别重要程度也较高。信息增益率是表示特征词在所有文本集中的信息增益[20],即该特征词所包含的信息量,根据特征词重要程度的不同,以信息增益率赋予其不同的权值,采用信息增益率加权的方法体现特征词的全局重要程度,对文本分类将实现更高的精确度。

给定训练集D={d1,d2,…,dn},i=1,2,…,n,特征词wk在训练集D中的信息增益率IIGR(C,wk)定义为:

(14)

其中,IIG(C,wk)表示特征词wk在训练集中的信息增益,H(wk)表示wk在训练集中的信息熵。信息增益的计算公式如下:

IIG(C,wk)=H(C)-H(C|wk)=

(15)

信息熵H(wk)计算公式如下:

(16)

通过计算所得的文本中各个特征词的信息增益率IIGR(C,wk),可将特征词wk的权重fki定义为:

(17)

结合上述过程,可得到式(3)的最佳分类类别。

针对传统朴素贝叶斯算法在文本分类中准确率较低的不足,本文提出新型朴素贝叶斯文本分类算法。在推导过程中融合泊松分布模型,由此引入特征权重项,并通过信息增益率进行特征加权,从而改善传统分类器性能。PWNB算法实现步骤如下:

步骤1定义泊松分布概率函数p(X=k)。概率函数的参数λ和k在物理意义上体现了随机事件的发生率,文本中特征词出现的随机性和不确定性符合泊松分布这一随机过程,用特征词发生率代替概率函数的λ参数和k变量时引入特征词权重,可以实现对算法性能的优化。

步骤2将文本di表示为泊松分布模型。首先将文本表示为向量形式,根据朴素贝叶斯文本分类算法基于属性独立性假设,文本中各个特征词wk(k=1,2,…,|V|)相互独立,将各个特征词代入泊松模型的k项,k值表示随机事件特定时间或空间的发生次数,映射为特征词的出现频率。为消除属性独立性假设对分类精度带来的影响,将各个特征词权重fwk作为k值嵌入泊松模型。

步骤3转化函数zjc。要得到测试文本的最佳分类类别,函数zjc的取值是关键,因此,将泊松模型表示的文本代入函数zjc进行运算转化,得到仅与泊松参数和特征词权值相关的函数式。

步骤4以信息增益率对特征加权。特征词信息增益率表示特征词在整个文本集中包含信息量的相对比例,特征词在训练集中信息增益率越高,表示其包含信息量越大,则该特征词的权重就越高,定义信息增益率对文本中各个特征词作加权处理,最后以式(17)中所得的平均信息增益率作为最终权值fk,将其代入步骤3得到的函数式zjc。

步骤5返回式(3)的最佳分类类别。

3 实验结果与分析

3.1 数据集

实验采用UCI KDD Archive的20-newsgroups英文文本数据集,该数据集是文本分类、文本挖掘和信息检索研究的国际标准数据集之一,包含从20个不同新闻组中收集的19 997篇新闻文本,涉及政治、科学、体育、计算机等20个主题,每个主题包含约1 000篇文档。实验选取其中10类数据:alt.atheism,comp.graphics,comp.os.ms-windows.misc,comp.sys.ibm.pc.hardware,comp.sys.mac.hardware,comp.windows.x,misc.forsale,rec.autos,rec.motorcycles,rec.sport.baseball。为方便实验结果的记录,将10类数据分别记为C1～C10,实验选取数据集的80%作为训练集、20%作为测试集,同时采用Python3.7编程,并在其开发平台PyCharm上运行测试。

3.2 分类性能评估

对文本分类效果的评估,通常使用3个性能指标,即准确率P、召回率R和F1值:

(18)

(19)

(20)

其中,A表示实际与PWNB算法所得di∈Cj的文本数量;B表示实际di∉Cj而PWNB算法所得di∈Cj的文本数量;C表示实际di∈Cj而PWNB算法所得di∉Cj的文本数量。准确率和召回率分别表示分类器分类的精确程度和分类器分类的完备程度,F1值为综合准确率和召回率之后的性能指标。

3.3 实验步骤与结果

实验步骤如下:

步骤1数据预处理。文本包含大量对分类无用的信息,会对分类效果产生干扰,因此,对数据集所有文本进行分词、去除停用词和标点符号等。

步骤2文本向量化。将文本转化为向量空间模型(Vector Space Model,VSM),将文本di表示为一个空间向量{w1,w2,…,w|V|},i=1,2,…,n,wk为特征词(k=1,2,…,|V|),|V|为特征词总个数。

步骤3特征选择。由于文本中包含海量的特征词,导致文本向量维度过大,也为运算带来不便,因此需要进行特征选择处理。计算每个特征词wk在训练集中包含的信息增益IIG(C,wk),并根据IIG值进行特征选择。

步骤4分类器构造。依据改进算法构造朴素贝叶斯文本分类器,并将通过K-fold交叉验证法测试分类器性能(K值取10),将测试结果与NB算法、KNN分类算法、SVM分类算法以及2种改进朴素贝叶斯文本分类算法RW,C-MNB和CFSNB的效果进行比较。

表1显示了PWNB算法与NB算法性能指标的详细数据对比,其中NB算法的准确率、召回率、F1值的均值分别为87.8%、87.7%、87.7%,PWNB算法的准确率、召回率、F1值的均值分别为91.5%、91.4%、91.4%,较NB算法均提升了3.7个百分点。为直观表达,绘制如图1所示的柱状图,显示PWNB算法和NB算法在各个文本类别下的F1值对比。可以看出PWNB算法相比传统算法在各类文本中的F1值均有所提升。由此可见,使用泊松分布和信息增益率加权结合朴素贝叶斯的PWNB算法,可使分类器性能得到大幅提升。

表1 PWNB算法与NB算法的分类性能对比

图1 PWNB算法与NB算法的F1值对比

表2显示了PWNB算法和其他多种算法的分类性能对比,包括NB、RW,C-MNB、CFSNB、KNN、SVM算法,其中:RW,C-MNB算法是基于卡方统计的属性加权朴素贝叶斯算法,其通过评估特征词和类别之间的正负依赖性改善分类器性能;CFSNB是基于CFS属性选择的属性加权朴素贝叶斯算法,其通过度量特征词和类别相关性的方法进而对特征词加权,改善了分类器性能。可以看出,相比上述2种改进算法,PWNB算法引入泊松随机过程,通过泊松参数对随机事件良好的预测效果优化朴素贝叶斯文本分类算法,同时使用信息增益率进行特征加权,每个特征词在文本中的重要程度都能在分类中体现,达到全局优化的效果。从实验结果可以看出,PWNB算法在准确率上相比RW,C-MNB算法和CFSNB算法分别提升了2.3个百分点和0.9个百分点,同时其分类性能接近KNN和SVM算法。

表2 6种算法与多种算法的分类性能对比

图2显示了各个算法的执行效率对比,其中PWNB、NB、RW,C-MNB、CFSNB、KNN、SVM算法的执行时间分别是24.8 s、21.3 s、24.4 s、25.8 s、103.1 s、118.2 s,可以看出,PWNB算法执行效率相比NB算法、RW,C-MNB算法、CFSNB算法基本在同等水平,而远超KNN算法和SVM算法,这源于朴素贝叶斯算法本身的简易性和高效性。

图2 6种算法的执行时间对比

综合上述实验结果可知,本文改进的朴素贝叶斯文本分类算法在保证原算法时间开销的基础上改善了分类器性能,可有效提高文本分类准确率。

4 结束语

朴素贝叶斯算法是一种重要的文本分类算法,但其分类准确率较低。针对此不足,本文提出基于泊松分布和信息增益率加权的文本分类算法。以泊松分布相关参数λ匹配特征词在某一类别文档中出现的平均次数,以k值匹配特征词在文本中出现的频率,并将其转换为由信息增益率计算而得的权值,即对特征词做加权处理,从而消除朴素贝叶斯算法中属性重要性一致假设造成的影响。实验结果表明,该算法能够在保证简单性和高效性的同时,提高文本分类的准确率。虽然本文算法在时间复杂度方面具有较大优势,但其准确率仍有可提升的空间,后续将针对此问题对算法做进一步改进。