Bagging k -dependence Bayesian network classifiers

Abstract

Bagging has attracted much attention due to its simple implementation and the popularity of bootstrapping. By learning diverse classifiers from resampled datasets and averaging the outcomes, bagging investigates the possibility of achieving substantial classification performance of the base classifier. Diversity has been recognized as a very important characteristic in bagging. This paper presents an efficient and effective bagging approach, that learns a set of independent Bayesian network classifiers (BNCs) from disjoint data subspaces. The number of bits needed to describe the data is measured in terms of log likelihood, and redundant edges are identified to optimize the topologies of the learned BNCs. Our extensive experimental evaluation on 54 publicly available datasets from the UCI machine learning repository reveals that the proposed algorithm achieves a competitive classification performance compared with state-of-the-art BNCs that use or do not use bagging procedures, such as tree-augmented naive Bayes (TAN), $k$ -dependence Bayesian classifier (KDB), bagging NB or bagging TAN.

Keywords

Bagging bayesian network classifiers log likelihood disjoint subspaces of dataset

1. Introduction

Classification is a fundamental issue in data mining and pattern recognition [1, 2], and its aim is to build a classifier that can assign the appropriate class label $y$ , from a set of $m$ values of the class variable $Y$ to an unlabeled instance $\bm{x}=(x_{1},\ldots,x_{n})$ , with values for a collection of $n$ predictive attributes $\textbf{X}=\{X_{1},\ldots,X_{n}\}$ . Ensemble learning can boost base learners or weak learners to strong learners and is considered the most popular research direction in machine learning. Numerous empirical and theoretical studies have demonstrated the effectiveness and efficiency of ensemble learning. Ideally, each learner should exhibit a certain “diversity” in its group behavior, either implicitly or explicitly.

Many theoretical studies have explored famous ensemble methods, such as boosting and bagging, which have been successfully adopted in a large number of applications [3, 4, 5, 6]. Bagging [7] is an ensemble method that has attracted much attention due to its simple implementation and the popularity of bootstrapping [3, 7, 8]. This method aims to obtain predicted labels from a set of diverse classifiers and then combine these models into a single predictive classification. Bagging trains several base learners from different bootstrap samples by calling a base learning algorithm. To increase classification accuracy, the predictions from individual base learners are summarized into a single general prediction [9]. Diversity is encouraged “implicitly” via a random sampling of the data space. Boosting, particularly AdaBoost, is a family of learners that “explicitly” encourages diversity by altering the distribution of the training data. Each learner substantially differs from others and may make more accurate predictions in cases where previous predictors have made errors [10].

Bayesian network (BN) is a powerful formalism for representing and reasoning under conditions of uncertainty, and Bayesian network classifier (BNC) has been increasingly used in a wide range of classification tasks [11, 12, 13, 14] after the success of naïve Bayes (NB), which has the simplest topology by assuming that each attribute is independent from the others given the class variable [2]. Ensemble BNCs focus on the diversity of conditional dependencies in the topologies of committee members. Averaged one-dependence estimators (AODE) [15] assumes that all other attributes are independent of each other given the class and one shared attribute, $X_{\alpha}$ , the super parent. Researchers have proposed several methods, such as attribute selection [16], attribute weighing [17, 18], model selection [19], and model weighing [20], to encourage diversity among ODE members.

Bagging randomly samples from the training data and does not apply any measurements to ensure the emergence of diversity. A serious limitation of current ensemble methods is the lack of comprehensibility. How to improve the comprehensibility of knowledge learned from ensembles is an important yet largely understudied direction [21]. To ensure diversity in this paper, the training dataset $\mathcal{D}$ is divided into $m$ disjoint subspaces and an arbitrary $k$ -dependence BNC is trained for each subspace $\mathcal{D}_{i}$ . The unlabeled testing instance $t$ is extended to a pseudo instance $t_{i}$ with class label $y_{i}$ ( $1\leqslant i\leqslant m$ ), and a $k$ -dependence BNC is trained for $t_{i}$ . These weak BNCs describe the dependency relationships among the attributes implicated in different data subspaces and produce different generalization behaviors.

The contributions of this paper are as follows:

•
We prove theoretically and experimentally that, the conditional dependencies among attributes may vary greatly across different subspaces of the training data. The entropy functions $H_{\mathcal{B}_{i}}(\mathcal{D}_{i})$ and $h_{b_{i}}(t_{i})$ are introduced to respectively identify the significant conditional dependencies among attributes implicated in the training subspace $\mathcal{D}_{i}$ and labeled testing instance $t_{i}$ . These functions are then applied to optimize the topologies of the learned BNCs, $B_{i}$ and $b_{i}$ .
•
BNCs learn from disjoint subspaces rather than the resampled data, thereby ensuring diversity in the data distribution. Bagging combines BNCs with the same class label by applying a uniformly weighted average, and a prediction is made by applying the Bayes rule to select the maximum posterior probability. The experimental results show that this adjustment is effective and demonstrate that it can help improve zero-one loss, bias, variance, and root mean squared error.

The rest of this paper is organized as follows: Section 2 clarifies the relationship between entropy function $H_{\mathcal{B}}$ and topology $\mathcal{B}$ , and reviews some state-of-the-art BNCs. Section 3 introduces the basic idea and learning procedure of the proposed algorithm, bagging $k$ -dependence BNC (BKDB). Section 4 compares the performance of BKDB with that of related approaches on 54 datasets. Section 5 concludes the paper and presents directions for future work.

Figure 1.
Topologies of (a) NB and (b) TAN.

2. Related research work

A BNC can be defined by the pair $\mathcal{B}=\{\mathcal{G},\Theta\}$ , where $\mathcal{G}$ denotes the directed acyclic graph in which the nodes correspond to domain variables $\{X_{1},\cdots,X_{n},Y\}$ and the arcs between nodes represent the direct dependencies between the variables. $\Theta$ denotes the conditional probability tables that quantify the probabilistic model. For any labeled instance $(\bm{x},y)$ , BNC models the joint distribution $P(\bm{x},y)$ and factorizes it according to topology $\mathcal{G}$ as follows:

$\displaystyle P(\bm{x},y)=P(y)P(\bm{x}|y)=P(y)\prod_{i=1}^{n}{P(x_{i}|\Pi_{i},% y)},$ (1)

where $\Pi_{i}$ denotes the set of parents of $X_{i}$ . One key issue in learning BNC is how to identify the significant conditional dependencies between attribute $X_{i}$ and its parents $\Pi_{i}$ . As shown in Fig. 1a, NB has the simplest topology among all BNCs, assuming that all attributes are independent given the class. However, this unrealistic assumption would harm the performance of NB in applications with complex attribute dependencies [22, 23, 24, 25, 26]. The joint probability estimate for NB is $P(y)\prod_{i=1}^{n}{P(x_{i}|y)}$ . Due to the effectiveness and efficiency of NB, there has been a lot of prior work that explores approaches to alleviating NB’s independence assumption.

Figure 2.

Topologies of (a) KDB and (b) AODE.

By adding augmented edges to the topology of NB, the tree augmented naive Bayes (TAN) (Fig. 1b) and $k$ -dependence Bayesian classifier (KDB) [27] (Fig. 2a) relax the independence assumption of NB and respectively extend NB from a 0-dependence topology to a 1-dependence or even an arbitrary $k$ -dependence topology, thereby covering a wide spectrum of BNCs from NB to full BNC. In contrast to single-model BNCs, ensemble BNCs ensure diversity in conditional dependencies by generating multiple subclassifiers. Previous theoretical and empirical research shows that an ensemble is often more accurate than any base classifiers in the ensemble [28, 29]. A good ensemble BNC can fully represent the coverage of conditional dependencies and distribute the errors of base BNCs across different parts of the instance space. One key issue in creating an effective ensemble is how to choose an appropriate function for combining the predictions of the base classifiers [30, 31].

Diversity in independence assumptions leads to diversity in learned topologies. ATAN [32] respectively chooses each attribute as the root node of the maximum weighted spanning tree to help reduce its bias at the cost of variance. AODE (Fig. 2b) utilizes a restricted class of super-parent one-dependence estimators (SPODEs) to mitigate the negative effect of the biased estimate of probability distribution learned from single-model classifiers. The weaker independence assumption of AODE is necessarily true if NB’s is true and may also be true when NB’s is not [33]. Jiang et al. [17] proposed to use information-theoretic metrics, such as mutual information, conditional log likelihood and area under the ROC curve (AUC), to assign weights to SPODEs. These metrics aim to find a balance between the goodness of fit and model simplicity. Bagging trains an ensemble BNC on randomly sampled data. Hellman et al. [34] introduced Ensembled Continuous Bayesian Networks (ECBNs), which are trained on both the data subset and the attribute subset, to learn salient dependence relationships and predict values for continuous data. Kunwar et al. [35] pseudo-randomly selected subsets of components of the attribute vector and then constructed BNCs on randomly chosen subspaces by using the Random Subspace method.

Boosting iteratively trains an ensemble BNC on weighted training data. Oza and Russel [36] introduced Online Bagging, which alleviates the limitation of standard bagging (i.e. requiring the entire training set to be available beforehand for learning). The theoretical foundations of this approach were further developed by Bifet and Holmes [37, 38]. They introduced two modifications of Oza’s algorithm called Adaptive-Size Hoeffding Trees (ASHT) and Leveraging Bagging, which aim at adding more randomization to the input and output of the base classifiers. Boosting has been proven efficient in handling imbalanced data. However, boosting learning may be prone to overfitting when a small amount of training data is used. To address this problem, Yu et al. [39] proposed a bayesian undirected graphical model interpretation for co-training, which alternately uses the most confident unlabeled data instance(s) in one modality to assist the model training of another modality. Freund and Schapire [40] proposed adaptive boosting to generate multiple weak classifiers with the weight distribution of different training instances. Foo et al. [41] trained weak classifiers by using the biased Baum-Welch algorithm under the AdaBoost framework. Recently, the hybrids of bagging and boosting techniques are reported to outperform many other complex algorithms. EasyEnsemble and BalanceCascade [42] use bagging as the main ensemble learning method, and they train each bag by using AdaBoost.

3. Bagging

k

-dependence Bayesian network classifier

3.1 Difference in probability distribution across various data subspaces

For TAN or $k$ -dependence BNC (KDB), the conditional mutual information (CMI) $I(X_{i};X_{j}|Y)$ is used to measure the conditional dependence between attributes $X_{i}$ and $X_{j}$ , and can be defined as:

$\displaystyle I(X_{i};X_{j}|Y)=\sum_{Y}\sum_{X_{i}}\sum_{X_{j}}P(x_{i},x_{j},y% )\log\frac{P(x_{i},x_{j}|y)}{P(x_{i}|y)P(x_{j}|y)}=\sum_{Y}P(y)\left\{\sum_{X_% {i}}\sum_{X_{j}}P(x_{i},x_{j}|y)\log\frac{P(x_{i},x_{j}|y)}{P(x_{i}|y)P(x_{j}|% y)}\right\}=\sum_{Y}P(y)I(X_{i};X_{j}|y)$ (2)

Figure 3.

The distributions of values of $I(X_{i};X_{j}|y)$ when (a) $y=0$ and (b) $y=1$ .

In Eq. (2), $I(X_{i};X_{j}|Y)$ is the mathematical expectation of $I(X_{i};X_{j}|y)$ . If the values of $I(X_{i};X_{j}|y)$ vary greatly across different class labels, then the conditional dependence among attributes will also vary and may result in a biased estimate of conditional joint probability $P(\bm{x}|y)$ . Take the Spambase dataset (Table 1) as an example. The value distributions of $I(X_{i};X_{j}|y)$ for different $y$ are shown in Fig. 3, which reveals that the values of $I(X_{i};X_{j}|y)$ are evenly distributed when $y=1$ but are unevenly distributed when $y=0$ .

Figure 4.

Scatter plot (a) and corresponding contour plot (b) of conditional dependencies identified by comparing $I(X_{i};X_{j}|y=0)$ .

Figure 5.

Scatter plot (a) and corresponding contour plot (b) of conditional dependencies identified by comparing $I(X_{i};X_{j}|y=1)$ .

As the dependence degree increases, the number of conditional dependencies to be described in BNC will increase exponentially (i.e., the number of conditional dependencies for KDB is $nk-\frac{k^{2}}{2}-\frac{k}{2}$ ), and the possibility for the BNCs learned from different subspaces of training data to be identical will significantly decrease. Besides, the difference in $I(X_{i};X_{j}|y)$ for different class labels may lead to differences in the identified conditional dependencies and bias the estimates of conditional and joint probabilities. As shown in Figs 4a and 5a, each data point in the scatter plots denotes a specific conditional dependence among the attributes in KDB that is measured by $I(X_{i};X_{j}|y=0)$ or $I(X_{i};X_{j}|y=1)$ on the Spambase dataset. For clarity, the kernel density estimation (KDE) is applied to interpret the data and each kernel acts as a probability density function centered on the location of its corresponding data point in the parameter space. The corresponding contour plots produced by KDE are shown in Figs 4b and 5b, which reveal differences in the topologies of the learned KDBs.

3.2 General conditional dependencies among attributes

For specific instance $d_{i}$ in the training dataset $\mathcal{D}$ , the log likelihood $\log P_{\mathcal{B}}(d_{i})$ corresponds to the number of bits needed to describe $d_{i}$ based on the probability distribution $P_{\mathcal{B}}$ . The entropy function $H_{\mathcal{B}}(\mathcal{D})$ can be used to measure the extent to which the learned BNC $\mathcal{B}$ fits the training data $\mathcal{D}$ and can be defined as [43]

