Biology Reference
In-Depth Information
D
implies that
E
=
C
or
E
=
D
,then
C
is called the
successor
a
(or
lower neighbor
)of
D
,and
D
is called the
predecessor
(or
upper neighbor
)of
C
.
The diagram representing an ordered set (where only successors/predecessors are
connected by edges) is called a
Hasse diagram
(or a line diagram). See Fig. 8.1
for an example of the line diagram of a Galois lattice.
For a concept
C
=(
ext
(
C
)
,
int
(
C
)),
ext
(
C
)=
obj
(
int
(
C
)) and
int
(
C
)=
attr
(
ext
(
C
)). Thus,
C
is uniquely determined by either its extent,
ext
(
C
),orby
its intent,
int
(
C
). We denote the concepts restricted to the objects
C
≺
E
≺
O
B
O
=
by
{
ext
(
C
):
C
∈B}
M
B
M
=
{
int
(
C
):
C
∈B}
.
For
A
∈
, and the attributes
by
B
O
, the corresponding concept is (
A,
attr
(
A
)).For
J
∈B
M
, the corresponding
concept is (
obj
(
J
)
,J
). The order
is completely determined by the inclusion
order on 2
O
or equivalently by the reverse inclusion order on 2
M
.Thatis,
≺
L
=
<
B
>
are order-isomorphic. We have the property that
(
obj
(
Z
)
,Z
) is a successor of (
obj
(
X
)
,X
) in
,
≺
>
and
L
M
=
<
B
M
,
⊇
L
if and only if
Z
is a successor
of
X
in
L
M
. Since the set of all concepts is finite, the lattice order relation is
completely determined by the covering (successor/predecessor) relation. Thus,
to construct the lattice, it is sufficient to compute all concepts and identify all
successors of each concept.
8.3. Basic Properties
In this section, we describe some basic properties of the concepts on which our
lattice construction algorithms are based.
Proposition 8.1.
Let
C
be a concept in
B
O
,
M
,
I
)
.For
i
∈M\
int
(
C
)
,if
(
E
i
=
ext
(
C
)
∩
nbr
(
i
)
is not empty,
E
i
is closed. Consequently,
(
E
i
,
attr
(
E
i
))
is
a concept.
Proof.
For
i ∈M\
int
(
C
), suppose that
E
i
=
ext
(
C
)
∩
nbr
(
i
) is not empty. We
will show that
obj
(
attr
(
E
i
)) =
E
i
.Since
E
i
⊆
obj
(
attr
(
E
i
)), it remains to show
that
obj
(
attr
(
E
i
))
⊆
E
i
.Bydefinition,
obj
(
int
(
C
)
∪{
i
}
)=(
∩
j∈
int(
C
)
nbr
(
j
))
∩
nbr
(
i
)=
ext
(
C
)
∩
nbr
(
i
)=
E
i
. Thus, (
int
(
C
)
∪{
i
}
)
⊆
attr
(
obj
(
int
(
C
)
∪{
i
}
)) =
attr
(
E
i
). Consequently,
obj
(
attr
(
E
i
))
⊆
obj
(
int
(
C
)
∪{
i
}
)=
E
i
.
Example.
Consider the concept
C
=(
abcd,
∅
) of context in Fig. 8.1, we have
E
1
=
abc,E
2
=
bd,E
3
=
ac,E
4
=
bd
.
a
Some authors called this as immediate successor.
Search WWH ::
Custom Search