# Influences of Three-Way Concept Lattice Caused by Variations of Attribute Values

Authors: Huilai Zhi; Shulin Hu
Journal: Scientific Programming
 (2019)

---

## Abstract

Three-way concept lattices have been widely used in various types of applications. As the construction of three-way concept lattices is rather time consuming, especially for large formal contexts, it is not applicable to construct the lattices from the beginning when changes are made to the contexts. Motivated by this problem, the influences of three-way concept lattices caused by variations of attribute values are explored in this study. Specifically, we discuss two types of changes. One is changing the value of a specific incidence relation from 0 to 1, and the other is from 1 to 0. Furthermore, two types of three-way concept lattices are investigated. One is the object-induced three-way concept lattice, and the other is the attribute-induced three-way concept lattice. Both the mathematical proofs and the examples show the effectiveness of our proposed methods.


---

## Body

## 1. Introduction

Formal concept analysis (FCA) is a mathematical theory put forward by Wille in 1982 [1, 2]. Concept lattice is one of the main outcomes of FCA and describes a domain by using a set of concepts. At present, FCA has been used as an effective tool in data analysis and knowledge discovery. For instance, it has been applied in the fields of CT analysis [3], expert systems [4, 5], data mining [6, 7], data clustering [8, 9], software engineering [10], etc. However, it is worth noting that although both positive attributes and negative attributes play equal roles in many knowledge-based activities [11, 12, 13], classical concepts concern only positive attributes while left negative ones aside. As a result, we may lose many useful information.By taking both positive and negative attributes into consideration, Qi et al. [14, 15] proposed the theory of three-way concept analysis (3WCA). In essence, 3WCA generalizes classical FCA by absorbing the theory of three decisions [16–21]. In 3WCA, there are two types of concept lattices. One is object-induced three-way concept lattice, and the other is attribute-induced three-way concept lattice. It has been proved that as a generalization of classical concepts, three-way concepts can provide more details than that of classical concepts [15]. On the basis of an object-induced three-way concept, we divide the attributes of the intent of this concept into three disjoint parts: positive parts, negative parts, and the rest, based on which we can make further decisions.Nowadays, three-way concept analysis has attracted more and more attentions. Li and Wang [22] proposed three-way approximate concepts under the framework of three-way concept analysis. Shivhare and Cherukuri [23] applied the idea of three-way concept analysis to simulate a cognitive learning process. Mouliswaran et al. [24] designed a role-based access control scheme by using three-way formal concept analysis. Ren and Wei [25] studied the attribute reduction of three-way concept lattices. Li et al. [26] described a three-way cognitive concept learning process from a multigranularity perspective. Zhi and Li [27] studied granular description based on positive and negative attributes. Furthermore, in order to manage fuzziness, Singh [28, 29] proposed three-way fuzzy concepts. In addition, Singh also generalized three-way concepts to bipolar fuzzy concepts [30] and m-polar fuzzy concepts [31] to derive useful concepts from fuzzy contexts for decision making.As three-way concept lattice is of vital importance in 3WCA-based applications, the construction of three-way concept lattices is an important topic and deserves our continuous efforts. For instance, Qi et al. [14, 15] elaborated on the relationship between three-way concept lattices and classical concept lattices and constructed three-way concept lattices by combining the sublattices of classical concept lattices.Compared with the construction of three-way concept lattices, how to effectively update the three-way concept lattices to cater the continuous changing of formal context has not received enough attentions. However, this is very important both in theoretical research and applications. Let’s consider the following example.Example 1.
Consider five European students, each of which wants to learn some courses about Chinese history. At present, the available courses are about five dynasties of Chinese history, i.e., Tang Dynasty, Song Dynasty, Yuan Dynasty, Ming Dynasty, and Qing Dynasty. Before they come to China, each student has chosen their interested dynasties. In Table1, their interests are listed and a “×” indicates a student favors a specific dynasty. For instance, as the Yuan Dynasty had a great influence on European history, four students have chosen this dynasty. By using this table, we want to analysis the main interests of the students.
However, after they came to China, some of them changed their minds. For instance, the charming of Xi’an attracted another two students to choose Tang Dynasty. At the same time, three students removed Yuan Dynasty from their curriculums. Accordingly, Table1 is updated to Table 2, and we have to update our analysis result. Furthermore, if the analysis is based on three-way concept lattices, we must initially update the three-way concept lattice and then update the analysis result. Then, incremental approaches are needed to solve this problem, and studies have shown their effectiveness to cater dynamic systems [32, 33, 34].
Motivated by the above problems, we will investigate the approach to update the three-way concept lattice caused by variations of attribute values. Specifically, this problem can be formulated as follows: given a formal context and its three-way concept lattice, if the attribute values are changed, how to update the corresponding three-way concept lattice. As in dynamic information systems, the values of attributes keep changing from time to time and the construction of a concept lattice is rather time consuming, the problem discussed in this paper is extremely important in both theoretical research and applications.
The rest of this paper is organized as follows. Section2 briefly reviews some basic notions in 3WCA. In Section 3, the influences of changing attribute values on the object-induced three-way concept lattice are studied, and the algorithms for updating the object-induced three-way concept lattice are proposed. In Section 4, we investigate the effect of changing attribute values on the attribute-induced three-way concept lattice. Finally, conclusions are provided in Section 5.Table 1
Students and their interests before they came to China.
Tang
Song
Yuan
Ming
Qing
1
×
×
2
×
×
×
3
×
×
×
4
×
×
5
×
×
×Table 2
Students and their interests after they came to China.
Tang
Song
Yuan
Ming
Qing
1
×
×
2
×
×
×
3
×
×
×
4
×
×
5
×
×


## 2. Preliminaries

