# A Bayesian Classifier Learning Algorithm Based on Optimization Model

Authors: Sanyang Liu; Mingmin Zhu; Youlong Yang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Naive Bayes classifier is a simple and effective classification method, but its attribute independence assumption makes it unable to express the dependence among attributes and affects its classification performance. In this paper, we summarize the existing improved algorithms and propose a Bayesian classifier learning algorithm based on optimization model (BC-OM). BC-OM uses the chi-squared statistic to estimate the dependence coefficients among attributes, with which it constructs the objective function as an overall measure of the dependence for a classifier structure. Therefore, a problem of searching for an optimal classifier can be turned into finding the maximum value of the objective function in feasible fields. In addition, we have proved the existence and uniqueness of the numerical solution. BC-OM offers a new opinion for the research of extended Bayesian classifier. Theoretical and experimental results show that the new algorithm is correct and effective.


---

## Body

## 1. Introduction

With the development of information technology, in particular the progress of network technology, multimedia technology and communication technology, massive data analysis, and processing become more and more important. Since Bayesian network as classifier has a solid mathematical basis and takes the prior information of samples into consideration, it is now one of the hottest areas in machine learning and data mining fields. Moreover, it has been applied to a wide range of tasks such as natural spoken dialog systems, vision recognition, medical diagnosis, genetic regulatory network inference, and so forth [1–8]. Naive Bayes (NB) [9–11] is a simple and effective classification model. Although its performance can be comparable with other classification methods, such as decision trees and neural network, its attribute of independence assumption limits its real application. Extending its structure is a direct way to overcome the limitation of naive Bayes [12–14], since attribute dependencies can be explicitly represented by arcs. Tree-augmented naive Bayes (TAN) [9] is an extended tree-like naive Bayes in which the class node directly points to all attribute nodes and an attribute node can have only one parent from another attribute node. On this basis, Cheng et al. presented Bayesain-network-Augmented naive Bayes (BAN) [15, 16] which further expanded the tree-like structure of TAN classifier and allowed the dependency relation between any two attribute nodes. In constructing BAN, they use a scoring function based on the minimum description length principle. Unfortunately, the search for the best network is performed in the space of all possible networks, and the number of elements in this space increases exponentially with the number of nodes, finding the best structure is NP-hard [17, 18].Based on above analysis, this paper presents a Bayesian classifier learning algorithm based on optimization model (BC-OM) for the first time, inspired by constraint-based Bayesian network structure learning method [19–22]. We discuss the classification principles of Bayesian classifier from a new view. Because chi-squared tests are a standard tool for measuring the dependency between pairs of variables [23], BC-OM first introduces the chi-squared statistic to define the dependence coefficients of variables. Then, it uses the dependence coefficients to construct an overall measure of the dependence in a classifier structure, from which the objective function for our optimization model can be derived. Therefore, a problem of searching for an optimal classifier can be turned into finding the maximum value of the objective function in feasible fields. The function extremum corresponds to the best classifier. Finally, BC-OM improves the efficiency of classification and delete irrelevant or redundant attributes by using the d-separation rule of Bayesian network. Theoretical and experimental results show the proposed algorithm is not only effective in improving the accuracy, but also has a high learning speed and simple solving procedure.The remainder of this paper is organized as follows. Section2 reviews the existing Bayesian network classifiers. We describe our algorithm and its theoretical proofs in Section 3. Section 4 details the experimental procedures and results of the proposed algorithm. Finally, in Section 5, we conclude and outline our future work.


## 2. Background