$\displaystyle H_{\mathcal{B}}(\mathcal{D})=-\sum_{Y,\textbf{X}}P(y,\bm{x}|% \mathcal{D})\log P_{\mathcal{B}}(y,\bm{x}|\mathcal{D})=H(Y)+\sum_{i=1}^{n}H(X_% {i}|Y,\Pi_{i}^{\mathcal{B}},\mathcal{D}).$ (3)

To mitigate the negative effect of the i.i.d. assumption and finely tune the conditional dependency relationships among attributes, the training set $\mathcal{D}$ is divided into $m$ subspaces and the instances in each subspace (e.g., $\mathcal{D}_{i}$ ) have the same class label (e.g., $y_{i}$ ). Given the BNC $\mathcal{B}_{i}$ learned from $\mathcal{D}_{i}$ , the corresponding entropy function is

$\displaystyle H_{\mathcal{B}_{i}}(\mathcal{D}_{i})=-\sum_{\textbf{X}}P(\bm{x}|% \mathcal{D}_{i})\log P_{\mathcal{B}_{i}}(\bm{x}|\mathcal{D}_{i})=\sum_{j=1}^{n% }H(X_{j}|\Pi_{j}^{\mathcal{B}_{i}},\mathcal{D}_{i}).$ (4)

Figure 6.

Example of BKDB.

Figure 7.

The distribution and histogram of $H(X_{i}|X_{j})$ .

The number of bits encoded in an ideal $\mathcal{B}_{i}$ should correspond to the minimum of $H_{\mathcal{B}_{i}}(\mathcal{D}_{i})$ . As shown in Fig. 6, similar to the basic idea of KDB [27], the attributes for subset $\mathcal{D}_{i}$ are sorted by comparing $H(X_{j}|\mathcal{D}_{i})$ and the conditional dependencies between them are identified by comparing $H(X_{j}|\Pi_{j},\mathcal{D}_{i})$ . Suppose that the attribute order is $\{X_{1},\cdots,X_{n}\}$ , then $\Pi_{j}$ may be any subset of $\{X_{1},\cdots,X_{j-1}\}$ . To achieve a tradeoff between space and time complexities, a critical issue is how to choose the appropriate $\Pi_{j}$ . The subsumption resolution (SR) assumes [44] that, if $P(x_{k}|x_{j})=1$ , then the attribute value $x_{k}$ is determined by $x_{j}$ , and $x_{k}$ can be regarded as redundant if $x_{j}$ exists, i.e., $P(\bm{x})=P(x_{1},\cdots,x_{k-1},x_{k+1},\cdots,x_{n})$ . Similarly, if $P(x_{k}|\pi_{k})=1$ always holds for all possible values of $\{X_{k},\Pi_{k}\}$ , then $H(X_{k}|\Pi_{k})=0$ holds and Eq. (4) can be formulated as

$\displaystyle H_{\mathcal{B}_{i}}(\mathcal{D}_{i})=\sum_{j=1,j\neq k}^{n}H(X_{% j}|\Pi_{j}^{\mathcal{B}_{i}},\mathcal{D}_{i}).$ (5)

The conditional entropy $H(X_{i}|X_{j})$ can efficiently characterize the uncertainty of $X_{i}$ when all values of $X_{j}$ are known. Take the Spambase dataset for an example. The distribution of the estimates of $H(X_{i}|X_{j})$ and the corresponding histogram plot of $H(X_{i}|X_{j})$ are shown in Figs 7a and b, respectively, which reveal that the correlations among the attributes vary greatly and that lower values of $H(X_{i}|X_{j})$ happen more often than not. Therefore, redundant attributes can be identified by comparing $H(X_{i}|\Pi_{i})$ .

In the following discussion, if the values of $H_{\mathcal{B}_{i}}(\mathcal{D}_{i})$ do not change significantly (less than 5%) before and after removing $H(X_{k}|\Pi_{k},\mathcal{D}_{i})(1\leqslant k\leqslant n)$ from $H_{\mathcal{B}_{i}}(\mathcal{D}_{i})$ , then $X_{k}$ will be identified as redundant and the edges pointing to it will be removed. However, the edges pointing from $X_{k}$ to the other attributes remain, that is, $X_{k}$ can still be the parent of other attributes. This approach can help reduce conditional entropy while improving the general robustness of the network structure. The procedure of learning BKDB ${}_{i}$ from training subspace $D_{i}$ is described in Algorithm 7.

[htbp] LearnStructure ( $\mathcal{D}_{i}$ ).Training subset $D_{i}$ , dependence degree $k$ . The topology of BKDB ${}_{i}$ .

Compute $H(X_{j}|\mathcal{D}_{i})$ for each attribute $X_{i}$ . Compute $H(X_{j}|X_{k},\mathcal{D}_{i})(j\neq k)$ for each pair of attributes.

Let $\mathcal{L}$ be a attribute list in ascending order of $H(X_{i}|\mathcal{D}_{i})$ .Initialize the used attribute list $S=\varnothing$ . Initialize the entropy function $H(\mathcal{D}_{i})=H^{\prime}=0$ . Let the topology of BKDB ${}_{i}$ begin with a single class node $Y$ . $j=1\to n$ Add a node to BKDB ${}_{i}$ representing $\mathcal{L}_{j}$ ;Add an edge from $Y$ to $\mathcal{L}_{j}$ in BKDB ${}_{i}$ ;Initialize $\Pi_{j}=\{Y\}$ ; Add $q=\min(\|S\|,k)$ edges from $q$ distinct attributes $X_{p}$ in $S$ with the minimum value for $H(\mathcal{L}_{j}|X_{p},\mathcal{D}_{i})$ and add $X_{p}$ to $\Pi_{j}$ ;Add $\mathcal{L}_{j}$ to $S$ ; $H(\mathcal{D}_{i})=H(\mathcal{D}_{i})+H(\mathcal{L}_{j}|\Pi_{j},\mathcal{D}_{i})$ ;

$j=1\to n$ $H^{\prime}\geqslant H(\mathcal{D}_{i})*0.95$ Remove edges $X_{q}\rightarrow\mathcal{L}_{j}$ and $Y\rightarrow\mathcal{L}_{j}$ from BKDB ${}_{i}$ where $X_{q}\in\Pi_{j}$ ; $H^{\prime}=H^{\prime}+H(\mathcal{L}_{j}|\Pi_{j},\mathcal{D}_{i})$ ;Return BKDB ${}_{i}$ .

To perform precise calculations of Eqs (1) and (2) for structure learning, the critical issue is to choose suitable distributions for the probabilities. For dataset $\mathcal{D}_{i}$ that contains instances with class label $y_{i}$ , the prior probability $P(x_{j})$ , conditional probability $P(x_{j}|\pi_{j})$ and joint probability $P(x_{j},\pi_{j})$ are estimated as

$\displaystyle P(x_{j}|\mathcal{D}_{i})=\frac{\sum_{i=1}^{N_{i}}\delta(x_{j})}{% N_{i}}$ (6) $\displaystyle P(x_{j},\pi_{j}|\mathcal{D}_{i})=\frac{\sum_{i=1}^{N_{i}}\delta(% x_{j},\pi_{j})}{N_{i}}$ (7) $\displaystyle P(x_{j}|\pi_{j},\mathcal{D}_{i})=\frac{\sum_{i=1}^{N_{i}}\delta(% x_{j},\pi_{j})}{\sum_{i=1}^{N_{i}}\delta(\pi_{j})}$ (8)

where $N_{i}$ is the number of training instances in $\mathcal{D}_{i}$ , $\delta(\cdot)$ is a binary function that is one if its parameters appear in the $i$ -th instance or zero otherwise.

Figure 8.

Algorithm flowchart.

3.3 Local conditional dependencies among attribute values in the testing instance

If BNCs focus on learning the general conditional dependencies from the training data while neglecting the characteristics of different instances, then the resulting overfitting will lead to biased estimates of conditional probability and negative effect on classification performance. To address this issue, by pre-assigning class label $y_{i}$ to testing instance $t=\{x_{1},\ldots,x_{n}\}$ , we aim to give high priority to the “right” conditional dependencies among the attribute values in the complete pseudo instance $t_{i}=\{x_{1},\ldots,x_{n},y_{i}\}$ , which will be described by a local BNC $b_{i}$ . The number of bits encoded in $b_{i}$ can be measured by

$\displaystyle h_{b_{i}}(t_{i})=-\log P_{b_{i}}(t_{i})=-\sum_{j=1}^{n}\log P(x_% {j}|\pi_{j}^{b_{i}})=-\sum_{j=1}^{n}h(x_{j}|\pi_{j}^{b_{i}}).$ (9)

To minimize $h_{b_{i}}(t_{i})$ , the conditional dependence between $x_{j}$ and its parents $\pi_{j}$ should help minimize each factor in $h_{b_{i}}(t_{i})$ , that is, $h(x_{j}|\pi_{j}^{b_{i}})$ . Similar to the learning procedure of Algorithm 7, the attribute values in $t_{i}$ are sorted by comparing $h(x_{j})$ , and the conditional dependencies between them are identified by comparing $h(x_{j}|\pi_{j}^{b_{i}})$ . If the values of $h_{b_{i}}(t_{i})$ do not change significantly (less than 5%) before and after removing $h(x_{j}|\pi_{j}^{b_{i}})(1\leqslant k\leqslant n)$ from $h_{b_{i}}(t_{i})$ , then $x_{k}$ will be identified as redundant and the edges pointing to it will be removed. The procedure of learning $b_{i}$ from $t_{i}$ is shown in Algorithm 3.3.

[h] LearnStructure ( $t_{i}$ ).Instance $t_{i}=\{x_{1},\cdots,x_{n},y_{i}\}$ with pre-assigned label $y_{i}$ , dependence degree $k$ . The topology of bkdb ${}_{i}$ . Compute $h(x_{j}|\emph{t}_{i})$ for each attribute $X_{j}$ . Compute $h(x_{j}|x_{k},\emph{t}_{i})$ $(j\neq k)$ for each pair of attribute values. Let $l$ be a attribute value list in ascending order of $h(x_{j}|\emph{t}_{i})$ .Initialize the used attribute value list $S=\varnothing$ . Initialize the entropy function $h(\emph{t}_{i})=h^{\prime}=0$ . Let the topology of bkdb ${}_{i}$ begin with a single class node $Y$ .

$j=1\to n$

Add a node to bkdb ${}_{i}$ representing $l_{j}$ ;Add an edge from $Y$ to $l_{j}$ in bkdb ${}_{i}$ ;Initialize $\Pi_{j}=\{Y\}$ ; Add $q=\min(\|S\|,k)$ edges from $q$ distinct attributes $X_{p}$ in $S$ with the minimum value for $h(l_{j}|x_{p},\emph{t}_{i})$ and add $X_{p}$ to $\Pi_{j}$ ;Add attribute $l_{j}$ to $S$ ;Compute $h(\emph{t}_{i})=h(\emph{t}_{i})+h(x_{j}|\pi_{j},\emph{t}_{i})$ ;

$j=\rm 1\to n$ $h^{\prime}\geqslant h(\emph{t}_{i})*0.95$ Remove edges $X_{q}\rightarrow l_{j}$ and $Y\rightarrow l_{j}$ from bkdb ${}_{i}$ where $X_{q}\in\Pi_{j}$ ; $h^{\prime}=h^{\prime}+h(l_{j}|\pi_{j},\emph{t}_{i})$ ;

The pseudo instance $t_{i}$ and training subset $\mathcal{D}_{i}$ form a new pseudo training subset $\mathcal{D}^{\prime}_{i}$ . To compute $h_{b_{i}}(t_{i})$ , the prior probability $P(x_{j})$ , conditional probability $P(x_{j}|\pi_{j})$ and joint probability $P(x_{j},\pi_{j})$ are estimated as

$\displaystyle P(x_{j}|\mathcal{D}^{\prime}_{i})=\frac{\sum_{i=1}^{N_{i}}\delta% (x_{j})+1}{N_{i}+1}$ (10) $\displaystyle P(x_{j}|\pi_{j},\mathcal{D}^{\prime}_{i})=\frac{\sum_{i=1}^{N_{i% }}\delta(x_{j},\pi_{j})+1}{\sum_{i=1}^{N_{i}}\delta(\pi_{j})+1}$ (11)

3.4 Bagging

The ensemble classifier should perform better, on average, than any individual member. Several combiners have been proposed to combine these members, including the linear, product, and voting combiners. $\mathcal{B}_{i}$ and $b_{i}$ learn from the training subset $\mathcal{D}_{i}$ and pseudo instance $t_{i}$ , respectively, and their topologies describe the conditional dependencies among the attributes or among specific attribute values, respectively. $\mathcal{B}_{i}$ is robust whereas it may not represent the conditional dependencies implicated in $t_{i}$ , especially when the attribute values in $t_{i}$ rarely appear in $\mathcal{D}_{i}$ . On the contrary, $b_{i}$ can precisely model the conditional dependencies among the attribute values in $t_{i}$ whereas $b_{i}$ is non-robust. Given that $\mathcal{B}_{i}$ and $b_{i}$ are built independently and are complementary in nature, the linear combiner is applicable to them. In this case, the estimate of conditional probability for $\mathcal{B}_{i}$ and $b_{i}$ is

$\displaystyle P(\bm{x}|y_{i})=\mathcal{W}_{\mathcal{B}_{i}}\cdot P(\bm{x}|y_{i% },\mathcal{B}_{i})+\mathcal{W}_{b_{i}}\cdot P(\bm{x}|y_{i},b_{i}).$ (12)