A formal context is a tripleK=G,M,I [1], consisting of a nonempty finite set of objects G, a nonempty finite set of attributes M, and a crisp binary relation I which is functionally given as I:G×M⟶0,1 with Ix,a=1 (resp. Ix,a=0), indicating that object x satisfies (resp. does not satisfy) the attribute a. Moreover, the complement of K is defined as Kc=G,M,Ic, where Ic=G×M−I.ForX∈2G and A∈2M, the associated positive operators ∗:2G⟶2M and ∗:2M⟶2G are, respectively, defined as(1)X∗=a∈M∀x∈X,Ix,a=1,A∗=x∈G∀a∈A,Ix,a=1.Besides, the associated negative operators∗¯:2G⟶2M and ∗¯:2M⟶2G are, respectively, defined as(2)X∗¯=a∈M∀x∈X,Ix,a=0,A∗¯=x∈G∀a∈A,Ix,a=0.LetG be a nonempty finite set and 2G×2G be the Cartesian product. Then, 2G×2G is a poset. The corresponding partial order relation ≤ is defined as(3)A1,B1≥A2,B2⟺A1⊇A2,B1⊇B2.Moreover, ifA1=A2 and B1=B2, then A1,B1=A2,B2.In addition, the intersection “∩” and union “∪” in 2G×2G are, respectively, defined as(4)A1,B1∩A2,B2=A1∩A2,B1∩B2,A1,B1∪A2,B2=A1∪A2,B1∪B2.In 3WCA, there are two types of three-way concept lattices. One is the object-induced three-way concept lattice, and the other is the attribute-induced three-way concept lattice.Definition 1.
[14, 15]. Let K=G,M,I be a formal context, X∈2G and A,B∈2M×2M. A pair of three-way operators ⋗:2G⟶2M×2M and ⋖:2M×2M⟶2G are defined, respectively, as(5)X⋗=X∗,X∗¯,A,B⋖=A∗∩B∗¯.Definition 2.
[14, 15]. Let K=G,M,I be a formal context, X∈2G and A,B∈2M×2M. If X⋗=A,B and A,B⋖=X, then the ordered pair X,A,B is called an object-induced three-way concept. Moreover, X and A,B are called the extent and intent of the concept X,A,B, respectively.
Then, all the object-induced three-way concepts contained inK form a complete lattice, which is called the object-induced three-way concept lattice of K and denoted by OELK.
Furthermore, letX1,A1,B1 and X2,A2,B2 be two concepts of K. If X1,A1,B1≤X2,A2,B2 and there does not exist another concept X3,A3,B3 of K such that X1,A1,B1≤X3,A3,B3≤X2,A2,B2, then X1,A1,B1 is called a lower neighbour of X2,A2,B2 or equivalently X2,A2,B2 is called an upper neighbour of X1,A1,B1, which is denoted by X1,A1,B1≺X2,A2,B2 or X2,A2,B2≻X1,A1,B1.Definition 3.
[14, 15]. Let K=G,M,I be a formal context, A∈2M and X,Y∈2G×2G. A pair of three-way operators ⋗:2M⟶2G×2G and ⋖:2G×2G⟶2M are defined, respectively, as(6)A⋗=A∗,A∗¯,X,Y⋖=X∗∩Y∗¯.Definition 4.
[14, 15]. Let K=G,M,I be a formal context, A∈2M and X,Y∈2G×2G. If A⋗=X,Y and X,Y⋖=A, then the ordered pair X,Y,A is called an attribute-induced three-way concept. Moreover, X,Y and A are called the extent and intent of the concept X,Y,A, respectively.
Then, all the attribute-induced three-way concepts contained inK form a complete lattice, which is called the attribute-induced three-way concept lattice of K and denoted by AELK.
Furthermore, letX1,Y1,A1 and X2,Y2,A2 be two concepts of K. If X1,Y1,A1≤X2,Y2,A2 and there does not exist another concept X3,Y3,A3 of K such that X1,Y1,A1≤X3,Y3,A3≤X2,Y2,A2, then X1,Y1,A1 is called a lower neighbour of X2,Y2,A2 or equivalently X2,Y2,A2 is called an upper neighbour of X1,Y1,A1, which is denoted by X1,Y1,A1≺X2,Y2,A2 or X2,Y2,A2≻X1,Y1,A1.


## 3. The Effects on Object-Induced Three-Way Concept Lattices When Changing Attribute Values

In this section, we investigate the effects on object-induced three-way concept lattices caused by the variations of attribute values. At the beginning, we give several useful symbols.(i)
LetI and I′ be the binary relations before and after changing a specific attribute value of the original formal context, respectively(ii)
LetOELK and OELK′ be the object-induced three-way concept lattices of the formal contexts before and after changing a specific attribute value of the original formal context, respectively


### 3.1. The Effects on Object-Induced Three-Way Concept Lattices When Changing Attribute Values from 0 to 1

In this section, we investigate the effects on object-induced three-way concept lattices when changing attribute values from 0 to 1.Theorem 1.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then the corresponding object-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, then generate a new concept X1∪x,A2∪a,B2−a(ii)
Furthermore, ifX1∪x=X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 and X2,A2,B2 are no longer concepts in the updated concept lattice
And ifX1∪x=X2 and A1,B1≠A2∪a,B2−a, then X2,A2,B2 is no longer a concept in the updated concept lattice.
And ifX1∪x≠X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 is no longer a concept in the updated concept lattice.Proof.
Firstly, we prove that ifX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, then X1∪x,A2∪a,B2−a is a new concept of the updated lattice.
On one hand, we haveX1∪x⋗I′=X1⋗I′∩x⋗I′. As the only change made to the context is changing Ix,a from 0 to 1 and a∈A1, we can deduce that x⋗I′=A2∪a,B2−a and X1⋗I′=X1⋗I=A1,B1. As X1,A1,B1≺X2,A2,B2, we get that A1⊇A2∪a and B1⊇B2−a.
Then, we have that(7)X1∪x⋗I′=X1⋗I′∩x⋗I′=A1,B1∩A2∪a,B2−a=A2∪a,B2−a.
On the other hand, we have(8)A2∪a,B2−a⋖I′=A2∪a∗I′∩B2−a∗¯I′=A2∗I′∩a∗I′∩B2−a∗¯I′.
Besides, based on the conditionX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, we get that X2⊇X1∪x. As the only change made to the context is changing Ix,a from 0 to 1, we can deduce that a∗I′=a∗I∪x=X1∪x and A2∗I′=A2∗I=X2. Moreover, it is easy to show that B2−a∗¯I′⊇B2∗¯I′=X2. To sum up, we derive that(9)A2∪a,B2−a⋖I′=A2∗I′∩a∗I′∩B2−a∗¯I′=X1∪x.
By combining (7) and (9), the first part of the theorem is proved.
As the proof of the second part of the theorem is trivial, we omit it here.Theorem 2.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then update the object-induced three-way concept lattice as follows: if there is a concept X1,A1,B1 with a∈A1, all the extents of its upper neighbours do not contain an element x, and X2,A2,B2 is a smallest father concept of X1,A1,B1 such that x∈X2, then generate a new concept X1∪x,A2∪a,B2−a.Proof.
It can be proved similarly as that of Theorem 1. Besides, it is trivial to show that bothX1,A1,B1 and X2,A2,B2 are still concepts of the lattice after changing Ix,a from 0 to 1.Theorem 3.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1 and if there is a concept X,A,B with x⊂X and a∈B, then update the object-induced three-way concept lattice as follows:(i)
If there does not exist a conceptA,B−a⋖,A,B−a, then generate a new concept X,A,B−a(ii)
If there does not exist a conceptX−x,X−x⋗, then generate a new concept X−x,A,B(iii)
X,A,B is no longer a concept after changing Ix,a from 0 to 1Proof.
Before changingIx,a from 0 to 1, a∈B implies that a is not possessed by X. After changing Ix,a from 0 to 1, a is possessed by object x. Then, X,A,B is no longer a concept. Meanwhile, B−a is the set of attributes which are not possessed by X. Moreover, as there does not exist a concept in the form of A,B−a⋖,A,B−a, we have to generate a new concept X,A,B−a. Besides, as B is the set of attributes which are not possessed by X−x and there does not exist a concept in the form of X−x,X−x⋗, we have to generate a new concept X−x,A,B.
Based on the above discussions, we propose Algorithm1 for updating an object-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
LetN be the number of concepts of OELK. In Algorithm 1, we visit the concept lattice only once. Therefore, the complexity of Algorithm 1 is ON.Algorithm 1:Updating object-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
Require: OELK and changing Ix,a from 0 to 1.
Ensure: OELK′.
(1)
Sort the concepts into a queueQ based on the ascending order of their extents.
(2)
For concept X,A,B in Q
(3)
If there exists another concept X′,A′,B′ such that X′,A′,B′≻X,A,B, a∈A, and x∈X′
(4)
Then
(5)
Generate a new conceptX∪x,A′∪a,B′−a.
(6)
IfX′=X∪x and A,B=A′∪a,B′−a, delete X′,A′,B′ and X,A,B.
(7)
IfX′=X∪x and A,B≠A′∪a,B′−a, delete X′,A′,B′.
(8)
IfX′≠X∪x and A,B=A′∪a,B′−a, delete X,A,B.
(9)
End If
(10)
If a∈A and all the extents of its upper neighbours do not contain x
(11)
Then
(12)
IfX′,A′,B′ is a smallest father concept of X,A,B such that x∈X′
(13)
then generate a new conceptX∪x,A′∪a,B′−a.
(14)
End If
(15)
If x⊂X and a∈B
(16)
Then
(17)
If there does not exist a conceptA,B−a⋖,A,B−a, then generate a concept X,A,B−a.
(18)
If there does not exist a conceptX−x,X−x⋗, then generate a concept X−x,A,B.
(19)
DeleteX,A,B.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.


