Biology Reference
In-Depth Information
8.2. Background and Terminology on FCA
In FCA, a triple (
O
,
M
,
I
) is called a
context
,where
O
=
{
g
1
,g
2
,...,g
n
}
is a set
of
n
elements, called
objects
;
M
=
{
1
,
2
,...,m
}
is a set of
m
elements, called
attributes
;and
is a binary relation. The context is often represented
by a
cross-table
asshowninFig.8.1. Aset
X
I⊆O×M
⊆O
is called an
object set
,anda
set
J
⊆M
is called an
attribute set
. Following the convention, we write an object
set
{
a,c,e
}
as
ace
, and an attribute set
{
1
,
3
,
4
}
as 134.
For
i
∈M
, denote the adjacency list of
i
by
nbr
(
i
)=
{
g
∈O
:(
g,i
)
∈I}
.
Similarly, for
g
∈O
, denote the adjacency list of
g
by
nbr
(
g
)=
{
i
∈M
:(
g,i
)
∈
I}
.
Definition 8.1.
The function
attr
:2
O
−→
2
M
maps a set of objects to their com-
. The function
obj
:2
M
−→
2
O
maps a set of attributes to their common objects:
obj
(
J
)=
mon attributes:
attr
(
X
)=
∩
g∈X
nbr
(
g
),for
X
⊆O
∩
j∈J
nbr
(
j
),for
J
⊆M
.
It is easy to check that for
X
⊆O
,
X
⊆
obj
(
attr
(
X
)),andfor
J
⊆M
,
J
⊆
attr
(
obj
(
J
)).Note
obj
(
∅
)=
O
and
attr
(
∅
)=
M
.
Definition 8.2.
An object set
X
⊆O
is
closed
if
X
=
obj
(
attr
(
X
)). An attribute
set
J
⊆M
is closed if
J
=
attr
(
obj
(
J
)).
The composition of
obj
and
attr
induces a
Galois connection
between 2
O
and
2
M
. Readers are referred to [13] for properties of the Galois connection.
Definition 8.3.
Apair
C
=(
A,B
), with
A
⊆O
and
B
⊆M
, is called a
concept
if
A
=
obj
(
B
) and
B
=
attr
(
A
).
For a concept
C
=(
A,B
),bydefinition, both
A
and
B
are closed. The object
set
A
is called the
extent
of
C
, written as
A
=
ext
(
C
), and the attribute set
B
is called the
intent
of
C
, and written as
B
=
int
(
C
). The set of all concepts of
the context (
O
,
M
,
I
) is denoted by
B
(
O
,
M
,
I
) or simply
B
when the context is
understood.
Let (
A
1
,B
1
) and (
A
2
,B
2
) be two concepts in
B
. Observe that if
A
1
⊆
A
2
,
then
B
2
⊆
B
1
. We order the concepts in
B
by the following relation
≺
:
(
A
1
,B
1
)
≺
(
A
2
,B
2
)
⇐⇒
A
1
⊆
A
2
(
B
2
⊆
B
1
)
.
It is not difficult to see that the relation
≺
is a partial order on
B
. In fact,
L
=
<
B
>
is a complete lattice and it is known as the
concept
or
Galois
lattice of
the context (
,
≺
O
,
M
,
I
).For
C,D
∈B
with
C
≺
D
,ifforall
E
∈B
such that
Search WWH ::
Custom Search