Biology Reference
In-Depth Information
and
denote the set of all concepts. This algorithm can be easily modified to run
in O ( mn ) incremental time [23]. Observe that the space of total size of all con-
cepts is needed if one is to keep the entire structure explicitly. There were several
other algorithms [13, 19], all run in O ( n 2 m ) polynomial delay. There is another
algorithm [31] that is based on divide-and-conquer approach, but the analytical
running time of the algorithm is unknown as it is difficult to analyze.
There are several algorithms in data mining for computing frequent closed
itemsets, such as CHARM(-L) [35, 36], CLOSET(+) [25, 32] and LCM [29].
Boros et al. [6] gave an algorithm with O ( m 2 n ) incremental polynomial running
time, where n =
B
|O|
and m =
|M|
.
Our Results. In this paper, by making use of the lattice structure of concepts,
we present a simple and fast algorithm for computing all concepts together with
its lattice order. The main idea of the algorithm is that given a concept, when
all of its successors are considered together (i.e. in a batch manner), they can be
efficiently computed. We compute concepts in the Breadth First Search (BFS)
order - the ordering given by BFS traversal of the lattice. When computing the
concepts in this way, not only do we compute all concepts but also we identify
all successors of each concept. Another idea of the algorithm is that we make
use of the concepts generated to dynamically update the adjacency relations. The
running time of our algorithm is O ( a∈ ext( C ) | cnbr ( a )
) polynomial delay for
each concept C (see Section 8.2 for related background and terminology), where
cnbr ( a ) is the reduced adjacency list of a . Our algorithm is faster than the best
known algorithms for constructing a lattice because the algorithm is faster than a
basic algorithm that runs in O ( a∈ ext( C ) | nbr ( a )
|
is number of
attributes adjacent to the object a , and this basic algorithm is already as fast as the
current best algorithms for the problem.
We also present two variants of the algorithm: one is computing all concepts
only and another is constructing the frequent closed itemset lattice. Both algo-
rithms are faster than the current start-of-the-art program for these problems.
|
),where
| nbr ( a )
|
Outline. The paper is organized as follows. In Section 8.2, we review some
background and notation on FCA. In Section 8.3, we describe some basic proper-
ties of concepts that we use in our lattice-construction algorithm. In Section 8.4,
we first describe the high level idea of our algorithm. Then we describe how to ef-
ficiently implement the algorithm. In Section 8.5, we describe two variants of the
algorithm. One is for computing all concepts only and another is for constructing
a frequent closed itemset lattice. We conclude with discussion in Section 8.6.
Search WWH ::




Custom Search