# Three-Way Concept Analysis for Incomplete Formal Contexts

Authors: Huilai Zhi; Hao Chao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Recently, incomplete formal contexts have received more and more attention from the communities of formal concept analysis. Different from a complete context where the binary relations between all the objects and attribute are known, an incomplete formal context has at least a pair of object and attribute with a completely unknown binary relation. Partially known formal concepts use interval sets to indicate the incompleteness. Three-way formal concept analysis is capable of characterizing a target set by combining positive and negative attributes. However, how to describe target set, by pointing out what attributes it has with certainty and what attributes it has with possibility and what attributes it does not has with certainty and what attributes it does not has with possibility, is still an open problem. This paper combines the ideas of three-way formal concept analysis and partially known formal concepts and presents a framework of approximate three-way concept analysis. At first, approximate object-induced and attribute-induced three-way concept lattices are introduced, respectively. And then, the relationship between approximate three-way concept lattice and classical three-way concept lattice are investigated. Finally, examples are presented to demonstrate and verify the obtained results.


---

## Body

## 1. Introduction

Formal concept analysis (FCA), a mathematical framework founded on lattice theory [1], has become an effective data analysis tool in various applications [2–5]. Formal context and formal concept are two cornerstones in FCA. A formal context, which is composed of a nonempty set of objects and a nonempty set of attributes, describes a domain in an ideal case. Given any object of the context, one can precisely point out which attributes it possesses and which attributes it does not possess. Intuitively, a concept is composed of two parts, that is, a set of objects, which is known as the extent of the concept, and a set of attributes, which is known as the intent of the concept. The “jointly possessed” relationship between the extent and the intent of a concept is affirmative; i.e., each object of the extent has all the attributes in the intent with certainty and each attribute of the intent is enjoyed by all the objects in the extent with certainty.In classical FCA, only positive attributes are concerned. As a result, given a set of objects, one cannot directly point out which attributes they do not possess. By incorporating the ideas of three-way decisions [6, 7], Qi et al. [8] proposedthree-way concept analysis (3WCA), in which one can characterize target set by both positive and negative attributes. Studies have shown that three-way concepts can provide more details than that of classical concepts [9]. Intuitively, the intent of an object-induced three-way concept has positive part and negative part. Positive part points out which attributes are enjoyed by all the objects in the extent, while negative part points out which attributes are not enjoyed by all the objects in the extent. Dually, the extent of an attribute-induced three-way concept is also equipped with both positive part and negative part.Since its the proposal, 3WCA has become a hot topic. For instance, Qian et al. [10] proposed a method of constructing three-way concept lattices by using divide and conquer strategy. Singh [11, 12] used three-way fuzzy concept lattice to facilitate medical diagnoses and also took uncertain attributes into consideration and put forward a method of decomposing a context based on positive, negative, and uncertain attributes. Li et al. [13] studied the cognitive learning process based on three-way concepts. Zhi and Li [14] studied granule description based on positive and negative attributes.However, in many circumstances, we can not describe the relationships between objects and attributes precisely and completely. Incomplete formal contexts, introduced by Burmeister and Holzer [15], are a widely adopted approach to deal with the incompleteness of data. In an incomplete formal context, an object enjoys a set of attribute and does not enjoy another set of attributes; meanwhile, whether this object enjoys the rest of attributes is not known. Partially known formal concepts, which extend classical formal concepts and use interval set to manage the incompleteness [16–20], have been intensively studied. Ill-known formal concept [21] and approximate concepts [22, 23] are all examples of partially known formal concepts. However, in the aforementioned studies only positive attributes were considered while negative ones were ignored. In order to manage incompleteness and take both positive and negative attributes into consideration, it is appealing and interesting to combine 3WCA and partially known formal concepts together. And this is also the objective of this paper.This paper is organized as follows. Section2 briefly reviews some basic notions in FCA, 3WCA, and incomplete formal contexts. Section 3 introduces approximate object-induced three-way concept lattice. Besides, the relationships between approximate object-induced three-way concept lattice and classical object-induced three-way concept lattice [8, 9] is also investigated. By applying duality principle, Section 4 briefly presents approximate attribute-induced three-way concept lattice. Finally, conclusions are provided in Section 5.


## 2. Related Theoretical Foundations

In this section, in order to make our paper self-contained, we briefly review some basic notions in FCA, 3WCA, and incomplete formal contexts.


### 2.1. Formal Concept Analysis

The discussions of formal concept analysis always start with the notion of a formal context defined as follows.Definition 1 (see [24]).
A formal context is a tripleK=(G,M,I), where G and M are two nonempty and finite sets, and I is a binary relation on G×M specifies the relationships between G and M. Moreover, G and M are called object set and attribute set, respectively, and, for any x∈G and a∈M, one uses (x,a)∈I to indicate that the object x has the attribute a and (x,a)∈I to indicate the opposite.In order to define a formal concept, one has to define two derivation operators as follows.Definition 2 (see [24]).
LetK=(G,M,I) be a formal context. For X∈2G and A∈2M; the derivation operations ∗:2G→2M and ∗:2M→2G are defined by (1)X∗=a∈M∣∀x∈X,x,a∈IandA∗=x∈G∣∀a∈A,x,a∈I,respectively.By using the above two derivation operators, formal concepts can be defined as follows.Definition 3 (see [24]).
LetK=(G,M,I) be a formal context, X∈2G and A∈2M. The pair (X,A) is called a formal concept, if X∗=A and A∗=X.Then, all the concepts contained inK, ordered by (2)X1,A1≤X2,A2⇔X1⊆X2⇔A1⊇A2,form a complete lattice, which is known as the concept lattice of K and denoted by L(K).


### 2.2. Three-Way Concept Analysis

