=Paper=
{{Paper
|id=Vol-1252/cla2014_submission_23
|storemode=property
|title=Removing an Incidence from a Formal Context
|pdfUrl=https://ceur-ws.org/Vol-1252/cla2014_submission_23.pdf
|volume=Vol-1252
|dblpUrl=https://dblp.org/rec/conf/cla/KauerK14
}}
==Removing an Incidence from a Formal Context==
https://ceur-ws.org/Vol-1252/cla2014_submission_23.pdf
Removing an incidence from a formal context
Martin Kauer? and Michal Krupka??
Department of Computer Science
Palacký University in Olomouc
17. listopadu 12, CZ-77146 Olomouc
Czech Republic
martin.kauer@upol.cz
michal.krupka@upol.cz
Abstract. We analyze changes in the structure of a concept lattice cor-
responding to a context resulting from a given context with a known
concept lattice by removing exactly one incidence. We identify the set
of concepts affected by the removal and show how they can be used for
computing concepts in the new concept lattice. We present algorithms
for incremental computation of the new concept lattice, with or without
structural information.
1 Introduction
When computing concept lattices of two very similar concepts (i.e., differing only
in a small number of incidences), it doesn’t seem to be efficient to compute both
concept lattices independently. Rather, an incremental method of computing one
of the lattices using the other would be more desirable. Also, analyzing structural
differences between concept lattices of two similar contexts would be interesting
from the theoretical point of view.
This paper presents first results in this direction. Namely, we consider two
formal contexts differing in just one incidence and develop a method of comput-
ing the concept lattice of the context without the incidence from the other one.
In other words, we give a first answer to the question “What happens to the
concept lattice, if we remove one cross from the context?”.
Our results are the following. We consider contexts hX, Y, Ii and hX, Y, Ji
such that J results from I by removing exactly one incidence. Further we consider
the respective concept lattices B(I) and B(J). For these contexts and concept
lattices we
1. identify concepts in B(I), affected by the removal (they form an interval in
B(I)),
?
The author acknowledges support by IGA of Palacky University, No. PrF 2014 034
??
The author acknowledges support by the ESF project No. CZ.1.07/2.3.00/20.0059.
The project is co-financed by the European Social Fund and the state budget of the
Czech Republic.
2. show how they transform to concepts in the new concept lattice (they will
either vanish entirely, or transform to one or two concepts),
3. derive several further results on the correspondence between the two lattices,
4. propose two basic algorithms for transforming incrementally B(I) to B(J).
Several algorithms for incremental computation of concept lattices have been
developed in the past [1, 5, 8, 6, 7, 2] (see also [4] for a comparison of some of the
algorithms). In general, the algorithms build a concept lattice incrementally
by modifying formal contexts by adding or removing objects one by one. Our
approach is different as we focus on removing just one incidence.
2 Formal concept analysis
Formal Concept Analysis has been introduced in [9], our basic reference is [3].
A (formal) context is a triple C = hX, Y, Ii where X is a set of objects, Y a set
of attributes and I ⊆ X × Y a binary relation between X and Y . For hx, yi ∈ I
it is said “The object x has the attribute y”.
For subsets A ⊆ X and B ⊆ Y we set
A↑I = {y ∈ Y | for each x ∈ A it holds hx, yi ∈ I},
B ↓I = {x ∈ X | for each y ∈ B it holds hx, yi ∈ I}.
The pair h↑I , ↓I i is a Galois connection between sets X and Y , i.e., it satisfies
for each A, A1 , A2 ⊆ X, B, B1 , B2 ⊆ Y ,
1. If A1 ⊆ A2 , then A↑2I ⊆ A↑1I , if B1 ⊆ B2 , then B2↓I ⊆ B1↓I .
2. A ⊆ A↑I ↓I and B ⊆ B ↓I ↑I .
If A↑I = B and B ↓I = A, then the pair hA, Bi is called a formal concept of
hX, Y, Ii. The set A is called the extent of hA, Bi, the set B the intent of hA, Bi.
A partial order ≤ on the set B(X, Y, I) of all formal concepts of hX, Y, Ii is
defined by hA1 , B1 i ≤ hA2 , B2 i iff A1 ⊆ A2 (iff B2 ⊆ B1 ). B(X, Y, I) along with
≤ is a complete lattice and is called the concept lattice of hX, Y, Ii. Infima and
suprema in B(X, Y, I) are given by
* [ ↓I ↑I +
^ \
hAj , Bj i = Aj , Bj , (1)
j∈J j∈J j∈J
* +
_ [ ↑I ↓I \
hAj , Bj i = Aj , Bj . (2)
j∈J j∈J j∈J
One of immediate consequences of (1) and (2) is that the intersection of any
system of extents (resp. intents) is again an extent (resp. intent).
Mappings γI : x 7→ h{x}↑I ↓I , {x}↑I i and µI : y 7→ h{y}↓I , {y}↓I ↑I i assign to
each object x its object concept and to each attributeW y its attribute concept.
V We
call a subset K ⊆ L, where L is a complete lattice, -dense (resp. -dense) if
and only if any element of L can be expressed by suprema (resp. infima) of some W
elements fromV K. The set of all object concepts (resp. attribute concepts) is -
dense (resp. -dense) in B(X, Y, I). This can be easily seen from (1) (resp. (2)).
We will also need a notion of an interval in lattice L. We call a subset K ⊆ L
an interval, if and only if there exist elements a, b ∈ L such that K = {k ∈
L | a ≤ k ≤ b}. We denote K as [a, b].
3 Problem statement and basic notions
Let hX, Y, Ii, hX, Y, Ji be two contexts over the same sets of objects and at-
tributes such that hx0 , y0 i ∈
/ J and I = J ∪ {hx0 , y0 i}.
We usually denote concepts of hX, Y, Ii by c, c1 , hA, Bi, hA1 , B1 i, etc., and
concepts of hX, Y, Ji by d, d1 , hC, Di, hC1 , D1 i, etc. The respective concept
lattices will be denoted B(I) and B(J).
Our goal is to find an efficient way to compute the concept lattice B(J) from
B(I). We provide two solutions to this problem. First solution computes just
elements of B(J), the second one adds also information on its structure. In this
section we introduce some basic tools and prove simple preliminary results.
The following proposition shows a correspondence between the derivation
operators of contexts hX, Y, Ii and hX, Y, Ji.
Proposition 1. For each A ⊆ X and B ⊆ Y it holds
↑ ↓
↑J A I if x0 ∈
/ A, ↓J B I if y0 ∈
/ B,
A = B =
A↑I \ {y0 } if x0 ∈ A, B ↓I \ {x0 } if y0 ∈ B.
In particular, A↑J ⊆ A↑I and B ↓J ⊆ B ↓I .
Proof. Immediate.
Formal concepts from the intersection B(I) ∩ B(J) are called stable. These
concepts are not influenced by removing the incidence hx0 , y0 i from I. When
computing B(J) from B(I), stable concepts need not be recomputed.
Proposition 2. A concept c ∈ B(I) is not stable iff c ∈ [γI (x0 ), µI (y0 )].
Proof. If c = hA, Bi ∈/ [γI (x0 ), µI (y0 )], then either x0 ∈/ A, or y0 ∈
/ B. If, for
instance, x0 ∈/ A, then by Proposition 1, B = A↑I = A↑J , showing B is the
intent of a d ∈ B(J). Now by Proposition 1,
↓
B I =A if y0 ∈
/ B,
B ↓J = ↓I
B \ {x0 } = A \ {x0 } = A if y0 ∈ B
and so d = c. The case y0 ∈ / B is dual.
To prove the opposite direction it is sufficient to notice that c ∈ [γI (x0 ), µI (y0 )]
is equivalent to hx0 , y0 i ∈ A × B, excluding the case hA, Bi ∈ B(J).
For concepts c = hA, Bi ∈ B(I), d = hC, Di ∈ B(J) we set
c = hA , B i = hA↑J ↓J , A↑J i, c = hA , B i = hB ↓J , B ↓J ↑J i,
d = hC , D i = hD↓I , D↓I ↑I i, d = hC , D i = hC ↑I ↓I , C ↑I i.
Evidently, c , c ∈ B(J) and d , d ∈ B(I). c (resp. c ) is called the upper
(resp. lower ) child of c. In our setting, d = d (it would not be the case if I \ J
had more than one element). It is the (unique) concept from B(I), containing,
as a rectangle, the rectangle represented by d.
The following theorem shows basic properties of the pairs h , i and h , i.
Proposition 3 (child operators). The mappings c 7→ c , c 7→ c , and d 7→
d are isotone and satisfy
c ≤ c , d ≤ d , c = c , d = d ,
c ≥ c , d ≥ d , c = c , d = d .
Proof. Isotony follows directly from definition.
Let c = hA, Bi. From Proposition 1 we have A↑J ⊆ A↑I . Thus, A = A↑I ↓I ⊆
↑J ↓I
A , whence c ≤ c . Similarly, for d = hC, Di, D↓J ⊆ D↓I , whence D↓I ↑J ⊆
↓J ↑J
D = D.
To prove c = c it suffices to show that for the extent A of c it holds
A↑J ↓I ↑J = A↑J . By Proposition 1, we have two possibilities: either A↑J = A↑I ,
or A↑J = A↑I \ {y0 }. In the first case A↑J ↓I ↑J = A↑J holds trivially, in the
second case A↑J ↓I = A↑J ↓J (by the same proposition, because y0 ∈ / A↑J ) and
↑J ↓I ↑J ↑J ↓J ↑J ↑J
A =A = A . The equality d = d can be proved similarly.
The assertions for lower children are dual.
Corollary 1. The mappings c 7→ c and d 7→ d are closure operators and
the mappings c 7→ c and d 7→ d are interior operators.
Following two theorems utilize the operators , , , to give several equiv-
alent characterizations of stable concepts. First we prove a proposition.
Proposition 4. The following assertions are equivalent for any c = hA, Bi ∈
B(I).
1. c is stable,
2. A↑I = A↑J ,
3. B ↓I = B ↓J .
Proof. “2 ⇒ 3”: by Proposition 1, A ⊆ A↑J ↓J = B ↓J ⊆ B ↓I = A.
“3 ⇒ 2”: dual.
The other implications follow by definition, since c is stable iff both 2. and
3. are satisfied.
Proposition 5 (stable concepts in B(I)). The following assertions are equiv-
alent for a concept c ∈ B(I):
1. c is stable,
2. c ∈
/ [γI (x0 ), µI (y0 )],
3. c = c ,
4. c = c ,
5. c = c .
Proof. Directly from Proposition 4.
Proposition 6 (stable concepts in B(J)). The following assertions are equiv-
alent for a concept d ∈ B(J):
1. d is stable,
2. d = d ,
3. d is stable.
Proof. Directly from Proposition 4.
4 Computing B(J ) without structural information
Proposition 7. The following holds for c = hA, Bi ∈ B(I) and d = hC, Di ∈
B(J): If d = c , then B ∈ {D, D ∪ {y0 }} and if d = c , then A ∈ {C, C ∪ {x0 }}.
Proof. By definition of , D = A↑J , which is by Proposition 1 either equal to
B, or to B \ {y0 }. Similarly for .
Proposition 8. A non-stable concept d ∈ B(J) is a (upper or lower) child of
exactly one concept c ∈ B(I). This concept is non-stable and satisfies c = d =
d .
Proof. Let d = hC, Di. Since d is non-stable, then either C ↑I 6= C ↑J , or D↓I 6=
D↓J . Suppose C ↑I 6= C ↑J and set A = C, B = C ↑I . By Proposition 1, x0 ∈ C,
y0 ∈/ D and B = D ∪ {y0 }. By the same proposition, A = C = D↓J = D↓I ,
whence A is an extent of I. Thus, c = hA, Bi ∈ B(I) and it is non-stable because
x0 ∈ A and y0 ∈ B (Proposition 2). Since D = C ↑J = A↑J , d = c . A = C
yields c = d .
We prove uniqueness of c. By Proposition 7, if for c0 = hA0 , B 0 i ∈ B(I) we
have d = c0 , then either B 0 = D, or B 0 = D ∪ {y0 }. The first case is impossible,
because it would make D an intent of I and, consequently, d a stable concept.
The second case means c0 equals c above. There is a third case left: if d = c0 ,
then C = B 0↓J . Since x0 ∈ C, we have y0 ∈ / B 0 (Proposition 1). Thus, C = B 0↓I
(Proposition 1 again). Consequently, C ↑I = B 0 and since y0 ∈ / B 0 , B 0 = C ↑J
(Proposition 1 for the last time). Thus, d = c0 , which is a contradiction with
non-stability of d.
The case D↓I 6= D↓J is proved dually (in this case we obtain d = c ).
The meaning of the previous theorem is that for each non-stable concept in
B(J) there exists exactly one non-stable concept in B(I), such that these two
are related via mappings , or , .
The theorem leads the following simple way of constructing B(J) from B(I).
For each c ∈ B(I) the following has to be done:
1. If c is stable, then it has to be added to B(J).
2. If c is not stable, then each its non-stable child (i.e., each non-stable element
of {c , c }) has to be added to B(J).
This method ensures that all proper elements will be added to B(J) (i.e., no
element will be omitted) and each element will be added exactly once.
Stable (resp. non-stable) concepts can be identified by means of Proposition
11. The following proposition shows a simple way of detecting whether a child
of a non-stable concept from B(I) is stable. It also describes the role of fixpoints
of operators and .
Proposition 9. Let c ∈ B(I) be non-stable. Then
– c is non-stable iff c is a fixpoint of ,
– c is non-stable iff c is a fixpoint of .
Proof. If c is not stable, then c = (c ) by Theorem 8. On the other hand, if
c is stable, then c = c by Theorem 6, which rules out c = c, because in
that case c would be equal to c , which would make it stable by Theorem 5.
The proof for c is dual.
Example 1. In Fig. 1 we can see some examples of contexts with concepts of
different types w.r.t. operators , .
The method is utilized in Algorithm 1.
Algorithm 1 Transforming B(I) into B(J) (without structural information).
procedure TransformConcepts(B(I))
B(J) ← B(I);
for all c = hA, Bi ∈ [γI (x0 ), µI (y0 )] do
B(J) ← B(J) \ {c};
if c = c then
B(J) ← B(J) ∪ {c };
end if
if c = c then
B(J) ← B(J) ∪ {c };
end if
end for
return B(J);
end procedure
Time complexity of Algorithm 1 is clearly O(|B(I)||X||Y |) in the worst case
scenario. Indeed, the number of non-stable concepts is at most equal to |B(I)|
and the computation of operators , can be done in O(|X| · |Y |) time.
5 Computing B(J ) with structural information
To analyze changes in the structure of a concept lattice after removing an inci-
dence, we need to investigate deeper properties of the closure operator and
the interior operator and the sets of their fixpoints.
y1 y2 y3 y0
y0 y1 y2
x0 × × × •
x0 • × ×
x1 × ×
x1
x2 × ×
x2
x3 × ×
(a) The least concept is not sta-
(b) Several non-trival non-stable
ble and is a fixpoint of both op-
concepts are fixpoints of both op-
erators.
erators.
y1 y2 y0 y0 y1 y2
x0 × • x0 • ×
x1 × × x1 × × ×
x2 × x2
(c) Concept h{x0 , x1 }, {y0 , y2 }i (d) Concept h{x0 , x1 }, {y0 , y1 }i
is a fixpoint of , but not . is a fixpoint of , but not .
y1 y2 y3 y4 y0
y0 y1 y2 x0 × × •
x0 • x1 × × ×
x1 × × x2 ×
x2 x3 × × ×
(e) Concept h{x0 , x1 }, {y0 }i is x4 ×
not a fixpoint of any operator. (f) Two concepts are not fix-
points of any operator.
Fig. 1: Examples of contexts with concepts of different types w.r.t. operators
, .
Proposition 10. Each stable concept is a fixpoint of both and .
Proof. Follows directly from Theorem 5 and Theorem 6.
Since is an interior operator and is a closure operator on B(I), we
have for each c ∈ B(I), c ≤ c ≤ c . Thus, we can consider the interval
[c , c ] ⊆ B(I).
Proposition 11. For any c ∈ B(I), each concept from [c , c ]\{c} is stable.
Proof. First we prove that either c equals c, or is its upper neighbor. Let
c = hA, Bi. By definition, the intent of c is equal to A↑J ↓I ↑I . By Proposition
1, A↑J ∈ {B, B \ {y0 }}. Thus, A↑J ↓I ↑I ∈ {B, B \ {y0 }}. If it equals B, then
c = c. Otherwise the intents of c and c differ in exactly one attribute,
which makes c and c neighbors. Also notice that in this case c is stable
because its intent does not contain y0 (Proposition 2).
Now let c0 ≤ c be non-stable. If c = c , then c0 ≤ c. If c < c , then c is
non-stable (Proposition 10) whereas c is stable. Non-stable concepts in B(I)
form an interval (Theorem 5). Thus, c0 ∨ c is non-stable and should be less than
c . Hence, c0 ∨ c = c (c is a lower neighbor of c ), concluding c0 ≤ c again.
In a similar way we obtain the inequality c0 ≥ c for each non-stable c0 ≥
c .
The following proposition shows an important property of the sets of fixpoints
w.r.t. the ordering on B(I): The set of fixpoints of is a lower set whereas the
set of fixpoints of is an upper set.
Proposition 12. Let c ∈ B(I) be a non-stable concept. If c is a fixpoint of ,
then each c0 ≤ c is also a fixpoint of . If c is a fixpoint of , then each c0 ≥ c
is also a fixpoint of .
Proof. Let c = c and c0 ≤ c. If c0 is stable, then the assertion follows by
Proposition 10. Suppose c0 is not stable. By extensivity and isotony of , c0 ≤
c0 ≤ c = c. Thus, c0 is not stable (Proposition 2) and c0 = c0 by
Proposition 11.
The case c = c is dual.
The above results are used in Algorithm 2, which computes the lattice B(J)
together with the information of its ordering. The algorithm is more complicated
than the previous one. We provide a short description of the algorithm, together
with some examples. Due to space limitations, we will not dwell into details. We
will also leave out dual parts of similar cases.
The algorithm processes all non-stable concepts of B(I) in a bottom-up di-
rection, using an arbitrary linear ordering v such that if c1 ≤ c2 , then c1 v c2 .
Each concept is either modified (by removing x0 from the extent or y0 from in-
tent), or disposed of entirely. Sometimes, new concepts are created. All concepts
also get updated their lists of upper and lower neighbors.
Let c = hA, Bi be an arbitrary non-stable concept from B(I) (c ∈ [γI (x0 ), µI (y0 )]).
– If c = c , c = c , then c will “split” into d1 ≤ d2 .
- We set d1 = c and d2 = c .
- The concept d1 will be a lower neighbor of d2 .
- If for a lower neighbor cl of c it holds cl = cl , cl 6= cl , then it
will be a lower neighbor of d2 . It is necessary to check whether d1 and
cl will be neighbors. It certainly holds cl ≤ d1 , but there can be
a concept k, such that cl ≤ k ≤ d1 .
- Dually for upper neighbors.
- If for a non-stable neighbor cn of c it holds cn = cn , cn = cn , i.e.,
the same conditions as for c (cn will split into dn1 , dn2 ), then d1 , dn1
and d2 , dn2 will be neighbors.
- All other upper (resp. lower) neighbors will be neighbors of d2 (resp. d1 ).
– If c = c and c 6= c , then c will lose y0 from its intent.
- Denote the transformed c as d = hC, Di = c = hA, B \ {y0 }i.
- If for an upper neighbor cu it holds cu = cu , cu 6= cu (cu will
lose x0 from its extent), then cu and d will become incomparable. It
is necessary to check whether c , cu and c, cu should be neighbors
(again, there can be a concept between them).
– If c 6= c and c = c , then c will lose x0 from its extent.
- Denote transformed c as d = hC, Di = c = hA \ {x0 }, Bi.
– If c 6= c and c 6= c , then c will vanish entirely.
- It is necessary to check whether c and c should be neighbors (again,
a concept can lie between them).
- Denote by U the set of all upper neighbors of c, except for c . There
is no fixed point of among the elements from U .
- Denote by L the set of all lower neighbors of c, except for c .
- Concepts from U and L will not be neighbors.
Concepts will either become incomparable or one of them or both will
vanish. There is also no need for additional checks regarding neighbor-
hood relationship between concepts from U and c (resp. L and c )
or their neighbors.
- It holds ∀cl ∈ L : cl ≤ c ≤ c , but it is necessary to check if there is a
concept between them.
- Similarly, it holds ∀cu ∈ U : c ≤ c ≤ cu , but again it is necessary to
check if there is a concept between them.
The number of iterations in TransformConceptLattice is at most |B(I)|,
which occurs when each concept in B(I) is non-stable. In each of the iterations,
tests c = c and c = c are performed and one of the procedures Split-
Concept, RelinkReducedIntent, UnlinkVanishedConcept is called. It
can be easily seen that the tests can be performed quite efficiently and do not
add to the time complexity.
The most time consuming among the above three procedures is SplitCon-
cept. It iterates through all upper (which can be bounded by |X|) and lower
(which can be bounded by |Y |) neighbors of the concept c. For each of the
neighbors it might be necessary to check if the interval between the neighbor
and certain other concept is empty (and we should make a new edge). This can
be done by checking intents/extents of its neighbors.
The above considerations lead to the result that time complexity of Algorithm
2 is in the worst case O(|B| · |X|2 · |Y |).
Example 2. In Fig. 2, we can see some examples of transformations of non-stable
concepts from B(I) into concepts of B(J).
In Algorithm 2 we will assume that following functions are already defined:
– U pperN eighbors(c) - returns upper neighbors of c;
– LowerN eighbors(c) - returns lower neighbors of c;
– Link(c1 , c2 ) - introduces neighborhood relationship between c1 and c2 ;
– U nlink(c1 , c2 ) - cancels neighborhood relationship between c1 and c2 .
Algorithm 2 Transforming B(I) with structural information into B(J).
procedure LinkIfNeeded(c1 , c2 )
if @k ∈ B(I) : c1 < k < c2 then
Link(c1 , c2 );
end if
end procedure
procedure SplitConcept(c ∈ [γI (x0 ), µI (y0 )])
d1 = c ; d2 = c ;
Link(d1 , d2 );
for all u ∈ U pperN eighbors(c) do
U nlink(c, u); Link(d2 , u);
end for
for all l ∈ LowerN eighbors(c) do
U nlink(l, c); Link(l, d1 );
end for
for all u ∈ U pperN eighbors(c) do
if u 6= u then
U nlink(d2 , u); Link(d1 , u); LinkIf N eeded(d2 , u );
end if
end for
for all l = hC, Di ∈ LowerN eighbors(c) do
if y0 ∈/ D then
U nlink(l, d1 ); Link(l, d2 ); LinkIf N eeded(l , d1 );
end if
end for
return d1 , d2 ;
end procedure
procedure RelinkReducedIntent(c ∈ [γI (x0 ), µI (y0 )])
for all u = hC, Di ∈ U pperN eighbors(c) do
if u 6= u then
U nlink(c, u);
LinkIf N eeded(c , u); LinkIf N eeded(c, u );
end if
end for
end procedure
procedure UnlinkVanishedConcept(c ∈ [γI (x0 ), µI (y0 )])
for all u ∈ U pperN eighbors(c) do
U nlink(c, u); LinkIf N eeded(c , u);
end for
for all l ∈ LowerN eighbors(c) do
U nlink(l, c);
end for
end procedure
procedure TransformConceptLattice(B(I))
for all c = hA, Bi ∈ [γI (x0 ), µI (y0 )] from least to largest w.r.t. v do
if c = c and c = c then . Concept will split.
B(I) ← B(I) \ {c};
B(I) ← B(I) ∪ SplitConcept(c);
else if c 6= c and c = c then . Extent will be smaller.
A ← A \ {x0 };
else if c = c and c 6= c then . Intent will be smaller.
RelinkReducedIntent(c);
B ← B \ {y0 };
else if c 6= c and c 6= c then . Concept will vanish.
B(I) ← B(I) \ {c};
U nlinkV anishedConcept(c);
end if
end for
end procedure
cu
cu cu
cu = cu
cu
cu = cu cu c
c = c = c
cu cl
c cl
cl = cl cl = cl
cl cl
cl cl
(a) Concepts become incomparable. (b) Concept in middle “splits into two”.
c cu = cu c cu c cu = cu c cu
c c
c cl = cl c cl c cl = cl c cl
(c) Concept in the middle vanishes. (d) Concept in the middle vanishes.
There is already another concept be-
tween its children.
Fig. 2: Examples of transformations of non-stable concepts from B(I) into con-
cepts of B(J).
6 Conclusion
We analyzed changes of the structure of a concept lattice, caused by removal
of exactly one incidence from the associated formal context. We proved some
theoretical results and presented two algorithms with time complexities O(|B| ·
|X| · |Y |) (Algorithm 1; without structure information) and O(|B| · |X|2 · |Y |)
(Algorithm 2; with structure information).
There exist several algorithms for incremental computation of concept lattice
[1, 5, 8, 6, 7, 2], based on addition and/or removal of objects. Our approach is new
in that we recompute a concept lattice based on a removal of just one incidence.
Note that the algorithm proposed by Nourine and Raynaud in [7] has time
complexity O((|Y | + |X|) · |X| · |B|), which is better than complexity of our
Algorithm 2. However, experiments presented in [5] indicate that this algorithm
sometimes performs slower than some algorithms with time complexity O(|B| ·
|X|2 ·|Y |). In the case of our Algorithm 2, some preliminary experiments indicate
that the size of the interval of non-stable concepts is usually relatively small,
which substantially reduces the overall processing time of the algorithm.
A natural next step would be investigate adding incidences to a formal con-
text, instead of removing. This problem, however, seems to be more difficult
than the first one, namely because the set of non-stable concepts in the lattice
B(J) has more complicated structure (it is not an interval) and also because not
all non-stable concepts in B(I) can be computed via the operator . We will try
to address this issues in the future. We will also focus on the following:
– experimenting with proposed algorithms on various datasets and comparing
them with other known algorithms,
– generalizing the results to allow removing and adding more incidences at the
same time.
References
1. Carpineto, C., Romano, G.: Concept Data Analysis: Theory and Applications. John
Wiley & Sons (2004)
2. Dowling, C.E.: On the irredundant generation of knowledge spaces. J. Math. Psy-
chol. 37(1), 49–62 (1993)
3. Ganter, B., Wille, R.: Formal Concept Analysis – Mathematical Foundations.
Springer (1999)
4. Kuznetsov, S.O., Obiedkov, S.: Comparing performance of algorithms for generating
concept lattices. Journal of Experimental and Theoretical Artificial Intelligence 14,
189–216 (2002)
5. Merwe, D., Obiedkov, S., Kourie, D.: Addintent: A new incremental algorithm for
constructing concept lattices. In: Eklund, P. (ed.) Concept Lattices, Lecture Notes
in Computer Science, vol. 2961, pp. 372–385. Springer Berlin Heidelberg (2004)
6. Norris, E.M.: An algorithm for computing the maximal rectangles in a binary rela-
tion. Revue Roumaine de Mathématiques Pures et Appliquées 23(2), 243–250 (1978)
7. Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inf. Process. Lett.
71(5-6), 199–204 (1999)
8. Outrata, J.: A lattice-free concept lattice update algorithm based on *CbO. In:
Ojeda-Aciego, M., Outrata, J. (eds.) CLA. CEUR Workshop Proceedings, vol. 1062,
pp. 261–274. CEUR-WS.org (2013)
9. Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts.
In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Boston (1982)