加权粗糙朴素贝叶斯算法范文

《计算机应用研究杂志》2015年第五期

1相关研究

朱敏等在文献[7]中采用粗糙集来生成朴素贝叶斯网络预测模型的网络结构和各节点的条件概率表，有效去除了样本数据集中的冗余属性，使得朴素贝叶斯算法更加简洁有效；孙艳等在文献[8]中首先利用粗糙集技术得到网页分类决策的属性约简表，然后通过朴素贝叶斯算法进行分类过滤，降低了系统开销，且过滤准确度有明显提高；王纯子等在文献[9]中在基于贝叶斯理论的网络攻防对峙模型中引入粗糙集技术，提高了该模型对冗余信息的处理性能，有效缩减了博弈分析中策略空间的规模。在上述文献中，通过在贝叶斯算法中引入粗糙集技术，有效消除了冗余属性，降低了计算复杂度，并使贝叶斯算法的分类准确度大幅上升，但是它们局限于在属性约简后直接使用朴素贝叶斯算法对样本集进行分类，而没有尝试将粗糙集技术和加权朴素贝叶斯模型进行结合。Orhan等人在文献[10]中采用最小二乘法确定目标函数中的权向量，并以该权向量为依据，为各条件属性赋予相应的权值，使算法的复杂度有所简化，但同时降低了贝叶斯分类器的准确性；邓维彬等在文献[11]中将条件属性与决策属性之间的互信息作为衡量条件属性在分类过程中重要程度的标准，并以两者之间互信息的数学期望作为条件属性的权值，在一定程度上优化了朴素贝叶斯分类器的分类性能；WuJ等在文献[12]中采用MarkHall所提出的加权思想作为目标函数，并利用差分进化法获取最优权向量，最终建立加权朴素贝叶斯模型，使贝叶斯分类器的分类准确性有所提升；TaheriS等在文献[13]中通过基于准割线法的局部优化技术为条件属性确定最优权值，实验结果显示最终的分类性能较之朴素贝叶斯模型有一定程度的提高；EndoT等在文献[14]中，在以往将Shannon熵做为权值设定标准的加权朴素贝叶斯模型基础上对其进行扩展，改为以包含参数的Renyi熵来确定条件属性的最优权值，并通过对参数的调控对分类精确度进行优化，为加权朴素贝叶斯模型的研究提供了一个新的思路。

上述加权朴素贝叶斯模型均在不同程度上提高了朴素贝叶斯算法的分类性能，但是该类传统的加权方法局限于将权值作为对条件属性预测能力的描述，权值的大小完全取决于衡量条件属性的权重时所选择的方法，这在某些情况下会严重影响到朴素贝叶斯方法最终的分类准确性。例如：假设两个条件属性ix和i1x之间具有强烈的相互作用，不满足条件独立性假设，为了最大程度上保证朴素贝叶斯方法的准确率，遵循“加权平均”的思想，应该为ix和i1x赋予较低的权值，将它们在分类过程中的影响进行相应降低；但是若ix和i1x在某种衡量权重的方法（例如互信息）的度量中得值均较高，遵照“预测能力强则权值较高”的原则，它们依然会被赋予较高的权值，其在分类过程中的影响依然会被相应放大，反而对最终分类结果的准确性增加负面影响。因此，不同于传统加权方法“预测能力越强权值越高”的设定标准，本文认为权值最重要的作用不在于对条件属性在分类过程中的预测能力加以描述，并据此对其在分类过程中的作用进行相应放大或缩小，而在于当条件属性之间存在违反条件独立性假设的情况时，最大程度上减少该类情况对分类准确性的影响，确保朴素贝叶斯分类器的分类性能。综上所述，本文提出一种新型加权粗糙朴素贝叶斯方法，首先利用粗糙集技术对待分类样本进行属性约简，获得彼此相互独立的核心属性；然后基于约简后得到的最简属性子集，以整个测试数据集|D|作为出发点，以最大化数据集的条件似然估计为标准，从整体层面上对条件属性设定最优权值。最终获得一种新型加权粗糙朴素贝叶斯模型对数据集中所包含的对象进行分类判断。

2粗糙集理论及信息约简

2.1粗糙集相关定义定义1粗糙集理论中一个知识系统S可以表示为SU,R,V,F，其中U是对象的集合，也称为论域，RCD是属性集合，子集C和D分别称为条件属性集和决策属性集，{|}aVVaC是属性值的集合，aV表示属性a的值域，f:URV是一个信息函数，指定U中每一个对象x的属性值.

2.2基于粗糙集的属性约简设知识系统SU,R,V,F中RCD，则知识系统S可以通过TU,R,CD加以表述，TU,R,CD称作2.2基于粗糙集的属性约简设知识系统SU,R,V,F中RCD，则知识系统S可以通过TU,R,CD加以表述，TU,R,CD称作决策系统，简称决策表。如表1所示，就是决策表形式的一个知识表达系统。如果从分类系统的条件属性集中去掉某些属性并不影响分类效果，则称这些属性为冗余属性，可以将其从属性集中删除。而属性约简就是从原有的属性集出发，以分类效果为依据消除冗余属性，最终获取分类系统的最简属性子集。本文通过Skowron差别矩阵和属性选择的约简方法[16]对测试数据集进行属性约简.

3朴素贝叶斯分类模型

利用粗糙集技术对决策表进行属性约简后，条件属性集的维度得到大幅降低。根据前文对决策表约简后得到的属性约简表，进一步通过新型加权方法为条件属性赋予相应的权值，最终获取一种新型加权粗糙朴素贝叶斯模型对数据集所包含的对象进行分类。