### 3.2. The Effects on Object-Induced Three-Way Concept Lattices When Changing Attribute Values from 1 to 0

In this section, we study the effects on object-induced three-way concept lattices when changing attribute values from 1 to 0.Theorem 4.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then the corresponding object-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, then generate a new concept X1∪x,A2−a,B2∪a(ii)
Furthermore, ifX1∪x=X2 and A1,B1=A2−a,B2∪a, then X1,A1,B1 and X2,A2,B2 are no longer concepts in the updated concept lattice
And ifX1∪x=X2 and A1,B1≠A2−a,B2∪a, then X2,A2,B2 is no longer a concept in the updated concept lattice.
And ifX1∪x≠X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 is no longer a concept in the updated concept lattice.Proof.
Firstly, we prove that ifX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, then X1∪x,A2−a,B2∪a is a new concept of the updated lattice.
On one hand, we haveX1∪x⋗I′=X1⋗I′∩x⋗I′. As the only change made to the context is changing Ix,a from 1 to 0 and a∈B1, we can deduce that x⋗I′=A2−a,B2∪a and X1⋗I′=X1⋗I=A1,B1. As X1,A1,B1≺X2,A2,B2, we get that A1⊇A2−a and B1⊇B2∪a.
Then, we have that(10)X1∪​x⋗I′=X1⋗I′∩​x⋗I′=A1,B1∩A2−a,B2∪a=A2−a,B2∪a.
On the other hand, we have(11)A2−a,B2∪a⋖I′=A2−a∗I′∩B2∪a∗¯I′=A2−a∗I′∩B2∗¯I′∩a∗¯I′.
Besides, based on the conditionX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, we get that X2⊇X1∪x. As the only change made to the context is changing Ix,a from 1 to 0, we can deduce that a∗¯I′=a∗¯I∪x=X1∪x and B2∗¯I′=B2∗¯I=X2. Moreover, it is easy to show that A2−a∗I′⊇A2∗I′=X2. To sum up, we derive that(12)A2−a,B2∪a⋖I′=A2−a∗I′∩B2∗¯I′∩a∗¯I′=X1∪x.
By combining (10) and (12), the first part of the theorem is proved.
As the proof of the second part of the theorem is trivial, we omit it here.Theorem 5.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then update the object-induced three-way concept lattice as follows: if there is a concept X1,A1,B1 with a∈B1, all the extents of its upper neighbours do not contain an element x, and X2,A2,B2 is a smallest father concept of X1,A1,B1 such that x∈X2, then generate a new concept X1∪x,A2−a,B2∪a.Proof.
It can be proved similarly as that of Theorem 4. Besides, it is trivial to show that bothX1,A1,B1 and X2,A2,B2 are still concepts of the lattice after changing Ix,a from 1 to 0.Theorem 6.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0 and if there is a concept X,A,B with x⊂X and a∈A, then update the object-induced three-way concept lattice as follows:(i)
If there does not exist a conceptA−a,B⋖,A−a,B, then generate a new concept X,A−a,B(ii)
If there does not exist a conceptX−x,X−x⋗, then generate a new concept X−x,A,B(iii)
X,A,B is no longer a concept after changing Ix,a from 1 to 0Proof.
Before changingIx,a from 1 to 0, a∈A implies that a is possessed by X. After changing Ix,a from 1 to 0, a is not possessed by object x. Then, X,A,B is no longer a concept. Meanwhile, A−a is the set of attributes which are commonly possessed by X. Moreover, as there does not exist a concept in the form of A−a,B⋖,A−a,B, we have to generate a new concept X,A−a,B. Besides, as A is the set of attributes which are possessed by X−x and there does not exist a concept in the form of X−x,X−x⋗, we have to generate a new concept X−x,A,B.
Based on the above discussions, we propose Algorithm2 for updating an object-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
LetN be the number of concepts of OELK. Similar to Algorithm 1, the complexity of Algorithm 2 is also ON.Algorithm 2:Updating object-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
Require: OELK and changing Ix,a from 1 to 0.
Ensure: OELK′.
(1)
Sort the concepts into a queueQ based on the ascending order of their extents.
(2)
For concept X,A,B in Q
(3)
If there exists another concept X′,A′,B′ such that X′,A′,B′≻X,A,B, a∈B, and x∈X′
(4)
Then
(5)
Generate a new conceptX∪x,A′−a,B′∪a.
(6)
IfX′=X∪x and A,B=A′−a,B′∪a, delete X′,A′,B′ and X,A,B.
(7)
IfX′=X∪x and A,B≠A′−a,B′∪a, delete X′,A′,B′.
(8)
IfX′≠X∪x and A,B=A′−a,B′∪a, delete X,A,B.
(9)
End If
(10)
If a∈B and all the extents of its upper neighbours do not contain x
(11)
Then
(12)
IfX′,A′,B′ is a smallest father concept of X,A,B such that x∈X′
(13)
then generate a new conceptX∪x,A′−a,B′∪a.
(14)
End If
(15)
If x⊂X and a∈A
(16)
Then
(17)
If there does not exist a conceptA−a,B⋖,A−a,B, then generate a concept X,A−a,B.
(18)
If there does not exist a conceptX−x,X−x⋗, then generate a concept X−x,A,B.
(19)
DeleteX,A,B.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.Example 2.
Table3 shows a formal context K=G,M,I with G=1,2,3,4 and M=a,b,c,d,e. In the table, “×” means an object has an attribute and a blank indicates the opposite. The corresponding object-induced three-way concept lattice OELK is shown in Figure 1.
For convenience, in the representation of a concept we omit the curly braces and commas. For instance, we use23,d,ce instead of 2,3,d,c,e.
When we changeI3,e from 0 to 1, the updating process is described briefly as follows:(i)
As there exist two cases that fulfill the conditions of Theorem 1, i.e., there exist3,abd,ce≻∅,abcde,abcde and 13,b,∅≻1,bce,ad, we generate two new concepts 13,be,∅ and 3,abde,c, respectively, and delete the old concepts 3,abd,ce and 13,b,∅(ii)
As there exist three cases that fulfill the conditions of Theorem 3, i.e., there exist234,∅,e, 23,d,ce and 34,a,e, we finally generate two new concepts 23,d,c and 34,a,∅ respectively, and delete the old concepts 234,∅,e, 23,d,ce, and 34,a,c(iii)
Update partial orders between concepts where necessary, and the updated object-induced three-way concept latticeOELK′ is shown in Figure 2
Continued with the above discussions, if we restoreI3,e to its original value 0, the updating process is shown as follows:(i)
As there exist four cases that fulfill the conditions of Theorem 4, i.e., there exist1234,∅,∅≻24,∅,be, 23,d,c≻2,d,abce, 34,a,∅≻4,ac,bde, and 3,abde,c≻∅,abcde,abcde, we generate four new concepts 234,∅,e, 23,d,ce, 34,a,e, and 3,abd,ce, respectively, and delete the old concepts 23,d,c, 34,a,∅, and 3,abde,c(ii)
As there exists a concept13,be,∅ that fulfills the conditions of Theorem 6, we generate a new concept 13,b,∅ and delete the old concept 13,be,∅(iii)
Update partial orders between concepts when necessary, and the updated object-induced three-way concept lattice restores its original lattice that is shown in Figure1Table 3
A formal contextK of Example 2.
a
b
c
d
e
1
×
×
×
2
×
3
×
×
×
4
×
×Figure 1
Object-induced three-way concept latticeOELK of Example 2.Figure 2
Updated object-induced three-way concept latticeOELK′ of Example 2.