If the weights $\mathcal{W}_{\mathcal{B}_{i}}$ = $\mathcal{W}_{b_{i}}$ = $1/2$ , then the above estimate represents a simple uniform averaging of the probability estimates. The notation clearly allows for the possibility of a non-uniformly weighted average. If the classifiers have different accuracies on the data, then a non-uniform combination can theoretically produce lower errors than a uniform combination. However, adaptively determining the values of $\mathcal{W}_{\mathcal{B}_{i}}$ and $\mathcal{W}_{b_{i}}$ for different instances is always difficult. Therefore, the uniformly weighted average is often used in practice.

Diversity has been recognized as a very important characteristic in classifier combination. Bagging enhances diversity in an ensemble by training each member on a bootstrap resampled set of data drawn from the original training data [45]. The diversity of the resampled sets directly determines the diversity of BNC members. A high level of diversity is necessary for to improve ensemble BNCs. To address this issue, in this paper $\mathcal{D}_{i}$ and $t_{i}$ are introduced and they are obviously two different data subsets ( $t_{i}$ never appears in $\mathcal{D}_{i}$ and they are disjoint). As shown in Fig. 10, the corresponding BNCs $\mathcal{B}_{i}$ and $b_{i}$ learned are combined to describe the dependency relationship conditioned on class label $y_{i}$ . The following Bayes rule is then applied for the prediction and classification:

$\displaystyle y^{*}=\arg\max_{y_{i}\in Y}P(\bm{x},y_{i})=\arg\max P(y_{i})P(% \bm{x}|y_{i}).$ (13)

The classification procedure is presented in Algorithm 3.

[htbp] Classification.Training set $\mathcal{D}$ , testing instance $t$ and dependence degree $k$ . Class label $y^{*}$ for instance $t$ . Let $\mathcal{D}_{i}$ be the subspace of $\mathcal{D}$ with label $y_{i}$ , and let $t_{i}$ be the complete form of $t$ with pre-assigned label $y_{i}$ . $i=1\to m$ Let $\mathcal{B}_{i}=$ LearnStructure ( $\mathcal{D}_{i}$ ). $/*$ Algorithm 1 $*/$ Let $b_{i}=$ LearnStructure ( $t_{i}$ ). $/*$ Algorithm 2 $*/$ Compute $P(\bm{x}|y_{i})$ according to Eq. (12). Assign class label $y^{*}$ to instance $t$ according to Eq. (13). $y^{*}$ .

4. Experiments and results

Table 1
Datasets

Index	Dataset	#Instance	#Attribute	#Class	Index	Dataset	#Instance	#Attribute	#Class
1	Lung-cancer	32	56	3	28	Mfeat-mor	2,000	6	10
2	Labor-negotiations	57	16	2	29	Hypothyroid	3,163	25	2
3	Zoo	101	16	7	30	Kr-vs-kp	3,196	36	2
4	Echocardiogram	131	6	2	31	Dis	3,772	29	2
5	Lymphography	148	18	4	32	Hypo	3,772	29	4
6	Iris	150	4	3	33	Sick	3,772	29	2
7	Teaching-ae	151	5	3	34	Abalone	4,177	8	3
8	Hepatitis	155	19	2	35	Spambase	4,601	57	2
9	Wine	178	13	3	36	Waveform-5000	5,000	40	3
10	Autos	205	25	7	37	Phoneme	5,438	7	50
11	Sonar	208	60	2	38	Wall-following	5,456	24	4
12	Glass-id	214	9	3	39	Page-blocks	5,473	10	5
13	Audio	226	69	24	40	Optdigits	5,620	64	10
14	Dermatology	366	34	6	41	Satellite	6,435	36	6
15	House-votes-84	435	16	2	42	Mushrooms	8,124	22	2
16	Chess	551	39	2	43	Thyroid	9,169	29	20
17	Syncon	600	60	6	44	Pendigits	10,992	16	10
18	Soybean	683	35	19	45	Sign	12,546	8	3
19	Credit-A	690	15	2	46	Nursery	12,960	8	5
20	Crx	690	15	2	47	Magic	19,020	10	2
21	Breast-cancer-w	699	9	2	48	Letter-recog	20,000	16	26
22	Pima-ind-diabetes	768	8	2	49	Adult	48,842	14	2
23	Vehicle	846	18	4	50	Shuttle	58,000	9	7
24	Anneal	898	38	6	51	Connect-4	67,557	42	3
25	Tic-tac-toe	958	9	2	52	Waveform	100,000	21	3
26	Vowel	990	13	11	53	Localization	164,860	5	11
27	Car	1,728	6	4	54	Poker-hand	1,025,010	10	10

To compare the classification performance and clarify the difference among BNCs while dealing with datasets of different sizes, we gather a group of small datasets having less than 2000 instances and a group of relatively large datasets having more than 2000 instances, and up to one million instances. Small and large datasets respectively account for 50% of the total 54 datasets, which are publicly available from the UCI machine learning repository [46] and are described in detail in Table 1. We roughly divide the algorithms for comparison into three categories. The first one contains two state-of-the-art single-model BNCs, including TAN and KDB with $k=2$ . The second one consists of AODE and its variants, such as AODE, AODE-SR [44] and WAODE-MI [17]. In the last category, NB and TAN are respectively employed as the base learners of Bagging and AdaBoost. For estimating the probability distributions by counting, numeric attributes are discretized by using Minimum Description Length (MDL) [47]. Missing values for qualitative attributes are considered as a distinct value in all cases and those for quantitative attributes are replaced with means from the training data. Consider the possible “noise” in these data sets, we hypothesize that there is sufficient data present for every possible combination of attribute values, and direct estimation of each relevant multi-variate probability will still be reliable for BNC learning.

The classification performance is compared and analyzed in terms of zero-one loss, root mean square error (RMSE), bias, variance and MCC. Statistically a Win/Draw/Loss record (W/D/L) is calculated for each pair of competitors $A$ and $B$ with regard to a performance measure $M$ . The record represents the number of datasets in which $A$ respectively performs better, equally well or worse than $B$ in terms of $M$ . When the outcome of a one-tailed binomial sign test is less than 0.05, the difference between algorithms is supposed to be significant.

The abbreviations for competing algorithms are described below:

•

TAN, Tree-augmented Naive Bayes.

•

K ${}_{2}$ DB, $k$ -dependence Bayesian classifier with $k=2$ .

•

AODE, Averaged one-dependence estimators.

•

AODE-SR, AODE with subsumption resolution.

•

WAODE-MI, AODE using mutual information as the weight of each SPODE.

•

Boosting ${}_{\mathrm{NB}}$ , Boosting algorithm with NB employed as the base learning algorithm.

•

Boosting ${}_{\mathrm{TAN}}$ , Boosting algorithm with TAN employed as the base learning algorithm.

•

Bagging ${}_{\mathrm{NB}}$ , Bagging algorithm with NB employed as the base learning algorithm.

•

Boosting ${}_{\mathrm{TAN}}$ , Bagging algorithm with TAN employed as the base learning algorithm.

•

BKDB, Bagging $k$ -dependence BNC with $k=2$ .

The Boosting and Bagging algorithms are implemented with the Weka work-branch (version 3.8.3) using Java 8, other algorithms are conducted using C++.

4.1 Comparison of zero-one loss

Table 2
Win-Draw-Loss results of zero-one loss

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
Loss
TAN	37-7-10	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	34-9-11	25-14-15	–	–	–	–	–	–	–	–
AODE	39-11-4	22-16-16	24-13-17	–	–	–	–	–	–	–
AODE-SR	39-11-4	23-17-14	26-13-15	7-46-1	–	–	–	–	–	–
WAODE-MI	40-12-2	30-14-10	26-15-13	11-37-6	9-38-7	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	28-15-11	15-10-29	15-6-33	8-15-31	9-13-32	7-10-37	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	39-5-10	24-13-17	20-11-23	20-9-25	19-10-25	16-12-26	31-11-12	–	–	–
Bagging ${}_{\mathrm{NB}}$	11-30-13	14-5-35	12-6-36	8-7-39	8-4-42	8-6-40	12-16-26	13-5-36	–	–
Bagging ${}_{\mathrm{TAN}}$	41-5-8	28-18-8	24-11-19	21-14-19	20-14-20	13-22-19	41-6-7	25-13-16	41-7-6	–
BKDB	42-6-6	38-12-4	35-14-5	34-12-8	32-13-9	30-15-9	44-3-7	37-7-10	40-7-7	28-14-12

Table 3

Win-Draw-Loss results of zero-one loss on small datasets

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
Loss
TAN	14-3-10	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	11-6-10	7-7-13	–	–	–	–	–	–	–	–
AODE	14-9-4	10-8-9	14-10-3	–	–	–	–	–	–	–
AODE-SR	14-9-4	10-8-9	16-8-3	2-25-0	–	–	–	–	–	–
WAODE-MI	14-11-2	13-6-8	16-7-4	5-19-3	5-18-4	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	11-6-10	9-5-13	11-4-12	4-7-16	5-7-15	4-5-18	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	15-3-9	11-4-12	15-3-9	10-2-15	10-2-15	10-2-15	12-5-10	–	–	–
Bagging ${}_{\mathrm{NB}}$	9-10-8	13-2-12	11-4-12	8-4-15	8-2-17	8-4-15	12-3-12	13-1-13	–	–
Bagging ${}_{\mathrm{TAN}}$	14-5-8	14-8-5	17-4-6	11-7-9	12-5-10	9-9-9	19-4-4	17-1-9	14-7-6	–
BKDB	17-4-6	16-7-4	19-6-2	14-7-6	13-8-6	13-7-7	19-2-6	18-3-6	14-6-7	12-6-9

Table 4

Win-Draw-Loss results of zero-one loss on large datasets

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
Loss
TAN	23-4-0	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	23-3-1	18-7-2	–	–	–	–	–	–	–	–
AODE	25-2-0	12-8-7	10-3-14	–	–	–	–	–	–	–
AODE-SR	25-2-0	13-9-5	10-5-12	5-21-1	–	–	–	–	–	–
WAODE-MI	26-1-0	17-8-2	10-8-9	6-18-3	4-20-3	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	17-9-1	6-5-16	4-2-21	4-8-15	4-6-17	3-5-19	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	24-2-1	13-9-5	5-8-14	10-7-10	9-8-10	6-10-11	19-6-2	–	–	–
Bagging ${}_{\mathrm{NB}}$	2-20-5	1-3-23	1-2-24	0-3-24	0-2-25	0-2-25	0-13-14	0-4-23	–	–
Bagging ${}_{\mathrm{TAN}}$	27-0-0	14-10-3	7-7-13	10-7-10	8-9-10	4-13-10	22-2-3	8-12-7	27-0-0	–
BKDB	25-2-0	22-5-0	16-8-3	20-5-2	19-5-3	17-8-2	25-1-1	19-4-4	26-1-0	16-8-3

The detailed zero-one loss records are shown in Table A1. Corresponding W/D/L records are shown in Table 2, from which high-dependence BNCs show significant advantage over their competitors. TAN beats NB on 37 datasets and loses on 10. K ${}_{2}$ DB beats TAN on 25 datasets and loses on 15. Ensemble BNCs perform better than single-model ones. AODE beats TAN on 22 datasets and loses on 16, and beats K ${}_{2}$ DB on 24 datasets and loses on 17. Variants of AODE prove their effectiveness when compared to AODE in terms of zero-one loss. AODE-SR beats AODE on 7 datasets and loses on 1, and WAODE-MI beats AODE on 11 datasets and loses on 6. Bagging and Boosting are regarded as relatively simple device to improve the predictive performance of the base learner. Boosting ${}_{\mathrm{NB}}$ and Boosting ${}_{\mathrm{Tan}}$ respectively beats NB and TAN on 28 and 24 datasets. Bagging ${}_{\mathrm{NB}}$ is competitive with NB (11 wins and 13 losses) whereas the advantage of Bagging ${}_{\mathrm{Tan}}$ over TAN is relatively significant (28 wins and 8 losses). BKDB performs the best among all the BNCs.

For further analysis of the underlying mechanisms of these BNCs, we respectively provide the experimental results on small datasets and large datasets in terms of zero-one loss in Tables 3 and 4. The advantage of high-dependence BNCs is not significant while dealing small datasets, and some times they even perform poorer. TAN beats NB on 14 datasets and loses on 10. K ${}_{2}$ DB beats TAN on 7 datasets whereas loses on 13. The effectiveness of Bagging and Boosting is reduced to some extent, and only Bagging ${}_{\mathrm{Tan}}$ retains its advantage over TAN (14 wins and 5 losses). The advantage of BKDB is much more significant when compared to single-model BNCs. Obviously, small datasets cannot provide enough instances and biased estimate of conditional probabilities may results in biased estimate of joint probability, that will greatly reduce the generalization performance of single-model BNCs. In contrast, Bagging can help mitigate the negative effect caused, that can be proved from the experimental results that Bagging ${}_{\mathrm{Tan}}$ beats Boosting ${}_{\mathrm{Tan}}$ on 17 datasets and loses on 9. As for large datasets, mass data provides an important prerequisite for mining dependency relationships of high confidence level. From the experimental results in Table 4 we can see that, high-dependence topology, weighting, Bagging and Boosting all help improve the classification performance. BKDB can learn arbitrary $k$ -dependence relationships from disjoint subspaces of training data, and the diversity in dependency relationships can be fully represented by Bagging.

