分类在生物信息学、图像识别、医疗诊断、自然语言处理等领域有着广泛的应用^[1-2]。分类的目标是构造一个分类器，对由属性集描述的实例指定最合适的类标签。贝叶斯网络^[3]提供了一种表示因果关系的方法，它结合图模型理论和统计学来表达随机变量之间的不确定性知识，并高效地执行推理任务。由于具有坚实的理论基础以及综合先验信息和数据样本信息的能力，利用贝叶斯网络处理分类问题由来已久。朴素贝叶斯分类器^[4]是一种简单而有效的贝叶斯网络，它假设各个属性变量在给定分类变量后，是相互条件独立的。朴素贝叶斯分类器对很多问题有着很好的分类准确性，但属性变量间的条件独立性在大多数实际问题中明显不成立。因此，通过对朴素贝叶斯分类模型的改进，使得分类器的分类准确性得到进一步提升是机器学习和数据挖掘的研究热点之一。

通常存在2类方法改进朴素贝叶斯分类器：第一类方法是选择特征子集^[5-6]，寻找一个最佳的自变量子集来构造模型；第二类方法是放松独立性假设^[7-9]，改进贝叶斯网络分类器模型，使得模型对自变量的相关性结构有更为准确和灵活的建模，从而提高模型的分类准确性。另外，还有把这两种方法结合起来的混合式学习方法^[10]。当前，对于第2类方法的研究比较多。Friedman^[7]研究了具有树结构的TAN (tree augmented naïve bayes)分类器，它放松了朴素贝叶斯分类模型中的独立性假设条件，扩展了朴素贝叶斯网络的结构。允许每个属性结点最多可以依赖于1个非类结点。TAN具有较好的综合性能，体现了学习效率与分类精度之间的一种适当的折衷。BAN^[8]进一步扩展了TAN结构，允许属性之间可以形成任意有向无循环图，使其表示属性之间依赖关系的能力增强，可以进一步提高分类准确性。但是，BAN结构的学习需要高维计算，在小采样数据集上，学到的结果模型可能存在较大误差，影响分类准确性。

提出改进的最大相关最小冗余技术，用于确定每个属性结点的候选连接，在这个过程中，改进的最大相关最小冗余技术使用三维计算代替高维计算；同时，为了减小BAN分类器学习的计算维度，本文提出了一种受限的BAN分类器k-BAN，即允许每个属性结点最多可以依赖k(k＜＜N，N为属性结点个数)个非类结点，提高了计算的可靠性和健壮性，使BAN分类器适用于小采样数据集。并且，本文提出的受限BAN分类器学习算法(k-BAN)对结点与其候选父结点集之间的所有连接实现了穷尽查找，选择使分类准确性改进最大的连接关系集，由于每次加入多条有向边(k≥edges≥0)，与通用启发式学习算法(每次最多加入1条边)相比较，进一步减小了产生局部最优化结果的可能性。

1 相关概念和定理 1.1 有限样本数据集合

假设，存在关于一组变量X = {x₁，x₂，…，x_n}的采样数据集合D，P(x_i，x_k，…，x_j)，(1≤i，k，j≤n)表示变量组({x_i，x_k，…，x_j)}(1≤i，k，j≤n)之间的联合概率分布。采样数据集合D称为有限样本数据集合，当且仅当，从采样数据集合D，只能准确计算低维(维度≤3) 变量组之间的联合概率值，并对于较高维(维度＞3) 变量组之间的联合概率不能准确计算，只能获得近似值。

1.2 贝叶斯网络分类器模型(BAN)

BAN进一步扩展了NB和TAN，它允许属性结点之间可以形成任意的有向无循环图，而不只是树，使其表示依赖关系的能力增强，从而进一步增强分类的正确性。Friedman提出conditional log likelihood(CLL)计分方法^[7]，学习BAN分类器。Cheng和Greiner提出基于条件独立性测试(conditional mutual information，CMI)^[8]的BAN学习算法。BAN学习算法都需要高维计算，因此，在大多数测试数据集，特别是在高维小采样数据集上，其分类效果较NB和TAN差。

1.3 最大相关最小冗余和最大互信息关系定理

从信息论上看，特征选择中，最大互信息方法^[11]就是找到一个含有m个特征的特征集合S_m，使其与目标变量t的互信息最大，定义为：$\mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{S_m}} \;I({{S}_m};{t})$。

最大相关最小冗余是特征选择中涉及的概念^[12]，定义为

公式1 假设从特征集合X中已经选择了m-1个特征，用S_m-1表示。目标变量为t，目标是从特征集合X-S_m-1中，选择一个特征${{x}_m} = \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{x_j} \in X - {S_{m - 1}}} \left[{I({{x}_j};{t})-\frac{1}{{m-1}}\sum\limits_{{x_i} \in {S_{m-1}}} {I({{x}_j};{{x}_i})} } \right]\;$。

