Dimensionality Reduction in Unsupervised Learning of Conditional Gaussian Networks.
AbstractThis paper introduces a novel enhancement for unsupervised learning of conditional Gaussian networks that benefits from feature selection. Our proposal is based on the assumption that, in the absence of labels reflecting the cluster membership of each case of the database, those features that exhibit low correlation with the rest of the features can be considered irrelevant for the learning process. Thus, we suggest performing this process using only the relevant features. Then, every irrelevant feature is added to the learned model to obtain an explanatory model for the original database which is our primary goal. A simple and, thus, efficient measure to assess the relevance of the features for the learning process is presented. Additionally, the form of this measure allows us to calculate a relevance threshold to automatically identify the relevant features. The experimental results reported for synthetic and real-world databases show the ability of our proposal to distinguish between relevant and irrelevant features and to accelerate learning; however, still obtaining good explanatory models for the original database.
Introduction
One of the basic problems that arises in a great variety of elds, including pattern
recognition, machine learning and statistics, is the so-called data clustering problem
[1, 2, 10, 11, 18, 22]. Despite the dierent interpretations and expectations it gives rise
to, the generic data clustering problem involves the assumption that, in addition to the
observed variables (also referred to as predictive attributes or, simply, features), there is
a hidden variable. This last unobserved variable would re
ect the cluster membership
for every case in the database. Thus, the data clustering problem is also referred to
as 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 variable: The hidden cluster variable. That is, we
refer to a given database as incomplete when all the cases are unlabelled.
From the point of view adopted in this paper, the data clustering problem may
be dened as the inference of the generalized joint probability density function for a
given database. Concretely, we focus on learning conditional Gaussian networks for
data clustering [25, 26, 27, 36, 37]. Roughly speaking, a conditional Gaussian network
is a graphical model that encodes a conditional Gaussian distribution [25, 26, 27] for the
variables of the domain. Then, when applied to data clustering, it encodes a multivariate
normal distribution for the observed variables conditioned on each state of the cluster
variable.
As we aim to automatically recover the generalized joint probability density function
from a given incomplete database by learning a conditional Gaussian network, this paper
is concerned with the understanding of data clustering as a description task rather than
a prediction task. Thus, in order to encode a description of the original database, the
learnt model must involve all the original features instead of a subset of them. When
unsupervised learning algorithms focus on prediction tasks, feature selection has proven
to be a valuable technique to increase the predictive ability of the elicited models. In this
paper, we demonstrate that, even when focusing on description, feature selection (also
known as dimensionality reduction) can be a protable tool to improve the performance
of unsupervised learning.
The general framework that we propose to show how unsupervised learning of conditional
Gaussian networks can benet from feature selection is straightforward and consists
of three steps: (i) identication of the relevant features for learning, (ii) unsupervised
learning of a conditional Gaussian network from the database restricted to the relevant
features, and (iii) addition of the irrelevant features to the learnt network to obtain an
explanatory model for the original database. According to this framework, feature selection
is considered a preprocessing step that should be accompanied by a postprocessing
step to fulll our objective. This postprocessing step consists of the addition of every
irrelevant feature to the learnt model to have a nal model that encodes the generalized
joint probability density function for the original data.
To completely dene the framework, one should decide on the automatic dimensionality
reduction scheme to identify the relevant features for learning. This paper
introduces a simple relevance measure to assess the relevance of the features for the
learning process in order to select a subset of them containing the most salient ones.
Additionally, we propose a heuristic method to automatically qualify every feature as
completely relevant or irrelevant for the learning process. This is carried out by the
automatic calculation of a relevance threshold. Those features with relevance measure
values higher than the relevance threshold are considered relevant for the learning pro-
cess, whereas the rest are qualied as irrelevant.
The experimental results reported in this paper show that the framework depicted
above provides us with good explanatory models for the original database reducing the
cost of the learning process as only relevant features are used in this process. In addition
to its eectiveness, the simplicity of the automatic dimensionality reduction scheme that
we propose represents a valuable advantage as it allows the framework to reduce the
dimensionality of the database where to perform learning very e-ciently. Besides, our
scheme is not tied to any particular learning algorithm and, therefore, it can be adapted
to most of them.
The remainder of this paper is organized as follows. In Section 2, we introduce conditional
Gaussian networks for data clustering. Section 3 is dedicated to explain in detail
our automatic dimensionality reduction scheme. We present a new relevance measure
as well as how to automatically discover the relevant and irrelevant features through the
calculation of a relevance threshold. This section also presents how to t our proposal
into unsupervised learning of conditional Gaussian networks under the framework already
outlined. Some experimental results showing the ability of our proposal to identify
the relevant features and to accelerate the learning process are compiled in Section 4.
Finally, we draw conclusions in Section 5.
Conditional Gaussian Networks for Data Cluster-
ing
This section starts introducing the notation used throughout this paper. Then, we give
a formal denition of conditional Gaussian networks. We also present the Bayesian
Structural EM algorithm [13], which is used for explanatory purposes as well as in our
experiments presented in Section 4 due to its good performance in unsupervised learning
of conditional Gaussian networks.
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 boldface upper-case
to designate a set of variables and the same boldface lower-case letter or letters to
denote an assignment of a state to each variable in a given set. The generalized joint
probability density function of X is represented as (x). Additionally,
the generalized conditional probability density function of X given y. If all the
variables in X are discrete, then is the joint probability mass function of X.
Thus, denotes the conditional probability mass function of X given y. On
the other hand, if all the variables in X are continuous, then is the joint
probability density function of X. Thus, f(x j y) denotes the conditional probability
density function of X given y.
2.2 Conditional Gaussian Networks
As we have already mentioned, when facing a data clustering problem we assume the
existence of a random variable X partitioned as
an n-dimensional continuous variable Y and a unidimensional discrete hidden cluster
variable C. X is said to follow a conditional Gaussian distribution [25, 26, 27] if the
distribution of Y, conditioned on each state of C, is a multivariate normal distribution.
That is:
(c) is the n-dimensional mean vector,
and (c), the n  n variance matrix, is positive denite.
We dene a conditional Gaussian network (CGN) for X as a graphical model that
encodes a conditional Gaussian distribution for X [25, 26, 27, 36, 37]. Essentially, CGNs
belong to a class of mixed graphical models introduced for the rst time by Lauritzen
and Wermuth [27], and further developed in [25, 26]. This class groups models in which
both discrete and continuous variables can be present and for which the conditional
distribution of the continuous variables given the discrete variables is restricted to be
multivariate Gaussian. More recently, CGNs have been successfully applied to data
clustering [36, 37].
Concretely, a CGN is dened by a directed acyclic graph s (model structure) determining
the conditional (in)dependencies among the variables of Y, a set of local
probability density functions and a multinomial distribution for the variable C. The
model structure yields to a factorization of the generalized joint probability density
function for X as follows:
Y
where
denotes the conguration of the parents of Y i ,
, consistent with x.
The local probability density functions and the multinomial distribution are those in
the previous equation and we assume that they depend on a nite set of parameters
Therefore, Equation 2 can be rewritten as follows:
Model structure
Multinomial distribution
Local probability density functions
c1
c1
c1
c2
c2
c2

