Axiomatic Approach to Feature Subset Selection Based on Relevance.
AbstractRelevance has traditionally been linked with feature subset selection, but formalization of this link has not been attempted. In this paper, we propose two axioms for feature subset selectionsufficiency axiom and necessity axiombased on which this link is formalized: The expected feature subset is the one which maximizes relevance. Finding the expected feature subset turns out to be NP-hard. We then devise a heuristic algorithm to find the expected subset which has a polynomial time complexity. The experimental results show that the algorithm finds good enough subset of features which, when presented to C4.5, results in better prediction accuracy.
Introduction
The problem of feature subset selection (FSS hereafter) has long been an active research topic
within statistics and pattern recognition (e.g., [9]), but most work in this area has dealt with
linear regression. In the past few years, researchers in machine learning have realised (see for
example, [18, 16]) that practical algorithms in supervised machine learning degrade in performance
(prediction accuracy) when faced with many features that are not necessary for predicting the
desired output. Therefore FSS has since received considerable attention from machine learning
researchers interested in improving the performance of their algorithms.
Common machine learning algorithms, including top-down induction of decision trees, such as
CART, ID3, and C4.5, and nearest-neighbour algorithms (such as instance-based learning), are
known to suffer from irrelevant features [18, 19]. A good choice of features may not only help
improve performance accuracy, but also aid in finding smaller models for the data, resulting in
better understanding and interpretation of the data.
Broadly speaking, FSS is to select a subset of features from the feature space which is good
enough regarding its ability to describe the training dataset and to predict for future cases. There
is a wealth of algorithms for FSS (see for example, [2, 15, 1, 17, 14, 24]). With regard to how to
evaluate the goodness of a subset of features, the FSS methods fall into two broad categories: filter
approach and wrapper approach, which are illustrated in Figures 1 and 2. In the filter approach, a
good feature set is selected as a result of pre-processing based on properties of the data itself and
Feature Set Feature Selection Algorithm Learning Algorithm

Figure

1: Filter model.
Feature Set Feature subset evaluation
Feature subset search
Learning Algorithm
Learning Algorithm

Figure

