Biology Reference
In-Depth Information
Chapter 8
Faster Algorithms for Constructing a Concept (Galois) Lattice
Vicky Choi
Department of Computer Science, Virginia Tech, USA
vchoi@cs.vt.edu
In this paper, we present a fast algorithm for constructing a concept (Galois)
lattice of a binary relation, including computing all concepts and their lattice
order. We also present two efficient variants of the algorithm, one for computing
all concepts only, and one for constructing a frequent closed itemset lattice. The
running time of our algorithms depends on the lattice structure and is faster than
all other existing algorithms for these problems.
8.1. Introduction
Formal Concept Analysis (FCA) [13] has found many applications since its in-
troduction. As the size of datasets grows, such as data generated from high-
throughput technologies in bioinformatics, there is a need for efficient algorithms
for constructing concept lattices. The input of FCA consists of a triple (
O
,
M
,
I
),
called
context
,where
O
is a set of objects,
M
is a set of attributes, and
I
is a bi-
nary relation between
. In FCA, the context is structured into a set of
concepts
. The set of all concepts, when ordered by set-inclusion, satisfies the
properties of a
complete lattice
. The lattice of all concepts is called
concept
[33]
or
Galois
[4] lattice. When the binary relation is represented as a bipartite graph,
each concept corresponds to a maximal bipartite clique (or maximal biclique).
There is also a one-one correspondence of a closed itemset [37] studied in data
mining and a concept in FCA. The one-one correspondence of all these termi-
nologies - concepts in FCA, maximal bipartite cliques in theoretical computer
science (TCS), and closed itemsets in data mining (DM) - was known [6, 37].
There is extensive work of the related problems in these three communities, in
TCS [1, 6, 10, 14, 15, 20, 28] in FCA [3, 5, 11-13, 16-19, 21-23, 30, 31], and in
DM[2,7,9,24-27, 32, 34-37]. In general, in TCS, the research focuses on effi-
ciently enumerating all maximal bipartite cliques (of a bipartite graph); in FCA,
O
and
M
169
Search WWH ::
Custom Search