=Paper=
{{Paper
|id=None
|storemode=property
|title=A Lattice-Free Concept Lattice Update Algorithm based on *CbO
|pdfUrl=https://ceur-ws.org/Vol-1062/paper22.pdf
|volume=Vol-1062
|dblpUrl=https://dblp.org/rec/conf/cla/Outrata13
}}
==A Lattice-Free Concept Lattice Update Algorithm based on *CbO==
https://ceur-ws.org/Vol-1062/paper22.pdf
A lattice-free concept lattice update algorithm
based on ∗CbO?
Jan Outrata
Dept. Computer Science, Palacky University, Olomouc
17. listopadu 12, CZ-77146 Olomouc, Czech Republic
jan.outrata@upol.cz
Abstract. Updating a concept lattice when introducing new objects to
input data can be done by any of the so-called incremental algorithms for
computing concept lattice of the data. The algorithms use and update
the lattice while introducing new objects one by one. The present concept
lattice of input data without the new objects is thus required before the
update. In this paper we propose an efficient algorithm for updating
the lattice from the present and new objects only, not requiring the
possibly large concept lattice of present objects. The algorithm results
as a modification of the CbO algorithm for computing the set of all formal
concepts, or its modifications like FCbO, PCbO or PFCbO, to compute
new and modified formal concepts only and the changes of the lattice
order relation when input data changes. We describe the algorithm and
present an experimental evaluation of its performance and a comparison
with AddIntent incremental algorithm for computing concept lattice.
1 Introduction
In applications of Formal Concept Analysis (FCA) [3, 16] the input data are often
not fixed during the life of the application and concept lattice is not computed
from the data once. The changes of input data result in corresponding changes
of concept lattice of the data and to compute the new, changed, concept lattice
we would like to compute the changes only and “update” the present lattice
instead of recomputing the whole lattice from new, changed, input data.
The particular change of object-attribute relational data processed in FCA,
namely the introduction of new objects (described by particular values of at-
tributes), can be handled by the so-called incremental algorithms for computing
concept lattice, Norris’s [13], Object Intersections [2] or, more recent, AddIn-
tent [12], for instance, or the incremental lattice update algorithms presented
in [2]. The algorithms build/update the lattice incrementally by adding objects
of input data, one by one, to present concept lattice computed so far from al-
ready processed objects, starting from the first object and empty concept lattice.
?
Support by the ESF project No. CZ.1.07/2.3.00/20.0059, the project co-financed by
the European Social Fund and the state budget of the Czech Republic, is acknowl-
edged.
c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA
2013, pp. 261–274, ISBN 978–2–7466–6566–8, Laboratory L3i, University of La
Rochelle, 2013. Copying permitted only for private and academic purposes.
262 Jan Outrata
The lattice is required for the computation and the present lattice of input data
before the introduction of new objects would be required for the update of the
lattice when adding the objects. However, that lattice can be large, the appli-
cation may not store it (it can be even impossible due to space requirements)
or it can be stored at different (presentation) place than the computation place,
or there can be other drawbacks and difficulties of keeping the whole lattice.
Moreover, handling of the other changes of input data like deletion or alteration
(i.e. changing of values of attributes) of existing objects would call for more
or less (depending on the particular algorithm) extensive modifications of the
incremental algorithm.
In the following we propose efficient algorithm for updating the concept lat-
tice, i.e. computing the lattice changes resulting by input data changes, from
the present (already processed) and new objects only, not requiring the concept
lattice of present objects. The algorithm results as a modification of Kuznetsov’s
Close-by-One (CbO) algorithm [8–10] for computing the set of all formal con-
cepts or any of its recent derivatives including FCbO [14], PCbO [7] or PFCbO [6].
When introducing new objects to input data the modified algorithm computes
and outputs the resulting new and modified formal concepts only and the respec-
tive changes in the lattice order relation (pairs of formal concepts to be created
or deleted). Note that (1) new formal concept here is a concept in new data
with (some of the) introduced objects in its object set (extent) and attribute
set (intent) not equal to intent of any concept in the data before the update
and modified formal concept is a concept in new data with the same intent as
some existing concept in data before update and enlarging its extent by (some
of the) introduced objects, other formal concepts in new data are called old; (2)
since the concept lattice (before update) is not required by the algorithm the
computed changes in the lattice order relation are output only and have to be
applied where the (part of the) lattice is stored and (3) introducing new ob-
jects to input data cannot result in removal of formal concepts from the concept
lattice [4, 15]. Moreover, considering instead the new objects to be some of the
objects of input data to be deleted from the data, the present objects to be the
set of objects of input data after the deletion and the computed formal con-
cepts to be resulting concepts to remove or modify together with the “inverse”
changes of the lattice order relation, we have easily handled also the change of
input data consisting of deleting existing objects. The change by altering objects
can be handled by first deleting the objects and then by introducing the altered
objects, interpreting the output formal concepts accordingly. Finally, changes of
input data by introducing new and deleting or altering existing attributes are
completely analogical and can be handled (better than by altering objects) by
an algorithm re-described with objects and attributes switched or by the present
algorithm with objects and attributes switched in input data (transposed data)
and in output formal concepts.
The algorithm is described in Section 2, for the case of changing input data
by introducing new objects, including an illustrative example. In Section 3 we
present an experimental evaluation of performance of the algorithm and a com-
A lattice-free concept lattice update algorithm based on *CbO 263
parison with AddIntent algorithm [12], which is considered one of the up-to-date
most efficient incremental algorithms for computing concept lattice.
2 The algorithm
We describe the algorithm as a modification of Fast Close-by-One (FCbO) al-
gorithm [14], as it happens to be one of the up-to-date most efficient (sequen-
tial/serial) derivatives of CbO [5]. In essence, the modification equally applies
also to other CbO derivatives and CbO itself. A deep knowledge of FCbO is not
required in the description, however, basic knowledge is beneficial. The modifi-
cation consists of two parts: (1) computing new and modified formal concepts
only when introducing new objects to input data and (2) determining changes
in the lattice order relation. We describe the parts separately in Sections 2.1
and 2.2.
In the descriptions below we assume the reader is familiar with basics of
FCA, see [2, 3] for reference. Input object-attribute data (formal context) is
denoted by the triplet hX, Y, Ii, with assumed finite nonempty sets of objects
X = {0, 1, . . . , m} and attributes Y = {0, 1, . . . , n}, and I ⊆ X × Y being an
incidence relation with hx, yi ∈ I saying that object x ∈ X has attribute y ∈ Y .
Concept-forming operators defined on I as usual [3] are denoted by ↑I : 2X 7→ 2Y
and ↓I : 2Y 7→ 2X , B(X, Y, I) denotes the set of all formal concepts in I and ≤
the partial order relation on B(X, Y, I) forming together a concept lattice.
2.1 New and modified concepts
In this section we describe how to compute new and modified formal concepts
when introducing new objects to input data. Let us suppose we are introducing to
input data hX, Y, Ii (finite nonempty set of) new objects XN = {m + 1, . . . , m0 }
not present in X (XN ∩ X = ∅), sharing (finite nonempty set of) attributes
YN = {i, . . . , k}. We do not assume any overlap of YN and Y (YN can contain new
attributes not present in Y ) but in usual scenario of introducing new objects to
input data we have YN ⊆ Y . Denote the incidence relation between XN and YN
by N ⊆ XN × YN and the new input data with new objects added by the triplet
hX 0 , Y 0 , I 0 i, where X 0 = X ∪ XN = {0, . . . , m0 }, Y 0 = Y ∪ YN = {0, . . . , n0 },
n0 = k if k > n and n0 = n otherwise, and I 0 ⊆ X 0 ×Y 0 such that I 0 ∩(X ×Y ) = I,
I 0 ∩ (XN × YN ) = N and I 0 ∩ (X × (YN \ Y )) = I 0 ∩ (XN × (Y \ YN )) = ∅. Hence
I 0 is the union of I and N both extended to X 0 and Y 0 .
First, observe that attributes of YN which are not shared by any of objects
XN cannot participate in any new nor modified formal concept of B(X 0 , Y 0 , I 0 ),
with the exception of formal concept hY 0↓I 0 , Y 0 i. Hence we will assume in the
following, without loss of generality, that all attributes of YN are shared by at
least one object from XN . For an algorithm for computing new and modified
formal concepts only it is then sufficient to process only attributes YN .
Now, for any B 0 = B ↓I 0 ↑I 0 ⊆ YN , if B 0 = B 00 = B ↓I ↑I then the formal
concept hA0 , B 0 i ∈ B(X 0 , Y 0 , I 0 ) with the same intent B 0 = B 00 as formal con-
cept hA00 , B 00 i ∈ B(X, Y, I) is a modified formal concept enlarging the extent of
264 Jan Outrata
Algorithm 1: Procedure UpdateFastGenerate-
From(hA, Bi, y, {Ny | y ∈ Y }), cf. [14]
// list hA, Bi, e.g., print it on screen or store it
1 if (A ∩ X)↑I 0 = B then
2 if (A ∩ X) ⊂ A then
3 list hA, Bi as modified;
4 end
5 else
6 list hA, Bi as new;
7 end
0 0
8 if B = Y or y > n then
9 return
10 end
0
11 for j from y upto n do
12 set Mj to Nj ;
// go through attributes from YN only
13 if j 6∈ B and j ∈ YN and Nj ∩ Yj ⊆ B ∩ Yj then
14 set C to A ∩ {j}↓I 0 ;
15 set D to C ↑I 0 ;
16 if B ∩ Yj = D ∩ Yj then
17 put hhC, Di, ji to queue;
18 else
19 set Mj to D;
20 end
21 end
22 end
23 while get hhC, Di, ji from queue do
24 UpdateFastGenerateFrom(hC, Di, j + 1, {My | y ∈ Y });
25 end
26 return
hA00 , B 00 i by objects A0 \ A00 ⊆ XN if A0 ⊃ A00 (otherwise hA0 , B 0 i = hA00 , B 00 i
is old). Otherwise, if B 0 ⊂ B 00 = B ↓I ↑I (since the ⊃ inclusion cannot happen
since X 0 ⊃ X) then the formal concept hA0 , B 0 i ∈ B(X 0 , Y 0 , I 0 ) is a new formal
concept and the formal concept hA00 , B 00 i ∈ B(X, Y, I) is called its generator [4,
15]. In both cases, A0 ∩ X = A00 .
We use the above presented ideas to modify FCbO algorithm described in [14]
as recursive procedure FastGenerateFrom. The procedure computes and lists
the set B(X, Y, I) of all formal concepts of input data hX, Y, Ii. We modify
the procedure to compute and list the new and modified formal concepts of
hX 0 , Y 0 , I 0 i only when adding new objects XN described by attributes YN to
hX, Y, Ii. The modified procedure UpdateFastGenerateFrom is depicted in
Algorithm 1. The original procedure FastGenerateFrom is thoroughly de-
scribed in [14] so we describe only the modifications introduced in Update-
FastGenerateFrom.
A lattice-free concept lattice update algorithm based on *CbO 265
The procedure accepts as its arguments a formal concept hA, Bi (an initial
formal concep t), an attribute y ∈ YN (first attribute to be processed) and a
set {Ny ⊆ Y | y ∈ Y } of subsets of attributes Y (see [14] for the meaning of
the set), and uses local variables queue as a temporary storage for computed
formal concepts and My (y ∈ Y ) as sets of attributes which are used in pl ace
of the third argument for further invocations of the procedure. After invocation,
the procedure recursively descends through the space of new and modified for-
mal concepts of hX 0 , Y 0 , I 0 i resulted by adding new objects XN described by
attributes YN to hX, Y, Ii.
When invoked with hA, Bi and y ∈ YN (first attribute to be processed) and
{Ny | y ∈ Y }, UpdateFastGenerateFrom first checks if (A ∩ X)↑I 0 equals B
(line 1), in which case, if further (A∩X) ⊂ A (line 2), hA, Bi is a modified formal
concept (see above) and it is listed as such. In the other case, hA, Bi is a new
formal concept. Then the procedure behaves exactly as the original procedure
FastGenerateFrom, see [14] for full description, with the exception that it
goes through attributes j ∈ YN only (line 13). Let us recall that the set Yj ⊆ Y 0
is defined by
Yj = {y ∈ Y 0 | y < j}.
In order to list all new and modified formal concepts of hX 0 , Y 0 , I 0 i which
are not formal concepts of hX, Y, Ii, each of them exactly once, we invoke Up-
dateFastGenerateFrom with h∅↓I 0 , ∅↓I 0 ↑I 0 i, y being the first attribute in YN
and {Ny = ∅ | y ∈ Y } as its initial arguments. The correctness of Algorithm 1
follows from the correctness of FCbO algorithm [14] and the above description
of its modification.
Example 1. We illustrate Algorithm 1 on the following example. Consider an
input data given in an usual way (rows correspond to objects, columns to at-
tributes and table entries indicate whether an object has an attribute) by the
upper part, rows 0 to 2, of the table depicted below (left). The data induces 8
formal concepts C1 to C8 depicted on the right.
C1 = h{0, 1, 2}, ∅i, C5 = h{0}, {0, 2, 3}i,
C2 = h{0, 2}, {0}i, C6 = h{1, 2}, {1, 5}i,
I 0 1 2 3 4 5 C3 = h{2}, {0, 1, 5}i, C7 = h{1}, {1, 3, 4, 5}i,
0 × × × C4 = h∅, {0, 1, 2, 3, 4, 5}i, C8 = h{0, 1}, {3}i.
1 × × × ×
2 × × × C1∗ = h{0, 1, 2, 3, 4}, ∅i, C6∗ = h{1, 2, 3}, {1, 5}i,
C2∗ = h{0, 2, 4}, {0}i, C11 = h{1, 3}, {1, 3, 5}i,
3 × × ×
4 × × × × C5∗ = h{0, 4}, {0, 2, 3}i, C8∗ = h{0, 1, 3, 4}, {3}i,
C9 = h{4}, {0, 2, 3, 5}i, C12 = h{1, 3, 4}, {3, 5}i,
C10 = h{2, 4}, {0, 5}i, C13 = h{1, 2, 3, 4}, {5}i.
266 Jan Outrata
Now we introduce to the data two new objects represented by rows 3 and
4 of the lower part of the table. The introduction results in induction of 5 new
formal concepts C9 to C13 and 5 modified formal concepts C ∗ depicted below
the old formal concepts. The concepts are listed down-right in order in which
they are listed by procedure UpdateFastGenerateFrom.
Remark 1. Algorithm 1 can be easily used to list all formal concepts of input
data hX 00 , Y 00 , I 00 i incrementally, i.e. processing the data object by object, as in-
cremental algorithms for computing concept lattice do. Namely, we invoke proce-
dure UpdateFastGenerateFrom with initial arguments repeatedly Si−1 for each
object i ∈ X 00 = {0, . . . , n00 }, setting hX, Y, Ii := h{0, . . . , i − 1}, j=0 {j}↑I 00 , I ∩
Si−1
({0, . . . , i − 1} × j=0 {j}↑I 00 )i, XN := {i}, YN := {i}↑I 00 and N := XN × YN
for each invocation, and filter out listed modified formal concepts listing new
formal concepts only. Such a computation of all formal concepts of data is, how-
ever, quite inefficient due to many repeated (though efficient) computations of
formal concepts listed as modified by procedure UpdateFastGenerateFrom,
see the performance evaluation in Section 3. The concepts are, moreover, fil-
tered out from the listing but, however, necessary to compute in order to decide
whether a concept is new or modified. Incremental algorithms iterate over (so
far) incrementally computed and stored concept lattice to decide and compute
new formal concepts which is more efficient. On the other hand, as discussed in
introduction Section 1, the concept lattice is required for the computation and
must be stored by the incremental algorithms, while Algorithm 1 requires input
data only/instead and does not need to store anything.
2.2 Lattice order relation
In this section we describe how to determine the changes in the concept lattice
order relation which need to be done with the addition of new formal concepts
to the lattice. Note that the modified formal concepts cannot raise a change in
the relation since attribute set (intent) of a modified concept remains unchanged
with introduction of new objects to input data, as discussed above.
In order to determine the changes in concept lattice order relation by the
modified FCbO algorithm introduced in previous Section 2.1, we first have to
determine the concept lattice order relation alone since the FCbO algorithm,
as well as the modification, computes the set of formal concepts of input data
only. So, in the following, we describe an extension of Fast Close-by-One (FCbO)
algorithm [14] to determine the concept lattice order relation ≤ on the set of
all formal concepts B(X, Y, I) of input data hX, Y, Ii computed by the original
algorithm, i.e. making an algorithm for computing concept lattice of hX, Y, Ii. In
fact, we will not determine the whole order relation but rather its cover relation.
Recall that the cover relation on B(X, Y, I) for ≤ is defined such that a formal
concept hA2 , B2 i covers a formal concept hA1 , B1 i if hA1 , B1 i ≤ hA2 , B2 i and
there is no formal concept hA3 , B3 i distinct from both hA1 , B1 i and hA2 , B2 i
such that hA1 , B1 i ≤ hA3 , B3 i ≤ hA2 , B2 i, i.e. the cover relation is the transitive
reduct of ≤. And since we do not store and use the computed concept lattice in
A lattice-free concept lattice update algorithm based on *CbO 267
our algorithm for updating the lattice, we will not store and use the computed
formal concepts nor the concept lattice order cover relation in the extended
FCbO algorithm as well. Besides listing the formal concepts, we will only list
the pairs of formal concepts to be created or deleted in the relation at the place
where it is stored.
We now describe how to extend FCbO algorithm, as described in [14], to
determine the concept lattice order cover relation on the set of computed for-
mal concepts, i.e. to compute concept lattice. We can use the pseudocode in
Algorithm 1 if we look apart from the modifications to FCbO introduced there
(the check whether hA, Bi is new or modified formal concept between lines 1
and 6 and going through attributes from YN only at line 12), in which case we
obtain the original procedure FastGenerateFrom from [14]. We will need a
little knowledge of FCbO (or CbO) now. The algorithm, see the pseudocode of
procedure UpdateFastGenerateFrom, computes a formal concept hC, Di =
hA ∩ {j}↓ , (A ∩ {j}↓ )↑ i (lines 14 and 15) from a formal concept hA, Bi for all
attributes j ∈ Y such that y ≤ j ≤ n which are not present in B (lines 12
and 13). Certainly hC, Di ≤ hA, Bi. If hC, Di passes the canonicity test (line 16)
and is listed we list the pair hhC, Di, hA, Bii as to be created in the cover rela-
tion in spite of that the formal concepts in it need not fulfill the definition of
cover relation. We do it since a test for the fulfilment would be too expensive
compared to that in the case of nonfulfilment we will list the pair later again as
to be deleted from the relation.
Next, since further formal concepts hC ∩ {j 0 }↓ , (C ∩ {j 0 }↓ )↑ i are computed
from hC, Di in the next recursive invocation of(Update)FastGenerateFrom
for attributes j 0 ≥ j + 1 (j + 1 is passed in y argument in the invocation,
line 20), in order to list pairs hhE, F i, hC, Dii to be created in the cover re-
lation, we determine formal concepts hE, F i = hC ∩ {i}↓ , (C ∩ {i}↓ )↑ i for all
attributes j − 1 ≥ i ≥ 0 (which are not present in D). Due to the order in which
formal concepts are computed by FCbO, formal concepts hE, F i were already
computed (and listed) in some of the previous stages of the algorithm before
the computation of hC, Di. However, since formal concepts are not stored in
FCbO nor in our extension, we have to compute the concepts hE, F i repeatedly.
Again, formal concepts hE, F i, hC, Di in the pairs need not fulfill the definition
of cover relation. Here, however, we can use a cheap test known from Lindig’s
NextNeighbor algorithm [11], but limited to attributes 0, . . . , j − 1 ∈ Y . The
test is based on the fact that a formal concept hC, Di 6= hY ↓ , Y i covers a for-
mal concept hE, F i = hC ∩ {i}↓ , (C ∩ {i}↓ )↑ i, i 6∈ D iff (C ∩ {k}↓ )↑ = F for
all attributes k ∈ F \ D (cf. Theorem 1 in [11]). If the test passes, we list the
pair hhE, F i, hC, Dii as to be created in the cover relation. We do it even for
formal concepts in the pair which pass the test and do not fulfill the definition
of cover relation due to the limitation of the test to attributes 0, . . . , j − 1 ∈ Y
for the same reason as above for pairs hhC, Di, hA, Bii. To resolve these cases
we simply, together with listing the pair hhE, F i, hC, Dii, list as to be deleted
from the relation the pair hhE, F i, hA, Bii which does not fulfill the definition
of the relation and could have been listed as to be created in the cover rela-
268 Jan Outrata
tion in this or the previous stage (previous recursive invocation of procedure
(Update)FastGenerateFrom) of the extended algorithm. The justification
of this and that all such pairs will be listed as to be deleted from the cover
relation is postponed to the full version of the paper.
The modified procedure LatticeFastGenerateFrom, which implements
the above presented ideas to procedure FastGenerateFrom to extend FCbO
algorithm to determine the concept lattice order cover relation on the set of
formal concepts computed by FCbO, i.e. to compute concept lattice, is depicted
in Algorithm 2. As with the procedure UpdateFastGenerateFrom in Sec-
tion 2.1, we describe only the modifications introduced to FastGenerateFrom.
The original FCbO algorithm remains in essence intact, including its argu-
ments and local variables, all the modifications to original procedure FastGen-
erateFrom are in the computed formal concept hC, Di processing part before
the recursive call of the procedure (line 28), between lines 16 and 29. First note
that the listing of hC, Di moved from the beginning of the procedure (see Algo-
rithm 1) here, resulting effectively in the need to list the formal concept passed
in the initial invocation of the procedure before the invocation. Note also that
this move does not change the order of listed formal concepts. Then, after listing
the pair hhC, Di, hA, Bii as to be created in the cover relation, between lines 18
and 27, formal concepts hE, F i = hC ∩{i}↓ , (C ∩{i}↓ )↑ i, i 6∈ D covered by hC, Di
are re-computed (lines 20 and 21) and listed in pairs hhE, F i, hC, Dii as to be
created in the cover relation, for attributes j − 1 ≥ i ≥ 0. The test of cover-
ing (line 23) is performed using the min local variable in a slightly modified
form borrowed from the original description of Lindig’s NextNeighbor algorithm
in [11]. With listing of hhE, F i, hC, Dii, the pair hhE, F i, hA, Bii is listed as to
be deleted from the cover relation as discussed above.
In order to output concept lattice of hX, Y, Ii, that means to list all for-
mal concepts of hX, Y, Ii, each of them exactly once, together with all pairs of
formal concepts to create or delete (if the pair exists) in order to obtain the
cover relation of concept lattice of hX, Y, Ii, each pair of formal concepts in the
cover relation listed exactly once, we first list h∅↓ , ∅↓↑ i and then invoke Lat-
ticeFastGenerateFrom with h∅↓ , ∅↓↑ i, y = 0 and {Ny = ∅ | y ∈ Y } as its
initial arguments. The correctness of Algorithm 2 follows from the correctness
of FCbO algorithm [14] and the above description of its extension.
Determination of changes in (the cover relation of) concept lattice of hX, Y, Ii
needed to be done in reaction to the introduction of new objects to input data
is then a matter of merging the Algorithms 1 and 2. In addition to that we list,
for each new formal concept hC, Di computed from formal concept hA, Bi (or
hC, Di = h∅↓I 0 , ∅↓I 0 ↑I 0 i) and its generator hE, F i = hC ∩ X, (C ∩ X)↑I 0 i, with
listing of hC, Di also pairs hhF ↓I 0 , F i, hC, Dii as to be created in the cover rela-
tion and hhF ↓I 0 , F i, hA, Bii as to be deleted from the cover relation. The pairs
will then not be listed in the extension introduced in procedure LatticeFast-
GenerateFrom. Due to space limitations of the paper, the merged algorithm
is postponed to the full version of the paper.
A lattice-free concept lattice update algorithm based on *CbO 269
Algorithm 2: Procedure LatticeFastGenerate-
From(hA, Bi, y, {Ny | y ∈ Y }), cf. [14]
1 if B = Y or y > n then
2 return
3 end
4 for j from y upto n do
5 set Mj to Nj ;
6 if j 6∈ B and Nj ∩ Yj ⊆ B ∩ Yj then
7 set C to A ∩ {j}↓ ;
8 set D to C ↑ ;
9 if B ∩ Yj = D ∩ Yj then
10 put hhC, Di, ji to queue;
11 else
12 set Mj to D;
13 end
14 end
15 end
16 while get hhC, Di, ji from queue do
// list hC, Di, e.g., print it on screen or store it
// list hhC, Di, hA, Bii as to be created in the cover relation,
e.g., print C and A (or D and B) on screen or store them
17 set min to Yj ;
18 for i from j − 1 downto 0 do
19 if i 6∈ D then
20 set E to C ∩ {i}↓ ;
21 set F to E ↑ ;
22 set min to min \ {i};
23 if D ∩ Yj ∩ min = F ∩ Yj ∩ min then
// list hhE, F i, hC, Dii as to be created in the cover
relation
// list hhE, F i, hA, Bii as to be deleted from the cover
relation
24 set min to min ∪ {i};
25 end
26 end
27 end
28 LatticeFastGenerateFrom(hC, Di, j + 1, {My | y ∈ Y });
29 end
30 return
Example 2. We illustrate Algorithm 2 and the merged algorithm for the input
data from Example 1. Below (top left) there is depicted concept lattice consisting
of the 8 formal concepts C1 to C8 , with the concepts and pairs of concepts in cover
relation of the lattice, listed in the order in which they are listed by procedure
LatticeFastGenerateFrom, below the lattice.
270 Jan Outrata
Next (to the right) to the lattice there is then the concept lattice and below
the listing of the 8 formal concepts the listing of the 5 new formal concepts
C9 to C13 and changes in the cover relation after the introduction of the two
new objects to the data. The changes are depicted in bold face in the lattice
and the listing of concepts and pairs of concepts in the changes are again listed
down-right in order in which they would be listed by a procedure describing the
merged algorithm.
C1 C1
C8 C2 C13 C8 C2
C6 C5 C6 C12 C5
C10
C3 C11 C3 C9
C7 C7
C4 C4
C1 , C5 : hC5 , C2 i, hC4 , C5 i,
C2 : hC2 , C1 i, C6 : hC6 , C1 i, hC3 , C6 i,
C3 : hC3 , C2 i, C7 : hC7 , C6 i, hC4 , C7 i,
C4 : hC4 , C3 i, C8 : hC8 , C1 i, hC7 , C8 i, hC5 , C8 i.
∗ ∗
C9 : hC9 , C5 i, hC4 , C9 i, C12 : hC12 , C8 i, hC11 , C12 i, hC9 , C12 i,
∗ ∗ ∗
C10 : hC10 , C2 i, hC3 , C10 i, hC9 , C10 i, C13 : hC13 , C1 i, hC6 , C13 i, hC12 , C13 i, hC10 , C13 i.
∗
C11 : hC11 , C6 i, hC7 , C11 i,
3 Experimental evaluation
The asymptotic worst-case time complexity of Algorithm 1 remains the same as
of FCbO (and CbO) algorithm, O(|B(X, Y, I)|·|Y |2 ·|X|), because when “intro-
ducing” all objects to empty data it actually performs FCbO. The complexity
of Algorithm 2 is in the worst case |Y | factor higher but on average it performs
a constant factor slower than FCbO (and ramification of the worst-case time
complexity of FCbO itself remains a challenging open problem [14]).
We have run several experiments to evaluate the performance of Algorithms 1
and 2 and also the merged algorithm. For listing all formal concepts or concept
lattice of input data we also compared the algorithms with AddIntent incre-
mental algorithm [12] for computing concept lattice. In the comparison, we also
run Algorithm 1 and the merged algorithm in the way processing input data
incrementally as mentioned in Remark 1, for the sake of presenting more fair
comparison with true incremental algorithm, though such usage of our algo-
rithms is not efficient (as mentioned in the remark).
In the experiments, we used our implementations of the presented algorithms
in ANSI C, which are modifications of our (performance efficient) FCbO algo-
rithm implementation used for performance evaluation in [14], while the imple-
mentation of AddIntent algorithm was borrowed from one of the authors of [12].
A lattice-free concept lattice update algorithm based on *CbO 271
10 320 30
time (seconds)
time (seconds)
256 24
time (seconds)
8
6 192 18
4 128 12
2 64 6
0 0 0
500 60 70 800 900 1000 10 12 14 16 18 20 0 1 2 3 4 5
attributes fill ratio (%) log(new objects)
Fig. 1. Running time of Algorithm 1 on random data dependent on number of at-
tributes (on the left, introducing a single new object), on fill ratio (percentage of ×s,
in the middle, introducing a single new object) and on number of new objects (on the
right).
1.25 60
time (seconds)
1.25
time (seconds)
time (seconds)
1 48
1 0.75 36
0.75
0.50 24
0.50
0.25 0.25 12
0 0 0
0 0.6 1.2 1.8 2.4 3 0 205 410 615 820 1025 0 205 410 615 820 1025
log(new objects) new objects new objects
Fig. 2. Running time of Algorithm 1 dependent on number of new (last) objects for
mushroom (on the left), anonymous-msweb (in the middle) and T10I4D100K datasets
(on the right), solid line—orig. object ordering, dashed line—random object ordering.
The experiments were run on otherwise idle 32-bit i386 hardware (2× Intel Xeon
3.2 GHz, 3 GB RAM) and we were interested in the performance of all algorithms
measured by running time. We have run the algorithms on synthetic randomly
generated data with various size and percentage of ×s in the table (fill ratio,
with normal distribution) as well as with three selected real benchmark datasets
from the UCI Machine Learning Repository [1].
In the first set of experiments we evaluated Algorithm 1 for updating the set
of all formal concepts (computing new and modified concepts) when introducing
new objects to input data. The performance for introducing a single new ob-
ject (with randomly generated attributes) to random data with 100000 objects
is illustrated in Figure 1. The graphs show the dependency of time required to
compute the update on the number of attributes, of data with fixed table fill
ratio 5 % (the graph on the left) and on the fill ratio of tables with fixed 150
attributes (the graph in the middle). Figure 1 (right) then illustrates the per-
formance for introducing a growing number of new objects to random data with
the number of objects being 100000 minus the number of the new objects, 200
attributes and 5 % table fill ratio. Note that the number of new objects in the
graph is in logarithmic scale. The illustration for the benchmark datasets, of the
performance of introducing a growing number of last objects of the data to the
data without the objects, is presented in Figure 2 (right). In the graph the solid
line is for data with objects ordered as in the original dataset and the dashed
line is for data with randomly ordered objects (the time is an average from three
orderings).
We can see from the graphs showing the performance of updating the set of
all formal concepts when introducing a single new object to the data (Figure 1,
272 Jan Outrata
60 510 60
time (seconds)
408
time (seconds)
time (seconds)
48 48
36 306 36
24 204 24
12 102 12
0 0 0
150 170 190 210 230 250 10 12 14 16 18 20 150 170 190 210 230 250
attributes fill ratio (%) attributes
Fig. 3. Running time dependent on number of attributes (on the left and right) and
on fill ratio (percentage of ×s, in the middle), solid line—Algorithm 2 (left, mid-
dle)/merged algorithm (right), dashed line—AddIntent, dotted line—FCbO (left, mid-
dle)/Algorithm 1 (right).
Table 1. Running time (in seconds) of determining the cover relation of concept lattice
and numbers of formal concepts for selected datasets.
orig. object ordering random object ordering
dataset size fill ratio #concepts
Alg. 2 AddInt. FCbO Alg. 2 AddInt. FCbO
mushroom 8124 × 119 19.167 % 238710 10.010 9.760 0.830 11.025 8.061 0.919
anon. web 32711 × 296 1.019 % 129009 2.860 6.540 1.326 2.841 6.521 1.306
T10I4D100K 100000 × 1000 1.010 % 2347376 453.060 342.966 55.523 452.893 343.056 55.490
left and middle) that this operation is extremely fast compared to computing
all formal concepts which took 7061 seconds for 500 attributes and 355 seconds
for fill ratio 10 %! The reason is of course computing only a bare fraction of
new and modified formal concepts among all concepts. Introducing more new
objects (Figure 1, right, and Figure 2) is much faster too, up to a limit of the
number of new objects depending on the total number of objects in data and
then being close to the time of computing all formal concepts (compare for
benchmark datasets with FCbO times in Table 1). Note also that running times
for mushroom dataset differ for original and random orderings of objects.
In the second set of experiments we evaluated Algorithm 2 for determining
the cover relation of concept lattice of input data. The performance for random
data is illustrated in Figure 3. The graph on the left shows the dependency of
required time on the number of attributes, of data with 10000 objects and fixed
table fill ratio 5 %, the graph in the middle shows the dependency on the fill
ratio of tables with 1000 objects and fixed 100 attributes. The graphs show also
the comparison with AddIntent algorithm and the original FCbO algorithm; the
solid line is for Algorithm 2, the dashed line is for AddIntent and the dotted
line is for FCbO. The performance for the benchmark datasets is presented in
Table 1. Again, the times are given for data with objects ordered as in the original
dataset and for data with randomly ordered objects (the time is an average from
three orderings), and we also put information on size, fill ratio and the number
of all formal concepts for each dataset.
From the graphs we can see that Algorithm 2 considerably outperforms
AddIntent algorithm on synthetic random data (in particular for higher fill ratio
of data table), while for real benchmark datasets this must not always be the
case (T10I4D100K, closely mushroom). This, however, heavily depends on the
concept lattice structure (size of the cover relation) of the datasets. We can also
A lattice-free concept lattice update algorithm based on *CbO 273
Table 2. Running time (in seconds) of computing all formal concepts or concept lattice
when processing input data incrementally and numbers of formal concepts computed
in total for selected datasets.
orig. object ordering random object ordering
dataset #concepts in total
merged alg. AddInt. Alg. 1 merged alg. AddInt. Alg. 1
mushroom 9577435 130.746 9.760 128.993 284.983 8.061 284.130
anon. web 992259 41.386 6.540 41.320 41.342 6.521 41.077
T10I4D100K 14240918 2389.180 342.966 2384.160 2388.793 343.056 2378.703
see from the comparison with FCbO algorithm, as to the rest expected, that
determining the cover relation takes considerably more time than computing
just the set of the formal concepts. Also, ordering of objects in the benchmark
datasets makes almost no difference in the running times.
Finally, the comparison of performance of Algorithm 1 and the merged al-
gorithm with AddIntent, of computing the set of all formal concepts or concept
lattice when processing input data incrementally as mentioned in Remark 1, is
presented in Figure 3 (right) and Table 2. The graph shows the performance
for the data with 10000 objects and fixed table fill ratio 5 % from the preceding
evaluation of Algorithm 2 (the time is an average from three random order-
ings of objects); the solid line is for the merged algorithm, the dashed line is
for AddIntent and the dotted line is for Algorithm 1. In the table we also put,
for our algorithms, for the sake of comparison, the numbers of formal concepts
computed in total (for original ordering of objects in datasets).
The results are really interesting here. For the real benchmark datasets
AddIntent algorithm significantly outperforms our algorithms, see Table 2. This
was expected since, as hinted by Remark 1, the algorithms are not designed and
ment to be used as incremental algorithms (processing objects one by one). What
is, however, very surprising is that on synthetic random data both Algorithm 1
and the merged algorithm considerably outperform AddIntent and, moreover,
computing concept lattice (determining cover relation) takes just a little more
time than computing the set of formal concepts only. It seems that the usage of
the algorithms as incremental algorithms, after all, deserves more attention!
4 Conclusion
We have introduced algorithms for updating the set of all formal concepts of
object-attribute relational data when the data change (new objects or attributes
are introduced or existing are deleted or altered) by computing only new and
modified formal concepts and for determining the concept lattice order relation,
i.e. computing concept lattice of the data. Together the algorithms form an algo-
rithm for updating concept lattice of object-attribute data from the data only,
not requiring the possibly large concept lattice computed before the update as
the so-called incremental (update) algorithms do. The algorithms result as mod-
ification or extension of FCbO algorithm for computing the set of all formal
concepts of data and the modifications can be equally applied to any other re-
cent algorithms (PCbO, PFCbO) derived from Kuznetsov’s CbO algorithm. The
274 Jan Outrata
experimental evaluation of performance of the algorithms have shown that the
update is performed by the first algorithm significantly faster than re-computing
all formal concepts or whole concept lattice and that the second algorithm is per-
formance comparable to incremental algorithms for computing concept lattice.
The future research will be focused on further experimental and real-world
application use evaluation of the algorithms and performance comparison with
other incremental (update) algorithms for computing concept lattice.
References
1. Bache K., Lichman M.: UCI Machine Learning Repository. University of California,
Irvine, CA, School of Information and Computer Sciences, 2013.
http://archive.ics.uci.edu/ml
2. Carpineto C., Romano G.: Concept data analysis. Theory and applications. J. Wi-
ley, 2004.
3. Ganter B., Wille R.: Formal concept analysis. Mathematical foundations. Berlin:
Springer, 1999.
4. Godin R., Missaoui R., Alaoui H.: Incremental Concept Formation Algorithms
Based on Galois Lattices. Computation Intelligence 11(1995), 246-267.
5. Kirchberg M., Leonardi E., Tan Y. S., Link S., K L Ko R., Lee B. S.: Formal Con-
cept Discovery in Semantic Web Data. In: Proc. ICFCA 2012, LNAI, 7278(2012),
164–179.
6. Krajca P., Outrata J., Vychodil V.: Advances in algorithms based on CbO. In:
Proc. CLA 2010, 325–337.
7. Krajca P., Outrata J., Vychodil V.: Parallel algorithm for computing fixpoints of
galois connections. Annals of Mathematics and Artificial Intelligence 59(2)(2010),
257–272.
8. Kuznetsov S. O.: Interpretation on graphs and complexity characteristics of a
search for specific patterns. Automatic Documentation and Mathematical Linguis-
tics, 24(1)(1989), 37–45.
9. Kuznetsov S. O.: A fast algorithm for computing all intersections of objects
in a finite semi-lattice. Automatic Documentation and Mathematical Linguistics,
27(5)(1993), 11–21.
10. Kuznetsov S. O.: Learning of Simple Conceptual Graphs from Positive and Nega-
tive Examples. PKDD 1999, 384–391.
11. Lindig C.: Fast concept analysis. Working with Conceptual Structures–
–Contributions to ICCS 2000, 2000, 152–161.
12. van der Merwe D., Obiedkov S. A., Kourie D. G.: AddIntent: A New Incremen-
tal Algorithm for Constructing Concept Lattices. In: Proc. ICFCA 2004, LNAI
2961(2004), 205–206.
13. Norris E. M.: An Algorithm for Computing the Maximal Rectangles in a Binary
Relation. Revue Roumaine de Mathématiques Pures et Appliquées, 23(2)(1978),
243–250.
14. Outrata J., Vychodil V.: Fast Algorithm for Computing Fixpoints of Galois
Connections Induced by Object-Attribute Relational Data. Information Sciences
185(1)(2012), 114-127.
15. Valtchev P., Missaoui R.: Building Concept (Galois) Lattices from Parts: Gener-
alizing the Incremental Methods. LNAI 2120(2001), 290-303.
16. Wille R.: Restructuring lattice theory: an approach based on hierarchies of con-
cepts. Ordered Sets, 1982, 445–470, 1982.