在逐渐缩小的空间上渐进学习朴素贝叶斯参数.doc

在逐渐缩小的空间上渐进学习朴素贝叶斯参数
文章编号:1001-9081(2012)01-0223-05 doi:10.3724/sp.j.1087.2012.00223


摘 要:局部加权朴素贝叶斯(lwnb)是朴素贝叶斯(nb)的一种较好的改进，判别频率估计(dfe)可以极大地提高nb的泛化正确率。受lwnb和dfe启发，提出逐渐缩小空间（gcs）算法用来学习nb参数：对于一个测试实例，寻找包含全体训练实例的全局空间的一系列逐渐缩小的子空间。这些子空间具有两种性质：1)它们都包含测试实例；2)一个空间一定包含在任何一个比它大的空间中在逐渐缩小的空间上使用修改的dfe(mdfe)算法渐进地学习nb的参数，然后使用nb分类测试实例。与lwnb的根本不同是：gcs使用全体训练实例学习nb并且gcs可以实现为非懒惰版本。实现了gcs的决策树版本（gcs-t），gcs-t是非懒惰算法,它使用决策树寻找子空间。实验结果显示，与c4.5以及贝叶斯分类算法(如naive bayes、baysiannet、nbtree、lwnb、隐朴素贝叶斯)相比，gcs-t具有较高的泛化正确率，并且gcs-t的分类速度明显快于lwnb。
关键词:朴素贝叶斯；局部模型；全局模型；决策树；朴素贝叶斯树
abstract: locally weighted naive bayes (lwnb) is a good improvement of naive bayes (nb) and discriminative frequency estimate (dfe) remarkably improves the generalization accuracy of naive bayes. inspired by lwnb and dfe, this paper proposed gradually contracting spaces (gcs) algorithm to learn parameters of naive bayes. given a test instance, gcs found a series of subspaces in global space which contained all training instances. all of these subspaces contained the test instance and any of them must be contained by others that are bigger than it. then gcs used training instances contained in those subspaces to gradually learn parameters of naive bayes (nb) by modified version of dfe (mdfe) which was a modified version of dfe and used nb to classify test instances. gsc trained naive bayes with all training data and achieved an eager version, which was the essential difference between gsc and lwnb. decision tree version of gcs named gcs-t was implemented in this paper. the experimental results show that gcs-t has higher generalization accuracy compared with c4.5 and some bayesian classification algorithms such as naive bayes, baysiannet, nbtree, hidden naive bayes (hnb), lwnb, and the classification speed of gcs-t is remarkably faster than lwnb.

key words: naive bayes (nb); local model; global model; decision tree; nbtree
0 引言
对于测试实例itest，如果知道它所属的潜在概率分布p，根据贝叶斯决策理论［1］，利用p可以对itest最优分类。现实中所能得到的训练数据总是有限的，因此几乎不可能准确估计潜在概率分布p。为了使用有限的数据尽可能准确地估计概率分布p，往往需要做一些条件独立假设。朴素贝叶斯（naive bayes, nb）使用最极端的条件独立假设：给定类标号属性后，其他各属性之间条件独立。尽管有极端的条件独立假设，朴素贝叶斯在多数情况下依然表现出优秀的泛化性能，且具有较低的训练时间复杂度，这引起了人们的极大兴趣。许多方法试图通过放松条件独立假设进一步提高朴素贝叶斯的泛化性能，这类方法有朴素贝叶斯树（nbtree）［2］、贝叶斯网（baysiannet）［3-4］、局部加权朴素贝叶斯（locally weighted naive bayes, lwnb）［5］和隐朴素贝叶斯（hidden naive bayes, hnb）［6］等。
baysiannet、hnb通过增加父节点个数放松条件独立假设。nbtreelwnb在局部训练空间［2,5,7］中建立朴素贝叶斯从而放松条件独立假设。在局部空间建立分类器的另一个好处是：如果在很大的全局实例空间中建立分类器，很难保证它对空间中每一部分实例都有较高的泛化正确率；但是，如果仅在全局空间的一个局部区域内建立分类器，使用该分类器对属于该局部空间的实例分类，一般来说能提高泛化正确率。
判别参数学习［8］也是一类提高朴素贝叶斯泛化性能的方法。扩展逻辑回归（extension logistic regression, elr）［9］和判别频率估计(discriminative frequency estimate, dfe)［10］是最具代表性的两种判别参数学习算法，它们都能显著提高朴素贝叶斯的泛化正确率。elr和dfe的泛化性能基本相当，但dfe的学习速度比elr快很多［9］。
受lwnb和dfe启发，本文提出算法逐渐缩小空间（gradually contracting spaces, gcs），在根据测试实例itest寻找的一系列子空间上使用修改的dfe算法渐进地学习朴素贝叶斯(nb)的参数，然后使用nb分类测试实例itest。本文实现了gcs的决策树版本(decision tree version of gcs, gcs-t)，实验结果显示，与naive bayes、baysiannet、nbtree、lwnb、hnb以及c4.5相比，在实验中所选多数数据集上gcs-t具有更好的泛化性能，并且gcs-t的分类速度明显比lwnb快。

