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