第一作者:张伟(1987—),男,山西大同人,博士生.研究方向为数据挖掘和机器学习.email:15112102@bjtu.edu.cn.
朴素贝叶斯模型具有的简单性和有效性,使其在诸多问题领域表现出优良的性能,但其属性条件独立性假设在实际应用中难以成立.而属性加权是降低属性条件独立性假设对分类器性能影响的主要途径.传统建立在整个数据集上的单一全局模型忽略了每个测试实例所具有的特点,同时从整个训练集上学习到的属性权重并不能准确反映每个属性对待分类实例的影响.为此提出一种基于数据驱动的懒惰式局部属性加权方法,它在每个测试实例的近邻集合上学习属性权重,并通过最优化方法建立相应的局部属性加权朴素贝叶斯模型.实验结果表明:和当前常见的准朴素贝叶斯模型相比,本文模型具有较高的分类准确率.
Naive Bayes(NB) classifier has exhibited excellent performance on many problem domains due to its simplicity and efficiency. In reality the conditional independence assumption of Naïve Bayes isn’t always true. Attribute weighting is one of the most popular methods to alleviate this assumption’s influence on classification results. However, traditional classification models ignore characteristics of each test instance, and the weight vector learned from the whole training set failed to reflect each attribute’s contribution of distinguishing each test instance correctly. To this end, a data driven lazy learning locally attribute weighted naive Bayes model is proposed. The attribute weights for each test instance are learned from its neighborhoods, and learned weights are employed to build the locally weighted model by optimization method. Experimental results on benchmark datasets demonstrate that the proposed approach is more accurate than other classical classifiers.
朴素贝叶斯(Naive Bayes)是一种简单而且高效的分类模型, 它在属性条件独立性假设的前提下利用贝叶斯定理进行分类[1].NB模型的属性条件独立性假设在现实中难以成立, 原因主要有两个:1)对于给定的类属性, 属性之间并不总是相互独立的, 它们之间通常存在依赖关系; 2)数据集中的属性对于类属性归属的影响并不总是相同的, 如数据集中的冗余属性对类属性的归属没有影响.
为了弱化属性条件独立性假设的束缚, 提高NB的分类性能, 不同学者提出了多种改进方法.这些方法大致可以分为3类:
第1类称作准朴素贝叶斯, 准朴素贝叶斯的基本思想是在属性之间引入依赖关系来放松属性条件独立性假设, 这使得准朴素贝叶斯模型具有比NB更复杂的网络结构.由于和其他贝叶斯网络结构类型相比, 树形结构可以在多项式时间内被有效学习, 一种简单的做法就是将拓展结构限定为树形结构[2], 例如, 树增强型朴素贝叶斯分类器(Tree Augmented Naive Bayes, TAN)[3]和(Super Parent-TAN, SP-TAN)[4].
第2类方法通过属性选择或属性加权来提高NB的分类性能, 数据集中的冗余属性不仅增加了分类模型学习过程中的计算量, 同时还会降低分类的准确率, 所以属性选择经常作为提高分类器性能的方法[5, 6, 7].和准朴素贝叶斯方法相比, 属性选择不会改变NB模型的结构, 同时可以有效提高NB的分类性能[8, 9].但是实际中属性对类属性的归属的影响不同, 而属性选择不能区分不同属性在分类过程中的重要程度.
属性加权通常看作是比属性选择更一般化的方法, 不仅可以排除冗余属性, 还可以区分不同属性在分类过程的重要程度.NB模型的属性条件独立性假设本质上是假定了各个属性对类属性的贡献相同, 通过属性加权可以区分不同属性对类属性归属的不同影响.
使用属性加权来改善NB模型的性能, 其难点在于如何获得能够准确反映属性对类属性归属影响的权重[10, 11, 12, 13, 14].对于NB模型, 传统的属性加权方式主要采用不同的度量方式来增加强预测属性的属性权重同时减小弱预测属性的权重, 文献[10]使用属性和类属性的增益比作为属性权重.文献[11]用属性在决策树中的最小深度来为属性加权.近些年一些研究人员提出通过优化权重来整体改善分类器预测性能.文献[12]提出用局部优化算法求属性对于不同类属性的权重.文献[13]基于差分进化算法求属性权重.文献[14]通过优化算法求负条件对数似然或均方误差的最小值来设置属性权重, 这种方式不仅降低了违背属性条件独立性假设对分类模型的影响, 还使得分类器的整体性能得到改善.但这些属性加权方法都是从整个数据集合上学习属性权重, 这样的属性权重对于每个测试实例只在平均意义下是最好的, 并不能真实反映每个测试实例的属性对自身分类的重要程度.
第3类方法通过局部实例加权降低属性条件独立性假设对分类性能的影响.文献[15]将局部实例加权技术应用于NB模型, 为每一个测试实例基于加权近邻实例建立局部实例加权朴素贝叶斯(Locally Weighted Naive Bayes, LWNB)模型, 但仅对实例加权, 忽略了不同属性对分类性能的影响.
实际中同一属性对不同实例分类的贡献可能是不同的, 为了获得测试实例准确的属性权重, 本文作者将懒惰式学习方式和属性加权方法相结合, 提出在测试实例的近邻集合上学习测试实例的属性权重, 使得不同实例可能对应不同属性权重的局部属性加权朴素贝叶斯(Locally Attribute Weighted Naive Bayes, LAWNB)模型.本文使用优化算法求解测试实例的属性权重向量, 这样获得的属性权重不仅可以更准确的反映每个测试实例属性对自身分类的影响, 还可以用来整体改善局部分类模型的性能.实验结果表明本文方法获得的测试实例的属性权重和整个数据集上求得的全局属性权重相比能够更准确的反映测试实例属性对其自身分类的贡献, 同时可以显著提高NB模型的分类性能.
本文的主要贡献如下:1)针对全局属性权重不能准确反映每个测试实例属性对其自身类属性归属影响的问题, 提出了一种学习每个测试实例属性权重的方法; 2)不同于传统的基于加权近邻实例建立局部分类模型, 本文提出在测试实例的近邻集合上用优化算法学习每个测试实例的属性权重, 并建立局部属性加权模型.
本节对文中用到的定义、符号及一些背景知识进行介绍.
本文用符号
准朴素贝叶斯模型和NB模型都基于贝叶斯定理[1]为
网络结构上的差异使得式(1)具有不同的分解形式.基于属性条件独立性假设的NB有如下分解[1]
式中,
TAN, SP-TAN等准朴素贝叶斯模型分解形式
式中:
实例间的相似性是本文在近邻集合上学习测试实例属性权重的基础, 实际中有很多度量方式可用于度量实例间的相似性, 本文使用标准Euclidean距离函数度量实例间的相似性.
令
欧式距离的时间复杂度
为了研究测试实例属性对其自身分类的贡献, 本文提出了局部属性加权朴素贝叶斯模型.
为了避免零概率的出现, 采用文献[16]提出的M估计对先验概率和条件概率进行平滑处理.近邻实例集合上类属性
式中:
式中,
假设属性
式中:
文献[17]提出用最大条件对数似然(Conditional Log-Likelihood, CLL)来评价贝叶斯网络结构能获得更准确的类概率估计.因此, 本文尝试通过在测试实例的近邻集合上求最大条件似然对数的最大值来获得测试实例的属性权重向量w.本文在实例集合
其中
目标函数
基于目标函数和相应的梯度, 使用文献[18]的L-BFGS-M优化程序来求测试实例
算法1.AttributeWeights
输入:近邻实例集合
输出:测试实例属性权重向量wx.
01:用式(5)和式(6)计算数据集Dk(x)中的P(c)和P(ai|c)
02:将P(c)和P(ai|c)代入目标函数JCLL(w)的相关式(7)和式(9)
03:基于式(7)和式(9)用L-BFGS-M优化程序计算函数- JCLL(w)取最小值的解向量w
04:wx¬ w
05:return
在近邻集合上利用优化算法学习测试实例属性权重的算法的时间复杂度取决于优化算法求解过程的收敛速度, 而本文采用的优化算法是一种L-BFGS算法, 该算法比较适合在大规模数据集上进行计算, 它具有牛顿法收敛速度快的特点.
任意一个测试实例
满足条件
式中:
由于计算测试实例的每个类属性后验概率的式(10)中的分母都相同, 测试实例x的属性加权模型可简化为
式中
将每个测试实例的属性加权朴素贝叶斯模型称为LAWNB.算法2给出了建立LAWNB模型的一般过程.
算法2. LAWNB
输入:训练实例集合
输出:测试实例
01:从数据集
02:
03:根据式(11)计算各类属性
04:
05:return
算法2描述了为每个测试实例建立LAWNB模型的过程, 其中需要进行实例选择和计算测试实例的属性权重.这个过程增加了模型的计算量.获得属性权重后, 在近邻集合上为单个测试实例建立LWNB模型和NB模型的时间复杂度相同.此外, 较小的训练集合可以显著减少单个模型求属性权重的计算时间.因此, 当训练集规模较大时, 本文为单个测试实例建立模型的时间比全局属性加权(Weighting attributes to Alleviate Naive Bayes' Independence Assumption, WANBIA)模型的训练时间显著减少.本文LAWNB模型预测过程中需要存储训练集, 这使得本文算法的空间复杂度较高, 同时本文算法的时间复杂度和测试集的规模成线性关系.
实验运行环境的CPU为3 GHz, 内存为4 GB, 操作系统是Linux.本节在20个UCI的数据集[19]上对LAWNB模型性能进行评价.表1给出了实验数据集的内容.
下面分析和实验相关的一些预处理步骤.1)数值属性:本文的局部属性加权朴素贝叶斯模型不能处理数值属性, 使用文献[20]提出的监督属性离散化方法对数值属性进行离散化处理.2)缺失值:本文采用式(5)和式(6)中的方式处理缺失值.
本文模型在weka-3-8平台实现, 在每个数据集上进行10次10重交叉验证, 每个分类器都是在完全相同的交叉验证集合上进行训练和预测, 最后将获得的100个准确率的平均值作为分类器在数据集上的准确率.使用双尾假设t检验对每个数据集上LAWNB模型和对比模型的显著性进行分析, 显著性水平为0.05.
在表2中对20个数据集上的LAWNB模型和用于比较的模型的准确率情况进行了比较统计, 其中,
本文做两个实验, 第1个实验分析LAWNB模型准确率在20个数据集上随
本节对20个数据集上LAWNB模型的准确率随
1)有3个数据集sonar, autos和vowel上的准确率随
2)有2个数据集上的准确率有明显波动:glass上的准确率波动最为明显, 在
3)有15个数据集上的准确率随着
图2中给出了LAWNB模型在20个数据集上平均准确率随
基于以上分析, 可以得出结论:邻域越大并不意味着LAWNB模型的准确率越高, 本文提出的局部属性加权朴素贝叶斯模型偏好较小的邻域.考虑到文献[15]建立的局部实例加权朴素贝叶斯模型中取
LAWNB模型和LWNB模型相比, 在15个数据集上显著提高, 在4个数据集上没有显著不同, 只在1个数据集上较低, 而且在20个数据集上的平均准确率比NB模型高9.14%, 是本文所有对比模型中最大的, 实验结果表明局部属性加权是一种有效提高朴素贝叶斯性能的方式.
LAWNB模型与WANBIA模型相比, 在9个数据集上的分类准确率显著更高, 在7个数据集上没有显著不同, 在4个上显著较差, 其中数据集vowel上的准确率提高了33.2%, 在4个较差的数据集上准确率的差值都不超过2%.为了更直观地说明学习测试实例属性权重的意义, 本文从vowel集合中选择了3个实例, 其中WANBIA模型预测正确一个, 而LAWNB模型对3个实例的预测都正确.然后, 对两种模型计算出的属性权重进行了比较分析.
图3中给出了vowel整个数据集合上的全局属性权重和3个测试实例的属性权重, 其中dataset表示WANBIA模型在整个vowel集合上求得的属性权重, inst1, inst2分别表示用WANBIA模型预测错误的测试实例的属性权重, inst3表示两模型都预测正确的实例的属性权重,
从图3(a)和图3(b)中可以看出WANBIA模型预测错误的两个测试实例的属性权重向量和整个数据集合上的全局属性权重向量显著不同, 而WANBIA模型正确预测的一个测试实例的属性权重向量和全局属性权重向量相近, 同时从图3(b)中可以看出不同测试实例之间的属性权重也存在明显差异.图3表明从整个数据集合上学习到的全局属性权重有时并不能准确反映每个属性对测试实例分类的贡献, 这可能会导致一些实例的错误预测, 而表2中的实验结果进一步说明学习每个测试实例的属性权重可以用来改善分类器性能.
1)与LWNB模型相比, 本文提出的LAWNB模型在9个数据集上的准确率显著提高, 在8个数据集上没有显著不同, 在3个数据集上较差, 其中在ionosphere数据集上提高了6.22%, 在diabetes数据集上提高了4.87%, 最差的数据集是sonar, 准确率降低了8.75%.实验结果表明局部属性加权朴素贝叶斯模型的分类性能可与局部实例加权朴素贝叶斯模型相比.
2)与TAN模型相比, 有17个显著更好, 3个没有显著不同, 在audiology数据集上提高了24.99%, 在zoo数据集上提高了21.35%, 在glass数据集上提高了15.26%, LAWNB模型在20个数据集上的平均准确比TAN模型高5.6%, 这表明通过局部属性加权比通过简单的增加属性间依赖关系更有利于改善朴素贝叶斯的分类器性能.
3)与AODE模型相比, 有12个显著改善, 5个没有显著不同, 显著较差的有3个, 在数据集glass上准确率提高了9.75%, 在数据集audiology数据集上准确率提高了7.29%, 在数据集kr-vs-kp上准确率提高了6.73%, 最差的数据集breast-cancer上准确率降低了2.6%.
4)与WAODE模型相比, 显著改善的有10个, 没有显著不同的有5个, 显著较差的有5个, 在数据集glass上准确率提高了9.89%, 在数据集anneal.ORIG上提高了5.10%, 在数据集hypothyroid上提高了3.84%, 最差的数据集ionosphere上准确降低了3.67%.
与以上几种准朴素贝叶斯分类模型相比的实验结果说明:本文提出的局部属性加权是一种有效改善朴素贝叶斯分类性能的方式, LAWNB模型可以作为当前最先进的准朴素贝叶斯分类模型的一种有效替代.
3.5 7个模型的运行时间分析
本节在hypothyroid数据集上对7个模型的运行时间进行了分析, 将hypothyroid数据集等分为10个集合, 选择第1个集合作为测试集, 其他9个集合合并组成训练集, 在训练集上训练模型, 在测试集上进行预测, 取10次实验中模型运行时间的平均值作为模型的运行时间, 图4中给出了6个模型的运行时间随测试实例个数增长的变化趋势, 其中l = 0对应各模型在训练集合上建立模型的时间, 对于局部模型来说是建立第1个测试实例模型的训练时间.
从图4中可以发现懒惰式模型LAWNB和LWNB的模型运行时间随着测试实例数递增呈现出线性递增的趋势, 而全局模型的运行时间主要由模型的训练时间决定.因此, 当测试集超过一定的规模, 懒惰式模型的运行时间比全局模型更多.从图4中看出当测试实例数超过100后, 本文LAWNB模型的运行时间比其他模型更多.从图4中还可知为单个实例建立局部属性加权LAWNB模型所用时间比WANBIA模型的训练时间显著更少, 和NB、LWNB、TAN、AODE和WAODE模型的训练时间相近.对于较大规模的测试集, 懒惰式模型预测过程需要花费较多时间, 但懒惰式模型为深入研究每个具体实例提供了途径, 这是研究懒惰式模型的根本意义所在.
本文作者提出的LAWNB模型在建立过程中从测试实例的近邻集合上学习测试实例的属性权重, 然后对测试实例预测过程中的属性进行加权.通过在多个数据集上与当前常见的4种改进NB分类器对比, 实验结果表明:LAWNB模型不仅保持了NB模型的简单性, 还显著改善了其分类性能.
今后可考虑将本文所提出的LAWNB模型应用于贝叶斯网络和其他更多的实际应用问题中, 以解决属性重要程度的不准确度量对分类预测的影响.
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|