Information Technology Reference
In-Depth Information
({CD, MAGAZINE, NEWSPAPER, VIDEOTAPE, BOOK}, )
Φ
MEDIA
SHOP
free-
c
1
({CD, VIDEOTAPE}, {sound})
timely
paper
sound
distribution
c
2
c
({CD, NEWSPAPER}, {free-distribution})
CD
X
X
({MAGAZINE, NEWSPAPER, BOOK}, {paper})
3
MAGAZINE
X
X
c
4
({MAGAZINE, NEWSPAPER}, {timely, paper})
NEWSPAPER
X
X
X
c
({NEWSPAPER}, {free-distribution, timely, paper})
5
VIDEOTAPE
X
c
({CD}, {free-distribution, sound})
6
BOOK
X
( , {free-distribution, timely, paper, sound})
Φ
(a)
(b)
Fig. 11.
An example relation between objects and attributes.
a
Formal context.
b
Concepts for the formal context.
Note that (3) and (4) imply each other by definition. If we have
c
1
≤ c
2
,then
c
1
is called a
subconcept
of
c
2
and
c
2
is a
superconcept
of
c
1
. For instance, in
Fig. 11b, we have
c
5
≤ c
3
.
The set
L
of all concepts of a given formal context and the partial order
≤
form a complete lattice, called
concept lattice
:
2
O
×
2
A
| A
L
(
C
)=
{
(
O, A
)
∈
=
σ
(
O
)and
O
=
τ
(
A
)
}.
(5)
The
infimum
(
) of two concepts in this lattice is computed by intersecting their
extentsasfollows:
(
O
1
,A
1
)
(
O
2
,A
2
)=(
O
1
∩ O
2
,σ
(
O
1
∩ O
2
))
.
(6)
The infimum describes a set of common attributes of two sets of objects. Simi-
larly, the
supremum
(
) is determined by intersecting the intents:
(
O
1
,A
1
)
(
O
2
,A
2
)=(
τ
(
A
1
∪ A
2
)
,A
1
∪ A
2
)
.
(7)
The supremum yields the set of common objects, which share all attributes in
the intersection of two sets of attributes.
The concept lattice for the formal context in Fig. 11a can be depicted as a di-
rected acyclic graph whose nodes represent the concepts and whose edges denote
the superconcept-subconcept relation
as shown in Fig. 12. Figure 12 is also
called a
line diagram
, which consists the names of all objects and all attributes
of the given context. The nodes represent the concepts and the information of
the context can be read from the diagram by the following simple reading rule:
≤
An object
if and only if there is an upwards
leading path from the node named by
o
has an attribute
a
o
a,
to the node named by
or, dually, with
Search WWH ::
Custom Search