## 3.1. The Effects on Object-Induced Three-Way Concept Lattices When Changing Attribute Values from 0 to 1

In this section, we investigate the effects on object-induced three-way concept lattices when changing attribute values from 0 to 1.Theorem 1.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then the corresponding object-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, then generate a new concept X1∪x,A2∪a,B2−a(ii)
Furthermore, ifX1∪x=X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 and X2,A2,B2 are no longer concepts in the updated concept lattice
And ifX1∪x=X2 and A1,B1≠A2∪a,B2−a, then X2,A2,B2 is no longer a concept in the updated concept lattice.
And ifX1∪x≠X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 is no longer a concept in the updated concept lattice.Proof.
Firstly, we prove that ifX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, then X1∪x,A2∪a,B2−a is a new concept of the updated lattice.
On one hand, we haveX1∪x⋗I′=X1⋗I′∩x⋗I′. As the only change made to the context is changing Ix,a from 0 to 1 and a∈A1, we can deduce that x⋗I′=A2∪a,B2−a and X1⋗I′=X1⋗I=A1,B1. As X1,A1,B1≺X2,A2,B2, we get that A1⊇A2∪a and B1⊇B2−a.
Then, we have that(7)X1∪x⋗I′=X1⋗I′∩x⋗I′=A1,B1∩A2∪a,B2−a=A2∪a,B2−a.
On the other hand, we have(8)A2∪a,B2−a⋖I′=A2∪a∗I′∩B2−a∗¯I′=A2∗I′∩a∗I′∩B2−a∗¯I′.
Besides, based on the conditionX1,A1,B1≺X2,A2,B2 with a∈A1 and x∈X2, we get that X2⊇X1∪x. As the only change made to the context is changing Ix,a from 0 to 1, we can deduce that a∗I′=a∗I∪x=X1∪x and A2∗I′=A2∗I=X2. Moreover, it is easy to show that B2−a∗¯I′⊇B2∗¯I′=X2. To sum up, we derive that(9)A2∪a,B2−a⋖I′=A2∗I′∩a∗I′∩B2−a∗¯I′=X1∪x.
By combining (7) and (9), the first part of the theorem is proved.
As the proof of the second part of the theorem is trivial, we omit it here.Theorem 2.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then update the object-induced three-way concept lattice as follows: if there is a concept X1,A1,B1 with a∈A1, all the extents of its upper neighbours do not contain an element x, and X2,A2,B2 is a smallest father concept of X1,A1,B1 such that x∈X2, then generate a new concept X1∪x,A2∪a,B2−a.Proof.
It can be proved similarly as that of Theorem 1. Besides, it is trivial to show that bothX1,A1,B1 and X2,A2,B2 are still concepts of the lattice after changing Ix,a from 0 to 1.Theorem 3.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1 and if there is a concept X,A,B with x⊂X and a∈B, then update the object-induced three-way concept lattice as follows:(i)
If there does not exist a conceptA,B−a⋖,A,B−a, then generate a new concept X,A,B−a(ii)
If there does not exist a conceptX−x,X−x⋗, then generate a new concept X−x,A,B(iii)
X,A,B is no longer a concept after changing Ix,a from 0 to 1Proof.
Before changingIx,a from 0 to 1, a∈B implies that a is not possessed by X. After changing Ix,a from 0 to 1, a is possessed by object x. Then, X,A,B is no longer a concept. Meanwhile, B−a is the set of attributes which are not possessed by X. Moreover, as there does not exist a concept in the form of A,B−a⋖,A,B−a, we have to generate a new concept X,A,B−a. Besides, as B is the set of attributes which are not possessed by X−x and there does not exist a concept in the form of X−x,X−x⋗, we have to generate a new concept X−x,A,B.
Based on the above discussions, we propose Algorithm1 for updating an object-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
LetN be the number of concepts of OELK. In Algorithm 1, we visit the concept lattice only once. Therefore, the complexity of Algorithm 1 is ON.Algorithm 1:Updating object-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
Require: OELK and changing Ix,a from 0 to 1.
Ensure: OELK′.
(1)
Sort the concepts into a queueQ based on the ascending order of their extents.
(2)
For concept X,A,B in Q
(3)
If there exists another concept X′,A′,B′ such that X′,A′,B′≻X,A,B, a∈A, and x∈X′
(4)
Then
(5)
Generate a new conceptX∪x,A′∪a,B′−a.
(6)
IfX′=X∪x and A,B=A′∪a,B′−a, delete X′,A′,B′ and X,A,B.
(7)
IfX′=X∪x and A,B≠A′∪a,B′−a, delete X′,A′,B′.
(8)
IfX′≠X∪x and A,B=A′∪a,B′−a, delete X,A,B.
(9)
End If
(10)
If a∈A and all the extents of its upper neighbours do not contain x
(11)
Then
(12)
IfX′,A′,B′ is a smallest father concept of X,A,B such that x∈X′
(13)
then generate a new conceptX∪x,A′∪a,B′−a.
(14)
End If
(15)
If x⊂X and a∈B
(16)
Then
(17)
If there does not exist a conceptA,B−a⋖,A,B−a, then generate a concept X,A,B−a.
(18)
If there does not exist a conceptX−x,X−x⋗, then generate a concept X−x,A,B.
(19)
DeleteX,A,B.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.


