Alleviating the independence assumptions of averaged one-dependence estimators by model weighting

Abstract

Of numerous proposals to refine naive Bayes by weakening its attribute independence assumption, averaged one-dependence estimators (AODE) has been shown to be able to achieve significantly higher classification accuracy at a moderate cost in classification efficiency. However, all one-dependence estimators (ODEs) in AODE have the same weights and are treated equally. To address this issue, model weighting, which assigns discriminate weights to ODEs and then linearly combine their probability estimates, has been proved to be an efficient and effective approach. Most information-theoretic weighting metrics, including mutual information, Kullback-Leibler measure and the information gain, place more emphasis on the correlation between root attribute (value) and class variable. We argue that the topology of each ODE can be divided into a set of local directed acyclic graphs (DAGs) based on the independence assumption, and multivariate mutual information is introduced to measure the extent to which the DAGs fit data. Based on this premise, in this study we propose a novel weighted AODE algorithm, called AWODE, that adaptively selects weights to alleviate the independence assumption and make the learned probability distribution fit the instance. The proposed approach is validated on 40 benchmark datasets from UCI machine learning repository. The experimental results reveal that, AWODE achieves bias-variance trade-off and is a competitive alternative to single-model Bayesian learners (such as TAN and KDB) and other weighted AODEs (such as WAODE).

Keywords

Independence assumption averaged one-dependence estimators model weighting

1. Introduction

Bayesian network classifiers (BNCs) [1, 2, 3, 4, 5, 6] provide a powerful tool for knowledge representation and inference under uncertainty. However, learning the topology of BNC is an NP-hard problem [7], thus heuristic learning and approximate learning are the realistic solutions. To estimate high-dimensional multi-variate probabilities from the training data, Naive Bayes (NB) [8] infers the joint probability by assuming that the attributes $X=\{X_{1},\ldots,X_{n}\}$ are conditionally independent given the class variable $Y$ [9]. This unrealistic assumption helps NB avoid learning the dependency relationships between attributes and makes it be an extremely efficient classification approach. Among numerous proposals to alleviate the independence assumption of NB, Averaged One-dependence Estimators (AODE) [10] has come out as the most attractive option due to its capability for improving NB’s prediction accuracy without undue computational overheads.

AODE utilizes a restricted class of super-parent one-dependence estimators (SPODEs) and aggregates the predictions of all qualified estimators within this class. Each SPODE assumes that all the other attributes are conditionally independent given $Y$ and one super-parent attribute, $X_{\alpha}$ [11, 12]. This weaker independence assumption is necessarily true if NB’s is true and may also be true when NB’s is not [13]. AODE’s search-free approach learns by extrapolation from marginal to full-multivariate probability distributions, that further reduces NB’s bias at the cost of increase in variance. Extensive study comparing different semi-naive Bayes [14, 15, 16] shows that AODE exhibits significant advantage over other semi-naive techniques, including tree augmented Naive Bayes (TAN) [17], $k$ -dependence Bayesian classifier (KDB) [18] and hidden Naive Bayes (HNB) [19], in terms of error reduction.

The SPODEs in AODE have discriminative independence assumptions and their network topologies differ greatly, thus diversity is introduced in terms of data distribution. Linear model weighting has been proved effective by calculating the weight associated with each member to linearly combine their estimates of joint probability. AODE combines the SPODEs by applying uniformly weighted average, and the prediction is made by applying Bayes rule to select the maximum posterior probability. Information-theoretic metrics, e.g., mutual information (MI), conditional log likelihood (CLL) and area under the ROC curve (AUC) have been applied to assign weights to SPODEs [20, 21]. These metrics aim to find a balance between the goodness of fit and model simplicity, and thus they provide a combined score for a proposed explanatory model (a SPODE in our context) and for the data given the model.

However, the independence assumption of SPODE may not be suitable for different instances to the same extent, and that may result in biased estimate of joint probability distribution and harm AODE’s generalization performance. Thus SPODE’s weight should be adaptively changed from instance to instance. For example, the primary value of weighting by mutual information is its capacity to reflect the impact of the root attribute on the class variable, whereas the impact will not remain the same when they take different values and that will reduce the generalization performance of the final weighted AODE. Previous approaches used some form of variants of information-theoretic metrics, e.g., the Kullback-Leibler (KL) divergence and information gain (IG), to measure the correlation between the root attribute value and class variable for weighting [22].

Due to the individual independence assumption of these SPODEs in AODE, the joint probability distributions corresponding to their topologies may fit the data to different extents. One key issue for weighting is how to evaluate the reasonableness of the topologies of SPODEs. The contributions of this paper are listed as follows:

•
The topology of SPODE member in AODE is divided into a set of local topologies based on the independence assumption. Then multi-variate mutual information is redefined and introduced as an information metric to measure the reasonableness of the local topology in terms of weighting. The proposed weighted AODE algorithm, called adaptively weighted one-dependence estimators (AWODE), adaptively selects weights for SPODEs to alleviate the independence assumption, and the weights can help finely tune the ensemble of SPODEs to make the learned joint probability distribution fit each instance.
•
Through extensive experiments on 40 datasets from the UCI (University of California, Irvine) machine learning repository [23], weighting can help improve both the interoperability of these SPODE members and the generalization performance of the final ensemble BNC. We prove that AWODE achieves bias-variance trade-off and is a competitive alternative to single-model Bayesian learners (such as TAN and KDB) and other weighted AODE algorithms (such as WAODE).

The rest of this paper is organized as follows. In Section 2, we introduce related work for alleviating the independence assumptions of NB and AODE. In Section 3, we introduce the basic idea of information metric for weighting AODE. Section 4 presents experimental evaluation of our proposed methods and their comparison with related approaches. Section 5 presents conclusions and directions for future research.
2. Background theory and related research work

Formally, the topology of BNC learned from training data is a directed acyclic graph $\mathcal{B}$ in which vertices correspond to the $n$ predictive attributes $\{X_{1},\ldots,X_{n}\}$ and class variable $Y$ , and edges represent direct dependencies between the attributes. An unlabeled instance $\textbf{x}=(x_{1},x_{2},\ldots,x_{n})$ is a vector of $n$ attribute values $x_{i}$ , each observed for an attribute variable $X_{i}(1\leqslant i\leqslant n)$ . Classification is done by applying Bayes rule to assign appropriate class label $y$ to x with the highest posterior probability.

$\displaystyle y^{*}=\arg\max P(y|\textbf{x})=\arg\max P(y)P_{\mathcal{B}}(% \textbf{x}|y).$ (1)

Figure 1.

Example of (a) Naive bayes, (b) An SPODE in AODE.

As Fig. 1a shows, by assuming the attributes are independent of each other given the class variable, NB uses the following formula to estimate $P(\textbf{x}|y)$ :

$\displaystyle P_{\text{NB}}(\textbf{x}|y)=\prod^{n}_{i=1}P(x_{i}|y).$ (2)

If only relevant, especially non-redundant, attributes are selected and used for prediction, the robustness and classification performance of NB will improve. Univariate filter approach helps mitigate the negative effects of the curse-of-dimensionality which results in exponential increase in the required training data as the number of attributes are increased [24]. Researchers proposed to search through the entire space of all attribute subsets to exclude attributes that introduce dependencies. Langley and Sage proposed Forward Sequential Selection (FSS) [25] to iteratively add each candidate attribute to the subset that starts from an empty set. The performance of the resulting NB on the training data will be evaluated by a scoring measure [26], which can be mutual information, odds ratio, weight of evidence and symmetrical uncertainty coefficient. Kittler proposed Backwards Sequential Elimination (BSE) [25] in the reverse search direction of FSS. Multi-variate filter approach promotes the inclusion of variables that are relevant for classification and at the same time, avoids including redundant variables. Hall proposed Correlation-based Feature Selection (CFS) to determine the relevance of the attribute subset [27]. It uses a best-first search (BFS) to traverse through feature subset space. Any kind of heuristic (FSS, BSE, BFS, etc.) can be used to search for this optimal subset.

Attribute weighting is strictly more powerful than attribute selection, as it reduces to attribute selection by assigning the weights of redundant attributes to zero, whereas attribute selection cannot perform the same as attribute weighting if the weights are between zero and one. Hilden and Bjerregaard [28] proposed to alleviate the negative effects caused by violations of NB’s independence assumption by assigning the attributes with the same weight. Zhang and Sheng [29] proposed to measure the attribute weights with the gain ratio, which is generally used for splitting nodes in decision trees [30]. Wu and Cai [31] proposed to employ a greedy search strategy for attribute weighting based on differential evolution algorithms. Then the independence assumption for NB turns to be

$\displaystyle P(\textbf{x}|y)=\prod^{n}_{i=1}P(x_{i}|y)^{w_{i}}.$ (3)

For BNC learning, using a single model to make predictions ignores the uncertainty as to which is the correct model. Thus, all possible models in the model space under consideration should be used when making predictions, with each model weighted by its probability of being the correct model. SPODEs stand between NB ignoring the attribute dependencies on one hand and full BNCs taking maximum flexibility for modelling dependencies on the other, and have demonstrated remarkable performance by exploiting one-order attribute dependencies and keeping the effectiveness of probability estimation. As illustrated in Fig. 1b, SPODEs in AODE relax NB’s attribute independence assumption by allowing all attributes to depend on a common attribute, the superparent, in addition to the class variable. For SPODE ${}^{\alpha}$ that takes $X_{\alpha}$ as the superparent, its independence assumption can be described as follows

$\displaystyle P_{\text{SPODE}^{\alpha}}(\textbf{x}|x_{\alpha},y)=\prod^{n}_{i=% 1}P(x_{i}|x_{\alpha},y).$ (4)

AODE aggregates the predictions of all qualified SPODEs. For a training dataset with $n$ attributes, there can be $n$ candidate SPODEs, each taking a different attribute as its superparent. Thus AODE avoids model selection and maintains the robustness of NB. Ensemble learning helps mitigative the negative effect caused by the possible biased independence assumption in one SPODE. And AODE relatively relaxes the independence assumption without learning the structure of a BN. The prediction of AODE is produced by averaging the predictions of all qualified SPODEs, and the estimate of joint probability for AODE is

$\displaystyle P_{\text{AODE}}(\textbf{x},y)=\frac{\sum_{\alpha=1\wedge F(x_{% \alpha})\geqslant m}^{n}P(y,x_{\alpha})P_{\text{SPODE}^{\alpha}}(x_{1},\ldots,% x_{n}|x_{\alpha},y)}{|\{\alpha:1\leqslant\alpha\leqslant n\wedge F(x_{\alpha})% \geqslant m\}|},$ (5)