Concept lattice uses positive attributes to characterize a target set. However, many studies have shown that positive attributes and negative attributes are of equal importance in describing a target [25–28]. By taking both positive and negative attributes into consideration, Qi et al. [8, 9] proposedthree-way concept analysis (3WCA), which has become a hot topic in FCA [10, 20, 23].Definition 4 (see [24]).
LetK=(G,M,I) be a formal context. For X∈2G and A∈2M, the negative derivation operations ∗-:2G→2M and ∗-:2M→2G are defined by (3)X∗-=a∈M∣∀x∈X,x,a∈IcandA∗-=x∈G∣∀a∈A,x,a∈Ic,respectively, where Ic=G×M-I.Definition 5 (see [8, 9]).
LetK=(G,M,I) be a formal context. For X∈2G and (A,B)∈2M×2M, the three-way derivation operations p:2G→2M×2M and q:2M×2M→2G are defined by (4)Xp=X∗,X∗-andA,Bq=A∗∩B∗-,respectively.Definition 6 (see [8, 9]).
LetK=(G,M,I) be a formal context, X∈2G and (A,B)∈2M×2M. The pair (X,(A,B)) is called an object-induced three-way concept, if Xp=(A,B) and (A,B)q=X.Then, all the object-induced three-way concepts contained inK, ordered by (5)X1,A1,B1≤X2,A2,B2⇔X1⊆X2⇔A1⊇A2andB1⊇B2,form a complete lattice, which is called the object-induced three-way concept lattice (OEL for short) of K and denoted by OEL(K). The algorithm for building OEL can be found in [9].Dually, we can define attribute-induced three-way concept lattice (AEL for short) of K and denote it by AEL(K). Interested readers can refer to [8, 9] for more details.Both object-induced three-way concepts and attribute-induced three-way concepts are collectively called three-way concepts. Likewise, both object-induced three-way concept lattices and attribute-induced three-way concept lattices are collectively called three-way concept lattices.


### 2.3. Incomplete Formal Context

To establish a sound semantical basis, a possible world semantics of an incomplete formal context as a family of complete formal contexts was introduced by several researchers [15, 29, 30]. More appealingly, Djouadi [21] provided an elegant interpretation of an incomplete context in terms of two special completions.Definition 7 (see [15]).
An incomplete context is a quadrupleK=(G,M,{+,?,-},R) consisting of a nonempty and finite set G of objects, a nonempty and finite set M of attributes, the set {+,?,-} of values, and a mapping R:G×M→{+,?,-}, where R(x,a)=+ means x has the attribute a, R(x,a)=- means that the object x does not have the attribute a, and R(x,a)=? indicates that it is unknown whether or not the object x has the attribute a.In the remainder of this paper, a formal context defined in Definition1 is called a complete context in order to distinguish it from an incomplete context.Definition 8 (see [20]).
A complete formal contextK=(G,M,J) is called a completion of K=(G,M,{+,?,-},R) if J satisfies the following two conditions: (6)Rx,a=+⇒x,a∈J,Rx,a=-⇒x,a∈J.Here, the binaryJ is derived by changing each ? into either + or −.Definition 9 (see [20]).
In an incomplete contextK=(G,M,{+,?,-},R), the least completion and the greatest completion are defined by (7)K∗=G,M,J∗,J∗=x,a∣Rx,a=+,K∗=G,M,J∗,J∗=x,a∣Rx,a=+∪x,a∣Rx,a=?,respectively.Example 10.
Table1 depicts an incomplete context K=(G,M,{+,?,-},R) in which G={1,2,3,4,5} and M={a,b,c,d,e,f}.Table 1
An example of incomplete formal contextK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − ? 4 − ? − + + + 5 − + + + − −The greatest and least completion ofK, i.e., K∗ and K∗, are shown in Tables 2 and 3, respectively.Table 2
The greatest completion ofK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − + 4 − + − + + + 5 − + + + − −Table 3
The least completion ofK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − − 4 − − − + + + 5 − + + + − −


## 2.1. Formal Concept Analysis

The discussions of formal concept analysis always start with the notion of a formal context defined as follows.Definition 1 (see [24]).
A formal context is a tripleK=(G,M,I), where G and M are two nonempty and finite sets, and I is a binary relation on G×M specifies the relationships between G and M. Moreover, G and M are called object set and attribute set, respectively, and, for any x∈G and a∈M, one uses (x,a)∈I to indicate that the object x has the attribute a and (x,a)∈I to indicate the opposite.In order to define a formal concept, one has to define two derivation operators as follows.Definition 2 (see [24]).
LetK=(G,M,I) be a formal context. For X∈2G and A∈2M; the derivation operations ∗:2G→2M and ∗:2M→2G are defined by (1)X∗=a∈M∣∀x∈X,x,a∈IandA∗=x∈G∣∀a∈A,x,a∈I,respectively.By using the above two derivation operators, formal concepts can be defined as follows.Definition 3 (see [24]).
LetK=(G,M,I) be a formal context, X∈2G and A∈2M. The pair (X,A) is called a formal concept, if X∗=A and A∗=X.Then, all the concepts contained inK, ordered by (2)X1,A1≤X2,A2⇔X1⊆X2⇔A1⊇A2,form a complete lattice, which is known as the concept lattice of K and denoted by L(K).


## 2.2. Three-Way Concept Analysis

Concept lattice uses positive attributes to characterize a target set. However, many studies have shown that positive attributes and negative attributes are of equal importance in describing a target [25–28]. By taking both positive and negative attributes into consideration, Qi et al. [8, 9] proposedthree-way concept analysis (3WCA), which has become a hot topic in FCA [10, 20, 23].Definition 4 (see [24]).
LetK=(G,M,I) be a formal context. For X∈2G and A∈2M, the negative derivation operations ∗-:2G→2M and ∗-:2M→2G are defined by (3)X∗-=a∈M∣∀x∈X,x,a∈IcandA∗-=x∈G∣∀a∈A,x,a∈Ic,respectively, where Ic=G×M-I.Definition 5 (see [8, 9]).
LetK=(G,M,I) be a formal context. For X∈2G and (A,B)∈2M×2M, the three-way derivation operations p:2G→2M×2M and q:2M×2M→2G are defined by (4)Xp=X∗,X∗-andA,Bq=A∗∩B∗-,respectively.Definition 6 (see [8, 9]).
LetK=(G,M,I) be a formal context, X∈2G and (A,B)∈2M×2M. The pair (X,(A,B)) is called an object-induced three-way concept, if Xp=(A,B) and (A,B)q=X.Then, all the object-induced three-way concepts contained inK, ordered by (5)X1,A1,B1≤X2,A2,B2⇔X1⊆X2⇔A1⊇A2andB1⊇B2,form a complete lattice, which is called the object-induced three-way concept lattice (OEL for short) of K and denoted by OEL(K). The algorithm for building OEL can be found in [9].Dually, we can define attribute-induced three-way concept lattice (AEL for short) of K and denote it by AEL(K). Interested readers can refer to [8, 9] for more details.Both object-induced three-way concepts and attribute-induced three-way concepts are collectively called three-way concepts. Likewise, both object-induced three-way concept lattices and attribute-induced three-way concept lattices are collectively called three-way concept lattices.