## 3.2. The Effects on Object-Induced Three-Way Concept Lattices When Changing Attribute Values from 1 to 0

In this section, we study the effects on object-induced three-way concept lattices when changing attribute values from 1 to 0.Theorem 4.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then the corresponding object-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, then generate a new concept X1∪x,A2−a,B2∪a(ii)
Furthermore, ifX1∪x=X2 and A1,B1=A2−a,B2∪a, then X1,A1,B1 and X2,A2,B2 are no longer concepts in the updated concept lattice
And ifX1∪x=X2 and A1,B1≠A2−a,B2∪a, then X2,A2,B2 is no longer a concept in the updated concept lattice.
And ifX1∪x≠X2 and A1,B1=A2∪a,B2−a, then X1,A1,B1 is no longer a concept in the updated concept lattice.Proof.
Firstly, we prove that ifX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, then X1∪x,A2−a,B2∪a is a new concept of the updated lattice.
On one hand, we haveX1∪x⋗I′=X1⋗I′∩x⋗I′. As the only change made to the context is changing Ix,a from 1 to 0 and a∈B1, we can deduce that x⋗I′=A2−a,B2∪a and X1⋗I′=X1⋗I=A1,B1. As X1,A1,B1≺X2,A2,B2, we get that A1⊇A2−a and B1⊇B2∪a.
Then, we have that(10)X1∪​x⋗I′=X1⋗I′∩​x⋗I′=A1,B1∩A2−a,B2∪a=A2−a,B2∪a.
On the other hand, we have(11)A2−a,B2∪a⋖I′=A2−a∗I′∩B2∪a∗¯I′=A2−a∗I′∩B2∗¯I′∩a∗¯I′.
Besides, based on the conditionX1,A1,B1≺X2,A2,B2 with a∈B1 and x∈X2, we get that X2⊇X1∪x. As the only change made to the context is changing Ix,a from 1 to 0, we can deduce that a∗¯I′=a∗¯I∪x=X1∪x and B2∗¯I′=B2∗¯I=X2. Moreover, it is easy to show that A2−a∗I′⊇A2∗I′=X2. To sum up, we derive that(12)A2−a,B2∪a⋖I′=A2−a∗I′∩B2∗¯I′∩a∗¯I′=X1∪x.
By combining (10) and (12), the first part of the theorem is proved.
As the proof of the second part of the theorem is trivial, we omit it here.Theorem 5.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then update the object-induced three-way concept lattice as follows: if there is a concept X1,A1,B1 with a∈B1, all the extents of its upper neighbours do not contain an element x, and X2,A2,B2 is a smallest father concept of X1,A1,B1 such that x∈X2, then generate a new concept X1∪x,A2−a,B2∪a.Proof.
It can be proved similarly as that of Theorem 4. Besides, it is trivial to show that bothX1,A1,B1 and X2,A2,B2 are still concepts of the lattice after changing Ix,a from 1 to 0.Theorem 6.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0 and if there is a concept X,A,B with x⊂X and a∈A, then update the object-induced three-way concept lattice as follows:(i)
If there does not exist a conceptA−a,B⋖,A−a,B, then generate a new concept X,A−a,B(ii)
If there does not exist a conceptX−x,X−x⋗, then generate a new concept X−x,A,B(iii)
X,A,B is no longer a concept after changing Ix,a from 1 to 0Proof.
Before changingIx,a from 1 to 0, a∈A implies that a is possessed by X. After changing Ix,a from 1 to 0, a is not possessed by object x. Then, X,A,B is no longer a concept. Meanwhile, A−a is the set of attributes which are commonly possessed by X. Moreover, as there does not exist a concept in the form of A−a,B⋖,A−a,B, we have to generate a new concept X,A−a,B. Besides, as A is the set of attributes which are possessed by X−x and there does not exist a concept in the form of X−x,X−x⋗, we have to generate a new concept X−x,A,B.
Based on the above discussions, we propose Algorithm2 for updating an object-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
LetN be the number of concepts of OELK. Similar to Algorithm 1, the complexity of Algorithm 2 is also ON.Algorithm 2:Updating object-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
Require: OELK and changing Ix,a from 1 to 0.
Ensure: OELK′.
(1)
Sort the concepts into a queueQ based on the ascending order of their extents.
(2)
For concept X,A,B in Q
(3)
If there exists another concept X′,A′,B′ such that X′,A′,B′≻X,A,B, a∈B, and x∈X′
(4)
Then
(5)
Generate a new conceptX∪x,A′−a,B′∪a.
(6)
IfX′=X∪x and A,B=A′−a,B′∪a, delete X′,A′,B′ and X,A,B.
(7)
IfX′=X∪x and A,B≠A′−a,B′∪a, delete X′,A′,B′.
(8)
IfX′≠X∪x and A,B=A′−a,B′∪a, delete X,A,B.
(9)
End If
(10)
If a∈B and all the extents of its upper neighbours do not contain x
(11)
Then
(12)
IfX′,A′,B′ is a smallest father concept of X,A,B such that x∈X′
(13)
then generate a new conceptX∪x,A′−a,B′∪a.
(14)
End If
(15)
If x⊂X and a∈A
(16)
Then
(17)
If there does not exist a conceptA−a,B⋖,A−a,B, then generate a concept X,A−a,B.
(18)
If there does not exist a conceptX−x,X−x⋗, then generate a concept X−x,A,B.
(19)
DeleteX,A,B.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.Example 2.
Table3 shows a formal context K=G,M,I with G=1,2,3,4 and M=a,b,c,d,e. In the table, “×” means an object has an attribute and a blank indicates the opposite. The corresponding object-induced three-way concept lattice OELK is shown in Figure 1.
For convenience, in the representation of a concept we omit the curly braces and commas. For instance, we use23,d,ce instead of 2,3,d,c,e.
When we changeI3,e from 0 to 1, the updating process is described briefly as follows:(i)
As there exist two cases that fulfill the conditions of Theorem 1, i.e., there exist3,abd,ce≻∅,abcde,abcde and 13,b,∅≻1,bce,ad, we generate two new concepts 13,be,∅ and 3,abde,c, respectively, and delete the old concepts 3,abd,ce and 13,b,∅(ii)
As there exist three cases that fulfill the conditions of Theorem 3, i.e., there exist234,∅,e, 23,d,ce and 34,a,e, we finally generate two new concepts 23,d,c and 34,a,∅ respectively, and delete the old concepts 234,∅,e, 23,d,ce, and 34,a,c(iii)
Update partial orders between concepts where necessary, and the updated object-induced three-way concept latticeOELK′ is shown in Figure 2
Continued with the above discussions, if we restoreI3,e to its original value 0, the updating process is shown as follows:(i)
As there exist four cases that fulfill the conditions of Theorem 4, i.e., there exist1234,∅,∅≻24,∅,be, 23,d,c≻2,d,abce, 34,a,∅≻4,ac,bde, and 3,abde,c≻∅,abcde,abcde, we generate four new concepts 234,∅,e, 23,d,ce, 34,a,e, and 3,abd,ce, respectively, and delete the old concepts 23,d,c, 34,a,∅, and 3,abde,c(ii)
As there exists a concept13,be,∅ that fulfills the conditions of Theorem 6, we generate a new concept 13,b,∅ and delete the old concept 13,be,∅(iii)
Update partial orders between concepts when necessary, and the updated object-induced three-way concept lattice restores its original lattice that is shown in Figure1Table 3
A formal contextK of Example 2.
a
b
c
d
e
1
×
×
×
2
×
3
×
×
×
4
×
×Figure 1
Object-induced three-way concept latticeOELK of Example 2.Figure 2
Updated object-induced three-way concept latticeOELK′ of Example 2.


