Biology Reference
In-Depth Information
attribute set (if exists) of
obj
(
XS
). Namely, we first search if
obj
(
XS
) exists by
a set exact matching operation. If it does not, then
XS
is closed. Otherwise, if the
size of the existing attribute set of
obj
(
XS
) is greater than
,then
XS
is not
closed. In our running example, 3 is not closed because
obj
(3) =
ac
has a larger
attribute set 13.
|
XS
|
8.4. Algorithm: Constructing a Concept/Galois Lattice
In this section, we first describe the algorithm in general terms, independent of
the implementation details. We then show how the algorithm can be implemented
efficiently.
8.4.1.
High-Level Idea
Recall that constructing a concept lattice includes generating all concepts and
identifying each concept's successors.
Our algorithm starts with the top concept (
)). We process the con-
cept by computing all its
successors
, and then recursively process each succes-
sor by either the Depth First Search (DFS) order — the ordering obtained by
DFS traversal of the lattice — or Breadth First Search (BFS) order. Accord-
ing to Proposition 8.2, successors of a concept can be computed from its chil-
dren.
O
,
attr
(
O
Let
C
=(
obj
(
X
)
,X
) be a concept.
First, we compute all the chil-
dren
Child
(
C
)=
{
(
obj
(
XS
)
,XS
):
S
∈
AttrChild
(
X
)
}
.
Then for each
S
∈
AttrChild
(
X
), we check if
XS
is closed. If
XS
is closed, (
obj
(
XS
)
,XS
)
is a successor of
C
. Since a concept can have several predecessors, it can be gen-
erated several times. We check its existence to make sure that each concept is
processed once and only once. The pseudo-code of the algorithm based on BFS
is shown in Algorithm 8.1.
Algorithm 8.1.
Concept-Lattice Construction - BFS
Compute the top concept
C
=(
O
,
attr
(
O
));
Initialize a queue
Q
=
{
C
}
;
Compute
Child
(
C
);
while
Q
is not empty
do
C
= dequeue(
Q
);
Let
X
=
int
(
C
) and suppose
AttrChild
(
X
)=
<S
1
,S
2
,...,S
k
>
;
for
i
=1to
k
do
if
XS
i
is closed
then
Denote the concept (
obj
(
XS
i
)
,XS
i
) by
K
;
Search WWH ::
Custom Search