# Extracting Credible Dependencies for Averaged One-Dependence Estimator Analysis

Authors: LiMin Wang; ShuangCheng Wang; XiongFei Li; BaoRong Chi
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Of the numerous proposals to improve the accuracy of naive Bayes (NB) by weakening the conditional independence assumption, averaged one-dependence estimator (AODE) demonstrates remarkable zero-one loss performance. However, indiscriminate superparent attributes will bring both considerable computational cost and negative effect on classification accuracy. In this paper, to extract the most credible dependencies we present a new type of seminaive Bayesian operation, which selects superparent attributes by building maximum weighted spanning tree and removes highly correlated children attributes by functional dependency and canonical cover analysis. Our extensive experimental comparison on UCI data sets shows that this operation efficiently identifies possible superparent attributes at training time and eliminates redundant children attributes at classification time.


---

## Body

## 1. Introduction

Bayesian networks (BNs) are a key research area of knowledge discovery and machine learning. A BN consists of two parts: a qualitative part and a quantitative part. The qualitative part denotes the graphical structure of the network, while the quantitative part consists of the conditional probability tables (CPTs) in the network. Although BNs are considered efficient inference algorithms, the quantitative part is considered a complex component and learning an optimal BN structure from existing data has been proven to be an NP-hard problem. The graphical structure of naive Bayes (NB) is simple and definite because of the conditional independence assumption between attributes, making NB efficient and effective [1, 2]. However, violations of this conditional independence assumption can make the classification of NB suboptimal. Numerous algorithms have been proposed to retain the desirable simplicity and efficiency of NB while alleviating the problems of the independence assumption. Averaged one-dependence estimator (AODE) [3, 4] utilizes a restricted class of one-dependence estimators (ODEs) and aggregates the predictions of all qualified estimators within this class. A superparent attribute is indiscriminately selected from an attribute set as the parent of all the other attributes in each ODE. By averaging the estimates of all of the three-dimensional estimators, AODE makes a weaker conditional independence assumption than NB. Previous studies that compared different variations of NB techniques prove that AODE is significantly better than other NB techniques in terms of zero-one loss reduction [5]. Since its introduction in 2005, AODE has enjoyed considerable popularity because of its capability to improve the accuracy of NB [5].Another strategy to remedy violations of the attribute independence assumption is to eliminate highly correlated attributes. Backward sequential elimination (BSE) [6] uses a simple heuristic wrapper approach that selects a subset of the available attributes to minimize zero-one loss on the training set. BSE is effective especially for data sets with highly correlated attributes. Forward sequential selection (FSS) [7] uses the reverse search direction to BSE. However, both FSS and BSE have high computational overheads, especially on learning algorithms with high classification time complexity, because they apply the algorithms repeatedly until no accuracy improvement occurs. Subsumption resolution (SR) [8] identifies pairs of attribute values, such that one appears to subsume (be a generalization of) the other and deletes the generalization. Near-subsumption resolution (NSR) [8] is a variant of SR; it extends SR by deleting not only generalizations but also near-generalizations. For different instances, SR and NSR may find different attributes to remove, making them much more flexible than BSE and FSS. Since generalization mainly deals with pairs of attribute, there is no solution for more complicated situation and loop relationship. In this paper, we present a new type of seminaive Bayesian operation, which selects parent (SP) attributes by building maximum weighted spanning tree and removes children (RC) attributes by functional dependency and canonical cover analysis. Thus this algorithm has the advantages of BSE, FSS, and SR.The remainder of the paper is organized as follows. Section2 introduces the basic ideas of NB, AODE, and related background theory. Section 3 introduces the SP and RC techniques for attribute selection and elimination with AODE and presents the theoretical justification. Section 4 shows the experimental results on UCI data sets and a detailed analysis of different attribute selection techniques. The final section concludes the paper.


## 2. Related Research Work

### 2.1. NB and AODE

The aim of supervised learning is to predict from a training set the class of a testing instancex
=
{
x
1
,
…
,
x
n
}, where x
i is the value of the ith attribute. We estimate the conditional probability of P
(
y
∣
x
) by selecting arg
max
⁡
y
P
(
y
∣
x
), where y
∈
{
c
1
,
…
,
c
k
} are the k classes. From Bayes theorem, we have
(1)
P
(
y
x
)
=
P
(
y
,
x
)
P
(
x
)
∝
P
(
y
,
x
)
∝
P
(
x
∣
y
)
P
(
y
)
.NB simplified the estimation ofP
(
x
|
y
) by conditional independence assumption
(2)
P
(
x
y
)
=
∏
i
=
1
n
P
(
x
i
∣
y
)
.Then, the following equation is often calculated in practice rather than (1):
(3)
P
(
y
x
)
∝
P
(
y
)
∏
i
=
1
n
P
(
x
i
∣
y
)
.The corresponding network structure is depicted in Figure1(a). One advantage of NB is avoiding model selection because selecting between alternative models can be expected to increase variance and allow a learning system to overfit the training data [3]. In consequence, changes in the training data will not lead to any change in NB, which leads in turn to lower variance [4]. By contrast, the underlying conditional probability tables will change correspondingly for those approaches (e.g., NB) with a definite model form when the training data changes, resulting in relatively gradual changes in the pattern of classification.The network structure of NB and AODE.
(a)
(b)Numerous techniques have sought to enhance the accuracy of NB by relaxing the conditional independence assumption while attaining the efficiency and efficacy of one-dependence classifiers. Among them, averaged one-dependence estimator (AODE) [3, 4] utilizes a restricted class of one-dependence estimators (ODEs) and aggregates the predictions of all qualified estimators within this class. A superparent attribute (e.g., x
i) is selected as the parent of all the other attributes in each ODE, since
(4)
P
(
x
,
y
)
=
P
(
x
1
,
…
,
x
i
,
…
,
x
n
,
y
)
=
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
,
x
i
,
y
)
=
P
(
x
i
,
y
)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
.Independence is assumed among the remaining attributes givenx
i and y. Consider
(5)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
x
i
,
y
)
=
∏
j
=
1
,
j
≠
i
n
P
(
x
j
∣
x
i
,
y
)
.Hence,x can be classified by selecting
(6)
arg
max
⁡
y
P
(
x
,
y
)
=
arg
max
⁡
y
P
(
x
i
,
y
)
∏
j
=
1
,
j
≠
i
n
‍
P
(
x
j
∣
x
i
,
y
)
.The corresponding network structure of AODE is depicted in Figure1(b). AODE maintains the robustness and much of the efficiency of NB and at the same time exhibits significantly higher classification accuracy for many data sets. Therefore, it has the potential to be a valuable substitute for NB over a considerable range of classification tasks.


### 2.2. Related Background Theory

In the following discussion, Greek letters(
α
,
β
,
γ
,
…
) are used to denote sets of attributes. Lowercase letters represent the specific values used by corresponding attributes (e.g., x
i represents X
i
=
x
i). P
(
·
) denotes the probability and P
^
(
·
) denotes the probability estimation of P
(
·
). Given a relation R (in a relational database), attribute Y of R is functionally dependent on attribute X of R and X of R functionally determines Y of R (in symbols X
→
Y). Armstrong (1974) proposed in [9] a set of axioms (or, more precisely, inference rules) to infer all the functional dependencies (FDs) on a relational database, which represent the expert knowledge of the organizational data and their interrelationships. The axioms mainly include the following rules.(i)
Augmentation rule: ifα
→
β holds and γ is a set of attributes, then α
γ
→
β
γ.
(ii)
Transitivity rule: ifα
→
β holds and β
→
γ holds, then α
→
γ.
(iii)
Union rule: ifα
→
β holds and α
→
γ holds, then α
→
β
γ.
(iv)
Decomposition rule: ifα
→
β
γ holds, then α
→
β, α
→
γ.
(v)
Pseudotransitivity rule: ifα
→
β holds and γ
β
→
δ holds, then α
γ
→
δ holds.Based on the aforementioned rules, we use the FD rules of probability in [10, 11] to link FD and probability theory. The following rules are included in the FD-probability theory link.(i)
Representation equivalence rule of probability: suppose data setS consists of two attribute sets {
α
,
β
} and β can be inferred by α; that is, the FD α
→
β holds; then the following joint probability distribution holds:
(7)
P
(
α
)
=
P
(
α
,
β
)
.
(ii)
Augmentation rule of probability: ifα
→
β holds and γ is a set of attributes, then the following joint probability distribution holds:
(8)
P
(
α
,
γ
)
=
P
(
α
,
β
,
γ
)
.
(iii)
Transitivity rule of probability: ifα
→
β and β
→
γ hold, then the following joint probability distribution holds:
(9)
P
(
α
)
=
P
(
α
,
γ
)
.
(iv)
Pseudotransitivity rule of probability: ifα
→
β and γ
β
→
δ hold, then the following joint probability distribution holds:
(10)
P
(
α
,
γ
)
=
P
(
α
,
γ
,
δ
)
.In the 1940s, Claude E. Shannon introduced information theory, the theoretical foundation of modern digital communication. Although Shannon was principally concerned with the problem of electronic communications, the theory has much broader applicability. Two commonly used definitions of information theory are described as follows.Definition 1.
Mutual informationI
(
Y
;
X
) measures the information quantity that is transferred between attributes X and Y:
(11)
I
(
Y
;
X
)
=
∑
x
∈
X
‍
∑
y
∈
Y
‍
P
(
x
,
y
)
log
⁡
2
⁡
P
(
x
,
y
)
P
(
x
)
P
(
y
)
,
where P
(
x
,
y
) is the joint probability distribution function of X and Y, and P
(
x
) and P
(
y
) are the marginal probability distribution functions of X and Y, respectively. High mutual information indicates a great relationship between X and Y; and zero mutual information between two random variables means they are independent.Definition 2.
Conditional mutual information (CMI)I
(
X
1
;
X
2
∣
Y
) measures the dependence between each pair of attributes {
X
1
,
X
2
} given Y, which is shown as follows:
(12)
I
(
X
1
;
X
2
∣
Y
)
=