## 4. The Effects on Attribute-Induced Three-Way Concept Lattices When Changing Attribute Values

By using duality principle, we can get the results about the effects on attribute-induced three-way concept lattices when changing attribute values. Hence, we just present our approaches but omit the details.


### 4.1. The Effects on Attribute-Induced Three-Way Concept Lattices When Changing Attribute Values from 0 to 1

In this subsection, we list the results about the effects on attribute-induced three-way concept lattices when changing attribute values from 0 to 1.Theorem 7.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then the corresponding attribute-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,Y1,A1≺X2,Y2,A2 with a∈A1 and x∈X2, then generate a new concept X1∪x,Y1−x,A2∪a(ii)
Furthermore, ifA1=A2∪a and X2,Y2=X1∪x,Y1−x, then X1,Y1,A1 and X2,Y2,A2 are no longer concepts in the updated concept lattice
And ifA1=A2∪a and X2,Y2≠X1∪x,Y1−x, then X1,Y1,A1 is no longer a concept in the updated concept lattice.
And ifA1≠A2∪a and X2,Y2=X1∪x,Y1−x, then X2,Y2,A2 is no longer a concept in the updated concept lattice.Theorem 8.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then update the attribute-induced three-way concept lattice as follows: if there is a concept X1,Y1,A1 with x∈X1, all the intents of its lower neighbours do not contain an element a, and X2,Y2,A2 is a biggest son concept of X1,Y1,A1 such that a∈A2, then generate a new concept X2∪x,Y2−x,A1∪a.Theorem 9.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1 and if there is a concept X,Y,A with a⊂A and x∈Y, then update the attribute-induced three-way concept lattice as follows:(i)
If there does not exist a conceptX,Y−x,X,Y−x⋗, then generate a new concept X,Y−x,A(ii)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a(iii)
X,Y,A is no longer a concept after changing Ix,a from 0 to 1
Based on the above discussions, we propose Algorithm3 for updating an attribute-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
LetN be the number of concepts of AELK. The complexity of Algorithm 3 is ON.Algorithm 3:Updating attribute-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
Require: AELK and changing Ix,a from 0 to 1.
Ensure: AELK′.
(1)
Sort the concepts into a queueQ based on the descending order of their extents.
(2)
For concept X,Y,A in Q
(3)
If there exists another concept X′,Y′,A′ such that X′,Y′,A′≺X,Y,A, a∈A′, and x∈X
(4)
Then
(5)
Generate a new conceptX′∪x,Y′−x,A∪a.
(6)
IfA′=A∪a and X,Y=X′∪x,Y′−x, delete X′,Y′,A′ and X,Y,A.
(7)
IfA′=A∪a and X,Y≠X′∪x,Y′−x, delete X′,Y′,A′.
(8)
IfA′≠A∪a and X,Y=X′∪x,Y′−x, delete X,Y,A.
(9)
End If
(10)
If x∈X and all the intents of its lower neighbours do not contain a
(11)
Then
(12)
IfX′,A′,B′ is a biggest son concept of X,Y,A such that a∈A′
(13)
then generate a new conceptX′∪x,Y′−x,A∪a.
(14)
End If
(15)
If a⊂A and x∈Y
(16)
Then
(17)
If there does not exist a conceptX,Y−x,X,Y−x⋗, then generate a new concept X,Y−x,A.
(18)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a.
(19)
DeleteX,Y,A.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.


### 4.2. The Effects on Attribute-Induced Three-Way Concept Lattices When Changing Attribute Values from 1 to 0