## 2.3. Incomplete Formal Context

To establish a sound semantical basis, a possible world semantics of an incomplete formal context as a family of complete formal contexts was introduced by several researchers [15, 29, 30]. More appealingly, Djouadi [21] provided an elegant interpretation of an incomplete context in terms of two special completions.Definition 7 (see [15]).
An incomplete context is a quadrupleK=(G,M,{+,?,-},R) consisting of a nonempty and finite set G of objects, a nonempty and finite set M of attributes, the set {+,?,-} of values, and a mapping R:G×M→{+,?,-}, where R(x,a)=+ means x has the attribute a, R(x,a)=- means that the object x does not have the attribute a, and R(x,a)=? indicates that it is unknown whether or not the object x has the attribute a.In the remainder of this paper, a formal context defined in Definition1 is called a complete context in order to distinguish it from an incomplete context.Definition 8 (see [20]).
A complete formal contextK=(G,M,J) is called a completion of K=(G,M,{+,?,-},R) if J satisfies the following two conditions: (6)Rx,a=+⇒x,a∈J,Rx,a=-⇒x,a∈J.Here, the binaryJ is derived by changing each ? into either + or −.Definition 9 (see [20]).
In an incomplete contextK=(G,M,{+,?,-},R), the least completion and the greatest completion are defined by (7)K∗=G,M,J∗,J∗=x,a∣Rx,a=+,K∗=G,M,J∗,J∗=x,a∣Rx,a=+∪x,a∣Rx,a=?,respectively.Example 10.
Table1 depicts an incomplete context K=(G,M,{+,?,-},R) in which G={1,2,3,4,5} and M={a,b,c,d,e,f}.Table 1
An example of incomplete formal contextK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − ? 4 − ? − + + + 5 − + + + − −The greatest and least completion ofK, i.e., K∗ and K∗, are shown in Tables 2 and 3, respectively.Table 2
The greatest completion ofK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − + 4 − + − + + + 5 − + + + − −Table 3
The least completion ofK.
a b c d e f 1 + + − − + + 2 − + + − − + 3 + − − − − − 4 − − − + + + 5 − + + + − −


## 3. Approximate Object-Induced Three-Way Concept Lattice

In this section, we propose approximate object-induced three-way concept lattice. Besides, we further study the relationships between approximate object-induced three-way concept lattice and classical object-induced three-way concept lattice [8, 9].


### 3.1. Approximate Object-Induced Three-Way Concept Lattice