In this section, we discuss previous work that is relevant to this paper, and describe some of the notations used firstly. We use boldface capital letters such asV, E, X for sets of variables. General variables are denoted by italic capital letters or index italic capital letters X, R, V-; specific values taken by these variables are denoted x-, r-, v-. Specially, we use the same italic letters X, Y, V- for graph nodes which corresponds with the random variables.Classification is a basic task in data analysis and pattern recognition that requires the construction of a classifier, that is, a function that assigns a class label to instances described by a set of attributes. The induction of classifiers from data sets of preclassified instances is a central problem in machine learning. LetV={V1,V2,…,Vn} represent the variable set which corresponds with the training data set D. We assume that V1 is the class variable and {V2,V3,…,Vn} is the set of attribute variables. Bayesian networks are often used for classification problems, in which the main task is to construct the classifier structure G from a given set of training data with class labels and then compute the posterior probability PG(v1∣V2,V3,…,Vn), where v1 is the value that V1 takes. Thus, it only needs to predict the class with the highest value of probability PG(v1∣V2,V3,…,Vn), that is,
(1)v1*=argmaxv1∈dom(V1)PG(v1∣V2,V3,…,Vn).
According to Bayes theorem, maximizing PG(v1∣V2,V3,…,Vn) is equivalent to maximizing P(v1)·PG(V2,V3,…,Vn∣v1). The difference between the existing Bayesian classifiers is the computing mode of PG(·).Figure1 schematically illustrates the structures of the Bayesian classifiers considered in this paper. In naive Bayes, each attribute node has the class node as its parent, but does not have any parent from attribute nodes. Computing PG(V2,V3,…,Vn∣v1) is equal to ∏‍i=2nPG(Vi∣v1). Because the values of PG(v1) and PG(Vi∣v1) can be easily estimated from training examples, naive Bayes is easy to construct. However, its prerequisite of condition independence assumption and data completeness limit its real application. TAN takes the naive Bayes and adds edges to it in which the class node directly points to all attribute nodes and an attribute node can have only one parent from another attribute node. Computing PG(V2,V3,…,Vn∣v1) is equivalent to ∏‍i=2nPG(Vi∣Vj,v1), where Vj∈{V1,V2,…,V(i-1)}. It is an efficient extend of naive Bayes. BAN is a specific case of general Bayesian network classifier, in which the class node also directly points to all attribute nodes, but there is no limitation on the arcs among attribute nodes (except that they do not form any directed cycle). It is clear that TAN and BAN are useful to model correlations among attribute nodes that cannot be captured by naive Bayes. They embody a good tradeoff between the equality of the approximation of correlations among attributes and the computational complexity in the learning stage. In addition, existing algorithms using the same idea to construct the structure of Bayesian classifier which first learn the dependent relationships among attribute variables using Bayesian network structure learning algorithm, then add the class variable as the root node of the network. It is equivalent to learning the best Bayesian network among those in which V1 is a root. Thus, even if we could improve the performance of a naive Bayes classifier in this way, the computational effort required may not be worthwhile.Illustration of NB, TAN, and BAN structures.
(a)
NB
(b)
TAN
(c)
BANBased on above analysis, this paper presents an optimization model to learn the structure of Bayesian classifier, which inspired by constraint-based Bayesian network structure learning method. It is the first time that a problem of structural learning for a Bayesian classifier is transformed into its related mathematical programming problem by defining objective function and feasible region. And, we also propose a new method to measure the dependent relationships between attributes. The theoretical basis of this method is established by Theorem1 [24].Theorem 1.
Given a data setD and a variable set V={V1,V2,…,Vn}, if the hypothesis that Vi and Vj are conditionally independent given Vk is true, then the statistics Uij∣k2=2∑a,b,cNijkabclog[NijkabcNkc/(NikacNjkbc)] approximates to a distribution χ2(l) with l=(ri-1)(rj-1)rk degrees of freedom, where ri, rj, and rk represent the number of configurations for the variables Vi, Vj, and Vk, respectively. Nijkabc is the number of cases in D where Vi=a, Vj=b, and Vk=c. Nikac is the number of cases in D where Vi=a and Vk=c and Nkc is the number of cases in D where Vk=c.


## 3. A Bayesian Classifier Learning Algorithm Based on Optimization Model

### 3.1. Optimization Model Design

