Information Technology Reference
In-Depth Information
For overlapped class distributions, such that
a<c
≤
b<d
, one computes
⎧
⎨
x
<a
q,
x
b
−
q
b−a
,
x
∈
[
a, c
[
b−x
b−a
+
p
x
−c
P
e
=
P
−
1
+
P
1
=
d−c
,x
∈
(4.19)
q
[
c, b
[
⎩
x
−c
d
x
∈
p
c
,
[
b, d
[
−
p,
x
≥
d
and
⎧
⎨
x
<a
q
ln
q
+
p
ln
p,
+
q
x
−a
b−a
+
p
ln
q
x
−a
b−a
+
p
,
q
b−x
b−a
x
∈
[
a, c
[
ln
q
b−x
b−a
+
p
x
−c
ln
p
x
−c
d−c
+
q
b−x
b−a
+
q
x
−a
b−a
d−c
ln
q
x
−a
d−c
d−c
,
H
S
(
E
)=
⎩
+
p
d−x
+
p
d−x
x
∈
[
c, b
[
b−a
ln
p
x
−c
d
c
+
q
+
p
d−x
c
ln
q
+
p
d−x
c
,x
∈
p
x
−c
d
[
b, d
[
−
c
−
d
−
d
−
x
≥
p
ln
p
+
q
ln
q,
d
(4.20)
where we have used formulas (4.2) and (4.17) and the usual convention
0ln0=0.
Note that both
P
e
and
H
S
are functions of
x
although we omit this de-
pendency for notational simplicity.
Figure 4.2 shows
P
e
and
H
S
as functions of
x
for two different settings. In
Fig. 4.2a min
P
e
is attained for
x
∗
anywhere in [0
.
7
,
1] (where
P
e
is constant),
but error entropy attains its minimum at the extremes of the overlapped
region,
x
∗
=0
.
7 or
x
∗
=1. The reason lies in the decrease of uncertainty (and
consequently of entropy) experimented by the error variable taking only two
values (in
) for those choices of
x
∗
: entropy prefers to correctly
classify one class at the expense of the other. This behavior is general for any
class setting with
b
{−
2
,
0
}
or
{
0
,
2
}
c
. Figure 4.2b illustrates a more general setting,
but again the global minimum of
H
S
(
E
) matches the min
P
e
solution. This
is observed for any class setting, which means that Shannon error entropy
splits are always optimal for uniform distributed classes (for a complete proof
see [216]).
−
a
=
d
−
Example 4.2.
Consider two Gaussian classes with mean
μ
t
and standard de-
viations
σ
t
,for
t
.Then
F
X|t
(
x
)=
x
−∞
∈{−
1
,
1
}
=
Φ
x
−
e
−
(
x
−
μ
t
)
2
1
√
2
πσ
t
μ
t
2
σ
t
(4.21)
σ
t
where
Φ
(
) is the standardized Gaussian CDF. Figure 4.3 shows
H
S
(
E
) and
P
e
as a function of the split point
x
, revealing that entropy has a quite
different behavior depending on the class settings. First, Fig. 4.3a, 4.3b and
·