Learning Recursive Bayesian Multinets for Data Clustering by Means of Constructive Induction.
This paper introduces and evaluates a new class of knowledge model, the recursive Bayesian multinet (RBMN), which encodes the joint probability distribution of a given database. RBMNs extend Bayesian networks (BNs) as well as partitional clustering systems. Briefly, a RBMN is a decision tree with component BNs at the leaves. A RBMN is learnt using a greedy, heuristic approach akin to that used by many supervised decision tree learners, but where BNs are learnt at leaves using constructive induction. A key idea is to treat expected data as real data. This allows us to complete the database and to take advantage of a closed form for the marginal likelihood of the expected complete data that factorizes into separate marginal likelihoods for each family (a node and its parents). Our approach is evaluated on synthetic and real-world databases.
Introduction
One of the main problems that arises in a great variety of elds, including pattern
recognition, machine learning and statistics, is the so-called data clustering problem
[1, 3, 7, 14, 15, 22, 25]. Data clustering can be viewed as a data-partitioning problem,
where we partition data into dierent clusters based on a quality or similarity criterion
(e.g., as in K-Means [30]). Alternatively, data clustering is one way of representing the
joint probability distribution of a database. We assume that, in addition to the observed
or predictive attributes, there is a hidden variable. This unobserved variable re
ects
the cluster membership for every case in the database. Therefore, the data clustering
problem is also an example of learning from incomplete data due to the existence of such
a hidden variable. Incomplete data represents a special case of missing data, where all
the missing entries are concentrated in a single (hidden) variable. That is, we refer to a
given database as incomplete when the classication is not given. Parameter estimation
and model comparison in classical and Bayesian statistics provide a solution to the
data clustering problem. The most frequently used approaches include mixture density
models (e.g., Gaussian mixture models [3]) and Bayesian networks (e.g., AutoClass [8]).
We aim to automatically recover the joint probability distribution from a given
incomplete database by learning recursive Bayesian multinets (RBMNs). Roughly, a
recursive Bayesian multinet is a decision tree [4, 44] where each decision path (i.e., a
conjunction of predictive attribute-value pairs) ends in an alternate component Bayesian
network (BN) [6, 24, 29, 38].
RBMNs are a natural extension of BNs. While the conditional (in)dependencies
encoded by a BN are context-non-specic conditional (in)dependencies, RBMNs allow
us to work with context-specic conditional (in)dependencies [21, 49], which dier from
decision path to decision path.
Our heuristic approach to the learning of RBMNs requires the learning of its component
BNs from incomplete data. In the last few years, several methods for learning
BNs have arisen [5, 12, 23, 37, 48], some of them that learn from incomplete data
[9, 17, 33, 39, 40, 49]. We describe how the Bayesian heuristic algorithm for the learning
of BNs for data clustering developed by Pe~na et al. [39] is extended to learn RBMNs.
A key step in the Bayesian approach to learning graphical models in general and BNs
in particular is the computation of the marginal likelihood of data given the model. This
quantity is the ordinary likelihood of data averaged over the parameters with respect
to their prior distribution. When dealing with incomplete data, the exact calculation
of the marginal likelihood is typically intractable [12], thus, such a computation has to
be approximated [11]. The existing methods are rather ine-cient for our purpose of
eliciting a RBMN from an incomplete database, since they do not factorize into scores
for families (i.e., nodes and their parents). Hence, we would have to recompute the
score for the whole structure from anew, although only the factors of some families had
changed.
To avoid this problem, we use the algorithm developed in [39] based upon the work
done in [49]. We search for parameter values for the initial structure by means of the EM
algorithm [13, 31], or by means of the BC+EM method [40]. This allows us to complete
the database by using the current model, that is, by treating expected data as real data,
which results in the possibility of using a score criterion that is both in closed form and
The remainder of this paper is organized as follows. In Section 2, we describe BNs,
Bayesian multinets (BMNs) and RBMNs for data clustering. Section 3 is dedicated to
the heuristic algorithm for the learning of component BNs from incomplete data. In
Section 4, we describe the algorithm for the learning of RBMNs for data clustering.
Finally, in Section 5 we present some experimental results. The paper nishes with
Section 6 where we draw some conclusions and outline some lines of further research.
BNs, BMNs and RBMNs for data clustering
2.1 Notation
We follow the usual convention of denoting variables by upper-case letters and their
states by the same letters in lower-case. We use a letter or letters in bold-face upper-case
to designate a set of variables and the same bold-face lower-case letter or letters to
denote an assignment of state to each variable in a given set. jXj is used to refer to the
number of states of the variable X. We use p(x j y) to denote the probability that
y. We also use p(x j y) to denote the conditional probability distribution
(mass function, as we restrict our discussion to the case where all the variables are
discrete) for X given y. Whether p(x j y) refers to a probability or a conditional
probability distribution should be clear from the context.
As we mentioned, when facing a data clustering problem we assume the existence
of the n-dimensional random variable X that is partitioned as into an
(n 1)-dimensional random variable Y (predictive attributes), and a unidimensional
hidden variable C (cluster variable).
2.2 BNs for data clustering
Given an n-dimensional variable C), a BN [6, 24, 29, 38]
for X is a graphical factorization of the joint probability distribution for X. A BN
is dened by a directed acyclic graph b (model structure) determining the conditional
(in)dependencies among the variables of X and a set of local probability distributions.
When b contains an arc from the variable X j to the variable X i , X j is referred to as a
parent of X i . We denote by Pa(b) i the set of all the parents that the variable X i has in
b. The structure lends itself to a factorization of the joint probability distribution for
X as follows:
Y
where pa(b) i denotes the state of the parents of X i , Pa(b) i , consistent with x. The local
probability distributions of the BN are those in Equation 1 and we assume that they
depend on a nite set of parameters    b 2    b . Therefore, Equation 1 can be rewritten
as follows:
Y
If b h denotes the hypothesis that the conditional (in)dependence assertions implied
by b hold in the true joint probability distribution for X, then we obtain from Equation 2
Y
According to the partition of X as Equation 3 can be rewritten as
follows:
Y
where prepa(b) i denotes the state of those parents of Y i that correspond to predictive
attributes, consistent with y.
Thus, a BN is completely dened by a pair (b;   b ). The rst of the two components
is the model structure, and the second component is the set of parameters for the local
probability distributions corresponding to b. See Figure 1 for an example of a BN
structure for data clustering with ve predictive attributes.
2.3 BMNs for data clustering
The conditional (in)dependencies determined by the structure of a BN are called context-
non-specic conditional (in)dependencies [49], also known as symmetric conditional
(in)dependencies [21]. That is, if the structure implies that two sets of variables are
independent given some conguration (or state) of a third set of variables, then the
two rst sets are also independent given every other conguration of this third set

Figure