1 相关工作
kohavi提出nbtree［2］，该算法把朴素贝叶斯和决策树结合起来，在决策树的叶节点上建立朴素贝叶斯。nbtree划分节点的标准是能否提高nbtree在训练集上的交叉验证正确率。nbtree叶节点上的朴素贝叶斯仅体现局部空间内训练实例（到达叶节点的训练实例）的分布特征，而gcs中学习到的朴素贝叶斯主要体现局部空间内训练实例的分布特征，但它也在一定程度上体现全体实例的分布特征。
lwnb［5］是一种懒惰分类算法，该算法分类测试实例之前不训练分类器，只保存训练实例集。分类时，用欧氏距离在训练实例集合中找到测试实例的k个近邻，根据k个近邻到测试实例的距离对它们加权并用加权后的近邻训练朴素贝叶斯，然后对测试实例分类。lwnb分类速度较慢，训练实例数量较大时这个问题尤为严重。
hnb［6］已不具有朴素贝叶斯或贝叶斯网的结构特征。hnb给类属性之外的任一属性a加一个隐父节点h，其他的所有属性都通过h影响属性a。本质上说，hnb中类属性之外任一属性a的父节点是除属性a之外的所有属性，只是这些属性以不同的概率作为a的父节点。
dfe［10］是一种基于统计的判别参数学习算法，它与频率估计（frequency estimate fe）算法［10］的唯一区别是fe统计训练实例之前不对实例加权，而dfe根据当前分类器对训练实例的分类正确率对实例加权统计，这使贝叶斯分类器更加拟合训练数据。一般情况下使用dfe学习参数可以提高朴素贝叶斯的泛化正确率。
2 gcs算法
2.1 学习朴素贝叶斯参数
使用x代表离散型属性，x代表x的具体取值，xij代表属性xi的第j种取值。使用x代表一组离散型属性组成的向量，x代表x的具体取值。使用c代表类标号，c代表c的具体取值，cj代表c的第j种取值。离散型训练数据集d包括一组训练实例，每一个实例用(x, c)表示。现在用大小写和空心字来表示字符，请根据现在的书写方式，补充文中哪些还需要处理并统一的字符。
朴素贝叶斯结构如图1，类标号c是属性x1,x2,…,xm的父节点，给定c后，x1,x2,…,xm之间相互独立。图1中每个节点处都保存一个概率分布。朴素贝叶斯使用式(1)计算后验概率分布：
p(c|x1,x2,…,xm)=αp(c)∏mi=1p(xi|c)(1)
其中：α是正则化因子；p(c)和p(xi|c)都被记录在条件概率分布表（conditional probability table, cpt）中，也就是说cpt中包含了类标号c取各种值时它的概率值p(c)以及属性xi，类标号c的各种不同取值组合的条件概率为p(xi|c)，i=1,2,…,m。使用式(2)计算p(xi=xij|c=ck)：
p(xi=xij|c=ck)=nijk/nik(2)
其中nijk代表训练数据d中在属性xi上取值为xij并且类标号取值为ck的实例个数，nik=∑jnijk。p(c=ck)用式（3）计算：
p(c=ck)=nk/n(3)
其中：n代表训练数据d中实例的总个数，nk代表d中类标号取值为ck的实例个数。
为了方便实现，cpt的每一个表项θijk等于nijk或nk(θ00k=nk)，而不再等于p(xi=xij|c=ck)或p(c=ck)。由nijk或nk很容易计算出p(xi=xij|c=ck)或p(c=ck)。
学习朴素贝叶斯实质上是学习cpt中的表项θijk，θijk也叫做朴素贝叶斯的参数。dfe学习θijk的过程［10］在如下的伪码中给出，它实质上就是在训练实例上做m（伪码中dfe在全体训练数据上的迭代次数）次加权统计。为了在gcs算法中使用dfe学习参数，修改的dfe算法为mdfe(modified version of dfe)算法，修改的方法是去掉算法dfe中标号为1)的语句，其他不变。