4.2 Comparison of bias and variance

Table 5
Win-Draw-Loss results of bias and variance

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
Bias
TAN	34-7-13	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	35-7-12	29-19-6	–	–	–	–	–	–	–	–
AODE	40-12-2	25-17-12	20-8-26	–	–	–	–	–	–	–
AODE-SR	40-11-3	27-19-8	20-11-23	2-51-1	–	–	–	–	–	–
WAODE-MI	41-7-6	27-20-7	19-13-22	12-35-7	12-36-6	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	37-10-7	26-4-24	25-4-25	20-6-28	20-6-28	20-6-28	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	44-2-8	41-7-6	31-9-14	33-7-14	32-8-14	32-7-15	32-15-7	–	–	–
Bagging ${}_{\mathrm{NB}}$	24-15-15	13-4-37	15-1-38	10-5-39	10-4-40	9-4-41	4-13-37	3-5-46	–	–
Bagging ${}_{\mathrm{TAN}}$	41-4-9	22-17-15	19-6-29	23-9-22	24-7-23	19-14-21	25-10-19	8-17-29	44-5-5	–
BKDB	37-8-9	35-13-6	25-16-13	26-15-13	25-15-14	22-17-15	29-5-20	18-8-28	39-4-11	26-12-16
Variance
TAN	6-5-43	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	11-2-41	11-13-30	–	–	–	–	–	–	–	–
AODE	11-9-34	38-9-7	41-5-8	–	–	–	–	–	–	–
AODE-SR	14-8-32	40-8-6	42-6-6	7-46-1	–	–	–	–	–	–
WAODE-MI	10-7-37	37-8-9	39-7-8	6-35-13	5-34-15	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	5-2-47	15-5-34	21-7-26	7-7-40	6-8-40	7-6-41	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	5-2-47	4-8-42	11-10-33	4-2-48	3-3-48	3-3-48	11-15-28	–	–	–
Bagging ${}_{\mathrm{NB}}$	18-9-27	38-5-11	39-4-11	27-6-21	26-7-21	26-7-21	42-5-7	46-3-5	–	–
Bagging ${}_{\mathrm{TAN}}$	9-7-38	32-6-16	38-1-15	12-8-34	11-8-35	15-9-30	30-12-12	46-6-2	10-6-38	–
BKDB	13-6-35	38-4-12	40-10-4	16-13-25	14-14-26	17-13-24	40-3-11	44-4-6	18-6-30	26-7-21

The bias-variance decomposition for zero-one loss is often used for analyzing the performance of ensemble algorithms [21, 28]. The W/D/L records in terms of bias and variance are shown in Table 5. The detailed bias and variance records are respectively shown in Tables A2 and A3.

In terms of bias TAN beats NB with 34 wins and 13 losses, K ${}_{2}$ DB beats TAN with 29 wins and 6 losses, and AODE and its variants perform similarly to K ${}_{2}$ DB. Thus the bias advantage can be attributed to the complex topology of high-dependence single BNCs or relatively simple topologies represented by different committee members of ensemble BNCs. Boosting ${}_{\mathrm{NB}}$ enjoys significant advantage over NB (37 wins and 7 losses), and Boosting ${}_{\mathrm{TAN}}$ over TAN (41 wins and 6 losses). Boosting focuses on the wrongly classified instances and this strategy has proved to be feasible for reducing the bias of the base learner. In contrast, the effectiveness of Bagging is less significant. For example, Bagging ${}_{\mathrm{TAN}}$ beats TAN with 22 wins and 15 losses.

It is very difficult to achieve the trade-off between bias and variance. Low bias with high variance or high bias with low variance often happens. In terms of variance NB beats TAN with 43 wins and 6 losses, TAN beats K ${}_{2}$ DB with 39 wins and 11 losses. Obviously, complex topology increases the risk of overfitting and that may result in high variance. Because of the same reason, Boosting makes the final learner be sensitive to variations in the training data. NB beats Boosting ${}_{\mathrm{NB}}$ with 47 wins and 5 losses, and TAN beats Boosting ${}_{\mathrm{TAN}}$ with 42 wins and 4 losses. In contrast, Bagging introduces diversity by making the topologies of ensemble BNCs reflect possible dependency relationship implicated in different subspaces of training data, and that may greatly mitigate the negative caused by overfitting. Bagging ${}_{\mathrm{TAN}}$ beats TAN with 32 wins and 16 losses. AODE and its variants enjoy significant advantage over K ${}_{2}$ DB and TAN.

Figure 9.

Attribute values for instance $T_{1}$ , $T_{2}$ and $T_{3}$ .

High-dependence topology and Bagging help BKDB exhibit excellent bias-variance trade-off. Among 2-dependence BNCs, BKDB enjoys significant advantage over K ${}_{2}$ DB in terms of bias (25 wins and 13 lossses) and variance (40 wins and 4 lossses). To illustrate the basic idea of BKDB, we take three testing instances $T_{1}$ , $T_{2}$ and $T_{3}$ (see detail in Fig. 9) from dataset Spambase. Suppose that we have divided dataset Spambase into different subspaces $\mathcal{D}_{i}$ with class labels $y_{i}$ , and preassigned $T_{i}(1\leqslant i\leqslant 3)$ with different class labels $y_{0}$ or $y_{1}$ . Similar to Figs 4 and 5, the contour plots of conditional dependencies learned are shown in Fig. 10. Given different class label $y_{j}$ , the topology learned will overfit pseudo instance $(T_{i},y_{j})$ and that may help reduce the sensitivity to training data. From Fig. 10 we can clearly see that, the topologies learned from $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ may be different, and the topologies learned from $(T_{i},y_{j})(1\leqslant i\leqslant 3,0\leqslant j\leqslant 1)$ may vary greatly. The diversity in topologies resulted from the disjoint training data or pseudo instances exploits the advantages of Bagging to the full.

Figure 10.

The contour plots of conditional dependencies learned from (a) $\mathcal{D}_{0}$ , (b) $(T_{1},y_{0})$ , (c) $(T_{2},y_{0})$ , (d) $(T_{3},y_{0})$ , (e) $\mathcal{D}_{1}$ , (f) $(T_{1},y_{1})$ , (g) $(T_{2},y_{1})$ , and (h) $(T_{3},y_{1})$ .

4.3 Root mean squared error

Regularly RMSE is used as a standard statistical metric for model evaluation and is defined as:

$\displaystyle\mathrm{RMSE}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}{(1-\hat{P}(y|\bm{x}% ))^{2}}}$ (14)

where $\hat{P}(y|\bm{x})$ is the predicted posterior probability of the true class label given $\bm{x}$ . The RMSE records are shown in Table A4 and corresponding W/D/L records are shown in Table 6. TAN beats NB on 40 datasets and loses on 7. K ${}_{2}$ DB beats TAN on 19 datasets and loses on 9. Thus high-dependence topology will help differentiate posterior probability of the true class label from those of the wrong labels. NB is robust since its topology is definite regardless of the variation in training data, whereas TAN is unstable since the conditional dependencies implicated may vary due to the variation. Boosting is applicable to robust BNC but not applicable to unstable BNC. Boosting ${}_{\mathrm{NB}}$ outperforms NB with 23 wins and 15 losses, whereas TAN outperforms Boosting ${}_{\mathrm{TAN}}$ with 28 wins and 12 losses. AODE beats K ${}_{2}$ DB on 19 datasets and loses on 12. AODE and its variants perform similarly in terms of RMSE. Bagging ${}_{\mathrm{NB}}$ outperforms NB with 13 wins and 6 losses, Bagging ${}_{\mathrm{TAN}}$ outperforms TAN with 24 wins and 2 losses. Bagging shows significant advantage over Boosting in improving the base learner in terms of RMSE. BKDB has the characteristics of high-dependence topology and Bagging, and performs the best among all the algorithms in terms of RMSE.

Table 6

Win-Draw-Loss results of RMSE on 54 datasets

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
RMSE
TAN	40-7-7	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	38-7-9	19-26-9	–	–	–	–	–	–	–	–
AODE	36-14-4	16-28-10	19-23-12	–	–	–	–	–	–	–
AODE-SR	39-11-4	19-28-7	19-25-10	1-52-1	–	–	–	–	–	–
WAODE-MI	40-10-4	20-28-6	18-26-10	5-47-2	3-49-2	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	23-16-15	9-15-30	10-15-29	6-15-33	6-14-34	6-14-34	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	26-13-15	12-14-28	11-17-26	8-14-32	7-14-33	7-14-33	23-16-15	–	–	–
Bagging ${}_{\mathrm{NB}}$	13-35-6	11-8-35	11-8-35	8-12-34	7-9-38	7-9-38	18-16-20	20-8-26	–	–
Bagging ${}_{\mathrm{TAN}}$	43-4-7	24-28-2	23-19-12	25-18-11	20-22-12	15-27-12	40-8-6	38-8-8	42-8-4	–
BKDB	43-8-3	27-23-4	23-24-7	29-18-7	25-22-7	23-24-7	40-9-5	40-8-6	38-11-5	19-24-11

4.4 Matthews correlation coefficient

Figure 11.

The distribution of $H(Y)$ on 54 datasets.

Most datasets don’t have exactly the same number of instances in each class. The entropy function $H(Y)$ is applied to measure the extent to which the data is unevenly distributed for different classes and the distribution of values of $H(Y)$ is shown in Fig. 11. From Fig. 11, we can see that the values of $H(Y)$ vary greatly for different datasets, among which dataset Kr-vs-kp (No. 30) has the minimum value of $H(Y)$ . Matthews correlation coefficients (MCC) [48] is commonly applied in machine learning as a measure of the quality of binary and multi-class classifications. The higher MCC value corresponds to better performance. For training data with $m$ class labels, the multi-class problem is first converted into a two-class problem as depicted in [49], and the $m\times m$ -dimensional confusion matrix or contingency table C summarizes the results of the classifications as follows:

$\displaystyle C=\left[\begin{array}[]{ccc}C_{11}&\dots&C_{1m}\\ \vdots&\ddots&\vdots\\ C_{m1}&\dots&C_{mm}\\ \end{array}\right]$

From Eq. (2), for single-model BNCs, e.g., TAN or KDB, the conditional dependence measured by conditional mutual information may not generalize well to training subspace of the minority class. The diversity introduced by Bagging makes the committee member underfit the whole training data. By dividing training data into subspaces according to class labels, BKDB can deeply mine the conditional dependencies given specific class label and that will greatly mitigate the negative effect caused by imbalanced data.

The detailed MCC records are shown in Table A5. From the W/D/L records shown in Table 7, K ${}_{2}$ DB beats TAN, and AODE and its variants beat K ${}_{2}$ DB although the advantages are not significant. Bagging is more effective in terms of MCC when applied to BNCs with significant dependency relationships. For example, Bagging ${}_{\mathrm{TAN}}$ outperforms TAN with 6 wins and 3 losses, and outperforms AODE with 9 wins and 4 losses. It even outperforms 2-dependence KDB, i.e., K ${}_{2}$ DB, with 9 wins and 7 losses. In contrast, the advantage of BKDB is more significant compared to other BNCs. For example, it outperforms K ${}_{2}$ DB with 18 wins and only 1 loss, and outperforms AODE with 16 wins and 5 losses.

Table 7

Win-Draw-Loss results of MCC on 54 datasets

Classifier	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$
MCC
TAN	23-24-7	–	–	–	–	–	–	–	–	–
K ${}_{2}$ DB	25-18-11	11-35-8	–	–	–	–	–	–	–	–
AODE	26-25-3	8-41-5	12-32-10	–	–	–	–	–	–	–
AODE-SR	26-25-3	10-39-5	12-32-10	1-52-1	–	–	–	–	–	–
WAODE-MI	27-25-2	12-37-5	12-35-7	3-48-3	2-49-3	–	–	–	–	–
Boosting ${}_{\mathrm{NB}}$	13-26-9	5-29-14	6-25-17	5-26-17	3-28-17	3-25-20	–	–	–	–
Boosting ${}_{\mathrm{TAN}}$	20-16-11	7-33-7	7-31-9	7-28-12	7-27-13	6-28-13	16-25-5	–	–	–
Bagging ${}_{\mathrm{NB}}$	9-35-4	6-19-23	10-15-23	6-17-25	6-16-26	5-19-24	7-27-13	10-14-22	–	–
Bagging ${}_{\mathrm{TAN}}$	22-21-3	6-37-3	9-30-7	9-33-4	9-31-6	9-32-5	20-21-4	9-33-4	19-22-4	–
BKDB	29-22-3	20-34-0	18-35-1	16-33-5	16-32-6	15-34-5	24-22-2	15-30-2	23-20-5	10-32-4

Figure 12.

Comparisons of training and classification time.

4.5 Time

We present the comparisons results of training time and classification time in Fig. 12. All experiments have been conducted on a desktop computer with AMD Ryzen 5 1500X CPU @ 3.80 GHz, 64 bits and 32G of memory. No parallelization techniques have been used in any case, although most algorithms could be parallelized. As shown in Fig. 12, Bagging needs more time than Boosting for training. As indicated by the analysis of structure complexity, K ${}_{2}$ DB needs more time than TAN for training. Both NB and AODE don’t need to learn the topology, but only need to build the conditional probability table for estimating the conditional probabilities. The training time for BKDB is highly related to the number of classes and data quantities, and it only needs less time for training compared to Boosting ${}_{\mathrm{TAN}}$ and Bagging ${}_{\mathrm{TAN}}$ . For dataset $\mathcal{D}_{i}$ containing instances with class label $y_{i}$ , our implementation of BKDB generates a three-dimensional table of co-occurrence counts for each combination of three attribute values. As an entry must be updated for every training instance and every combination of the three attribute-values for that instance, the time complexity of forming the three dimensional probability table is $\mathcal{O}(Nn^{3})$ , where $n$ is the number of attributes and $N$ is the number of training instances. To learn the general conditional dependencies BKDB ( $k=2$ ) needs to calculate the conditional entropy $H(X_{j}|\Pi_{j},\mathcal{D}_{i})$ , and the time complexity is $\mathcal{O}((nv)^{3})$ , where $v$ is the maximum number of discrete values that an attribute may take.