where $F(x_{\alpha})$ is a count of the number of training examples having attribute-value $x_{\alpha}$ and is used to enforce the limit $m$ that we place on the support needed in order to accept a conditional probability estimate. If we regard the combination of $X_{\alpha}$ and $Y$ as a superclass variable $Y^{*}$ , the topology of $\text{SPODE}^{\alpha}$ is just the same as that of NB.

NB has $n$ attributes and AODE has $n$ SPODEs. Inspired by the learning strategies for improving NB, similar strategies can be applied for improving AODE. NB performs attribute selection and AODE performs SPODE selection. Yang and Korb [32] proposed Forward Sequential Addition (FSA), which begins with an empty ensemble and then uses hill-climbing search to iteratively add SPODEs most helpful for lowering the ensemble’s classification error. The ensemble that achieves the lowest leave-one-out Cross validation (CV) error in training during the addition process is selected. Inspired by the BSE strategy for attribute selection in NB [25], BSE starts out with a full ensemble including every SPODE [32]. It then uses hill-climbing search to iteratively eliminate SPODEs whose individual exclusion is most helpful for lowering the classification error. The ensemble that achieves the lowest leave-one-out CV error in training during the elimination process is selected.

NB performs powerful attribute weighting and similarly, AODE performs SPODE weighting. The classification accuracy of different SPODEs in AODE may differ greatly for the same dataset. Hence, it is problematic to treat all the SPODEs equally. Jiang et al. [20] proposed to respectively use mutual information, conditional log likelihood, classification accuracy and area under the ROC curve as the information metrics for measuring the weights of different SPODEs, and then linearly combine their probability estimates of $P(\textbf{x},y)$ . Yu et al. [22] proposed a more fine-grained weighting approach, which respectively uses the Kullback-Leibler measure and the information gain to study the relationship between root attribute value and class variable. The joint probability for SPODE is estimated by Eq. (6). Wang et al. [33] redefined joint entropy and conditional entropy to respectively measure the uncertainty of superparent or non-superparent attribute value. The weights assigned to different SPODE members will be finely tuned to make the final weighted AODE fit different instances. Lou et al. [34] proposed to use log likelihood function to measure the extent to which the independence assumption of SPODE is suitable to fit the probability distribution. The weighting approach proposed by Duan et al. [35] considered not only the mutual dependence between the superparent and class variable on weighting, but also the conditional dependence between the superparent and non-superparent attributes.

$\displaystyle P_{\text{AWODE}}(\textbf{x},y)=\frac{\sum_{\alpha=1\wedge F(x_{% \alpha})\geqslant m}^{n}\mathcal{W}(\alpha)P(y,x_{\alpha})\prod^{n}_{j=1,j\neq% \alpha}p(x_{j}|x_{\alpha},y)}{\sum_{\alpha=1\wedge F(x_{\alpha})\geqslant m}^{% n}\mathcal{W}(\alpha)}.$ (6)

3. Information theory and AODE

Information theory [36] was first introduced and developed by Shannon to explain the principle behind point-to-point communication and data storing. Mutual information $I(X_{i};X_{j})$ and conditional mutual information $I(X_{i};X_{j}|Y)$ have been applied to measure mutual dependence and conditional mutual dependence for BNC learning [37, 38]. These information-theoretic metrics take whole training data as the learning object and consider all possible values of $X_{i}$ and $Y$ .

.

The mutual information $I(X_{i};X_{j})$ measures the information that variables $X_{i}$ and $X_{j}$ share or the mutual dependence between them, and is defined as follows:

$\displaystyle I(X_{i};X_{j})=\sum_{x_{i}}\sum_{x_{j}}P(x_{i},x_{j})\log\frac{P% (x_{i},x_{j})}{P(x_{i})P(x_{j})}$ (7)

.

The conditional mutual information $I(X_{i};X_{j}|Y)$ measures the information that variables $X_{i}$ and $X_{j}$ share given $Y$ or the conditional dependence between them, and is defined as follows:

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

.

The multivariate mutual information measures the influence of variable $Y$ on the amount of information shared between $X_{i}$ and $X_{j}$ , and is defined as follows:

$\displaystyle I(X_{i};X_{j};Y)=I(X_{i};X_{j})-I(X_{i};X_{j}|Y)=I(X_{i};Y)-I(X_% {i};Y|X_{j})$ (9)

Figure 2.

The topology of SPODE (a) and its local topologies that respectively take $X_{1}$ (b), $X_{2}$ (c) and $X_{n}$ (d) as the children node.

Each attribute in SPODE takes $X_{\alpha}$ and class variable $Y$ as the superparent. As shown in Fig. 2, using the independence statements encoded in SPODEs, the topology of SPODE can be divided into $n-1$ local topologies that take $X_{i}(1\leqslant i\leqslant n,i\neq\alpha)$ as the children node. Each local topology $X_{i}\leftarrow Y\rightarrow X_{\alpha}\rightarrow X_{i}$ can be used to explicitly represent the local probability distributions $P(x_{i},x_{\alpha},y)$ , and the joint probability distribution for SPODE is uniquely determined by these probability distributions.

Similar to the basic idea of target learning [39], AWODE also takes each unlabeled instance $\textbf{x}=\{x_{1},\ldots,x_{n}\}$ as the target or learning object. $I(x_{i};x_{j})$ , $I(x_{i};x_{j}|y)$ and $I(x_{i};x_{j};y)$ are respectively variants of $I(X_{i};X_{j})$ , $I(X_{i};X_{j}|Y)$ and $I(X_{i};X_{j};Y)$ . They take specific instance as the learning object and are applied to identify the relationships between attribute values.

.

For data point $(x_{1},\ldots,x_{n},y)$ , the pointwise mutual information $I(x_{i};x_{j})$ measures the information that variable values $x_{i}$ and $x_{j}$ share, and is defined as follows:

$\displaystyle I(x_{i};x_{j})=\log\frac{P(x_{i},x_{j})}{P(x_{i})P(x_{j})}$ (10)

.

For data point $(x_{1},\ldots,x_{n},y)$ , the pointwise conditional mutual information $I(x_{i};x_{j}|y)$ measures the information that variable values $x_{i}$ and $x_{j}$ share given $y$ or the conditional dependence between them, and is defined as follows:

$\displaystyle I(x_{i};x_{j}|y)=\log\frac{P(x_{i},x_{j}|y)}{P(x_{i}|y)P(x_{j}|y)}$ (11)

.

For data point $(x_{1},\ldots,x_{n},y)$ , the pointwise multivariate mutual information measures the influence of variable value $y$ on the amount of information shared between $x_{i}$ and $x_{j}$ , and is defined as follows:

$\displaystyle I(x_{i};x_{j};y)=I(x_{i};y)-I(x_{i};y|x_{j})=I(x_{i};x_{j})-I(x_% {i};x_{j}|y)$ (12)

The multivariate mutual information may be positive, negative or zero. The positivity corresponds to relations generalizing the pairwise correlations between $x_{i}$ and $x_{j}$ , nullity corresponds to a refined notion of independence, and negativity detects enhanced relations due to the appearance of $y$ [40, 41]). Thus the multivariate mutual information can be used to measure the difference in correlation between attribute values $x_{i}$ and $x_{j}$ before and after knowing $y$ .

For unlabeled instance $\textbf{x}=\{x_{1},\ldots,x_{n}\}$ , the appearance of attribute value pair $\{x_{i},x_{\alpha}\}(1\leqslant i,\alpha\leqslant n)$ means implicit or significant correlation between them. If the probability distribution of x approximates the independence assumption of SPODE ${}^{\alpha}$ and $y$ is the true class label, then the correlation should be enhanced given $y$ . The label of testing instance x may take any one of the $|Y|$ possible values of variable $Y$ . Thus x can be assumed to be equivalent to a pseudo training set $\mathcal{P}$ that consists of $|Y|$ instances as follows,