公式2 在每次特征选择，只选择一个特征的条件下，最大相关最小冗余方法最佳近似于

$ {{x}_m} = \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{x_j} \in X - {S_{m - 1}}} \left[{I({{x}_j};{t})-\frac{1}{{m-1}}\sum\limits_{{x_i} \in {S_{m-1}}} {I({{x}_j};{{x}_i})} } \right]\\ \approx \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{x_j} \in X - {S_{m - 1}}} [{I}{\rm{(\{ }}{{S}_{m-1}}{\rm{, }}{{x}_j}{\rm{\} ;}}{t}{\rm{)}}]。$

公式2相似于最大相关最小冗余特征选择公式1，公式(2) 的第二项要求特征集合中的各个特征最大相互独立(即最小冗余)，同时，第一项要求特征集合中的每个特征最大依赖于目标变量C。Peng和Ding通过实验已经验证^[12]，在小采样数据集上，如果一次只加入一个特征(即贪婪算法)，那么MRMR准则是最大互信息方法的近似最佳实现方案。

2 改进最大相关最小冗余特征选择技术和受限BAN模型 2.1 改进的最大相关最小冗余特征选择技术

假设分类属性为C，目标属性为t，从属性集合X中已经选择了m-1个特征，用S_m-1表示；从属性集合X-S_m-1中，选择一个属性

$ {{x}_m} = \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{x_j} \in X - {S_{m - 1}}} \left[{I({{x}_j};{t}\left| C \right.)-\frac{1}{{m-1}}\sum\limits_{{x_i} \in {S_{m-1}}} {I({{x}_j};{{x}_i}\left| C \right.)} } \right]\;, $

(1)

使得{S_m-1，x_m}属性集合与目标属性t的条件互信息近似最大，即${{x}_m} = \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{{x_j} \in X - {S_{m - 1}}} \left[{I(\{ {{S}_{m-1}}, {{x}_j}\} ;{t}\left| C \right.)} \right]\;$。

2.2 受限BAN分类模型(k-BAN)

贝叶斯分类模型是一种典型的基于统计方法的分类模型，它将事件的先验概率与后验概率联系起来，利用先验信息和样本数据信息确定事件的后验概率。

假设U={A₁，A₂，…，A_n，C}是离散随机变量的有限集，其中A₁，A₂，…，A_n是属性变量，类变量C的取值范围为{c₁，c₂，…，c_l}，a_i是属性A_i的取值，Π_Ai表示A_i的父结点集合(不考虑C)。实例x_i={a₁，a₂，…，a_n}属于类c_j的概率，可表示为

$ \begin{array}{l} P({\mathit{c}_j}\left| {{a_1}, {a_2}, \cdot \cdot \cdot, {a_n}} \right.) = \frac{{P({\mathit{a}_1}, {\mathit{a}_2}, \cdot \cdot \cdot, {a_n}\left| {{c_j}} \right.)\mathit{P}{\rm{(}}{\mathit{c}_j}{\rm{)}}}}{{P({\mathit{a}_1}, {\mathit{a}_2}, \cdot \cdot \cdot, {\mathit{a}_n})}} = \\ \alpha P({\mathit{c}_j})P({\mathit{a}_1}, {\mathit{a}_2}, \cdot \cdot \cdot, {a_n}\left| {{c_j}} \right.) = \alpha P({\mathit{c}_j})\mathop \prod \limits_{i = 1}^n P({\mathit{a}_i}{\left| \mathit{\Pi } \right._{{A_i}}}, {\mathit{c}_j})。\end{array} $

因此，给定某一实例{a₁，a₂，…，a_n}，选择使$P({\mathit{c}_j})\mathop \prod \limits_{i = 1}^n P({\mathit{a}_i}{\left| \mathit{\Pi } \right._{{A_i}}}, {\mathit{c}_j})$最大的类c_j作为该实例的类标签。

受限BAN分类模型(k-BAN)假设|Π_Ai|≤k，其中(i=1，…，n)。当k=0时，受限BAN模型等价为NB分类模型；当k=1时，受限BAN模型等价为TAN分类模型；当k=n时，受限BAN模型等价为不受限BAN分类模型。其中，A_i候选父结点集合S_m为{A_l1，A_l2，…，A_lk}，A_lj≠A_i，j=1，…，k，使得I(S_m，A_i|C)条件互信息最大，即，$\mathop {{\rm{argmax}}}\limits_{{S_m}} I({S_m};{A_i}\left| C \right.)$。

3 受限BAN分类器学习算法

受限BAN分类器学习算法k-BAN实现了4个方面的改进。

