类依赖实例加权朴素贝叶斯算法研究

Study on Class-Specific Instance Weighted Naive Bayes

摘要: 为削弱朴素贝叶斯中属性条件独立性假设的影响，人们提出了许多改进朴素贝叶斯的方法，实例加权是一个重要的改进方向，但现有实例权重构造是将训练样本作为一个整体进行处理，没有考虑类内实例的分布情况。因此，本文提出两种类依赖实例加权朴素贝叶斯算法：基于相关性的类依赖实例加权朴素贝叶斯(CCSIWNB)和类依赖属性值频率实例加权朴素贝叶斯(CSAVFWNB)。关于CCSIWNB，实例权重是在计算类内每个实例与该类众数实例相似度后，消除该实例与其它类众数实例的平均相似度基础上得到的。关于CSAVFWNB，实例的权重是由类内属性值频率向量和该类属性值个数向量的内积得到的。最后，采用标准UCI数据集将CCSIWNB、CSAVFWNB与朴素贝叶斯算法和其它实例加权朴素贝叶斯算法进行仿真实验，结果表明本文提出的算法在准确率上优于其它算法。

Abstract: In order to weaken the influence of attribute conditional independence hypothesis in naive Bayes, many improved naive Bayes methods have been proposed, and instance weighting is an important improvement direction. However, the existing instance weight construction considers the training sample as a whole, without considering the distribution of instances in the class. Therefore, two kinds of class-specific weighted naive Bayes algorithms are proposed in this paper: correlation- based class-specific instance weighted Naive Bayes (CCSIWNB) and class-specific attribute value frequency instance weighted Naive Bayes (CSAVFWNB). About CCSIWNB, the weight is obtained on the basis of calculating the similarity between each instance of certain class and the mode instance of the same class, and eliminating the average similarity between the instance and the mode in-stances of the other class. For CSAVFWNB, the weight of each instance is the inner product of the at-tribute value frequency vector and the attribute value number vector in the same class. Finally, CCSIWNB and CSAVFWNB are simulated with naive Bayes algorithm and other case weighted naive Bayes algorithm using standard UCI data set. The results show that the proposed algorithm is supe-rior to other algorithms in accuracy.

1. 引言

朴素贝叶斯是数据挖掘领域中常用的一种分类算法，模型不但简单，而且在解决各种问题中效果良好，且不易受噪声影响，非常稳健。在分类学习过程，分类器给每个新实例分配一个类标签，朴素贝叶斯利用贝叶斯定理计算新实例最可能的标签。假设测试实例x对应的属性值为 $a_1,a_2,\cdots ,a_m$ ，m是属性的个数， $a_j$ 是x的第j个属性值，则实例x被划分为具有最大后验概率的类别，即 $c\left(x\right)=\underset{c\in C}{\arg \max }P\left(c\right)P\left(a_1,a_2,\cdots ,a_m|c\right)$ ，其中C是类别c所有可能值的集合。在朴素贝叶斯学习中，假设给定类下所有属性都是独立的，即 $P\left(a_1,a_2,\cdots ,a_m|c\right)={\displaystyle \underset{j=1}{\overset{m}{\prod }}P\left(a_j|c\right)}$ ，因此最大后验概率分类为

$c\left(x\right)=\underset{c\in C}{\arg \max }P\left(c\right){\displaystyle \underset{j=1}{\overset{m}{\prod }}P\left(a_j|c\right)}$ ， (1)

然而，属性条件独立性假设在现实生活中往往难以达到，学者们提出了不同方面的改进，大致分为两个方向：一是基于不切实际的属性条件独立性假设；二是对不可靠的概率估计进行改进。

