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.
In applications of Formal Concept Analysis (FCA) [
The particular change of object-attribute relational data processed in FCA,
namely the introduction of new objects (described by particular values of
attributes), can be handled by the so-called incremental algorithms for computing
concept lattice, Norris’s [
In the following we propose efficient algorithm for updating the concept
lattice, 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 [
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
comparison with AddIntent algorithm [
We describe the algorithm as a modification of Fast Close-by-One (FCbO)
algorithm [
In the descriptions below we assume the reader is familiar with basics of
FCA, see [
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 hX0, Y 0, I0i, where X0 = X ∪ XN = {0, . . . , m0}, Y 0 = Y ∪ YN = {0, . . . , n0}, n0 = k if k > n and n0 = n otherwise, and I0 ⊆ X0 ×Y 0 such that I0 ∩(X ×Y ) = I, I0 ∩ (XN × YN ) = N and I0 ∩ (X × (YN \ Y )) = I0 ∩ (XN × (Y \ YN )) = ∅. Hence I0 is the union of I and N both extended to X0 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(X0, Y 0, I0), with the exception of formal concept hY 0↓I0 , Y 0i. 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 B0 = B↓I0 ↑I0 ⊆ YN , if B0 = B00 = B↓I ↑I then the formal
concept hA0, B0i ∈ B(X0, Y 0, I0) with the same intent B0 = B00 as formal
concept hA00, B00i ∈ B(X, Y, I) is a modified formal concept enlarging the extent of
Algorithm 1: Procedure
From(hA, Bi, y, {Ny | y ∈ Y }), cf. [
put hhC, Di, ji to queue;
hA00, B00i by objects A0 \ A00 ⊆ XN if A0 ⊃ A00 (otherwise hA0, B0i = hA00, B00i
is old). Otherwise, if B0 ⊂ B00 = B↓I↑I (since the ⊃ inclusion cannot happen
since X0 ⊃ X) then the formal concept hA0, B0i ∈ B(X0, Y 0, I0) is a new formal
concept and the formal concept hA00, B00i ∈ B(X, Y, I) is called its generator [
We use the above presented ideas to modify FCbO algorithm described in [
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 [
When invoked with hA, Bi and y ∈ YN (first attribute to be processed) and
{Ny | y ∈ Y }, UpdateFastGenerateFrom first checks if (A ∩ X)↑I0 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 [
Yj = {y ∈ Y 0 | y < j}.
In order to list all new and modified formal concepts of hX0, Y 0, I0i which
are not formal concepts of hX, Y, Ii, each of them exactly once, we invoke
UpdateFastGenerateFrom with h∅↓I0 , ∅↓I0 ↑I0 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 [
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 attributes 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. C10 = h{2, 4}, {0, 5}i,
C5 = h{0}, {0, 2, 3}i, C6 = h{1, 2}, {1, 5}i, C7 = h{1}, {1, 3, 4, 5}i, C8 = h{0, 1}, {3}i.
C6∗ = h{1, 2, 3}, {1, 5}i, C11 = h{1, 3}, {1, 3, 5}i, C8∗ = h{0, 1, 3, 4}, {3}i, C12 = h{1, 3, 4}, {3, 5}i, C13 = h{1, 2, 3, 4}, {5}i.
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 hX00, Y 00, I00i incrementally, i.e. processing the data object by object, as incremental algorithms for computing concept lattice do. Namely, we invoke procedure UpdateFastGenerateFrom with initial arguments repeatedly for each object i ∈ X00 = {0, . . . , n00}, setting hX, Y, Ii := h{0, . . . , i − 1}, Sij−=10{j}↑I00 , I ∩ ({0, . . . , i − 1} × Sij−=10{j}↑I00 )i, XN := {i}, YN := {i}↑I00 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, however, 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, filtered 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 [
We now describe how to extend FCbO algorithm, as described in [
Next, since further formal concepts hC ∩ {j0}↓, (C ∩ {j0}↓)↑i are computed
from hC, Di in the next recursive invocation of (Update)FastGenerateFrom
for attributes j0 ≥ 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
relation, 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 [
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 Section 2.1, we describe only the modifications introduced to FastGenerateFrom.
The original FCbO algorithm remains in essence intact, including its
arguments and local variables, all the modifications to original procedure
FastGenerateFrom 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
Algorithm 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
covering (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 [
In order to output concept lattice of hX, Y, Ii, that means to list all
formal 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
LatticeFastGenerateFrom 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 [
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∅↓I0 , ∅↓I0 ↑I0 i) and its generator hE, F i = hC ∩ X, (C ∩ X)↑I0 i, with listing of hC, Di also pairs hhF ↓I0 , F i, hC, Dii as to be created in the cover relation and hhF ↓I0 , 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 LatticeFastGenerateFrom. Due to space limitations of the paper, the merged algorithm is postponed to the full version of the paper. LatticeFastGenerateExample 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.
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.
C6 C7
C3 C4
C1 C8 C2
C5
C13
C8 C2 C6 C12
C5 C1
C10 C7
C11 C3 C9
C4 C1, C2 : hC2, C1i, C3 : hC3, C2i, C4 : hC4, C3i, C9 : hC9, C5∗i, hC4, C9i, C10 : hC10, C2∗i, hC3, C10i, hC9, C10i,
C11 : hC11, C6∗i, hC7, C11i, 3
C5 : hC5, C2i, hC4, C5i, C6 : hC6, C1i, hC3, C6i, C7 : hC7, C6i, hC4, C7i, C8 : hC8, C1i, hC7, C8i, hC5, C8i.
C12 : hC12, C8∗i, hC11, C12i, hC9, C12i,
C13 : hC13, C1∗i, hC6∗, C13i, hC12, C13i, hC10, C13i.
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
“introducing” 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 [
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
incremental algorithm [
In the experiments, we used our implementations of the presented algorithms
in ANSI C, which are modifications of our (performance efficient) FCbO
algorithm implementation used for performance evaluation in [
2 3
log(new objects)
4
5
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 [
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 object (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 performance 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, 60 )s 48 d con 36 e (se 24 itm12 0150 170 190 210 230 250 attributes 510 )s408 d con306 e (se204 itm102 010 12 14 16 18 20 ll ratio (%) 60 )s 48 d con 36 e (se 24 itm12 0150 170 190 210 230 250 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, middle)/merged algorithm (right), dashed line—AddIntent, dotted line—FCbO (left, middle)/Algorithm 1 (right). 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 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 algorithm 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 orderings 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
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 algorithm 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 modification 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 recent algorithms (PCbO, PFCbO) derived from Kuznetsov’s CbO algorithm. The 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 performance 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.