As there exist uncertainties in the incomplete formal context, the attributes shared by target set may not be fixed. In order to solve this problem, we will use intervals to indicate the variances in building an approximate three-way concept.Definition 11.
LetK=(G,M,{+,?,-},R) be an incomplete context. For a∈M, the lower and upper derivation operators R_∗,R¯∗:M→2G are, respectively, defined as follows:(8)aR_∗=x∈G∣Rx,a=+,aR¯∗=x∈G∣Rx,a=+orRx,a=?.Moreover, forX∈2G, the lower and upper derivation operators R_∗,R¯∗:2G→2M are, respectively, defined as(9)XR_∗=a∈M∣aR_∗⊇X,XR¯∗=a∈M∣aR¯∗⊇X.Definition 12.
LetK=(G,M,{+,?,-},R) be an incomplete context. For a∈M, the negative lower and upper derivation operators R_∗-,R¯∗-:M→2G are, respectively, defined as follows:(10)aR_∗-=x∈G∣Rx,a=-,aR¯∗-=x∈G∣Rx,a=-orRx,a=?.Moreover, forX∈2G, the negative lower and upper derivation operators R_∗-,R¯∗-:2G→2M are respectively defined as follows:(11)XR_∗-=a∈M∣aR_∗-⊇X,XR¯∗-=a∈M∣aR¯∗-⊇X.Definition 13.
LetK=(G,M,{+,?,-},R) be an incomplete formal context. For X∈2G and (A,B,C,D)∈2M×2M×2M×2M, two operators α:2G→2M×2M×2M×2M and β:2M×2M×2M×2M→2G are, respectively, defined as(12)Xα=XR_∗,XR¯∗,XR_∗-,XR¯∗-,A,B,C,Dβ=x∈G∣xR_∗⊇A∧xR¯∗⊇B∧xR_∗-⊇C∧(xR¯∗-⊇D.Semantically,XR_∗ contains the attributes that are certain to be possessed by X, XR¯∗ contains the attributes that are possible to be possessed by X, XR_∗- contains the attributes that are certain to be not possessed by X, and XR¯∗- contains the attributes that are possible to be not possessed by X. (A,B,C,D)β is the maximal set of the objects that have all the attributes in A with certainty, have all the attributes in B-A with possibility, do not have all the attributes in C with certainty, and do not have all the attributes in D-C with possibility.Besides, the four setsA, B, C, and D are actually from two interval sets [A,B] and [C,D]. As this is obvious and for the sake of a simpler representation, we do not use interval sets in this definition.Definition 14.
LetK=(G,M,{+,?,-},R) be an incomplete formal context, X∈2G and (A,B,C,D)∈2M×2M×2M×2M. The pair (X,(A,B,C,D)) is called an approximate object-induced three-way concept, if Xα=(A,B,C,D) and (A,B,C,D)β=X.Then, all the approximate object-induced three-way concepts contained inK, ordered by (13)X1,A1,B1,C1,D1≤X2,A2,B2,C2,D2⇔X1⊆X2⇔A1⊇A2andB1⊇B2andC1⊇C2andD1⊇D2,form a complete lattice, which is called the approximate object-induced three-way concept lattice (AOEL for short) of K and denoted by AOEL(K).Intuitively, approximate object-induced three-way concept(X,(A,B,C,D)) is the combination of SE-ISI formal concepts (X,[A,B]) and (X,[C,D]) defined in the incomplete formal context and its complement context in [20]. However, neither the SE-ISI concepts derived from the incomplete formal context nor the ones derived from its complement context can generate all the approximate object-induced three-way concepts. Besides, approximate object-induced three-way concepts are not simple combinations of these two types of SE-ISI concepts. That is, there does not exist a one to one correspondence between SE-ISI concepts from incomplete formal context and its complement. In other words, there is a SE-ISI concept (X,[A,B]) of an incomplete formal context and there may not always exist a SE-ISI concept (X,[C,D]) from its complement context, and vice versa. As a result, the set of the extents of SE-ISI concepts of an incomplete formal context and its complement is just a subset of the extents of approximate object-induced three-way concepts of the same incomplete formal context. Therefore, approximate object-induced three-way concepts provide more information than that of SE-ISI concepts.Definition 15.
LetU be a nonempty finite set and 2U×2U×2U×2U be the Cartesian product built on 2U. Then, (2U×2U×2U×2U,≤) is a poset where the partial order relation ≤ in 2U×2U×2U×2U is defined as (14)A1,B1,C1,D1≤A2,B2,C2,D2⇔A1⊆A2,B1⊆B2,C1⊆C2,D1⊆D2.Moreover, ifA1=A2, B1=B2, C1=C2, and D1=D2, then (A1,B1,C1,D1) is said to be equal to (A2,B2,C2,D2) and is denoted by (A1,B1,C1,D1)=(A2,B2,C2,D2).Besides, the intersection ‘∩’ and union ‘∪’ in 2U×2U×2U×2U are defined, respectively, as (15)A1,B1,C1,D1∩A2,B2,C2,D2=A1∩A2,B1∩B2,C1∩C2,D1∩D2,A1,B1,C1,D1∪A2,B2,C2,D2=A1∪A2,B1∪B2,C1∪C2,D1∪D2.Proposition 16.
LetK=(G,M,{+,?,-},R) be an incomplete context. For X, X1, X2∈2G and (A,B,C,D), (A1,B1,C1,D1), (A2,B2,C2,D2)∈2M×2M×2M×2M, the following properties hold.(i)X1⊆X2⇒X1α≥X2α, (A1,B1,C1,D1)≤(A2,B2,C2,D2)⇒(A1,B1,C1,D1)β⊇(A2,B2,C2,D2)β(ii)X⊆Xαβ, (A,B,C,D)≤(A,B,C,D)βα(iii)Xα=Xαβα, (A,B,C,D)β=(A,B,C,D)βαβ(iv)(X1∪X2)α=X1α∩X2α, ((A1,B1,C1,D1)∪(A2,B2,C2,D2))β=(A1,B1,C1,D1)β∩(A2,B2,C2,D2)βProof.
As the operatorsα and β incorporate the ideas of the three-way derivation operations, this proposition can be proved analogously as that of three-way derivation operations. Interested readers can refer to papers [8, 9].Theorem 17.
LetK=(G,M,{+,?,-},R) be an incomplete context. In AOEL(K), the infimum and supremum are, respectively, given by (16)X1,A1,B1,C1,D1∧X2,A2,B2,C2,D2=X1∩X2,A1,B1,C1,D1∪A2,B2,C2,D2βα,X1,A1,B1,C1,D1∨X2,A2,B2,C2,D2=X1∪X2αβ,A1,B1,C1,D1∩A2,B2,C2,D2.Proof.
The theorem is immediate from Proposition16.


### 3.2. The Connections between AOEL and OEL

In the following, we useAOELE(K) to represent the set of extents of an approximate object-induced three-way concept lattice AOEL(K) and use OELE(K) to represent the set of extents of an object-induced three-way concept lattice OEL(K).Theorem 18.
LetK=(G,M,{+,?,-},R) be an incomplete context. Then OELE(K∗)∪OELE(K∗)=AOELE(K).Proof.
On one hand, let(X,(A,B,C,D)) be an approximate object-induced three-way concept of AOEL(K). Assume that there does not exist an object-induced three-way concept (X,(A,D)) of OEL(K∗) and an object-induced three-way concept (X,(B,C)) of OEL(K∗); then there must be an object-induced three-way concept (Y,(A,D)) of OEL(K∗) with Y⊂X or an object-induced three-way concept (Z,(B,C)) of OEL(K∗) with Z⊂X. If (Y,(A,D))∈OEL(K∗) is true; then there must be an approximate object-induced three-way concept (Y,(A,B,C,D)) of AOEL(K), and this contradicts with the fact that (X,(A,B,C,D))∈AOEL(K). If (Z,(B,C))∈OEL(K∗) is true, then there must be an approximate object-induced three-way concept (Z,(A,B,C,D)) of AOEL(K), and this also contradicts with the fact that (X,(A,B,C,D))∈AOEL(K).
On the other hand, ifX,B,C∈OELK∗ and X,A,D∈OELK∗, then there must be an approximate object-induced three-way concept X,A,B,C,D of AOELK. If X,B,C∈OELK∗ and ∃X,A,D∈OELK∗, then there must be an approximate object-induced three-way concept X,E,B,C,F of AOELK, where Y,E,F is the smallest object-induced three-way concept in OELK∗ with Y⊃X. If X,A,D∈OELK∗ and ∃X,B,C∈OELK∗, then X,A,E,F,D is an approximate object-induced three-way concept X,E,B,C,F of AOELK, where (Z,(E,F)) is the smallest object-induced three-way concept in OEL(K∗) with Z⊃X.
To sum up, this theorem is at hand.Based on Theorem18, we give Algorithm 1 to build the approximate object-induced three-way concept lattice of a given incomplete formal context.Algorithm 1:Constructing approximate object-induced three-way concept lattice of an incomplete formal context.
Require: An incomplete context K=(G,M,{+,?,-},R). Ensure: Approximate object-induced three-way concept lattice AOEL(K). (1) Initialize AOEL(K)=∅; (2) Construct object-induced three-way concept lattices OEL(K∗) and OEL(K∗); (3) If (X,(B,C))∈OEL(K∗) and (X,(A,D))∈OEL(K∗), then add (X,(A,B,C,D)) into AOEL(K); (4) If (X,(B,C))∈OEL(K∗) and ∃(X,(A,D))∈OEL(K∗), then find the smallest object-induced three-way concept ( Y , ( E , F ) ) in OEL(K∗) with Y⊇X and add (X,(E,B,C,F)) into AOEL(K); (5) If (X,(A,D))∈OEL(K∗) and ∃(X,(B,C))∈OEL(K∗), then find the smallest object-induced three-way concept ( Y , ( E , F ) ) in OEL(K∗) with Y⊇X and add (X,(A,E,F,D)) into AOEL(K); (6) Establish ≤ relations between all the approximate object-induced three-way concepts in AOEL(K); (7) Output AOEL(K).In Algorithm1, for a given incomplete context K, we use two object-induced three-way concept lattices OEL(K∗) and OEL(K∗) to build an approximate object-induced three-way concept lattice. Moreover, an object-induced three-way concept lattice can be built based on two classical concept lattices [9]. So, the complexity of Algorithm 1 is determined by the construction of a classical concept lattice. Incidentally, the best time complexity of constructing a concept lattice is O(G2∣M∣N) (N is the number of concepts of the constructed concept lattice) [31].Example 19.
Continuing Example10, in this example, in the representation of a concept, we omit the braces and comma for convenience.Figure1 shows the object-induced three-way concept lattice OEL(K∗) and Figure 2 shows the object-induced three-way concept lattice OEL(K∗).Figure 1
Object-induced three-way concept latticeOEL(K∗). Figure 1 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).Figure 2
Object-induced three-way concept latticeOEL(K∗). Figure 2 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).By using Algorithm1, we can get the approximate object-induced three-way concept lattice AOEL(K), which is shown by Figure 3. We take several examples to show the main ideas of Algorithm 1.Figure 3
Approximate object-induced three-way concept latticeAOEL(K).(i) As(134,f,c)∈OEL(K∗) and (134,∅,c)∈OEL(K∗), then there must be an object-induced three-way concept (134,∅,f,c,c) in AOEL(K).(ii) As(1234,f,∅)∈OEL(K∗) and (G,∅,∅)∈OEL(K∗) are the smallest three-way concept of OEL(K∗) whose intent contains the intent of the former three-way concept, then there must be an object-induced three-way concept (1234,∅,f,∅,∅) in AOEL(K).(iii) As(35,∅,ef)∈OEL(K∗) and (235,∅,e)∈OEL(K∗) are the smallest three-way concept of OEL(K∗) whose intent contains the intent of the former three-way concept, then there must be an object-induced three-way concept (35,∅,∅,e,ef) in AOEL(K).