Figure

1: Structure, local probability density functions and multinomial distribution for
a CGN with three continuous variables and one binary cluster variable.
Y
where  c
denotes the parameters for the local probability density functions
when
If s h denotes the hypothesis that the conditional (in)dependence assertions implied
by s hold in the true generalized joint probability density function of X, then we obtain
from Equation 3 that:
Y
In order to encode a conditional Gaussian distribution for X, each local probability
density function of a CGN should be a linear-regression model. Thus, when
normal distribution with mean  and standard deviation
0). Given this form, a missing arc from Y j to Y i implies that b c
the linear-regression model. When the local parameters are  c
(b c
is a column vector.
loop
1. Run the EM algorithm to compute the MAP parameters b
for s l given
2. Perform search over model structures, evaluating each model structure by
l
l
3. Let s l+1 be the model structure with the highest score among these encountered in the search
4. if Score(s l : s l

Figure

2: A schematic of the BS-EM algorithm.
The interpretation of the components of the local parameters  c
follows: Given
i is the unconditional mean of Y i , v c
i is the conditional variance
of Y i given Pa(s) i , and b c
linear coe-cient re
ecting the strength
of the relationship between Y j and Y i . See Figure 1 for an example of a CGN with three
continuous variables and one binary cluster variable.
Note that the model structure is independent of the value of the cluster variable C,
thus, the model structure is the same for all the values of C. However, the parameters
of the local probability density functions do depend on the value of C and they may
dier for the distinct values of the variable C.
2.3 Learning Conditional Gaussian Networks from Incomplete
Data
One of the methods for learning CGNs from incomplete data is the well-known Bayesian
Structural EM (BS-EM) algorithm developed by Friedman in [13]. Due to its good
performance, this algorithm has received special attention in the literature and has
motivated several variants of itself [32, 34, 35, 41]. We use the BS-EM algorithm for
explanatory purposes as well as in our experiments presented in Section 4.
When applying the BS-EM algorithm in a data clustering problem, we assume that
we have a database of N cases, every case is represented by an
assignment to the n observed variables of the involved in the problem
domain. So, there are (n + 1)N random variables that describe the database. Let O
denote the set of observed variables, that is, the nN variables that have assigned values.
Similarly, let H denote the set of hidden or unobserved variables, that is, the N variables
that re
ect the unknown cluster membership of each case of d.
For learning CGNs from incomplete data, the BS-EM algorithm performs a search
over the space of CGNs based on the well-known EM algorithm [7, 29] and direct optimization
of the Bayesian score. As shown in Figure 2, the BS-EM algorithm is comprised
of two steps: An optimization of the CGN parameters and a structural search for model
selection. Concretely, the BS-EM algorithm alternates between a step that nds the
maximum a posteriori (MAP) parameters for the current CGN structure usually by
means of the EM algorithm, and a step that searches over CGN structures. At each
iteration, the BS-EM algorithm attempts to maximize the expected Bayesian score instead
of the true Bayesian score.
As we are interested in solving data clustering problems of considerable size, the
direct application of the BS-EM algorithm as it appears in Figure 2 may be an unrealistic
and ine-cient solution. In our opinion, the reason of this possible ine-ciency is that the
computation of Score(s : s l ) implies a huge computational expense as it takes account
of every possible completion of the database. It is common to use a relaxed version
of the presented BS-EM algorithm that just considers the most likely completion of
the database to compute Score(s : s l ) instead of considering every possible completion.
Thus, this relaxed version of the BS-EM algorithm is comprised of the iteration of a
parametric optimization for the current model, and a structural search once the database
has been completed with the most likely completion by using the best estimate of the
generalized joint probability density function of the data so far (current model). That
is, the posterior probability distribution of the cluster variable C for each case of the
database,
l ), is calculated. Then, the case is assigned to the cluster where
the maximum of the posterior probability distribution of C is reached. We use this
relaxed version in our experiments of Section 4.
To completely specify the BS-EM algorithm, we have to decide on the structural
search procedure (step 2 in Figure 2). The usual approach is to perform a greedy hill-climbing
search over CGN structures considering all possible additions, removals and
reversals of a single arc at each point in the search. This structural search procedure
is desirable as it exploits the decomposition properties of CGNs and the factorization
properties of the Bayesian score for complete data. However, any structural search
procedure that exploits these properties can be used.
The log marginal likelihood of the expected complete data, log (d j s h ), is usually
chosen as the score to guide the structural search. We make use of it in our experiments.
According to [15], under the assumptions that (i) the database restricted to the cluster
variable C, d C , is a multinomial sample, (ii) the database d is complete, and (iii) the
parameters of the multinomial distribution of C are independent and follow a Dirichlet
distribution, we have that:
Y
Y
Y
Y
where d Y; c is the database d restricted to the continuous variables Y and to cases where
is the set of values that the cluster variable C can take. The term
p(d corresponds to the marginal likelihood of a trivial Bayesian network having
only a single node C. It can be calculated in closed form under reasonable assumptions
according to [5]. Moreover, each term of the form f c (d Y; c j s h ), for all c 2 V al(C),
represents the marginal likelihood of a domain containing only continuous variables
under the assumption that the continuous data is sampled from a multivariate normal
distribution. Then, these terms can be evaluated in factorable closed form under some
reasonable assumptions according to [15, 16, 19].
3 Automatic Dimensionality Reduction in Unsupervised
Learning of Conditional Gaussian Networks
This section is devoted to the detailed presentation of a new automatic dimensionality
reduction scheme applied to unsupervised learning of CGNs. The section starts with an
introductory revision on the general problem of feature selection, and a brief discussion
on some of the problems that appear when adapting supervised feature selection to the
unsupervised paradigm.
3.1 From Supervised to Unsupervised Feature Selection
In many data analysis applications the size of the data can be large. The largeness can
be due to an excessive number of features, the huge number of instances, or both. For
learning algorithms to work e-ciently, and even sometimes eectively, one may need to
reduce the data size. Feature selection has proven to be a valuable technique to achieve
such a reduction of the dimensionality of the data by selecting a subset of features on
which to focus the attention in the subsequent learning process.
In its general form, feature selection is considered a problem of searching for an
optimal subset of the original features according to a certain criterion [3, 23, 28]. The
criterion species the details of measuring the goodness of feature subsets as well as
the relevance of each feature. The choice of a criterion is in
uenced by the purpose
of feature selection. However, what is shared by the dierent purposes is the desire
of improving the performance of the subsequent learning algorithm usually in terms of
speed of learning, predictive ability of the learnt models, and/or comprehensibility of
the learnt models.
Roughly speaking, feature selection involves an algorithm to explore the space of
potential feature subsets, and an evaluation function to measure the quality of these
feature subsets. Since the space of all feature subsets of n features has size 2 n , feature
selection mechanisms typically perform a non-exhaustive search. One of the most popular
techniques is the use of a simple hill-climbing search known as sequential selection
which may be either forward or backward [3, 23, 28]. In the former, the search starts
with an empty set of selected features and, at each time, it adds the best feature among
unselected ones according to the evaluation function. The process stops when no further
improvement can be made. Similarly, backward sequential selection begins with the full
set of features and, at each time, it removes the worst feature based on the evaluation
function until no improvement is found. As it is addressed by Doak [9], feature selection
mechanisms based on sequential selection can require a great deal of processing time
in databases with large number of features. Also, more complex and eective search
algorithms can be used to explore the space of potential feature subsets. The main
advantage of these algorithms over sequential selection is that they avoid getting stuck
in local maxima by means of randomness. However, these approaches usually involve
a huge computational eort. One of the recent works in the eld is reported in [20].
In this paper, the authors propose exploring the space of feature subsets according to
an evolutionary, population-based, randomized search algorithm which represents an
instance of the Estimation of Distribution Algorithm (EDA) approach [24].
In [23], the authors distinguish two approaches to the evaluation function for feature
selection: Wrapper and lter. The wrapper approach implies a search for an optimal
feature subset tailored to the performance function of the subsequent learning algorithm.
That is, it considers feedback from the performance function of the particular subsequent
learning algorithm as part of the function to evaluate feature subsets. On the other
hand, the lter approach relies on intrinsic properties of the data that are presumed to
aect the performance of the learning algorithm but they are not a direct function of its
performance. Then, the lter approach tries to assess the merits of the dierent feature
subsets from the data, ignoring the subsequent learning algorithm.
When applied to supervised learning, the main objective of feature selection is the
improvement of the classication accuracy or class label predictive accuracy of the models
elicited by the subsequent learning algorithm considering only the relevant features
for the task. Independently of the approach used, both lter and wrapper approaches
require the class labels to be present in the data in order to carry out feature selection.
Filter approaches evaluate feature subsets usually by assessing the correlation of every
feature with the class label by using dierent measures [3, 28]. On the other hand, wrapper
approaches rely on the performance of the learning algorithm itself by measuring
the classication accuracy on a validation set to evaluate the goodness of the dierent
feature subsets [3, 23, 28]. There is some evidence from supervised feature selection
research that wrapper approaches outperform lter approaches [21].
Although feature selection is a central problem in data analysis as suggested by
the growing amount of research in this area, the vast majority of the research has been
carried out under the supervised learning paradigm (supervised feature selection), paying
little attention to unsupervised learning (unsupervised feature selection). Only a few
works exist addressing the latter problem. In [6], the authors present a method to rank
features according to an unsupervised entropy measure. Their algorithm works as a lter
approach plus a backward sequential selection search. Devaney and Ram [8] proposes
a wrapper approach combined with either a forward or a backward sequential selection
search to perform conceptual clustering. In [39], Talavera introduces a lter approach
combined with a search in one step, and a wrapper approach combined with either
a forward or a backward sequential selection search as feature selection mechanisms in
hierarchical clustering of symbolic data. The lter approach uses the feature dependence
measure dened by Fisher [11]. Whereas the performance criterion considered in [39]
is the multiple predictive accuracy measured by the average accuracy of predicting the
values of each feature present in the testing data, [40] applies the mechanism comprised
of a lter approach and a search in one step presented in [39] to feature selection in
conceptual clustering of symbolic data considering the class label predictive accuracy as
performance criterion.
In our opinion, two are the main problems to translate supervised feature selection
into unsupervised feature selection. Firstly, the absence of class labels re
ecting
the membership for every case in the database that is inherent to the unsupervised
paradigm makes impossible the use of the same evaluation functions as in supervised
feature selection. Secondly, there is not a standard accepted performance task for unsupervised
learning. Due to this lack of a unied performance criterion, the meaning of
optimal feature subset may vary from task to task. A natural solution to both problems
is proposed in [39] by interpreting the performance task of unsupervised learning as the
multiple predictive accuracy. This seems a reasonable approach because it extends the
standard accepted performance task for supervised learning to unsupervised learning.
Whereas the former learning comprises the prediction of only one feature, the class,
from the knowledge of many, the latter aims the prediction of many features from the
knowledge of many [12]. On the other hand, [6, 8, 40] evaluate their unsupervised feature
selection mechanisms by measuring the class label predictive accuracy of the learnt
models over the cases of a testing set after having performed learning in a training set
where the class labels were masked out. The speed of learning and the comprehensibility
of the learnt models are also studied in [8, 39], although they are considered less
important performance criteria.
3.2 How Learning Conditional Gaussian Networks for Data
Clustering Benets from Feature Selection
Our motivation to perform unsupervised feature selection diers from the motivation of
the previously referred papers due to our distinct point of view over the data clustering
problem. When the learnt models for data clustering are primarily evaluated regarding
their multiple or class label predictive accuracy, as it occurs in [6, 8, 39, 40], feature selection
has proven to be a valuable technique to reduce the dimensionality of the database
where to perform learning. This usually pursues an improvement of the performance of
the learnt models considering only the relevant features for the task. However, when
the main goal of data clustering, as it happens in this paper, is description rather than
prediction, the learnt models must involve all the features that the original database
has in order to encode a description of this database.
It is well-known that unsupervised learning of CGNs to solve data clustering problems
is a di-cult and time consuming task, even so more when focusing on description as
all the original features are usually considered in the learning process. With the aim to
solve these handicaps, we propose a framework where learning CGNs for data clustering
benets from feature selection. The framework is straightforward and consists of three
steps: (i) identication of the relevant features for learning, (ii) unsupervised learning
of a CGN from the database restricted to the relevant features, and (iii) addition of the
irrelevant features to the learnt CGN to obtain an explanatory model for the original
database. Thus, feature selection is considered a preprocessing step that should be accompanied
by a postprocessing step to achieve our objective. The postprocessing step
consists of the addition of every irrelevant feature to the elicited model as conditional
independent of the rest given the cluster variable.
To make the framework applicable to unsupervised learning of CGNs, we should
dene relevance. However, the meaning of relevance depends on the particular purpose
of dimensionality reduction due to the lack of a unied performance criterion for data
clustering. In our concrete case, the objective of reducing the dimensionality of the
databases when learning CGNs for data clustering is to decrease the cost of the learning
process while still obtaining good explanatory models for the original data. The
achievement of such a goal can be assessed by comparing, in terms of explanatory power
and runtime of the learning process, a CGN learnt from the given original database and
a CGN elicited when using dimensionality reduction in the learning process.
Such an assessment of the achievement of our objective leads us to make the following
assumption on the consideration of a feature as either relevant or irrelevant for the
learning process: In the absence of labels re
ecting the cluster membership of each case
of the database, those features that exhibit low correlation with the rest of features
can be considered irrelevant for the learning process. Implicitly, this assumption denes
relevance according to our purpose to perform dimensionality reduction. It is important
to note that the assumption is independent of any clustering of the data, so it can be
readily applied without requiring a previous clustering of the database.
The justication of the previous assumption is straightforward. Features low correlated
with the rest are likely to remain conditionally independent of the rest of features
given the cluster variable when learning a CGN from the original database. Thus, a
CGN elicited from the original database restricted to features highly correlated with
the rest is likely to encode the same set of conditional dependence assertions as a CGN
learnt from the original database. The parameters for the local probability density functions
of the features that appear in both CGNs should be similar as well. Furthermore,
if low correlated features are added to that CGN elicited from the restricted database
as conditional independent of the rest given the cluster variable, then this nal CGN
is likely to encode the same set of conditional dependence and independence assertions
as the CGN learnt from the original data. Thus, the explanatory power of both CGNs
should be almost the same as the models are likely to be very similar.
Some other works that have successfully made use of a similar assumption are [11,
39, 40]. Although the three works present the assumption in its general form, they only
validate it for conceptual clustering of symbolic data. Our paper is the rst, to our
knowledge, that veries it for continuous domains.
3.2.1 Relevance Measure
In order to assess the relevance of Y i , evaluating
the following simple and, thus, e-cient relevance measure:
ijjrest
where n is the number of features in the database, N is the number of cases in the
database and r ijjrest is the sample partial correlation of Y i and Y j adjusted for the remainder
variables. This last quantity can be expressed in terms of the maximum likelihood
estimates of the elements of the inverse variance matrix as r ijjrest
Then, the relevance measure value for each feature Y i ,
as the average likelihood ratio test statistic for excluding an edge between Y i and any
other feature in a graphical Gaussian model [38]. This means that those features likely
to remain conditional independent of the rest given the cluster variable as learning
progresses receive low relevance measure values. Thus, this measure shows a reasonable
behavior according to our denition of relevance.
3.2.2 Relevance Threshold
After having calculated the relevance measure value for every feature of the database,
a decreasing relevance ranking of the features can be obtained. Now, we would like to
know how many of them are needed to perform learning appropriately, that is, we would
like to identify, in the relevance ranking, the relevant features for the learning process.
If we knew that only k features were needed, we could simply choose the rst k features
in our relevance ranking, namely, those k features with the highest relevance measure
values. However, to have this kind of knowledge is not at all usual. We propose a novel
and automatic solution for this problem.
The relevance measure value for each feature Y i , interpreted as
the average value of the likelihood ratio test statistic for excluding a single edge between
Y i and any other feature in a graphical Gaussian model. Thus, we propose the following
Evaluate the relevance measure for each feature Y i ,
Calculate the relevance threshold
Let Y Rel be the feature subset containing only the relevant features
loop
1. Run the EM algorithm to compute the MAP parameters b
s Rel
l
for s Rel
l given
2. Perform search over model structures, evaluating each model structure by
l
s Rel
l
l
s Rel
l
l
3. Let s Rel
l+1 be the model structure with the highest score among these encountered in the search
4. exit loop when Score(s Rel
l
l
Let s final be the nal model obtained after adding the irrelevant features to s Rel
l
Calculate the MAP parameters b
s final for s final
Return (s final , b

Figure

3: A schematic of how to t our automatic dimensionality reduction scheme into
the BS-EM algorithm under the framework presented.
heuristic: The relevance threshold is calculated as the rejection region boundary for an
edge exclusion test in a graphical Gaussian model for the likelihood ratio test statistic
(see [38] for details). This heuristic agrees with our purpose to perform dimensionality
reduction as it qualies as irrelevant those features likely to remain conditional independent
of the rest given the cluster variable as learning progresses. As shown in [38],
the distribution function of the likelihood ratio test statistic is as follows:
is the distribution function of a X 2
1 random variable. Thus, for a 5 % test,
the rejection region boundary (which is considered our relevance threshold) is given by
the resolution of the following equation:
By a simple manipulation, the resolution of the previous equation turns into nding the
root of an equation. The Newton-Raphson method, used in our experiments, is only an
example of suitable methods for solving the equation. Only those features that exhibit
relevance measure values higher than the relevance threshold are qualied as relevant
for the learning process. The rest of the features are treated as irrelevant.
3.2.3 Fitting Automatic Dimensionality Reduction into Learning
In this subsection, we present how to t our automatic dimensionality reduction scheme
into the BS-EM algorithm under the general framework previously introduced. However,
it should be noticed that our scheme is not coupled to any particular learning algorithm
and it could be adapted to most of them.

Figure

3 shows that, after the preprocessing step that consists of our automatic
dimensionality reduction scheme, the BS-EM algorithm is applied as usual but restricting
the original database to the relevant features, Y Rel , and the hidden cluster
variable C. That is, the database where to perform learning consists of N cases,

Figure

4: Example of a TANB model structure with seven predictive attributes.
g, where every case is represented by an assignment to the relevant
features. So, there are (r + 1)N random variables that describe the database,
where r is the number of relevant features We denote the set of observed
variables restricted to the relevant features and the set of hidden variables by O Rel
(jO Rel respectively. Obviously, in Figure 3, s Rel
l represents
the model structure when only the relevant features are considered in the learning pro-
cess, and s Rel
l
denotes the hypothesis that the conditional (in)dependence assertions
implied by s Rel
l hold in the true joint probability density function of Y Rel .
Learning ends with the postprocessing step that comprises the addition of every
irrelevant feature to the model returned by the BS-EM algorithm as conditional independent
of the rest given the cluster variable. This results in an explanatory model for
the original database. The local parameters for those nodes of the nal model associated
to the irrelevant features can be easily estimated after completing the original database
d with the last completion of the restricted database d Rel .
4 Experimental Evaluation
This section is dedicated to show the ability of our proposal to perform an automatic
dimensionality reduction that accelerates unsupervised learning of CGNs without degrading
the explanatory power of the nal models. In order to reach such a conclusion,
we perform 2 sorts of experiments in synthetic and real-world databases. The rst evaluates
the relevance measure introduced in Section 3.2.1 as a means to assess the relevance
of the features for the learning process. The second evaluates the ability of the relevance
threshold calculated as it appears in Section 3.2.2 to automatically distinguish between
relevant and irrelevant features for learning.
As we have addressed, we use the BS-EM algorithm as our unsupervised learning
algorithm. In the current experiments, we limit the BS-EM algorithm to learn Tree
Augmented Naive Bayes (TANB) models [14, 30, 36]. This is a sensible and usual
decision to reduce the otherwise large search space of CGNs. Moreover, this allows to
solve e-ciently data clustering problems of considerable size as it is well-known the
di-culty involved in learning densely connected CGNs from large databases, and the
painfully slow probabilistic inference when working with these.
TANB models constitute a class of compromise CGNs dened by the following con-
dition: Predictive attributes may have, at most, one other predictive attribute as a
parent. Figure 4 shows an example of a TANB model structure. TANB models are
CGNs where an interesting trade-o between e-ciency and eectiveness is achieved,
that is, a balance between the cost of the learning process and the quality of the learnt
CGNs [36].
4.1 Databases Involved
There are 2 synthetic and 2 real-world databases involved in our experimental evaluation.
The knowledge of the CGNs used to generate the synthetic databases allows us to assess
accurately the achievement of our objectives. Besides, the real-world databases provide
us with a more realistic evaluation framework.
To obtain the 2 synthetic databases, we constructed 2 TANB models of dierent
complexity to be sampled. The rst TANB model involved 25 predictive continuous
attributes and 1 3-valued cluster variable. The rst 15 of the 25 predictive attributes
were relevant and the rest irrelevant. The 14 arcs between the relevant attributes were
randomly chosen. The unconditional mean of every relevant attribute was xed to 0 for
the rst value of the cluster variable, 4 for the second and 8 for the third. The linear
coe-cients were randomly generated in the interval [-1, 1], and the conditional variances
were xed to 1 (see Equation 5). The multinomial distribution for the cluster variable C
was uniform. Every irrelevant attribute followed a univariate normal distribution with
mean 0 and variance 1 for each of the 3 values of the cluster variable.
The second TANB model involved predictive continuous attributes and 1 3-valued
cluster variable. The rst 15 of the predictive attributes were relevant and the rest
irrelevant. The 14 arcs between the relevant attributes were randomly chosen. The
unconditional mean of every relevant attribute was xed to 0 for the rst value of
the cluster variable, 4 for the second and 8 for the third. The linear coe-cients were
randomly generated in the interval [-1, 1], and the conditional variances were xed
to 2 (see Equation 5). The multinomial distribution for the cluster variable C was
uniform. Every irrelevant attribute followed a univariate normal distribution with mean
0 and variance 5 for each of the 3 values of the cluster variable. This second model
was considered more complex than the rst due to the higher degree of overlapping
between the probability density functions of each of the clusters and the higher number
of irrelevant attributes.
From each of these 2 TANB models, we sampled 4000 cases for the learning databases
and 1000 cases for the testing databases. In the forthcoming, the learning databases
sampled from these 2 TANB models will be referred to as synthetic1 and synthetic2,
respectively. Obviously, we discarded all the entries corresponding to the cluster variable
for the 2 learning databases and the 2 testing databases.
Another source of data for our evaluation consisted of 2 well-known real-world
databases from the UCI repository of Machine Learning databases [33]:
waveform which is an articial database consisting of 40 predictive features. The
last 19 predictive attributes are noise attributes which turn out to be irrelevant
for describing the underlying 3 clusters. We used the data set generator from the
UCI repository to obtain 4000 cases for learning and 1000 cases for testing
pima which is a real database containing 768 cases and 8 predictive features. There
are 2 clusters. We used the rst 700 cases for learning and the last 68 cases for
testing.
The rst database was chosen due to our interest in working with databases of considerable
size (thousands of cases and tens of features). In addition to this, it represented an
opportunity to evaluate the eectiveness of our approach as the true irrelevant features
were known beforehand. The second database, considerably shorter in both number
of cases and number of features, was chosen to get feedback on the scalability of our
dimensionality reduction scheme. Obviously, we deleted all the cluster entries for the 2
learning databases and the 2 testing databases.
4.2 Performance Criteria
There exist 2 essential purposes to focus on the explanatory power or generalizability
of the learnt models. The rst purpose is to summarize the given databases into the
learnt models. The second purpose is to elicit models which are able to predict unseen
instances [28]. Thus, the explanatory power of the learnt CGNs should be assessed
by evaluating the achievement of both purposes. The log marginal likelihood, sc nal,
and the multiple predictive accuracy, L(test), of the learnt CGNs seem to be sensible
performance measures for the rst and the second purpose, respectively. The multiple
predictive accuracy is measured as the logarithmic scoring rule of Good [17]:
jd test j
y2d test
log f(y
where d test is a set of test cases and jd test j is the number of test cases. The higher the
value for this criterion, the higher the multiple predictive accuracy of the learnt CGNs.
Note that L(test) is not the primary performance measure but 1 of the 2 measures to
assess the explanatory power of the learnt CGNs. When focusing on description, L(test)
is extremely necessary to detect models that, suering from overtting, have high sc nal
values although they are not able to generalize the learning data to unseen instances.
It should be noted that Equation 10 represents a kind of probabilistic approach to the
standard multiple predictive accuracy understanding the latter as the average accuracy
of predicting the value of each feature present in the testing data. When the data
clustering problem is considered as the inference of a generalized joint probability density
function from the learning data via unsupervised learning of a CGN, the probabilistic
approach presented in Equation 10 is more appropriate than the standard multiple
predictive accuracy. This can be illustrated with a simple example. Let us imagine 2
dierent CGNs that exhibit the same standard multiple predictive accuracy but dierent
multiple predictive accuracy measured as the logarithmic scoring rule of Good. This
would re
ect that the generalized joint probability density functions encoded by the
2 CGNs are dierent. Moreover, this would imply that 1 of the 2 CGNs generalizes
the learning data to unseen instances better (i.e., the likelihood of the unseen instances
is higher) than the other, although their standard multiple predictive accuracy is the
same. Thus, the standard multiple predictive accuracy would not be an appropriate
performance criterion in this context as it would be unable to distinguish between these
models. Some other works that have made use of the logarithmic scoring rule of Good
to assess the multiple predictive accuracy are [31, 34, 36, 37, 41].
The runtime of the overall learning process, runtime, is also considered as valuable
information. Every runtime reported includes the runtimes of the preprocessing step
(dimensionality reduction), learning algorithm and postprocessing step (addition of the
irrelevant features).
All the results reported are averages over 10 independent runs for the synthetic1,
synthetic2 and waveform databases, and over 50 independent runs for the pima database
due to its shorter size. The experiments are run on a Pentium 366 MHz computer.
features of synthetic12216104relevance503010features of synthetic2251791
relevance3010features of waveform31197relevance1062features of pima7531
Figure

5: Relevance measure values for the features of the databases used. The dashed
lines correspond to the relevance thresholds.
4.3 Results: Relevance Ranking

Figure

5 plots the relevance measure values for the features of each of the 4 databases
considered. Additionally, it shows the relevance threshold (dashed line) for each database.
In the case of the synthetic databases, the 10 true irrelevant features of the synthetic1
database and the 15 of the synthetic2 database clearly appear with the lowest relevance
measure values.
In the case of the waveform database, it may be interesting to compare the graph of

Figure

5 with other graphs reported in [4, 40, 42] for the same database. Caution should
be used as a detailed comparison is not advisable due to the fact that relevance is dened
in dierent ways depending on the particular purpose of each these works. Moreover,
the work by Talavera [40] is limited to conceptual clustering of symbolic data, then, the
original waveform database was previously discretized. However, it is noticeable that
the 19 true irrelevant features appear plotted with low relevance values in the 4 graphs.
Although the shape of the graphs restricted to the 21 relevant features varies for the 3
works reported ([4, 40, 42]), these agree with our graph and consider the rst and last
few of these relevant features less important than the rest of the 21. The shape of our
graph is slightly closer to those that appear in [4, 42] than to the one plotted in [40].
Then, we can conclude that the relevance measure proposed exhibits a desirable
behavior for the databases where the true irrelevant features are known as it clearly
assigns low relevance values to them. The following subsection evaluates if these values
are low enough to automatically distinguish between relevant and irrelevant features
through the calculation of a relevance threshold.

Figure

6 shows the log marginal likelihood (sc nal) and multiple predictive accuracy
number of selected features for synthetic12216104sc_final
-74000
-76000
-78000
-80000
-82000
-84000
-86000
-88000
number of selected features for synthetic12216104L(test)
number of selected features for synthetic2251791
sc_final
-122000
-132000
number of selected features for synthetic2251791
number of selected features for waveform31197sc_final
-122000
number of selected features for waveform31197L(test)
number of selected features for pima7531
sc_final
-9000
number of selected features for pima7531

Figure

log marginal likelihood (sc nal) and multiple predictive accuracy (L(test)) of
the nal CGNs for the databases used as functions of the number of features selected
as relevant from a decreasing relevance ranking.
(L(test)) of the nal CGNs for the 4 databases considered as functions of the number
of features selected as relevant for learning. In addition to this, Figure 7 reports on the
runtime needed to learn the nal CGNs as a function of the number of features selected
number of selected features for synthetic12216104runtime
number of selected features for synthetic2251791
runtime
(seconds)1006020number of selected features for waveform31197runtime
(seconds)2000
number of selected features for pima7531
runtime

Figure

7: Runtime needed to learn the nal CGNs for the databases used as a function
of the number of features selected as relevant from a decreasing relevance ranking.
as relevant for learning. The selection of k features as relevant means the selection of
the k rst features of the decreasing relevance ranking obtained for the features of each
concrete database according to their relevance measure values. Thus, in this rst part of
the experimental evaluation we do not perform an automatic dimensionality reduction.
Instead, we aim to study performance as a function of the number of features involved
in learning. This allows us to evaluate the ability of our relevance measure to assess the
relevance of the features for the learning process.
In general terms, Figure 6 conrms that our relevance measure is able to induce an
eective decreasing relevance ranking of the features of each database considered. That
is, the addition of the features that have low relevance measure values (last features of
the rankings) does not imply a signicant increase in the quality of the nal models,
even in some cases, it hurts the explanatory power. Thus, this gure conrms that the
assumption that low correlated features are irrelevant for the learning process works
very well on the continuous domains considered. On the other hand, the addition of
these irrelevant features tends to increase the cost of the learning process measured as
runtime (see Figure 7).
Particularly interesting are the results for the synthetic databases where the original
models are known. The selection of true irrelevant features to take part in learning does
not produce better models but increases the runtime of the learning process. Also, it is
known that the last 19 of the 40 features of the waveform database are true irrelevant
features. According to the relevance measure values for the features of the waveform
database (see Figure 5), all the 19 true irrelevant features would appear in the last 21
positions of the decreasing relevance ranking. Furthermore, it can be appreciated from

Figure

6 that the addition of these 19 irrelevant features does not signicantly increase

Table

1: Comparison of the performance achieved when learning CGNs from the original
databases and when our automatic dimensionality reduction scheme is applied.
features original dimensionality dimensionality reduction
database original relevant sc nal L(test) runtime sc nal L(test) runtime
synthetic2
the explanatory power of the nal CGNs. The results obtained for the pima database,
where there is no knowledge on the existence of true irrelevant features, share the fact
that using all the features in the learning process degrades the quality of the nal models
as well as making the learning process slower. Thus, the explanatory power of the nal
CGNs appears to be not monotonic with respect to the addition of features as relevant
for learning. Hence the need of automatic tools for discovering irrelevant features that
may degrade the eectiveness and enlarge the runtime of learning.
4.4 Results: Automatic Dimensionality Reduction

Figure

5 shows the relevance threshold (dashed line), calculated as shown in Section 3.2.2,
for each of the databases considered. Only those features that exhibit relevance measure
values higher than the relevance threshold are qualied as relevant. The rest of the
features are considered irrelevant for learning.
It is interesting to notice that, for the 2 synthetic databases, all the true irrelevant
features are identied independently of the complexity of the sampled model. It should
be remembered that the synthetic2 database was sampled from a model more complex
than the one used to generate the synthetic1 database. The results obtained for the
waveform database are also specially appealing as the 19 true irrelevant features are
correctly identied. Moreover, our scheme considers 8 features of the remainder 21
features also as irrelevant. This appears to be a sensible decision as these 8 features
correspond to the rst 4 and the last 4 of the 21 relevant features. Remember that
[4, 40, 42] agree in this point: The rst and last few of the 21 relevant features are less
important than the rest of relevant features.

Table

1 compares, for the 4 databases considered, the performance achieved when
no dimensionality reduction is carried out and the performance achieved when our automatic
dimensionality reduction scheme is applied to learn CGNs. The column relevant
indicates the number of relevant features automatically identied by our scheme for each
database (see Figure 5). It clearly appears from the table that our scheme is able to
automatically set up a relevance threshold that induces a saving in runtime but still
obtaining good explanatory models. The application of our scheme as a preprocessing
step for the BS-EM algorithm (Figure provides us with a saving of runtime over the
original BS-EM algorithm that achieves 22 % for the synthetic1 database and
the synthetic2 database. Moreover, the explanatory power of the CGNs elicited from
the original synthetic databases and the CGNs obtained when using the automatic dimensionality
reduction scheme are exactly the same.
For the waveform database, our automatic dimensionality reduction scheme proposes
a reduction of the number of features of 68 %: Only 13 out of the 40 original features are
considered relevant. This reduction induces a gain in terms of runtime of 58 % whereas
our scheme does not signicantly hurt the quality of the learnt models. On the other
hand, the CGNs learnt with the help of our automatic dimensionality reduction scheme
from the pima database exhibit, on average, a more desirable behavior than the CGNs
elicited from the original pima database: Higher log marginal likelihood and multiple
predictive accuracy whereas the runtime of the learning process is shortened.
Conclusions
The main contribution of this paper is twofold. First, the proposal of a novel automatic
scheme to perform unsupervised dimensionality reduction comprised of (i) a simple and
e-cient measure to assess the relevance of every feature for the learning process, and
(ii) a heuristic to calculate a relevance threshold to automatically distinguish between
relevant and irrelevant features. Second, to present a framework where unsupervised
learning of CGNs benets from our proposed scheme in order to obtain models that describe
the original databases. This framework proposes performing learning taking into
account only the relevant features identied by the automatic dimensionality reduction
scheme presented. Then, every irrelevant feature is incorporated into the learnt model
in order to obtain an explanatory CGN for the original database.
Our experimental results for synthetic and real-world domains have suggested great
advantages derived from the use of our automatic dimensionality reduction scheme in
unsupervised learning of CGNs: A huge decrease of the runtime of the learning process,
and an achievement of nal models that appear to be as good as and, sometimes, even
better than the models obtained using all the features in the learning process. Addi-
tionally, the experimental results have proven that the assumption that we made, once
relevance was dened according to our purpose to perform dimensionality reduction,
works fairly well in the continuous domains considered.
This paper has primarily focused on the gain in e-ciency without degrading the
explanatory power of the nal models derived from the use of the referred scheme as a
preprocessing for the learning process. However, it is worth noticing that the identica-
tion of the relevant and irrelevant features for the learning process allows us to reach a
better comprehensibility and readability of the problem domains and the elicited models.
Few works have addressed the problem of unsupervised feature selection as a pre-processing
step [6, 8, 39, 40]. However, all of them dier from our work. Whereas we
focus on the description of the original database, [6, 8, 40] are interested in the class
label predictive accuracy and [39] in the multiple predictive accuracy. This impossibilities
a fair comparison between these dierent approaches. Moreover, our automatic
dimensionality reduction scheme oers a series of advantages over the other existing
mechanisms. In addition to its simplicity and e-ciency, our scheme is not coupled to
any particular learning algorithm and it could be adapted to most of them. On the
other hand, the existing unsupervised feature selection mechanisms based on wrapper
approaches are tailored to the performance criterion of the particular subsequent learning
algorithm (see [8, 39]) and, thus, usually require a great deal of processing time for
large databases. Furthermore, [6, 40] propose feature selection mechanisms based on l-
ter approaches that only provide the user with a ranking of the features leaving open the
problem of determining how many features should be used to perform a proper learning.
Our scheme is able to automatically distinguish between relevant and irrelevant features
in the relevance ranking. Then, one line of future research could be the extension of our
current contribution to categorical data in order to overcome the problem of determining
the number of features to be used by the subsequent learning algorithm.
We are aware that the contribution presented in this paper is unable to deal properly
with domains where redundant features exist (i.e., features whose values can be
exactly determined from the rest of the features). The reason is that the relevance
measure introduced in Section 3.2.1 scores each feature separately instead of groups of
features. Thus, redundant features would be considered relevant although they would
not provide the learning process with additional information over the true relevant fea-
tures. To detect these features is necessary because they have an eect on the runtime
of the learning process. One of the lines of research that we are currently exploring is
concerned with the extension of the general framework depicted in this paper to the
case where redundant features exist. Our current work is focused on the derivation of a
new relevance measure to assess the gain in relevance of each feature in relation to the
features considered relevant so far.

Acknowledgments

J.M. Pe~na wishes to thank Dr. Steve Ellacott for his interest in this work and his useful
comments. He also made it possible to visit the School of Computing and Mathematical
Sciences of the University of Brighton, Brighton, United Kingdom. The authors would
also like to thank the two anonymous reviewers whose useful comments to a previous
version of this paper have helped us to improve our manuscript.
This work was supported by the Spanish Ministry of Education and Culture (Min-
isterio de Educacion y Cultura) under AP97 44673053 grant.



--R

Analysis for Applications








Pattern Classi







Clustering Algorithms



Finding Groups in Data

Estimation of Distribution Algorithms.



Feature Selection for Knowledge Discovery and Data Mining
The EM Algorithm and Extensions



UCI repository of Machine Learning databases










--TR

--CTR
Martin H. C. Law , Mario A. T. Figueiredo , Anil K. Jain, Simultaneous Feature Selection and Clustering Using Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1154-1166, September 2004
Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004
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
data clustering;edge exclusion tests;conditional Gaussian networks;feature selection