方向一包括结构扩展和属性加权(选择)两种方法。结构扩展主要研究属性间的关联关系，主要有网状结构的朴素贝叶斯，树扩展朴素贝叶斯，平均单依赖估测器模型，隐朴素贝叶斯等结构扩展，具体可参考文献 [1] - [6] 。属性加权是对每个属性赋予不同的权重，属性选择是从原始属性集中删除不具有预测能力或预测能力微弱的属性，即对入选属性赋予权重1，删除属性赋予权重0，所以属性选择是一种特殊的属性加权，具体可参阅文献 [7] [8] [9] [10] 。众所周知，为了避免概率为零，公式(1)中的先验概率 $P\left(c\right)$ 和条件概率 $P\left(a_j|c\right)$ 利用拉普拉斯平滑方法计算：

$P\left(c\right)=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\delta \left(c_i,c\right)}+1}{n+k}$ ， (2)

$P\left(a_j|c\right)=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\delta \left(a_{ij},a_j\right)\delta \left(c_i,c\right)}+1}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\delta \left(c_i,c\right)}+n_j}$ ， (3)

其中n为训练实例的个数，k为类的个数， $n_j$ 为第j个属性值的个数， $c_i$ 为第i个训练实例的类标号， $a_{ij}$ 为第i个训练实例的第j个属性值， $\delta \left(a,b\right)$ 是示性函数，当 $a=b$ 时，函数值为1，当 $a\ne b$ 时，函数值为0。

方向二是对不可靠的概率估计进行改进，也就是对公式(2)和(3)进行改进，具体包含两种方法：概率微调和实例加权(选择)。概率微调是先利用NB分类，然后根据每个训练分类结果对先验概率(3)进行微调，再利用微调后的概率进行NB分类，从而提高分类的准确率，具体可参阅文献 [11] [12] [13] [14] [15] 。实例加权是根据训练实例的分布或者重要程度给每个实例分配不同的权重，是先计算出所有训练实例的权重，再利用加权后的数据来构建朴素贝叶斯分类器，即先给每个实例赋予不同的权重计算概率(2)和(3)，再进行NB分类。相对概率微调法，它不仅对条件概率计算优化，同时对先验概率进行改进，而概率微调法主要对条件概率进行改进。此时公式(2)和(3)改进为：

$P\left(c\right)=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i\delta \left(c_i,c\right)}+1}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i}+k}$ ， (4)

$P\left(a_j|c\right)=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i\delta \left(a_{ij},a_j\right)\delta \left(c_i,c\right)}+1}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i\delta \left(c_i,c\right)}+n_j}$ ， (5)

其中 $w_i$ 是第i个训练实例的权重。

实例加权是在实例的维度上对数据进行处理，实例选择是一种特殊的实例加权，当实例的权重为1时，实例被保留，当权重为0时，实例被删除。实例加权(选择)是当下研究的一个热门方向，如何确定权重 $w_i$ 是问题研究的关键。考虑到不同实例与测试实例的远近程度对分类的影响也不同，往往通过计算测试实例与训练实例之间的距离来确定实例权重，如Xie等 [16] 提出了一种基于选择性邻域的惰性学习朴素贝叶斯算法，其基本思想是根据测试实例与训练实例之间属性值不同的个数将训练实例划分为不同半径的领域，在不同领域上构建多个朴素贝叶斯分类器，利用分类精度最高的分类器对测试实例分类；Frank等 [17] 提出了局部加权朴素贝叶斯算法，该算法将局部加权线性回归思想运用到朴素贝叶斯的实例加权中，实例的权重根据训练实例与测试实例之间的欧氏距离计算得到，离测试实例近的训练实例分配更多的权重。另外，考虑到实例中各属性取值的分布情况对分类的影响不一样，通过分析各实例属性分布情况确定实例权重，如Jiang [18] 等通过计算每个实例和实例众数之间的相似度确定实例权重，通过衡量每个实例与中心实例的接近程度提出了改进实例加权朴素贝叶斯算法(Instance Weighted Naive Bayes, IWNB)；Xu [19] 等通过计算属性值频率向量与属性值个数向量的内积作为实例的权重，提出了基于属性值频率加权朴素贝叶斯(Attribute Value Frequency-Based Instance Weighted Naive Bayes, AVFWNB)。杨等 [20] 考虑到众数实例非唯一和每个属性对分类的影响不一样，利用算术平均和加权平均，将属性权重嵌入到实例权重的构造中，对IWNB算法进行改进，提出了嵌入属性加权的实例加权朴素贝叶斯算法(Embedded-attribute Weighted Instance-weighted Naive Bayes, EAWIWNB)。