$\displaystyle\textbf{x}=\{x_{1},\ldots,x_{n}\}\Leftrightarrow\mathcal{P}=\left% \{\begin{array}[]{l}\mathcal{P}_{1}=\{x_{1},\ldots,x_{n},y_{1}\}\\ \mathcal{P}_{2}=\{x_{1},\ldots,x_{n},y_{2}\}\\ \ldots\\ \mathcal{P}_{|Y|}=\{x_{1},\ldots,x_{n},y_{|Y|}\}\end{array}\right.$ (13)

Given pseudo training data $\mathcal{P}$ , from Eq. (12) the multivariate mutual information $I_{\mathcal{P}}(x_{i},x_{\alpha},Y)$ is applied to measure the difference in correlation between attribute values $\{x_{i},x_{\alpha}\}$ for the local topology with $X_{\alpha}$ as the superparent,

$\displaystyle I_{\mathcal{P}}(x_{i},x_{\alpha},Y)=\sum_{y}I(x_{i};x_{\alpha};y% )=\sum_{y}\{I(x_{\alpha};x_{i})-I(x_{\alpha};x_{i}|y)\}=\sum_{y}\{I(x_{\alpha}% ;y)-I(x_{\alpha};y|x_{i})\}$ (14)

Consider all the $n-1$ local topologies shown in Fig. 2, from Eq. (14) the correlation between $x_{\alpha}$ and the other attribute value can be measured by

$\displaystyle\hat{I}_{\mathcal{P}}=\sum_{i=1,i\neq\alpha}^{n}I_{\mathcal{P}}(x% _{i};x_{\alpha};Y)=\sum_{i=1,i\neq\alpha}^{n}\sum_{y}\{I(x_{\alpha};y)-I(x_{% \alpha};y|x_{i})\}$ (15)

From Eqs (10) and (11) we have

$\displaystyle\left\{\begin{array}[]{l}I(x_{\alpha};y)=\log\frac{P(x_{\alpha},y% )}{P(x_{\alpha})P(y)}\\ I(x_{\alpha};y|x_{i})=\log\frac{P(x_{\alpha},y|x_{i})}{P(x_{\alpha}|x_{i})P(y|% x_{i})}\end{array}\right.$ (16)

and

$\displaystyle\hat{I}_{\mathcal{P}}=\sum_{i=1,i\neq\alpha}^{n}\sum_{y}\log\{P(x% _{\alpha},y)-\log P(x_{\alpha})-\log P(y)-\log P(x_{i},x_{\alpha},y)-\log P(x_% {i})+\log P(x_{i},x_{\alpha})+\log P(x_{i},y)\}=-\sum_{i=1,i\neq\alpha}^{n}% \sum_{y}\{(\log P(x_{i},x_{\alpha},y)-\log P(x_{i},x_{\alpha}))-(\log P(x_{i},% y)-\log P(x_{i}))-(\log P(x_{\alpha},y)-\log P(x_{\alpha}))+\log P(y)\}=-\sum_% {i=1,i\neq\alpha}^{n}\sum_{y}\{\log P(y|x_{i},x_{\alpha})-\log P(y|x_{i})-\log P% (y|x_{\alpha})+\log P(y)\}=-\sum_{i=1,i\neq\alpha}^{n}\sum_{y}\log P(y|x_{i},x% _{\alpha})+\sum_{y}\left\{\sum_{i=1,i\neq\alpha}^{n}\log P(y|x_{i})+(n-1)\log P% (y|x_{\alpha})\right\}-(n-1)\sum_{y}\log P(y)=-\sum_{i=1,i\neq\alpha}^{n}\sum_% {y}\log P(y|x_{i},x_{\alpha})+(n-2)\sum_{y}\log P(y|x_{\alpha})+\sum_{y}\sum_{% i=1}^{n}\log P(y|x_{i})-(n-1)\sum_{y}\log P(y).$ (17)

Because for different SPODEs, the value of $\sum_{y}\sum_{i=1}^{n}\log P(y|x_{i})-(n-1)\sum_{y}\log P(y)$ remains the same while classifying the same instance, and thus it is considered as a constant and neglected for simplicity. Then $\hat{I}_{\mathcal{P}}$ turns to be

$\displaystyle\hat{I}_{\mathcal{P}}=-\sum_{i=1,i\neq\alpha}^{n}\sum_{y}\log P(y% |x_{i},x_{\alpha})+(n-2)\sum_{y}\log P(y|x_{\alpha})+\bigtriangleup$ (18)

From the topology of SPODE ${}^{\alpha}$ shown in Fig. 2, class variable $Y$ and attribute $X_{i}$ are both the superparents, and many prior research works focus on the correlations between them for weighting. However, $\{X_{i},X_{\alpha},Y\}$ forms a local directed acyclic graph for each individual $X_{i}(i\neq\alpha)$ , $Y$ may influence the correlation between $X_{\alpha}$ and $X_{i}$ to different extents when they take different values. For different data points, from the definition of pointwise multivariate mutual information we can see that, $Y$ may enhance or weaken the correlation between $X_{\alpha}$ and $X_{i}$ . That is, knowing $y$ may not surely provide positive influence for enhancing the correlation, and for different class label $y$ the influence may differ greatly. Equation (18) in fact provides an information metric to measure the reasonableness of the topology of SPODE ${}^{\alpha}$ in terms of weighting. Thus in this paper, we propose to use $\mathcal{W}(\alpha)=\hat{I}_{\mathcal{P}}-\bigtriangleup$ as the weighting metric. The resulting AWODE algorithm is presented in Algorithm 1.

[h] The AWODE algorithm.Training dataset $\mathcal{D}$ with $N$ instances, testing instance $\textbf{x}=\{x_{1},x_{2},\ldots x_{n}\}$ . Class label for x.

Generate a three-dimensional table of co-occurrence counts for each pair of attribute values and each class label.

According to the attribute values in test instance x, for each class label $y$ , compute $\hat{P}(y|x_{i},x_{j})$ and $\hat{P}(y|x_{j})$ based on the estimates of $\hat{P}(x_{j},y)$ and $\hat{P}(x_{i},x_{j},y)$ .

$\alpha$ = 1 $\to$ $n$

take $x_{\alpha}$ as the superparent of SPODE ${}_{\alpha}$ ;

compute $\mathcal{W}(\alpha)=-\sum_{i=1,i\neq\alpha}^{n}\sum_{y}\log P(y|x_{i},x_{% \alpha})+(n-2)\sum_{y}\log P(y|x_{\alpha})$ according to Eq. (18);

Compute $P_{\mathrm{AWODE}}(\textbf{x},y)$ according to Eq. (6) and output the class label by selecting $y^{*}=\mathop{\arg\max}_{y}P_{\mathrm{AWODE}}(\textbf{x},y)$

Table 1 summarizes the time complexity of each BNC discussed. At training time, AODE needs to generate a three-dimensional table of co-occurrence counts for each pair of attribute values and each class label, and the time complexity is $\mathcal{O}(tn^{2})$ [10], where $t$ is the number of training instances and $n$ is the number of attributes. AWODE needs to calculate the pointwise multivariate mutual information for weighting. The resulting time complexity of forming the three dimensional probability table is $\mathcal{O}(m(nv)^{2})$ , where $m$ is the number of class labels and $v$ is the maximum number of values per attribute, as an entry must be updated for each pair of attribute values in testing instance and all possible class labels. At classification time, for estimating the conditional probabilities in Eq. (5) AODE needs to consider each pair of qualified parent and children attributes within each class, and the time complexity is $\mathcal{O}(mn^{2})$ . AWODE has identical time complexity to AODE because it behaves identically to AODE at classification time. Thus AWODE needs an additional operation for computing the weights, and that does not increase the overall classification time complexity.

Table 1

Complexity summary for different BNCs, where $N$ is the number of training instances, $n$ is the number of attributes, $v$ is the maximum number of values per attribute, $m$ is the number of class labels. $k$ is the parameter $k$ selected in KDB

BNC	Training time	Classification time
NB	$\mathcal{O}(Nn)$	$\mathcal{O}(mn)$
TAN	$\mathcal{O}(Nn^{2}+m(nv)^{2}+n^{2}\textit{logn})$	$\mathcal{O}(mn)$
KDB	$\mathcal{O}(Nn^{2}+m(nv)^{2}+Nnk)$	$\mathcal{O}(mnk)$
AODE	$\mathcal{O}(Nn^{2})$	$\mathcal{O}(mn^{2})$
WAODE-MI	$\mathcal{O}(Nn^{2}+mnv)$	$\mathcal{O}(mn^{2})$
AVWAODE-KL	$\mathcal{O}(Nn^{2}+mnv)$	$\mathcal{O}(mn^{2})$
AVWAODE-IG	$\mathcal{O}(Nn^{2}+mnv)$	$\mathcal{O}(mn^{2})$
AWODE	$\mathcal{O}(Nn^{2}+m(nv)^{2})$	$\mathcal{O}(mn^{2})$

Table 2

Data sets

No.	Data set	Instance	Attribute	Class	No.	Data set	Instance	Attribute	Class
1	Labor	57	16	2	21	Vowel	990	13	11
2	Labor-negotiations	57	16	2	22	Splice-c4.5	3177	60	3
3	Zoo	101	16	7	23	Kr-vs-kp	3196	36	2
4	Promoters	106	57	2	24	Dis	3772	29	2
5	Echocardiogram	131	6	2	25	Hypo	3772	29	4
6	Lymphography	148	18	4	26	Abalone	4177	8	3
7	Iris	150	4	3	27	Waveform-5000	5000	40	3
8	Teaching-ae	151	5	3	28	Optdigits	5620	64	10
9	Hepatitis	155	19	2	29	Satellite	6435	36	6
10	Wine	178	13	3	30	Mushrooms	8124	22	2
11	Glass-id	214	9	3	31	Thyroid	9169	29	20
12	Soybean-large	307	35	19	32	Pendigits	10992	16	10
13	Ionosphere	351	34	2	33	Seer_mdl	18962	13	2
14	Cylinder-bands	540	39	2	34	Magic	19020	10	2
15	Balance-scale	625	4	3	35	Letter-recog	20000	16	26
16	Soybean	683	35	19	36	Shuttle	58000	9	7
17	Breast-cancer-w	699	9	2	37	Waveform	100000	21	3
18	Vehicle	846	18	4	38	Localization	164860	5	11
19	Anneal	898	38	6	39	Covtype	581012	54	7
20	Tic-tac-toe	958	9	2	40	Poker-hand	1025010	10	10

4. Experiments

The experiments are conducted on 40 benchmark datasets from the UCI machine learning repository [23], and for these datasets it is supposed that there is no noisy data. Table 2 describes the detailed characteristics of these datasets in ascending order of their sizes, including the number of instances, attributes and classes. As listed in Table 2, the dataset size ranges from 57 instances of Labor to 1,025,010 instances of Poker-hand, and the number of class labels also spans from 2 to 50, enabling us to examine classifiers on datasets with various characteristics. Each algorithm is tested on each dataset using 10 rounds of 10-fold cross validation.

To incorporate the missing values of any attributes into probability computation, the missing values for qualitative attributes and those for quantitative attributes are respectively replaced with a distinct value and mean value in all cases. The BNCs discussed in this paper cannot handle continuous attributes directly, numeric attributes, if any, are discretized using Minimum Description Length Discretization (MDL)[42]. Since $m$ -estimation leads to more accurate probabilities than the Laplace estimation [43], $m$ -estimation ( $m=1$ ) is applied to smooth the probability estimates. Consider the “noise” caused by the above data pre-processing steps, 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. All the experiments run on a desktop computer with an Intel(R) Core(TM) i5-4210U CPU @1.7 GHz, 64 bits and 8G of memory.

In this section, we compare the performance of our proposed methods AWODE with state-of-the-art BNCs, including semi-naive Bayes approaches and weighted AODE approaches. Jiang et al. proposed in [20] to use mutual information, conditional log likelihood, classification accuracy and area under the ROC curve as the weighting metrics, among which mutual information is proved to be the most effective one and thus introduced in the following study only. The BNCs for comparison study are listed as follows.

•
NB [8], Naive Bayes.
•
TAN [17], Tree-augmented Naive Bayes.
•
KDB [18], $k$ -dependence Bayesian classifier with $k=$ 2.
•
AODE [10], Averaged one-dependence estimators.
•
WAODE ${}_{\mathrm{MI}}$ [20], AODE which uses mutual information for weighting.
•
AVWAODE-KL [22], AODE which uses the Kullback-Leibler (KL) measure for weighting.
•
TAODE [33], targeted AODE.
•
IWAODE [34], Independence Weighted AODE.
•
IBWAODE [35], Instance-Based Weighting AODE.
•
AWODE.

Tables A1–A4 in the Appendix respectively show the experimental results in terms of zero-one loss, bias, variance and MCC. Win-draw-loss records summarizing the relative zero-one loss, bias and variance are respectively shown in Tables 3–6, and cell $\left[i;j\right]$ in each table contains the number of datasets on which classifier on row $i$ performs better, equally better or poorer than the classifier on column $j$ . Only when the outcome of a one-tailed binomial sign test is less than 0.05, the difference between algorithms is supposed to be significant.
4.1 Comparisons in terms of zero-one loss

Table 3
W/D/L comparison results of 0–1 loss on all data sets

W/D/L	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE
TAN	25 $\backslash$ 7 $\backslash$ 8
KDB	22 $\backslash$ 9 $\backslash$ 9	19 $\backslash$ 8 $\backslash$ 13
AODE	27 $\backslash$ 8 $\backslash$ 5	18 $\backslash$ 13 $\backslash$ 9	21 $\backslash$ 9 $\backslash$ 10
WAODE ${}_{\text{MI}}$	29 $\backslash$ 8 $\backslash$ 3	23 $\backslash$ 10 $\backslash$ 7	21 $\backslash$ 10 $\backslash$ 9	7 $\backslash$ 28 $\backslash$ 5
AVWAODE-KL	29 $\backslash$ 7 $\backslash$ 4	22 $\backslash$ 10 $\backslash$ 8	21 $\backslash$ 9 $\backslash$ 10	12 $\backslash$ 22 $\backslash$ 6	7 $\backslash$ 29 $\backslash$ 4
TAODE	29 $\backslash$ 7 $\backslash$ 4	21 $\backslash$ 12 $\backslash$ 7	22 $\backslash$ 7 $\backslash$ 11	12 $\backslash$ 24 $\backslash$ 4	6 $\backslash$ 28 $\backslash$ 6	8 $\backslash$ 23 $\backslash$ 9
IWAODE	28 $\backslash$ 9 $\backslash$ 3	22 $\backslash$ 10 $\backslash$ 8	22 $\backslash$ 10 $\backslash$ 8	9 $\backslash$ 31 $\backslash$ 0	6 $\backslash$ 32 $\backslash$ 2	6 $\backslash$ 26 $\backslash$ 8	6 $\backslash$ 29 $\backslash$ 5
IBWAODE	31 $\backslash$ 6 $\backslash$ 3	19 $\backslash$ 12 $\backslash$ 9	18 $\backslash$ 12 $\backslash$ 10	8 $\backslash$ 25 $\backslash$ 7	8 $\backslash$ 22 $\backslash$ 10	10 $\backslash$ 18 $\backslash$ 12	7 $\backslash$ 24 $\backslash$ 9	7 $\backslash$ 22 $\backslash$ 11
AWODE	30 $\backslash$ 6 $\backslash$ 4	22 $\backslash$ 10 $\backslash$ 8	25 $\backslash$ 5 $\backslash$ 10	16 $\backslash$ 20 $\backslash$ 4	11 $\backslash$ 23 $\backslash$ 6	9 $\backslash$ 26 $\backslash$ 5	8 $\backslash$ 30 $\backslash$ 2	12 $\backslash$ 21 $\backslash$ 7	14 $\backslash$ 19 $\backslash$ 7

Figure 3.

The comparison results in terms of zero-one loss.

Zero-one loss is the most common loss function to evaluate the classification performance. The bagging mechanism helps AODE exhibit excellent generalization ability by using multiple “weak” SPODEs in terms of bias, and large number of dependency relationships in one single-model BNC can be distributed throughout these committee members. Variance wise, the unrealistic independence assumption of each SPODE in AODE makes it insensitive to the variation in training data and reduces the risk of overfitting. Thus AODE enjoys the advantage over single-model BNCs in terms the trade-off between bias and variance. From Table 3, AODE performs significantly better than all the single-model BNCs, including NB (27 wins and 5 losses), TAN (18 wins and 9 losses) and KDB (21 wins and 10 losses). The independence assumption makes SPODE fail to actively learn the true estimation of joint probability distribution. By assigning discriminative weights to different SPODEs according to information-theoretic metrics, e.g., mutual information (MI), information gain (IG) and Kullback-Leibler measure (KL), corresponding weighted AODEs, including WAODE ${}_{\text{MI}}$ , AVWAODE-IG and AVWAODE-KL, aim to find a balance between the goodness of fitting the data and model simplicity, and thereby achieve excellent classification performance without overfitting. Since the advantage of AVWAODE-IG is not significant compared to AODE, there is no follow-up comparison of AVWAODE-IG. However, these weighting metrics only focus on the relationship between root attribute (values) and class. In contrast, multivariate mutual information applied by AWODE measures the reasonableness of the local topologies based on the independence assumption.

The significant difference in data quantities makes ever more urgent the need for highly adaptive learners that have high classification accuracy along with high expressivity (i.e., capacity to learn very complex multivariate probability distributions). AWODE is such a learner. The weights assigned to SPODEs will be self-adaptive for different instances, and that will help improve both the inter-operability of these SPODEs and the generalization performance of the final ensemble BNC. To compare the performance of these BNCs while dealing with datasets of different sizes, the datasets are divided into two categories, small datasets (with number of instances $<$ 3,000) and large datasets (with number of instances $>$ 3,000).

From Fig. 3(a) WAODE ${}_{\text{MI}}$ enjoys the advantage, although non-significant, over AODE while dealing with small datasets (3 wins and 2 losses) and large datasets (4 wins and 3 losses). AVWAODE-KL finely tunes the weights of SPODE members in AODE by instantial weighting, and the weight assigned to the same SPODE may vary greatly while dealing with different instances. From Fig. 3b AVWAODE-KL performs similarly to AODE while dealing with small datasets (5 wins and 5 losses), whereas outperforms AODE while dealing with large datasets (7 wins and 1 loss). In contrast, TAODE performs much better than AODE on both small datasets (6 wins and 2 losses) and large datasets (6 wins and 2 losses). IWAODE outperforms AODE while dealing with small datasets (4 wins and 0 loss) and large datasets (5 wins and 0 loss). Besides, IBWAODE performs relatively better than AODE on small datasets (6 wins and 4 losses), but much poorer on large datasets (2 wins and 3 losses). AWODE shows excellent generalization performance, and it enjoys significant advantage over AODE while dealing with small datasets (10 wins and 2 losses) and large datasets (6 wins and 2 losses).

4.2 Bias and variance

Table 4
W/D/L comparison results of bias on all data sets

W/D/L	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE
TAN	25 $\backslash$ 4 $\backslash$ 11
KDB	23 $\backslash$ 7 $\backslash$ 10	20 $\backslash$ 12 $\backslash$ 8
AODE	29 $\backslash$ 7 $\backslash$ 4	17 $\backslash$ 14 $\backslash$ 9	17 $\backslash$ 4 $\backslash$ 19
WAODE ${}_{\text{MI}}$	31 $\backslash$ 2 $\backslash$ 7	22 $\backslash$ 14 $\backslash$ 4	16 $\backslash$ 11 $\backslash$ 13	12 $\backslash$ 23 $\backslash$ 5
AVWAODE-KL	29 $\backslash$ 4 $\backslash$ 7	21 $\backslash$ 12 $\backslash$ 7	13 $\backslash$ 14 $\backslash$ 13	10 $\backslash$ 23 $\backslash$ 7	4 $\backslash$ 27 $\backslash$ 9
TAODE	29 $\backslash$ 5 $\backslash$ 6	21 $\backslash$ 13 $\backslash$ 6	15 $\backslash$ 13 $\backslash$ 12	7 $\backslash$ 30 $\backslash$ 3	4 $\backslash$ 27 $\backslash$ 9	6 $\backslash$ 28 $\backslash$ 6
IWAODE	31 $\backslash$ 5 $\backslash$ 4	21 $\backslash$ 12 $\backslash$ 7	17 $\backslash$ 9 $\backslash$ 14	10 $\backslash$ 27 $\backslash$ 3	10 $\backslash$ 26 $\backslash$ 4	8 $\backslash$ 25 $\backslash$ 7	11 $\backslash$ 24 $\backslash$ 5
IBWAODE	29 $\backslash$ 7 $\backslash$ 4	17 $\backslash$ 12 $\backslash$ 11	13 $\backslash$ 9 $\backslash$ 18	10 $\backslash$ 18 $\backslash$ 12	9 $\backslash$ 17 $\backslash$ 14	10 $\backslash$ 17 $\backslash$ 13	10 $\backslash$ 15 $\backslash$ 15	6 $\backslash$ 19 $\backslash$ 15
AWODE	34 $\backslash$ 2 $\backslash$ 4	24 $\backslash$ 10 $\backslash$ 6	19 $\backslash$ 8 $\backslash$ 13	15 $\backslash$ 22 $\backslash$ 3	9 $\backslash$ 26 $\backslash$ 5	11 $\backslash$ 27 $\backslash$ 2	8 $\backslash$ 29 $\backslash$ 3	12 $\backslash$ 22 $\backslash$ 6	18 $\backslash$ 18 $\backslash$ 4

The bias-variance decomposition provides valuable insights into the components of the error of learned classifiers. Bias measures the deviation between the expected output of the learning algorithm and the real result, and low bias generally means that the BNC is better able to adapt to training data. Given instance x, bias measures how closely the classifier can describe the decision boundary and is defined as [44]

$\displaystyle\textit{bias}^{2}=\frac{1}{2}\sum_{\hat{y},y\in Y}[P(\hat{y}|% \textbf{x})-P(y|\textbf{x})]^{2}$ (19)

where $y$ and $\hat{y}$ are the true class label and the label which predicted by classifier. Ensemble BNCs can represent more conditional dependencies among attributes, thus they commonly achieve bias advantage. From Table 4, AODE outperforms NB (29 wins and 4 losses) and TAN (17 wins and 9 losses), and performs similarly to 2-dependence KDB (17 wins and 19 losses). Using different metrics for weighting can help reduce bias. WAODE ${}_{\text{MI}}$ significantly outperforms AODE (12 wins and 5 losses). AVWAODE-KL performs similarly to AODE (10 wins and 7 losses). TAODE enjoys advantage over AODE, although non-significant (7 wins and 3 losses). Meanwhile, IWAODE performs much better than AODE (10 wins and 3 losses). In contrast, IBWAODE performs poorer than AODE (10 wins and 12 losses). AWODE performs the best among weighted AODEs on reducing bias. The information implicated in testing instance is introduced by weighting, and that enhances the ability of AWODE to fit data indirectly.

Table 5

W/D/L comparison results of variance on all data sets

W/D/L	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE
TAN	4 $\backslash$ 3 $\backslash$ 33
KDB	7 $\backslash$ 2 $\backslash$ 31	10 $\backslash$ 8 $\backslash$ 22
AODE	8 $\backslash$ 7 $\backslash$ 25	29 $\backslash$ 7 $\backslash$ 4	31 $\backslash$ 3 $\backslash$ 6
WAODE ${}_{\text{MI}}$	10 $\backslash$ 5 $\backslash$ 25	29 $\backslash$ 6 $\backslash$ 5	29 $\backslash$ 5 $\backslash$ 6	5 $\backslash$ 24 $\backslash$ 11
AVWAODE-KL	8 $\backslash$ 4 $\backslash$ 28	26 $\backslash$ 8 $\backslash$ 6	30 $\backslash$ 4 $\backslash$ 6	5 $\backslash$ 16 $\backslash$ 19	4 $\backslash$ 19 $\backslash$ 17
TAODE	8 $\backslash$ 5 $\backslash$ 27	27 $\backslash$ 7 $\backslash$ 6	28 $\backslash$ 6 $\backslash$ 6	3 $\backslash$ 23 $\backslash$ 14	5 $\backslash$ 22 $\backslash$ 13	13 $\backslash$ 21 $\backslash$ 6
IWAODE	9 $\backslash$ 4 $\backslash$ 27	27 $\backslash$ 9 $\backslash$ 4	29 $\backslash$ 4 $\backslash$ 7	6 $\backslash$ 24 $\backslash$ 10	8 $\backslash$ 22 $\backslash$ 10	12 $\backslash$ 24 $\backslash$ 4	8 $\backslash$ 24 $\backslash$ 8
IBWAODE	9 $\backslash$ 10 $\backslash$ 21	32 $\backslash$ 5 $\backslash$ 3	30 $\backslash$ 5 $\backslash$ 5	17 $\backslash$ 17 $\backslash$ 6	20 $\backslash$ 12 $\backslash$ 8	27 $\backslash$ 9 $\backslash$ 4	27 $\backslash$ 10 $\backslash$ 3	20 $\backslash$ 13 $\backslash$ 7
AWODE	9 $\backslash$ 4 $\backslash$ 27	29 $\backslash$ 5 $\backslash$ 6	31 $\backslash$ 2 $\backslash$ 7	6 $\backslash$ 24 $\backslash$ 10	9 $\backslash$ 23 $\backslash$ 8	12 $\backslash$ 23 $\backslash$ 5	13 $\backslash$ 22 $\backslash$ 5	10 $\backslash$ 20 $\backslash$ 10	8 $\backslash$ 8 $\backslash$ 24

Given instance x, variance reflects the sensitivity of learned BNC to variations in the training data, and overfitting may lead to higher variance [45]. Variance is defined as [44]

$\displaystyle\textit{variance}=\frac{1}{2}\left[1-\sum_{\hat{y}\in Y}P(\hat{y}% |\textbf{x})^{2}\right]$ (20)

where $y$ and $\hat{y}$ are the true class label and the label which predicted by classifier. The topologies of NB and AODE remain the same irrespective of the variations in training data. From Table 5, NB performs the best in terms of variance among single-model BNCs, and AODE performs the best among ensemble BNCs. IBWAODE performs the best among all weighted AODEs, followed by AWODE. They both can flexibly assign discriminative weights to each single SPODE for different test instances by instantial weighting, which can help reduce variance despite the relatively high computational overhead. AWODE achieves the bias-variance tradeoff such that its bias significantly decreases at the cost of variance. High variance incurred by overfitting labeled training data may results in degradation in classification accuracy, whereas that incurred by overfitting unlabeled testing instance may result in improvement in classification accuracy.

4.3 Matthews correlation coefficient

Table 6
W/D/L comparison results of MCC on all data sets

W/D/L	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE
TAN	15 $\backslash$ 18 $\backslash$ 7
KDB	15 $\backslash$ 15 $\backslash$ 10	9 $\backslash$ 22 $\backslash$ 9
AODE	21 $\backslash$ 16 $\backslash$ 3	7 $\backslash$ 29 $\backslash$ 4	11 $\backslash$ 23 $\backslash$ 6
WAODE ${}_{\text{MI}}$	20 $\backslash$ 18 $\backslash$ 2	11 $\backslash$ 25 $\backslash$ 4	11 $\backslash$ 25 $\backslash$ 4	3 $\backslash$ 34 $\backslash$ 3
AVWAODE-KL	22 $\backslash$ 15 $\backslash$ 3	10 $\backslash$ 25 $\backslash$ 5	12 $\backslash$ 22 $\backslash$ 6	3 $\backslash$ 32 $\backslash$ 5	0 $\backslash$ 37 $\backslash$ 3
TAODE	21 $\backslash$ 16 $\backslash$ 3	9 $\backslash$ 26 $\backslash$ 5	12 $\backslash$ 22 $\backslash$ 6	2 $\backslash$ 36 $\backslash$ 2	3 $\backslash$ 34 $\backslash$ 3	5 $\backslash$ 33 $\backslash$ 2
IWAODE	20 $\backslash$ 18 $\backslash$ 2	9 $\backslash$ 27 $\backslash$ 4	11 $\backslash$ 24 $\backslash$ 5	2 $\backslash$ 35 $\backslash$ 3	4 $\backslash$ 32 $\backslash$ 4	5 $\backslash$ 34 $\backslash$ 1	2 $\backslash$ 36 $\backslash$ 2
IBWAODE	20 $\backslash$ 19 $\backslash$ 1	9 $\backslash$ 28 $\backslash$ 3	11 $\backslash$ 24 $\backslash$ 5	6 $\backslash$ 33 $\backslash$ 1	4 $\backslash$ 33 $\backslash$ 3	5 $\backslash$ 33 $\backslash$ 2	3 $\backslash$ 36 $\backslash$ 1	3 $\backslash$ 34 $\backslash$ 3
AWODE	24 $\backslash$ 15 $\backslash$ 1	11 $\backslash$ 27 $\backslash$ 2	15 $\backslash$ 20 $\backslash$ 5	5 $\backslash$ 34 $\backslash$ 1	6 $\backslash$ 31 $\backslash$ 3	7 $\backslash$ 31 $\backslash$ 2	6 $\backslash$ 34 $\backslash$ 0	6 $\backslash$ 31 $\backslash$ 3	4 $\backslash$ 34 $\backslash$ 2

Figure 4.

The comparison results in terms of Matthews Correlation Coefficient.

Standard learning algorithms are designed under the premise of a balanced class distribution. When dealing with skewed class distributions, the classification problem will become more difficult as the number of class labels increases [46, 47]. The Matthews correlation coefficient (MCC) [48] is introduced by biochemist Brian W. Matthews in 1975 to measure the quality of binary (two-class) classifications. It can be described in the form of a contingency matrix by calculating the Pearson product moment correlation coefficient[49] between actual and predicted values. For multi-class datasets, the classification results can be shown in the form of a confusion matrix as follows in terms of the extended MCC [50].

$\displaystyle\left[\begin{array}[]{ccc}N_{11}&\ldots&N_{1m}\\ \vdots&\ddots&\vdots\\ N_{m1}&\ldots&N_{mm}\end{array}\right]$ (21)

Each entry $N_{ii}(1\leqslant i\leqslant m)$ denotes the number of instances that were assigned with the true class label $C_{i}$ . Each entry $N_{ij}(i\neq j,1\leqslant i,j\leqslant m)$ denotes the number of instances that were assigned with class label $C_{j}$ whereas the true class was $C_{i}$ . Then the extended MCC can be calculated as follows according to the confusion matrix:

$\displaystyle\textit{MCC}=\frac{\sum_{mij}N_{ii}N_{jm}-N_{ij}N_{mi}}{\sqrt{% \sum_{i}(\sum_{j}N_{ij})(\sum_{j^{\prime},i^{\prime}\neq i}N_{i^{\prime}j^{% \prime}})}\sqrt{\sum_{i}(\sum_{j}N_{ji})(\sum_{j^{\prime},i^{\prime}\neq i}N_{% j^{\prime}i^{\prime}})}}$ (22)

The MCC is an effective balanced measure to describe the confusion matrix of true and false positives and negatives by a single number [49, 51]. Table A4 shows the average results of MCC on all datasets. The corresponding W/D/L comparison results are presented in Table 6. To compare the performance of these BNCs while dealing with datasets of different sizes, the datasets are divided into two categories, two-class datasets (with two class labels) and multi-class datasets (with more than two class labels).

From Fig. 4a, WAODE ${}_{\text{MI}}$ performs poorer than AODE on two-class datasets (1 win and 2 losses), and better on multi-class datasets (2 wins and 1 loss). Similarly, from Fig. 4b, AVWAODE-KL performs poorer than AODE on two-class datasets (1 win and 4 losses), and it outperforms AODE on multi-class datasets (2 wins and 1 loss). As shown in Fig. 4c, TAODE performs poorer than AODE on two-class datasets (0 win and 2 losses), whereas better on multi-class datasets (2 wins and 0 loss). Meanwhile, from Fig. 4d, IWAODE performs poorer than AODE on two-class datasets (0 win and 2 losses), and better on multi-class datasets (2 wins and 1 loss). As shown in Fig. 4e and f, IBWAODE and AWODE show excellent generalization performance and enjoy significant advantage over AODE. They respectively outperform AODE on 4 and 3 multi-class datasets.

4.4 Analysis of classification and training time

Figure 5.

Time comparisons.

Figure 5 shows the mean training and classification time comparisons of the different out-of-core BNCs relative to AWODE. Each bar represents the sum of all 40 datasets in a 10-fold cross validation experiment. As shown in Fig. 5a, due to the independence assumptions the topologies of NB and AODE are determined before training, thus their training times are the least when compared to the other BNCs. Among single-model BNCs, TAN and KDB respectively learn 1-dependence and 2-dependence relationships from data at training time, and KDB needs extra time to compute mutual information for sorting attributes. With respect to classification time, high-dependence BNCs need a bit more time to compute the conditional probabilities than low-dependence BNCs. Thus, KDB takes a bit more time than TAN and NB. AODE and weighted AODEs need to aggregate the estimates of joint probabilities of all qualified SPODEs, thus as shown in Fig. 5b their computation overheads are similar whereas they are computationally expensive compared to single-model BNCs.

Among weighted AODEs, for WAODE ${}_{\text{MI}}$ the information-theoretic metric for weighting, i.e., mutual information, considers all possible values of the superparent attribute and will be computed at training time. WAODE ${}_{\text{MI}}$ needs a bit more time to compute weighted probabilities for each SPODE at classification time. In contrast, AVWAODE-KL, TAODE, IWAODE, IBWAODE and AWODE apply instantial weighting and fully consider the difference among testing instances. Thus they perform identically to AODE at training time, but they need extra time to compute weights according to different weighting metrics at classification time.

5. Conclusions

The ensemble learning mechanism and independence assumption help AODE enjoy advantage in reducing bias and variance. A potential disadvantage of AODE is its unreasonable non-distinctive weights assigned to SPODEs. In current research, weighting for AODE focuses on the dependency relationship between the root attribute (or root attribute value) and the class variable. We argue that, the weight should help evaluate the reasonableness of the independence assumptions implicated in SPODEs. Based on this premise, the multivariate mutual information is introduced to measure the correlation between attributes in each local topology of the SPODE. Our proposed algorithm, called AWODE, learns weights from specific instance rather than training dataset, and thus retains the simplicity and direct theoretical foundation of AODE while alleviating the limitations of its independence assumptions. The experimental results on datasets from UCI machine learning repository reveal that, AWODE has substantially lower bias than AODE at the cost of a small increase in variance. Because the independence assumptions of SPODEs are violated to different extents, applying model selection together with model weighting to choose the best few rather than all the SPODEs will further help the final ensemble approximate the true joint probability distribution. An interesting future work will be the exploration of more effective methods to select SPODEs and learn the weights for them.

Footnotes

Appendix

Table A1

Experimental results of 0–1 loss

No.	Data set	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE	AWODE
1	Labor	0.0351	0.0526	0.0351	0.0526	0.0526	0.0526	0.0526	0.0526	0.0526	0.0351
2	Labor-negotiations	0.0702	0.1053	0.0702	0.0526	0.0526	0.0351	0.0526	0.0526	0.0526	0.0351
3	Zoo	0.0297	0.0099	0.0495	0.0297	0.0297	0.0297	0.0198	0.0297	0.0198	0.0198
4	Promoters	0.0755	0.1321	0.2547	0.1321	0.1415	0.1321	0.1226	0.1226	0.1038	0.1509
5	Echocardiogram	0.3359	0.3282	0.3435	0.3206	0.3206	0.3435	0.3359	0.3282	0.3282	0.3282
6	Lymphography	0.1486	0.1757	0.2365	0.1689	0.1554	0.1622	0.1554	0.1554	0.1419	0.1622
7	Iris	0.0867	0.0800	0.0867	0.0867	0.0867	0.0867	0.0867	0.0867	0.0867	0.0867
8	Teaching-ae	0.4967	0.5497	0.5364	0.4901	0.4503	0.4570	0.4636	0.4636	0.4570	0.4503
9	Hepatitis	0.1935	0.1677	0.1871	0.1806	0.1806	0.2000	0.1871	0.1871	0.1742	0.1871
10	Wine	0.0169	0.0337	0.0225	0.0225	0.0169	0.0169	0.0281	0.0169	0.0169	0.0281
11	Glass-id	0.2617	0.2196	0.2196	0.2523	0.2570	0.2383	0.2523	0.2523	0.2196	0.2336
12	Soybean-large	0.1238	0.1107	0.0879	0.0782	0.0814	0.0814	0.0782	0.0814	0.0912	0.0782
13	Ionosphere	0.1054	0.0684	0.0741	0.0741	0.0712	0.0655	0.0741	0.0712	0.0712	0.0684
14	Cylinder-bands	0.2148	0.2833	0.2259	0.1889	0.1796	0.1907	0.1870	0.1815	0.1926	0.1926
15	Balance-scale	0.2720	0.2736	0.2784	0.2832	0.2816	0.2832	0.2832	0.2816	0.2832	0.2592
16	Soybean	0.0893	0.0469	0.0556	0.0469	0.0483	0.0498	0.0483	0.0483	0.0542	0.0483
17	Breast-cancer-w	0.0258	0.0415	0.0744	0.0358	0.0358	0.0372	0.0401	0.0372	0.0372	0.0343
18	Vehicle	0.3924	0.2943	0.2943	0.2896	0.2872	0.2849	0.2766	0.2872	0.2896	0.2754
19	Anneal	0.0379	0.0111	0.0089	0.0089	0.0089	0.0089	0.0078	0.0089	0.0178	0.0078
20	Tic-tac-toe	0.3069	0.2286	0.2035	0.2651	0.2724	0.2808	0.2630	0.2547	0.2662	0.2463
21	Vowel	0.4242	0.1303	0.1818	0.1495	0.1949	0.1889	0.1323	0.1566	0.1697	0.1343
22	Splice-c4.5	0.0444	0.0466	0.0941	0.0365	0.0365	0.0362	0.0362	0.0368	0.0378	0.0362
23	Kr-vs-kp	0.1214	0.0776	0.0416	0.0842	0.0576	0.0544	0.0773	0.0748	0.0826	0.0942
24	Dis	0.0159	0.0159	0.0138	0.0130	0.0143	0.0143	0.0125	0.0133	0.0127	0.0122
25	Hypo	0.0138	0.0141	0.0114	0.0095	0.0101	0.0098	0.0119	0.0098	0.0114	0.0098
26	Abalone	0.4762	0.4587	0.4563	0.4472	0.4475	0.4458	0.4465	0.4470	0.4482	0.4448
27	Waveform-5000	0.2006	0.1844	0.2000	0.1462	0.1450	0.1486	0.1466	0.1462	0.1442	0.1472
28	Optdigits	0.0767	0.0407	0.0372	0.0311	0.0302	0.0290	0.0290	0.0302	0.0276	0.0285
29	Satellite	0.1806	0.1214	0.1080	0.1148	0.1148	0.1187	0.1147	0.1158	0.1117	0.1161
30	Mushrooms	0.0196	0.0001	0.0000	0.0001	0.0000	0.0000	0.0002	0.0000	0.0002	0.0002
31	Thyroid	0.1111	0.0720	0.0706	0.0701	0.0655	0.0614	0.0629	0.0654	0.0706	0.0638
32	Pendigits	0.1181	0.0321	0.0294	0.0200	0.0199	0.0202	0.0200	0.0206	0.0185	0.0202
33	Seer_mdl	0.2379	0.2376	0.2555	0.2328	0.2315	0.2371	0.2340	0.2329	0.2325	0.2330
34	Magic	0.2239	0.1675	0.1637	0.1752	0.1762	0.1834	0.1725	0.1773	0.1744	0.1757
35	Letter-recog	0.2525	0.1300	0.0986	0.0883	0.0853	0.0826	0.0838	0.0871	0.0854	0.0833
36	Shuttle	0.0039	0.0015	0.0009	0.0008	0.0009	0.0008	0.0008	0.0008	0.0011	0.0008
37	Waveform	0.0220	0.0202	0.0256	0.0180	0.0181	0.0181	0.0182	0.0184	0.0181	0.0179
38	Localization	0.4955	0.3575	0.2964	0.3596	0.3566	0.3536	0.3544	0.3766	0.3593	0.3553
39	Covtype	0.3158	0.2517	0.1421	0.2387	0.2289	0.2180	0.2246	0.2342	0.2366	0.2220
40	Poker-hand	0.4988	0.3295	0.1961	0.4812	0.1758	0.3103	0.3453	0.0771	0.4690	0.3311

Table A2

Experimental results of bias

No.	Data set	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE	AWODE
1	Labor	0.0289	0.0211	0.0279	0.0347	0.0200	0.0342	0.0363	0.0195	0.0205	0.0111
2	Labor-negotiations	0.0505	0.0716	0.0553	0.0316	0.0268	0.0405	0.0474	0.0253	0.0268	0.0232
3	Zoo	0.0318	0.0303	0.0403	0.0273	0.0273	0.0282	0.0282	0.0273	0.0282	0.0273
4	Promoters	0.0786	0.1329	0.1569	0.4777	0.5489	0.5346	0.4000	0.5083	0.2840	0.4740
5	Echocardiogram	0.2844	0.2642	0.3065	0.2751	0.2572	0.2788	0.2763	0.2814	0.2840	0.2812
6	Lymphography	0.0902	0.1027	0.1041	0.0933	0.0951	0.0859	0.0931	0.0892	0.0857	0.0831
7	Iris	0.0612	0.0638	0.0596	0.0586	0.0656	0.0720	0.0592	0.0578	0.0664	0.0500
8	Teaching-ae	0.4836	0.4566	0.4606	0.4370	0.3984	0.4016	0.4198	0.4274	0.4616	0.4124
9	Hepatitis	0.1537	0.1712	0.1741	0.1649	0.1655	0.1782	0.1724	0.1724	0.1749	0.1627
10	Wine	0.0331	0.0507	0.0520	0.0346	0.0381	0.0361	0.0376	0.0351	0.0317	0.0364
11	Glass-id	0.2901	0.2756	0.2713	0.2785	0.2780	0.2823	0.2785	0.2797	0.2818	0.2827
12	Soybean-large	0.1070	0.1422	0.1086	0.0648	0.0655	0.0638	0.0651	0.0656	0.0811	0.0657
13	Ionosphere	0.1220	0.0804	0.0855	0.0744	0.0751	0.0756	0.0764	0.0784	0.0881	0.0790
14	Cylinder-bands	0.2000	0.3117	0.1939	0.1589	0.1501	0.1546	0.1610	0.1487	0.1711	0.1620
15	Balance-scale	0.1840	0.1843	0.1902	0.1905	0.1827	0.1827	0.1905	0.1844	0.1905	0.1725
16	Soybean	0.1015	0.0522	0.0491	0.0524	0.0503	0.0509	0.0515	0.0518	0.0693	0.0522
17	Breast-cancer-w	0.0187	0.0384	0.0449	0.0338	0.0327	0.0337	0.0334	0.0303	0.0234	0.0173
18	Vehicle	0.3330	0.2382	0.2494	0.2415	0.2398	0.2409	0.2412	0.2409	0.2435	0.2393
19	Anneal	0.0354	0.0201	0.0073	0.0214	0.0194	0.0196	0.0214	0.0190	0.0181	0.0189
20	Tic-tac-toe	0.2614	0.1746	0.1367	0.2005	0.2104	0.2063	0.2008	0.1973	0.1994	0.1941
21	Vowel	0.3301	0.1942	0.1745	0.1895	0.1811	0.1836	0.1698	0.1860	0.2249	0.1711
22	Splice-c4.5	0.0351	0.0395	0.0961	0.0308	0.0315	0.0312	0.0308	0.0306	0.0331	0.0316
23	Kr-vs-kp	0.1107	0.0702	0.0417	0.0747	0.0518	0.0467	0.0688	0.0633	0.0763	0.0798
24	Dis	0.0165	0.0193	0.0191	0.0170	0.0179	0.0183	0.0178	0.0167	0.0168	0.0176
25	Hypo	0.0092	0.0124	0.0077	0.0071	0.0078	0.0077	0.0079	0.0074	0.0080	0.0081
26	Abalone	0.4180	0.3126	0.3033	0.3201	0.3212	0.3150	0.3183	0.3205	0.3199	0.3139
27	Waveform-5000	0.1762	0.1232	0.1157	0.1235	0.1184	0.1208	0.1213	0.1197	0.1219	0.1222
28	Optdigits	0.0685	0.0275	0.0250	0.0233	0.0224	0.0217	0.0224	0.0221	0.0200	0.0218
29	Satellite	0.1746	0.0950	0.0808	0.0902	0.0902	0.0922	0.0897	0.0921	0.0884	0.0895
30	Mushrooms	0.0237	0.0001	0.0001	0.0004	0.0002	0.0003	0.0004	0.0002	0.0004	0.0004
31	Thyroid	0.0994	0.0587	0.0553	0.0611	0.0561	0.0527	0.0550	0.0563	0.0648	0.0547
32	Pendigits	0.1095	0.0314	0.0207	0.0228	0.0231	0.0225	0.0225	0.0231	0.0200	0.0231
33	Seer_mdl	0.2361	0.2114	0.2100	0.2226	0.2137	0.2143	0.2150	0.2186	0.2214	0.2178
34	Magic	0.2111	0.1252	0.1241	0.1600	0.1541	0.1676	0.1546	0.1600	0.1595	0.1592
35	Letter-recog	0.2207	0.1032	0.0806	0.0876	0.0823	0.0807	0.0814	0.0850	0.0877	0.0805
36	Shuttle	0.0040	0.0008	0.0007	0.0006	0.0006	0.0007	0.0006	0.0006	0.0007	0.0006
37	Waveform	0.0219	0.0152	0.0210	0.0156	0.0158	0.0157	0.0149	0.0166	0.0157	0.0158
38	Localization	0.4523	0.3106	0.2134	0.3129	0.3068	0.3004	0.3010	0.3281	0.3126	0.2967
39	Covtype	0.3067	0.2298	0.1193	0.2207	0.2083	0.1984	0.2034	0.2166	0.2183	0.2022
40	Poker-hand	0.4979	0.2865	0.1326	0.4216	0.1716	0.2630	0.2622	0.0805	0.3969	0.2546

Table A3

Experimental results of variance

No.	Data set	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE	AWODE
1	Labor	0.0395	0.0632	0.0721	0.0179	0.0221	0.0658	0.0321	0.0384	0.0268	0.0363
2	Labor-negotiations	0.0653	0.1389	0.1289	0.0526	0.0626	0.0911	0.0789	0.0800	0.0626	0.0716
3	Zoo	0.0439	0.0606	0.0658	0.0424	0.0424	0.0445	0.0445	0.0424	0.0445	0.0424
4	Promoters	0.0786	0.1729	0.1889	0.0994	0.0654	0.0911	0.1486	0.0946	0.1389	0.0946
5	Echocardiogram	0.1272	0.1265	0.1400	0.1319	0.1335	0.1328	0.1284	0.1326	0.1277	0.1305
6	Lymphography	0.0343	0.1116	0.1408	0.0476	0.0479	0.0467	0.0498	0.0476	0.0408	0.0455
7	Iris	0.0428	0.0662	0.0404	0.0374	0.0364	0.0420	0.0388	0.0402	0.0436	0.0360
8	Teaching-ae	0.1484	0.1914	0.1494	0.1650	0.1776	0.1744	0.1622	0.1686	0.1564	0.1636
9	Hepatitis	0.0424	0.0582	0.0612	0.0527	0.0541	0.0473	0.0492	0.0492	0.0486	0.0529
10	Wine	0.0093	0.0493	0.0649	0.0231	0.0246	0.0300	0.0251	0.0276	0.0141	0.0195
11	Glass-id	0.0930	0.1075	0.1189	0.1004	0.1051	0.1008	0.1004	0.1020	0.0999	0.1018
12	Soybean-large	0.0783	0.1176	0.0982	0.0842	0.0855	0.0832	0.0839	0.0854	0.0738	0.0824
13	Ionosphere	0.0242	0.0401	0.0581	0.0385	0.0368	0.0407	0.0381	0.0404	0.0238	0.0362
14	Cylinder-bands	0.0656	0.0739	0.0750	0.0961	0.1010	0.0959	0.0923	0.1002	0.0828	0.0947
15	Balance-scale	0.0848	0.0941	0.0872	0.0854	0.0913	0.0913	0.0854	0.0921	0.0854	0.1005
16	Soybean	0.0302	0.0654	0.0439	0.0326	0.0341	0.0341	0.0331	0.0332	0.0290	0.0324
17	Breast-cancer-w	0.0010	0.0337	0.0504	0.0134	0.0128	0.0157	0.0164	0.0156	0.0122	0.0110
18	Vehicle	0.1120	0.1299	0.1283	0.1277	0.1276	0.1275	0.1273	0.1254	0.1245	0.1285
19	Anneal	0.0168	0.0161	0.0152	0.0197	0.0161	0.0138	0.0174	0.0158	0.0103	0.0142
20	Tic-tac-toe	0.0455	0.0824	0.1125	0.0513	0.0604	0.0652	0.0528	0.0556	0.0529	0.0620
21	Vowel	0.2542	0.2445	0.2325	0.2344	0.2310	0.2334	0.2284	0.2337	0.2463	0.2307
22	Splice-c4.5	0.0078	0.0289	0.0800	0.0085	0.0083	0.0087	0.0085	0.0087	0.0089	0.0083
23	Kr-vs-kp	0.0186	0.0152	0.0111	0.0186	0.0119	0.0143	0.0208	0.0165	0.0185	0.0201
24	Dis	0.0069	0.0005	0.0011	0.0071	0.0021	0.0056	0.0040	0.0065	0.0036	0.0033
25	Hypo	0.0051	0.0071	0.0069	0.0049	0.0056	0.0054	0.0055	0.0057	0.0068	0.0056
26	Abalone	0.0682	0.1693	0.1769	0.1544	0.1543	0.1626	0.1561	0.1523	0.1539	0.1623
27	Waveform-5000	0.0259	0.0690	0.0843	0.0410	0.0420	0.0426	0.0426	0.0416	0.0402	0.0412
28	Optdigits	0.0153	0.0185	0.0254	0.0139	0.0137	0.0138	0.0140	0.0138	0.0132	0.0139
29	Satellite	0.0139	0.0367	0.0455	0.0363	0.0364	0.0389	0.0362	0.0379	0.0325	0.0381
30	Mushrooms	0.0043	0.0002	0.0002	0.0001	0.0001	0.0004	0.0002	0.0003	0.0001	0.0001
31	Thyroid	0.0205	0.0257	0.0272	0.0235	0.0239	0.0247	0.0243	0.0237	0.0202	0.0239
32	Pendigits	0.0157	0.0200	0.0236	0.0127	0.0129	0.0127	0.0130	0.0124	0.0107	0.0131
33	Seer_mdl	0.0097	0.0381	0.0613	0.0194	0.0273	0.0318	0.0295	0.0219	0.0200	0.0241
34	Magic	0.0174	0.0490	0.0491	0.0297	0.0289	0.0307	0.0313	0.0298	0.0291	0.0296
35	Letter-recog	0.0471	0.0591	0.0709	0.0448	0.0455	0.0461	0.0457	0.0455	0.0417	0.0455
36	Shuttle	0.0009	0.0004	0.0003	0.0004	0.0004	0.0005	0.0004	0.0004	0.0003	0.0004
37	Waveform	0.0009	0.0053	0.0037	0.0025	0.0023	0.0028	0.0034	0.0019	0.0024	0.0019
38	Localization	0.0460	0.0594	0.1099	0.0580	0.0632	0.0656	0.0657	0.0577	0.0577	0.0691
39	Covtype	0.0094	0.0245	0.0399	0.0200	0.0224	0.0229	0.0240	0.0195	0.0200	0.0222
40	Poker-hand	0.0000	0.0424	0.0633	0.0273	0.0602	0.0346	0.0607	0.0087	0.0346	0.0696

Table A4

Experimental results of MCC

No.	Data set	NB	TAN	KDB	AODE	WAODE ${}_{\text{MI}}$	AVWAODE-KL	TAODE	IWAODE	IBWAODE	AWODE
1	Labor	0.9273	0.8864	0.9230	0.8864	0.8864	0.8864	0.8864	0.8864	0.8864	0.9230
2	Labor-negotiations	0.8459	0.7659	0.8518	0.8864	0.8864	0.9273	0.8864	0.8864	0.8864	0.9230
3	Zoo	0.9611	0.9871	0.9348	0.9611	0.9610	0.9610	0.9742	0.9610	0.9740	0.9740
4	Promoters	0.8515	0.7380	0.5179	0.7380	0.7380	0.7380	0.7581	0.7559	0.7937	0.9813
5	Echocardiogram	0.1569	0.1460	0.0868	0.1820	0.1820	0.0988	0.1276	0.1643	0.1553	0.1553
6	Lymphography	0.7202	0.6633	0.5493	0.6782	0.7041	0.6915	0.7040	0.7041	0.7301	0.6912
7	Iris	0.8701	0.8800	0.8701	0.8701	0.8701	0.8701	0.8701	0.8701	0.8701	0.8901
8	Teaching-ae	0.2552	0.1774	0.1990	0.2651	0.3265	0.3149	0.3052	0.3052	0.3154	0.3256
9	Hepatitis	0.4780	0.4763	0.3961	0.4487	0.4360	0.3684	0.4224	0.3956	0.4870	0.4356
10	Wine	0.9745	0.9488	0.9659	0.9661	0.9745	0.9744	0.9574	0.9744	0.9745	0.9574
11	Glass-id	0.5986	0.6631	0.6633	0.6132	0.6062	0.6347	0.6139	0.6132	0.6652	0.6429
12	Soybean-large	0.8677	0.8797	0.9039	0.9158	0.9120	0.9120	0.9158	0.9120	0.9016	0.9158
13	Ionosphere	0.7689	0.8507	0.8380	0.8378	0.8441	0.8567	0.8378	0.8505	0.8449	0.8505
14	Cylinder-bands	0.5686	0.4180	0.5335	0.6140	0.6321	0.6103	0.6172	0.6289	0.6080	0.6066
15	Balance-scale	0.5009	0.4983	0.4901	0.4799	0.4829	0.4799	0.4799	0.4829	0.4799	0.5261
16	Soybean	0.9045	0.9487	0.9391	0.9496	0.9479	0.9463	0.9480	0.9479	0.9417	0.9480
17	Breast-cancer-w	0.9447	0.9078	0.8340	0.9226	0.9226	0.9193	0.9127	0.9197	0.9183	0.9259
18	Vehicle	0.4860	0.6094	0.6078	0.6161	0.6178	0.6217	0.6328	0.6196	0.6162	0.6349
19	Anneal	0.9109	0.9722	0.9776	0.9777	0.9777	0.9777	0.9804	0.9777	0.9561	0.9804
20	Tic-tac-toe	0.2849	0.4740	0.5367	0.3848	0.3643	0.3505	0.3899	0.4039	0.3821	0.4416
21	Vowel	0.5336	0.8568	0.8001	0.8357	0.7857	0.7924	0.8546	0.8279	0.8135	0.8523
22	Splice-c4.5	0.9279	0.9241	0.8471	0.9408	0.9407	0.9412	0.9413	0.9403	0.9388	0.9413
23	Kr-vs-kp	0.7567	0.8453	0.9167	0.8320	0.8859	0.8918	0.8457	0.8626	0.8350	0.8116
24	Dis	0.4922	0.1842	0.4063	0.5600	0.5109	0.5272	0.5709	0.5600	0.5507	0.5695
25	Hypo	0.9054	0.9007	0.9204	0.9337	0.9298	0.9323	0.9165	0.9316	0.9214	0.9317
26	Abalone	0.3039	0.3112	0.3131	0.3283	0.3278	0.3305	0.3291	0.3282	0.3269	0.3330
27	Waveform-5000	0.7189	0.7234	0.7001	0.7822	0.7828	0.7774	0.7809	0.7812	0.7849	0.7810
28	Optdigits	0.9149	0.9547	0.9587	0.9654	0.9664	0.9678	0.9678	0.9664	0.9694	0.9684
29	Satellite	0.7807	0.8504	0.8665	0.8593	0.8593	0.8551	0.8593	0.8584	0.8627	0.8580
30	Mushrooms	0.9612	0.9998	1.0000	0.9998	1.0000	1.0000	0.9995	1.0000	0.9995	0.9995
31	Thyroid	0.7724	0.8378	0.8368	0.8465	0.8547	0.8618	0.8592	0.8555	0.8468	0.8583
32	Pendigits	0.8699	0.9643	0.9674	0.9778	0.9779	0.9776	0.9778	0.9772	0.9795	0.9776
33	Seer_mdl	0.4756	0.4693	0.4282	0.4819	0.4826	0.4682	0.4772	0.4800	0.4822	0.4806
34	Magic	0.4894	0.6234	0.6330	0.6085	0.6052	0.5915	0.6154	0.6016	0.6108	0.6073
35	Letter-recog	0.7378	0.8648	0.8975	0.9082	0.9114	0.9141	0.9129	0.9093	0.9112	0.9134
36	Shuttle	0.9891	0.9957	0.9975	0.9979	0.9976	0.9978	0.9979	0.9977	0.9969	0.9979
37	Waveform	0.9674	0.9698	0.9620	0.9730	0.9728	0.9729	0.9728	0.9725	0.9728	0.9732
38	Localization	0.3660	0.5474	0.6274	0.5430	0.5469	0.5507	0.5499	0.5156	0.5433	0.5492
39	Covtype	0.5068	0.6008	0.7716	0.6250	0.6403	0.6530	0.6455	0.6284	0.6279	0.6491
40	Poker-hand	0.0000	0.4242	0.6487	0.0813	0.6801	0.4488	0.3853	0.8660	0.1179	0.4128

References

Heckerman

Geiger

and Chickering

D.M.

, Learning bayesian networks: the combination of knowledge and statistical data, Machine Learning 20(3) (1995), 197–243.

Zang

Wen

Wang

Liu

and Song

, A novel topic feature for image scene classification, Neurocomputing 148 (2015), 467–476.

Pearl

, Causality: models, reasoning and inference, Cambridge university press 29, 2009.

Bielza

and Larranaga

, Discrete bayesian network classifiers: A survey, ACM Computing Surveys 47(1) (2014), 1–43.

Liu

Huang

Chen

and Jia

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

Koivisto

and Sood

, Exact Bayesian structure discovery in Bayesian networks, Journal of Machine Learning Research 5 (2004), 549–573.

Chickering

D.M.

, Learning Bayesian Networks is NP-Complete, In: Learning from Data. Lecture Notes in Statistics, Springer, New York, vol 112, 1996, pp. 121–130.

Langley

Iba

and Thompson

, An analysis of bayesian classifiers, In: the tenth national conference on artificial intelligence, AAAI Press, 1992, pp. 223–228.

Langley

and Sage

, Induction of selective Bayesian classifiers, Morgan Kaufmann, 1994.

10.

Webb

G.I.

Boughton

and Wang

, Not so naive bayes: Aggregating one-dependence estimators, Machine Learning 58 (2005), 5–24.

11.

Yang

Webb

G.I.

Cerquides

Korb

K.B.

Boughton

and Ting

, To select or to weigh: A comparative study of linear combination schemes for superparent-one-dependence estimators, IEEE Transactions on Knowledge and Data Engineering 19(12) (2007), 1652–1665.

12.

Keogh

E.J.

and Pazzani

M.J.

, Learning augmented Bayesian classifiers: A comparison of distribution-based and classification-based approaches, In: the seventh international workshop on artificial intelligence and statistics, 1999, pp. 225–230.

13.

Zheng

Webb

G.I.

Suraweera

and Zhu

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

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.

Liu

Wang

and Mammadov

, Learning semi-lazy Bayesian network classifier under the c.i.i.d assumption, Knowledge-Based Systems 208 (2020), 106422.

16.

Long

Wang

Duan

and Sun

, Robust structure learning of bayesian network by identifying significant dependencies, IEEE Access 7 (2019), 116661–116675.

17.

Friedman

Geiger

and Goldszmidt

, Bayesian network classifiers, Machine Learning 29 (1997), 131–163.

18.

Sahami

, Learning limited dependence bayesian classifiers, In: the second ACM International Conference on Knowledge Disvovery and Data Mining. Portland, 1996, pp. 335–338.

19.

Jiang

Zhang

and Cai

, A novel bayes model: Hidden naive bayes, IEEE Transactions on Knowledge and Data Engineering 21 (2009), 1361–1371.

20.

Jiang

Zhang

Cai

and Wang

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

21.

Xiang

and Kang

, Attribute weighting for averaged one-dependence estimators, Applied Intelligence 46(3) (2016), 616–629.

22.

Jiang

and Zhang

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

23.

Bache

and Lichman

, UCI Machine Learning Available online: https://archive.ics.uci.edu/ml/datasets.html.

24.

Howard

R.A.

, Dynamic programming, Management Science 12(5) (1966), 317–348.

25.

Langley

and Sage

, Induction of Selective Bayesian Classifiers, In: the tenth Conference on Uncertainty in Artificial Intelligence, 1994, pp. 399–406.

26.

Yang

and Moody

, Data visualization and feature selection: new algorithms for nongaussian data, Advances in Neural Information Processing Systems (2000), 687–693.

27.

Hall

M.A.

, Correlation-based feature selection for discrete and numeric class machine learning, In: The Seventeenth International Conference on Machine Learning. Morgan Kaufmann, 2000, pp. 359–366.

28.

Hilden

and Hilden

, Computer-aided diagnosis and the atypical case, In: Decision Making and Medical Care: Can Information Science Help, North-Holland Publishing Company, 1976, pp. 365–378.

29.

Zhang

and Zhang

, Learning weighted naive Bayes with accurate ranking, In: the Fourth IEEE International Conference on Data Mining, 2004, pp. 567–570.

30.

Duda

Hart

and Hart

, Pattern Classification. John Wiley and Sons, 2006.

31.

Hart

and Hart

, Attribute weighting via differential evolution algorithm for attribute weighted naive Bayes, Journal of Computational Information Systems 7(5) (2011), 1672–1679.

32.

Yang

Korb

Ting

and Ting

G.I.

, Ensemble selection for superparent-one-dependence estimators, In: Eighteenth Australian Joint Conference on Artificial Intelligence. Lecture notes in artificial intelligence, Sydney, 2005, pp. 102–112.

33.

Wang

Chen

Liu

and Sun

, Self-adaptive attribute value weighting for averaged one-dependence estimators, IEEE Access 8 (2020), 27887–27900.

34.

Lou

Wang

and Mammadov

, Model weighting for one-dependence estimators by measuring the independence assumptions, IEEE Access 8 (2020), 150465–150477.

35.

Duan

Wang

Chen

and Sun

, Instance-based weighting filter for superparent one-dependence estimators, Knowledge-Based Systems, 2020, p. 203.

36.

Shannon

C.E.

, A mathematical theory of communication, The Bell System Technical Journal 27 (1948), 379–423.

37.

Wang

and Wang

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

38.

Long

Wang

and Wang

, Robust Structure Learning of Bayesian Network by Identifying Significant Dependencies, IEEE Access, 2019, pp. 116661–116675.

39.

Wang

and Mammadov

, Target Learning: A Novel Framework to Mine Significant Dependencies for Unlabeled Data, In: twenty-second Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Deakin Univ, 2018, pp. 106–117.

40.

Baudot

Tapia

Bennequin

and Goaillard

J.M.

, Topological information data analysis, Entropy 21(9) (2019), 869.

41.

Tapia

Baudot

Formizano-Treziny

Dufour

and Goaillard

J.M.

, Neurotransmitter identity and electrophysiological phenotype are genetically coupled in midbrain dopaminergic neurons, Scientific Reports 8 (2018), 13637.

42.

FayyadandK.Irani

, Multi-Inerval discretization of continuous-valued attributes for classification learning, In: Thirteenth International Joint Conference on Artificial Intelligence. Chambery, 1993, pp. 1022–1029.

43.

Cestnik

, Estimating probabilities: a crucial task in machine learning, In: European Conference on Artificial Intelligence, 1990, pp. 147–149.

44.

Cestnik

and Wolpert

D.H.

, Bias plus variance decomposition for zeroone loss functions, In Thirteenth International Conference on International Conference on Machine Learning, 1996. pp. 275–283.

45.

Zheng

and Webb

G.I.

, Efficient lazy elimination for averaged one-dependence estimators, In: The Twenty-Third International Conference. Machine Learning, Pittsburgh, 2006, pp. 1113–1120.

46.

and Garcia

E.A.

, Learning from imbalanced data, IEEE Transactions on Knowledge and Data Engineering 21(9) (2009), 1263–1284.

47.

Sun

Wong

A.K.C.

and Wong

M.S.

, Classification of imbalanced data: a review, International Journal of Pattern Recognition and Artificial Intelligence 23(4) (2009), 687–719.

48.

Matthews

B.W.

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

49.

Powers

D.M.W.

, Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation, Journal of Machine Learning Technologies 2(1) (2011), 37–63.

50.

Gorodkin

, Comparing two K-category assignments by a K-category correlation coefficient, Computational Biology and Chemistry 28(5) (2004), 367–374.

51.

Sabri

Fethi

Mohammed

E.A.

et al., Optimal classifier for imbalanced data using Matthews Correlation Coefficient metric, PLOS One 12(6) (2017), e0177678.

Alleviating the independence assumptions of averaged one-dependence estimators by model weighting

Abstract

Keywords

1. Introduction

.

.

.

.

.

.

Table 3 W/D/L comparison results of 0–1 loss on all data sets

Table 4 W/D/L comparison results of bias on all data sets

Table 6 W/D/L comparison results of MCC on all data sets

Footnotes

Appendix

References

Table 3
W/D/L comparison results of 0–1 loss on all data sets

Table 4
W/D/L comparison results of bias on all data sets

Table 6
W/D/L comparison results of MCC on all data sets