1) 使用改进的最大相关最小冗余特征选择技术，即公式(1)，替换基于最大条件互信息的CLL或CMI公式，获得给定变量的候选父结点集合，从而将确定候选父结点集合的计算维度降到三维，在小采样数据集上，提高了计算的可靠性和健壮性。

2) 提出受限BAN模型，限制每个结点的父结点集合中变量的个数不超过k，将条件概率P(a_i|Π_i，C)的计算维度降到k+1，当k较小时，在小采样数据集上，进一步提高了计算的可靠性和健壮性。

3) 本算法的每次贪婪查找学习到多条有向连接边(0≤edges≤k)，与通用BAN学习算法(每次贪婪查找最多学习到1条有向连接边)相比较，能够更容易地跳出局部最优值。

4) 每次贪婪查找，通过对结点和其候选父结点之间的所有有向连接边集进行穷尽搜索，进一步减小了所学分类器的局部最优化。

3.1 算法描述

输入：分类结点为C，n个结点变量集合X={A₁，A₂，…，A_n}，X_handled表示已经处理过的结点集合，A_best表示在一次贪婪查找后，要加入到X_handled的结点；cπ_i表示A_i的候选父结点集合，π_i表示A_i的当前父结点集合；E_im表示A_i与cπ_i之间任意一个有向连接边集，E_i表示A_i与cπ_i之间的所有的有向边集的集合E_i={E_im}，(0≤m＜3^k)，S_edges表示一次贪婪查找中，可能加入到当前分类器的所有有向连接边集的集合S_edges={E_i}，(1≤i≤n)；E_cur表示当前分类器Class_cur的有向边集，E_new表示新分类器Class_new的有向边集；Accuracy_cur表示当前分类器Class_cur的分类性能，Accuracy_new表示新分类器Class_new的分类性能；Class_best表示当前获得的分类性能最好的分类器，Accuracy_best表示Class_best的分类性能；布尔变量isModified=true表示当前的贪婪查找获得了分类性能更好的分类器，否则，表示贪婪查找过程结束。MI(n，n)是一个n·n的二维数组。

约束条件：|π_i|≤k，1≤i≤n,

输出：受限的BAN分类器。

算法：

/*第一部分：初始化*/

  /*求出结点间的两两条件互信息*/

  1)  initialize MI(n，n) to 0；

  2)  for i=1 to n do

  3)    for j= i+1 to n do

  4)    begin

  5)      MI[i，j]=MI[j，i]= I(x_i，x_j|C)；

  6)    end for

  7)  end for

  /*初始化当前分类器为朴素贝叶斯分类器，并计算NB的分类性能*/

  8)  Class_cur=NB；Accuracy_cur=Accuracy_NB；π_i=Φ，(1≤i≤n)；X_handled=Φ；；

/*第二部分：进行贪婪查找，每次加入一个结点的多条有向连接边，使获得的分类器的分类性能最好，直到不能找到分类性能更好的分类器为止*/

  9)  do { //一次贪婪查找过程

  10)      for each A_i，(1≤i≤n)

  11)         cπ_i=Φ；

  12)      end for

  13)      S_edges=Φ；

            /*求出每个未处理结点A_i的cπ_i*/

  14)      for each A_i，A_i$ \notin $X_handled，1≤i≤n

  15)        while |cπ_i|+|π_i|＜k

  16)          $y = \mathop {{\rm{argmax}}}\limits_{{A_j} \in X - {A_i} - c{\pi _i} - {\pi _i}} \left[ {MI[{A_i},{A_j}\left| C \right.] - \frac{1}{{\left| {{\pi _i}\left| { + \left| {c\left. {{\pi _i}} \right|} \right.} \right.} \right.}}\sum\limits_{A \in {\pi _i} + c{\pi _i}} {MI[A,{A_j}\left| C \right.]} } \right]\;$

  17)          cπ_i=cπ_i∪{y}；

  18)        end while

  19)      end for

  /*对每个cπ_i，确定A_i与cπ_i结点之间的所有有向连接边集的集合E_i，加入S_edges*/

  20)      for each cπ_i，cπ_i≠Φ，1≤i≤n

  21)        acquire all the sets E_i of directed edges between A_i and cπ_i；

  22)        S_edges=S_edges∪E_i；

  23)      end for

  /*对于每个有向连接边集，将其加入当前分类器，获得一个新的分类器，并进行比较处理*/

  24)      Class_best=Class_cur；Accuracy_best=Accuracy_cur；A_best=Φ；stModified=false；

  25)      for each E_im，E_im∈S_edges，1≤i≤n。

  26)      acquire a new classifier Class_new，E_new=E_cur∪E_im；

           /*判断分类器Class_new是否满足受限BAN的约束条件*/

  27)      for each nodeA_j(1≤j≤n)

  28)        Compute the number ParentNum_j of parent nodes for A_j in the Class_new；

  29)      end for

  30)      if all ParentNum_j≤k，(1≤j≤n) then

             /*如果满足约束条件，进行如下比较处理：*/

  31)        compute Accuracy_new for Class_new；

  32)      if Accuracy_new＞Accuracy_best then

  33)          Class_best=Class_new；Accuracy_best=Accuracy_new；A_best=A_i；

  34)          stModified=true；

  35)        end if

  36)      end if

  37)   end for // corresponding to line 25)

  /*如果在一次贪婪查找中，获得了一个分类性能更好的分类器，则如下处理：*/

  38)   eifstModified==true then

  39)      Class_cur=Class_best，Accuracy_cur=Accuracy_best，X_handled=X_handled∪{A_best}；

  40)      for each node A_j(1≤j≤n)

  41)        Update π_j according to the Class_cur；

  42)      end for

  43)   endif

  44) while，                                 (stModified==true)；

  45) return Class_cur；