∑
y
∈
Y
‍
P
(
y
)
∑
x
1
∈
X
1
‍
∑
x
2
∈
X
2
‍
P
(
x
1
,
x
2
∣
y
)
m
m
m
m
m
c
m
f
f
f
f
m
×
log
⁡
2
P
(
x
1
,
x
2
∣
y
)
P
(
x
1
∣
y
)
P
(
x
2
∣
y
)
.Theorem 3.
Given instancex
=
{
x
1
,
…
,
x
n
} and class label y, if there exists FD x
2
→
x
1, then x
1 is extraneous for classification. That means P
(
y
∣
x
)
=
P
(
y
∣
x
⇀
x
1
), where “⇀” represents the set difference.Proof.
By applying the augmentation rule and the decomposition rule, fromx
2
→
x
1 we can obtain
(13)
{
x
⇀
x
1
}
⟶
x
1
,
{
x
⇀
x
1
,
y
}
⟶
x
1
.
By applying the representation equivalence rule of probability and the augmentation rule of probability, we can obtain(14)
P
(
x
)
=
P
(
x
⇀
x
1
)
,
P
(
x
,
y
)
=
P
(
x
⇀
x
1
,
y
)
.
Then,(15)
P
(
y
∣
x
)
=
P
(
x
,
y
)
P
(
x
)
=
P
(
x
⇀
x
1
,
y
)
P
(
x
⇀
x
1
)
=
P
(
y
∣
x
⇀
x
1
)
.
We can also prove Theorem3 from the viewpoint of information theory, since
(16)
I
(
Y
;
X
)
=
-
∑
x
∈
X
‍
∑
y
∈
Y
‍
log
⁡
2
P
(
x
,
y
)
P
(
x
,
y
)
P
(
x
)
P
(
y
)
=
-
∑
x
⇀
x
1
∈
X
⇀
X
1
‍
∑
y
∈
Y
‍
log
⁡
2
P
(
x
⇀
x
1
,
y
)
f
f
f
f
f
f
f
×
P
(
x
⇀
x
1
,
y
)
P
(
x
⇀
x
1
)
P
(
y
)
=
I
(
Y
;
X
⇀
X
1
)
.
End of the proof.As for AODE, (4) will turn to be
(17)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
=
P
(
x
2
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
=
∏
j
=
2
,
j
≠
i
n
‍
P
(
x
j
∣
x
i
,
y
)
.Thus, if FDx
2
→
x
1 is neglected, the contribution of x
1 to classification will be calculated repeatedly for each ODE and the classification result may be wrong.


## 2.1. NB and AODE

The aim of supervised learning is to predict from a training set the class of a testing instancex
=
{
x
1
,
…
,
x
n
}, where x
i is the value of the ith attribute. We estimate the conditional probability of P
(
y
∣
x
) by selecting arg
max
⁡
y
P
(
y
∣
x
), where y
∈
{
c
1
,
…
,
c
k
} are the k classes. From Bayes theorem, we have
(1)
P
(
y
x
)
=
P
(
y
,
x
)
P
(
x
)
∝
P
(
y
,
x
)
∝
P
(
x
∣
y
)
P
(
y
)
.NB simplified the estimation ofP
(
x
|
y
) by conditional independence assumption
(2)
P
(
x
y
)
=
∏
i
=
1
n
P
(
x
i
∣
y
)
.Then, the following equation is often calculated in practice rather than (1):
(3)
P
(
y
x
)
∝
P
(
y
)
∏
i
=
1
n
P
(
x
i
∣
y
)
.The corresponding network structure is depicted in Figure1(a). One advantage of NB is avoiding model selection because selecting between alternative models can be expected to increase variance and allow a learning system to overfit the training data [3]. In consequence, changes in the training data will not lead to any change in NB, which leads in turn to lower variance [4]. By contrast, the underlying conditional probability tables will change correspondingly for those approaches (e.g., NB) with a definite model form when the training data changes, resulting in relatively gradual changes in the pattern of classification.The network structure of NB and AODE.
(a)
(b)Numerous techniques have sought to enhance the accuracy of NB by relaxing the conditional independence assumption while attaining the efficiency and efficacy of one-dependence classifiers. Among them, averaged one-dependence estimator (AODE) [3, 4] utilizes a restricted class of one-dependence estimators (ODEs) and aggregates the predictions of all qualified estimators within this class. A superparent attribute (e.g., x
i) is selected as the parent of all the other attributes in each ODE, since
(4)
P
(
x
,
y
)
=
P
(
x
1
,
…
,
x
i
,
…
,
x
n
,
y
)
=
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
,
x
i
,
y
)
=
P
(
x
i
,
y
)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
.Independence is assumed among the remaining attributes givenx
i and y. Consider
(5)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
x
i
,
y
)
=
∏
j
=
1
,
j
≠
i
n
P
(
x
j
∣
x
i
,
y
)
.Hence,x can be classified by selecting
(6)
arg
max
⁡
y
P
(
x
,
y
)
=
arg
max
⁡
y
P
(
x
i
,
y
)
∏
j
=
1
,
j
≠
i
n
‍
P
(
x
j
∣
x
i
,
y
)
.The corresponding network structure of AODE is depicted in Figure1(b). AODE maintains the robustness and much of the efficiency of NB and at the same time exhibits significantly higher classification accuracy for many data sets. Therefore, it has the potential to be a valuable substitute for NB over a considerable range of classification tasks.


## 2.2. Related Background Theory

In the following discussion, Greek letters(
α
,
β
,
γ
,
…
) are used to denote sets of attributes. Lowercase letters represent the specific values used by corresponding attributes (e.g., x
i represents X
i
=
x
i). P
(
·
) denotes the probability and P
^
(
·
) denotes the probability estimation of P
(
·
). Given a relation R (in a relational database), attribute Y of R is functionally dependent on attribute X of R and X of R functionally determines Y of R (in symbols X
→
Y). Armstrong (1974) proposed in [9] a set of axioms (or, more precisely, inference rules) to infer all the functional dependencies (FDs) on a relational database, which represent the expert knowledge of the organizational data and their interrelationships. The axioms mainly include the following rules.(i)
Augmentation rule: ifα
→
β holds and γ is a set of attributes, then α
γ
→
β
γ.
(ii)
Transitivity rule: ifα
→
β holds and β
→
γ holds, then α
→
γ.
(iii)
Union rule: ifα
→
β holds and α
→
γ holds, then α
→
β
γ.
(iv)
Decomposition rule: ifα
→
β
γ holds, then α
→
β, α
→
γ.
(v)
Pseudotransitivity rule: ifα
→
β holds and γ
β
→
δ holds, then α
γ
→
δ holds.Based on the aforementioned rules, we use the FD rules of probability in [10, 11] to link FD and probability theory. The following rules are included in the FD-probability theory link.(i)
Representation equivalence rule of probability: suppose data setS consists of two attribute sets {
α
,
β
} and β can be inferred by α; that is, the FD α
→
β holds; then the following joint probability distribution holds:
(7)
P
(
α
)
=
P
(
α
,
β
)
.
(ii)
Augmentation rule of probability: ifα
→
β holds and γ is a set of attributes, then the following joint probability distribution holds:
(8)
P
(
α
,
γ
)
=
P
(
α
,
β
,
γ
)
.
(iii)
Transitivity rule of probability: ifα
→
β and β
→
γ hold, then the following joint probability distribution holds:
(9)
P
(
α
)
=
P
(
α
,
γ
)
.
(iv)
Pseudotransitivity rule of probability: ifα
→
β and γ
β
→
δ hold, then the following joint probability distribution holds:
(10)
P
(
α
,
γ
)
=
P
(
α
,
γ
,
δ
)
.In the 1940s, Claude E. Shannon introduced information theory, the theoretical foundation of modern digital communication. Although Shannon was principally concerned with the problem of electronic communications, the theory has much broader applicability. Two commonly used definitions of information theory are described as follows.Definition 1.
Mutual informationI
(
Y
;
X
) measures the information quantity that is transferred between attributes X and Y:
(11)
I
(
Y
;
X
)
=
∑
x
∈
X
‍
∑
y
∈
Y
‍
P
(
x
,
y
)
log
⁡
2
⁡
P
(
x
,
y
)
P
(
x
)
P
(
y
)
,
where P
(
x
,
y
) is the joint probability distribution function of X and Y, and P
(
x
) and P
(
y
) are the marginal probability distribution functions of X and Y, respectively. High mutual information indicates a great relationship between X and Y; and zero mutual information between two random variables means they are independent.Definition 2.
Conditional mutual information (CMI)I
(
X
1
;
X
2
∣
Y
) measures the dependence between each pair of attributes {
X
1
,
X
2
} given Y, which is shown as follows:
(12)
I
(
X
1
;
X
2
∣
Y
)
=