In this subsection, we list the results about the effects on attribute-induced three-way concept lattices when changing attribute values from 1 to 0.Theorem 10.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then the corresponding attribute-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,Y1,A1≺X2,Y2,A2 with a∈A1 and x∈Y2, then generate a new concept X1−x,Y1∪x,A2∪a(ii)
Furthermore, ifA1=A2∪a and X2,Y2=X1−x,Y1∪x, then X1,Y1,A1 and X2,Y2,A2 are no longer concepts in the updated concept lattice
And ifA1=A2∪a and X2,Y2≠X1−x,Y1∪x, then X1,Y1,A1 is no longer a concept in the updated concept lattice.
And ifA1≠A2∪a and X2,Y2=X1−x,Y1∪x, then X2,Y2,A2 is no longer a concept in the updated concept lattice.Theorem 11.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then update the attribute-induced three-way concept lattice as follows: if there is a concept X1,Y1,A1 with x∈Y1, all the intents of its lower neighbours do not contain an element a, and X2,Y2,A2 is a biggest son concept of X1,Y1,A1 such that a∈A2, then generate a new concept X2−x,Y2∪x,A1∪a.Theorem 12.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0 and if there is a concept X,Y,A with a⊂A and x∈X, then update the attribute-induced three-way concept lattice as follows:(i)
If there does not exist a conceptX−x,Y,X−x,Y⋗, then generate a new concept X−x,Y,A(ii)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a(iii)
X,Y,A is no longer a concept after changing Ix,a from 1 to 0
Based on the above discussions, we propose Algorithm4 for updating an attribute-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
LetN be the number of concepts of AELK. The complexity of Algorithm 4 is ON.Algorithm 4:Updating attribute-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
Require: AELK and changing Ix,a from 1 to 0.
Ensure: AELK′.
(1)
Sort the concepts into a queueQ based on the descending order of their extents.
(2)
For concept X,Y,A in Q
(3)
If there exists another concept X′,Y′,A′ such that X′,Y′,A′≺X,Y,A, a∈A′, and x∈Y
(4)
Then
(5)
Generate a new conceptX′−x,Y′∪x,A∪a.
(6)
IfA′=A∪a and X,Y=X′−x,Y′∪x, delete X′,Y′,A′ and X,Y,A.
(7)
IfA′=A∪a and X,Y≠X′−x,Y′∪x, delete X′,Y′,A′.
(8)
IfA′≠A∪a and X,Y=X′−x,Y′∪x, delete X,Y,A.
(9)
End If
(10)
If x∈Y and all the intents of its lower neighbours do not contain a
(11)
Then
(12)
IfX′,A′,B′ is a biggest son concept of X,Y,A such that a∈A′
(13)
then generate a new conceptX′−x,Y′∪x,A∪a.
(14)
End If
(15)
If a⊂A and x∈X
(16)
Then
(17)
If there does not exist a conceptX−x,Y,X−x,Y⋗, then generate a new concept X−x,Y,A.
(18)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a.
(19)
DeleteX,Y,A.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.Example 3.
Table4 shows a formal context K=G,M,I with G=1,2,3,4 and M=a,b,c,d. In the table, “×” means an object has an attribute and a blank indicates the opposite. The corresponding attribute-induced three-way concept lattice AELK is shown in Figure 3.
When we changeI3,a from 0 to 1, the updating process is recorded briefly as follows:(i)
As there exists a pair of concepts12,34,a≺1234,1234,∅ that fulfill the conditions of Theorem 7, we generate a new concept 123,4,a and delete the old concept 12,34,a(ii)
As there exists a concept23,14,b that fulfills the conditions of Theorem 8, we generate a new concept 23,4,ab(iii)
As there exist three concepts1,3,ac, 2,34,ad, and ∅,3,acd that fulfill the conditions of Theorem 9, we finally generate two new concepts 1,∅,ac and ∅,3,cd and delete old concepts 1,3,ac, 2,34,ad, and ∅,3,acd(iv)
Update partial orders between concepts when necessary, and the updated attribute-induced three-way concept latticeAELK′ is shown in Figure 4
Continued with the above discussions, if we restoreI3,a to its original value 0, the updating process is depicted briefly as follows:(i)
As there exist three pairs of concepts123,4,a≺1234,1234,∅, 1,∅,ac≺14,23,c, and ∅,∅,abcd≺∅,3,cd that fulfill the conditions of Theorem 10, we generate three new concepts 12,34,a, 1,3,ac, and ∅,3,acd and delete the old concepts 123,4,a, 1,∅,ac, and ∅,3,cd(ii)
As there exists a concept2,134,d that fulfills the conditions of Theorem 11, we generate a new concept 2,34,ad(iii)
As there exists a concept23,4,ab that fulfills the conditions of Theorem 12, we delete this old concept(iv)
Update partial orders between concepts when necessary, and the updated attribute-induced three-way concept lattice restores its original lattice that is shown in Figure3Table 4
A formal contextK of Example 3.
a
b
c
d
1
×
×
2
×
×
×
3
×
4
×Figure 3
Attribute-induced three-way concept latticeAELK of Example 3.Figure 4
Updated attribute-induced three-way concept latticeAELK′ of Example 3.


## 4.1. The Effects on Attribute-Induced Three-Way Concept Lattices When Changing Attribute Values from 0 to 1

In this subsection, we list the results about the effects on attribute-induced three-way concept lattices when changing attribute values from 0 to 1.Theorem 7.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then the corresponding attribute-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,Y1,A1≺X2,Y2,A2 with a∈A1 and x∈X2, then generate a new concept X1∪x,Y1−x,A2∪a(ii)
Furthermore, ifA1=A2∪a and X2,Y2=X1∪x,Y1−x, then X1,Y1,A1 and X2,Y2,A2 are no longer concepts in the updated concept lattice
And ifA1=A2∪a and X2,Y2≠X1∪x,Y1−x, then X1,Y1,A1 is no longer a concept in the updated concept lattice.
And ifA1≠A2∪a and X2,Y2=X1∪x,Y1−x, then X2,Y2,A2 is no longer a concept in the updated concept lattice.Theorem 8.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1, then update the attribute-induced three-way concept lattice as follows: if there is a concept X1,Y1,A1 with x∈X1, all the intents of its lower neighbours do not contain an element a, and X2,Y2,A2 is a biggest son concept of X1,Y1,A1 such that a∈A2, then generate a new concept X2∪x,Y2−x,A1∪a.Theorem 9.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=0. If we change the value of Ix,a from 0 to 1 and if there is a concept X,Y,A with a⊂A and x∈Y, then update the attribute-induced three-way concept lattice as follows:(i)
If there does not exist a conceptX,Y−x,X,Y−x⋗, then generate a new concept X,Y−x,A(ii)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a(iii)
X,Y,A is no longer a concept after changing Ix,a from 0 to 1
Based on the above discussions, we propose Algorithm3 for updating an attribute-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
LetN be the number of concepts of AELK. The complexity of Algorithm 3 is ON.Algorithm 3:Updating attribute-induced three-way concept lattice when changing a specific attribute value from 0 to 1.
Require: AELK and changing Ix,a from 0 to 1.
Ensure: AELK′.
(1)
Sort the concepts into a queueQ based on the descending order of their extents.
(2)
For concept X,Y,A in Q
(3)
If there exists another concept X′,Y′,A′ such that X′,Y′,A′≺X,Y,A, a∈A′, and x∈X
(4)
Then
(5)
Generate a new conceptX′∪x,Y′−x,A∪a.
(6)
IfA′=A∪a and X,Y=X′∪x,Y′−x, delete X′,Y′,A′ and X,Y,A.
(7)
IfA′=A∪a and X,Y≠X′∪x,Y′−x, delete X′,Y′,A′.
(8)
IfA′≠A∪a and X,Y=X′∪x,Y′−x, delete X,Y,A.
(9)
End If
(10)
If x∈X and all the intents of its lower neighbours do not contain a
(11)
Then
(12)
IfX′,A′,B′ is a biggest son concept of X,Y,A such that a∈A′
(13)
then generate a new conceptX′∪x,Y′−x,A∪a.
(14)
End If
(15)
If a⊂A and x∈Y
(16)
Then
(17)
If there does not exist a conceptX,Y−x,X,Y−x⋗, then generate a new concept X,Y−x,A.
(18)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a.
(19)
DeleteX,Y,A.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.