## 3.1. Approximate Object-Induced Three-Way Concept Lattice

As there exist uncertainties in the incomplete formal context, the attributes shared by target set may not be fixed. In order to solve this problem, we will use intervals to indicate the variances in building an approximate three-way concept.Definition 11.
LetK=(G,M,{+,?,-},R) be an incomplete context. For a∈M, the lower and upper derivation operators R_∗,R¯∗:M→2G are, respectively, defined as follows:(8)aR_∗=x∈G∣Rx,a=+,aR¯∗=x∈G∣Rx,a=+orRx,a=?.Moreover, forX∈2G, the lower and upper derivation operators R_∗,R¯∗:2G→2M are, respectively, defined as(9)XR_∗=a∈M∣aR_∗⊇X,XR¯∗=a∈M∣aR¯∗⊇X.Definition 12.
LetK=(G,M,{+,?,-},R) be an incomplete context. For a∈M, the negative lower and upper derivation operators R_∗-,R¯∗-:M→2G are, respectively, defined as follows:(10)aR_∗-=x∈G∣Rx,a=-,aR¯∗-=x∈G∣Rx,a=-orRx,a=?.Moreover, forX∈2G, the negative lower and upper derivation operators R_∗-,R¯∗-:2G→2M are respectively defined as follows:(11)XR_∗-=a∈M∣aR_∗-⊇X,XR¯∗-=a∈M∣aR¯∗-⊇X.Definition 13.
LetK=(G,M,{+,?,-},R) be an incomplete formal context. For X∈2G and (A,B,C,D)∈2M×2M×2M×2M, two operators α:2G→2M×2M×2M×2M and β:2M×2M×2M×2M→2G are, respectively, defined as(12)Xα=XR_∗,XR¯∗,XR_∗-,XR¯∗-,A,B,C,Dβ=x∈G∣xR_∗⊇A∧xR¯∗⊇B∧xR_∗-⊇C∧(xR¯∗-⊇D.Semantically,XR_∗ contains the attributes that are certain to be possessed by X, XR¯∗ contains the attributes that are possible to be possessed by X, XR_∗- contains the attributes that are certain to be not possessed by X, and XR¯∗- contains the attributes that are possible to be not possessed by X. (A,B,C,D)β is the maximal set of the objects that have all the attributes in A with certainty, have all the attributes in B-A with possibility, do not have all the attributes in C with certainty, and do not have all the attributes in D-C with possibility.Besides, the four setsA, B, C, and D are actually from two interval sets [A,B] and [C,D]. As this is obvious and for the sake of a simpler representation, we do not use interval sets in this definition.Definition 14.
LetK=(G,M,{+,?,-},R) be an incomplete formal context, X∈2G and (A,B,C,D)∈2M×2M×2M×2M. The pair (X,(A,B,C,D)) is called an approximate object-induced three-way concept, if Xα=(A,B,C,D) and (A,B,C,D)β=X.Then, all the approximate object-induced three-way concepts contained inK, ordered by (13)X1,A1,B1,C1,D1≤X2,A2,B2,C2,D2⇔X1⊆X2⇔A1⊇A2andB1⊇B2andC1⊇C2andD1⊇D2,form a complete lattice, which is called the approximate object-induced three-way concept lattice (AOEL for short) of K and denoted by AOEL(K).Intuitively, approximate object-induced three-way concept(X,(A,B,C,D)) is the combination of SE-ISI formal concepts (X,[A,B]) and (X,[C,D]) defined in the incomplete formal context and its complement context in [20]. However, neither the SE-ISI concepts derived from the incomplete formal context nor the ones derived from its complement context can generate all the approximate object-induced three-way concepts. Besides, approximate object-induced three-way concepts are not simple combinations of these two types of SE-ISI concepts. That is, there does not exist a one to one correspondence between SE-ISI concepts from incomplete formal context and its complement. In other words, there is a SE-ISI concept (X,[A,B]) of an incomplete formal context and there may not always exist a SE-ISI concept (X,[C,D]) from its complement context, and vice versa. As a result, the set of the extents of SE-ISI concepts of an incomplete formal context and its complement is just a subset of the extents of approximate object-induced three-way concepts of the same incomplete formal context. Therefore, approximate object-induced three-way concepts provide more information than that of SE-ISI concepts.Definition 15.
LetU be a nonempty finite set and 2U×2U×2U×2U be the Cartesian product built on 2U. Then, (2U×2U×2U×2U,≤) is a poset where the partial order relation ≤ in 2U×2U×2U×2U is defined as (14)A1,B1,C1,D1≤A2,B2,C2,D2⇔A1⊆A2,B1⊆B2,C1⊆C2,D1⊆D2.Moreover, ifA1=A2, B1=B2, C1=C2, and D1=D2, then (A1,B1,C1,D1) is said to be equal to (A2,B2,C2,D2) and is denoted by (A1,B1,C1,D1)=(A2,B2,C2,D2).Besides, the intersection ‘∩’ and union ‘∪’ in 2U×2U×2U×2U are defined, respectively, as (15)A1,B1,C1,D1∩A2,B2,C2,D2=A1∩A2,B1∩B2,C1∩C2,D1∩D2,A1,B1,C1,D1∪A2,B2,C2,D2=A1∪A2,B1∪B2,C1∪C2,D1∪D2.Proposition 16.
LetK=(G,M,{+,?,-},R) be an incomplete context. For X, X1, X2∈2G and (A,B,C,D), (A1,B1,C1,D1), (A2,B2,C2,D2)∈2M×2M×2M×2M, the following properties hold.(i)X1⊆X2⇒X1α≥X2α, (A1,B1,C1,D1)≤(A2,B2,C2,D2)⇒(A1,B1,C1,D1)β⊇(A2,B2,C2,D2)β(ii)X⊆Xαβ, (A,B,C,D)≤(A,B,C,D)βα(iii)Xα=Xαβα, (A,B,C,D)β=(A,B,C,D)βαβ(iv)(X1∪X2)α=X1α∩X2α, ((A1,B1,C1,D1)∪(A2,B2,C2,D2))β=(A1,B1,C1,D1)β∩(A2,B2,C2,D2)βProof.
As the operatorsα and β incorporate the ideas of the three-way derivation operations, this proposition can be proved analogously as that of three-way derivation operations. Interested readers can refer to papers [8, 9].Theorem 17.
LetK=(G,M,{+,?,-},R) be an incomplete context. In AOEL(K), the infimum and supremum are, respectively, given by (16)X1,A1,B1,C1,D1∧X2,A2,B2,C2,D2=X1∩X2,A1,B1,C1,D1∪A2,B2,C2,D2βα,X1,A1,B1,C1,D1∨X2,A2,B2,C2,D2=X1∪X2αβ,A1,B1,C1,D1∩A2,B2,C2,D2.Proof.
The theorem is immediate from Proposition16.


## 3.2. The Connections between AOEL and OEL

In the following, we useAOELE(K) to represent the set of extents of an approximate object-induced three-way concept lattice AOEL(K) and use OELE(K) to represent the set of extents of an object-induced three-way concept lattice OEL(K).Theorem 18.
LetK=(G,M,{+,?,-},R) be an incomplete context. Then OELE(K∗)∪OELE(K∗)=AOELE(K).Proof.
On one hand, let(X,(A,B,C,D)) be an approximate object-induced three-way concept of AOEL(K). Assume that there does not exist an object-induced three-way concept (X,(A,D)) of OEL(K∗) and an object-induced three-way concept (X,(B,C)) of OEL(K∗); then there must be an object-induced three-way concept (Y,(A,D)) of OEL(K∗) with Y⊂X or an object-induced three-way concept (Z,(B,C)) of OEL(K∗) with Z⊂X. If (Y,(A,D))∈OEL(K∗) is true; then there must be an approximate object-induced three-way concept (Y,(A,B,C,D)) of AOEL(K), and this contradicts with the fact that (X,(A,B,C,D))∈AOEL(K). If (Z,(B,C))∈OEL(K∗) is true, then there must be an approximate object-induced three-way concept (Z,(A,B,C,D)) of AOEL(K), and this also contradicts with the fact that (X,(A,B,C,D))∈AOEL(K).
On the other hand, ifX,B,C∈OELK∗ and X,A,D∈OELK∗, then there must be an approximate object-induced three-way concept X,A,B,C,D of AOELK. If X,B,C∈OELK∗ and ∃X,A,D∈OELK∗, then there must be an approximate object-induced three-way concept X,E,B,C,F of AOELK, where Y,E,F is the smallest object-induced three-way concept in OELK∗ with Y⊃X. If X,A,D∈OELK∗ and ∃X,B,C∈OELK∗, then X,A,E,F,D is an approximate object-induced three-way concept X,E,B,C,F of AOELK, where (Z,(E,F)) is the smallest object-induced three-way concept in OEL(K∗) with Z⊃X.
To sum up, this theorem is at hand.Based on Theorem18, we give Algorithm 1 to build the approximate object-induced three-way concept lattice of a given incomplete formal context.Algorithm 1:Constructing approximate object-induced three-way concept lattice of an incomplete formal context.
Require: An incomplete context K=(G,M,{+,?,-},R). Ensure: Approximate object-induced three-way concept lattice AOEL(K). (1) Initialize AOEL(K)=∅; (2) Construct object-induced three-way concept lattices OEL(K∗) and OEL(K∗); (3) If (X,(B,C))∈OEL(K∗) and (X,(A,D))∈OEL(K∗), then add (X,(A,B,C,D)) into AOEL(K); (4) If (X,(B,C))∈OEL(K∗) and ∃(X,(A,D))∈OEL(K∗), then find the smallest object-induced three-way concept ( Y , ( E , F ) ) in OEL(K∗) with Y⊇X and add (X,(E,B,C,F)) into AOEL(K); (5) If (X,(A,D))∈OEL(K∗) and ∃(X,(B,C))∈OEL(K∗), then find the smallest object-induced three-way concept ( Y , ( E , F ) ) in OEL(K∗) with Y⊇X and add (X,(A,E,F,D)) into AOEL(K); (6) Establish ≤ relations between all the approximate object-induced three-way concepts in AOEL(K); (7) Output AOEL(K).In Algorithm1, for a given incomplete context K, we use two object-induced three-way concept lattices OEL(K∗) and OEL(K∗) to build an approximate object-induced three-way concept lattice. Moreover, an object-induced three-way concept lattice can be built based on two classical concept lattices [9]. So, the complexity of Algorithm 1 is determined by the construction of a classical concept lattice. Incidentally, the best time complexity of constructing a concept lattice is O(G2∣M∣N) (N is the number of concepts of the constructed concept lattice) [31].Example 19.
Continuing Example10, in this example, in the representation of a concept, we omit the braces and comma for convenience.Figure1 shows the object-induced three-way concept lattice OEL(K∗) and Figure 2 shows the object-induced three-way concept lattice OEL(K∗).Figure 1
Object-induced three-way concept latticeOEL(K∗). Figure 1 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).Figure 2
Object-induced three-way concept latticeOEL(K∗). Figure 2 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).By using Algorithm1, we can get the approximate object-induced three-way concept lattice AOEL(K), which is shown by Figure 3. We take several examples to show the main ideas of Algorithm 1.Figure 3
Approximate object-induced three-way concept latticeAOEL(K).(i) As(134,f,c)∈OEL(K∗) and (134,∅,c)∈OEL(K∗), then there must be an object-induced three-way concept (134,∅,f,c,c) in AOEL(K).(ii) As(1234,f,∅)∈OEL(K∗) and (G,∅,∅)∈OEL(K∗) are the smallest three-way concept of OEL(K∗) whose intent contains the intent of the former three-way concept, then there must be an object-induced three-way concept (1234,∅,f,∅,∅) in AOEL(K).(iii) As(35,∅,ef)∈OEL(K∗) and (235,∅,e)∈OEL(K∗) are the smallest three-way concept of OEL(K∗) whose intent contains the intent of the former three-way concept, then there must be an object-induced three-way concept (35,∅,∅,e,ef) in AOEL(K).