∑
y
∈
Y
‍
P
(
y
)
∑
x
1
∈
X
1
‍
∑
x
2
∈
X
2
‍
P
(
x
1
,
x
2
∣
y
)
m
m
m
m
m
c
m
f
f
f
f
m
×
log
⁡
2
P
(
x
1
,
x
2
∣
y
)
P
(
x
1
∣
y
)
P
(
x
2
∣
y
)
.Theorem 3.
Given instancex
=
{
x
1
,
…
,
x
n
} and class label y, if there exists FD x
2
→
x
1, then x
1 is extraneous for classification. That means P
(
y
∣
x
)
=
P
(
y
∣
x
⇀
x
1
), where “⇀” represents the set difference.Proof.
By applying the augmentation rule and the decomposition rule, fromx
2
→
x
1 we can obtain
(13)
{
x
⇀
x
1
}
⟶
x
1
,
{
x
⇀
x
1
,
y
}
⟶
x
1
.
By applying the representation equivalence rule of probability and the augmentation rule of probability, we can obtain(14)
P
(
x
)
=
P
(
x
⇀
x
1
)
,
P
(
x
,
y
)
=
P
(
x
⇀
x
1
,
y
)
.
Then,(15)
P
(
y
∣
x
)
=
P
(
x
,
y
)
P
(
x
)
=
P
(
x
⇀
x
1
,
y
)
P
(
x
⇀
x
1
)
=
P
(
y
∣
x
⇀
x
1
)
.
We can also prove Theorem3 from the viewpoint of information theory, since
(16)
I
(
Y
;
X
)
=
-
∑
x
∈
X
‍
∑
y
∈
Y
‍
log
⁡
2
P
(
x
,
y
)
P
(
x
,
y
)
P
(
x
)
P
(
y
)
=
-
∑
x
⇀
x
1
∈
X
⇀
X
1
‍
∑
y
∈
Y
‍
log
⁡
2
P
(
x
⇀
x
1
,
y
)
f
f
f
f
f
f
f
×
P
(
x
⇀
x
1
,
y
)
P
(
x
⇀
x
1
)
P
(
y
)
=
I
(
Y
;
X
⇀
X
1
)
.
End of the proof.As for AODE, (4) will turn to be
(17)
P
(
x
1
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
=
P
(
x
2
,
…
,
x
i
-
1
,
x
i
+
1
,
…
,
x
n
∣
x
i
,
y
)
=
∏
j
=
2
,
j
≠
i
n
‍
P
(
x
j
∣
x
i
,
y
)
.Thus, if FDx
2
→
x
1 is neglected, the contribution of x
1 to classification will be calculated repeatedly for each ODE and the classification result may be wrong.


## 3. Attribute Selection and Elimination

AODE makes a weaker attribute conditional independence assumption than that of NB. It selects one attribute as superparent in turn for each ODE submodel, and the other attributes are supposed to be conditionally independent. Previous studies have demonstrated that AODE has a considerably lower bias than that of NB with moderate increases in variance and time complexity [5]. The same attribute may play different roles (either parent or child) in different ODE submodels. In the following discussion, we will repair harmful interdependencies from two viewpoints: (
1
) select parent (p) attributes (SP) by building maximum weighted spanning tree; (
2
) remove children (c) attributes (RC) by functional dependency analysis.


### 3.1. How to Select Parent Attributes

SP selects the branch nodes as thep attributes from maximum weighted spanning tree (MST), the learning procedure of which can be summarized as follows.(1)
Use CMI to measure the weights of edges between each pair of attributes. Sort the edges into descending order by CMI. LetT be the set of edges comprising the MST. Set T
=
{
Φ
}.
(2)
Find the edge with the greatest weight and add this edge toT if and only if it does not form a cycle in T. If no remaining edges exist, exit and report MST to be disconnected.
(3)
IfT has n
-
1 edges (where n is the number of vertices in MST) stop and output T. Otherwise go to step (
2
).Thep attributes selected must satisfy the criterion that they either appear as the branch nodes in MST or as the leaf nodes but with stronger relationship with other attributes. Figures 2(a), 2(b), and 2(c) show the original spanning tree, procedure of selecting edges, and final MST, respectively. As shown in Figure 2(c), attributes ②, ③, and ⑥ are branch nodes and can be used as p attributes. In addition, ①, ④, and ⑤ are leaf nodes with corresponding CMIs of 7, 6, and 2, respectively. The CMIs are then sorted into descending order. In this paper, if the sum of CMIs of the first k leaf nodes is greater than 85% of the sum of CMIs of all leaf nodes, we suppose that they represent the most important marginal relationships and can also be selected as p attributes. For example, since
(18)
7
+
6
7
+
6
+
2
=
86.7
%
>
85
%
,
then ① and ④ can be used as p attributes. This criterion helps to ensure that strong, and only strong, relationships among attributes will be retained. By contrast, AODE [4] indiscriminately uses each attribute as superparent even if some attributes may be independent of others. Besides, SP supports incremental learning because it may reselect the subset of attributes when a new training instance becomes available.Example of building MST.
(a)
(b)
(c)At training time SP needs only to form the tables of joint attribute value, class frequencies to estimate the probabilitiesP
^
(
y
), P
^
(
y
,
x
i
), and P
^
(
y
,
x
i
,
x
j
), which are required for estimating P
^
(
x
i
∣
y
), P
^
(
x
i
,
x
j
∣
y
), and P
^
(
x
j
∣
y
,
x
i
) in turn. Calculating the estimates requires a simple scan through the data, an operation of time complexity O
(
t
n
2
), where t is the number of training instances and n is the number of attributes. To build maximum weighted spanning tree, SP must first calculate the CMI, requiring consideration for each pair of attributes, every pairwise combination of their respective values in conjunction with each class value. The time complexity to build a MST is O
(
n
2
log
⁡
n
). The resulting time complexity is O
(
t
n
2
+
k
(
n
v
)
2
+
n
2
log
⁡
n
) and space complexity is O
(
k
(
n
v
)
2
), where k is the number of classes and v is the average number of values for an attribute. At classification time SP needs only to store the probability tables, space complexity O
(
k
(
n
v
)
2
). This compression over the table required at training time is achieved by storing probability estimates for each attribute value conditioned by the parent selected for that attribute and the class. The time complexity of classifying a single instance is O
(
k
n
2
).


### 3.2. How to Eliminate Children Attributes

Kohavi and Wolpert [12] presented a bias-variance decomposition of expected misclassification rate, which is a powerful tool from sampling theory statistics for analyzing supervised learning scenarios. Suppose y and y
^ are the true class label and that class generated by a learning algorithm, respectively; the zero-one loss function is defined as
(19)
ξ
(
y
,
y
^
)
=
1
-
δ
(
y
,
y
^
)
,
where δ
(
y
,
y
^
)
=
1 if y
^
=
y and 0 otherwise. The bias term measures the squared difference between the average output of the target and the algorithm. This term is defined as follows:
(20)
bias
=
1
2
∑
y
^
,
y
∈
Y
‍
[
P
(
y
^
∣
x
)
-
P
(
y
∣
x
)
]
2
,
where x is the combination of any attribute value. The variance term is a real valued nonnegative quantity and equals zero for an algorithm that always makes the same guess regardless of the training set. The variance increases as the algorithm becomes more sensitive to changes in the training set. It is defined as follows:
(21)
variance
=
1
2
[
1
-
∑
y
^
∈
Y
P
(
y
^
∣
x
)
2
]
.Moore and McCabe [13] illustrated bias and variance through shooting arrows at a target, as described in Figure 3. The perfect model can be regarded as the bull’s eye on a target and the learned classifier as an arrow fired at the bull’s eye. Bias and variance describe what happens when an archer fires many arrows at the target. Bias means that the aim is off and the arrows land consistently off the bull’s eye in the same direction. Variance means that the arrows are scattered. Large variance means that repeated shots are widely scattered on the target. They do not give similar results but differ widely among themselves.Bias and variance in shooting arrows at a target.
(a)
High bias, low variance
(b)
Low bias, high variance
(c)
High bias, high variance
(d)
Low bias, low varianceIt is reported that removing redundant children attributes from within ODEs can help to decrease both bias and zero-one loss [3, 14]. Subsumption resolution (SR) [8] identifies pairs of attribute values such that one can replace the other. Deleting x
j from a Bayesian classifier should not be harmful when x
j is a generalization of x
i; that is, P
(
x
j
∣
x
i
)
=
1.0. Only the attribute value x
i is necessary for classification; that is, P
(
y
∣
x
1
,
…
,
x
n
)
=
P
(
y
|
x
1
,
…
,
x
j
-
1
,
x
j
+
1
,
…
,
x
n
). Such deletion may improve a classifier’s estimate if it makes unwarranted assumptions about the relationship of x
j to the other attributes when estimating intermediate probability values, such as NB’s independence assumption. Since P
(
x
j
|
x
i
)
=
1.0 can be represented as FD: x
i
→
x
j, SR and FD have the same meaning but from different viewpoints.SR mainly considers pair relationship of one-one. However, four basic relationships exist in the real world: one-one, one-many, many-many, and many-one. These four relationships can be grouped into two sets: one-one and many-one. Thus, SR cannot resolve interdependencies when a loop appears in the many-one relationship. The data presented in Table1 shows a loop example with four attributes {
X
1
,
X
2
,
X
3
,
X
4
} and class label Y. For the first instance {
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
}, suppose {
X
2
=
b
1
}, {
X
4
=
d
1
}, and {
X
1
=
a
1
} are generalizations of {
X
1
=
a
1
}, {
X
2
=
b
1
,
X
3
=
c
1
}, and {
X
4
=
d
1
}, respectively. The loop relationship is described in Figure 4(a), where “→” represents the one-one relationship and “⇢” represents the many-one relationship. After SR, only attributes X
3 are used for classification and NB will misclassify the first instance as “Y
=
y
2”, even though it occurs in the training data. For different testing instances, different correlated attributes will be deleted. These instances will be illustrated from the viewpoint of FD. {
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
} can be replaced by three FDs:(1)
{
X
1
=
a
1
}
→
{
X
2
=
b
1
},
(2)
{
X
2
=
b
1
,
X
3
=
c
1
}
→
{
X
4
=
d
1
},
(3)
{
X
4
=
d
1
}
→
{
X
1
=
a
1
}.Table 1
A loop relationship example.
X
1
X
2
X
3
X
4
Y
a
1
b
1
c
1
d
1
y
1
a
2
b
2
c
1
d
2
y
2
a
1
b
1
c
2
d
1
y
2
a
2
b
1
c
2
d
3
y
1
a
2
b
2
c
1
d
3
y
2Loop relationship between attributes of training instance.
(a)
(b)
(c)The following results can be generated. We can obtain{
X
1
=
a
1
}
→
{
X
1
=
a
1
,
X
2
=
b
1
} from FD (
1
) by applying union rule. As shown in Figure 4(b), X
2 disappears and the arc that once connects X
2 and X
4 now extends to connect X
1 and X
4.We can obtain{
X
1
=
a
1
,
X
3
=
c
1
}
→
{
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
} from FD (
2
) by applying augmentation rule. As Figure 4(c) shows, the arc from X
4 to X
1 is removed to avoid a loop relationship. Thus, we can infer and obtain the other two attribute values from two attribute values of {
X
1
=
a
1
,
X
3
=
c
1
}. Correspondingly the first instance will be correctly classified.It should be noted that SP selectsp attributes from the probabilistic viewpoint by calculating CMI while RC selects c attributes from the logical viewpoint by inferring FDs from the training data. That is, the learning procedure of SP + RC is divided into two parts; SP roughly describes the basic structure of each submodel which uses p attributes as superparents and other attributes as the children; and for different instances, RC further refines the model by deleting redundant children attributes and thus makes the final model much more flexible and robust. Suppose an extreme instance, the CMIs of all attributes are all small and equal, and then all the attributes will be selected as p attributes. The structure will be just the same as AODE after applying SP. But for different testing instances, different FDs can help to make each submodel express the key dependencies. For example, suppose FD
1
=
{
x
1
→
x
2
} holds for instance-1 and FD
2
=
{
x
2
→
x
3
} holds for instance-2; Figures 5, 6, and 7 show the original AODE structure after applying SP and corresponding structures for instance-1 and instance-2, respectively.Figure 5
Original network structures of AODE submodels.Figure 6
Network structures corresponding to instance-1.Figure 7
Network structures corresponding to instance-2.Discovering FD from existing databases is an important issue. This issue has long been investigated and has been recently addressed with a data mining viewpoint in a novel and efficient way. Rather than exhibiting the set of all functional dependencies which hold in a relation, related work aims to discover a smaller cover equivalent to this set. This problem is known as FD inference. Association rules can be used to discover the relationships and potential associations of items or attributes among huge data. These rules can be effective in uncovering unknown relationships, thereby providing results that can be the basis of forecast and decision. They have proven to be useful tools for an enterprise as they strive to improve their competitiveness and profitability.


## 3.1. How to Select Parent Attributes

SP selects the branch nodes as thep attributes from maximum weighted spanning tree (MST), the learning procedure of which can be summarized as follows.(1)
Use CMI to measure the weights of edges between each pair of attributes. Sort the edges into descending order by CMI. LetT be the set of edges comprising the MST. Set T
=
{
Φ
}.
(2)
Find the edge with the greatest weight and add this edge toT if and only if it does not form a cycle in T. If no remaining edges exist, exit and report MST to be disconnected.
(3)
IfT has n
-
1 edges (where n is the number of vertices in MST) stop and output T. Otherwise go to step (
2
).Thep attributes selected must satisfy the criterion that they either appear as the branch nodes in MST or as the leaf nodes but with stronger relationship with other attributes. Figures 2(a), 2(b), and 2(c) show the original spanning tree, procedure of selecting edges, and final MST, respectively. As shown in Figure 2(c), attributes ②, ③, and ⑥ are branch nodes and can be used as p attributes. In addition, ①, ④, and ⑤ are leaf nodes with corresponding CMIs of 7, 6, and 2, respectively. The CMIs are then sorted into descending order. In this paper, if the sum of CMIs of the first k leaf nodes is greater than 85% of the sum of CMIs of all leaf nodes, we suppose that they represent the most important marginal relationships and can also be selected as p attributes. For example, since
(18)
7
+
6
7
+
6
+
2
=
86.7
%
>
85
%
,
then ① and ④ can be used as p attributes. This criterion helps to ensure that strong, and only strong, relationships among attributes will be retained. By contrast, AODE [4] indiscriminately uses each attribute as superparent even if some attributes may be independent of others. Besides, SP supports incremental learning because it may reselect the subset of attributes when a new training instance becomes available.Example of building MST.
(a)
(b)
(c)At training time SP needs only to form the tables of joint attribute value, class frequencies to estimate the probabilitiesP
^
(
y
), P
^
(
y
,
x
i
), and P
^
(
y
,
x
i
,
x
j
), which are required for estimating P
^
(
x
i
∣
y
), P
^
(
x
i
,
x
j
∣
y
), and P
^
(
x
j
∣
y
,
x
i
) in turn. Calculating the estimates requires a simple scan through the data, an operation of time complexity O
(
t
n
2
), where t is the number of training instances and n is the number of attributes. To build maximum weighted spanning tree, SP must first calculate the CMI, requiring consideration for each pair of attributes, every pairwise combination of their respective values in conjunction with each class value. The time complexity to build a MST is O
(
n
2
log
⁡
n
). The resulting time complexity is O
(
t
n
2
+
k
(
n
v
)
2
+
n
2
log
⁡
n
) and space complexity is O
(
k
(
n
v
)
2
), where k is the number of classes and v is the average number of values for an attribute. At classification time SP needs only to store the probability tables, space complexity O
(
k
(
n
v
)
2
). This compression over the table required at training time is achieved by storing probability estimates for each attribute value conditioned by the parent selected for that attribute and the class. The time complexity of classifying a single instance is O
(
k
n
2
).


## 3.2. How to Eliminate Children Attributes

Kohavi and Wolpert [12] presented a bias-variance decomposition of expected misclassification rate, which is a powerful tool from sampling theory statistics for analyzing supervised learning scenarios. Suppose y and y
^ are the true class label and that class generated by a learning algorithm, respectively; the zero-one loss function is defined as
(19)
ξ
(
y
,
y
^
)
=
1
-
δ
(
y
,
y
^
)
,
where δ
(
y
,
y
^
)
=
1 if y
^
=
y and 0 otherwise. The bias term measures the squared difference between the average output of the target and the algorithm. This term is defined as follows:
(20)
bias
=
1
2
∑
y
^
,
y
∈
Y
‍
[
P
(
y
^
∣
x
)
-
P
(
y
∣
x
)
]
2
,
where x is the combination of any attribute value. The variance term is a real valued nonnegative quantity and equals zero for an algorithm that always makes the same guess regardless of the training set. The variance increases as the algorithm becomes more sensitive to changes in the training set. It is defined as follows:
(21)
variance
=
1
2
[
1
-
∑
y
^
∈
Y
P
(
y
^
∣
x
)
2
]
.Moore and McCabe [13] illustrated bias and variance through shooting arrows at a target, as described in Figure 3. The perfect model can be regarded as the bull’s eye on a target and the learned classifier as an arrow fired at the bull’s eye. Bias and variance describe what happens when an archer fires many arrows at the target. Bias means that the aim is off and the arrows land consistently off the bull’s eye in the same direction. Variance means that the arrows are scattered. Large variance means that repeated shots are widely scattered on the target. They do not give similar results but differ widely among themselves.Bias and variance in shooting arrows at a target.
(a)
High bias, low variance
(b)
Low bias, high variance
(c)
High bias, high variance
(d)
Low bias, low varianceIt is reported that removing redundant children attributes from within ODEs can help to decrease both bias and zero-one loss [3, 14]. Subsumption resolution (SR) [8] identifies pairs of attribute values such that one can replace the other. Deleting x
j from a Bayesian classifier should not be harmful when x
j is a generalization of x
i; that is, P
(
x
j
∣
x
i
)
=
1.0. Only the attribute value x
i is necessary for classification; that is, P
(
y
∣
x
1
,
…
,
x
n
)
=
P
(
y
|
x
1
,
…
,
x
j
-
1
,
x
j
+
1
,
…
,
x
n
). Such deletion may improve a classifier’s estimate if it makes unwarranted assumptions about the relationship of x
j to the other attributes when estimating intermediate probability values, such as NB’s independence assumption. Since P
(
x
j
|
x
i
)
=
1.0 can be represented as FD: x
i
→
x
j, SR and FD have the same meaning but from different viewpoints.SR mainly considers pair relationship of one-one. However, four basic relationships exist in the real world: one-one, one-many, many-many, and many-one. These four relationships can be grouped into two sets: one-one and many-one. Thus, SR cannot resolve interdependencies when a loop appears in the many-one relationship. The data presented in Table1 shows a loop example with four attributes {
X
1
,
X
2
,
X
3
,
X
4
} and class label Y. For the first instance {
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
}, suppose {
X
2
=
b
1
}, {
X
4
=
d
1
}, and {
X
1
=
a
1
} are generalizations of {
X
1
=
a
1
}, {
X
2
=
b
1
,
X
3
=
c
1
}, and {
X
4
=
d
1
}, respectively. The loop relationship is described in Figure 4(a), where “→” represents the one-one relationship and “⇢” represents the many-one relationship. After SR, only attributes X
3 are used for classification and NB will misclassify the first instance as “Y
=
y
2”, even though it occurs in the training data. For different testing instances, different correlated attributes will be deleted. These instances will be illustrated from the viewpoint of FD. {
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
} can be replaced by three FDs:(1)
{
X
1
=
a
1
}
→
{
X
2
=
b
1
},
(2)
{
X
2
=
b
1
,
X
3
=
c
1
}
→
{
X
4
=
d
1
},
(3)
{
X
4
=
d
1
}
→
{
X
1
=
a
1
}.Table 1
A loop relationship example.
X
1
X
2
X
3
X
4
Y
a
1
b
1
c
1
d
1
y
1
a
2
b
2
c
1
d
2
y
2
a
1
b
1
c
2
d
1
y
2
a
2
b
1
c
2
d
3
y
1
a
2
b
2
c
1
d
3
y
2Loop relationship between attributes of training instance.
(a)
(b)
(c)The following results can be generated. We can obtain{
X
1
=
a
1
}
→
{
X
1
=
a
1
,
X
2
=
b
1
} from FD (
1
) by applying union rule. As shown in Figure 4(b), X
2 disappears and the arc that once connects X
2 and X
4 now extends to connect X
1 and X
4.We can obtain{
X
1
=
a
1
,
X
3
=
c
1
}
→
{
X
1
=
a
1
,
X
2
=
b
1
,
X
3
=
c
1
,
X
4
=
d
1
} from FD (
2
) by applying augmentation rule. As Figure 4(c) shows, the arc from X
4 to X
1 is removed to avoid a loop relationship. Thus, we can infer and obtain the other two attribute values from two attribute values of {
X
1
=
a
1
,
X
3
=
c
1
}. Correspondingly the first instance will be correctly classified.It should be noted that SP selectsp attributes from the probabilistic viewpoint by calculating CMI while RC selects c attributes from the logical viewpoint by inferring FDs from the training data. That is, the learning procedure of SP + RC is divided into two parts; SP roughly describes the basic structure of each submodel which uses p attributes as superparents and other attributes as the children; and for different instances, RC further refines the model by deleting redundant children attributes and thus makes the final model much more flexible and robust. Suppose an extreme instance, the CMIs of all attributes are all small and equal, and then all the attributes will be selected as p attributes. The structure will be just the same as AODE after applying SP. But for different testing instances, different FDs can help to make each submodel express the key dependencies. For example, suppose FD
1
=
{
x
1
→
x
2
} holds for instance-1 and FD
2
=
{
x
2
→
x
3
} holds for instance-2; Figures 5, 6, and 7 show the original AODE structure after applying SP and corresponding structures for instance-1 and instance-2, respectively.Figure 5
Original network structures of AODE submodels.Figure 6
Network structures corresponding to instance-1.Figure 7
Network structures corresponding to instance-2.Discovering FD from existing databases is an important issue. This issue has long been investigated and has been recently addressed with a data mining viewpoint in a novel and efficient way. Rather than exhibiting the set of all functional dependencies which hold in a relation, related work aims to discover a smaller cover equivalent to this set. This problem is known as FD inference. Association rules can be used to discover the relationships and potential associations of items or attributes among huge data. These rules can be effective in uncovering unknown relationships, thereby providing results that can be the basis of forecast and decision. They have proven to be useful tools for an enterprise as they strive to improve their competitiveness and profitability.


## 4. Experimental Study

We expect AODE with SP and RC to exhibit low zero-one loss and low bias. Thus, we compare the performance of the system with the following attribute selection methods. First isp attribute addition (PAA), which starts with p and c initialized to the empty and full sets, respectively. It adds one p attribute to each ODE at each step. Second is c attribute addition (CAA), which begins with p and c initialized to the full and empty sets, respectively. It adds one c attribute to every ODE at each step. Third is p attribute elimination (PAE), which starts with p and c initialized to the full set and deletes one p attribute from every ODE at each step. Fourth is c attribute elimination (CAE), which deletes one c attribute from every ODE at each step. Fifth and sixth are SR and NSR, respectively.Table2 summarizes the characteristics of each data set, including the numbers of instances, attributes, and classes. Missing values for qualitative attributes are replaced with modes and those for quantitative attributes are replaced with means from the training data. We estimate the base probabilities P
(
y
), P
(
y
,
x
i
), and P
(
y
,
x
i
,
x
j
) using the Laplace estimate as follows [15]:
(22)
P
^
(
y
)
=
F
(
y
)
+
1
K
+
k
,
P
^
(
y
,
x
i
)
=
F
(
y
,
x
i
)
+
1
K
i
+
k
i
,
P
^
(
y
,
x
i
,
x
j
)
=
F
(
y
,
x
i
,
x
j
)
+
1
K
i
j
+
k
i
j
,
where F
(
·
) is the frequency with which a combination of terms appears in the training data, K is the number of training instances for which the class value is known, K
i is the number of training instances for which both the class and attribute X
i are known, and K
i
j is the number of training instances for which all of the class and attributes X
i and X
j are known. k is the number of attribute values of class Y, k
i is the number of attribute value combinations of Y and X
i, and k
i
j is the number of attribute value combinations of Y, X
j, and X
i. As NB and AODE require discrete valued data, all data were discretized using minimum description length (MDL) discretization [16]. Classifier is formed from data set and bias, variance, and zero-one loss estimated from the performance of those classifiers on the same data set. Experiments are performed on a dual-processor 3.1 GHz Windows XP computer with 3.16 Gb RAM. All algorithms are applied to the 22 data sets described in Table 2.Table 2
Data sets.
Number
Data set
Number of instances
Attribute
Class
1
Abalone
4177
8
3
2
Adult
48842
14
2
3
Anneal
898
38
6
4
Audio
226
69
24
5
Car
1728
7
4
6
Chess
551
39
2
7
Cleveland
303
13
2
8
Connect 4
67557
42
3
9
Contact lenses
24
4
3
10
Donation
5749132
11
2
11
Heart
303
13
2
12
Hepatitis
155
19
2
13
Hungarian
294
13
2
14
Hypothyroid
3163
25
2
15
Iris
150
4
3
16
kr versus kp
3196
36
2
17
Labor
57
16
2
18
Mushroom
8124
22
2
19
Nursery
12960
8
5
20
Optdigits
5620
64
10
21
Satellite
6435
37
6
22
Shuttle
58000
9
7


### 4.1. Zero-One Loss, Bias, and Variance Results

Table3 presents for each data set the zero-one loss, which is estimated by 50 runs of twofold cross-validation to give an accurate estimation of the average performance of an algorithm. The advantage of this technique is that it uses the full training data as the training set and the testing set. Moreover, every case in the training data is used for the same number of times in each of the roles of training and testing data. Tables 4 and 5 provide the bias and variance results, respectively. The zero-one loss, bias, or variance across multiple data sets provides a gross measure of relative performance.Table 3
Experimental results of zero-one loss.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.512
0.528
0.491
0.519
0.489
0.493
0.396
0.402
Adult
0.212
0.187
0.182
0.158
0.149
0.152
0.137
0.131
Anneal
0.017
0.014
0.013
0.013
0.012
0.011
0.017
0.008
Audio
0.272
0.263
0.247
0.258
0.258
0.217
0.261
0.158
Car
0.236
0.222
0.117
0.212
0.132
0.249
0.127
0.082
Chess
0.147
0.135
0.121
0.129
0.099
0.142
0.128
0.102
Cleveland
0.259
0.262
0.251
0.252
0.247
0.196
0.247
0.178
Connect 4
0.277
0.268
0.289
0.271
0.275
0.267
0.264
0.238
Contact lenses
0.422
0.415
0.409
0.411
0.395
0.445
0.401
0.375
Donation
0.002
0.002
0.002
0.001
0.000
0.001
0.000
0.000
Heart
0.192
0.187
0.182
0.189
0.191
0.197
0.189
0.174
Hepatitis
0.216
0.213
0.209
0.211
0.198
0.208
0.187
0.163
Hungarian
0.193
0.192
0.187
0.190
0.194
0.196
0.217
0.163
Hypothyroid
0.031
0.026
0.021
0.029
0.024
0.021
0.037
0.012
Iris
0.118
0.128
0.125
0.121
0.113
0.102
0.077
0.087
kr  versus kp
0.070
0.071
0.091
0.075
0.068
0.067
0.061
0.072
Labor
0.062
0.051
0.047
0.060
0.059
0.061
0.057
0.053
Mushroom
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
Nursery
0.088
0.091
0.085
0.081
0.085
0.083
0.089
0.072
Optdigits
0.051
0.055
0.053
0.052
0.051
0.049
0.049
0.030
Satellite
0.122
0.119
0.117
0.132
0.112
0.117
0.116
0.114
Shuttle
0.001
0.001
0.001
0.000
0.001
0.001
0.001
0.000Table 4
Experimental results of bias.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.332
0.351
0.327
0.312
0.312
0.307
0.291
0.316
Adult
0.147
0.151
0.148
0.152
0.118
0.120
0.155
0.161
Anneal
0.235
0.187
0.236
0.224
0.211
0.200
0.188
0.179
Audio
0.181
0.201
0.183
0.191
0.184
0.127
0.207
0.212
Car
0.152
0.164
0.155
0.148
0.134
0.138
0.127
0.131
Chess
0.106
0.110
0.092
0.114
0.104
0.112
0.113
0.112
Cleveland
0.071
0.068
0.072
0.069
0.064
0.048
0.052
0.049
Connect 4
0.201
0.165
0.199
0.215
0.192
0.197
0.202
0.204
Contact lenses
0.132
0.129
0.133
0.142
0.154
0.112
0.127
0.126
Donation
0.207
0.219
0.211
0.212
0.214
0.206
0.183
0.179
Heart
0.133
0.131
0.135
0.140
0.159
0.162
0.130
0.132
Hepatitis
0.112
0.120
0.114
0.121
0.113
0.109
0.115
0.113
Hungarian
0.205
0.211
0.206
0.198
0.203
0.211
0.204
0.219
Hypothyroid
0.013
0.013
0.012
0.015
0.009
0.007
0.008
0.008
Iris
0.090
0.088
0.090
0.101
0.094
0.067
0.087
0.085
kr versus kp
0.067
0.070
0.071
0.085
0.069
0.075
0.061
0.058
Labor
0.102
0.099
0.098
0.101
0.104
0.107
0.103
0.099
Mushroom
0.002
0.002
0.002
0.003
0.001
0.002
0.001
0.001
Nursery
0.050
0.049
0.050
0.048
0.052
0.054
0.051
0.049
Optdigits
0.028
0.029
0.028
0.031
0.029
0.028
0.027
0.025
Satellite
0.077
0.075
0.074
0.078
0.080
0.078
0.081
0.078
Shuttle
0.003
0.004
0.003
0.005
0.002
0.003
0.002
0.002Table 5
Experimental results of variance.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.127
0.134
0.142
0.152
0.165
0.161
0.151
0.153
Adult
0.045
0.043
0.046
0.043
0.044
0.042
0.040
0.048
Anneal
0.137
0.146
0.139
0.144
0.152
0.155
0.142
0.145
Audio
0.103
0.101
0.092
0.085
0.082
0.078
0.091
0.087
Car
0.101
0.108
0.118
0.122
0.132
0.133
0.112
0.115
Chess
0.108
0.112
0.103
0.089
0.093
0.088
0.102
0.096
Cleveland
0.152
0.162
0.172
0.179
0.192
0.187
0.207
0.198
Connect 4
0.110
0.105
0.108
0.112
0.110
0.107
0.098
0.092
Contact lenses
0.202
0.213
0.192
0.182
0.178
0.180
0.175
0.172
Donation
0.048
0.054
0.051
0.052
0.064
0.061
0.069
0.062
Heart
0.128
0.133
0.137
0.128
0.142
0.138
0.156
0.152
Hepatitis
0.055
0.058
0.059
0.061
0.063
0.060
0.058
0.053
Hungarian
0.207
0.217
0.196
0.180
0.183
0.177
0.195
0.191
Hypothyroid
0.004
0.004
0.005
0.005
0.004
0.006
0.004
0.004
Iris
0.092
0.096
0.090
0.094
0.092
0.088
0.085
0.081
kr versus kp
0.032
0.032
0.031
0.031
0.023
0.021
0.020
0.020
Labor
0.037
0.034
0.036
0.037
0.038
0.036
0.027
0.024
Mushroom
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
Nursery
0.025
0.026
0.027
0.028
0.029
0.031
0.037
0.032
Optdigits
0.021
0.020
0.021
0.022
0.023
0.023
0.022
0.019
Satellite
0.045
0.047
0.049
0.050
0.049
0.045
0.051
0.048
Shuttle
0.003
0.003
0.004
0.003
0.002
0.002
0.002
0.002The basic relationships among attributes can be clearly observed by building MST. If one attribute is connected with several other attributes, the attribute is supposed to have crossed functional zones and will be selected asp attribute to retain complementarity. If one attribute is connected with only one other attribute, its independence characteristics may be obvious and will be reconsidered by the weight of CMI. Besides, RC helps to detect the situation in which the relationships that hold in MST need to be refined. Table 3 shows that the advantage of SP + RC is significant compared with SR and NSR in terms of zero-one loss. However, SR and NSR have a significant advantage over CAA, PAA, CAE, and PAE. The disappointing performances of CAA, PAA, CAE, and PAE can be ascribed to their susceptibility to getting trapped into poor selections by local minima during the first several additions or deletions.The records in Table4 show that all the c attribute selection algorithms applying SR, NSR, or FDs have a significant advantage in bias over CAE and PAE. In addition, CAE and PAE outperform CAA and PAA. However, comparing SP + RC with SP again does not show obvious difference. This result indicates that SP takes the main role for classification and its effect differs greatly in different data sets. The same result can also be inferred by comparing SP + RC with SR. The training sets containing only 25% of each data set for bias-variance evaluation are small because the data sets are primarily small. The bias of SP + RC decreases as training set size increases because more data will lead to more accurate probability distribution estimates and hence to more appropriate p attribute selection. Of these algorithms, RC, SR, and NSR have the weakest sensitivity to the changes in training data because they can utilize the testing set to infer rules for c attribute elimination. By contrast PAA, PAE, CAA, and CAE perform model selection and their biases differ greatly with different training data.With respect to variance, as Table5 shows, the variance of SP + RC does not show obvious advantage to other algorithms. Low-variance algorithms tend to enjoy an advantage with small data sets, whereas low-bias algorithms tend to enjoy an advantage with large data sets. Cross data set experimental studies of the traditional form presented above also support this hypothesis. The main reason may be that the relationship inferred based on MST may overfit the training data because SP needs to calculate CMI to construct MST. This requires enough instances to achieve precise probability estimation.In the following discussion, canonical cover analysis [17], which can use limited number (e.g., 100) of instances to infer credible FD set, is applied in tandem with functional dependency analysis. Let F
c be a canonical cover for a set of simple FDs and the procedure of computing F
c is described as  in Algorithm 1.Algorithm 1:
F
c = FDs
repeat
Use the union rule to replace any dependencies inF
c of the form
α
1
→
β
1 and α
1
→
β
2 with α
1
→
β
1
β
2.
Find a functional dependencyα
→
β in F
c with an extraneous
attribute either inα or in β.
If an extraneous attribute is found, delete it fromα
→
β in F
c.
until (F
c does not change)The chosen canonical cover is the set of minimal dependencies. Such a cover is information lossless and is considerably smaller than the set of all valid dependencies. These qualities are particularly important to decrease variance while zero-one loss and bias are not affected negatively because of the provision of relevant knowledge wherein redundancy is minimized and extraneous information is discarded. Five large data sets with number of instances >10,000 are selected for variance comparison. The experimental results are shown in Table6, and we can see that canonical cover analysis can help to project AODE to be competitive with other attribute selection strategies from the viewpoint of variance comparison.Table 6
Variance results on 5 large data sets normalized with respect to AODE.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Adult
0.8653
0.8269
0.8846
0.8269
0.8461
0.8076
0.7692
0.7115
Connect 4
0.9091
0.8677
0.8925
0.9256
0.9078
0.8842
0.8099
0.7603
Donation
0.6575
0.7397
0.6986
0.7123
0.8767
0.8356
0.9452
0.7393
Nursery
0.6756
0.7027
0.7297
0.7567
0.7837
0.8378
0.9875
0.5945
Shuttle
0.7142
0.7142
0.9523
0.7142
0.4761
0.4761
0.4761
0.4761


### 4.2. Elimination Ratio

Statistically a win/draw/loss record (W/D/L) is calculated for each pair of competitorsA and B with regard to a performance measure M. The record represents the number of data sets in which A, respectively, beats, loses to, or ties with B on M. Small improvements in leave-one-out error may be attributable to chance. Consequently, it may be beneficial to use a statistical test to assess whether an improvement is significant. A standard binomial sign test, assuming that wins and losses are equiprobable, is applied to these records. A difference is considered to be significant when the outcome of a two-tailed binomial sign test is less than 0.05. To observe the effect of p attribute elimination of SP on zero-one loss, we used the following criterion:
(23)
E
Ratio
p
=
E
p
n
,
where E
p is the number of p attributes eliminated and n is the number of attributes. Table 7 shows the comparison results. The E
Ratio
p of SP is much higher than that of the other two p attribute elimination algorithms, PAA and PAE. The statistical records in Table 3 show that the corresponding zero-one loss of SP is lower generally. We suggest that the reason for SP’s outstanding performance on zero-one loss reduction is that it greatly utilizes the probabilistic dependency relationship on training data.Table 7
Win/draw/loss comparison of elimination ratio ofp attribute.
W/D/L
PAE
PAA
PAA
8/10/4
SP
9/9/4
6/11/5For example, the elimination ratio of SP is as high as 61.5% for data set “anneal.” However, the corresponding zero-one loss is lower than that of PAA and PAE. The main reason may be that, for as many as 38 attributes and only 894 instances, some attributes may have cross-functional zones, and only a few attributes may play the decisive role. After calculating and comparing the sum of CMI between one attribute and all the other attributes, most of the eliminated attributes have weak relationships to other attributes or are even nearly independent of them.SP selectsp attributes based on MST; attributes with a strong relationship among them will be selected first. If any attribute is removed by mistake, the classification results will not be affected greatly. However, for different training sets, especially when their sizes are very small, the conditional distribution estimates may differ greatly and different structures of MST may be obtained. Different p attributes will be selected for classification. The number of FDs extracted from RC is less than that from SR because numerous p attributes are eliminated during SP, especially for data set “audio,” with fewer p attributes and much more complicated FDs to remove c attributes. In the W/D/L records, the advantage in zero-one loss is significant with respect to SP versus PAE or SP versus PAA, but not SP + RC versus SP. This result shows that the advantage of SP + RC is from SP but not from RC.With the increasing number of attributes, more RAM is needed to store joint probability distributions. An important restriction of our algorithm is that the number of the left side of FD should be no more than 2. To observe the effect of SP + RC and SR on each data set, we calculate thec attribute elimination ratios by the following criterion:
(24)
E
Ratio
c
=
∑
i
=
1
N
E
c
i
N
,
where E
c
i is the number of c attributes eliminated for the ith instance, and N is the size of data set. Table 8 shows the comparison results of E
Ratio
c of SP + RC with the other three c attribute elimination algorithms, CAA, CAE, and SR. Table 3 shows that SP + RC has a significant advantage in zero-one loss over SR and NSR while SR and NSR outperform CAA and CAE. Comparing Table 3 with Table 8 reveals that both RC and SR can help to decrease zero-one loss. However, the effectiveness of RC relies greatly on SP while SR can always improve the performance of AODE. If SP removes p attributes by mistake, some valuable FDs will not be extracted by RC. However, if just redundant p nodes are eliminated, RC can extract more reliable FDs than SR because RC has considered all possible situations of SR.Table 8
Win/draw/loss comparison of elimination ratio ofc attribute.
W/D/L
CAE
CAA
SR
NSR
CAA
6/12/4
SR
9/9/4
6/12/4
NSR
9/8/5
6/11/5
6/11/5
RC
11/7/4
11/9/2
10/8/4
9/9/4For example, on data set “hypothyroid” theE
Ratio
c of RC is 32%, which indicates that RC just uses approximately 30% of all attributes as c attribute. The reason for this high ratio is that SP has eliminated 21% of the attributes from the data set. For data set “anneal,” the E
Ratio
c is also as high as 34%, and the zero-one loss is much higher than that of the other three algorithms. This result means SP has removed some p attributes by mistake; RC cannot extract FDs that are dependent on those deleted p attributes. Hence, the experimental results of SP + RC can still be improved if we can find other methods to keep more valuable p attributes for classification.


## 4.1. Zero-One Loss, Bias, and Variance Results

Table3 presents for each data set the zero-one loss, which is estimated by 50 runs of twofold cross-validation to give an accurate estimation of the average performance of an algorithm. The advantage of this technique is that it uses the full training data as the training set and the testing set. Moreover, every case in the training data is used for the same number of times in each of the roles of training and testing data. Tables 4 and 5 provide the bias and variance results, respectively. The zero-one loss, bias, or variance across multiple data sets provides a gross measure of relative performance.Table 3
Experimental results of zero-one loss.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.512
0.528
0.491
0.519
0.489
0.493
0.396
0.402
Adult
0.212
0.187
0.182
0.158
0.149
0.152
0.137
0.131
Anneal
0.017
0.014
0.013
0.013
0.012
0.011
0.017
0.008
Audio
0.272
0.263
0.247
0.258
0.258
0.217
0.261
0.158
Car
0.236
0.222
0.117
0.212
0.132
0.249
0.127
0.082
Chess
0.147
0.135
0.121
0.129
0.099
0.142
0.128
0.102
Cleveland
0.259
0.262
0.251
0.252
0.247
0.196
0.247
0.178
Connect 4
0.277
0.268
0.289
0.271
0.275
0.267
0.264
0.238
Contact lenses
0.422
0.415
0.409
0.411
0.395
0.445
0.401
0.375
Donation
0.002
0.002
0.002
0.001
0.000
0.001
0.000
0.000
Heart
0.192
0.187
0.182
0.189
0.191
0.197
0.189
0.174
Hepatitis
0.216
0.213
0.209
0.211
0.198
0.208
0.187
0.163
Hungarian
0.193
0.192
0.187
0.190
0.194
0.196
0.217
0.163
Hypothyroid
0.031
0.026
0.021
0.029
0.024
0.021
0.037
0.012
Iris
0.118
0.128
0.125
0.121
0.113
0.102
0.077
0.087
kr  versus kp
0.070
0.071
0.091
0.075
0.068
0.067
0.061
0.072
Labor
0.062
0.051
0.047
0.060
0.059
0.061
0.057
0.053
Mushroom
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
Nursery
0.088
0.091
0.085
0.081
0.085
0.083
0.089
0.072
Optdigits
0.051
0.055
0.053
0.052
0.051
0.049
0.049
0.030
Satellite
0.122
0.119
0.117
0.132
0.112
0.117
0.116
0.114
Shuttle
0.001
0.001
0.001
0.000
0.001
0.001
0.001
0.000Table 4
Experimental results of bias.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.332
0.351
0.327
0.312
0.312
0.307
0.291
0.316
Adult
0.147
0.151
0.148
0.152
0.118
0.120
0.155
0.161
Anneal
0.235
0.187
0.236
0.224
0.211
0.200
0.188
0.179
Audio
0.181
0.201
0.183
0.191
0.184
0.127
0.207
0.212
Car
0.152
0.164
0.155
0.148
0.134
0.138
0.127
0.131
Chess
0.106
0.110
0.092
0.114
0.104
0.112
0.113
0.112
Cleveland
0.071
0.068
0.072
0.069
0.064
0.048
0.052
0.049
Connect 4
0.201
0.165
0.199
0.215
0.192
0.197
0.202
0.204
Contact lenses
0.132
0.129
0.133
0.142
0.154
0.112
0.127
0.126
Donation
0.207
0.219
0.211
0.212
0.214
0.206
0.183
0.179
Heart
0.133
0.131
0.135
0.140
0.159
0.162
0.130
0.132
Hepatitis
0.112
0.120
0.114
0.121
0.113
0.109
0.115
0.113
Hungarian
0.205
0.211
0.206
0.198
0.203
0.211
0.204
0.219
Hypothyroid
0.013
0.013
0.012
0.015
0.009
0.007
0.008
0.008
Iris
0.090
0.088
0.090
0.101
0.094
0.067
0.087
0.085
kr versus kp
0.067
0.070
0.071
0.085
0.069
0.075
0.061
0.058
Labor
0.102
0.099
0.098
0.101
0.104
0.107
0.103
0.099
Mushroom
0.002
0.002
0.002
0.003
0.001
0.002
0.001
0.001
Nursery
0.050
0.049
0.050
0.048
0.052
0.054
0.051
0.049
Optdigits
0.028
0.029
0.028
0.031
0.029
0.028
0.027
0.025
Satellite
0.077
0.075
0.074
0.078
0.080
0.078
0.081
0.078
Shuttle
0.003
0.004
0.003
0.005
0.002
0.003
0.002
0.002Table 5
Experimental results of variance.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Abalone
0.127
0.134
0.142
0.152
0.165
0.161
0.151
0.153
Adult
0.045
0.043
0.046
0.043
0.044
0.042
0.040
0.048
Anneal
0.137
0.146
0.139
0.144
0.152
0.155
0.142
0.145
Audio
0.103
0.101
0.092
0.085
0.082
0.078
0.091
0.087
Car
0.101
0.108
0.118
0.122
0.132
0.133
0.112
0.115
Chess
0.108
0.112
0.103
0.089
0.093
0.088
0.102
0.096
Cleveland
0.152
0.162
0.172
0.179
0.192
0.187
0.207
0.198
Connect 4
0.110
0.105
0.108
0.112
0.110
0.107
0.098
0.092
Contact lenses
0.202
0.213
0.192
0.182
0.178
0.180
0.175
0.172
Donation
0.048
0.054
0.051
0.052
0.064
0.061
0.069
0.062
Heart
0.128
0.133
0.137
0.128
0.142
0.138
0.156
0.152
Hepatitis
0.055
0.058
0.059
0.061
0.063
0.060
0.058
0.053
Hungarian
0.207
0.217
0.196
0.180
0.183
0.177
0.195
0.191
Hypothyroid
0.004
0.004
0.005
0.005
0.004
0.006
0.004
0.004
Iris
0.092
0.096
0.090
0.094
0.092
0.088
0.085
0.081
kr versus kp
0.032
0.032
0.031
0.031
0.023
0.021
0.020
0.020
Labor
0.037
0.034
0.036
0.037
0.038
0.036
0.027
0.024
Mushroom
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
Nursery
0.025
0.026
0.027
0.028
0.029
0.031
0.037
0.032
Optdigits
0.021
0.020
0.021
0.022
0.023
0.023
0.022
0.019
Satellite
0.045
0.047
0.049
0.050
0.049
0.045
0.051
0.048
Shuttle
0.003
0.003
0.004
0.003
0.002
0.002
0.002
0.002The basic relationships among attributes can be clearly observed by building MST. If one attribute is connected with several other attributes, the attribute is supposed to have crossed functional zones and will be selected asp attribute to retain complementarity. If one attribute is connected with only one other attribute, its independence characteristics may be obvious and will be reconsidered by the weight of CMI. Besides, RC helps to detect the situation in which the relationships that hold in MST need to be refined. Table 3 shows that the advantage of SP + RC is significant compared with SR and NSR in terms of zero-one loss. However, SR and NSR have a significant advantage over CAA, PAA, CAE, and PAE. The disappointing performances of CAA, PAA, CAE, and PAE can be ascribed to their susceptibility to getting trapped into poor selections by local minima during the first several additions or deletions.The records in Table4 show that all the c attribute selection algorithms applying SR, NSR, or FDs have a significant advantage in bias over CAE and PAE. In addition, CAE and PAE outperform CAA and PAA. However, comparing SP + RC with SP again does not show obvious difference. This result indicates that SP takes the main role for classification and its effect differs greatly in different data sets. The same result can also be inferred by comparing SP + RC with SR. The training sets containing only 25% of each data set for bias-variance evaluation are small because the data sets are primarily small. The bias of SP + RC decreases as training set size increases because more data will lead to more accurate probability distribution estimates and hence to more appropriate p attribute selection. Of these algorithms, RC, SR, and NSR have the weakest sensitivity to the changes in training data because they can utilize the testing set to infer rules for c attribute elimination. By contrast PAA, PAE, CAA, and CAE perform model selection and their biases differ greatly with different training data.With respect to variance, as Table5 shows, the variance of SP + RC does not show obvious advantage to other algorithms. Low-variance algorithms tend to enjoy an advantage with small data sets, whereas low-bias algorithms tend to enjoy an advantage with large data sets. Cross data set experimental studies of the traditional form presented above also support this hypothesis. The main reason may be that the relationship inferred based on MST may overfit the training data because SP needs to calculate CMI to construct MST. This requires enough instances to achieve precise probability estimation.In the following discussion, canonical cover analysis [17], which can use limited number (e.g., 100) of instances to infer credible FD set, is applied in tandem with functional dependency analysis. Let F
c be a canonical cover for a set of simple FDs and the procedure of computing F
c is described as  in Algorithm 1.Algorithm 1:
F
c = FDs
repeat
Use the union rule to replace any dependencies inF
c of the form
α
1
→
β
1 and α
1
→
β
2 with α
1
→
β
1
β
2.
Find a functional dependencyα
→
β in F
c with an extraneous
attribute either inα or in β.
If an extraneous attribute is found, delete it fromα
→
β in F
c.
until (F
c does not change)The chosen canonical cover is the set of minimal dependencies. Such a cover is information lossless and is considerably smaller than the set of all valid dependencies. These qualities are particularly important to decrease variance while zero-one loss and bias are not affected negatively because of the provision of relevant knowledge wherein redundancy is minimized and extraneous information is discarded. Five large data sets with number of instances >10,000 are selected for variance comparison. The experimental results are shown in Table6, and we can see that canonical cover analysis can help to project AODE to be competitive with other attribute selection strategies from the viewpoint of variance comparison.Table 6
Variance results on 5 large data sets normalized with respect to AODE.
Data set
PAE
CAE
PAA
CAA
SR
NSR
SP
SP + RC
Adult
0.8653
0.8269
0.8846
0.8269
0.8461
0.8076
0.7692
0.7115
Connect 4
0.9091
0.8677
0.8925
0.9256
0.9078
0.8842
0.8099
0.7603
Donation
0.6575
0.7397
0.6986
0.7123
0.8767
0.8356
0.9452
0.7393
Nursery
0.6756
0.7027
0.7297
0.7567
0.7837
0.8378
0.9875
0.5945
Shuttle
0.7142
0.7142
0.9523
0.7142
0.4761
0.4761
0.4761
0.4761


## 4.2. Elimination Ratio

Statistically a win/draw/loss record (W/D/L) is calculated for each pair of competitorsA and B with regard to a performance measure M. The record represents the number of data sets in which A, respectively, beats, loses to, or ties with B on M. Small improvements in leave-one-out error may be attributable to chance. Consequently, it may be beneficial to use a statistical test to assess whether an improvement is significant. A standard binomial sign test, assuming that wins and losses are equiprobable, is applied to these records. A difference is considered to be significant when the outcome of a two-tailed binomial sign test is less than 0.05. To observe the effect of p attribute elimination of SP on zero-one loss, we used the following criterion:
(23)
E
Ratio
p
=
E
p
n
,
where E
p is the number of p attributes eliminated and n is the number of attributes. Table 7 shows the comparison results. The E
Ratio
p of SP is much higher than that of the other two p attribute elimination algorithms, PAA and PAE. The statistical records in Table 3 show that the corresponding zero-one loss of SP is lower generally. We suggest that the reason for SP’s outstanding performance on zero-one loss reduction is that it greatly utilizes the probabilistic dependency relationship on training data.Table 7
Win/draw/loss comparison of elimination ratio ofp attribute.
W/D/L
PAE
PAA
PAA
8/10/4
SP
9/9/4
6/11/5For example, the elimination ratio of SP is as high as 61.5% for data set “anneal.” However, the corresponding zero-one loss is lower than that of PAA and PAE. The main reason may be that, for as many as 38 attributes and only 894 instances, some attributes may have cross-functional zones, and only a few attributes may play the decisive role. After calculating and comparing the sum of CMI between one attribute and all the other attributes, most of the eliminated attributes have weak relationships to other attributes or are even nearly independent of them.SP selectsp attributes based on MST; attributes with a strong relationship among them will be selected first. If any attribute is removed by mistake, the classification results will not be affected greatly. However, for different training sets, especially when their sizes are very small, the conditional distribution estimates may differ greatly and different structures of MST may be obtained. Different p attributes will be selected for classification. The number of FDs extracted from RC is less than that from SR because numerous p attributes are eliminated during SP, especially for data set “audio,” with fewer p attributes and much more complicated FDs to remove c attributes. In the W/D/L records, the advantage in zero-one loss is significant with respect to SP versus PAE or SP versus PAA, but not SP + RC versus SP. This result shows that the advantage of SP + RC is from SP but not from RC.With the increasing number of attributes, more RAM is needed to store joint probability distributions. An important restriction of our algorithm is that the number of the left side of FD should be no more than 2. To observe the effect of SP + RC and SR on each data set, we calculate thec attribute elimination ratios by the following criterion:
(24)
E
Ratio
c
=
∑
i
=
1
N
E
c
i
N
,
where E
c
i is the number of c attributes eliminated for the ith instance, and N is the size of data set. Table 8 shows the comparison results of E
Ratio
c of SP + RC with the other three c attribute elimination algorithms, CAA, CAE, and SR. Table 3 shows that SP + RC has a significant advantage in zero-one loss over SR and NSR while SR and NSR outperform CAA and CAE. Comparing Table 3 with Table 8 reveals that both RC and SR can help to decrease zero-one loss. However, the effectiveness of RC relies greatly on SP while SR can always improve the performance of AODE. If SP removes p attributes by mistake, some valuable FDs will not be extracted by RC. However, if just redundant p nodes are eliminated, RC can extract more reliable FDs than SR because RC has considered all possible situations of SR.Table 8
Win/draw/loss comparison of elimination ratio ofc attribute.
W/D/L
CAE
CAA
SR
NSR
CAA
6/12/4
SR
9/9/4
6/12/4
NSR
9/8/5
6/11/5
6/11/5
RC
11/7/4
11/9/2
10/8/4
9/9/4For example, on data set “hypothyroid” theE
Ratio
c of RC is 32%, which indicates that RC just uses approximately 30% of all attributes as c attribute. The reason for this high ratio is that SP has eliminated 21% of the attributes from the data set. For data set “anneal,” the E
Ratio
c is also as high as 34%, and the zero-one loss is much higher than that of the other three algorithms. This result means SP has removed some p attributes by mistake; RC cannot extract FDs that are dependent on those deleted p attributes. Hence, the experimental results of SP + RC can still be improved if we can find other methods to keep more valuable p attributes for classification.


## 5. Conclusion and Future Work

AODE provides an attractive framework by averaging all models from a restricted class of one-dependence classifiers. The class of all such classifiers that have all other attributes depends on a common attribute and the class attribute. The current work aims to improve the accuracy derived by MST and FD from weakening the attribute independence assumption without high computational overheads.Overall, this study developed a classification learning technique that retains the simplicity and direct theoretical foundation of AODE while reducing computational overhead without incurring a negative effect on classification performance. Thep attribute of AODE can also be considered the parent of the class attribute. Therefore, we hypothesize that the success of AODE and its variations may be attributed to the fact that AODE not only aggregates all other restricted classes of models but also extends NB to handle the parent of class attribute. If this hypothesis can be proven, we can design a novel and perhaps more effective Bayesian classifier than AODE by constructing the Markov blanket of class attributes.



---

*Source: 470821-2014-06-17.xml*