1: Example of the structure of a BN for data clustering for
C). It follows from the gure that the joint probability distribution
factorizes as
of variables. A BMN [21] is a generalization of the BN model that is able to encode
context-specic conditional (in)dependencies [49], also known as asymmetric conditional
(in)dependencies [21]. Therefore, a BMN structure may imply that two sets of variables
are independent given some conguration of a third set, and dependent given another
conguration of this third set. Formally, a BMN for
distinguished variable G 2 Y is a graphical factorization of the joint probability distribution
for X. A BMN is dened by a probability distribution for G and a set of
component BNs for XnfGg, each of which encodes the joint probability distribution for
XnfGg given a state of G. Because the structure of each component BN may vary, a
BMN can encode context-specic conditional (in)dependence assertions. In this paper,
we limit the distinguished variable G to be one of the original predictive attributes.
However, [49] allows the distinguished variable to be either one of the predictive attributes
or the hidden cluster variable C. When this last happens, each leaf represents
a single cluster. These models are called mixtures of BNs according to [49]. Figure 2
shows the structure of a BMN for data clustering when the distinguished variable G has
two values.
Let s and    s denote the structure and parameters of a BMN for X and distinguished
variable G. In addition, let us suppose that b g and    g denote the structure and parameters
of the g-th component BN of the BMN. Also, let s h denote the hypothesis that the
context-specic conditional (in)dependencies implied by s hold in the true joint probability
distribution for X and distinguished variable G. Therefore, the joint probability
distribution for X encoded by the BMN is given by:
where    denotes the parameters of the BMN, b h
g is a short-hand
for the conjunction of s h and The last term of
the previous equation can be further factorized according to the structure of the g-th
component BN of the BMN (Equation 4).
Thus, a BMN is completely dened by a pair (s;    s ). The rst of the two components
is the structure of the BMN, and the second component is the set of parameters.
We may see a BMN as a depth-one decision tree [4, 44], where the distinguished
variable is the root and there is a branch for each of its states. At the end of each of
Y
Y =y5 52Y =y
Figure

2: Example of the structure of a BMN for data clustering for
distinguished variable There are two component BNs
as the distinguished variable is dichotomic (jY 5 j=2). Dotted lines correspond to the
distinguished variable Y 5 .
these branches is a leaf which is a component BN. Thus, it is helpful to see the dotted
lines of Figure 2 as conforming a decision tree with component BNs as leaves.
2.4 RBMNs for data clustering
Let us follow with the view of a BMN as a depth-one decision tree where leaves are component
BNs. We propose to use deeper decision trees where leaves are still component
BNs. By denition, every component of a BMN is limited to be a BN. A RBMN allows
every component to be either a BN (at a leaf) or recursively a RBMN.
RBMNs extend BNs and BMNs, but RBMNs also extend partitional clustering systems
[16]. RBMNs can be considered as extensions of BNs because, like BMNs and mixtures
of BNs, RBMNs allow us to encode context-specic conditional (in)dependencies.
Thus, they constitute a more
exible tool than BNs and provide the user with structured
and specialized domain knowledge as alternative component BNs are learnt for every
decision path. Moreover, RBMNs generalize the idea behind BMNs by oering the possibility
of having decision paths with conjunctions of as many predictive attribute-value
pairs as we want. The only constraint is that these decision paths must be represented
by a decision tree.
Additionally, RBMNs extend traditional partitional clustering systems. A previous
work with the same aim is [16] where Fisher and Hapanyengwi propose to perform
data clustering based upon a decision tree. The measure used to select the divisive
attribute at each node during the decision tree construction consists of the computation
of the sum of information gains over all attributes, while in the supervised paradigm the
measure is limited to the information gain over a single specied class attribute. This is
a natural generalization of the works on supervised learning where the performance task
comprises the prediction of only one attribute from the knowledge of many, whereas the
generic performance task in unsupervised learning is the prediction of many attributes
Y =y
BN BN
BN BN
Y =y
Y =y
Y =y 32Distinguished
decision tree T
BNs
Component

Figure

3: Example of the structure of a 2-levels RBMN for data clustering for
distinguished decision tree T. This RBMN has two
component BMNs, each of them with two component BNs (assuming that the variables
in the distinguished decision tree are all dichotomic). Dotted lines correspond to the
distinguished decision tree T.
from the knowledge of many. Thus, RBMNs and the work by Fisher and Hapanyengwi
aim to learn a decision tree with knowledge at leaves su-cient for making inference
along many attributes. This implies that both paradigms are considered extensions
of traditional partitional clustering systems as they are concerned with characterizing
clusters of observations rather than partitioning them.
We dene a RBMN according to the intuitive idea of a decision tree with component
BNs as leaves. Let T be a decision tree, here referred to as distinguished decision
tree, where (i) every internal node in T represents a variable of Y, (ii) every internal
node has as many children or branches coming out from it as states for the variable
represented by the node, (iii) all the leaves are at the same level, and (iv) if T(root; l) is
the set of variables that are in the decision path between the root and the leaf l of the
distinguished decision tree, there are then no repeated variables in T(root; l). Condition
(iii) is imposed to simplify the understanding of RBMNs and their learning, but such a
constraint can be removed in practice. Let us dene XnT(root; l) as the set of all the
variables in X except those that are in the decision path between the root and the leaf
l of the distinguished decision tree T. Thus, a RBMN for
and distinguished decision tree T is a graphical factorization of the joint probability
distribution for X. A RBMN is dened by a probability distribution for the leaves of
T and a set of component BNs, each of which encodes the joint probability distribution
for XnT(root; l) given the l-th leaf of T. Thus, the component BN at every leaf of
the distinguished decision tree does not consider attributes involved in the tests on the
decision path leading to the leaf.
Obviously, BMNs are a special case of RBMNs in which T is a distinguished decision
tree with only one internal node, the distinguished variable. Moreover, we could assume
that BNs are also a special case of RBMNs in which the distinguished decision tree
contains no internal nodes.

Figure