对于上述实例加权算法，不管是基于距离还是属性值分布构造权重，它们都是把所有实例作为一个整体进行考虑，没有考虑到类别对权重构造的影响。因此，本文在基于属性值分布情况的基础上将类别考虑进去，在不同类别下考虑属性值分布情况构造实例权重提出了两种新的类依赖实例加权算法，分别是基于相关性的类依赖实例加权朴素贝叶斯算法和类依赖属性值频率加权朴素贝叶斯算法，并利用UCI数据集进行实证分析。

下文结构安排如下：第2节介绍了基于相关性的类依赖实例加权朴素贝叶斯；第3节介绍了类依赖属性值频率加权朴素贝叶斯；第4节详细描述了实验设置和实验结果；第5节对全文进行总结。

2. 基于相关性的类依赖实例加权朴素贝叶斯

实例加权中关键的步骤是如何给每个实例分配权重，IWNB算法是通过计算每个实例和实例众数之间的相似度来确定实例的权重，它是根据属性取值分布情况来确定权重的，相对NB而言，在分类精度上有所提高。然而，对方考虑的属性取值分布情况是对整个训练样本集中考虑，没有与类别同时考虑。众所周知，训练样本都有给定的类标签，每个实例对分类的重要性和它的类标签密切相关的，所以在考虑实例中各个属性取值的分布情况时，要结合实例的类别进行考虑，每个实例与它所在类的众数实例，即类中心的相似度要大，与其它类中心的相似度要小。换句话说，对于每个实例，我们要肯定其对自身所在类的贡献，同时要消除其对其它类的影响。为此，我们参照IWNB算法的思想，结合类别分析属性取值的分布情况，同时消除类间影响(在其他类别中出现造成的冗余信息)，提出了一种基于相关性的类依赖实例加权朴素贝叶斯算法(Correlation-Based Class-Specific Instance Weighted Naive Bayes, CCSIWNB)，该算法在构造实例权重时不仅考虑到了类别来优化不可靠的概率估计，还通过消除冗余信息来弱化属性间条件独立性的影响。CCSIWNB算法首先根据训练样本的分类，将不同样本进行归类；其次参照Jiang [18] 给出的属性值众数、实例众数定义得到每类的实例众数；然后通过判断训练实例所属类别，并利用重叠度量方法计算出实例与其所属类别实例众数的相似度，并减去与其他类众数实例相似度的平均值，最后利用Sigmoid函数归一化得到该实例的权重，具体计算公式如下：

$R_i=s\left(x_i,y_j\right)-\frac{1}{k-1}{\displaystyle \underset{t=1\wedge t\ne j}{\overset{k}{\sum }}s\left(x_i,y_t\right)}$ (6)

$w_i=\frac{1}{1+{\text{e}}^{-R_i}}$ ， (7)

其中 $x_i$ 为训练集的第i个实例， $y_j$ 表示第j类实例众数，k为类别个数， $s\left(x_i,y_j\right)={\displaystyle \underset{t=1}{\overset{m}{\sum }}\delta \left(a_t\left(x_i\right),a_t\left(y_j\right)\right)}$ 表示第i个实例与第j类实例众数的相似度， ${\displaystyle \underset{t=1\wedge t\ne j}{\overset{k}{\sum }}s\left(x_i,y_t\right)}$ 表示第i个实例与其他类实例众数的相似度的和，通过求平均得到该实例与其它类间的平均冗余度，公式(7)为归一化处理， $w_i$ 为第i个实例的最终权重。CCSIWNB算法流程见下表1：

Table 1. CCSIWNB algorithm flow

表1. CCSIWNB算法流程