有序号的程序——————————shift+alt+y
程序前

algorithm: learning nb by discriminative frequency estimate
input: naive bayes parameters θijk; training dataset d, di∈d; iterator number m
1）
initialize each naive bayes parameters θijk to 1;
2）
for e from 1 to m do

3）
for each di in d do
4）
compute probability of ith training instance being correctly classified by current naive bayes, denote by p(c|di)
5）
double weight=1-p(c|di)
6）
for each corresponding parameters θijk in naive bayes do
7）
let θijk=θijk+weight
程序后


2.2 gcs算法
dfe在全体训练实例上迭代m次学习参数θijk，建立的是全局模型。lwnb［5］表明在局部空间上建立朴素贝叶斯多数情况下可以提高泛化正确率。lwnb学习的朴素贝叶斯仅体现局部空间内训练实例的分布特征，完全忽略局部空间之外训练实例的分布。本文提出的gcs算法在包含全体训练实例的全局空间u0以及它的逐渐缩小的局部子空间u1,…,ur上渐进学习nb的参数，使得nb既能突出体现局部空间内训练实例的分布特征，又能在一定程度上体现全局空间内训练实例的分布特征。gcs是对全局模型和局部模型的折中
gcs算法主要步骤：对于一个测试实例itest，使用某种方法在包含所有训练实例的全局空间u0内寻找局部子空间u1,…,ur并且itest∈urur-1…u1u0。建立朴素贝叶斯nb0,nb1,…,nbr。初始化nb0的参数为均匀分布，然后在空间u0包含的训练实例上使用mdfe学习nb0的参数。使用nb0的参数初始化nb1的参数，在空间u1包含的训练实例上使用mdfe学习nb1的参数，重复这个过程，直到学习完nbr的参数。使用nbr分类属于空间ur的测试实例itest。

gcs划分后的空间满足i，itest∈ui，并且i、j，如果i懒惰分类器。但lwnb只能实现为懒惰分类器。
2.3 gcs-t
决策树［11］是经典的分类算法之一，它从根节点开始不断划分空间，直到叶节点。决策树的每个节点n都代表一个子空间。从根节点到叶节点的每一条路径中，父节点代表的实例空间肯定包含子节点代表的实例空间，这与gcs算法对局部子空间u1,…，ur的要求一致。使用决策树确定局部子空间的gcs算法叫gcs-t，它是非懒惰算法。
gcs-t首先使用c4.5和全体训练实例建立一棵决策树。决策树的每个节点代表一个局部空间，在每个节点中存储到达该节点处的所有训练实例并离散化这些训练实例中的连续型属性。然后沿着决策树从根节点到叶节点的每一条路径，使用mdfe在逐渐缩小的局部空间上渐进地学习朴素贝叶斯参数并把学习到的朴素贝叶斯关联到该路径的叶节点上。分类时，测试实例沿着决策树的一条路径到达叶节点，然后使用叶节点上的朴素贝叶斯分类实例。
gcs-t的伪码描述如下所示。程序实现时，gcs-t中的建树过程和学习朴素贝叶斯的过程可以同时进行。
程序前

algorithm: decision tree version of gcs
input: training dataset d; iteration number of dfe rn, pn
uses c4.5 and training dataset d building a decision tree dt, each node of the decision tree maintains training data arriving to the node;
discretize all training data maintained by dt;
buildgcs-t (dt) {
build a naive bayes nb and initialize parameters of nb to uniform then use mdfe and training data maintained by root of dt to learn parameters of nb, iteration number of mdfe set to rn;
for each soni:=the ith son node of the root of dt
incrementallybuildnbbymdfe (soni, nb); }
incrementallybuildnbbymdfe(node, nb) {
if(node==null)
return;
else
build a naive bayes nbson and copy nbs parameters to initialize parameters of nbson, then use mdfe and training data maintained by node to learn parameters of nbson, iteration number of mdfe set to pn;
for each soni:=the ith son node of node in dt
incrementallybuildnbbymdfe (soni, nbson); }
程序后

