Databases Reference
In-Depth Information
To decrease the influence of parameter
β
on Battitis MIFS,
55
we consider
a more accurate estimation of the redundant information
Ir
.
Proposition 1:
F
, suppose that the information is
distributed uniformly throughout the regions of
H
(
f
s
),
H
(
f
i
), and
H
(
C
),
44
and that the classes
C
do not change the ratio of entropy of
f
s
to the
mutual information between
f
s
and
f
i
; if all the selected features in
S
are completely independent to each other, the total redundant information
of the candidate feature
f
i
to all the selected features in subset
S
with
respect to output classes
C
, denoted by
I
r
, can be calculated by the simple
summation.
For any
f
s
∈
S
,
f
i
∈
QMIFS
(1) Initialization: Set
F
←
initial set of
n
features,
S
←
empty set.
(2) Computation of the MI with the output class:
∀
f
i
∈
F
, compute
I
(
C
;
f
i
).
(3) Selection the first feature: Find the feature that maximizes
I
(
C
;
f
i
), set
F
f
i
(4) Greedy selection: Repeat until desired numbers of features are selected.
•
←
Ff
i
,S
←
Computation of entropy:
∀f
s
∈
S
, compute
H
(
fs
)ifitisnotyet
available.
•
Computation of the MI between variables: For all couples of features
(
f
i
,f
s
)with
f
i
∈
F
,
f
s
∈
S
, compute
I
(
f
i
,f
s
)and
φ
ik
=
I
(
f
i
;
f
k
)
/H
(
f
k
), if it is not yet available.
•
Selection of the next feature: Choose the feature
f
i
∈
F
that
β
f
i
I
(
f
i
,f
s
)
maximizes
I
(
C
;
f
i
)
−
,set
F
←
Ff
i
,S
←
f
i
.
(5) Output the set S containing the selected features.
8.2.5.
Floating search for feature selection
Exhaustive search is computationally prohibitive. Heuristic search employs
monotonic features i.e., adding a feature to the current set, does not
decrease value of criterion function. But breakdown to sequential search is
structural errors which can cause non-monotonicity.
64,65
So here sequential
search is combined with backtracking to improve accuracy. Here number
of forward and backtracking steps is dynamically controlled. The resulting
feature set are not nested as in (l, r) algorithm, so there is sucient chance
to correct the decision in later steps. In general (l, r) there is no way of