3. 类依赖属性值频率加权朴素贝叶斯

IWNB算法利用重叠度量方法计算训练实例与众数实例的相似度构造实例权重，获得的实例权重都为整数，数值上缺乏权重的含义，只考虑了属性值是否同时出现，没有利用属性值的频率信息，为此Xu等 [19] 学者提出了一种基于属性值频率的实例加权分类器，该方法考虑了两个方面：1)属性值的频率包含一些重要的信息，这些信息也可以用来定义训练实例的权重。2) 每个训练实例的权值与其属性值频率向量和整个训练数据集的属性值个数向量呈正相关。与IWNB相比，AVFWNB充分考虑了每个属性值的频率信息，同时涉及更大的解空间，即实例权重从整数范围扩大到了连续的正有理数，但该方法没有考虑到类别对实例权重构造的影响。

为解决以上问题，本文提出了一种基于属性值频率的类依赖实例加权朴素贝叶斯(Class-specific Attribute Value Frequency Instance Weighted Naive Bayes, CSAVFWNB)。该算法首先将训练数据按类别进行划分，接着对每个类计算出类依赖属性值频率 $f_{c,ij}$ 以及类依赖属性值个数 $n_{c,j}$ ，最后考虑按类划分之后的类依赖属性值频率向量与类依赖属性值个数向量呈正相关，将两者做内积后得到的数值作为实例权重，具体计算公式如下：

$f_{c,ij}=\frac{{\displaystyle \underset{k=1}{\overset{n}{\sum }}\delta \left(a_{kj},a_{ij}\right)\delta \left(c_k,c_i\right)}}{n_{c_i}}$ (8)

其中 $f_{c,ij}$ 为 $a_{ij}$ (第i个训练实例的第j个属性值)的类依赖属性值频率， $c_i,c_k$ 分别为第i个实例与第k个实例的类别标签， $n_{c_i}$ 为第i个实例所在类的实例总个数， $a_{kj}$ 为第k个训练实例的第j个属性值。

另外，设 $n_{c,j}$ 为第c类中第j个属性的属性值个数，则类依赖属性值数向量可表示为 $\left(n_{c,1},n_{c,2},\cdots ,n_{c,m}\right)$ 。然后，根据实例权重确定的方法，第i个训练实例权重定义为其类依赖属性值频率向量与类依赖属性值数量向量的内积(标量积)。具体计算公式为：

$w_i=\left(f_{c,i1},f_{c,i2},\cdots ,f_{c,im}\right)\cdot \left(n_{c,1},n_{c,2},\cdots ,n_{c,m}\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}\left(f_{c,ij}\ast n_{c,j}\right)}$ (9)

$w_i$ 为最终的类依赖实例权重，CSAVFWNB算法流程见表2：

Table 2. CSAVFWNB algorithm flow

表2. CSAVFWNB算法流程

4. 实验结果与分析

4.1. 实验环境与数据处理

实验环境：本文所有实验都是在win10系统，128G(SSD) + 1T(HDD)硬盘，Intel(R) Core(TM) i5-6300HQ CPU，内存16G的PC机上通过R 4.2.0版本完成。

本文在UCI数据集中选取了10个具有分类标签的数据集进行实验，见表3。这些数据集来源于现实生活的多个领域，包含各种类型的数据特征。我们首先对数据集进行预处理，读取实例个数、属性个数以及分类个数，判断是否存在缺失值，对于包含缺失值的案例，实验中采用删除该案例的方式进行处理。

Table 3. 10 experimental data sets

表3. 10个实验数据集

4.2. 结果与分析

实验结果是通过将数据集随机分成90%的训练集及10%的测试集，最后进行10折交叉验证得到结果进行平均而获得的。表4给出了四种算法分类精度的详细比较结果，第一列为实验所用测试数据集，后面几列为四种算法在这些数据集下的平均分类精确度以及方差，其中标记有“√”和“o”的符号表示当进行p = 0.05显著性水平的配对双尾t检验时，以第一种算法为参照，其他算法是否与其存在显著差异，“√”和“o”分别表示该算法在某个数据集上明显优于或输于第一种算法，平均值和输赢(W/T/L)值汇总在表格底部。

