Databases Reference
In-Depth Information
optimal feature subset may not be unique. This approach conducts a search
in the space of possible parameters. A search requires a state space,
28
an initial state, a termination condition and a search engine (either hill
climbing or best first search). For
n
features size of search space is
O
(2
n
).
The drawbacks of wrapper methods are significant as well.
(1) In the mining contest, the number of features with which we have to
deal is quite large when the FS process is carried out as a preprocessing
stage in these mining tasks. The complexity and the execution time
make the task unfeasible.
(2) As the feature selection depends on the classification algorithm, we lose
generality because of the behavior of the classification algorithm
29
in
terms of accuracy and eciency as the good performance of the system
depends directly on the goodness of the classification algorithm chosen.
Furthermore the selection of a classification method slightly suitable for
a certain problem may give rise to choose or eliminate features wrongly.
(3) The combination of the wrapper methods with Soft Computing
30
techniques such as GAS and Neural Networks to carry out the FS
process make it turns into a tough problem especially when the sets of
examples (and/or) features are large.
8.2. Non-Soft Computing Techniques for Feature Selection
In this Section we will discuss few of the classical non-evolutionary
31
feature
selection methods.
8.2.1.
Enumerative algorithms
. All the possible
D
C
d
subsets are evaluated and the
best one among them is chosen. This guarantees the optimal solution,
but the computational time is intractable when the problem size is
not small.
•
Branch and Bound
•
Exhaustive Search
.
32
This algorithm generates a search tree that
identifies the features being removed from the original set. It achieves
a substantial reduction in the number of subset evaluations by pruning
21
those sub trees that will never be superior to the current best solution.
However, the main problem with this algorithm is its exponential time
complexity. Additionally, this algorithm requires the strict assumption of
monotonicity,
33
i.e., adding new features never degrades the performance.