虽然gcs-t和nbtree都使用决策树划分空间并在叶节点上关联朴素贝叶斯，但它们生长决策树和学习朴素贝叶斯的方法有很大不同。nbtree中决策树生长依赖于叶节点上朴素贝叶斯的分类正确率；而gcs-t中决策树的生长完全独立于叶节点上的朴素贝叶斯。gcs-t叶节点上的朴素贝叶斯使用全体训练实例学习参数，但不同子空间内训练实例对参数影响的大小不同；而nbtree叶节点上的朴素贝叶斯仅使用到达该叶节点的训练实例学习。
3 实验与分析
实验使用25个选自uci资源库［12］的数据集，包括了大部分不同领域的数据。表1列出每个数据集中的实例个数、类个数和属性个数等信息。
算法gcs-t在weka［13］框架下实现，其中mdfe的迭代次数rn和pn设置为2（多次实验发现设置为2时算法泛化性能较好），划分空间的决策树使用weka中的j48，参数为默认设置。对于缺值数据，使用weka中的replacemissingvalues处理，并用weka中的discretize根据有监督的最小描述长度（minimum description length, mdl)原则请补充mdl的中文名称和英文全称。离散化连续型数据。gcs-t中的naive bayes使用拉普拉斯估计避免概率为零的情况。
实验中将本文提出的算法gcs-t分别与算法naive bayes、bayesiannet、nbtree、lwnb、hnb、c4.5进行比较。nbtree、hnb（预先使用discretize离散化训练数据）、c4.5（j48）都使用weka中的实现，参数为默认设置。bayesiannet使用weka中的实现，父节点搜索算法选择k2，评分选择bayes，最大父节点个数设为2，其他为默认设置。naive bayes使用weka中的实现，选择离散化数据，其他参数为默认设置。lwnb使用weka中的分类器lwl，预先使用discretize离散化训练数据（与文献［5］中做法一致），基分类器选择naive bayes，近邻个数设为50（文献［5］将近邻个数设为50），其他参数为默认设置。
表2列出算法gcs-t、naive bayes、c4.5（j48）、nbtree、bayesiannet、hnb在各个数据集上的平均泛化正确率及标准差在各个数据集上的平均泛化正确率（分类正确的实例个数/测试实例总个数×100%）及标准差，平均泛化正确率和标准差是在每个数据集上做10次10折交叉验证（100次实验）得到的。表2的最后一行标明了在实验中所选25个数据集上与gcs-t相比，其他算法赢（泛化正确率显著高）、平、输（泛化正确率显著低）的个数。这里所说的显著使用置信水平为0.95的t测试度量。表2倒数第二行总结各个算法在25个数据集上的平均泛化正确率。

总结表2中实验结果如下。gcs-t的泛化性能明显优于naive bayes（gcs-t赢19输1）、bayesiannet（gcs-t赢16输0）、nbtree（gcs-t赢14输2）、hnb（gcs-t赢14输3）、lwnb（gcs-t赢15输3）。gcs-t的泛化性能在一定程度上优于j48（gcs-t赢15输5）。gcs-t在25个数据集上的平均泛化正确率明显高于naive bayes（gcs-t高3.12%）、j48（gcs-t高1.78%）、bayesiannet（gcs-t高1.40%）。而gcs-t的平均泛化正确率略高于nbtree（gcs-t高1.20%）、hnb（gcs-t高1.04%）、lwnb（gcs-t高0.78%）。但lwnb是懒惰算法，分类速度随训练实例个数的增加而线性降低，而gcs-t不是懒惰算法，分类速度不受训练实例个数影响，它的分类速度比lwnb快得多。
从上述实验结果看出：在实验中所有基于贝叶斯统计的分类器中，gcs-t的泛化正确率最高。在训练数据量比较小时，朴素贝叶斯能够很好地拟合训练数据集，且由于结构简单，它不容易出现过度拟合现象，因此在测试集上有较高的泛化正确率。但在训练数据量较大时，朴素贝叶斯在训练数据集上会出现拟合不足问题，这是因为朴素贝叶斯不能很好地体现训练数据的局部分布特征。而gcs-t克服了这个弱点，gcs-t沿着决策树从根节点到叶节点的每一条路径，使用mdfe在逐渐缩小的局部空间上渐进地学习朴素贝叶斯，这个过程保证最终学习到的朴素贝叶斯既能体现全体训练数据的分布特征又能很好地体现局部训练数据的分布特征，这是gcs-t成功的关键。
表3给出了表2中各种算法在25此处为25个，而表3的表名中却有42个数据集，到底是多少？个数据集上的平均训练时间和测试时间，训练/测试时间使用weka中的usercpu_time_(training/testing)度量。可以看出，算法gcs-t的训练时间仅是决策树的6倍。gcs-t的测试时间基本上是lwnb的1/42，并且lwnb的测试时间随训练样本数量的增加而线性增长但gcs-t的测试时间不受训练样本数量影响。
gcs-t中朴素贝叶斯的参数使用dfe学习，而本实验所用weka中实现的其他贝叶斯算法都使用fe学习参数。su［10］的实验表明，使用迭代4次的dfe学习参数能提高贝叶斯分类算法的泛化正确率。为了让实验更加公平，本文修改了weka，让本实验中用到的贝叶斯分类算法都使用迭代4次的dfe学习参数，进而得到了第二组实验结果，如表4所示。从表4中可看出，尽管使用dfe学习参数后多数算法的泛化性能都有所提高，但它们的平均泛化正确率依然低于本文中提出的算法gcs-t。
表5给出了表4中各种算法在25个数据集上的平均训练时间和测试时间。
4 结语
本文提出算法gcs。对于一个测试实例itest，gcs在包含所有训练实例的全局空间u0中寻找子空间u1,…，ur并且itest∈urur-1…u1u0，在空间u0,…,ur所包含的训练实例上使用mdfe渐进地学习朴素贝叶斯参数。
gcs可以实现为非懒惰版本，本文实现了gcs的非懒惰版本gcs-t，在训练阶段使用决策树寻找局部子空间，它的分类速度比懒惰算法lwnb快得多。本文实验结果显示，在大多数数据集上，gcs-t的泛化性能优于naive bayes、nbtree、bayesiannet、hnb、lwnb（无论它们使用判别或生成方法学习参数）以及c4.5。