3.1朴素贝叶斯分类算法朴素贝叶斯分类算法以贝叶斯决策理论为基础，在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公示对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。

3.2加权朴素贝叶斯分类模型朴素贝叶斯算法以条件独立性假设为基础，但该假设在实际应用中通常并不成立，因此有学者提出了条件属性权重法，即为不同的条件属性分别赋予对应的权值，将朴素贝叶斯模型扩展为加权朴素贝叶斯模型.在加权朴素贝叶斯模型中，最关键的步骤在于如何确定条件属性所对应的权值。传统的加权方法以单个的条件属性作为出发点，以条件属性预测能力的大小为标准对条件属性设定权值。如本文相关研究部分所述，该类方法在某些情况下反而会对最终的分类结果产生负面影响。因此，本文在为条件属性设定最优权值的过程中，不再着眼于根据条件属性预测能力的大小对其在分类过程中的作用进行相应放大或缩小，而是以整个数据集|D|作为出发点，以最大化数据集的条件似然估计为标准对条件属性设定权值，从最大程度上减小由于条件属性不满足条件独立性假设对分类结果造成的不良影响。为条件属性计算最优权值的大致流程如下.

4实验结果与分析

朴素贝叶斯分类器（NaïveBayesianClassfier,NBC）在垃圾邮件过滤、模式识别、入侵检测等多个领域被广泛应用，为了验证本文所提出的新型加权粗糙朴素贝叶斯方法的正确性和实用性，本文选择在垃圾邮件过滤领域对该方法加以实际应用，并对实验结果进行相关分析。本文所有实验均在WindowsXP下，硬件配置为Pentium42.3GHzCPU，内存4GB，硬盘500GB，以MATLAB8.0为实验环境。邮件样本来自中国教育和科研计算机网紧急响应组(CCERT)提供的中文邮件样本集(CDSCE，CCERTDataSetsofChineseEmails)，该样本集包含正常邮件9272封，垃圾邮件25088封。从中随机抽取5500封邮件构建邮件样本库，其中包含垃圾邮件3000封，正常邮件2500封。实验方法采用“十字交叉验证法”，并以召回率、正确率和精确率作为过滤器评价标准.综合上述实验结果可知，（1）使用粗糙集技术对邮件样本进行属性约简后，在三个评价标准上NB算法都可以更快地达到峰值，且曲线变化平缓，无明显波动。证明基于粗糙集的属性约简在不影响最终分类结果的前提下去除了冗余属性和噪声干扰，优化了分类性能；（2）MIWNB和REWNB算法在召回率上分别比NB算法提高了1.63%和0.9%，在精确率上分别比NB算法提高了0.61%和1.87%，在准确率上分别比NB算法提高了1.32%和1.85%。就分类性能而言，以条件属性的预测能力为标准设定权值的加权朴素贝叶斯模型只是略优于朴素贝叶斯模型；（3）RSBN和RSABD算法同样采用了粗糙集技术和朴素贝叶斯方法相结合的策略，但它们局限于在属性约简后直接使用朴素贝叶斯算法对样本集进行分类，而没有尝试将朴素贝叶斯模型进行加权处理。在召回率上比MIWNB和REWNB算法的平均值分别提高了1.3%和0.53%；在精确率上比MIWNB和REWNB算法的平均值分别提高了0.71%和1.41%；在准确率上比MIWNB和REWNB算法的平均值分别提高了1.56%和1.38%。虽然相对于MIWNB和REWNB算法，在分类性能上有所提升，但总体提升幅度不大；（4）本文提出的NWRNB算法由于以最大化数据集的条件似然估计为标准，得到的（近似）全局最优权向量更趋合理，在召回率上比NB算法提高了5.5%，比MIWNB和REWNB算法的平均值提高了6.08%，比RSBN和RSABD算法的平均值提高了5.02%；在精确率上比NB提高了7.32%，比MIWNB和REWNB算法的平均值提高了4.23%，比RSBN和RSABD算法的平均值提高了3.35%；在准确率上比NB算法提高了6.42%，比MIWNB和REWNB算法的平均值提高了4.84%，比RSBN和RSABD算法的平均值提高了3.37%；极大地提高了朴素贝叶斯模型的分类性能。

5结束语

本文针对待分类数据集中存在冗余属性以及传统加权朴素贝叶斯模型没有从整体层面上考虑权值对最终分类结果的影响的问题，提出一种新型加权粗糙朴素贝叶斯分类方法。在利用粗糙集技术对样本进行属性约简，获取最优条件属性子集的基础上，以最大化数据集的对数条件似然估计为标准设定权值，构造加权朴素贝叶斯分类模型。通过在垃圾邮件过滤领域对该方法进行验证，朴素贝叶斯分类器的分类效率得到有效提高，而且分类性能更加优越。证明本文所提出的方法不仅可以在不影响最终分类结果的前提下消除冗余属性，而且新型加权方法所获取的（近似）最优权值较之传统加权方法更加合理。除了条件似然函数（Conditionalloglikehood）以外，其它的一些函数也可以作为获取（近似）全局最优权向量的目标函数。比如在支持向量机（SVM）中常用的铰链损失函数（HingeLoss）以及在逻辑回归算法（LogicalisticRegression）中常用的对数损失函数（LogLoss）等，而且这些函数均有其特有的优点，因此，下一步的研究工作将是通过上述方法获取（近似）全局最优权向量，并与条件似然函数进行对比。

作者：王辉 黄自威 刘淑芬 单位：河南理工大学 计算机科学与技术学院 吉林大学 计算机科学与技术学院