3 helps us to illustrate the structure of a RBMN for data clustering as a
decision tree where each internal node is a predictive attribute and branches from that
node are states of the variable. Every leaf l is a component BN that does not consider
attributes in T(root; l). So, the induction of the component BNs is simplied. Since
every internal node of T is a predictive attribute, the hidden variable C appears in every
component BN. This fact implies that the component BN at each leaf of T does not
represent only one cluster as Fisher and Hapanyengwi propose in [16], but a context-
specic data clustering. That is, the data clustering encoded by each component BN
is totally unrelated to the data clusterings encoded by the rest. This means that the
probabilistic clusters identied by each component BN are not in correspondence with
those identied by the rest of component BNs. This is due to the fact that C acts
as a context-specic or local hidden cluster variable for every component BN. To be
exact, every variable of each component BN is a context-specic variable that does not
interact with the variables of any other component BN since the elicitation of every
component BN is totally independent of the rest. This is not explicitly re
ected in the
notation as every branch identies unambiguously each component BN and its variables.
Additionally, this avoids a too complex notation. This reasoning should also be applied
to BMNs as they are a special case of RBMNs.
Let s and    s denote the structure and parameters of a RBMN for X and distinguished
decision tree T. In addition, let us suppose that b l and    l denote the structure and
parameters of the l-th component BN of the RBMN. Also, let s h denote the hypothesis
that the context-specic conditional (in)dependencies implied by s hold in the true joint
probability distribution for X and distinguished decision tree T. Therefore, the joint
probability distribution for X encoded by the RBMN is given by:
l
where the leaf l is the only one that makes x be consistent with t(root; l),
denotes the parameters of the RBMN, L is the number of leaves
in T, b h
l is a shorthand for the conjunction of s h and T(root;
The last term of the previous equation can be further factorized
according to the structure of the l-th component BN of the RBMN (Equation 4).
Thus, a RBMN is completely dened by a pair (s;    s ). The rst of the two components
is the structure of the RBMN, and the second component is the set of parameters.
In this paper, we limit our discussion to the case in which the component BNs
are dened by multinomial distributions. That is, all the variables are nite discrete
variables and the local distributions at each variable in the component BNs consist of a
set of multinomial distributions, one for each conguration of the parents. In addition,
we assume that the proportions (probabilities) of data covered by the leaves of T follow
also a multinomial distribution.
As stated, RBMNs extend BNs due to their ability to encode context-specic conditional
(in)dependencies which increases the expressive power of RBMNs over BNs. A
decision tree eectively identies subsets of the original database where dierent component
BNs result a better, more
exible way t to data.
Other works in supervised induction identify instance subspaces through local or
component models. Kohavi [27] links Naive Bayes (NB) classiers and decision tree
learning. On the other hand, the work done by Zheng and Webb [50] combines the
previous work by Kohavi with a lazy learning algorithm to build Bayesian rules where
the antecedent is a conjunction of predictive attribute-value pairs, and the consequent is
a NB classier. Thus, both works share the fact that they use conjunctions of predictive
attribute-value pairs to dene instance subspaces described by NB classiers. Zheng
and Webb [50] give an extensive experimental comparison between these two and other
approaches for supervised learning in some well-known domains.
Langley [28] proposes to identify instance subspaces where the independence assumptions
made by the NB classier hold. His work is based upon the recursive split of the
original database by using decision trees where nodes are NB classiers and leaves are
sets of cases belonging to only one class.
To illustrate how RBMNs structure a clustering for a given database, we use a real-world
domain where data clustering was successfully performed by means of probabilistic
graphical models [41], with the aim of improving knowledge on the geographical distribution
of malignant tumors. A geographical clustering of the towns of the Autonomous
Community of the Basque Country (north of Spain) was performed. Every town was
described by the age-standardized cancer incidence rates of the six most frequent cancer
types for patients of each sex between 1986 and 1994. The authors obtained a geographical
clustering for male patients and a geographical clustering for female patients
as the dierences in the geographical patterns of malignant tumors for patients of each
sex are well-known by the experts. Each of both clusterings was achieved by means
of the learning of a BN. The nal clusterings were presented by using colored maps to
partition the towns in such a way that each town was assigned to the most probable
cluster according to the learnt BN, i.e., each town was assigned to the cluster with the
highest posterior probability.
Due to the dierent geographical patterns for male and female patients, it seems
quite reasonable to assume that a RBMN would be an eective and automatic tool to
face the referred real-world problem without relying on human expertise. That is, the
learning of a RBMN would be able to automatically identify that the instance subspace
for male patients encodes an underlying model dierent from the one encoded by the
instance subspace for female patients. However, the authors relied on human expertise
to divide the original database and treat separately male and female cases.

Figure

4 shows a RBMN that, ideally, would be learnt, and the structured clustering
obtained from this model. It is easy to see that the clusterings obtained for male and
female patients are dierent as well as context-specic. Furthermore, [41] reports that
the characterization of each cluster was completely dierent for male and female patients.
These dierences in the geographical patterns can not be captured when learning BNs
from the original joint database. In this example, Figure 4 is also a BMN since the
distinguished decision tree contains only one predictive attribute. However, it is easy
to see that a RBMN might represent a more complex decision tree that represented a
more specialized clustering. For example, we might expect dierent component BNs for
each of the four conjunctions
example could be encoded by a RBMN with a 2-levels distinguished decision tree.
A key idea in our approach to the learning of a RBMN for data clustering is to
decompose the problem into learning its component BNs from incomplete data. The
component BN corresponding to each leaf l is learnt from an incomplete database that
is a subset of the original incomplete database. This subset contains all the cases of
the original database that are consistent with t(root; l). Therefore, there still exists
a hidden variable when learning every component BN. That is why the problem of
learning a RBMN for data clustering is largely a problem of learning component BNs
from incomplete data. Thus, in the following section, we present a heuristic algorithm
for the learning of a BN from an incomplete database.
SEX=male SEX=female
BN male BN female

Figure

4: Scheme of the structure of the RBMN that, ideally, would be learnt for the real-world
domain described in [41]. Additionally, the clusterings encoded by the component
BNs are shown as colored maps. White towns were excluded from the study.
3 Learning BNs from incomplete data through constructive
induction
In this section, we describe a heuristic algorithm to elicit the component BNs from
incomplete data. We use this heuristic algorithm as part of the algorithm for the learning
of RBMNs for data clustering that we present in the following section.
3.1 Component BN structure
Due to the di-culty involved in learning densely connected BNs and the painfully slow
probabilistic inference when working with them, it is desirable to develop methods for
learning the simplest BNs that t the data adequately. Some examples of this trade-
between the cost of the learning process and the quality of the learnt models are
NB models [14, 43], Extended Naive Bayes (ENB) models [36, 37, 39, 42], and Tree
Augmented Naive Bayes models [18, 19, 20, 26, 32, 40]. Despite the wide recognition
that these models are a weaker representation of some domains than more general BNs,
the expressive power of these models is often acceptable. Moreover, these models appeal
to human intuition and can be learnt relatively quickly.
For the sake of brevity, the class of compromise BNs that we propose to learn as
component BNs will be referred to as ENB [42]. ENB models were introduced by Pazzani
[36, 37] as Bayesian classiers and later used by Pe~na et al. [39, 42] for data clustering.
ENB models can be considered as having an intermediate place between NB models
NB model Fully correlated model
ENB model
Y ,Y ,Y 3 5

Figure

5: Component BN (ENB model) structure that we propose to learn seen as
having a place between NB models and fully correlated models, when applied to the
data clustering problem.
and models with all the predictive attributes fully correlated (see Figure 5). Thus,
they keep the main features of both extremes: simplicity from NB models and a better
performance from fully correlated models.
ENB models are very similar to NB models since all the attributes are independent
given the cluster variable. The only dierence with NB models is that the number of
nodes in the structure of an ENB model can be shorter than the original number of
attributes in the database. The reasons are that (i) a selection of the attributes to
be included in the models can be performed, and (ii) some attributes can be grouped
together under the same node as fully correlated attributes (we refer to such nodes as
supernodes 1 ). Therefore, the class of ENB models ensures a better performance than NB
models while it maintains their simplicity. As we consider all the attributes relevant for
the data clustering task, we do not perform attribute selection as proposed by Pazzani.
The structure of an ENB model for data clustering lends itself to a factorization of
the joint probability distribution for X as follows:
r
Y
is a partition of y, where r is the number of nodes (including the
special nodes referred to as supernodes). Each z i is the set of values in y for the original
predictive attributes that are grouped together under a supernode Z i , or it is the value
in y for a predictive attribute Z i .
3.2 Algorithm for learning ENB models from incomplete data
The log marginal likelihood is often used as the Bayesian criterion to guide the search
for the best model structure. An important feature of the log marginal likelihood is
that, under some reasonable assumptions, it factorizes into scores for families. When a
criterion is factorable, search is more e-cient since we need not reevaluate the criterion
for the whole structure when only the factors of some families have changed. This is
an important feature when working with some heuristic search algorithms, because they
iteratively transform the model structure by choosing the transformation that improves
the score the most and, usually, this transformation does not aect all the families.
1 In the remainder of this paper, we refer to the set of nodes and supernodes of an ENB model simply
as nodes.
1.Choose initial structure and initial set of parameter values
for the initial structure
2.Parameter search step
3.Probabilistic inference to complete the database
4.Calculate sufficient statistics to compute the log p(d j b h )
5.Structure search step
6.Reestimate parameter values for the new structure
7.IF no change in the structure has been done
THEN stop
ELSE IF interleaving parameter search step
THEN go to 2
ELSE go to 3

Figure

A schematic of the algorithm for the learning of component BNs (ENB models)
from incomplete data.
When the variable that we want to classify is hidden the exact calculation of the
log marginal likelihood is typically intractable [12], thus, we have to approximate such
a computation [11]. However, the existing methods for doing this are rather ine-cient
for eliciting the component BNs (ENB models) from incomplete databases as they do
not factorize into scores for families.
To avoid this problem, we use the heuristic algorithm presented in [39], which is
shown in Figure 6. First, the algorithm chooses an initial structure and parameter
values. Then, it performs a parameter search step to improve the set of parameters
for the current model structure. These parameter values are used to complete the
database, because the key idea in this approach is to treat expected data as real data
(hidden variable completion by means of probabilistic inference with the current model).
Hence, the log marginal likelihood of the expected complete data, log p(d j b h ), can be
calculated by [12] in closed form. Furthermore, the factorability of the log marginal
likelihood into scores for families allows the performance of an e-cient structure search
step. After structure search, the algorithm reestimates the parameters for the new
structure that it nds to be the maximum likelihood parameters given the complete
database. Finally, the probabilistic inference process to complete the database and the
structure search are iterated until there is no change in the structure. Figure 6 shows the
possibility of interleaving the parameter search step or not after each structural change,
though we will not interleave parameter and structure search in the experiments to
follow for reasons of cost.
Another key point is that a penalty term is built into the log marginal likelihood to
guard against overly complex models. In [33] a similar use of this built-in penalty term
can be found.
In the remainder of this section, we describe the parameter search step and the
structure search step in more detail.
3.2.1 Parameter search
As seen in Figure 6, the heuristic algorithm that we use considers the possibility of
interleaving parameter and structure search steps. Concretely, this interleaving process
1.FOR every case y in the database DO
a.Calculate the posterior probability distribution p(c j
b.Let p max be the maximum of p(c j which is reached
for
fixing probability threshold
THEN assign the case y to the cluster c max
2.Run the BC method
a.Bound
b.Collapse
3.Set the parameter values for the current BN to be the BC's
output parameter values
4.Run the EM algorithm until convergence
5.IF BC+EM convergence
THEN stop
ELSE go to 1

Figure

7: A schematic of the BC+EM method.
is done, at least, in the rst iteration of the algorithm. By doing that, we ensure a good
set of initial parameter values. For the remaining iterations we can then decide whether
to interleave parameter and structure search steps or not. Although any parameter
search procedure can be considered to perform the parameter search step, currently,
we propose two alternative techniques: the well-known EM algorithm [13, 31], and the
BC+EM method [40].
According to [40], the BC+EM method exhibits a faster convergence rate, and more
eective and robust behavior than the EM algorithm. That is why the BC+EM method
is used in our experimental evaluation of RBMNs. Basically, the BC+EM method
alternates between the Bound and Collapse (BC) method [45, 46] and the EM algorithm.
The BC method is a deterministic method to estimate conditional probabilities from
databases with missing entries. It bounds the set of possible estimates consistent with
the available information by computing the minimum and the maximum estimate that
would be obtained from all possible completions of the database. These bounds are
then collapsed into a unique value via a convex combination of the extreme points with
weights depending on the assumed pattern of missing data. This method presents all the
advantages of a deterministic method and a dramatic gain in e-ciency when compared
with the EM algorithm [47].
The BC method is used in presence of missing data, but it is not useful when there
is a hidden variable as in the data clustering problem. The reason for this is that the
probability intervals returned by the BC method would be too large and poorly inform
the missing entries of the single hidden variable. The BC+EM method overcomes this
problem by performing a partial completion of the database at each step. See Figure 7
for a schematic of the BC+EM method.
For every case y in the database, the BC+EM method uses the current parameter
values to evaluate the posterior probability distribution for the cluster variable C given
y. Then, it assigns the case y to the cluster with the highest posterior probability
only if this posterior probability is greater than a threshold, xing probability threshold,
that the user must determine. The case remains incomplete if there is no cluster with
1.Consider joining each pair of attributes
2.IF there is an improvement in the log p(d j b h )
THEN make the joint that improves the score the most
ELSE return the current case representation

Figure

8: A template for the forward structure search step.
1.Consider splitting each attribute at each possible point
2.IF there is an improvement in the log p(d j b h )
THEN make the split that improves the score the most
ELSE return the current case representation

Figure

9: A template for the backward structure search step.
posterior probability greater than the threshold. As some of the entries of the hidden
variable have been completed during this process, we hope to have more informative
probability intervals when running the BC method. The EM algorithm is then executed
to improve the parameter values that the BC method has returned. The process is
repeated until convergence.
3.2.2 Structure search
In [10], Chickering shows that nding the BN structure with the highest log marginal
likelihood from the set of all the BN structures in which each node has no more than k
parents is NP-hard for k > 1. Therefore, it is clear that heuristic methods are needed.
Our particular choice is based upon the work done by Pazzani [36, 37]. Pazzani presents
algorithms for learning augmented NB classiers (ENB models) by searching for dependencies
among attributes: the Backward Sequential Elimination and Joining (BSEJ)
algorithm and the Forward Sequential Selection and Joining (FSSJ) algorithm. To nd
attribute dependencies, these algorithms perform constructive induction [2, 35], which
is the process of changing the representation of the cases in the database by creating
new attributes (supernodes) from existing attributes. As a result, some violation of conditional
independence assumptions made by NB models are detected and dependencies
among predictive attributes are included in the model. Ideally, a better performance is
reached while the model that we obtain after the constructive induction process maintains
the simplicity of NB models. Pazzani uses the term joining to refer to the process of
creating a new attribute whose values are the Cartesian product of two other attributes.
To carry out this change in the representation of the database, Pazzani proposes a hill-climbing
search combined with two operators: replacing two existing attributes with a
new attribute that is the Cartesian product of the two attributes, and either delete an
irrelevant attribute (resulting in the BSEJ) or add a relevant attribute (resulting in the
FSSJ).
The algorithm for the learning of component BNs that we use (Figure starts
from one of two possible initial structures: from a NB model or from a model with all
the variables fully correlated. When considering a NB model as the initial structure,
the heuristic algorithm performs a forward search step (see Figure 8). On the other
hand, when starting from a fully correlated model, the heuristic algorithm performs a
backward search step (see Figure 9).
Notice should be taken that the algorithm of Figure 6 has completed the database
before the structure search step is performed. Consequently, the log marginal likelihood
of the expected complete data has a factorable closed form. The algorithm uses the
factorability of the log marginal likelihood to score every possible change in the model
structure e-ciently.
Learning RBMNs for data clustering
In this section, we present our heuristic algorithm for the learning of RBMNs for data
clustering. This algorithm performs model selection using the log marginal likelihood of
the expected complete data to guide the search. This section starts deriving a factorable
closed form for the marginal likelihood of data for RBMNs.
4.1 Marginal likelihood criterion for RBMNs
Under the assumptions that (i) the variables in the database are discrete, (ii) cases
occur independently, (iii) the database is complete, and (iv) the prior distribution for
the parameters given a structure is uniform, the marginal likelihood of data has a closed
form for BNs that allows us to compute it e-ciently. In particular:
Y
Y
Y
where n is the number of variables, r i is the number of states of the variable X i , q i
is the number of states of the parent set of X i , N ijk is the number of cases in the
database where X i has its k-th value and the parent set of X i has its j-th value, and
(see [12] for a derivation).
This important result is extended to BMNs in [49] as follows: let    ig denote the set of
parameter variables associated with the local probability distribution of the i-th variable
belonging to XnfGg in the g-th component BN. Also, let    denote the set of parameter
variables corresponding to the weights of the mixture of component BNs.
If (i) the parameters variables   ;   are mutually
independent given s h (parameter independence), (ii) the parameter priors p(   ig j s h ) are
conjugate for all i and g, and (iii) the data d is complete, then the marginal likelihood
of data has a factorable closed form for BMNs. In particular:
log p(d j s h
log p(d X;g j b h
where d G is the data restricted to the distinguished variable G, and d X;g is the data
restricted to the variables XnfGg and to those cases in which g. The term p(d G )
is the marginal likelihood of a trivial BN having only a single node G. The terms in the
sum are log marginal likelihoods for the component BNs of the BMN.
Furthermore, this observation extends to RBMNs as follows: let    il denote the set of
parameter variables associated with the local probability distribution of the i-th variable
belonging to XnT(root; l) in the l-th component BN. Also, let L denote the number of
leaves in T and m denote the number of levels (depth) of T. Let    designate the set
1.Start from an empty tree l
2.WHILE stopping condition==FALSE DO
search leaf(l)
where search leaf(l) is
1.IF l is an empty tree or l is a leaf
THEN extension(l)
FOR every child ch of l DO
search leaf(ch)
and extension(l) is as follows
1.FOR every variable Y i in YnT(root; l) DO
b.FOR every state y ik of Y i DO
i.Let d ext;k be the database restricted to the variables
in ext, and to those cases in the database consistent
with t(root; l) and y ik
ii.Learn a component BN from d ext;k for the variables
in ext by means of constructive induction
c.Score the candidate BMN
2.Choose as extension the candidate BMN with the highest score

Figure

10: A schematic of the algorithm for the learning of RBMNs for data clustering.
of parameter variables corresponding to the weights of the mixture of component
BNs. If (i) the parameters variables   ;
are mutually independent given s h (parameter independence), (ii) the parameter priors
are conjugate for all i and l, and (iii) the data d is complete, then the marginal
likelihood of data has a factorable closed form for RBMNs. In particular:
log p(d j s h
[log p(d t(root;l)
l
where d t(root;l) is the database restricted to the variables in T(root; l) and to those
cases consistent with t(root; l), d X;t(root;l) is the database restricted to the variables in
XnT(root; l) and to those cases consistent with t(root; l). The sum of the rst terms
can be easily calculated as the log marginal likelihood of a trivial BN with a single node
with as many states as leaves in the distinguished decision tree T. The second terms in
the sum are log marginal likelihoods for the component BNs of the RBMN. Thus, under
the assumptions referred above, there is a factorable closed form to calculate them [12].
Therefore, the log marginal likelihood of data has a closed form for RBMNs, and it can
be calculated from the log marginal likelihoods of the component BNs. This fact allows
us to decompose the problem of learning a RBMN into learning its component BNs.
Y
Y =y5 52
Y =y
Y
Y =y 11
Y
Y ,Y ,Y

Figure

11: Example of the structure of a 2-levels RBMN for data clustering for
distinguished decision tree T. Dotted lines
correspond to the distinguished decision tree T. The component BN at the leaf l is obtained
as a result of improving by constructive induction the NB model for the variables
XnT(root; l).
4.2 Algorithm for learning RBMNs from incomplete data
The heuristic algorithm that we present in this section performs data clustering by
learning, from incomplete data, RBMNs as they were dened in Section 2.4.
The algorithm starts from an empty distinguished decision tree and, at each iter-
ation, it enlarges the tree in one level until a stopping condition is veried. Stopping
might occur at some user-specied depth, or when no further improvement in the log
marginal likelihood of the expected complete data for the current model (Equation 10) is
observed. To enlarge the current tree, every leaf (component BN) should be extended.
The extension of each leaf l consists of learning the best BMN for XnT(root; l) and
distinguished variable Y i , where Y i 2 YnT(root; l). This BMN replaces the leaf l. For
learning each component BN of the BMN, we use the algorithm presented in Figure 6.

Figure

11 shows an example of a 2-levels RBMN structure that could be the output of
the algorithm that we present in Figure 10.
In this last gure, we can see that the learning algorithm replaces every leaf l by
the best BMN for XnT(root; l) and distinguished variable Y
This is done as follows: let Y i be a variable of YnT(root; l), for every state y ik of Y i ,
the algorithm learns a component BN, b k , for the variables in ext
from an incomplete database d ext;k (the cluster variable is still hidden), where
g. This learning is carried out by the heuristic algorithm that we
have presented in Figure 6. The database d ext;k is a subset of the original database
(instance subspace), in fact, it is the original database d restricted to the variables in
ext, and to those cases consistent with the decision path t(root; l) and y ik . After this
process, we have a candidate BMN with distinguished variable Y i as a possible extension
for the leaf l. Given that Equation 9 provides us with a closed form for the log marginal
likelihood for BMNs, we can use it to score the candidate BMN as follows:
log p(d X;t(root;l) j s h
log p(d ext;k j b h
where d X;t(root;l) is as dened before, d Y i
;t(root;l) is the database restricted to the predictive
attribute Y i and to those cases consistent with t(root; l), d ext;k is as dened
above, and b h
k is the k-th component of the BMN. The rst term can be calculated as
the log marginal likelihood of a trivial BN having only a single node Y i , and the terms
in the sum are calculated using Equation 8. Once all the possible candidate BMNs for
extending the leaf l have been scored, the algorithm performs the extension with the
highest score.
5 Experimental results
This section is devoted to the experimental evaluation of the algorithm for the learning of
RBMNs for data clustering using both synthetic and real-world data. All the variables in
the domains that we considered were discrete, and all the local probability distributions
were multinomial distributions. In all the experiments, we assumed that the real number
of clusters was known, thus, we did not perform a search to identify the number of
clusters in the databases.
As we have already mentioned, currently, our algorithm for learning RBMNs from
incomplete data considers 2 alternative techniques to perform the parameter search for
the component BNs: the EM algorithm and the BC+EM method. According to [40],
the BC+EM method exhibits a more desirable behavior than the EM algorithm: faster
convergence rate, and more eective and robust behavior. Thus, the BC+EM method
was the one used in our experimental evaluation, although we are aware that alternative
techniques exist.
The convergence criterion for the BC+EM method was satised when either the
relative dierence between successive values of the log marginal likelihood for the model
structure was less than 10 6 or 150 iterations were reached. Following [40], we used
fixing probability threshold equal to 0.51.
As shown, the algorithm for the learning of RBMNs runs the algorithm for the learning
of component BNs a large number of times. That is why the runtime of the latter
algorithm should be kept as short as possible. Thus, throughout the experimental evaluation
we did not consider interleaving the parameter search step after each structural
change (Figure 6), though it is an open question as to whether interleaving parameter
and structure search would yield better results. Prior experiments [39] suggest that
interleaved search in our domains, however, do not yield better results. For the same
reason, we only considered the forward structure search step (Figure 8), thus, the initial
structure for each component BN was always a NB model. These decisions were made
based upon the results of the work done in [39].
5.1 Performance criteria
In this section, we describe the criteria of Table 1 that we use to compare the learnt
models and to evaluate the learning algorithm. The log marginal likelihood criterion
was used to select the best model structure. We use this score to compare the learnt
models as well. In addition to this, we consider the runtime as valuable information. We
also pay special attention to the performance of the learnt models in predictive tasks
expression comment
sc initial S n mean  standard deviation of the log marginal likelihood
of the initial model
sc nal S n mean  standard deviation of the log marginal likelihood
of the learnt model
standard deviation of the predictive ability of the
learnt model (10-fold cross-validation)
timeS n mean  standard deviation of the runtime of the learning
process (in seconds)

Table

1: Performance criteria.
(predictive ability). Predictive ability is measured by setting aside a test set. Following
learning, the log likelihood of the test set is measured given the learnt model.
All the experiments were run on a Pentium 366 MHz computer. All the results
reported for the performance criteria are averages over 5 independent runs.
5.2 Results on synthetic data
In this section, we describe our experimental results on synthetic data. Of course, one
of the disadvantages of using synthetic databases is that the comparisons may not be
realistic. However, seeing as the original or gold-standard models are known, they allow
us to show the reliability of the algorithm for the learning of RBMNs from incomplete
data and the improvement achieved by RBMNs over the results scored by BNs.
We constructed 4 synthetic databases (d 1 , d 2 , d 3 , and d 4 ) as follows. In d 1 and
there were 11 predictive attributes involved and 1 4-valued hidden cluster variable.
9 out of the 11 predictive attributes were 3-valued, and the 2 remaining were binary
attributes. To obtain d 1 and d 2 , we simulated 2 1-level RBMNs. Both models had a
distinguished decision tree with only 1 binary predictive attribute. Thus, there were 2
component BNs in each original model. At each of these component BNs several supernodes
were randomly created. The parameters for each local probability distribution of
the component BNs were randomly generated as far as they dened a local multinomial
distribution. Moreover, the weights of the mixture of component BNs were equal that is, the leaves followed a uniform probability distribution. From each of these 2
RBMNs we sampled 8000 cases resulting in d 1 and d 2 , respectively.
On the other hand, in d 3 and d 4 , there were 12 predictive attributes involved and
4-valued hidden cluster variable. 9 out of the 12 predictive attributes were 3-valued,
and the 3 remaining were binary attributes. For getting d 3 and d 4 , we simulated 2
2-levels RBMNs. Both models had a distinguished decision tree with 3 binary predictive
attributes. Thus, there were 4 component BNs in each original model. At each of these
component BNs several supernodes were randomly created. The parameters for each
local probability distribution of the component BNs were randomly generated as far
as they dened a local multinomial distribution. Moreover, the weights of the mixture
of component BNs were equal to 1, that is, the leaves followed a uniform probability
distribution. From each of these 2 RBMNs we sampled 16000 cases resulting in d 3 and
d 4 , respectively. Appendix A shows the structures of the 4 original RBMNs sampled.
Obviously, we discarded all the entries corresponding to the cluster variable for the
4 synthetic databases. Finally, every entry corresponding to a supernode was replaced
with as many entries as original predictive attributes that were grouped together under
database sc initial  S n depth sc nal  S n 10CV  S n timeS n

Table

2: Performance achieved when learning RBMNs for data clustering from the 4
synthetic databases. All the results are averages over 5 independent runs.
this supernode. That is, we \decoded" the Cartesian product of original predictive
attributes for every entry in the database corresponding to a supernode.

Table

2 compares the performance of the learnt RBMNs for dierent values of the
column depth, which represents the depth of the distinguished decision trees. Remember
that BNs were assumed to be a special case of RBMNs where the depth of the
distinguished decision trees was equal to 0. It follows from the table that the algorithm
for learning RBMNs from incomplete data is able to discover the complexity of the underlying
model: in the databases d 1 and d 2 , the models with the highest log marginal
likelihood are those with a 1-level distinguished decision tree, whereas, in the databases
d 3 and d 4 , the learnt RBMNs with the highest log marginal likelihood are those with
a 2-levels distinguished decision tree. Thus, the log marginal likelihood of the expected
complete data appears to behave eectively when used to guide the search, and when
considered as the stopping condition.
The detailed analysis of the RBMN learnt in each of the 5 runs for the 4 synthetic
databases considered suggests that, in general, the variables used to split the original
databases in several instance subspaces (internal nodes of the distinguished decision
trees of the RBMNs sampled) are discovered most of the runs. For instance, all the
runs on d 1 identify Y 1 as the root of the distinguished decision tree. Then, the learnt
RBMNs recover on average 100 % of the true instance subspaces. On the other hand, 3
out of the 5 runs on d 2 discover the true attribute that splits the domain in 2 instance
subspaces which results in an average of 60 % of true instance subspaces discovered. For
out of the 5 runs provide us with a RBMN with Y 12 as the root of the distinguished
decision tree. Moreover, 2 of these 3 runs also identify the rest of true internal nodes
of the original 2-levels RBMN. The third of these 3 runs only discovers 1 of the 2 true
internal nodes of the second level of the distinguished decision tree. Additionally, the
other 2 runs of the 5 on d 3 identify the 3 internal nodes of the distinguished decision
tree of the original RBMN (Y 12 , Y 1 and Y 2 ) but Y 2 appears as the root and, Y 12 and
Y 1 in the second level of the distinguished decision tree. Then, only 2 of the 4 instance
subspaces are eectively discovered in these 2 runs. As a result, the learnt models for
d 3 discover on average 60 % of the 2 main true instance subspaces and 70 % of the 4
more specic true subspaces. For d 4 , 3 out of the 5 runs provide us with a RBMN that
splits the original data in the 4 true instance subspaces. The remainder 2 runs provide
us with RBMNs that have Y 12 as the root of the distinguished decision trees and Y 2 as
1 of the other 2 internal nodes. However, they fail to identify Y 1 as the second node of
the second level of the original distinguished decision tree. Thus, the learnt models for
d 4 discover on average 100 % of the 2 main true instance subspaces and 80 % of the 4
more specic true subspaces.
From the point of view of the predictive task (measured in the 10CV column), we
can report that, in general, the learnt RBMNs outperform BNs. For the databases d 1
and d 2 , the biggest dierence in the predictive ability is reached between the learnt BNs
and the learnt RBMNs with depth equal to 1. Remember that the underlying original
models for these databases were 1-level RBMNs. Furthermore, the learnt 1-level RBMNs
received the highest sc nal . Exactly the same is observed for the synthetic databases d 3
and d 4 , where the biggest increase in the 10CV is reached between the learnt RBMNs
with depth equal to 1 and the learnt RBMNs with 2-levels distinguished decision trees.
Again, note that these 2-levels RBMNs were the models scored with the highest sc nal ,
and that the underlying original models were 2-levels RBMNs.
As the learnt RBMNs have more complex distinguished decision trees, the improvement
of their predictive ability decreases. However, as a general rule, the more complex
the models are, the higher the predictive ability is. This fact is well-known because
10-fold cross-validation scores the log likelihood of the test database, which does not
penalize the complexity of the model, as does the log marginal likelihood. In addition,
as the complexity of the distinguished decision tree increases, the instance subspaces
where to learn the component BNs reduce and, thus, the uncertainty decreases. In order
to avoid very complex models, our results show that the log marginal likelihood is
a suitable score to guide the search for the best RBMN.
From the point of view of the e-ciency (measured as the runtime of the learning pro-
cess), our experimental results show that the learning of RBMNs implies a considerable
computational expense when compared with the learning of BNs. However, this expense
appears justied by the empirical evidence that RBMNs behave more eectively in these
synthetic domains, in addition to their outlined advantages (context-specic conditional
(in)dependencies, structured clustering,
exibility, etc.
5.3 Results on real data
Another source of data for our evaluation consisted of 2 real-world databases from
the UCI machine learning repository [34]: the tic-tac-toe database and the nursery
database. The past usage of the tic-tac-toe database helps to classify it as a paradigmatic
domain for testing constructive induction methods. Despite being used for supervised
classication due to the presence of the cluster variable, we considered this a good
domain to evaluate the performance of our approach once the cluster entries were hidden.
Furthermore, the past usage of the nursery database shows its suitability for testing
constructive induction methods. In addition to this fact, the presence of 5 clusters and
the large number of cases made this database very interesting for our purpose once the
cluster entries were hidden.
The tic-tac-toe database contains 958 cases, each of them represents a legal tic-
tac-toe endgame board. Each case has 9 3-valued predictive attributes and there are
clusters. The nursery database consists of 12960 cases, each of them representing
an application for admission in the public school system. Each case has 8 predictive
attributes, which have between 2 and 5 possible values. There are 5 clusters. Obviously,
database sc initial  S n depth sc nal  S n 10CV  S n timeS n
nursery -57026120 0 -53910709 -6453126 306

Table

3: Performance achieved when learning RBMNs for data clustering from the 2
real-world databases. All the results are averages over 5 independent runs.
for both databases we deleted all the cluster entries.

Table

3 reports on the results achieved when learning RBMNs of dierent depth for
the distinguished decision tree from the 2 real-world databases. For both databases, the
learnt RBMNs outperform the learnt BNs in terms of both log marginal likelihood for
the learnt models and predictive ability. The learnt 1-level RBMNs obtain the highest
score for the log marginal likelihood for both domains. Moreover, these learnt RBMNs
with 1-level distinguished decision trees appear to be more predictive than more complex
models as the learnt RBMNs with 2-levels distinguished decision trees.
6 Conclusions and future research
We have proposed a new approach to perform data clustering based on a new class
of knowledge models: recursive Bayesian multinets (RBMNs). These models may be
learnt to represent the joint probability distribution from a given, complete or incom-
plete, database. RBMNs are a generalization of BNs and BMNs, as well as extensions
to classical partitional systems. Additionally, we have described a heuristic algorithm
for learning RBMNs for data clustering which simplies the learning to the elicitation of
the component BNs from incomplete data. Also, we have presented some of the advantages
derived from the use of RBMNs such as codication of context-specic conditional
(in)dependencies, structured and specialized domain knowledge, alternate clusterings
able to capture dierent patterns for dierent instance subspaces, and
exibility.
Our experimental results in both synthetic and real-world domains have shown that
the learnt RBMNs overcame the learnt BNs in terms of log marginal likelihood and
predictive ability for the learnt model. Moreover, in the synthetic domains, the score to
guide the structural search, the log marginal likelihood of the expected complete data,
has exhibited a suitable behavior as the instance subspaces implied by the underlying
original models have been eectively discovered.
To achieve such a gain there is an obvious increase in the runtime of the learning
process for RBMNs when compared with the learning of BNs. Our current research
is driven to, by means of a simple data preprocessing, reduce the set of the predictive
attributes that are considered to be placed in the distinguished decision tree. This
reduction of the search space would imply a huge save in runtime. Since our primary
aim was to introduce a new knowledge paradigm to perform data clustering, we did not
focus on exploiting all its possibilities. For instance, the denition of RBMNs introduced
in Section 2.4 limits the modelling power of RBMNs since all the leaves had to be at
the same level. This constraint was imposed for the sake of understandability of the
new model but it can be removed in practice resulting in the possibility of obtaining
more natural data clusterings. A limitation of the presented heuristic algorithm for the
learning of RBMNs is its monothetic nature, that is, only single attributes are considered
at each extension of a distinguished decision tree. We are currently considering the
possibility of learning polythetic decision paths in order to enrich the modelling power.
Another line of research that we are investigating is the extension of RBMNs to perform
data clustering in continuous domains. In this case, component BNs would have
to be able to deal with continuous attributes, thus, they would be conditional Gaussian
networks [29, 41, 42]. However, this approach would imply to search for the best discretization
of the attributes to be considered in the decision paths. [41] is an example
of real-world continuous domain where these mentioned extensions of RBMNs to continuous
data could be considered to perform data clustering as dierent patterns are
observed for dierent instance subspaces of the original data. This extension of RBMNs
to continuous domains would decrease the disrupting eects due to the discretization of
the original data that would be necessary to apply RBMNs as dened in this paper to
the problem domain presented in [41].

Acknowledgments

Jose Manuel Pe~na wishes to thank Dr. Dag Wedelin for his interest in this work. He
made the visit at Chalmers University of Technology at Gothenburg (Sweden) possible.
Technical support for this work was kindly provided by the Department of Computer
Science at Chalmers University of Technology.
Also, the authors would like to thank Prof. Douglas H. Fisher in addition to the two
anonymous referees for their useful comments and for addressing interesting readings
related to this work.
This work was supported by the spanish Ministerio de Educacion y Cultura under
AP97 44673053 grant.


Appendix

A
Structures of the original RBMNs sampled in order to obtain
the synthetic databases
Structures of the original 1-level and 2-levels RBMNs sampled to obtain the synthetic
databases. The rst two model structures correspond to the RBMNs sampled to generate
the synthetic databases d 1 (top) and d 2 (bottom), whereas the last two model structures
correspond to the RBMNs sampled to get the synthetic databases d 3 (top) and d 4
(bottom). Dotted lines correspond to the distinguished decision trees. All the predictive
attributes were 3-valued except Y 1 , Y 2 and Y 12 which were binary. The cluster variable
C was 4-valued.
Y =y
Y =y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
=y
Y
=y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
=y
Y
Y
=y
Y
=y
Y111212222
Y
Y
Y
Y
YY
Y
Y
Y
YY
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
YYY
=y
Y
Y
Y 6
Y
Y 41221212
Y
Y
Y 6
Y



--R

Analysis for Applications.
Constructive Induction: The Key to Design Creativity.


Operations for learning with graphical models.

Analyse Typologique.
AutoClass: A Bayesian Classi
Bayesian classi
Learning Bayesian networks is NP-complete

A Bayesian Method for the Induction of Probabilistic Networks from Data.
Maximum Likelihood from Incomplete Data via the EM Algorithm.
Pattern classi
Knowledge Acquisition via Incremental Conceptual Clustering.
Database Management and Analysis Tools of Machine Induction.
The Bayesian structural EM algorithm.
Bayesian network classi
Building Classi
Bayesian network classi
Knowledge representation and inference in similarity networks and Bayesian multinets.
Clustering Algorithms.
Learning Bayesian net- works: The combination of knowledge and statistical data
An introduction to Bayesian networks.
Finding Groups in Data.
Learning Augmented Bayesian Classi
Scaling Up the Accuracy of Naive-Bayes Classi ers: A Decision-Tree Hybrid
Induction of recursive Bayesian classi
Graphical Models.
Some Methods for Classi
The EM Algorithm and Extensions.


UCI repository of machine learning databases.
Pattern Recognition as Knowledge-Guided Computer In- duction
Constructive Induction of Cartesian Product Attributes.
Searching for dependencies in Bayesian classi
Probabilistic Reasoning in Intelligent Systems.
Learning Bayesian networks for clustering by means of constructive induction.
An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering.


Geometric Implications of the Naive Bayes Assumption.

Learning Bayesian Networks from Incomplete Databases.
Parameter Estimation in Bayesian Networks from Incomplete Databases.
Learning Conditional Probabilities from Incomplete Data: An Experimental Comparison.
Bayesian analysis in expert systems.
Learning Mixtures of DAG Models.
Lazy Learning of Bayesian Rules.
--TR
Probabilistic reasoning in intelligent systems: networks of plausible inference
A Bayesian Method for the Induction of Probabilistic Networks from Data
C4.5: programs for machine learning
Learning Bayesian Networks
Knowledge representation and inference in similarity networks and Bayesian multinets
Bayesian classification (AutoClass)
Bayesian Network Classifiers
Efficient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables
Learning Bayesian networks for clustering by means of constructive induction
An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering
Lazy Learning of Bayesian Rules
Clustering Algorithms
Introduction to Bayesian Networks
Expert Systems and Probabiistic Network Models
Knowledge Acquisition Via Incremental Conceptual Clustering
Induction of Recursive Bayesian Classifiers
Bayesian Network Classification with Continuous Attributes

--CTR
J. M. Pea , J. A. Lozano , P. Larraaga, Unsupervised learning of Bayesian networks via estimation of distribution algorithms: an application to gene expression data clustering, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.12 n.SUPPLEMENT, p.63-82, January 2004
Radu Stefan Niculescu , Tom M. Mitchell , R. Bharat Rao, Bayesian Network Learning with Parameter Constraints, The Journal of Machine Learning Research, 7, p.1357-1383, 12/1/2006
J. M. Pea , J. A. Lozano , P. Larraaga, Globally Multimodal Problem Optimization Via an Estimation of Distribution Algorithm Based on Unsupervised Learning of Bayesian Networks, Evolutionary Computation, v.13 n.1, p.43-66, January 2005
bayesian networks;constructive induction;BC+EM method;EM algorithm;bayesian multinets;data clustering