Table 4. Accuracy comparison of CCSIWNB with NB, IWNB, EAWIWNB

表4. CCSIWNB与NB、IWNB、EAWIWNB的精确度比较

Wilcoxon符号秩检验是一种常用的非参数统计检验，它适用检验成对观测数据之差是否来自均值为0的总体(产生数据的总体是否具有相同的均值)，对每个数据集的算法对的性能差异进行排序，同时忽略符号，并比较正负差异的秩。表5总结了CCSIWNB与其他三种算法的比较结果，其中V值表示基于两种算法在不同数据集下每次交叉验证得到的精确度差值且符号为正号的秩和。p值表示检验统计量大于或等于实际观察样本数据计算得到的检验统计量值的概率，符号“√”表示在该数据集下CSCIWNB和CSAVFWNB算法优于所比较的算法。

Table 5. Comparison results of Wilcoxon signed rank test between CSCIWNB and other algorithms

表5. CSCIWNB与其他算法的Wilcoxon符号秩检验比较结果

从表4与表5的比较结果可以看出，CCSIWNB算法明显优于NB，而且优于IWNB和EAWIWNB等实例加权算法，具体结果总结如下：

1) CCSIWNB在10个数据集上的平均分类准确率为82.59%，显著高于NB (80.07%)以及其他两种实例加权算法IWNB (81.08%)，EAWIWNB (80.4%)。

2) 基于配对双尾t检验，CCSIWNB优于NB (4胜6平0负)、IWNB (3胜6平1负)，EAWIWNB (4胜6平0负)。

3) 根据Wilcoxon符号秩检验结果，我们可以得出结论，当水平显著性为α = 0.05时，CCSIWNB显著优于NB、IWNB和EAWIWNB。

Table 6. Accuracy comparison of CSAVFWNB with NB, IWNB and AVFWNB

表6. CSAVFWNB与NB、IWNB、AVFWNB的精确度比较

Table 7. Comparison results of Wilcoxon signed rank test between CSAVFWNB and other algorithms

表7. CSAVFWNB与其他算法的Wilcoxon符号秩检验比较结果

从表6与表7的比较结果可以看出，CSAVFWNB算法明显优于NB，而且优于IWNB和AVFWNB等算法，实验结果总结如下：

CSAVFWNB在10个数据集上的平均分类准确率为81.72%显著高于NB (80.36%)，IWNB (81.14%)，AVFWNB (79.92%)。

基于配对双尾t检验，CSAVFWNB优于NB (3胜7平0负)、IWNB (3胜6平1负)，AVFWNB (3胜6平1负)。

根据Wilcoxon符号秩检验结果，我们可以得出结论，当水平显著性为α = 0.05时，我们提出的CSAVFWNB显著优于NB、IWNB和AVFWNB。

5. 结论

为了弱化不切实际的属性条件独立性假设以及改进不可靠的概率估计，本文提出了两种类依赖实例加权方法，CCSIWNB算法不仅考虑了类别，还针对属性间的相关性在一定程度上弱化了属性条件独立性假设。CSAVFWNB算法主要考虑类别与属性值频率之间存在一定的联系，同时类依赖属性值频率与类依赖属性值个数之间仍然呈正相关。根据实验结果表明，本文提出的两种类依赖实例加权算法在10个UCI数据集上皆优于NB、IWNB、EAWIWNB以及AVFWNB算法。我们提出的算法综合类别和属性取值的分布情况，但没有考虑到各个实例与测试实例的关系，从实例对分类的作用来看，如果能够综合三者进行考虑，效果应该会更好。因此，如何综合三者考虑构造实例权重，值得后期进一步研究。

基金项目

国家自然科学基金(11661003)；江西省自然科学基金(20192BAB201006)。

NOTES

^*通讯作者。