Information Technology Reference
In-Depth Information
LEM1 algorithm for computing a single global covering
(
input
:theset
A
of all attributes, partition
}
∗
on
U
;
{
d
output
: a single global covering
R
);
begin
compute partition
A
∗
;
P
:=
A
;
R
:=
∅
;
if
A
∗
≤{
}
∗
d
then
begin
for
each attribute
a
in
A
do
begin
Q
;
compute partition
Q
∗
;
if
Q
∗
≤{
:=
P
−{
a
}
}
∗
then
P
:=
Q
d
end
{for}
R
:=
P
end
{then}
end
{algorithm}.
The time complexity of the algorithm for computing a single global covering is
polynomial. For a set
X
,
|
|
X
denotes the cardinality of
X
.Let
m
be the number of
|
|=
|
|=
all cases, i.e.,
n
.The
time complexity of the algorithm, using a “brute force” approach, in the worst case
scenario, and assuming symbolic attributes, is
O
U
m
, and
n
be the number of all attributes, i.e.,
A
mn
2
. The time complexity of the
algorithm for the attributes with the number of values depending on
m
is
O
(
)
m
2
n
2
.
For the data set from Table
8.2
, the global covering is {
Temperature
,
Headache
}.
The above algorithm is implemented as LEM1 (Learning from Examples Module
version 1). It is a component of the data mining system LERS (Learning from Exam-
ples using Rough Sets). Another, similar approach to rule induction based on feature
selection was presented in [
1
].
The rule set, induced byLEM1 fromthe global covering {
Temperature
,
Headache
}
for the concept (
Flu
,
maybe
), is:
(
(
)
Temperature
,
high
)
and
(
Headache
,
no
)
ₒ
(
Flu
,
maybe
),
(
Temperature
,
normal
)
and
(
Headache
,
yes
)
ₒ
(
Flu
,
maybe
).
8.3 LEM2
An idea of blocks of attribute-value pairs is used in the LEM2 rule induction algorithm
(Learning from Examples Module, version 2), another component of LERS. LEM2
explores the search space of attribute-value pairs. We will quote a few definitions to
describe the LEM2 algorithm [
4
,
11
,
12
,
14
].
Search WWH ::
Custom Search