For classification, among single-model BNCs NB needs to estimate $P(y)$ and $P(x_{i}|y)$ , TAN needs to estimate $P(y)$ , $P(x_{i}|y)$ and $P(x_{i},x_{j},y)$ , and K ${}_{2}$ DB needs to estimate $P(y)$ and $P(x_{i},\pi_{i},y)$ where $\pi_{i}$ contains at most $k$ attribute values. More parameters means more classification time needed. As shown in Fig. 12, K ${}_{2}$ DB needs the most classification time among single-model BNCs. Bagging combines the probability estimates of committee members for classification and thus needs more time than Boosting for classification. AODE and its variants need more time than single-model BNCs. The time overhead for BKDB is significant compared to other BNCs. For testing instance with class label $y_{i}$ , according to Eqs (12) and (13), BKDB ( $k=2$ ) needs to update the estimates of conditional probabilities and the time complexity is $\mathcal{O}(Mn^{3})$ , where $M$ is the number of testing instances. To learn the local conditional dependencies BKDB ( $k=2$ ) needs to calculate the local conditional entropy $h(x_{j}|\pi_{j})$ and the time complexity is $\mathcal{O}(nv^{3})$ . To classify a testing instance, according to Eqs (14) and (15), BKDB needs extra time to estimate $P(\textbf{x}|y_{i})$ and calculate the joint probability $P(\textbf{x},y_{i})$ for comparison, the time complexity is $\mathcal{O}(mnv^{3})$ , where $m$ is the number of class labels.

5. Conclusions and future work

Ensuring diversity among committee members is a critical issue in ensemble learning. By dividing the training data into disjoint subspaces according to their class labels and then preassigning a class label to each testing instance, BKDB provides a feasible way for mining conditional dependencies not only from training data but also from testing instances. The difference in the learning objects ensures the diversity among learned BNCs. The experimental results prove the effectiveness and efficiency of BKDB in terms of zero-one loss, bias, variance and etc.

The joint entropy defined in Eq. (6) can measure the extent to which the learned BNC fits the training data. The estimate of conditional probabilities produced by weak BNCs may be biased, and in our future research we seek to explore other approaches for ensuring that the division of training data can help minimize the joint entropy. Another feasible way to achieve a bias-variance trade-off is to assign different weights to the committee members in terms of joint entropy and then linearly combine their probability estimates.

Footnotes

Acknowledgments

This work is supported by the National Key Research and Development Program of China (No. 2019YFC1804804) and the Scientific and Technological Developing Scheme of Jilin Province (No. 20200201281JC).

Appendix A

Table A1

Experimental results of zero-one loss

Dataset	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$	BKDB
Lung-cancer	0.4375	0.5938	0.5625	0.5000	0.5000	0.5000	0.6250	0.5938	0.4062	0.4688	0.4688
Labor-negotiations	0.0702	0.1053	0.0702	0.0526	0.0526	0.0526	0.1228	0.1228	0.0877	0.0877	0.0877
Zoo	0.0297	0.0099	0.0495	0.0297	0.0297	0.0297	0.0396	0.0099	0.0594	0.0396	0.0198
Echocardiogram	0.3359	0.3282	0.3435	0.3206	0.3206	0.3206	0.3511	0.3511	0.2901	0.3053	0.3206
Lymphography	0.1486	0.1757	0.2365	0.1689	0.1689	0.1554	0.1622	0.1622	0.1419	0.1486	0.1351
Iris	0.0867	0.0800	0.0867	0.0867	0.0867	0.0867	0.0667	0.0600	0.0533	0.0533	0.0800
Teaching-ae	0.4967	0.5497	0.5364	0.4901	0.4768	0.4503	0.4768	0.5166	0.5563	0.5695	0.4305
Hepatitis	0.1935	0.1677	0.1871	0.1806	0.1871	0.1806	0.1871	0.1677	0.1355	0.1355	0.1548
Wine	0.0169	0.0337	0.0225	0.0225	0.0225	0.0169	0.0225	0.0449	0.0112	0.0169	0.0225
Autos	0.3122	0.2146	0.2049	0.2049	0.2049	0.1951	0.2293	0.1805	0.2780	0.1902	0.1707
Sonar	0.2308	0.2212	0.2452	0.2260	0.2212	0.2260	0.1683	0.2163	0.2356	0.2356	0.2212
Glass-id	0.2617	0.2196	0.2196	0.2523	0.2570	0.2570	0.2103	0.1963	0.1869	0.1776	0.1963
Audio	0.2389	0.2920	0.3230	0.2035	0.2080	0.1903	0.1947	0.2257	0.2611	0.3186	0.2522
Dermatology	0.0191	0.0328	0.0656	0.0164	0.0164	0.0191	0.0273	0.0383	0.0246	0.0191	0.0164
House-votes-84	0.0943	0.0552	0.0506	0.0529	0.0529	0.0506	0.0552	0.0598	0.0966	0.0552	0.0506
Chess	0.1125	0.0926	0.0998	0.0998	0.1016	0.0944	0.1307	0.0853	0.1270	0.0889	0.0762
Syncon	0.0283	0.0083	0.0133	0.0100	0.0100	0.0100	0.0217	0.0200	0.0317	0.0117	0.0167
Soybean	0.0893	0.0469	0.0556	0.0469	0.0483	0.0483	0.0615	0.0732	0.0688	0.0454	0.0527
Credit-a	0.1406	0.1507	0.1464	0.1391	0.1304	0.1362	0.1362	0.1710	0.1406	0.1333	0.1493
Crx	0.1377	0.1478	0.1565	0.1348	0.1377	0.1377	0.1449	0.1725	0.1362	0.1464	0.1406
Breast-cancer-w	0.0258	0.0415	0.0744	0.0358	0.0358	0.0358	0.0429	0.0701	0.0258	0.0386	0.0615
Pima-ind-diabetes	0.2448	0.2383	0.2448	0.2383	0.2370	0.2383	0.2578	0.2539	0.2409	0.2396	0.2409
Vehicle	0.3924	0.2943	0.2943	0.2896	0.2884	0.2872	0.3865	0.2683	0.3806	0.2825	0.2730
Anneal	0.0379	0.0111	0.0089	0.0089	0.0078	0.0089	0.0579	0.0535	0.0646	0.0501	0.0078
Tic-tac-toe	0.3069	0.2286	0.2035	0.2651	0.2651	0.2724	0.1660	0.1221	0.2975	0.2265	0.2067
Vowel	0.4242	0.1303	0.1818	0.1495	0.1505	0.1949	0.2061	0.0576	0.3152	0.0667	0.1354
Car	0.1400	0.0567	0.0382	0.0816	0.0816	0.0885	0.0978	0.0312	0.1453	0.0538	0.0388
Mfeat-mor	0.3140	0.2970	0.3060	0.3145	0.3135	0.3130	0.3180	0.2925	0.3170	0.2840	0.3010
Hypothyroid	0.0149	0.0104	0.0107	0.0136	0.0120	0.0104	0.0142	0.0117	0.0149	0.0101	0.0101
Kr-vs-kp	0.1214	0.0776	0.0416	0.0842	0.0720	0.0576	0.0513	0.0535	0.1236	0.0710	0.0426
Dis	0.0159	0.0159	0.0138	0.0130	0.0119	0.0143	0.0148	0.0141	0.0146	0.0138	0.0127
Hypo	0.0138	0.0141	0.0114	0.0095	0.0095	0.0101	0.0151	0.0148	0.0146	0.0090	0.0127
Sick	0.0308	0.0257	0.0223	0.0273	0.0252	0.0244	0.0276	0.0236	0.0286	0.0236	0.0255
Abalone	0.4762	0.4587	0.4563	0.4472	0.4475	0.4475	0.4870	0.4613	0.4805	0.4503	0.4577
Spambase	0.1015	0.0669	0.0635	0.0672	0.0680	0.0648	0.0696	0.0578	0.1013	0.0648	0.0630
Waveform-5000	0.2006	0.1844	0.2000	0.1462	0.1424	0.1450	0.1884	0.1828	0.1952	0.1636	0.1614
Phoneme	0.2615	0.2733	0.1984	0.2392	0.2365	0.2308	0.2479	0.2690	0.2773	0.2330	0.1878
Wall-following	0.1054	0.0554	0.0401	0.0370	0.0370	0.0367	0.0286	0.0519	0.1146	0.0663	0.0385
Page-blocks	0.0619	0.0415	0.0391	0.0338	0.0338	0.0347	0.0415	0.0343	0.0610	0.0362	0.0296
Optdigits	0.0767	0.0407	0.0372	0.0311	0.0302	0.0302	0.0582	0.0354	0.0758	0.0361	0.0262
Satellite	0.1806	0.1214	0.1080	0.1148	0.1148	0.1148	0.1571	0.1141	0.1768	0.1145	0.0979
Mushrooms	0.0196	0.0001	0.0000	0.0001	0.0002	0.0000	0.0000	0.0000	0.0379	0.0000	0.0000
Thyroid	0.1111	0.0720	0.0706	0.0701	0.0686	0.0655	0.1145	0.0903	0.1122	0.0783	0.0581
Pendigits	0.1181	0.0321	0.0294	0.0200	0.0200	0.0199	0.0759	0.0393	0.1185	0.0345	0.0152
Sign	0.3586	0.2755	0.2539	0.2821	0.2817	0.2768	0.3604	0.2767	0.3585	0.2684	0.2236
Nursery	0.0973	0.0654	0.0289	0.0730	0.0730	0.0708	0.0804	0.0282	0.0971	0.0583	0.0532
Magic	0.2239	0.1675	0.1637	0.1752	0.1751	0.1762	0.1741	0.1556	0.2221	0.1554	0.1513
Letter-recog	0.2525	0.1300	0.0986	0.0883	0.0879	0.0853	0.2569	0.1080	0.2556	0.1331	0.0503
Adult	0.1592	0.1380	0.1383	0.1493	0.1410	0.1445	0.1463	0.1459	0.1585	0.1384	0.1320
Shuttle	0.0039	0.0015	0.0009	0.0008	0.0008	0.0009	0.0007	0.0006	0.0055	0.0010	0.0006
Connect-4	0.2783	0.2354	0.2283	0.2420	0.2384	0.2406	0.2784	0.2355	0.2779	0.2356	0.2186
Waveform	0.0220	0.0202	0.0256	0.0180	0.0181	0.0181	0.0201	0.0200	0.0217	0.0192	0.0183
Localization	0.4955	0.3575	0.2964	0.3596	0.3596	0.3566	0.4950	0.3541	0.4935	0.3465	0.2652
Poker-hand	0.4988	0.3295	0.1961	0.4812	0.4812	0.1758	0.4988	0.3290	0.4988	0.2237	0.0699

Table A2

Experimental results of bias

