第42卷第2期2018年4月
北京交通大学学报
JO U R N A L O F B E IJIN G JIA O T O N G U N IV E R S rrY
Vol.4 2 No.2
Apr. 2018
文章编号：1673-0291 (2018)02-0011-08 DOI：10.1 1860/j.issn.l 673-029 1.2018.02.003
一种局部属性加权朴素贝叶斯分类算法
张伟，王志海，原继东，刘海洋
(北京交通大学计算机与信息技术学院，北京100044)
摘要：朴素贝叶斯模型具有的简单性和有效性，使其在诸多问题领域表现出优良的性能，但其属 性条件独立性假设在实际应用中难以成立.而属性加权是降低属性条件独立性假设对分类器性能影响的主要途径.传统建立在整个数据集上的单一全局模型忽略了每个测试实例所具有的特点，同时从整个训练集上学习
到的属性权重并不能准确反映每个属性对待分类实例的影响.为此提出一种基于数据驱动的懒惰式局部属性加权方法，它在每个测试实例的近邻集合上学习属性权重，并通 过最优化方法建立相应的局部属性加权朴素贝叶斯模型.实验结果表明：和当前常见的准朴素贝叶 斯模型相比，本文模型具有较高的分类准确率.
关键词：朴素贝叶斯；懒惰式；属性加权；局部加权
中图分类号：T P18 文献标志码：A
A locally attribute weighted naive Bayes classifier
Z H A N G W et，W ANG Z hihai，YU AN Jido ng，L IU Haiyang
(School of Com puter and Inform ation T'cchnology，Beijing Jiaotong U niversity，Beijing 100044 ,China)
Abstract ：Naive Bayes (N B)classifier has exhibited excellent performance on m a n y problem domains due to i t s simplicity and efficiency. In reality the conditional independence assumption of Naive Bayes isn? t always true.Attribute weighting i s one of the most popular methods to alleviate this assumption's influence on classification results.H o w e v e r，traditional classification models ig
nore characteristics of each test instance，and the weight vector learned from the whole training t failed to reflect each attribute's contribution of distinguishing each test instance co--rectly. T o this end，a data driven lazy learning locally attribute weighted naive Bayes model i s propod. The attribute weights for each test instance are learned from i t s neighborhoods，and learned weights are employed to build the locally weighted model by optimization method. Expe--imental results on benchmark datats demonstrate that the propod approach i s more accurate than other classical classifiers.
Keywords：Naive Bayes; lazy learning； attribute weighting； locally weighted learning
朴素贝叶斯（NaiveBayes)是一种简单而且高效的分类模型，它在属性条件独立性假设的前提收稿日期=2017-05-23
基金项目：国家自然科学基金（61771058, 61672086, 61702030)；北京市自然科学基金（4182052)中央高校基本科研业务费专项资金(2017YJS036)
Foundation item s： National Natural Science Foundation of China ( 61771058，61672086，61702030); Beijing Municipal Natural Science Foundation (4182052) ; Fundamental RearchFunds for the Central Universities (2017YJS036)第一作者：张伟（1987—)男，山西大同人，博士生.研究方
向为数据挖掘和机器学习.email: 15112102@
引用格式：张伟•王志海•原继东•等.一种局部属性加权朴素贝叶斯分类算法北京交通大学学报，018.42():4 — 21.
Z H A N G W i W A N G Zhihai，Y U A N Jidong. et. al. A locally attribute weighted naive Bayes dassifieriJj. Beijing Jiaotong Uni
versity，2018,42(2) ：14 —21(in Chine)
第2期张伟等：一种局部属性加权朴素贝叶斯分类算法15
下利用贝叶斯定理进行分类[1].N B模型的属性条件 独立性假设在现实中难以成立，原因主要有两个：1) 对于给定的类属性，属性之间并不总是相互独立的，它们之间通常存在依赖关系；）数据集中的属性对于类属性归属的影响并不总是相同的，如数据集中 的冗余属性对类属性的归属没有影响.
为了弱化属性条件独立性假设的束缚，提高 N B的分类性能，不同学者提出了多种改进方法.这 些方法大致可以分为3类：
第1类称作准朴素贝叶斯，准朴素贝叶斯的基 本思想是在属性之间引人依赖关系来放松属性条件 独立
性假设，这使得准朴素贝叶斯模型具有比N B 更复杂的网络结构.由于和其他贝叶斯网络结构类型相比，树形结构可以在多项式时间内被有效学习，一种简单的做法就是将拓展结构限定为树形结构[2]，例如，树增强型朴素贝叶斯分类器（Tree A u gmented Naive Bayes， T A N)[3]
T A N,SP-T A N)[J].
第2类方法通过属性选择或属性加权来提高N B的分类性能，数据集中的冗余属性不仅增加了分类模型学习过程中的计算量，同时还会降低分类 的准确率，所以属性选择经常作为提高分类器性能的方法[57].和准朴素贝叶斯方法相比，属性选择不会改变N B模型的结构，同时可以有效提高N B的分类性能[89].但是实际中属性对类属性的归属的影 响不同，而属性选择不能区分不同属性在分类过程中的重要程度.
属性加权通常看作是比属性选择更一般化的方 法，不仅可以排除冗余属性，还可以区分不同属性在 分类过程的重要程度.N B模型的属性条件独立性假 设本质上是假定了各个属性对类属性的贡献相同，通过属性加权可以区分不同属性对类属性归属的不 同影响.
使用属性加权来改善N B模型的性能，其难点 在于如何获得能够准确反映属性对类属性归属影响 的权重[014 ].对于N B模型，传统的属性加权方式主要采用不同的度量方式来增加强预测属性的属性权 重同时减小弱预测属性的权重，文献[10]使用属性 和类属性的增益比作为属性权重.文献[11]用属性 在决
策树中的最小深度来为属性加权.近些年一些研究人员提出通过优化权重来整体改善分类器预测 性能.文献[12]提出用局部优化算法求属性对于不同类属性的权重.文献[13]基于差分进化算法求属性权重.文献[14]通过优化算法求负条件对数似然或均方误差的最小值来设置属性权重，这种方式不仅降低了违背属性条件独立性假设对分类模型的影 响，还使得分类器的整体性能得到改善.但这些属性 加权方法都是从整个数据集合上学习属性权重，这 样的属性权重对于每个测试实例只在平均意义下是 最好的，并不能真实反映每个测试实例的属性对自 身分类的重要程度.
第3 类方法通过局部实例加权降低属性条件独 立性假设对分类性能的影响.文献[15]将局部实例 加权技术应用于N B模型，为每一个测试实例基于加权近邻实例建立局部实例加权朴素贝叶斯(Locally Weighted NaiveBayes，L W N B)模型，但 仅对实例加权，忽略了不同属性对分类性能的影响.
实际中同一属性对不同实例分类的贡献可能是 不同的，为了获得测试实例准确的属性权重，本文作 者将懒惰式学习方式和属性加权方法相结合，提出 在测试实例的近邻集合上学习测试实例的属性权重，使得不同实例可能对应不同属性权重的局部属性加权朴素贝叶斯（Locally Attribute Weighted Naive Bayes,L A W N B)模型.本文使用优化算法求解测试实例的属性权重向量，这样获得的属性权重不仅可以更准确的反映每个测试实例属性对自身分 类的影响，还可以用来整体改善局部分类模型的性能.实验结果表明本文方法获得的测试实例的属性权重和整个数据集上求得的全局属性权重相比能够 更准确的反映测试实例属性对其自身分类的贡献，同时可以显著提高N B模型的分类性能.
本文的主要贡献如下：1)针对全局属性权重不能准确反映每个测试实例属性对其自身类属性归属 影响的问题，提出了一种学习每个测试实例属性权重的方法；）不同于传统的基于加权近邻实例建立局部分类模型，本文提出在测试实例的近邻集合上用优化算法学习每个测试实例的属性权重，并建立 局部属性加权模型.
1定义与背景
本节对文中用到的定义、符号及一些背景知识 进行介绍.
1.1 N B模型
本文用符号D ={x(0)，x(1)，…，”表示 包含沒个实例的集合^⑴二^^^^…^丨^表示实例集合中的第Z个实例为数据集中的属性个数(不包括类属性），A，表示实例的第z个属性，a(;)表示第Z个实例属性A，的取值.
准朴素贝叶斯模型和N B模型都基于贝叶斯定 理⑴为
16北京交通大学学报第42卷
P(c|X)=P(c)P(x
P(x)I c)()
网络结构上的差异使得式（1)具有不同的分解
形式.基于属性条件独立性假设的N B有如下
分解[1]
5-1
P X|c) =n P(!I c)(2)
t=0
式中，P(a|c)表示给定类属性c条件下第i个属
性取值a的条件概率.
T A N,SP-T A N等准朴素贝叶斯模型分解形式
P(x |c)=n P(“t I c，P:1(A t ))(3)
t = 0
式中：P J A t)表示属性A t依赖的属性集合，即结
构中属性节点A t的父节点集合（不包括类属性节
点）.集合P J A t)中包含的属性节点越多，获得准确
概率估计需要的数据就越多，模型的计算量就越大.
12相似性度量
实例间的相似性是本文在近邻集合上学习测试
实例属性权重的基础，实际中有很多度量方式可用
于度量实例间的相似性，本文使用标准Euclidean
距离函数度量实例间的相似性.
令表示第Z个训练实例x⑴到测试实例x
的距离.在距离度量过程中，若属性A t是名称型，则
第Z个训练实例和测试实例属性A t取值的差^(;)=
—a满足
0)，a(—a t
d l ={t t(4)
t1其他
欧式距离的时间复杂度05)为每个测试实例
x建立近邻实例集合D J x)过程中需要计算0()
个距离，其中《为训练集合中的实例个数.此外对计
算得到的《个距离使用堆排序，堆排序的时间复杂
度为O d b w)，所以为每个测试实例寻找々个近邻
实例的时间复杂度为+lb w)).
2局部属性加权朴素贝叶斯模型
为了研究测试实例属性对其自身分类的贡献，
本文提出了局部属性加权朴素贝叶斯模型.
2.1近邻集合上的概率计算
为了避免零概率的出现，采用文献[16]提出的
M估计对先验概率和条件概率进行平滑处理.近邻
实例集合上类属性c的先验概率计算公式为
P c i)t)+m/ I C I
P c(5)
式中：r表示近邻实例集合中实例的个数表示近邻实例集合中第*个训练实例的类属性值；，t表示第i个实例的权重；本文m取1 , |C |表示类属性
取值的个数，P表示类属性缺失的实例的个数，指 示函数7定义为
1,
I(x,y) —l
0)，
.1，x —y
# y ’
式中，x和y表示两个实例中同一属性的取值.
假设属性A，是名称型的，a，为属性A，在测试 实例中对应的值，则属性值a；的条件概率计算式为
P(a,|c,)—
]C;=I，，c).m/7 |A,
+]c r=i c'c)—,c
(6)式中：|A,|表示属性A，取值的个数，尸表示第z 个实例的第j个属性取值，，表示测试实例x的第j
个属性的取值;/?,c表示给定类属性c条件下属性 A, 缺失值的实例个数.
2.2测试实例的属性权重计算
文献[17]提出用最大条件对数似然(Conditional Log-Likelihood，CI丄）来评价贝叶斯网络结构能获得更准确的类概率估计.因此，本文尝试通过在测试实例的近邻集合上求最大条件似然对 数的最大值来获得测试实例的属性权重向量w.本 文在实例集合D上用条件对数似然函数定义的目标函数J C L L为
其中
J CLL (w)—^In P(c(
X]ln
,—0
tp(c(, ,w)
^'^^cf,w)
0(c?w)—P(c)n P(a t|c)
()
(8)
目标函数J c L L(W)的梯度记作
J c l l(W)
d w{
八
^'P(c，
Y j(l n(P(a,|
;w)ln(P (
)))—
')))(9)基于目标函数和相应的梯度，使用文献[18]的L-B F G S-M优化程序来求测试实例x的近邻集合 D;(x )上使得函数一J (:LL(w)取最小值的解作为测 试实例的属性权重向量W x，其中测试实例的每个属 性的权重™，满足0 <<1.算法1给出在近邻集 合上求测试实例属性权重的算法.
算法 l.AttributcWcights(_D t(x)，J CLL(w))
输人：近邻实例集合D t(x)，目标函数J c l l(w);
输出：测试实例属性权重向量wx.
01用式（5)和式（6)计算数据集D* (x)中的P(c)和P(at |c)
第2期张伟等：一种局部属性加权朴素贝叶斯分类算法17
02：将P Cc)和P (a」c)代入目标函数J cl.(w)的相关 式（7)和式（9)
03：基于式（7)和式（9)用L-BFGS-M优化程序计算函数 —J c i.i.(w)取最小值的解向量w
04：wx—w
05 ：return wx
在近邻集合上利用优化算法学习测试实例属性 权重的算法的时间复杂度取决于优化算法求解过程 的收敛速度，而本文采用的优化算法是一种i- B F G S算法，该算法比较适合在大规模数据集上进行计算，它具有牛顿法收敛速度快的特点.
2.3局部属性加权朴素贝叶斯模型和算法
任意一个测试实例x在其近邻实例集合D;(x )上的属性加权后验概率公式为
A p〇n,p (,I c)-.
P(c I x；w i) =^----—.-------,^；—
x c p(')n,p i')-
(0)属性权重.这个过程增加了模型的计算量.获得属性权 重后，在近邻集合上为单个测试实例建立L W N B模 型和N B模型的时间复杂度相同.此外，较小的训练集 合可以显著减少单个模型求属性权重的计算时间.因 此，当训练集规模较大时，本文为单个测试实例建立 模型的时间比全局属性加权（Weighting attributes to Alleviate Naive Bayes ,Independence Assumption，W A N B I A)模型的训练时间显著减少.本文I A W N B 模型预测过程中需要存储训练集，这使得本文算法的 空间复杂度较高，同时本文算法的时间复杂度和测试 集的规模成线性关系.
3实验分析
实验运行环境的C P U为3G H Z，内存为4G B，操作系统是Linux.本节在20个U C I的数据集[19]上 对I A W N B模型性能进行评价.表1给出了实验数 据集的内容.
满足条件
^'P(c r) =1v S P I C) =1，
式中：w x =—0，，…，—s-1)是测试实例的属性 权重向量；是测试实例属性.的权重a,，表示属 性A，的第j个取值；P C)表示集合D J x)上类属 性c的先验概率；P(a,, |c)表示集合队X)中给定类属性c条件下属性A，的第，个取值a，的概率 估计.
由于计算测试实例的每个类属性后验概率的式 (10)中的分母都相同，测试实例x的属性加权模型 可简化为
c(x) =a r g m a x P(c)n P I c)-'(11)式中,=0，1，…，5 —1.
将每个测试实例的属性加权朴素贝叶斯模型称 为L A W N B.算法2给出了建立L A W N B模型的一 般过程.
算法2. L A W N B(D，x，是，J C L I.(w))
输人：训练实例集合D，测试实例x，近邻实例个数々，目标函数J CI.L(W);
输出：测试实例x的类属性预测值c
01：从数据集D中寻找距离测试实例x最近的&个训练实例组成近邻实例集合(x )
02 : wx— AttributcWcights(_D A(x )，_/ci.i.(w))
03 ：根据式（11计算各类属性c对应的后验概率
04: c—最大后验概率对应的类属性
05 :return c
算法2描述了为每个测试实例建立L A W N B模 型的过程，其中需要进行实例选择和计算测试实例的
表1实验数据集内容
Tab.1Introduction o f the experimental datats
数据集名称
数据集类属性属性是否
大小取值个数个数有缺失值anneal
anneal. ORIG
audiology
autos
breast-cancer
credit-a
disbetes
glass
hypothyroid
ionosphere
898
898
226
690
768
2丄4
丄24
3丄0
435
99011
7
是
是
是
是
是
是
否
否
是
否
否
否
是
否
是
否
是
是
否
否下面分析和实验相关的一些预处理步骤.1)数 值属性：本文的局部属性加权朴素贝叶斯模型不能处理数值属性，使用文献[20]提出的监督属性离散化方法对数值属性进行离散化处理.2)缺失值：本文 米用式（5)和式（6)中的方式处理缺失值.
本文模型在weka-3-8平台实现，在每个数据集 上进行10次10重交叉验证，每个分类器都是在完 全相同的交叉验证集合上进行训练和预测，最后将 获得的100
个准确率的平均值作为分类器在数据集
18
北京交通大学学报第42卷
上的准确率.使用双尾假设t 检验对每个数据集上 不同的数据集个数，Z 表示准确率显著更差的数据 L A W N B 模型和对比模型的显著性进行分析，显著 集个数.为了进一步描绘准确率的一般情况，计算了 性水平为0.05.
每个分类器在20个数据集上的平均准确率，在表2 在表2中对20个数据集上的L A W N B 模型和 中的倒数第2行给出.平均准确率反映了分类器在 用于比较的模型的准确率情况进行了比较统计，其 20个数据集上的最基本的综合性能.表2给出了每 中，w 的值表示20个数据集中L A W N B 模型准确 个数据集上各算法的准确率，标准差，显著性对比结 率显著更高的数据集个数“表示准确率没有显著
果及各算法在20个数据集上的平均准确率.
表
2 7种分类模型的准确率和标准差
T'ab .2
C lassification accuracy and standard deviation of the 7 kinds of classification m odels
%
数据集名
LAWNB50NB
WANBIA
LWNB50TAN
AODE
WAODE
anneal
99.33 ±10786.62士3.7丄，98.30士丄.29 •98.24士丄.57 •96.80士丄.72 •96.8丄士2丄2 •98.47士丄.42 •anneal. ORIG 95.03 ±23374.78士4.4 •96.43士2.06 。92.83士2.83 •92.26士2.57 •93.64士2.43 •89.93士3.00 •audiology 78.9 ±8.4870.76士9.83 •77.56士9.4677.49士8.7553.20士丄0.4 •70.90士9.9
2 •75.3丄士9.34 •autos 76.3丄 ±9.3356.99士丄0.3 •75.03士8.8776.60士9.3277.29 士丄 0.273.79士9.79 •78.90 士8.9丄。breast-cancer 70.4 ±75772.67士7.84 。
7196 士 8.4473.8丄士8.08。70.57士7.8373.33士7.53 。7190 士 8.54credit-a 84.7丄 ±4.58士5.丄2 •86.04士4.80 。82.80士5.05 •
83.55士4.33 •85.97士4.48 。84.26士4.56diabetes 75.54 ±4.9475.59 士 5.丄 275.65士4.66
70.67士4.8丄，7295士4.90 •76.2 丄士 4.6875.74士4.44glass 7丄.9丄 ±9.648.6丄士丄丄.4 •69.77士丄丄.2 •7137 士丄 0.656.65士丄丄.9,62丄5士丄丄.0 •62.02士丄丄.7 •hypothyroid 97.42 ±0.9295.33士丄.08 •99.2 士 0.5 丄。96.30士丄.06 •9260士丄.丄9 •93.62士丄.22 •93.57士丄.2丄•k)n()sphere 89.9 ±4.9882.54士5.96 •9丄.丄9士4.79。83.07士6.36 •89.02士4.90916丄士4.70。92.96士4.丄7。iris 95.27 ±5.3095.67士4.9694.73士5.5595.53士4.939173 士7.丄0 •94.40士5.7495.60士5.03kr-vs-kp 97.80 ±0.928780士丄.8丄•93.4丄士丄.40 •97.76 士 0.8 丄88.75 士丄.77 •9107士丄.60 •94.丄6士丄.30 •mushroom 丄00.00 ±0.095.76 士 0.7丄.99.90士0.丄丄•丄 00.00 士 0.099.47士0.37 •99.95士0.08 •99.99士0.04 •gment 97.2 ±11080.丄丄士255 •94.48士丄.47 •96.60士丄.丄9 •9277士丄.74 •92.90士丄.72 •95.00士丄.44 •sick 97.54 ±0.859268士丄.25 •97.4丄士0.74 •96.75士丄.03 •
96.3丄士丄.39 •97.34 士丄.0697.78士0.95 。sonar 79.06 ±8.466777士丄18 •76.96士8.49
8782士6.丄4。76.92士8.36 •80.52 士 8.077.63 士丄 0.8soybean 93.丄9 ±3.692.70士3.0793.09士2.70
93.丄6士29丄88.2丄士3.77 •92.8 士 2.9 丄93.88士 2.4丄。vote 96.45 ±27丄90.05士4.57 •95.25士3.24 •95.32士3.34 •
92.33士4.09 •94.26士3.58 •94.5丄士3.79 •vowel 94.02 ±2.656292士5.丄5 •60.82士4.47 •95.丄
6士263。87丄4士3.50 •89.27士3.35 •92.丄0士3.丄3 •zoo
95.93 ±6.6395.04士6.9995.03士6.54 •96.73 士 6.丄74.57士丄5.2 •94.44士7.52 •97.丄3 士 5.3 丄。平均准确率
89.25
80.丄丄
87.丄丄88.90
83.6587.2588.04v / /，
—
丄5/4/丄
9/7/4
9/8/3丄7/3/0
丄2/5/3
丄0/5/5
•，。分别表示L A W N B 模型在数据集上的准确率显著下降或显著改进.
本文做两个实验，第1个实验分析L A W N B 模 型准确率在20个数据集上随々值的变化趋势，基于 此确定L A W N B 模型使用的参数.第2个实验将 L A W N B 和 N B 模型[1]，L W N B [15]，W A N B I A 模 型[14]，T A N ，均单依赖贝叶斯分类器（Aggregating ()ne-DependenceEstimators，A ()D E )模型[21]，加 权均单依赖贝叶斯分类器（Weightily Averaged ()ne-DependenceEstimators，W A O D E )模型[22]进 行了比较.3.1参数设置
本节对20个数据集上L A W N B 模型的准确率 随々值的变化规律进行了分析.图1中给出了 20个 数据集上模型准确率随々值从1〜300的变化趋势. 这些数据集上准确率的变化大致可以分为3类.
1)
有3个数据集sonar, autos和vowel上的准
确率随々值递增有明显的不断下降趋势.
2) 有2个数据集上的准确率有明显波动：glass
上的准确率波动最为明显，在1<々<70之间有起 伏，々=70时达到最大，然后出现连续下降；anneal. O R I G 上的准确率先减小后增大，6 = 80达到最大 后又减小，最后趋于稳定.
3)有15个数据集上的准确率随着6值变化先 增大后减小直至趋于稳定，这个过程中可能伴有微 小波动，但不影响整体走势.其中13个数据集的准 确率最大值出现在10<6 <100范围内，剩余两个 数据集在这个范围内的准确率最大值和整个范围内 准确率最大值的差小于1 %.
图2中给出了 L A W N B 模型在20个数据集上 平均准确率随6值的变化趋势.L A W N B 模型的平 均准确率在10< 6 < 70范围内变化不大，在6 = 60时平均准确率最大值为89. 32%；当6 = 10,50, 70时，平均准确率都为89. 25%，和最大平均准确 率相差不大；当6 >70后有下降趋势，6 = 300时平 均准确率最小值为87.97%.