2: Wrapper model.
independent of the induction algorithm. Section 5.1 presents a review on the empirical use of the
notion of goodness in this category.
There is a special type in this approach - feature weighting [15], which is slightly different from
the mainstream filter approach in the way the search for good feature set is conducted. Basically
the mainstream approach evaluates each subset of features and finds the "optimal", while the
weighting approach weighs each individual feature and selects a "quasi-optimal" set of features,
typically those whose weights exceed a given threshold [15, 17].
In the wrapper approach, feature selection is done with the help of induction algorithms. The
feature selection algorithm conducts a search for a good feature set using the induction algorithm
itself as part of the evaluation function. Typically, the feature subset which performs best for the
induction algorithm will be selected.
Both types of approach to FSS are closely related to the notion of relevance. For example,
FOCUS [2], RELIEF [15] and Schlimmer's model [22] use ``relevance'' to estimate the goodness of
feature subset in one way or another. Section 5.2 presents a review in this respect. Although the
wrapper approach does not use the relevance measure directly, it is shown [16] that the "optimal"
feature subset obtained this way must be from the relevant feature set (strongly relevant and weakly
relevant features).
However, the mathematical foundation for FSS is still lacking [26]. In [25], a unified frame-work
for relevance was proposed. In this framework relevance is quantified and related to mutual
information, and furthermore, it was shown that this quantification satisfies the axiomatic characterisations
of relevance laid down by leading researchers in this area. This renders the notion of
relevance having a solid mathematical foundation.
In light of these, we attempt to characterise FSS in terms of the relevance framework, in order
to give FSS a solid foundation for further theoretical study. We then present an algorithm for FSS
based on the relevance characterisation. We also present some experimental results applying this
algorithm to some real world datasets.
2 Characterisation of feature subset selection
In this section we are to characterise FSS in the realm of machine learning, which is confined to
the following sense.
The input to a (supervised) learning algorithm is a training set D of m labelled instances of
a target (concept) Y 1 . Typically D is assumed drawn independently and identically distributed
(i.i.d.) from an unknown distribution over the labelled instance space. An unlabelled instance x is
an element of the n dimensional space is the ith feature (or variable)
in the feature space Labelled instances are tuples ! x; y ? where y is the
label, or output. Let L be a learning algorithm having a hypothesis space H. L maps D to h 2 H
and h maps an unlabelled instance to a label. The task of the learning algorithm is to choose a
hypothesis that best explains the given data D.
In this paper, the training set D will be represented by a relation table r[X
the set of features and Y is the output or target variable. In what follows we will use r[X
denote both the learning task and the training set.
The problem of feature selection is then to search for a subset \Pi of X that not only performs
well on the training dataset, but also predicts well on unseen new cases - it is good enough. Our
objective in this section is to characterise what the best feature subset should be from first principles
as well as some known principles.
2.1 The preservation of learning information
Given a dataset r[X [ Y ], the learning task is to characterise the relationship between X and Y so
that this relationship can be used to predict on future cases (either one in the dataset or a new case).
Therefore any selected feature subset, if it is expected to work well on the given dataset, should
preserve the existing relationship between X and Y hidden in the dataset. A natural measure of
this relationship is the mutual information [7]. We call this relationship learning information.
Specifically, given a learning task r[X [ Y ], the learning information is the mutual information
suppose \Sigma and \Pi are two subsets of X . If I (\Sigma; Y
say that \Sigma and \Pi have the same contribution to the learning task. A sufficient feature set or
simply SFS of a learning task is a subset, \Sigma, of X such that I (\Sigma; Y
contribute the same to the learning task. This is re-stated as the following axiom:
Axiom 2.1 (Preservation of learning information) For a given learning task r[X [ Y ], the
best feature subset, \Pi, should preserve the learning information contained in the training dataset.
That is, I
The following two lemmas follow directly from the chain rule for mutual information and the
non-negativity of mutual information.
Lemma 2.1 Given r[X [ Y ]. For any \Pi ' X, I
From this lemma and the additivity of mutual information [7] we know that given a SFS \Pi,
removing all the remaining features \Sigma will not lose learning information contained in the original
dataset. In other words, Y is conditionally independent of \Sigma given \Pi.
1 Target or target concept is usually defined as a subset of an instance space [2], which can be interpreted as a
bi-partition of the instance space. Here we use it in the more general sense: a target concept is an arbitrary partition
of the instance space. It is regarded as a variable here.
2 In this paper we use X i
to refer to both a variable and the domain of the variable, when this can be identified
from the context.
3 [6, 12]. We use the notation in [12]. A relation scheme R is a set of variables (features). A relation (table) over
R is an indicator function for a set of tuples, written the tuple t is in the relation;
otherwise. For the purpose of this paper, we extend the indicator function such that is the
frequency of tuple t appearing in the relation. With this extension, we can talk about the distribution of the tuples,
which can be easily obtained.
Lemma 2.2 If \Pi is a SFS for a learning task r[X [ Y ], then any superset, \Sigma, of \Pi is also a SFS.
This lemma helps in determining SFSs without having to calculate the learning information. This
property is exploited in the design of an FSS algorithm later.
2.2 The simplest description: Occam's razor
Given a learning task, there may be a number of SFSs. However they may not perform the same on
prediction. The best feature subset should perform best in this respect. However it is not easy to
determine which subset of features predicts better since there is no full knowledge about the future.
Although the dataset is assumed to be drawn i.i.d. from the labelled instance space according to
an unknown distribution, this assumption doesn't help in individual cases. What we can do is to
focus on the training dataset itself and then apply some empirical principles. There are a number
of empirical principles. Occam's razor is one of them.
Occam's razor, known as the principle of parsimony, is a tool that has application in many
areas of science, and it has been incorporated into the methodology of experimental science. This
principle is becoming influential in machine learning, where this principle can be formulated as:
given two hypotheses that both are consistent with a training set of examples of a given task, the
simpler one will guess better on future examples of this task [4, 27, 3]. It has been shown (see for
example, [4]) that, under very general assumptions, Occam's razor produces hypotheses that with
high probability will be predictive of future cases.
One basic question is concerned with the meaning of "simplicity", namely Occam simplicity.
Typically Occam simplicity is associated with the difficulty of implementing a given task, namely
complexity of implementation. For example, the number of hidden neurons in neural networks [3];
the number of leaf nodes of a decision tree [10, 11]; the minimum description length (MDL) [21, 20];
and the encoding length [23]. However, Wolpert [27] noticed that the complexity of implementation
is not directly related to the issue of prediction or generalisation, therefore there is no direct reason
to believe that minimisation of such a complexity measure will result in improvement of general-
isation. Wolpert [27] then derived the uniform simplicity measure, which is concerned exclusively
with how learning generalises. Wolpert showed [27] that when expressed in terms of the uniform
simplicity measure Occam's razor is indeed a way to set up a good generaliser.
The main disadvantage of uniform simplicity measure is that the calculation of it needs "all
learning sets and all questions", as well as guessing distribution and simplicity distribution [27].
This is impossible in practice. It seems that uniform simplicity measures have only theoretical
significance. Fortunately many of the conventional simplicity measures are shown to be rough
approximations to the uniform simplicity measure [27]. In practice we can only rely on approxima-
tions, like those mentioned above.
Back to our problem: Most of the practical simplicity measures (approximations to uniform
simplicity measure) are model-dependent. However we are looking at FSS independently of any
learning model, so a model-independent simplicity measure is required. Entropy seems an ideal
candidate, as it measures the average number of bits (encoding length) to describe a source (e.g.,
a random variable).
Using the entropy as the Occam simplicity measure in our context, we have: given a learning
task r[X [Y ], the Occam's razor dictates the selection of a SFS \Pi which minimises H (\Pi; Y ), where
H is Shannon's entropy function. To make this formal, we re-state it, in conjunction with the
information preservation axiom, as the following axiom:
Axiom 2.2 (Minimum encoding length) Given a learning task r[X [Y ] and a set of sufficient
feature subsets. The one \Pi which minimises the joint should be favoured with
respect to its predictive ability.
Now we set out to characterise the \Pi which minimises the joint entropy.
Lemma 2.3 Given a learning task r[X [ Y ], consider two SFSs \Pi; \Sigma ' X. H
Proof. Since both \Pi and \Sigma are SFSs, by definition we have I (\Pi; Y
Therefore we have H(Y Furthermore we
have
According to this lemma, the most favourable feature subset would be the sufficient one which
has the least marginal entropy.
2.3 Characterisation of feature subset selection in terms of relevance
In the previous two sections we have derived two axiomatic characterisations of FSS: the preservation
of learning information, and minimum encoding length. In this section we are going to show
the above two axioms can all be re-stated in terms of relevance, in an even more concise form.
Given two variables X and Y , by definition (see appendix), the relevance of X to Y is
Therefore for a SFS \Pi ' X , i.e., I (\Pi; Y
preserving learning information amounts to preserving the relevance rela-
general (due to the fact that I (\Pi; Y the \Pi which
preserves learning information in fact maximises the relevance r(X ; Y ).
Consider two SFSs \Pi and \Sigma. Since, by definition, I (\Pi; Y
Therefore,
in conjunction with the previous requirement, the most favourable feature subset would be the
sufficient one which maximises the relevance r(Y ; X).
Summarising the above discussion we have the following theorem:
Theorem 2.1 Given a learning task r[X [ Y ], the most favourable feature subset is the \Pi which
is sufficient (preserving learning information, I (\Pi; Y minimises the joint entropy
Putting it concisely, this is the one which has maximum r(\Pi; Y )
and maximum r(Y ; \Pi).
This theorem formalises the more or less intuitively justified connection between relevance and FSS.
3 A relevance-based algorithm for feature selection
In this section we present a heuristic FSS algorithm which is based on the characterisation in
the previous section. A straightforward algorithm is to systematically examine all feature subsets
and find one which satisfies the above two axioms. Unfortunately, as shown in [8], this class
of algorithms turns out to be NP-complete. Branch and bound based on the characteristics of
relevance was attempted [25], but it was shown to be also exponential in general. So we attempted
heuristic approaches. Here we are to present our preferred heuristic FSS algorithm.
Our objective is to find a sufficient subset of features, which is close to optimal in the above
axiomatic sense. The heuristic used here is: if a feature or attribute is highly relevant on its own, it
it very likely that this feature is in the optimal feature set. Since features are examined individually,
we need to take into account the correlation among individual features. Consider, for example, two
features Y be the target. Suppose r(x 1
x 1 is selected, then x 2 is not needed any more since r(x according to Lemma 6.1. In
other words, x 2 becomes irrelevant given x 1 . Our algorithm should not select them both. To this
end, we design our algorithm, which takes advantage of conditional relevance.
Algorithm 3.1 (CR: feature selection based on conditional relevance) Given a learning
ffl Calculate, for every x 2 X, the relevance r(x; Y ), and find the feature x 0 with largest relevance
ffl Main procedure:
1.
2. Repeat: Add x i to BSFS such that x i is not in BSFS and r(x is the largest
among all possible relevance values.
3. Until r(BSFS; Y
ffl Return BSFS.
Clearly the time complexity for calculating relevance and finding the largest is O(N ). We
now analyse the complexity for the main procedure. At loop k where there are k features left for
inspection, we need to compute conditional relevance r(x features, hence a
complexity of O(k). To find the feature with largest conditional relevance value, we need
comparisons, hence a complexity of O(k \Gamma 1). In the worst case we need to loop from
to hence the complexity is P 1
Therefore the overall complexity for
above algorithm is O(N 2 ).
This algorithm is highly dependent on the choice of the initial set of features, which is the
individual feature most relevant to Y . The BSFS selected by CR is guaranteed to be SFS, but not
guaranteed to be necessary. It is conjectured that if x 0 is in the optimal SFS, then the BSFS found
by CR is indeed optimal.
4 Experiment and evaluation
Here we are to evaluate the performance of the feature selection algorithm presented in the previous
section using some real world datasets. We choose three datasets from the U. C. Irvine
machine learning repository: Australian, Diabetes, and Heart. Some general information about
these datasets is shown in Table 1.
To evaluate the performance of out feature selection algorithm, we chose to use the C4.5 module
in the Clementine package in our experiment. We feed the selected feature subsets to C4.5 and
compare the results with and without feature subset selections.
The test accuracies by C4.5 without and with feature selection are shown in Table 2. The
evaluation method we used is cross validation implemented in Clementine. From these experiment
results we see that applying our feature selection algorithm does indeed improve the test accuracies
for all three datasets, and the corresponding decision trees have smaller sizes. However the success
is limited in the sense that the accuracy improvements were not very great in this case. The
reason is probably that C4.5 has a built-in feature selection facility based on mutual information.
It is then reasonable to believe that if the feature selection algorithm described above is used with
other learning algorithms without built-in feature selection facilities (e.g., nearest neighbour), the
accuracy improvement could be higher than those reported here.
Dataset features no. of examples no. classes class distribution
Australian 14 690 2 44:5%(+)
Diabetes 8 768 2 65:1%(+)
Australian D C C D D D C D D C D D C C
Diabetes C C C C C C C C
Heart C D D C C D D C D C C C D

Table

1: General information about the datasets, where D refers to discrete (here categorical) and
C refers to continuous.
Size of trees Test accuracy Selected features Size of trees Test accuracy
Australian
Diabetes 54 72.9 2,5,6,7,8 42 74.2
Heart

Table

2: Decision tree sizes, test accuracies on decision trees generated by C4.5 without and with
feature selection, together with the selected feature sets. The evaluation method we used is cross
validation implemented in Clementine. The datasets are from the U. C. Irvine machine learning
repository: Australian credit, Diabetes, and Heart.
We also carry out an experiment to inspect the change of accuracies through gradually adding
features in the order of relevance values. We first rank all the features according to their individual
relevance values start evaluation from the one with highest relevance value.
The results are shown in Figure 3. From this figure we can see that as features are gradually added
in the order, the accuracy will on average go up first and reach a peak and then go down. This
diagram justifies to some extent our algorithm, although the algorithm may not always find the
feature subsets corresponding exactly to the peak points.
Another observation from this experiment is that the performance of C4.5 for the three datasets
is (in descending order): Australian, Heart and Diabetes (Table 2) in terms of the average (test)
accuracy, while the percentage of continuous features is in the (descending) order: Diabetes (8/8),
Heart (7/13), and Australian (6/14). It indicates that C4.5 doesn't work as well for continuous
features as for discrete features. Our feature selection algorithm didn't change this situation. In
C4.5, continuous features are treated as discrete features in such a way that their values are divided
into two groups, each of which is a discrete cluster used in the classification. From the granularity
point of view [13], the granularity of the continuous features are made simply too coarse. In our
feature selection algorithm, continuous features are treated as discrete features in such a way that
each continuous value is taken to be a discrete value and is used individually in the classification.
Again the granularity here seems too fine. This points to a direction for future studies: what is the
proper granularity for a continuous feature for use in classification?
Australian
Diabetes
Heart

Figure

3: Accuracy vs. first k features used in the relevance ranking, where k starts from
1. The relevance-based rankings for the three datasets are as follows. Australian:
Diabetes: 7,6,2,5,8,4,1,3; Heart: 5,8,10,13,3,12,1,4,9,11,2,7,6.
5 Comparison with related work
In this section we are to take a closer look at some related work from the relevance point of view
and compare them with ours.
5.1 How is the best feature subset characterised in the literature?
In [15], the best feature subset is characterised as sufficient and necessary to describe the target.
Ideally the sufficiency and necessity requirement is quantified by a measure J (\Pi; Y; D) which evaluates
the feature subset \Pi for the target concept Y and the given data D: the best feature subset
should have the best value of J (\Pi; Y; D). However the nature of the sufficiency and necessity requirement
was not made clear in [15]. In the context of learning from examples, it seems reasonable
that sufficiency concerns the ability of a feature subset to describe the given dataset (called qualified
later on), while the necessity concerns the optimality among all the qualified feature subsets
regarding predictive ability. From this we can say that our two axiomatic characterisations are
possible interpretations of the sufficiency and necessity requirement proposed in [15].
In practice, the best feature subsets are measured in pragmatic ways. For example, in FOCUS
[2] a good feature subset is a minimal subset which is consistent with the training dataset. Here the
consistency can be understood as the sufficiency requirement, since only when the feature subset
is consistent with the given dataset can it qualify to describe the dataset without losing learning
information. The minimality of feature subset can be understood as the necessity requirement, as
it was used as a bias of learning regarding which subset can predict better for future cases. In
RELIEF [15], a good subset is one whose elements each has a relevance level greater than a given
threshold. Here the relevancy and the threshold together determine whether a given feature subset
is sufficient (or qualified) to describe the given dataset. But there is no direct justification as to
why the feature subset determined in this way would perform better in predicting for future cases,
i.e., necessary. In [22] a good subset is one of the minimal determinations, but nothing is mentioned
as to which one is the best. Here all the minimal determinations are sufficient, but which of these
is necessary is left open.
5.2 Re-modelling using the relevance framework
Many FSS algorithms use "relevance" to estimate feature usefulness in one way or another. The
FOCUS [2] algorithm starts with an empty feature set and carries out breadth-first search until
it finds a minimal combination \Pi of features which is consistent with the training dataset. The
features in \Pi are relevant to the target concept C. In terms of the relevance framework [25], this
requirement amounts to r(\Pi; being minimum.
RELIEF is a feature relevance estimation algorithm, but the meaning of relevance is different
from ours and has not been theoretically justified. It associates with each feature a weight indicating
the relative relevance of that feature to the concept class (C) and returns a set of features whose
weights exceed a threshold. This amounts to firstly calculate, for each feature X , r(X ; C), and
then select a set of features such that for any X in this set, r(X ; C) - , where - is the threshold.
Compared to FOCUS, this method is computationally efficient. Furthermore, it allows features to
be ranked by relevance.
Schlimmer [22] described a related approach that carries out a systematic search through the
space of feature sets for all (not just the one with minimal cardinality) minimal determinations
which are consistent with training dataset. The algorithm has an attractive polynomial complexity
due to the space-for-time technique: caching the search path to avoid revisiting states. A determination
is in fact a SFS, and a minimal determination is such a SFS that removing any element will
render it not being a SFS anymore. Therefore this algorithm amounts to finding all SFSs within a
given length such that for each of these, \Pi, r(\Pi;
Most recent research on feature selection differs from these early methods by relying on wrapper
strategies rather than filtering schemes. The general argument for wrapper approaches is that the
induction method that will use the feature subset should provide a better estimate of accuracy
than a separate measure that may have an entirely different inductive bias. John, Kohavi, and
Pfleger [14] were the first to present the wrapper idea as a general framework for feature selection.
The generic wrapper technique must still use some measure to select among alternative features.
One natural scheme involves running the induction algorithm over the entire training data using
a given set of features, then measuring the accuracy of the learned structure on the training data.
However, John et al argue that a cross-validation method, which they use in their implementation,
provides a better measure of expected accuracy on novel test cases.
The major disadvantage of wrapper methods over filter methods is the former's computational
cost, which results from calling the induction algorithm for each feature set considered. This cost
has led some researchers to invent ingenious techniques for speeding the evaluation process.
The wrapper scheme in [16] does not use the relevance measure directly; rather, it uses the
accuracy obtained by applying an induction algorithm as the measure for the goodness of feature
sets. However, Kohavi and Sommerfield show that the "optimal" feature set X obtained this way
must be from the relevant feature set (strongly relevant and weakly relevant features). As shown
in [25] their strong relevance and weak relevance can be characterised by our relevance formalism,
so the wrapper scheme can also be modelled by our relevance, r(X
However, Caruana and Freitag [5] observe that not all features that are relevant are necessarily
useful for induction. They tested FOCUS and RELIEF on the calendar scheduling problem, where
they fed the feature sets obtained by those two algorithms to ID3/C4.5, and found that a more
direct feature selection procedure, hill-climbing in feature space, finds superior feature sets. They
didn't explain the reason for this. But a possible explanation based on relevance is as follows. For
a given concept class C there are many SFS's, where for each SFS, X , 1. One of the
many SFS's, which satisfies some criteria, should be optimal in general. This optimal feature set
may not be the minimal one in general. Starting from Occam's razor, we argue that the optimal
one should be such that r(C; X) is maximised.
In conclusion from the above discussion, RELIEF, Schlimmer's algorithm, and Wrapper take
into account only the sufficiency condition, evidenced by their addressing only r(X ; C). FOCUS
takes into account both sufficiency and necessity conditions. But the necessity is measured by
the cardinality of the feature subset being minimal. The relationship of this measurement to the
Occam's razor characterisation above is not clear yet.
6 Conclusion
In this paper we have derived, from first principles and Occam's razor principle, two axiomatic
requirements for any feature subset to qualify as "good": preservation of learning information and
minimum encoding length. Since FSS has traditionally linked with relevance, we further showed
that when identified with the variable relevance in the unified framework for relevance, relevance
has a direct relationship with FSS: maximising relevance in both ways (i.e.,
will result in the favourable feature subset.
Based on the axiomatic characterisation of FSS, one heuristic FSS algorithm was designed
and presented. This algorithm weights (ranks) features using conditional relevance r(X ; Y jZ) in
a step-wise way: it starts with the feature with the highest unconditional relevance value and
then keeps selecting features with highest conditional relevance values with respect to the current
selected subset. This algorithm can get rid of highly correlated features, and it is shown to have a
complexity of O(n 2 ).
We also presented evaluation results using three real world problems: Australian credit, Diabetes
diagnosis, and Heart diagnosis, all from the UCI machine learning repository. The purpose of the
evaluation is two fold. Firstly, we evaluated the performance of the algorithm. The results are quite
encouraging: the average test accuracies on three datasets were all improved, and the resultant
decision trees had smaller tree sizes. Since C4.5 has a built-in feature selection process, which is
based on gain ratio defined by mutual information, we conjecture that if the algorithm is used with
other learning algorithms without a built-in feature selection process (e.g., nearest neighbour), the
accuracy improvement could be higher.
Secondly, we evaluated the relationship between relevance and learning accuracy. The results
show a strong connection between relevance and learning accuracy. When all features are ranked
according to their conditional relevance values, adding features one by one to the feature set would
lead to a clear pattern of accuracy: first ascending to a peak and then descending gradually.
Therefore we conclude that highly relevant features can improve learning accuracies and highly
irrelevant features can degrade learning accuracies.
As an aside, we observed that C4.5 based learning accuracy (whether or not feature selection is
used) is related to the proportion of continuous features: the higher the proportion of continuous
features, the lower the accuracy. It is argued that one possible reason is that in C4.5 continuous
features are bi-partitioned, which could be too coarse. Future studies in this direction will focus
on developing algorithms to find proper granularities for continuous features.



--R

Feature selection for case-based classification of cloud types
Learning with many irrelevant features.
What size network is good for generalization of a specific task of interest?
Occam's Razor.
How useful is relevance?
A relational model of data for large shared data banks.
Elements of information theory.

Pattern recognition: A statistical approach.
What should be minimized in a decision tree?
The attribute selection problem in decision tree generation.
Relational Databases: A Tutorial for Statisticians.

Irrelevant features and the subset selection problem.
The feature selection problem: traditional methods and a new algorithm.
Feature Subset Selection Using the Wrapper Method: Over-fitting and Dynamic Search Space Topology
Estimating attributes: analysis and extensions of RELIEF.
Selection of relevant features in machine learning.
Machine learning
Inferring decision trees using the minimum description length principle.
Stochastic complexity and modeling.
Efficiently inducing determinations: a complete and systematic search algorithm that uses optimal pruning.
Occam algorithms for computing visual motion.
Prototype and feature selection by sampling and random mutation hill-climbing algorithms
Towards a unified framework of relevance
Computer systems that learn - classification and predication methods from statistics
The relationship between Occam's Razor and convergent guessing.
--TR

--CTR
Xianghong Zhou , Gareth Chelvanayagam , Michael Hallett, Identifying the most significant pairwise correlations of residues in different positions of helices: the subset selection problem using least squares optimization, Proceedings of the 2001 ACM symposium on Applied computing, p.51-55, March 2001, Las Vegas, Nevada, United States
Jong-Min Park, Convergence and Application of Online Active Sampling Using Orthogonal Pillar Vectors, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1197-1207, September 2004
Arno J. Knobbe , Eric K. Y. Ho, Maximally informative k-itemsets and their efficient discovery, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
relevance;knowledge discovery;machine learning;entropy;feature subset selection