Dataset	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$	BKDB
Lung-cancer	0.3330	0.3450	0.3490	0.2270	0.2270	0.2360	0.3256	0.3163	0.3006	0.3049	0.3980
Labor-negotiations	0.0505	0.0716	0.0553	0.0316	0.0316	0.0268	0.0419	0.0667	0.0276	0.0363	0.0547
Zoo	0.0318	0.0303	0.0403	0.0273	0.0273	0.0273	0.0786	0.0760	0.0844	0.0786	0.0330
Echocardiogram	0.2844	0.2642	0.3065	0.2751	0.2751	0.2572	0.2374	0.2350	0.2644	0.2543	0.2595
Lymphography	0.0902	0.1027	0.1041	0.0933	0.0933	0.0951	0.1658	0.1312	0.1598	0.1336	0.0933
Iris	0.0612	0.0638	0.0596	0.0586	0.0586	0.0656	0.0343	0.0359	0.0386	0.0315	0.0642
Teaching-ae	0.4836	0.4566	0.4606	0.4370	0.4370	0.3984	0.3678	0.3770	0.3800	0.3882	0.4336
Hepatitis	0.1537	0.1712	0.1741	0.1649	0.1649	0.1655	0.0774	0.0779	0.0970	0.0702	0.1733
Wine	0.0331	0.0507	0.0520	0.0346	0.0346	0.0381	0.0143	0.0181	0.0133	0.0157	0.0331
Autos	0.2181	0.2356	0.2253	0.2165	0.2165	0.2115	0.2056	0.1996	0.2328	0.2173	0.2138
Sonar	0.1672	0.1646	0.1686	0.1696	0.1696	0.1722	0.1191	0.1219	0.1596	0.1432	0.1664
Glass-id	0.2901	0.2756	0.2713	0.2785	0.2785	0.2780	0.1552	0.1441	0.1566	0.1406	0.2790
Audio	0.2733	0.3617	0.3493	0.1753	0.1753	0.1799	0.2263	0.2131	0.2828	0.2681	0.2932
Dermatology	0.0079	0.0274	0.0489	0.0055	0.0050	0.0061	0.0146	0.0326	0.0146	0.0289	0.0085
House-votes-84	0.0899	0.0410	0.0258	0.0430	0.0430	0.0406	0.0191	0.0183	0.0717	0.0302	0.0368
Chess	0.1413	0.1437	0.1119	0.1290	0.1244	0.1286	0.0762	0.0805	0.0953	0.0815	0.1342
Syncon	0.0516	0.0203	0.0314	0.0185	0.0187	0.0180	0.0195	0.0138	0.0369	0.0172	0.0296
Soybean	0.1015	0.0522	0.0491	0.0524	0.0514	0.0503	0.0741	0.0575	0.0825	0.0590	0.0640
Credit-a	0.0912	0.1171	0.1137	0.0921	0.0953	0.0900	0.1153	0.1110	0.1464	0.1276	0.0963
Crx	0.0922	0.1180	0.1197	0.0921	0.0980	0.0953	0.1188	0.1198	0.1493	0.1300	0.1041
Breast-cancer-w	0.0187	0.0384	0.0449	0.0338	0.0338	0.0327	0.0259	0.0278	0.0279	0.0257	0.0402
Pima-ind-diabetes	0.1957	0.1946	0.1944	0.1937	0.1935	0.1941	0.1575	0.1608	0.1667	0.1639	0.1916
Vehicle	0.3330	0.2382	0.2494	0.2415	0.2401	0.2398	0.3096	0.2147	0.3097	0.2062	0.2341
Anneal	0.0354	0.0201	0.0073	0.0214	0.0208	0.0194	0.0361	0.0294	0.0583	0.0628	0.0179
Tic-tac-toe	0.2614	0.1746	0.1367	0.2005	0.2005	0.2104	0.1084	0.1210	0.2290	0.1814	0.1559
Vowel	0.3301	0.1942	0.1745	0.1895	0.1805	0.1811	0.3166	0.1744	0.2773	0.2043	0.1755
Car	0.0937	0.0478	0.0387	0.0556	0.0556	0.0633	0.0637	0.0322	0.0988	0.0600	0.0389
Mfeat-mor	0.2624	0.2077	0.2142	0.2477	0.2475	0.2464	0.2421	0.2094	0.2415	0.2173	0.2227
Hypothyroid	0.0116	0.0104	0.0096	0.0094	0.0095	0.0099	0.0121	0.0114	0.0168	0.0122	0.0084
Kr-vs-kp	0.1107	0.0702	0.0417	0.0747	0.0654	0.0518	0.0283	0.0260	0.1065	0.0527	0.0407
Dis	0.0165	0.0193	0.0191	0.0170	0.0162	0.0179	0.0168	0.0167	0.0169	0.0190	0.0193
Hypo	0.0092	0.0124	0.0077	0.0071	0.0069	0.0078	0.0115	0.0107	0.0151	0.0110	0.0086
Sick	0.0246	0.0207	0.0198	0.0224	0.0227	0.0216	0.0218	0.0205	0.0233	0.0214	0.0223
Abalone	0.4180	0.3126	0.3033	0.3201	0.3199	0.3212	0.3607	0.2960	0.3595	0.3011	0.3054
Spambase	0.0929	0.0570	0.0497	0.0606	0.0600	0.0574	0.0417	0.0363	0.0848	0.0557	0.0564
Waveform-5000	0.1762	0.1232	0.1157	0.1235	0.1212	0.1184	0.1473	0.1110	0.1735	0.1227	0.1138
Phoneme	0.2216	0.2394	0.1572	0.2207	0.2137	0.2172	0.2009	0.1735	0.2299	0.2266	0.1706
Wall-following	0.0951	0.0491	0.0257	0.0251	0.0251	0.0253	0.0198	0.0306	0.1017	0.0532	0.0294
Page-blocks	0.0451	0.0308	0.0280	0.0251	0.0251	0.0243	0.0353	0.0283	0.0422	0.0247	0.0257
Optdigits	0.0685	0.0275	0.0250	0.0233	0.0229	0.0224	0.0373	0.0222	0.0665	0.0294	0.0216
Satellite	0.1746	0.0950	0.0808	0.0902	0.0902	0.0902	0.1254	0.0780	0.1598	0.0957	0.0813
Mushrooms	0.0237	0.0001	0.0001	0.0004	0.0004	0.0002	0.0000	0.0000	0.0517	0.0000	0.0000
Thyroid	0.0994	0.0587	0.0553	0.0611	0.0595	0.0561	0.0631	0.0586	0.0955	0.0650	0.0515
Pendigits	0.1095	0.0314	0.0207	0.0228	0.0228	0.0231	0.0427	0.0181	0.1115	0.0323	0.0168
Sign	0.3257	0.2420	0.2161	0.2531	0.2489	0.2461	0.3238	0.2443	0.3282	0.2492	0.1980
Nursery	0.0928	0.0521	0.0281	0.0651	0.0651	0.0616	0.0634	0.0114	0.0827	0.0569	0.0428
Magic	0.2111	0.1252	0.1241	0.1600	0.1534	0.1541	0.1260	0.1122	0.2090	0.1301	0.1263
Letter-recog	0.2207	0.1032	0.0806	0.0876	0.0868	0.0823	0.2262	0.0710	0.2219	0.1140	0.0526
Adult	0.1649	0.1312	0.1220	0.1437	0.1378	0.1387	0.1233	0.1137	0.1554	0.1257	0.1202
Shuttle	0.0040	0.0008	0.0007	0.0006	0.0006	0.0006	0.0006	0.0006	0.0050	0.0014	0.0005
Connect-4	0.2660	0.2253	0.2022	0.2264	0.2224	0.2237	0.2610	0.2158	0.2592	0.2152	0.1993
Waveform	0.0219	0.0152	0.0210	0.0156	0.0157	0.0158	0.0199	0.0112	0.0241	0.0154	0.0153
Localization	0.4523	0.3106	0.2134	0.3129	0.3129	0.3068	0.4444	0.3038	0.4562	0.3080	0.1979
Poker-hand	0.4979	0.2865	0.1326	0.4216	0.4216	0.1716	0.4988	0.2362	0.4988	0.1497	0.0670

Table A3

Experimental results of variance

Dataset	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$	BKDB
Lung-cancer	0.1970	0.2950	0.2810	0.2130	0.2130	0.2240	0.2212	0.2584	0.2542	0.2635	0.2520
Labor-negotiations	0.0653	0.1389	0.1289	0.0526	0.0526	0.0626	0.0995	0.1333	0.0852	0.0928	0.0821
Zoo	0.0439	0.0606	0.0658	0.0424	0.0424	0.0424	0.0640	0.1000	0.0649	0.0982	0.0518
Echocardiogram	0.1272	0.1265	0.1400	0.1319	0.1319	0.1335	0.1350	0.1382	0.0979	0.1047	0.1358
Lymphography	0.0343	0.1116	0.1408	0.0476	0.0476	0.0478	0.0899	0.1100	0.0542	0.0881	0.0720
Iris	0.0428	0.0662	0.0404	0.0374	0.0374	0.0364	0.0129	0.0189	0.0087	0.0164	0.0378
Teaching-ae	0.1484	0.1914	0.1494	0.1650	0.1650	0.1776	0.2028	0.2111	0.1767	0.1970	0.1624
Hepatitis	0.0424	0.0582	0.0612	0.0527	0.0527	0.0541	0.0940	0.0923	0.0303	0.0561	0.0463
Wine	0.0093	0.0493	0.0649	0.0231	0.0231	0.0246	0.0295	0.0455	0.0136	0.0232	0.0195
Autos	0.1349	0.1747	0.1821	0.1541	0.1541	0.1503	0.2147	0.2173	0.1924	0.2047	0.1538
Sonar	0.0907	0.1165	0.1199	0.0942	0.0942	0.1003	0.1349	0.1385	0.0924	0.1045	0.1032
Glass-id	0.0930	0.1075	0.1189	0.1004	0.1004	0.1051	0.1344	0.1402	0.1037	0.1091	0.1111
Audio	0.1000	0.0983	0.1373	0.1407	0.1407	0.1401	0.1387	0.1409	0.1322	0.1452	0.1415
Dermatology	0.0216	0.0513	0.0684	0.0199	0.0188	0.0242	0.0311	0.0658	0.0289	0.0531	0.0234
House-votes-84	0.0066	0.0170	0.0197	0.0094	0.0094	0.0083	0.0264	0.0404	0.0096	0.0160	0.0177
Chess	0.0401	0.0486	0.0531	0.0415	0.0422	0.0364	0.0632	0.0662	0.0471	0.0496	0.0402
Syncon	0.0204	0.0222	0.0301	0.0225	0.0218	0.0230	0.0267	0.0206	0.0189	0.0172	0.0235
Soybean	0.0302	0.0654	0.0439	0.0326	0.0349	0.0334	0.0740	0.0887	0.0397	0.0716	0.0303
Credit-a	0.0249	0.0555	0.0768	0.0305	0.0313	0.0321	0.0690	0.0823	0.0207	0.0393	0.0493
Crx	0.0200	0.0520	0.0663	0.0274	0.0268	0.0264	0.0714	0.0923	0.0163	0.0424	0.0437
Breast-cancer-w	0.0010	0.0337	0.0504	0.0134	0.0134	0.0128	0.0139	0.0336	0.0015	0.0246	0.0392
Pima-ind-diabetes	0.0715	0.0663	0.0689	0.0727	0.0698	0.0700	0.0942	0.0896	0.0679	0.0649	0.0705
Vehicle	0.1120	0.1299	0.1283	0.1277	0.1287	0.1276	0.1266	0.1541	0.1011	0.1136	0.1233
Anneal	0.0168	0.0161	0.0152	0.0197	0.0160	0.0161	0.0413	0.0394	0.0392	0.0402	0.0128
Tic-tac-toe	0.0455	0.0824	0.1125	0.0513	0.0513	0.0604	0.0900	0.1255	0.0657	0.0893	0.0848
Vowel	0.2542	0.2445	0.2325	0.2344	0.2304	0.2310	0.2687	0.2507	0.2360	0.2580	0.2245
Car	0.0520	0.0376	0.0434	0.0438	0.0438	0.0427	0.0488	0.0481	0.0724	0.0543	0.0425
Mfeat-mor	0.0622	0.1020	0.1031	0.0677	0.0679	0.0686	0.0725	0.0985	0.0664	0.0810	0.0893
Hypothyroid	0.0031	0.0034	0.0024	0.0034	0.0030	0.0033	0.0074	0.0069	0.0026	0.0024	0.0031
Kr-vs-kp	0.0186	0.0152	0.0111	0.0186	0.0166	0.0119	0.0305	0.0303	0.0292	0.0199	0.0165
Dis	0.0069	0.0005	0.0011	0.0071	0.0041	0.0021	0.0021	0.0026	0.0031	0.0006	0.0009
Hypo	0.0051	0.0071	0.0069	0.0049	0.0047	0.0056	0.0122	0.0107	0.0075	0.0051	0.0062
Sick	0.0047	0.0051	0.0043	0.0042	0.0039	0.0057	0.0150	0.0129	0.0036	0.0047	0.0048
Abalone	0.0682	0.1693	0.1769	0.1544	0.1543	0.1543	0.1111	0.1698	0.1091	0.1516	0.1706
Spambase	0.0092	0.0158	0.0214	0.0105	0.0105	0.0111	0.0343	0.0328	0.0096	0.0106	0.0150
Waveform-5000	0.0259	0.0690	0.0843	0.0410	0.0413	0.0420	0.0445	0.0914	0.0212	0.0452	0.0564
Phoneme	0.1215	0.1828	0.1064	0.1343	0.1360	0.1311	0.1589	0.1759	0.1230	0.1380	0.1119
Wall-following	0.0211	0.0288	0.0294	0.0242	0.0242	0.0242	0.0198	0.0347	0.0210	0.0264	0.0243
Page-blocks	0.0135	0.0143	0.0177	0.0124	0.0123	0.0130	0.0175	0.0166	0.0134	0.0116	0.0116
Optdigits	0.0153	0.0185	0.0254	0.0139	0.0138	0.0137	0.0349	0.0257	0.0174	0.0148	0.0107
Satellite	0.0139	0.0367	0.0455	0.0363	0.0363	0.0364	0.0362	0.0420	0.0128	0.0194	0.0307
Mushrooms	0.0043	0.0002	0.0002	0.0001	0.0001	0.0001	0.0003	0.0002	0.0041	0.0003	0.0001
Thyroid	0.0205	0.0257	0.0272	0.0235	0.0230	0.0239	0.0417	0.0428	0.0197	0.0233	0.0203
Pendigits	0.0157	0.0200	0.0236	0.0127	0.0127	0.0129	0.0357	0.0261	0.0147	0.0153	0.0113
Sign	0.0313	0.0386	0.0596	0.0378	0.0384	0.0403	0.0377	0.0459	0.0287	0.0343	0.0515
Nursery	0.0085	0.0168	0.0195	0.0105	0.0105	0.0111	0.0211	0.0195	0.0124	0.0140	0.0118
Magic	0.0174	0.0490	0.0491	0.0297	0.0291	0.0289	0.0483	0.0573	0.0155	0.0301	0.0439
Letter-recog	0.0471	0.0591	0.0709	0.0448	0.0448	0.0455	0.0614	0.0741	0.0570	0.0663	0.0370
Adult	0.0069	0.0165	0.0285	0.0116	0.0111	0.0113	0.0277	0.0370	0.0098	0.0174	0.0217
Shuttle	0.0009	0.0004	0.0003	0.0004	0.0004	0.0004	0.0009	0.0008	0.0012	0.0005	0.0003
Connect-4	0.0156	0.0149	0.0309	0.0222	0.0205	0.0215	0.0195	0.0195	0.0213	0.0204	0.0310
Waveform	0.0009	0.0053	0.0037	0.0025	0.0025	0.0023	0.0032	0.0106	0.0009	0.0039	0.0029
Localization	0.0460	0.0594	0.1099	0.0580	0.0580	0.0632	0.0546	0.0662	0.0393	0.0521	0.0948
Poker-hand	0.0000	0.0424	0.0633	0.0273	0.0273	0.0602	0.0000	0.0911	0.0000	0.0802	0.0039