## 4. Approximate Attribute-Induced Three-Way Concept Lattice

In this section, we propose approximate attribute-induced three-way concept lattice. As this can be done similarly as that of object-induced three-way concept lattice, we omit the details in this paper.Definition 20.
LetK=(G,M,{+,?,-},R) be an incomplete context. For x∈G, the lower and upper derivation operators R_∗,R¯∗:G→2M are, respectively, defined as(17)xR_∗=a∈M∣Rx,a=+,xR¯∗=a∈M∣Rx,a=+orRx,a=?.Furthermore, forA∈2M, the lower and upper derivation operators R_∗,R¯∗:2M→2G are, respectively, defined as(18)AR_∗=x∈G∣xR_∗⊇A,AR¯∗=x∈G∣xR¯∗⊇A.Definition 21.
LetK=(G,M,{+,?,-},R) be an incomplete context. For x∈G, the negative lower and upper derivation operators R_∗-,R¯∗-:G→2M are, respectively, defined as(19)xR_∗-=a∈M∣Rx,a=-,xR¯∗-=a∈M∣Rx,a=-orRx,a=?.Furthermore, forA∈2M, the negative lower and upper derivation operators R_∗-,R¯∗-:2M→2G are, respectively, defined as(20)AR_∗-=x∈G∣xR_∗-⊇A,AR¯∗-=x∈G∣xR¯∗-⊇A.Definition 22.
LetK=(G,M,{+,?,-},R) be an incomplete formal context. For A∈2M and (X,Y,Z,W)∈2G×2G×2G×2G, two operators κ:2A→2G×2G×2G×2G and λ:2G×2G×2G×2G→2M are, respectively, defined as(21)Aκ=AR_∗,AR¯∗,AR_∗-,AR¯∗-,X,Y,Z,Wλ=a∈A∣aR_∗⊇X∧aR¯∗⊇Y∧aR_∗-⊇Z∧aR¯∗-⊇W.Definition 23.
LetK=(G,M,{+,?,-},R) be an incomplete formal context, A∈2M, and (X,Y,Z,W)∈2G×2G×2G×2G. The pair ((X,Y,Z,W),A) is called an approximate attribute-induced three-way concept, if Aκ=(X,Y,Z,W) and (X,Y,Z,W)λ=A.Then, all the approximate attribute-induced three-way concepts contained inK, ordered by (22)X1,Y1,Z1,W1,A1≤X2,Y2,Z2,W2,A2⇔A1⊇A2⇔X1⊆X2andY1⊆Y2andZ1⊆Z2andW1⊆W2,form a complete lattice, which is called the approximate attribute-induced three-way concept lattice (AAEL for short) of K and denoted by AAEL(K).Proposition 24.
LetK=(G,M,{+,?,-},R) be an incomplete context. For A, A1, A2∈2M and (X,Y,Z,W), (X1,Y1,Z1,W1), (X2,Y2,Z2,W2)∈2G×2G×2G×2G, the following properties hold.(i)A1⊆A2⇒A1κ≥A2κ, (A1,B1,C1,D1)≤(X2,Y2,Z2,W2)⇒(X1,Y1,Z1,W1)λ⊇(X2,Y2,Z2,W2)λ(ii)A⊆Aκλ, (X,Y,Z,W)≤(X,Y,Z,W)λκ(iii)Aκ=Aκλκ, (X,Y,Z,W)λ=(X,Y,Z,W)λκλ(iv)(A1∪A2)κ=A1κ∩A2κ, ((X1,Y1,Z1,W1)∪(X2,Y2,Z2,W2))λ=(X1,Y1,Z1,W1)λ∩(X2,Y2,Z2,W2)λTheorem 25.
LetK=(G,M,{+,?,-},R) be an incomplete context. In AAEL(K), the infimum and supremum are, respectively, given by (23)X1,Y1,Z1,W1,A1∧X2,Y2,Z2,W2,A2=X1,Y1,Z1,W1∪X2,Y2,Z2,W2λκ,A1∩A2,X1,Y1,Z1,W1,A1∨X2,Y2,Z2,W2,A2=X1,Y1,Z1,W1∩X2,Y2,Z2,W2,A1∪A2κλ.In the following theorem, we useAAELI(K) to represent the set of intents of an approximate attribute-induced three-way concept lattice AAEL(K) and use AELI(K) to represent the set of intents of an attribute-induced three-way concept lattice AEL(K).Theorem 26.
LetK=(G,M,{+,?,-},R) be an incomplete context. Then AELI(K∗)∪AELI(K∗)=AOELI(K).Based on Theorem26, we give Algorithm 2 to build the approximate attribute-induced three-way concept lattice of a given incomplete formal context.Algorithm 2:Constructing approximate attribute-induced three-way concept lattice of an incomplete formal context.
Require: An incomplete context K=(G,M,{+,?,-},R). Ensure: Approximate attribute-induced three-way concept lattice AAEL(K). (1) Initialize AAEL(K)=∅; (2) Construct attribute-induced three-way concept lattices AEL(K∗) and AEL(K∗); (3) If ((Y,Z),A)∈AEL(K∗) and ((X,W),A)∈AEL(K∗), then add ((X,Y,Z,W),A) into AAEL(K); (4) If ((Y,Z),A)∈AEL(K∗) and ∃((X,Z),A)∈AEL(K∗), then find the smallest attribute-induced three-way concept ( ( U , V ) , B ) in AEL(K∗) with B⊇A and add ((U,Y,Z,V),A) into AAEL(K); (5) If ((X,W),A)∈AEL(K∗) and ∃((Y,Z),A)∈AEL(K∗), then find the smallest attribute-induced three-way concept ( ( U , V ) , B ) in AEL(K∗) with B⊇A and add ((X,U,V,W),A) into AAEL(K); (6) Establish ≤ relations between all the approximate attribute-induced three-way concepts in AAEL(K); (7) Output AAEL(K).Example 27.
Table4 depicts an incomplete context K=(G,M,{+,?,-},R) in which G={1,2,3,4,5} and M={a,b,c,d}.Table 4
An example of incomplete formal contextK.
a b c d 1 + + - - 2 - + + - 3 + - - ? 4 - ? - + 5 - + + +The greatest and least completion ofK, i.e., K∗ and K∗, are shown in Tables 5 and 6, respectively.Table 5
The greatest completion ofK.
a b c d 1 + + - - 2 - + + - 3 + - - + 4 - + - + 5 - + + +Table 6
The least completion ofK.
a b c d 1 + + - - 2 - + + - 3 + - - - 4 - - - + 5 - + + +Figure4 shows the attribute-induced three-way concept lattice AEL(K∗) and Figure 5 shows the attribute-induced three-way concept lattice AEL(K∗).Figure 4
Attribute-induced three-way concept latticeAEL(K∗). Figure 4 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).Figure 5
Attribute-induced three-way concept latticeAEL(K∗). Figure 5 is reproduced from Qi et al. (2014) (under the Creative Commons Attribution License/public domain).By using Algorithm2, we can get the approximate attribute-induced three-way concept lattice AAEL(K), which is shown by Figure 6.Figure 6
Approximate attribute-induced three-way concept latticeAAEL(K).