In this subsection, we give some basic concepts and theorems which is the foundation of the method proposed in this paper.A Bayesian classifier is a graphical representation of a joint probability distribution that includes two components. One is a directed acyclic graphG=(V,E), where the node set V={V1,V2,…,Vn} represents the class and attribute variables, and the edge set E represents direct dependency relationships between variables. The other is a joint probability distribution Θ={θi∣θi=P(Vi∣pa(Vi)),i=1,2,…,n} that quantifies the effects of pa(Vi) has on the variable Vi in G, where pa(Vi)={Vj∣Vj→Vi∈E}. We assume that V1 is the class node and {V2,V3,…,Vn} is the set of attribute nodes. The structure of G reflects the underlying probabilistic dependence relations among the nodes and a set of assertions about conditional independencies. The problem of data classification can be stated as follows: the learning goal is first to find the classifier structure that best matches D and estimate the parameters using the training data set D, then to assign class label to test instances. Since G is a directed acyclic graph, it can be represented by a binary node-node adjacency matrix X=(xij). Entry (i,j) is 1 if there is a directed arc from node i to node j, and 0 otherwise. That is,
(2)xij={1,ifVi→Vj∈E,0,ifVi→Vj∉E.LetR=X+X2+⋯+Xn be the sum of powers of the adjacency matrix. Entry rij∈R is equal to the number of directed paths from node Vi to node Vj in the graph [25].We wish to be able to use a mathematical programming formulation, and this formulation requires that we are able to measure the impact of adding or removing a single arc from the network. In order to approximate the impact of adding such an arc, we define the dependence coefficient.Definition 2.
Given a data setD and a variable set V={V1,V2,…,Vn}, we define the dependence coefficient cijα between variables Vi and Vj as cijα=mink≠i,j{Uij|k2-χij∣k,α2}, where Uij∣k2 is the U2 statistics of Vi and Vj given Vk, χij∣k,α2 is the critical value at the significance level α of a χ2 distribution with (ri-1)(rj-1)rk degrees of freedom.Obviously,cijα is a conservative estimate of the degree of dependence between two nodes. If cijα>0, then, regardless of the other variable involved, there is statistically significant dependence between Vi and Vj, so there should be an arc between them. If cijα<0, then there is at least one way of conditioning the relationship so that significant dependence is not present. We define C=(cij) the dependence coefficient matrix corresponding to the variable set V, that is,
(3)cij={cijα,ifi≠j,0,otherwise.Lemma 3.
Given a data setD and a variable set V, Vi and Vj are locally conditionally independent at the significance level α if and only if there is a node Vk∈V such that Uij|k2<χij|k,α2.The proof of Lemma3 can be obtained directly by Definition 2 and chi-square hypothesis test. According to Lemma 3, Vi and Vj are locally conditionally independent at the significance level α if and only if there is a node Vk∈V such that cij<0. Further, Vi and Vj are globally conditionally independent at the significance level α if and only if Uij∣k2<χij∣k,α2 for any k≠i,j. Based on this, we use the dependence coefficients to construct an overall measure of the dependence which will be treated as the objective function for our mathematical program.Definition 4.
For a Bayesian classifier with adjacency matrixX=(xij), the global dependence measure of the network is given by
(4)ℱ(X,α)=∑i=1n‍∑j=1,j≠in‍cijxij.According to the measure of Definition4, if Vi and Vj are conditionally independent, by Lemma 3  cij<0, and hence, adding an arc between Vi and Vj decreases the value of ℱ. Thus, we wish to find the feasible solution which increases ℱ. The optimal solution corresponds to the best classifier structure. We next explain what constitutes feasible network.Given the variable setV={V1,V2,…,Vn}, V1 is the class node and {Vi,i=2,…,n} is the set of attribute nodes. A directed network is a feasible classifier structure if and only if the following conditions are satisfied:(1)
for any attribute nodeVi∈V,i=2,…,n, there is no directed edge from Vi to V1;(2)
for any nodeVi∈V,i=1,2,…,n, there is no directed path from Vi to Vi, namely, the graph is acyclic;(3)
there exists at least one attribute nodeVi∈V,i=2,…,n which is dependent with class node V1, namely, there is an attribute node Vi such that Vi can be reached from V1 by a directed path.In order to incorporate the requirements of the above three conditions into a mathematical programming formulation, we express them by the following constrains:(1)
∑i=2nxi1=0;(2)
∑i=1nrii=0;(3)
∑j=2nr1j≥1.The feasible classifiers are those that satisfy constrains (1)–(3). Thus, learning best Bayesian classifier can be transformed into the following related mathematical programming problem, where the objective function is a global dependence measure of the network, and the feasible region is the set of classifiers with reachability constrains (1)–(3), that is,(OM)maxℱ(X,α)=∑i=1n∑j=1,j≠incijxij,s.t.∑i=2nxi1=0,∑i=1nrii=0,∑j=2nr1j≥1,xij∈{0,1}.


### 3.2. BC-OM Algorithm and Its Correctness

In this subsection, we present the main algorithm of this paper. Our method starts with finding the best Bayesian classifier by solving the above optimization model. Second, we use the d-separation rule of Bayesian network to delete irrelevant or redundant attributes in the network which have low dependence degree with the class variable. The parameters of modified network can be estimated. Third, classification is done by applying obtained classifier to predict the class label of test data. We prove the correctness of proposed method under the faithfulness assumption for the data distribution.Given a directed acyclic graphG=(V,E) where V is the node set and E the set of directed edges. A path ρ between two distinct nodes V1 and Vl is a sequence of distinct nodes in which the first node is V1, the last one is Vl and two consecutive nodes are connected by an edge, that is ρ=V1e1V2⋯el-1Vl where ei denotes Vi→Vi+1 or Vi←Vi+1 for i=1,2,…,(l-1).Definition 5.
A pathρ is said to be d-separated by a set Z in a directed acyclic graph G if and only if (1)  ρ contains a “head-to-tail meeting”: Vi→Vj→Vk or a “tail-to-tail meeting”: Vi←Vj→Vk such that the middle node Vj is in Z, or (2)  ρ contains a “head-to-head meeting”: Vi→Vj←Vk such that the middle node Vj is not in Z and no descendant of Vj is in Z. Specially, two distinct sets of nodes X and Y are said to be d-separated by a set Z in G if Z d-separates every path from any node in X to any node in Y [26].In this paper, we assume that all the distributions are compatible withG [27]. We also assume that all independencies of a probability distribution of variables in V can be checked by d-separations of G, called the faithfulness assumption [26]. The faithfulness assumption means that all independencies and conditional independencies among variables can be represented by G. Now we formally describe our method in the following Algorithm 1.Algorithm 1:BC-OM.
(
1
)  Input: Data set D; Variable set V = (V1, V2,…, Vn) (V1 is the class node and others are attribute
nodes).
(
2
) For any pair of variable Vi and Vj contained in V, calculate the dependence coefficient cij by
Definition2;
(
3
) Solve the mathematical programming (OM) and obtain the optimal solution X*=(xij);
(
4
) Build the classifier structure G* = (V, E*) by X*=(xij);
(
5
) For any variable Vi∈V, i≠1, if there is a subset Z⊂V∖{V1, Vi} such that Z d-separates Vi and
V1, then delete Vi in G*, update G* as V=V∖{Vi}, E*=E*∖{Vi→Vj or Vj→Vi, Vj∈ adj(Vi)};
(
6
)  Output: The built classifier G* = (V, E*).From the detailed steps of BC-OM, we can see that BC-OM classifier relaxes the restrictions on condition variable and further meets the need of practical application. Since its network structure is similar to that of BAN’s, BC-OM does not need to build all possible networks in which class node is a root and removes irrelevant or redundant nodes from the network before the process of estimating the network parameters, which greatly reduces the calculation for posterior probability of class variable. In fact, the training process of BC-OM is different from other BN classifiers. Its main task is to solve the mathematical programming(OM). To create the dependence coefficient matrix corresponding to (OM), BC-OM needs to compute the conditional statistics Uij∣k2. Moreover, just as other constraint based algorithms, the main cost of BC-OM is the number of conditional independence tests for computing the dependence coefficients of any two variables in step 2. The number of conditional independence tests is Cn2·Cn-21 and the computing complexity is O(n3). The total complexity of BC-OM is bound by O(n3·N), where n is the number of variables in the network and N is the number of cases in data set D. In principle, BC-OM is a structure-extension-based algorithm. In BC-OM, we essentially extend the structure of TAN by relaxing the parent set of each attribute node. Thus, the resulting structure is more complex than TAN, but more simple than BAN. Therefore, BC-OM is a good tradeoff between the model complexity and accuracy compared with TAN and BAN. Next, we prove the correctness of BC-OM algorithm under the faithfulness assumption.The next two results establish the existence and uniqueness properties of solution to(OM).Theorem 6.
Let𝒳={(xij)n×n∣xij∈{0,1}}. There always exists an X∈𝒳 such that X is a feasible point of (OM).Proof.
Given the set of variablesV={V1,V2,…,Vn} where V1 is the class variable and {V2,…,Vn} are the attribute variables. We give a matrix X as follows:
(5)xij={1,i=1,j=2,…,n,0,otherwise.
Obviously, the adjacency matrix X always satisfies the constrains (1)–(3). In fact, the graph represented by X is the Naive Bayes classifier. Thus, X is a feasible solution of (OM).According to Theorem6, we can prove that there exists a feasible classifier which satisfy constrains (1)–(3). Theorem 7 further shows that such classifier is unique under certain condition.Theorem 7.
LetX* be the optimal solution of (OM), C1={cij∣xij=1} and C2={cij∣xij=0} be the coefficient sets where xij is the element of X*. X* is the unique solution of (OM) if and only if any element in C1 cannot be expressed as the sum of any number of elements in C2.Proof.
Without loss of generality, we suppose, by reduction to absurdity, thatX(1) and X(2) are two optimal solutions of (OM). The values of the objective function is the same in both solutions, that is,
(6)∑i=1n‍∑j=1,j≠in‍cijxij(1)=∑i=1n‍∑j=1,j≠in‍cijxij(2)(7)⇒∑i=1n‍∑j=1,j≠in‍cij(xij(1)-xij(2))=0.
Let C1(1)={cij∣xij(1)=1}, C2(1)={cij∣xij(1)=0}. According to the assumption of X(1)≠X(2) and xij(1),xij(2)∈{0,1}, there must exist 1≤i0,j0≤n such that xi0j0(1)-xi0j0(2)=1, namely, xi0j0(1)=1,xi0j0(2)=0. Then, by (7),
(8)ci0j0+∑i≠i0‍∑j≠j0‍cij(xij(1)-xij(2))=0.
Since
(9)xij(1)-xij(2)={1,xij(1)=1,xij(2)=0,0,xij(1)=xij(2),-1,xij(1)=0,xij(2)=1,
then, by (8), there must exist ci1j1,…,cikjk∈C2(1) such that xirjr(1)-xirjr(2)=-1,r=1,…,k and ci0j0+∑r=1kcirjr(xirjr(1)-xirjr(2))=0, namely,
(10)ci0j0=∑r=1k‍cirjr,
where xi0j0(1)=1,xirjr(1)=0,r=1,…,k. This contradicts with the known condition that any element in C1(1) cannot be expressed as the sum of any number of elements in C2(1).Theorem 8.
LetG=(V,E),V=(V1,V2,…,Vn) be the classifier structure obtained by step 4 of BC-OM, where V1 is the class variable and V2,…,Vn are attribute variables. G*=(V*,E*) denotes the final output of BC-OM, then the classification results obtained by G and G* are consistent.Proof.
Without loss of generality, suppose(di2,…,din) is an example to be classified. The classifier represented by G is given as follows:
(11)v1*=argmaxv1∈dom(V1)p(v1∣v2=di2,…,vn=din).
We write the right side of (11) as p(v1∣v2,…,vn) in short. We can suppose that k redundant variables were deleted in step 5 of BC-OM, say the last k variables Vn-k+1, Vn-k+2,…,Vn. Then, V*={V1,V2,…,Vn-k}. According to step 5, {V2,…,Vn-k} d-separates V1 and {Vn-k+1,…,Vn}. Thus, V1 is conditional independent with {Vn-k+1,…,Vn} given {V2,…,Vn-k}. Equation (11) can be reduced as follows:
(12)v1*=argmaxv1∈dom(V1)p(v1,v2,…,vn)p(v2,…,vn)⟺v1*=argmaxv1∈dom(V1)p(v1,v2,…,vn)⟺v1*=argmaxv1∈dom(V1)p(v1,vn-k+1,…,vn∣v2,…,vn-k)·p(v2,…,vn-k)⟺v1*=argmaxv1∈dom(V1)p(v1∣v2,…,vn-k)·p(vn-k+1,…,vn∣v2,…,vn-k)⟺v1*=argmaxv1∈dom(V1)p(v1∣v2,…,vn-k).
We get the results.Theorem8 reveals that it is effective and correct to remove redundant or irrelevant attributes using d-separation rule, and the performance of Bayesian classifier can be improved.


## 3.1. Optimization Model Design

In this subsection, we give some basic concepts and theorems which is the foundation of the method proposed in this paper.A Bayesian classifier is a graphical representation of a joint probability distribution that includes two components. One is a directed acyclic graphG=(V,E), where the node set V={V1,V2,…,Vn} represents the class and attribute variables, and the edge set E represents direct dependency relationships between variables. The other is a joint probability distribution Θ={θi∣θi=P(Vi∣pa(Vi)),i=1,2,…,n} that quantifies the effects of pa(Vi) has on the variable Vi in G, where pa(Vi)={Vj∣Vj→Vi∈E}. We assume that V1 is the class node and {V2,V3,…,Vn} is the set of attribute nodes. The structure of G reflects the underlying probabilistic dependence relations among the nodes and a set of assertions about conditional independencies. The problem of data classification can be stated as follows: the learning goal is first to find the classifier structure that best matches D and estimate the parameters using the training data set D, then to assign class label to test instances. Since G is a directed acyclic graph, it can be represented by a binary node-node adjacency matrix X=(xij). Entry (i,j) is 1 if there is a directed arc from node i to node j, and 0 otherwise. That is,
(2)xij={1,ifVi→Vj∈E,0,ifVi→Vj∉E.LetR=X+X2+⋯+Xn be the sum of powers of the adjacency matrix. Entry rij∈R is equal to the number of directed paths from node Vi to node Vj in the graph [25].We wish to be able to use a mathematical programming formulation, and this formulation requires that we are able to measure the impact of adding or removing a single arc from the network. In order to approximate the impact of adding such an arc, we define the dependence coefficient.Definition 2.
Given a data setD and a variable set V={V1,V2,…,Vn}, we define the dependence coefficient cijα between variables Vi and Vj as cijα=mink≠i,j{Uij|k2-χij∣k,α2}, where Uij∣k2 is the U2 statistics of Vi and Vj given Vk, χij∣k,α2 is the critical value at the significance level α of a χ2 distribution with (ri-1)(rj-1)rk degrees of freedom.Obviously,cijα is a conservative estimate of the degree of dependence between two nodes. If cijα>0, then, regardless of the other variable involved, there is statistically significant dependence between Vi and Vj, so there should be an arc between them. If cijα<0, then there is at least one way of conditioning the relationship so that significant dependence is not present. We define C=(cij) the dependence coefficient matrix corresponding to the variable set V, that is,
(3)cij={cijα,ifi≠j,0,otherwise.Lemma 3.
Given a data setD and a variable set V, Vi and Vj are locally conditionally independent at the significance level α if and only if there is a node Vk∈V such that Uij|k2<χij|k,α2.The proof of Lemma3 can be obtained directly by Definition 2 and chi-square hypothesis test. According to Lemma 3, Vi and Vj are locally conditionally independent at the significance level α if and only if there is a node Vk∈V such that cij<0. Further, Vi and Vj are globally conditionally independent at the significance level α if and only if Uij∣k2<χij∣k,α2 for any k≠i,j. Based on this, we use the dependence coefficients to construct an overall measure of the dependence which will be treated as the objective function for our mathematical program.Definition 4.
For a Bayesian classifier with adjacency matrixX=(xij), the global dependence measure of the network is given by
(4)ℱ(X,α)=∑i=1n‍∑j=1,j≠in‍cijxij.According to the measure of Definition4, if Vi and Vj are conditionally independent, by Lemma 3  cij<0, and hence, adding an arc between Vi and Vj decreases the value of ℱ. Thus, we wish to find the feasible solution which increases ℱ. The optimal solution corresponds to the best classifier structure. We next explain what constitutes feasible network.Given the variable setV={V1,V2,…,Vn}, V1 is the class node and {Vi,i=2,…,n} is the set of attribute nodes. A directed network is a feasible classifier structure if and only if the following conditions are satisfied:(1)
for any attribute nodeVi∈V,i=2,…,n, there is no directed edge from Vi to V1;(2)
for any nodeVi∈V,i=1,2,…,n, there is no directed path from Vi to Vi, namely, the graph is acyclic;(3)
there exists at least one attribute nodeVi∈V,i=2,…,n which is dependent with class node V1, namely, there is an attribute node Vi such that Vi can be reached from V1 by a directed path.In order to incorporate the requirements of the above three conditions into a mathematical programming formulation, we express them by the following constrains:(1)
∑i=2nxi1=0;(2)
∑i=1nrii=0;(3)
∑j=2nr1j≥1.The feasible classifiers are those that satisfy constrains (1)–(3). Thus, learning best Bayesian classifier can be transformed into the following related mathematical programming problem, where the objective function is a global dependence measure of the network, and the feasible region is the set of classifiers with reachability constrains (1)–(3), that is,(OM)maxℱ(X,α)=∑i=1n∑j=1,j≠incijxij,s.t.∑i=2nxi1=0,∑i=1nrii=0,∑j=2nr1j≥1,xij∈{0,1}.


## 3.2. BC-OM Algorithm and Its Correctness

In this subsection, we present the main algorithm of this paper. Our method starts with finding the best Bayesian classifier by solving the above optimization model. Second, we use the d-separation rule of Bayesian network to delete irrelevant or redundant attributes in the network which have low dependence degree with the class variable. The parameters of modified network can be estimated. Third, classification is done by applying obtained classifier to predict the class label of test data. We prove the correctness of proposed method under the faithfulness assumption for the data distribution.Given a directed acyclic graphG=(V,E) where V is the node set and E the set of directed edges. A path ρ between two distinct nodes V1 and Vl is a sequence of distinct nodes in which the first node is V1, the last one is Vl and two consecutive nodes are connected by an edge, that is ρ=V1e1V2⋯el-1Vl where ei denotes Vi→Vi+1 or Vi←Vi+1 for i=1,2,…,(l-1).Definition 5.
A pathρ is said to be d-separated by a set Z in a directed acyclic graph G if and only if (1)  ρ contains a “head-to-tail meeting”: Vi→Vj→Vk or a “tail-to-tail meeting”: Vi←Vj→Vk such that the middle node Vj is in Z, or (2)  ρ contains a “head-to-head meeting”: Vi→Vj←Vk such that the middle node Vj is not in Z and no descendant of Vj is in Z. Specially, two distinct sets of nodes X and Y are said to be d-separated by a set Z in G if Z d-separates every path from any node in X to any node in Y [26].In this paper, we assume that all the distributions are compatible withG [27]. We also assume that all independencies of a probability distribution of variables in V can be checked by d-separations of G, called the faithfulness assumption [26]. The faithfulness assumption means that all independencies and conditional independencies among variables can be represented by G. Now we formally describe our method in the following Algorithm 1.Algorithm 1:BC-OM.
(
1
)  Input: Data set D; Variable set V = (V1, V2,…, Vn) (V1 is the class node and others are attribute
nodes).
(
2
) For any pair of variable Vi and Vj contained in V, calculate the dependence coefficient cij by
Definition2;
(
3
) Solve the mathematical programming (OM) and obtain the optimal solution X*=(xij);
(
4
) Build the classifier structure G* = (V, E*) by X*=(xij);
(
5
) For any variable Vi∈V, i≠1, if there is a subset Z⊂V∖{V1, Vi} such that Z d-separates Vi and
V1, then delete Vi in G*, update G* as V=V∖{Vi}, E*=E*∖{Vi→Vj or Vj→Vi, Vj∈ adj(Vi)};
(
6
)  Output: The built classifier G* = (V, E*).From the detailed steps of BC-OM, we can see that BC-OM classifier relaxes the restrictions on condition variable and further meets the need of practical application. Since its network structure is similar to that of BAN’s, BC-OM does not need to build all possible networks in which class node is a root and removes irrelevant or redundant nodes from the network before the process of estimating the network parameters, which greatly reduces the calculation for posterior probability of class variable. In fact, the training process of BC-OM is different from other BN classifiers. Its main task is to solve the mathematical programming(OM). To create the dependence coefficient matrix corresponding to (OM), BC-OM needs to compute the conditional statistics Uij∣k2. Moreover, just as other constraint based algorithms, the main cost of BC-OM is the number of conditional independence tests for computing the dependence coefficients of any two variables in step 2. The number of conditional independence tests is Cn2·Cn-21 and the computing complexity is O(n3). The total complexity of BC-OM is bound by O(n3·N), where n is the number of variables in the network and N is the number of cases in data set D. In principle, BC-OM is a structure-extension-based algorithm. In BC-OM, we essentially extend the structure of TAN by relaxing the parent set of each attribute node. Thus, the resulting structure is more complex than TAN, but more simple than BAN. Therefore, BC-OM is a good tradeoff between the model complexity and accuracy compared with TAN and BAN. Next, we prove the correctness of BC-OM algorithm under the faithfulness assumption.The next two results establish the existence and uniqueness properties of solution to(OM).Theorem 6.
Let𝒳={(xij)n×n∣xij∈{0,1}}. There always exists an X∈𝒳 such that X is a feasible point of (OM).Proof.
Given the set of variablesV={V1,V2,…,Vn} where V1 is the class variable and {V2,…,Vn} are the attribute variables. We give a matrix X as follows:
(5)xij={1,i=1,j=2,…,n,0,otherwise.
Obviously, the adjacency matrix X always satisfies the constrains (1)–(3). In fact, the graph represented by X is the Naive Bayes classifier. Thus, X is a feasible solution of (OM).According to Theorem6, we can prove that there exists a feasible classifier which satisfy constrains (1)–(3). Theorem 7 further shows that such classifier is unique under certain condition.Theorem 7.
LetX* be the optimal solution of (OM), C1={cij∣xij=1} and C2={cij∣xij=0} be the coefficient sets where xij is the element of X*. X* is the unique solution of (OM) if and only if any element in C1 cannot be expressed as the sum of any number of elements in C2.Proof.
Without loss of generality, we suppose, by reduction to absurdity, thatX(1) and X(2) are two optimal solutions of (OM). The values of the objective function is the same in both solutions, that is,
(6)∑i=1n‍∑j=1,j≠in‍cijxij(1)=∑i=1n‍∑j=1,j≠in‍cijxij(2)(7)⇒∑i=1n‍∑j=1,j≠in‍cij(xij(1)-xij(2))=0.
Let C1(1)={cij∣xij(1)=1}, C2(1)={cij∣xij(1)=0}. According to the assumption of X(1)≠X(2) and xij(1),xij(2)∈{0,1}, there must exist 1≤i0,j0≤n such that xi0j0(1)-xi0j0(2)=1, namely, xi0j0(1)=1,xi0j0(2)=0. Then, by (7),
(8)ci0j0+∑i≠i0‍∑j≠j0‍cij(xij(1)-xij(2))=0.
Since
(9)xij(1)-xij(2)={1,xij(1)=1,xij(2)=0,0,xij(1)=xij(2),-1,xij(1)=0,xij(2)=1,
then, by (8), there must exist ci1j1,…,cikjk∈C2(1) such that xirjr(1)-xirjr(2)=-1,r=1,…,k and ci0j0+∑r=1kcirjr(xirjr(1)-xirjr(2))=0, namely,
(10)ci0j0=∑r=1k‍cirjr,
where xi0j0(1)=1,xirjr(1)=0,r=1,…,k. This contradicts with the known condition that any element in C1(1) cannot be expressed as the sum of any number of elements in C2(1).Theorem 8.
LetG=(V,E),V=(V1,V2,…,Vn) be the classifier structure obtained by step 4 of BC-OM, where V1 is the class variable and V2,…,Vn are attribute variables. G*=(V*,E*) denotes the final output of BC-OM, then the classification results obtained by G and G* are consistent.Proof.
Without loss of generality, suppose(di2,…,din) is an example to be classified. The classifier represented by G is given as follows:
(11)v1*=argmaxv1∈dom(V1)p(v1∣v2=di2,…,vn=din).
We write the right side of (11) as p(v1∣v2,…,vn) in short. We can suppose that k redundant variables were deleted in step 5 of BC-OM, say the last k variables Vn-k+1, Vn-k+2,…,Vn. Then, V*={V1,V2,…,Vn-k}. According to step 5, {V2,…,Vn-k} d-separates V1 and {Vn-k+1,…,Vn}. Thus, V1 is conditional independent with {Vn-k+1,…,Vn} given {V2,…,Vn-k}. Equation (11) can be reduced as follows:
(12)v1*=argmaxv1∈dom(V1)p(v1,v2,…,vn)p(v2,…,vn)⟺v1*=argmaxv1∈dom(V1)p(v1,v2,…,vn)⟺v1*=argmaxv1∈dom(V1)p(v1,vn-k+1,…,vn∣v2,…,vn-k)·p(v2,…,vn-k)⟺v1*=argmaxv1∈dom(V1)p(v1∣v2,…,vn-k)·p(vn-k+1,…,vn∣v2,…,vn-k)⟺v1*=argmaxv1∈dom(V1)p(v1∣v2,…,vn-k).
We get the results.Theorem8 reveals that it is effective and correct to remove redundant or irrelevant attributes using d-separation rule, and the performance of Bayesian classifier can be improved.


## 4. Experimental Results

We run our experiments on 20 data sets from the UCI repository of Machine Learning datasets [28], which represent a wide range of domains and data characteristics. Table 1 shows the description of the 20 data sets which are ordered by ascending number of samples. In our experiments, missing values are replaced with the modes and means of the corresponding attribute values from the available data. For example, if the sex of someone is missing, it can be replaced by the mode (the value with the highest frequency) of the sexes of all the others. Besides, we manually delete three useless attributes: the attribute “ID number” in the dataset “Glass”, the attribute “name” in the dataset “Hayes-roth”, and the attribute “animal name” in the dataset “Zoo”.Table 1
Descriptions of UCI datasets used in the experiments.
NO.
Dataset
# Instances
# Attributes
# Classes
Missing value (N/Y)
1
Shuttle
15
6
2
N
2
Balloon
16
4
2
N
3
Lenses
24
4
3
N
4
Soybean (small)
47
35
4
N
5
Post-patient
90
8
3
Y
6
Zoo
101
17
7
N
7
Hayes-roth
132
5
3
N
8
Iris
150
4
3
N
9
Glass
214
10
7
N
10
Heart
267
22
2
N
11
Ionosphere
351
34
2
N
12
Monk’s
432
7
2
N
13
Vote
435
16
2
Y
14
Balance-scale
625
5
3
N
15
Tic-tac-toe
958
9
2
N
16
Car-evaluation
1728
6
4
N
17
Chess (kr-vs-kp)
3196
36
2
N
18
Mushroom
8124
22
2
Y
19
Nursery
12960
8
5
N
20
Letter
20000
16
26
NThe experimental platform is a personal computer with Pentium 4, 3.06 GHz CPU, 0.99 GB memory, and Windows XP. Our implementation is based on the BayesNet Toolbox for Matlab [29], which provides source code to perform several operations on Bayesian networks. The purpose of these experiments is to compare the performance of the proposed BC-OM with Naive Bayes, TAN and BAN in terms of classifier accuracy. The accuracy of each model is based on the percentage of successful predictions on the test sets of each data set. In all experiments, the accuracy of each model on each data set are obtained via 10 runs of 5-fold cross validation. Runs with the various algorithms are carried out on the same training sets and evaluated on the same test sets. In particular, the cross-validation folds are the same for all the experiments on each data set. Finally, we compared related algorithms via two-tailed t-test with a 95 percent confidence level. According to the statistical theory, we speak of two results for a data set as being “significantly different” only if the probability of significant difference is at least 95 percent [30].Table2 shows the accuracy (and standard deviation of accuracy) of each model on each data set, and the average values and standard deviation on all data sets are summarized at the bottom of the table. In each row, the best of the four classifier results are displayed in bold. If another’s performance is not significantly different from the best, it is also highlighted, but if the differences between all four classifies are not statistically significant, then none of them is highlighted. From our experiments, we can see that BC-OM is best in 6 cases. NB, TAN, and BAN are best in 6, 5, and 3 cases, respectively. When the number of samples is larger than 400, the performance of TAN and BAN is better than that of NB, and BC-OM is best. Although it can be seen that the performance of BC-OM and TAN becomes similar as the sample size increase, BC-OM has a higher accuracy on average. From a general point of view, we can see that from the first data set to the last one, the highlighted numbers change from few to even more in the sixth column of Table 2. It means the advantage of BC-OM is more evident with the increase of data size.Table 2
The detailed experimental results on accuracy and standard deviation.
NO.
Dataset
NB
TAN
BAN
BC-OM
1
Shuttle
83.52
±
5.85
85.33
±
7.03
84.43
±
6.83
82.33
±
5.94
2
Balloon
89.15
±
3.06
85.16
±
3.15
87.16
±
2.92
83.75
±
3.57
3
Lenses
92.56
±
2.44
93.25
±
2.85
89.67
±
3.16
91.12
±
3.02
4
Soybean (small)
90.91
±
2.35
84.98
±
3.16
87.36
±
2.44
89.74
±
3.23
5
Post-patient
80.29
±
3.39
79.94
±
3.47
81.26
±
3.56
80.12
±
3.48
6
Zoo
93.46
±
5.12
95.21
±
4.78
94.34
±
5.16
94.88
±
5.09
7
Hayes-roth
81.82
±
5.27
87.34
±
4.89
84.58
±
3.74
84.55
±
3.56
8
Iris
94.13
±
6.12
93.47
±
6.65
93.81
±
6.80
89.07
±
7.25
9
Glass
66.02
±
9.88
59.67
±
9.52
58.32
±
9.98
56.96
±
9.81
10
Heart
82.41
±
6.62
82.53
±
7.01
82.65
±
7.03
81.53
±
6.91
11
Ionosphere
90.54
±
4.03
90.61
±
3.98
91.45
±
4.14
90.99
±
4.82
12
Monk's
84.28
±
1.14
83.29
±
1.29
83.79
±
1.23
86.64
±
1.02
13
Vote
94.88
±
3.57
90.37
±
3.34
92.63
±
3.98
90.97
±
2.95
14
Balance-scale
90.91
±
1.51
84.97
±
2.44
87.94
±
2.31
90.77
±
1.85
15
Tic-tac-toe
70.11
±
4.45
73.16
±
4.47
75.74
±
4.83
76.21
±
3.82
16
Car-evaluation
84.95
±
2.74
93.44
±
1.89
89.2
±
1.02
95.42
±
1.03
17
Chess (kr-vs-kp)
87.88
±
1.91
91.68
±
1.66
90.27
±
1.12
92.65
±
1.4
18
Mushroom
92.85
±
0.56
99.89
±
0.1
96.37
±
0.76
99.91
±
0.1
19
Nursery
90.54
±
1.14
94.07
±
1.29
92.31
±
1.23
89.95
±
1.09
20
Letter
69.32
±
3.97
77.58
±
1.83
73.45
±
1.67
77.66
±
2.01
Average
86.85
±
4.81
86.63
±
3.7
85.69
±
3.69
86.76
±
3.57Table3 shows the compared results of two-tailed t-test, in which each entry w/t/l means that the model in the corresponding row wins in w data sets, ties in t data sets and loses in l data sets, compared to the model in the corresponding column. From Table 3, we can see that BC-OM significantly outperforms NB (9 wins and 4 losses), TAN (12 wins and 5 losses) and BAN (11 wins and 5 losses) in accuracy. Figures 2, 3, and 4 show two scatter-plots comparing BC-OM with NB, TAN, and BAN, respectively. In the scatter plot, each point represents a data set, where the x coordinate of a point is the percentage of misclassifications according to NB or TAN or BAN, and the y coordinate is the percentage of misclassifications according to BC-OM. Thus, points below the diagonal line correspond to data sets on which BC-OM performs better. From Figures 2 and 3, we can see that BC-OM generally outperforms NB and TAN as is also demonstrated in Table 3. It provides strong evidence that BC-OM is performing well against the other two classifiers both in terms of accuracy as well as the percentage of misclassifications. Figure 4 also shows BC-OM outperforming BAN, though the difference in performance is not as marked as in the results of Figures 2 and 3. In other words, the performance of BC-OM and BAN is similar in terms of the percentage of misclassifications. However, BC-OM has a higher accuracy and a more simple graph structure, which suggests that BC-OM is able to handle very large data sets and is a more promising classifier.Table 3
The compared results of two-tailedt-test on accuracy with the 95 percent confidence level.
w
/
t
/
l
NB
TAN
BAN
TAN
13/3/4
—
—
BAN
12/4/4
10/5/5
—
BC-OM
9/7/4
12/3/5
11/4/5Figure 2
Relative errors of BC-OM and NB.Figure 3
Relative errors of BC-OM and TAN.Figure 4
Relative errors of BC-OM and BAN.


## 5. Conclusions

In many real-world applications, classification is often required to make optimal decisions. In this paper, we summarize the existing improved algorithms for naive Bayes and propose a novel Bayesian classifier model: BC-OM. We conducted a systematic experimental study on a number of UCI datasets. The experimental results show that BC-OM has a better performance compared to the other state-of-the-art models for augmenting naive Bayes. It is clear that in some situations, it would be useful to model correlations among attributes. BC-OM is a good tradeoff between the quality of the approximation of correlations among attributes and the computational complexity in the learning stage. Considering its simplicity, BC-OM is a promising model that could be used in many field.In addition, we use the chi-squared statistic to estimate the dependence coefficients among attributes from dataset. We believe that the use of more sophisticated methods could improve the performance of the current BC-OM and make its advantage stronger. This is the main research direction for our future work.



---

*Source: 975953-2013-02-06.xml*