Table A4

Experimental results of RMSE for all classes

Dataset	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$	BKDB
Lung-cancer	0.5240	0.6178	0.5866	0.5627	0.5627	0.5658	0.6087	0.5544	0.4521	0.4639	0.4538
Labor-negotiations	0.2268	0.2778	0.2477	0.1995	0.1995	0.2057	0.2759	0.3025	0.2528	0.2734	0.2255
Zoo	0.0802	0.0647	0.0859	0.0677	0.0677	0.0724	0.0855	0.0778	0.1004	0.0855	0.0646
Echocardiogram	0.4896	0.4886	0.4889	0.4903	0.4904	0.4872	0.4854	0.4854	0.4330	0.4355	0.4839
Lymphography	0.2446	0.2684	0.3031	0.2478	0.2475	0.2496	0.2674	0.2684	0.2469	0.2303	0.2360
Iris	0.2078	0.1958	0.1968	0.2069	0.2069	0.2091	0.2124	0.2008	0.1702	0.1643	0.1964
Teaching-ae	0.4789	0.4825	0.4804	0.4670	0.4679	0.4668	0.4654	0.4875	0.4684	0.4711	0.4630
Hepatitis	0.3901	0.3610	0.3875	0.3754	0.3742	0.3695	0.3716	0.3991	0.3412	0.3197	0.3530
Wine	0.0926	0.1414	0.1211	0.0976	0.0976	0.0983	0.1194	0.1649	0.0854	0.1094	0.1183
Autos	0.2714	0.2361	0.2323	0.2324	0.2320	0.2290	0.2336	0.2144	0.2487	0.2045	0.2080
Sonar	0.4421	0.4131	0.4084	0.4285	0.4134	0.4091	0.3829	0.4263	0.4059	0.3780	0.3951
Glass-id	0.3540	0.3332	0.3395	0.3439	0.3440	0.3422	0.3312	0.3364	0.3094	0.2932	0.3236
Audio	0.1254	0.1453	0.1528	0.1194	0.1179	0.1189	0.1259	0.1364	0.1254	0.1390	0.1208
Dermatology	0.0631	0.0851	0.1206	0.0692	0.0677	0.0688	0.0945	0.1106	0.0710	0.0740	0.0857
House-votes-84	0.2997	0.2181	0.1969	0.1994	0.1994	0.1927	0.2037	0.2352	0.2928	0.1980	0.1943
Chess	0.2944	0.2594	0.2615	0.2725	0.2669	0.2603	0.3125	0.2682	0.2982	0.2543	0.2486
Syncon	0.0931	0.0500	0.0611	0.0554	0.0538	0.0537	0.0847	0.0797	0.0881	0.0524	0.0743
Soybean	0.0933	0.0642	0.0654	0.0656	0.0658	0.0646	0.0754	0.0797	0.0804	0.0616	0.0634
Credit-a	0.3350	0.3415	0.3480	0.3271	0.3231	0.3236	0.3329	0.3674	0.3315	0.3192	0.3319
Crx	0.3342	0.3411	0.3525	0.3253	0.3184	0.3219	0.3311	0.3748	0.3311	0.3243	0.3303
Breast-cancer-w	0.1570	0.1928	0.2497	0.1848	0.1848	0.1855	0.1922	0.2603	0.1586	0.1772	0.2170
Pima-ind-diabetes	0.4147	0.4059	0.4074	0.4078	0.4067	0.4059	0.4300	0.4303	0.4016	0.3956	0.4065
Vehicle	0.3934	0.3104	0.3122	0.3097	0.3086	0.3099	0.3803	0.3047	0.3763	0.2897	0.2994
Anneal	0.0981	0.0543	0.0539	0.0546	0.0519	0.0536	0.1206	0.1205	0.1226	0.1093	0.0576
Tic-tac-toe	0.4309	0.4023	0.3772	0.3995	0.3995	0.4085	0.3353	0.2989	0.4322	0.3986	0.3686
Vowel	0.2270	0.1271	0.1582	0.1425	0.1420	0.1633	0.1708	0.0941	0.2014	0.1234	0.1339
Car	0.2252	0.1617	0.1379	0.2005	0.2005	0.1983	0.1849	0.1064	0.2267	0.1657	0.1579
Mfeat-mor	0.2086	0.1940	0.1974	0.1985	0.1983	0.1983	0.2595	0.2294	0.2059	0.1885	0.1962
Hypothyroid	0.1138	0.0955	0.0937	0.1036	0.0986	0.0967	0.1164	0.1039	0.1116	0.0969	0.0936
Kr-vs-kp	0.3022	0.2358	0.1869	0.2638	0.2565	0.2343	0.2013	0.1953	0.3034	0.2319	0.2174
Dis	0.1177	0.1103	0.1024	0.1080	0.0996	0.1046	0.1187	0.1174	0.1107	0.1043	0.1032
Hypo	0.0766	0.0738	0.0671	0.0650	0.0643	0.0647	0.0821	0.0847	0.0762	0.0607	0.0715
Sick	0.1700	0.1434	0.1382	0.1572	0.1500	0.1452	0.1616	0.1486	0.1605	0.1389	0.1431
Abalone	0.4630	0.4250	0.4277	0.4193	0.4193	0.4193	0.4670	0.4501	0.4610	0.4189	0.4258
Spambase	0.2994	0.2403	0.2300	0.2336	0.2335	0.2301	0.2360	0.2249	0.2931	0.2285	0.2185
Waveform-5000	0.3348	0.2947	0.3149	0.2659	0.2637	0.2635	0.3135	0.3259	0.3282	0.2735	0.2763
Phoneme	0.0880	0.0902	0.0784	0.0885	0.0880	0.0871	0.1043	0.0987	0.0882	0.0828	0.0758
Wall-following	0.2177	0.1586	0.1363	0.1292	0.1292	0.1293	0.1107	0.1552	0.2197	0.1589	0.1263
Page-blocks	0.1450	0.1187	0.1128	0.1021	0.1022	0.1025	0.1228	0.1121	0.1384	0.1054	0.0964
Optdigits	0.1163	0.0837	0.0792	0.0733	0.0726	0.0729	0.1011	0.0816	0.1133	0.0748	0.0657
Satellite	0.2400	0.1851	0.1777	0.1800	0.1800	0.1800	0.2078	0.1873	0.2346	0.1710	0.1565
Mushrooms	0.1229	0.0083	0.0001	0.0109	0.0146	0.0062	0.0000	0.0040	0.1646	0.0053	0.0061
Thyroid	0.0967	0.0746	0.0744	0.0745	0.0731	0.0715	0.1183	0.0890	0.0953	0.0772	0.0661
Pendigits	0.1427	0.0725	0.0687	0.0568	0.0568	0.0569	0.1116	0.0838	0.1402	0.0722	0.0563
Sign	0.3984	0.3505	0.3334	0.3524	0.3520	0.3519	0.4155	0.3714	0.3965	0.3452	0.3192
Nursery	0.1766	0.1385	0.1121	0.1571	0.1571	0.1577	0.1559	0.0887	0.1767	0.1388	0.1314
Magic	0.3974	0.3461	0.3470	0.3541	0.3542	0.3526	0.3589	0.3424	0.3957	0.3344	0.3357
Letter-recog	0.1184	0.0860	0.0768	0.0707	0.0704	0.0695	0.1701	0.0847	0.1179	0.0851	0.0586
Adult	0.3409	0.3076	0.3089	0.3245	0.3146	0.3197	0.3231	0.3281	0.3392	0.3069	0.3031
Shuttle	0.0298	0.0182	0.0146	0.0126	0.0128	0.0131	0.0142	0.0127	0.0330	0.0159	0.0118
Connect-4	0.3587	0.3315	0.3247	0.3370	0.3342	0.3356	0.3685	0.3566	0.3586	0.3314	0.3195
Waveform	0.1176	0.0951	0.1145	0.0860	0.0860	0.0860	0.1016	0.1108	0.1170	0.0919	0.0876
Localization	0.2390	0.2095	0.1960	0.2095	0.2095	0.2087	0.2826	0.2699	0.2384	0.2057	0.1829
Poker-hand	0.2382	0.2124	0.1760	0.2217	0.2217	0.2093	0.2382	0.2770	0.2382	0.1999	0.1536

Table A5

Experimental results of MCC

Dataset	NB	TAN	K ${}_{2}$ DB	AODE	AODE-SR	WAODE-MI	Boosting ${}_{\mathrm{NB}}$	Boosting ${}_{\mathrm{TAN}}$	Bagging ${}_{\mathrm{NB}}$	Bagging ${}_{\mathrm{TAN}}$	BKDB
Lung-cancer	0.3290	0.1012	0.1371	0.2333	0.2333	0.2333	0.0330	0.0900	0.3920	0.2840	0.2925
Labor-negotiations	0.8459	0.7659	0.8518	0.8864	0.8864	0.8864	0.7440	0.7280	0.8060	0.8060	0.8058
Zoo	0.9611	0.9871	0.9348	0.9611	0.9611	0.9610	0.9570	0.9890	0.9330	0.9530	0.9740
Echocardiogram	0.1569	0.1460	0.0868	0.1820	0.1820	0.1820	0.0690	0.0690	0.3130	0.2540	0.1654
Lymphography	0.7202	0.6633	0.5493	0.6782	0.6800	0.7041	0.6950	N/A	0.7250	N/A	0.7434
Iris	0.8701	0.8800	0.8701	0.8701	0.8701	0.8701	0.9000	0.9100	0.9200	0.9200	0.8800
Teaching-ae	0.2552	0.1774	0.1990	0.2651	0.2853	0.3265	0.2890	0.2260	0.1650	0.1460	0.3580
Hepatitis	0.4780	0.4763	0.3961	0.4487	0.4224	0.4360	0.3830	0.4540	0.5910	0.5640	0.5167
Wine	0.9745	0.9488	0.9659	0.9661	0.9661	0.9745	0.9650	0.9320	0.9830	0.9740	0.9659
Autos	0.5995	0.7213	0.7340	0.7358	0.7358	0.7479	0.7030	0.7650	0.6480	N/A	0.7784
Sonar	0.5355	0.5557	0.5064	0.5452	0.5549	0.5452	0.6620	0.5660	0.5260	0.5260	0.5554
Glass-id	0.5986	0.6631	0.6633	0.6132	0.6062	0.6062	0.6750	0.6960	0.7110	0.7220	0.6995
Audio	0.7205	0.6561	0.6188	0.7623	0.7575	0.7781	N/A	N/A	N/A	N/A	0.7026
Dermatology	0.9763	0.9590	0.9182	0.9797	0.9797	0.9764	0.9680	0.9550	0.9710	0.9770	0.9798
House-votes-84	0.8065	0.8839	0.8936	0.8889	0.8889	0.8936	0.8830	0.8740	0.8010	0.8840	0.8944
Chess	0.6922	0.7482	0.7321	0.7275	0.7217	0.7438	0.6470	0.7840	0.6480	0.7590	0.7951
Syncon	0.9661	0.9900	0.9841	0.9881	0.9881	0.9881	0.9740	0.9760	0.9630	0.9860	0.9801
Soybean	0.9045	0.9487	0.9391	0.9496	0.9480	0.9479	0.9300	0.9170	0.9240	0.9480	0.9432
Credit-a	0.7149	0.6942	0.7031	0.7177	0.7359	0.7236	0.7240	0.6530	0.7150	0.7290	0.6970
Crx	0.7215	0.7002	0.6833	0.7265	0.7210	0.7206	0.7080	0.6500	0.7240	0.7030	0.7147
Breast-cancer-w	0.9447	0.9078	0.8340	0.9226	0.9226	0.9226	0.9050	0.8430	0.9440	0.9140	0.8630
Pima-ind-diabetes	0.4576	0.4652	0.4550	0.4667	0.4693	0.4660	0.4260	0.4300	0.4660	0.4630	0.4564
Vehicle	0.4860	0.6094	0.6078	0.6161	0.6181	0.6178	0.4820	0.6370	0.4890	0.6190	0.6370
Anneal	0.9109	0.9722	0.9776	0.9777	0.9804	0.9777	0.8500	0.8600	0.8340	0.8670	0.9804
Tic-tac-toe	0.2849	0.4740	0.5367	0.3848	0.3848	0.3643	0.6260	0.7260	0.3020	0.4770	0.5304
Vowel	0.5336	0.8568	0.8001	0.8357	0.8346	0.7857	0.7750	0.9370	0.6550	0.9270	0.8512
Car	0.6818	0.8787	0.9182	0.8205	0.8205	0.8108	0.8150	0.9390	0.7170	0.8920	0.9149
Mfeat-mor	0.6533	0.6705	0.6605	0.6517	0.6529	0.6535	0.6390	0.6740	0.6440	0.6840	0.6663
Hypothyroid	0.8539	0.8849	0.8810	0.8618	0.8714	0.8864	0.8420	0.8670	0.8460	0.8870	0.8887
Kr-vs-kp	0.7567	0.8453	0.9167	0.8320	0.8559	0.8859	0.8970	0.8930	0.7520	0.8590	0.9148
Dis	0.4922	0.1842	0.4063	0.5600	0.5549	0.5109	0.3300	0.3560	0.5230	0.3670	0.4583
Hypo	0.9054	0.9007	0.9204	0.9337	0.9332	0.9298	N/A	N/A	0.9050	N/A	0.9099
Sick	0.7541	0.7750	0.8025	0.7783	0.7879	0.7914	0.7510	0.7810	0.7610	0.7970	0.7805
Abalone	0.3039	0.3112	0.3131	0.3283	0.3280	0.3278	0.2630	0.3000	0.2730	0.3160	0.3126
Spambase	0.7862	0.8593	0.8667	0.8589	0.8570	0.8641	0.8550	0.8790	0.7870	0.8640	0.8678
Waveform-5000	0.7189	0.7234	0.7001	0.7822	0.7873	0.7828	0.7260	0.7260	0.7250	0.7540	0.7588
Phoneme	0.7207	0.7084	0.7880	0.7437	0.7466	0.7528	0.7370	N/A	N/A	N/A	0.7995
Wall-following	0.8454	0.9170	0.9395	0.9443	0.9443	0.9449	0.9590	0.9210	0.8330	0.9000	0.9420
Page-blocks	0.7351	0.8062	0.8070	0.8316	0.8316	0.8273	0.7990	0.8290	0.7430	0.8380	0.8486
Optdigits	0.9149	0.9547	0.9587	0.9654	0.9664	0.9664	0.9350	0.9610	0.9170	0.9600	0.9710
Satellite	0.7807	0.8504	0.8665	0.8593	0.8593	0.8593	0.8100	0.8610	0.7960	0.8610	0.8790
Mushrooms	0.9612	0.9998	1.0000	0.9998	0.9995	1.0000	1.0000	1.0000	0.9260	1.0000	1.0000
Thyroid	0.7724	0.8378	0.8368	0.8465	0.8474	0.8547	N/A	N/A	N/A	N/A	0.8696
Pendigits	0.8699	0.9643	0.9674	0.9778	0.9778	0.9779	0.9150	0.9560	0.8700	0.9620	0.9831
Sign	0.4667	0.5879	0.6196	0.5780	0.5786	0.5855	0.4640	0.5850	0.4670	0.5980	0.6650
Nursery	0.8570	0.9038	0.9577	0.8926	0.8926	0.8960	N/A	N/A	N/A	N/A	0.9220
Magic	0.4894	0.6234	0.6330	0.6085	0.6087	0.6052	0.6090	0.6530	0.4940	0.6510	0.6610
Letter-recog	0.7378	0.8648	0.8975	0.9082	0.9086	0.9114	0.7390	0.8880	0.7390	0.8630	0.9477
Adult	0.6069	0.6132	0.6075	0.6192	0.6309	0.6214	0.6130	0.5900	0.6070	0.6090	0.6245
Shuttle	0.9891	0.9957	0.9975	0.9979	0.9978	0.9976	0.9980	0.9990	0.9860	0.9980	0.9984
Connect-4	0.3631	0.4766	0.4994	0.4575	0.4661	0.4616	0.3680	0.4750	0.3700	0.4750	0.5182
Waveform	0.9674	0.9698	0.9620	0.9730	0.9729	0.9728	0.9700	0.9700	0.9680	0.9710	0.9727
Localization	0.3660	0.5474	0.6274	0.5430	0.5430	0.5469	N/A	0.5460	N/A	0.5550	0.6659
Poker-hand	0.0000	0.4242	0.6487	0.0813	0.0813	0.6801	N/A	N/A	N/A	N/A	0.8773

