1、 在逐渐缩小的空间上渐进学习朴素贝叶斯参数 文章编号 :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(
2、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 weig
3、hted 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.
4、 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 gra
5、dually 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 tr
6、ee 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 spee
7、d 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）使用最极端的条件独立假设：给定类标号属性后，其他各属性之间条件独立。尽管有极端的条件独立假设，朴素贝叶斯在多数情况
8、下依然表现出 优秀的泛化性能，且具有较低的训练时间复杂度，这引起了人们的极大兴趣。许多方法试图通过放松条件独立假设进一步提高朴素贝叶斯的泛化性能，这类方法有朴素贝叶斯树（ nbtree） 2、贝叶斯网（ baysiannet） 3-4、局部加权朴素贝叶斯（ locally weighted naive bayes, lwnb） 5和隐朴素贝叶斯（ hidden naive bayes, hnb） 6等。 baysiannet、 hnb通过增加父节点个数放松条件独立假设。 nbtree、lwnb在局部训练空间 2,5,7 中建立朴素贝叶斯从而放松条件独立假设。在局部空间建立分类器的另一个好处是：
9、如果在很大的全局实例空间中建立分类器，很难保证它对空间中每一部分实例都有较高的泛化正确率；但是，如果仅在全局空间的一个局部区域内建立分类器，使用该分类器对属于该局部空间的实例分类，一般来说能提高泛化正确率。 判别参数学习 8也是一类提高朴素贝叶斯泛化性能的方法。扩展逻辑回归（ extension logistic regression, elr） 9和判别频率估计 (discriminative frequency estimate, dfe) 10是最具代表性的两种判别参数学习算法，它们都能显著提高朴素贝叶斯的泛化正确率。 elr和 dfe的泛化性能基本相当，但 dfe的学习速度比 elr快
10、很多 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 的分类速度明显
11、比 lwnb快。 1 相关工作 kohavi 提出 nbtree 2，该算法把朴素贝叶斯和决策树结合起来，在决策树的叶节点上建立朴素贝叶斯。 nbtree划分节点的标准是能否提高 nbtree在训练集上的交叉验证正确率。 nbtree叶节点上的朴素贝叶斯仅体现局部空间 内训练实例（到达叶节点的训练实例）的分布特征，而 gcs中学习到的朴素贝叶斯主要体现局部空间内训练实例的分布特征，但它也在一定程度上体现全体实例的分布特征。 lwnb 5是一种懒惰分类算法，该算法分类测试实例之前不训练分类器，只保存训练实例集。合中找到测试实例的 k 个近邻，根据 k 个近邻到测试实例的距离对它们加权并用加权后的
12、近邻训练朴素贝叶斯，类。 lwnb分类速度较慢，训练实例数量较大时这个问题尤为严重。hnb 6已不具有朴素贝叶斯或贝叶斯网的结构特 征。 hnb给类属性之外的任一属性 a 加一个隐父节点 h，其他的所有属性都通过 h 影响属性 a。本质上说， hnb a的父节点是除属性 a 之外的所有属性，只是这些属性以不同的概率作为 a 的父节点。 dfe 10是一种基于统计的判别参数学习算法，它与频率估计（ frequency estimate, fe）算法 10的唯一区别是 fe统计训练实例之前不对实例加权，而 dfe根据当前分类器对训练实例的分类正确率对实例加权统计，这使贝叶斯分类器更加拟合训练数据。
13、一般情况下使用 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
14、之间相互独立。图 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, cptcpt 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) 其中
15、 n ijk d中在属性 x i上取值为 xij c k 的实例个数， n ik = jnijk p(c=c k)用式（ 3）计算： p(c=c k)=n k/n(3) 其中： n 代表训练数据 d 中实例的总个数， n k 代表 d 中类标号取值为 c k 的实例个数。 方便实现， cpt ijk nijk n k( 00k = n k)，而不再等于 p(x i=xij |c=c k)或 p(c=c k)。由 n ijk n k 很容易计算出 p(x i=x ij |c=c k)或 p(c=c k)。 cpt ijkijk dfe ijk10在如下的伪码中给出，它实质上就是在训练实例上做 m
16、（伪码中 dfe 练数据上的迭代次数）次加权统计。gcs算 法中使用 dfe学习参数，修改的 dfe算法为mdfe(modified version of dfe)算法，修改的方法是去掉算法 dfe中标号为 1)的语句，其他不变。 有序号的程序 shift+alt+y 程序前 algorithm: learning nb by discriminative frequency estimateinput: naive bayes parameters ijk ; training dataset d , d i d ; iterator number m1） initialize each n
17、aive 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） l
18、et ijk = ijk + weight 程序后 2.2 gcs 算法 dfe m 次学习参数 ijklwnb 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-1u 1 u 0。建立朴素贝叶斯 n
19、b 0,nb 1, ,nbr。初始化 nb 0 的参数为均匀分布，然后在空间 u 0 包含的训练实例上使用 mdfe nb 0 的参数。使用 nb 0 的参数初始化 nb 1 的参数，在空间 u 1 包含的训练实例上使用mdfe nb 1 的参数，重复这个过程，直到学习完 nb r 的参数。使用 nb r 分类属于空间 u r 的测试实例 i testgcs i， i test u i，并且 i、 j，如果 ij，那么 u i u j。不严格地说， nbr（用来分类 i test u i 中的训练实例 i+1次。随着 i 值的增加，空间 u i 中的训练实例在学习 nb r 参数时所起的作用越
20、来越大，也就是说越小的局部空间内的训练实例在学习 nb r 参数时所起的作用越大。而 u i 从包含全体训练实例的全局空间 u 0 开始，因此最终学习到的 nbr 既突出体现局部空间内训练实例分布特征，又在一定程度上体现全局空间内训练实例的分布特征。 gcs 空间 u 1, ,u r 的过程可以在分类器的训练阶段进行，因而 gcs lwnb2.3 gcs-t 决策树 11是经典的分类算法之一，它从根节点开始不断划分空间，直到叶节点。决策树的每个节点 n根节点到叶节点的每一条路径中， 父节点代表的实例空间肯定包含子节点代表的实例空间， gcs u1,， u r 的要求一致。 gcs 算法叫 gcs-t，它是非懒惰算法。 gcs-t 首先使 用 c4.5和全体训练实例建立一棵决策树。决策树的每个节点代表一个局部空间，在每个节点中存储到达该节点处的所有训练实例并离散化这些训练实例中的连续型属性。然后沿着决策树从根节点到叶节点的每一条路径，使用 mdfe在逐渐缩小的局部