## 4.2. The Effects on Attribute-Induced Three-Way Concept Lattices When Changing Attribute Values from 1 to 0

In this subsection, we list the results about the effects on attribute-induced three-way concept lattices when changing attribute values from 1 to 0.Theorem 10.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then the corresponding attribute-induced three-way concept lattice needs to be updated as follows:(i)
If there are two conceptsX1,Y1,A1≺X2,Y2,A2 with a∈A1 and x∈Y2, then generate a new concept X1−x,Y1∪x,A2∪a(ii)
Furthermore, ifA1=A2∪a and X2,Y2=X1−x,Y1∪x, then X1,Y1,A1 and X2,Y2,A2 are no longer concepts in the updated concept lattice
And ifA1=A2∪a and X2,Y2≠X1−x,Y1∪x, then X1,Y1,A1 is no longer a concept in the updated concept lattice.
And ifA1≠A2∪a and X2,Y2=X1−x,Y1∪x, then X2,Y2,A2 is no longer a concept in the updated concept lattice.Theorem 11.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0, then update the attribute-induced three-way concept lattice as follows: if there is a concept X1,Y1,A1 with x∈Y1, all the intents of its lower neighbours do not contain an element a, and X2,Y2,A2 is a biggest son concept of X1,Y1,A1 such that a∈A2, then generate a new concept X2−x,Y2∪x,A1∪a.Theorem 12.
LetK=G,M,I be a formal context, x∈G, a∈M, and Ix,a=1. If we change the value of Ix,a from 1 to 0 and if there is a concept X,Y,A with a⊂A and x∈X, then update the attribute-induced three-way concept lattice as follows:(i)
If there does not exist a conceptX−x,Y,X−x,Y⋗, then generate a new concept X−x,Y,A(ii)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a(iii)
X,Y,A is no longer a concept after changing Ix,a from 1 to 0
Based on the above discussions, we propose Algorithm4 for updating an attribute-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
LetN be the number of concepts of AELK. The complexity of Algorithm 4 is ON.Algorithm 4:Updating attribute-induced three-way concept lattice when changing a specific attribute value from 1 to 0.
Require: AELK and changing Ix,a from 1 to 0.
Ensure: AELK′.
(1)
Sort the concepts into a queueQ based on the descending order of their extents.
(2)
For concept X,Y,A in Q
(3)
If there exists another concept X′,Y′,A′ such that X′,Y′,A′≺X,Y,A, a∈A′, and x∈Y
(4)
Then
(5)
Generate a new conceptX′−x,Y′∪x,A∪a.
(6)
IfA′=A∪a and X,Y=X′−x,Y′∪x, delete X′,Y′,A′ and X,Y,A.
(7)
IfA′=A∪a and X,Y≠X′−x,Y′∪x, delete X′,Y′,A′.
(8)
IfA′≠A∪a and X,Y=X′−x,Y′∪x, delete X,Y,A.
(9)
End If
(10)
If x∈Y and all the intents of its lower neighbours do not contain a
(11)
Then
(12)
IfX′,A′,B′ is a biggest son concept of X,Y,A such that a∈A′
(13)
then generate a new conceptX′−x,Y′∪x,A∪a.
(14)
End If
(15)
If a⊂A and x∈X
(16)
Then
(17)
If there does not exist a conceptX−x,Y,X−x,Y⋗, then generate a new concept X−x,Y,A.
(18)
If there does not exist a conceptA−a⋖,A−a, then generate a new concept X,Y,A−a.
(19)
DeleteX,Y,A.
(20)
End If
(21)
Update partial orders between concepts where necessary.
(22)
End For
(23)
Return the updated lattice and end the algorithm.Example 3.
Table4 shows a formal context K=G,M,I with G=1,2,3,4 and M=a,b,c,d. In the table, “×” means an object has an attribute and a blank indicates the opposite. The corresponding attribute-induced three-way concept lattice AELK is shown in Figure 3.
When we changeI3,a from 0 to 1, the updating process is recorded briefly as follows:(i)
As there exists a pair of concepts12,34,a≺1234,1234,∅ that fulfill the conditions of Theorem 7, we generate a new concept 123,4,a and delete the old concept 12,34,a(ii)
As there exists a concept23,14,b that fulfills the conditions of Theorem 8, we generate a new concept 23,4,ab(iii)
As there exist three concepts1,3,ac, 2,34,ad, and ∅,3,acd that fulfill the conditions of Theorem 9, we finally generate two new concepts 1,∅,ac and ∅,3,cd and delete old concepts 1,3,ac, 2,34,ad, and ∅,3,acd(iv)
Update partial orders between concepts when necessary, and the updated attribute-induced three-way concept latticeAELK′ is shown in Figure 4
Continued with the above discussions, if we restoreI3,a to its original value 0, the updating process is depicted briefly as follows:(i)
As there exist three pairs of concepts123,4,a≺1234,1234,∅, 1,∅,ac≺14,23,c, and ∅,∅,abcd≺∅,3,cd that fulfill the conditions of Theorem 10, we generate three new concepts 12,34,a, 1,3,ac, and ∅,3,acd and delete the old concepts 123,4,a, 1,∅,ac, and ∅,3,cd(ii)
As there exists a concept2,134,d that fulfills the conditions of Theorem 11, we generate a new concept 2,34,ad(iii)
As there exists a concept23,4,ab that fulfills the conditions of Theorem 12, we delete this old concept(iv)
Update partial orders between concepts when necessary, and the updated attribute-induced three-way concept lattice restores its original lattice that is shown in Figure3Table 4
A formal contextK of Example 3.
a
b
c
d
1
×
×
2
×
×
×
3
×
4
×Figure 3
Attribute-induced three-way concept latticeAELK of Example 3.Figure 4
Updated attribute-induced three-way concept latticeAELK′ of Example 3.


## 5. Conclusion

In this paper, we study the influences of three-way concept lattices caused by variations of attribute values. Concretely, changes can be classified into two types. One is changing a specific attribute value from 0 to 1, and the other is from 1 to 0. Besides, as there are two types of three-way concept lattices, i.e., object-induced three-way concept lattice and attribute-induce three-way concept lattice, we give our solutions to the problems of these two types of three-way concept lattices, respectively. Besides, we also employ illustrative examples to show the details of our proposed methods.Some interesting and unsolved problems still deserve to be studied. For example, as knowledge representation and reasoning in fuzzy systems are extremely complex [35, 36, 37], how to update fuzzy concept lattice and fuzzy association rules are more interesting and challenging. In addition, how to effectively update approximate three-way concept lattices [22, 38, 39] is another interesting problem. These issues will be studied in our forthcoming work.



---

*Source: 7865197-2019-09-30.xml*