References

Kesavaraj

and Sukumaran

, A study on classification techniques in data mining, in: the Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT), IEEE, 2013, pp. 1–7.

Arias

Gámez

J.A.

and Puerta

J.M.

, Scalable learning of k-dependence bayesian classifiers under mapreduce, in: the IEEE International Conference on Trust, Security and Privacy in Computing and Communications, Vol. 2, IEEE, 2015, pp. 25–32.

Quinlan

J.R.

, Bagging, boosting, and C4.5, in: Association for the Advancement of Artificial Intelligence, AAAI Press, 1996, pp. 725–730.

Syarif

Zaluska

Prugel-Bennett

and Wills

, Application of bagging, boosting and stacking to intrusion detection, in: the International Workshop on Machine Learning and Data Mining in Pattern Recognition, Springer, 2012, pp. 593–602.

Yap

B.W.

Rani

K.A.

Rahman

H.A.A.

Fong

Khairudin

and Abdullah

N.N.

, An application of oversampling, undersampling, bagging and boosting in handling imbalanced datasets, in: the 1st International Conference on Advanced Data and Information Engineering, Springer, 2014, pp. 13–22.

Wang

Xiao

Zhou

and Zhou

, hMuLab: a biomedical hybrid MUlti-LABel classifier based on multiple linear regression, IEEE/ACM Transactions on Computational Biology and Bioinformatics 14(5) (2016), 1173–1180.

Breiman

, Bagging predictors, Machine Learning 24(2) (1996), 123–140.

Qian

Liang

Feng

and Shi

, A resampling ensemble algorithm for classification of imbalance problems, Neurocomputing 143 (2014), 57–67.

Clyde

and Lee

, Bagging and the Bayesian Bootstrap, in: the International Conference on Artificial Intelligence and Statistics, Morgan Kaufman Publishers, 2001, pp. 76–82.

10.

Freund

Schapire

R.E.

et al., Experiments with a new boosting algorithm, in: The International Conference on Machine Learning, Vol. 96, Morgan Kaufmann Publishers, 1996, pp. 148–156.

11.

Cheng

Greiner

Kelly

Bell

and Liu

, Learning Bayesian networks from data: an information-theory based approach, Artificial Intelligence 137(1–2) (2002), 43–90.

12.

Delage

Lee

and Ng

A.Y.

, A dynamic bayesian network model for autonomous 3d reconstruction from a single indoor image, in: the International Conference on Computer Vision and Pattern Recognition, Vol. 2, IEEE, 2006, pp. 2418–2428.

13.

de Campos

L.M.

Fernández-Luna

J.M.

and Huete

J.F.

, Bayesian networks and information retrieval: an introduction to the special issue, Information Processing & Management 40(5) (2004), 727–733.

14.

Duan

Wang

and Sun

, Efficient heuristics for learning Bayesian network from labeled and unlabeled data, Intelligent Data Analysis 24(2) (2020), 385–408.

15.

Webb

G.I.

Boughton

J.R.

and Wang

, Not so naive Bayes: aggregating one-dependence estimators, Machine Learning 58(1) (2005), 5–24.

16.

Chen

Martinez

A.M.

and Webb

G.I.

, Highly scalable attribute selection for averaged one-dependence estimators, in: the Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, 2014, pp. 86–97.

17.

Jiang

Zhang

Cai

and Wang

, Weighted average of one-dependence estimators, Journal of Experimental & Theoretical Artificial Intelligence 24(2) (2012), 219–230.

18.

Jiang

Wang

and Zhang

, Attribute value weighted average of one-dependence estimators, Entropy 19(9) (2017), 501.

19.

Yang

Webb

Cerquides

Korb

Boughton

and Ting

K.M.

, To select or to weigh: A comparative study of model selection and model weighing for spode ensembles, in: the European Conference on Machine Learning, Springer, 2006, pp. 533–544.

20.

Cooper

G.F.

and Herskovits

, A Bayesian method for constructing Bayesian belief networks from databases, in: the 7th Conference on Uncertainty in Artificial Intelligence, Elsevier, 1991, pp. 86–94.

21.

Zhou

Z.-H.

, When semi-supervised learning meets ensemble learning, in: the International Workshop on Multiple Classifier Systems, Springer, 2009, pp. 529–538.

22.

Zaidi

N.A.

Cerquides

Carman

M.J.

and Webb

G.I.

, Alleviating naive Bayes attribute independence assumption by attribute weighting, Machine Learning Research 14(1) (2013), 1947–1988.

23.

Zhang

Jiang

and Yu

, Class-specific attribute value weighting for Naive Bayes, Information Sciences 508 (2020), 260–274.

24.

Liangxiao

Zhang

and Cai

, A Novel Bayes Model: Hidden Naive Bayes, IEEE Transactions on Knowledge and Data Engineering, 2009, 1361–1371.

25.

Liu

Huang

Chen

and Jia

, A search problem in complex diagnostic Bayesian networks, Knowledge-Based Systems 30 (2012), 95–103.

26.

Liu

and Zhao

, Research and citation analysis of data mining technology based on Bayes algorithm, Mobile Networks and Applications 22(3) (2017), 418–426.

27.

Sahami

, Learning Limited Dependence Bayesian Classifiers, in: The 2nd International Conference on Knowledge Discovery and Data Mining, Vol. 96, AAAI Press, 1996, pp. 335–338.

28.

Bauer

and Kohavi

, An empirical comparison of voting classification algorithms: Bagging, boosting, and variants, Machine Learning 36(1–2) (1999), 105–139.

29.

Opitz

and Maclin

, Popular ensemble methods: An empirical study, Journal of Artificial Intelligence Research 11 (1999), 169–198.

30.

Brodley

and Lane

, Creating and exploiting coverage and diversity, in: AAAI-96 Workshop on Integrating Multiple Learned Models, Portland, OR, 1996, pp. 8–14.

31.

Dietterich

T.G.

et al., Ensemble learning, The Handbook of Brain Theory and Neural Networks 2 (2002), 110–125.

32.

Jiang

Cai

Wang

and Zhang

, Improving Tree augmented Naive Bayes for class probability estimation, Knowledge-Based Systems 26 (2012), 239–245.

33.

Webb

G.I.

Boughton

J.R.

Zheng

Ting

K.M.

and Salem

, Learning by extrapolation from marginal to full-multivariate probability distributions: decreasingly naive Bayesian classification, Machine Learning 86(2) (2012), 233–272.

34.

Hellman

McGovern

and Xue

, Learning ensembles of Continuous Bayesian Networks: An application to rainfall prediction, in: the Internatioanl Conference on Intelligent Data Understanding, IEEE, 2012, pp. 112–117.

35.

Kunwar

Pal

and Blumenstein

, Semi-supervised online Bayesian network learner for handwritten characters recognition, in: the 22nd International Conference on Pattern Recognition, IEEE, 2014, pp. 3104–3109.

36.

Oza

N.C.

, Online bagging and boosting, in: the International Conference on Systems, Man and Cybernetics, Vol. 3, IEEE, 2005, pp. 2340–2345.

37.

Bifet

Holmes

Pfahringer

and Gavalda

, Improving adaptive bagging methods for evolving data streams, in: the Asian Conference on Machine Learning, Springer, 2009, pp. 23–37.

38.

Bifet

Holmes

and Pfahringer

, Leveraging bagging for evolving data streams, in: the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2010, pp. 135–150.

39.

Krishnapuram

Rosales

and Rao

R.B.

, Bayesian co-training, Journal of Machine Learning Research 12(Sep) (2011), 2649–2680.

40.

Freund

and Schapire

R.E.

, A desicion-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55(1) (1997), 119–139.

41.

Foo

S.W.

Lian

and Dong

, Recognition of visual speech elements using adaptively boosted hidden Markov models, IEEE Transactions on Circuits and Systems for Video Technology 14(5) (2004), 693–705.

42.

Galar

Fernandez

Barrenechea

Bustince

and Herrera

, A review on ensembles for the class imbalance problem: bagging-, boosting-, and hybrid-based approaches, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 42(4) (2011), 463–484.

43.

Wang

Duan

Lou

and Sun

, Optimizing the topology of bayesian network classifiers by applying conditional entropy to mine causal relationships between attributes, IEEE Access 7 (2019), 134271–134279.

44.

Zheng

Webb

G.I.

Suraweera

and Zhu

, Subsumption resolution: an efficient and effective technique for semi-naive Bayesian learning, Machine Learning 87(1) (2012), 93–125.

45.

Kuncheva

L.I.

and Whitaker

C.J.

, Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy, Machine Learning 51(2) (2003), 181–207.

46.

Dua

and Graff

, UCI Machine Learning Repository, 2017. http://archive.ics.uci.edu/ml.

47.

Fayyad

and Irani

, Multi-interval discretization of continuous-valued attributes for classification learning, in: the 13th International Joint Conference on Artificial Intelligence, 1993, pp. 35–40.

48.

Matthews

B.W.

, Comparison of the predicted and observed secondary structure of T4 phage lysozyme, Biochimica et Biophysica Acta (BBA)-Protein Structure 405(2) (1975), 442–451.

49.

Yang

Fong

Wong

and Sun

, Optimizing Classification Decision Trees by Using Weighted Naive Bayes Predictors to Reduce the Imbalanced Class Problem in Wireless Sensor Network, International Journal of Distributed Sensor Networks, 2012, 15.

Bagging k -dependence Bayesian network classifiers

Abstract

Keywords

1. Introduction

3.1 Difference in probability distribution across various data subspaces

Table 1 Datasets

Table 2 Win-Draw-Loss results of zero-one loss

Table 5 Win-Draw-Loss results of bias and variance

5. Conclusions and future work

Footnotes

Acknowledgments

Appendix A

References

Table 1
Datasets

Table 2
Win-Draw-Loss results of zero-one loss

Table 5
Win-Draw-Loss results of bias and variance