## 5. Conclusions

In this section, we draw some conclusions to show the main contributions of our paper and give an outlook for further study.(i) A Brief Summary of Our Study. In this study, by combining the spirit of partially known formal concepts and 3WCA, we have introduced the framework of approximate three-way concept analysis. Concretely, we have presented approximate object-induced and attribute-induced three-way concept lattices. In addition, we have further explored the relationships between approximate three-way concept lattice and classical three-way concept lattice.(ii) The Differences and Similarities between Our Study and the Existing Ones. Our work is different from the existing partially known formal concept [17] with respect to the ability to manage incompleteness. Djouadi et al. [21] proposed an ill-known formal concept in the form of ((O∗,O∗),(A∗,A∗)), where (O∗,A∗) and (O∗,A∗) were concepts of the least completion K∗ and largest completion K∗. So, given a target object set, it is impossible to directly point out what attributes this target set has. Li et al. [22] defined an approximate concept (X,(A,B)), by using the interval set (A,B) to show the variance caused by the incompleteness of data. However, negative attributes were not considered. Li and Wang [23] presented a type of approximate concept in the form of (X,(M,N)), where M and N are the positive and negative attributes shared by X, respectively. By using this sort of concept, one can not recognize the variance caused by the incomplete information. In our study, approximate three-way concept is proposed in the form of (X,(A,B,C,D)), where (A,B) and (C,D) are two intervals used to show the range of both positive and negative attribute set of X. So, this type of approximated concept is more powerful as it combines the merits of partially known formal concept and 3WCA.(iii) An Outlook for Further Study. In this study, approximate three-way concept lattice is built via two classical three-way concept lattices. How to build approximate three-way concept lattice based on its own properties rather than classical three-way concept lattices is an interesting issue. Furthermore, how to build approximate three-way concept lattice by using dividing and conquer strategy is another issue that deserves to be investigated.In order to manage dynamical changes, Zhi and Li [32] have proposed methods of updating classical concept lattice. However, how to effectively update approximate three-way concept lattice is still an open problem. We will discuss these problems in depth in our forthcoming work.



---

*Source: 9546846-2018-09-12.xml*