Information Technology Reference
In-Depth Information
For an attribute-value pair
(
a
,
v
)
,a
block
of
(
a
,
v
)
, denoted by
[
(
a
,
v
)
]
,isthe
following set
{
x
|
x
∈
U
,
a
(
x
)
=
v
}
,
where
a
is the value of the attribute
a
for the case
x
.Let
B
be a nonempty lower or
upper approximation of a concept represented by a decision-value pair
(
x
)
(
d
,
w
)
.Let
T
be a
complex
of
B
, i.e., the set of attribute-value pairs
t
=
(
a
,
v
)
with
a
∈
B
. A block
of
T
, denoted by
[
T
]
, is the following set
∩{[
t
]|
t
∈
T
}
.
Set
B depends
on a set
T
of attribute-value pairs if and only if
∅ =[
T
]=
T
[
t
]ↆ
B
.
t
∈
Set
T
is a
minimal complex
of
B
if and only if
B
depends on
T
and no proper
subset
T
of
T
exists such that
B
depends on
T
.Let
T
be a nonempty collection of
nonempty sets of attribute-value pairs. Then
T
is a
local covering
of
B
if and only
if the following conditions are satisfied:
1. each member
T
of
T
is a minimal complex of
B
,
2.
∪{[
T
]|
T
∈
T
}=
B
, and
T
is minimal, i.e.,
T
has the smallest possible number of elements.
The LEM2 algorithm is presented below.
LEM2 algorithm for computing a single local covering
(
input
:aset
B
,
output
: a single local covering
T
of set
B
);
begin
G
B
;
T
:= ∅
:=
;
while
G
=∅
begin
T
:= ∅
;
T
(
G
)
:= {
t
|[
t
]∩
G
=∅}
;
while
T
=∅
or
[
T
] ↆ
B
begin
select a pair
t
∈
T
(
G
)
such that
|[
t
]∩
G
|
is
maximum; if a tie occurs, select a pair
t
∈
T
(
G
)
with the smallest cardinality of
;
if another tie occurs, select first pair;
T
[
t
]
:=
T
∪{
t
}
;
G
:= [
t
]∩
G
;
Search WWH ::
Custom Search