We analyze changes in the structure of a concept lattice corresponding to a context resulting from a given context with a known concept lattice by removing exactly one incidence. We identify the set of concepts a ected 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.
When computing concept lattices of two very similar concepts (i.e., di ering only in a small number of incidences), it doesn't seem to be e cient 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 di erences between concept lattices of two similar contexts would be interesting from the theoretical point of view.
This paper presents rst results in this direction. Namely, we consider two formal contexts di ering in just one incidence and develop a method of computing the concept lattice of the context without the incidence from the other one. In other words, we give a rst 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; J i 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), a ected by the removal (they form an interval in
B(I)), 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 [
Formal Concept Analysis has been introduced in [
For subsets A X and B Y we set
A"I = fy 2 Y j for each x 2 A it holds hx; yi 2 Ig;
B#I = fx 2 X j for each y 2 B it holds hx; yi 2 Ig: The pair h"I ; #I i is a Galois connection between sets X and Y , i.e., it satis es for each A; A1; A2 X, B; B1; B2 Y ,
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 de ned by hA1; B1i hA2; B2i 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. In ma and suprema in B(X; Y; I) are given by ^ hAj ; Bj i = j2J j2J _ hAj ; Bj i = * * \ Aj ; j2J [ Aj j2J [ Bj j2J "I #I #I "I +
; + ; \ Bj : j2J (1) (2) 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! hfxg"I #I ; fxg"I i and I : y 7! hfyg#I ; fyg#I "I i assign to each object x its object concept and to each attribute y its attribute concept. We call a subset K L, where L is a complete lattice, W-dense (resp. V-dense) if and only if any element of L can be expressed by suprema (resp. in ma) of some elements from K. The set of all object concepts (resp. attribute concepts) is Wdense (resp. V-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 2 L such that K = fk 2 L j a k bg. We denote K as [a; b]. 3
Let hX; Y; Ii, hX; Y; J i be two contexts over the same sets of objects and attributes such that hx0; y0i 2= J and I = J [ fhx0; y0ig.
We usually denote concepts of hX; Y; Ii by c, c1, hA; Bi, hA1; B1i, etc., and concepts of hX; Y; J i by d, d1, hC; Di, hC1; D1i, etc. The respective concept lattices will be denoted B(I) and B(J ).
Our goal is to nd an e cient 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; J i.
Proposition 1. For each A
X and B
A"J =
A"I if x0 2= A; A"I n fy0g if x0 2 A; B#J =
B#I if y0 2= B; B#I n fx0g if y0 2 B:
B#I .
Formal concepts from the intersection B(I) \ B(J ) are called stable. These concepts are not in uenced by removing the incidence hx0; y0i from I. When computing B(J ) from B(I), stable concepts need not be recomputed. Proposition 2. A concept c 2 B(I) is not stable iff c 2 [ I (x0); I (y0)]. Proof. If c = hA; Bi 2= [ I (x0); I (y0)], then either x0 2= A, or y0 2= B. If, for instance, x0 2= A, then by Proposition 1, B = A"I = A"J , showing B is the intent of a d 2 B(J ). Now by Proposition 1,
B#J =
B#I = A if y0 2= B;
B#I n fx0g = A n fx0g = A if y0 2 B and so d = c. The case y0 2= B is dual.
To prove the opposite direction it is su cient to notice that c 2 [ I (x0); I (y0)] is equivalent to hx0; y0i 2 A B, excluding the case hA; Bi 2 B(J ).
For concepts c = hA; Bi 2 B(I); d = hC; Di 2 B(J ) we set c d = hA ; B i = hA"J #J ; A"J i; = hC ; D i = hD#I ; D#I "I i; c d = hA ; B i = hB#J ; B#J "J i; = hC ; D i = hC"I #I ; C"I i: Evidently, c ; c 2 B(J ) and d ; d 2 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 n 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 c c ; ; d d d d ; ; c c = c ; = c ; d d = d ; = d : Proof. Isotony follows directly from de nition.
Let c = hA; Bi. From Proposition 1 we have A"J A"I . Thus, A = A"I #I A"J #I , whence c c . Similarly, for d = hC; Di, D#J D#I , whence D#I "J D#J "J = D.
To prove c = c it su ces 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 n fy0g. In the rst 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 2= A"J ) and A"J #I "J = A"J #J "J = A"J . The equality d = d can be proved similarly.
The assertions for lower children are dual.
Corollary 1. The mappings c 7! c the mappings c 7! c and d 7! d
and d 7! d are closure operators and are interior operators.
Following two theorems utilize the operators ; ; ; to give several equivalent characterizations of stable concepts. First we prove a proposition. Proposition 4. The following assertions are equivalent for any c = hA; Bi 2 B(I).
Proof. \2 ) 3": by Proposition 1, A A"J #J = B#J B#I = A. \3 ) 2": dual.
The other implications follow by de nition, since c is stable iff both 2. and 3. are satis ed.
Proposition 5 (stable concepts in B(I)). The following assertions are equivalent for a concept c 2 B(I):
Proposition 6 (stable concepts in B(J )). The following assertions are equivalent for a concept d 2 B(J ):
2. d = d ,
4
Computing B(J ) without structural information Proposition 7. The following holds for c = hA; Bi 2 B(I) and d = hC; Di 2 B(J ): If d = c , then B 2 fD; D [ fy0gg and if d = c , then A 2 fC; C [ fx0gg. Proof. By de nition of , D = A"J , which is by Proposition 1 either equal to B, or to B n fy0g. Similarly for .
Proposition 8. A non-stable concept d 2 B(J ) is a (upper or lower) child of exactly one concept c 2 B(I). This concept is non-stable and satis es 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 2 C, y0 2= D and B = D [ fy0g. By the same proposition, A = C = D#J = D#I , whence A is an extent of I. Thus, c = hA; Bi 2 B(I) and it is non-stable because x0 2 A and y0 2 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; B0i 2 B(I) we have d = c0 , then either B0 = D, or B0 = D [ fy0g. The rst 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 = B0#J . Since x0 2 C, we have y0 2= B0 (Proposition 1). Thus, C = B0#I (Proposition 1 again). Consequently, C"I = B0 and since y0 2= B0, B0 = 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 2 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 fc ; c g) 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 identi ed 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 xpoints of operators and .
Proposition 9. Let c 2 B(I) be non-stable. Then { c is non-stable iff c is a xpoint of { c is non-stable iff c is a xpoint 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 di erent 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 2 [ I (x0); I (y0)] do
B(J) B(J) n fcg; if c = c then
B(J) B(J) [ fc g; end if if c = c then
B(J) B(J) [ fc g; end if end for return B(J); end procedure
Time complexity of Algorithm 1 is clearly O(jB(I)jjXjjY j) in the worst case scenario. Indeed, the number of non-stable concepts is at most equal to jB(I)j and the computation of operators ; can be done in O(jXj jY j) time. 5
Computing B(J ) with structural information To analyze changes in the structure of a concept lattice after removing an incidence, we need to investigate deeper properties of the closure operator and the interior operator and the sets of their xpoints. (e) Concept hfx0; x1g; fy0gi is not a xpoint of any operator.
(f) Two concepts are not points of any operator.
x(a) The least concept is not stable and is a xpoint of both operators.
(b) Several non-trival non-stable concepts are xpoints of both operators. (c) Concept hfx0; x1g; fy0; y2gi is a xpoint of , but not .
(d) Concept hfx0; x1g; fy0; y1gi is a xpoint of , but not . Fig. 1: Examples of contexts with concepts of di erent types w.r.t. operators ; .
Proof. Follows directly from Theorem 5 and Theorem 6.
Since is an interior operator and have for each c 2 B(I), c c c [c ; c ] B(I).
is a closure operator on B(I), we . Thus, we can consider the interval Proposition 11. For any c 2 B(I), each concept from [c ; c ] n fcg is stable.
Proof. First we prove that either c equals c, or is its upper neighbor. Let c = hA; Bi. By de nition, the intent of c is equal to A"J #I "I . By Proposition 1, A"J 2 fB; B n fy0gg. Thus, A"J #I "I 2 fB; B n fy0gg. If it equals B, then c = c. Otherwise the intents of c and c di er 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 xpoints w.r.t. the ordering on B(I): The set of xpoints of is a lower set whereas the set of xpoints of is an upper set.
Proposition 12. Let c 2 B(I) be a non-stable concept. If c is a xpoint of then each c0 c is also a xpoint of . If c is a xpoint of , then each c0 is also a xpoint of . , c 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 direction, using an arbitrary linear ordering v such that if c1 c2, then c1 v c2. Each concept is either modi ed (by removing x0 from the extent or y0 from intent), 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 2 [ 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 n fy0gi. - 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 n fx0g; 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 xed 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 neighborhood relationship between concepts from U and c (resp. L and c ) or their neighbors. - It holds 8cl 2 L : cl c c , but it is necessary to check if there is a concept between them. - Similarly, it holds 8cu 2 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 jB(I)j, 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 SplitConcept, RelinkReducedIntent, UnlinkVanishedConcept is called. It can be easily seen that the tests can be performed quite e ciently and do not add to the time complexity.
The most time consuming among the above three procedures is SplitConcept. It iterates through all upper (which can be bounded by jXj) and lower (which can be bounded by jY j) 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(jBj jXj2 jY j).
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 de ned: { 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 2 B(I) : c1 < k < c2 then
Link(c1; c2); end if end procedure procedure SplitConcept(c 2 [ I (x0); I (y0)]) d1 = c ; d2 = c ; Link(d1; d2); for all u 2 UpperNeighbors(c) do
Unlink(c; u); Link(d2; u); end for for all l 2 LowerNeighbors(c) do
Unlink(l; c); Link(l; d1); end for for all u 2 UpperNeighbors(c) do if u 6= u then
Unlink(d2; u); Link(d1; u); LinkIfNeeded(d2; u end if end for for all l = hC; Di 2 LowerNeighbors(c) do if y0 2= D then
Unlink(l; d1); Link(l; d2); LinkIfNeeded(l ; d1); end if end for return d1; d2; end procedure ); procedure RelinkReducedIntent(c 2 [ I (x0); I (y0)]) for all u = hC; Di 2 UpperNeighbors(c) do if u 6= u then
Unlink(c; u);
LinkIfNeeded(c ; u); LinkIfNeeded(c; u end if end for end procedure procedure UnlinkVanishedConcept(c 2 [ I (x0); I (y0)]) for all u 2 UpperNeighbors(c) do
Unlink(c; u); LinkIfNeeded(c ; u); end for for all l 2 LowerNeighbors(c) do
Unlink(l; c); end for end procedure ); procedure TransformConceptLattice(B(I)) for all c = hA; Bi 2 [ I (x0); I (y0)] from least to largest w.r.t. v do cu = cu c = c
= c cl = cl cl c c c cu = cu cl = cl cu cu c c c c cl cl cu cl cu = cu cl = cl cl c c c cu = cu cl = cl cu c c cu cl cl cu cl (a) Concepts become incomparable.
(b) Concept in middle \splits into two". (c) Concept in the middle vanishes.
(d) Concept in the middle vanishes.
There is already another concept between its children.
Fig. 2: Examples of transformations of non-stable concepts from B(I) into concepts of B(J ). 6
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(jBj jXj jY j) (Algorithm 1; without structure information) and O(jBj jXj2 jY j) (Algorithm 2; with structure information).
There exist several algorithms for incremental computation of concept lattice
[
Note that the algorithm proposed by Nourine and Raynaud in [
A natural next step would be investigate adding incidences to a formal context, instead of removing. This problem, however, seems to be more di cult than the rst 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.