受限BAN分类器学习算法分为2个部分：

第一部分主要包括计算结点间的互信息，初始化分类器为朴素贝叶斯分类器，并计算其分类性能；

第二部分采用贪婪启发式方法，结合改进的最大相关最小冗余技术，确定结点的候选父结点集(结点个数不超过k)，穷尽查找每个结点和其候选父结点之间的有向连接边集，把分类性能近似最佳的有向连接边集加入当前分类器中，直到无法获得具有更好分类性能的分类器。

注：算法中第(21) 行的解释：假设结点A_i的候选父结点集合cπ_i={A₁，A₂}，那么，A_i与cπ_i结点间的所有有向连接边集合E_i={E_im，1≤m≤3^|cπ_i|}，其中，E_i1=Φ；E_i2={A₁→A_i}；E_i3={A_i→A₁}；E_i4={A₂→A_i}；E_i5={A_i→A₂}；E_i6={A₁→A_i，A₂→A_i}；E_i7={A₁→A_i，A_i→A₂}；E_i8={A_i→A₁，A₂→A_i}；E_i9={A_i→A₁，A_i→A₂}。

4 实验结果和分析

实现了受限BAN分类器k-BAN(k=3)、NB分类器、TAN分类器和BAN分类器。在配置为Pentium5 3GHz，2G RAM，Windows XP的计算机上进行实验，并且在算法的分类正确性上给出比较结果。考虑到，在小采样数据集上，P(a_i|Π_i，C)的可靠性和健壮性，选取较小的k值，k=3。

实验数据选自UCI资源库。表 1列出了每个数据集的实例个数、类个数、属性个数以及是否有丢失值等数据信息。由于算法不能处理连续型数值数据，因此，使用MLC++中^[13]的离散化工具对连续型数值离散化。在有丢失值的数据集中，将所有的丢失值作为一个单独的值来处理。

实验的主要目的是对k-BAN(k=3) 与NB，TAN和BAN分类器在每个数据集上的分类正确率进行比较。每个分类器的分类正确率是在测试集上成功预测的实例占总实例的百分比，采用10重交叉验证估计分类器的正确率。4个分类器在每个数据集上分别测试了20次，每次实验采用不同的10重划分。表 2列出了20次测试的平均正确率及标准方差。

从结果比较中可以看出，对于采样充分的大数据集(mushroom nursery)，BAN的分类正确性最好，k-BAN(k=3) 次之，但是分类正确性优于TAN和NB。当数据集合采样充分时，由于可以准确地计算变量组的联合概率值，因此，不受限的(即，无前提假设的)BAN分类模型的分类正确性好于受限的(即，存在前提假设的)BAN分类模型；限制条件弱的(例，3-BAN(k=3))BAN分类模型的分类正确性好于限制条件强(例，TAN(k=1)，NB(k=0))的BAN分类模型。

对于有限样本数据集，k-BAN(k=3) 分类性能优于BAN，TAN和NB。当数据集合样本数目相对变量维度较少时，只能准确计算低维变量组(维度3) 的联合概率值，3-BAN分类正确性优于BAN；但，3-BAN的分类正确性优于限制条件强(例，TAN(k=1)，NB(k=0))的BAN分类模型。

5 结语

在贝叶斯分类器学习中，正确性是评估学习算法优劣的主要指标。通过采用改进的最大相关最小冗余特征选择技术建立候选父节点集合和限制父结点的个数，减少了高维计算。同时，提出的算法在每次贪婪查找中，学习到多条有向连接边(最多不超过k条)，能够更好地减小所学分类器的局部最优化；而且，每次贪婪查找，通过对结点和其候选父结点之间的所有有向连接边集进行穷尽搜索，进一步减小了所学分类器的局部最优化。因此，在维数较高和小采样数据集上，受限BAN学习算法在实际测试中，与NB\\TAN\\BAN分类器比较，体现出了更好的分类正确性。