参考文献:
[1]
theodoridis s, koutroumbas k. pattern recognition ［m］. 4th ed. maryland heights, mo: elsevier, 2009.
[2]
kohavi r. scaling up the accuracy of nave bayes classifiers: a decision-tree hybrid ［c］// proceedings of the second international conference on knowledge discovery and data mining. new york: acm press, 1996: 202-207.
[3]
friedman n, geiger d, goldszmidt m. bayesian network classifiers ［j］. machine learning, 1997, 29(2/3): 131-163.
[4]
张连文,郭海鹏.贝叶斯网络引论［m］.北京：科学出版社,2006.
[5]
frank e, hall m, pfahringer b. locally weighted naive bayes ［c］// proceedings of the 19th conference in uncertainty in artificial intelligence. seattle: morgan kaufmann, 2003: 249-256.
[6]
jiang l, zhang h, cai z. a novel bayes model: hidden naive bayes ［j］. ieee transactions on knowledge and data engineering, 2009, 21(10): 1361-1371.
[7]
kai m t jonathan r w, swee c t et al. feature-subspace aggregating: ensembles for stable and unstable learners ［j］. machine learning, 2011, 82(3): 375-397.
[8]
pernkopf f, wohlmayr m. on discriminative parameter learning of bayesian network classifiers ［c］// european conference on machine learning and principle and practice of knowledge discovery in databases. berlin: springer-verlag, 2009: 221-237.
[9]
greiner r, su x, shen b, et al. structural extension to logistic regression: discriminative parameter learning of belief net classifiers ［j］. machine learning, 2005, 59(3): 297-322.
[10]
su j, zhang h, ling c x, et al. discriminative parameter learning for bayesian networks ［c］// proceedings of the 25th international conference on machine learning. new york: acm press, 2008: 1016-1023.
[11]
quinlan j r. c4.5: programs for machine learning ［m］. seattle: morgan kaufmann, 1993.
[12]
asuncion a newman d j. uci repository of machine learning databases ［eb/ol］. ［2011-03-25］. http://www.ics.uci.edu/~mlearn/ mlrepository.html.
[13]
witten i h, frank e, hall m a. data mining: practical machine learning tools and techniques ［m］. 3rd ed. seattle: morgan kaufmann, 2011.
收稿日期:2011-06-23;修回日期:2011-08-18。
基金项目:
国家自然科学基金资助项目（60901078）。
作者简介:
欧阳泽华(1987-)，男，河南商丘人，硕士研究生，主要研究方向：数据挖掘、机器学习； 郭华平(1982-)，男，河南信阳人，博士研究生，主要研究方向：数据挖掘、机器学习； 范明(1948-)，男，河南信阳人，教授，博士生导师，ccf高级会员，主要研究方向：数据库、数据挖掘、机器学习。