Relationships between three-way concepts and classical concepts

Abstract

In this paper, we firstly present some properties of classical concepts (i.e., formal concepts induced by positive operators and negative operators) and three-way concepts, respectively. Based on this, we systematically study the relationships between two types of three-way concepts (i.e., object-induced three-way concepts and attribute-induced three-way concepts) and classical concepts. More specifically, we can obtain all object-induced (attribute-induced) three-way concepts based on four relationships between all classical concepts and object-induced (attribute-induced) three-way concepts, where the four relationships are characterized by four theorems. After that, two algorithms are proposed to build an object-induced concept lattice and an attribute-induced concept lattice, respectively, and examples are given to verify these algorithms.

Keywords

Three-way concept analysis three-way concept formal concept relationship

1 Introduction

Formal concept analysis (FCA) was proposed by Wille in 1982 [1], and the basis of FCA is formal concepts and formal concept lattices. By now, FCA has evolved into an efficient tool for data analysis, and has been applied to various fields successfully [2 –9].

In decision analysis, the classical decision-making model is acceptance and rejection, but in real life, when the information is not sufficient (such as incomplete formal context), the decision made will be a great loss whether accepting or rejecting. For this case, Yao [10] proposed three-way decision-making (3WD) in 2012, which provides a unified discipline-independent framework for decision-making with three options (i.e., acceptance, rejection and non-commitment), this three-decision model is more realistic. Now, three-way decision-making, as an extension of two-way decision-making, has been widely investigated in various areas [11 –21].

Three-way concept analysis (3WCA), proposed by Qi et al. in 2014 [22], is a combination of FCA and 3WD [10 , 23–27]. The basis of 3WCA is three-way concepts and three-way concept lattices, where three-way concept includes object-induced three-way concept (OE-concept) and attribute-induced three-way concept (AE-concept), and three-way concept lattice includes OE-concept lattice and AE-concept lattice. Note that a three-way concept is composed of extension and intension. For an OE-concept, its intension includes two parts, i.e., positive intension and negative intension, which are used to express attributes “jointly possessed” and “jointly not possessed”. Dually, the extension of an AE-concept also includes two parts, i.e., positive extension and negative extension, which are used to express objects “jointly possessed” and “jointly not possessed”. Li et al. [28]. Proposed two kinds of approximate three-way concept lattice models in the incomplete formal context in 2015. Singh [29] proposed to generate the component wise three-way formal fuzzy concept and their hierarchical order visualization in the fuzzy concept lattice. Radhika [30] achieved a more precise recall by three-way concept analysis. Ren et al. [31] studied the structure three forms of partially-known formal concept and their relationships in a framework of three-way analysis with interval sets. Li et al. [32] studied three-way concept learning via multi-granularity from the viewpoint of cognition. Qi et al. [33] studied the connections between three-way concept lattices and classical concept lattices, from the viewpoints of elements, extension (intension) sets, and partial order, respectively, and obtain three-way concepts using the equivalent class.

Obviously, 3WCA is a new field for concept analysis and knowledge processing, and more work needs to be done from theories and applications. Especially, little work is done on the algorithms to build three-way lattice. This paper mainly studies the relationship between the classical concepts and the three-way concepts in the concept point of view. Some properties of classical concepts and three-way concepts will be discussed firstly, and through the positive and negative operators, combine a pair of classical concept into a three-way concept, we get four groups of OE-concepts (AE-concepts), and establish an equation relationship between the set of OE-concepts (AE-concepts) and the set of classical concepts, based on this equation relationship, we present a method to obtain all OE-concepts (AE-concepts) from classical concepts, and the corresponding algorithms will be proposed to build an OE-concept lattice and an AE-concept lattice, and examples will be given to verify these algorithms.

Though we do not divulgate all of utility and the applicability, the example of medical diagnosis shows that the utility and the applicability in the real world of my research, we hope that in the future work, we will pay attention to the utility and the applicability in the real world. Also, we hope that the other researchers can give some the utility and the applicability in the real world if they like use our results. We hope the results can throw away a brick in order to get a gem.

The paper is organized as follows. Section 2 briefly reviews some basic notions of FCA and 3WCA. Section 3 discusses some properties of classical concepts and three-way concepts, respectively. Section 4 studies relationships between two types of three-way concepts (i.e., object-induced three-way concepts and attribute-induced three-way concepts) and classical concepts, respectively, where algorithms are proposed to build an object-induced concept lattice and an attribute-induced concept lattice, and the corresponding examples are given to verify these algorithms. Finally, Section 5 concludes thispaper.

2 Preliminaries

This section briefly introduces some basic notions about FCA and 3WCA.

Some symbols are given in advance. We write P (·) to denote the power set of a set, and DP (·) to denote the product P (·) × P (·).

2.1 Basic notions of formal concept analysis

Definition 2.1.1. [2] A formal context is a triple (U, V, R), which consists of two sets U and V and a relation R between U and V. The elements of U are called the objects and the elements of V are called the attributes of the context. For x ∈ U and a ∈ V, we write (x, a) ∈ R as xRa, and say that the object x has the attribute a, or alternatively, the attribute a is possessed by the object x.

Remark 2.1.1. Let (U, V, R) be a formal context. If ∀x ∈ U, x^* ≠ φ, x^* ≠ V, and ∀a ∈ V, a^* ≠ φ, a^* ≠ U, we say the formal context (U, V, R) is canonical. Formal contexts mentioned in this paper are finite and canonical.

Definition 2.1.2. [2] Let (U, V, R) be a formal context. ∀X ⊆ U and A ⊆ V, a pair of operators * : P (U) → P (V) and * : P (V) → P (U) are defined by $\begin{matrix} X^{*} & = & {a \in V | \forall x \in X (xRa)} \\ A^{*} & = & {x \in U | \forall a \in A (xRa)} . \end{matrix}$

Lemma 2.1.1. [2] Let (U, V, R) be a formal context. ∀X₁, X₂, X ⊆ U, and ∀A₁, A₂, A ⊆ V, then

$X_{1} \subseteq X_{2} \Rightarrow X_{2}^{*} \subseteq X_{1}^{*},$ and $A_{1} \subseteq A_{2} \Rightarrow A_{2}^{*} \subseteq A_{1}^{*} .$

X ⊆ X^**, and A ⊆ A^**.

X^* = X^***, and A^* = A^***.

X ⊆ A^* ⇔ A ⊆ X^*.

$(X_{1} \cup X_{2})^{*} = X_{1}^{*} \cup X_{2}^{*}$ , and $(A_{1} \cup A_{2})^{*} = A_{1}^{*} \cup A_{2}^{*}$ .

$(X_{1} \cap X_{2})^{*} \supseteq X_{1}^{*} \cup X_{2}^{*}$ , and $(A_{1} \cap A_{2})^{*} \supseteq A_{1}^{*} \cup A_{2}^{*}$ .

Definition 2.1.3. [2] If X^* = A and A^* = X, then a pair (X, A) is called a formal concept. X is called the extension and A is called the intension of the concept (X, A). It is easy to know that (X^**, X^*) and (A^*, A^**) are formal concepts.

The family of all the concepts of (U, V, R) forms a complete lattice, which is called the concept lattice and denoted by CL (U, V, R). Analogously, we write the set of the extensions and the set of the intensions of all the concepts as CL_E (U, V, R) and CL_I (U, V, R), respectively.

Definition 2.1.4. [2] ∀ (X₁, A₁), (X₂, A₂) ∈ CL (U, V, R), the partial order is defined by: $(X_{1}, A_{1}) \leq (X_{2}, A_{2}) \Leftrightarrow X_{1} \subseteq X_{2}, A_{1} \supseteq A_{2}$

the infimum and supremum are given by $\begin{matrix} (X_{1}, A_{1}) \land (X_{2}, A_{2}) = (X_{1} \cap X_{2}, (A_{1} \cup A_{2})^{* *}) \\ (X_{1}, A_{1}) \lor (X_{2}, A_{2}) = ((X_{1} \cup X_{2})^{* *}, A_{1} \cap A_{2}) . \end{matrix}$

In Reference [4], the above two operator * are called positive operators, and concepts induced by positive operators are also called positive concepts (for short, P-concept). Correspondingly, a pair of negative operators is also given as follows.

Definition 2.1.5. [22] Let (U, V, R) be a formal context, and its complement context is (U, V, R^C), where R^C = (U × V) - R, For x ∈ U and a ∈ V, we write (x, a) ∈ R^C as xR^Ca, and say that the object x does not have the attribute a, or alternatively, the attribute a is not possessed by the object x.

Example 2.1.1. [22] A formal context (U, V, R) and its complement context (U, V, R^C) are shown in Tables 1 and 2, respectively, where U = {1, 2, 3, 4} and V = {a, b, c, d, e}.

Table 1
The formal context in Example 2.1.1

U a b c d e

1 × × × ×

2 × × ×

3 × × × ×

4 ×

U	a	b	c	d	e
1	×	×	×	×
2	×	×	×
3	×	×	×		×
4				×

Table 2

The complement context in Example 2.1.1

U	a	b	c	d	e
1					×
2				×	×
3				×
4	×	×	×		×

Definition 2.1.6. Let (U, V, R) be a formal context. ∀X ⊆ U, and A ⊆ V, a pair of negative operators, $\bar{*} : P (U) \to P (V)$ and $\bar{*} : P (V) \to P (U)$ , are defined by

$\begin{array}{l} X \bar{^{*}} = {a \in V | \forall x \in X (\neg (x R a))} \\ = {a \in V | \forall x \in X (x R^{C} a)} \\ A^{\bar{*}} = {x \in U | \forall a \in A (\neg (x R a))} \\ = {x \in U | \forall a \in A (x R^{C} a)} . \end{array}$

Similar to positive operators, negative operators have the similar properties.

Lemma 2.1.2. [22] Let (U, V, R) be a formal context. ∀X₁, X₂, X ⊆ U, and ∀A₁, A₂, A ⊆ V, then

$X_{1} \subseteq X_{2} \Rightarrow X_{2}^{\bar{*}} \subseteq X_{1}^{\bar{*}}$ , and $A_{1} \subseteq A_{2} \Rightarrow A_{2}^{\bar{*}} \subseteq A_{1}^{\bar{*}} .$

$X \subseteq X^{\bar{*} \bar{*}}$ , and $A \subseteq A^{\bar{*} \bar{*}}$ .

$X^{\bar{*}} = X^{\bar{*} \bar{*} \bar{*}}$ , and $A^{\bar{*}} = A^{\bar{*} \bar{*} \bar{*}}$ .

$X \subseteq A^{\bar{*}} \Leftrightarrow A \subseteq X^{\bar{*}}$ .

$(X_{1} \cup X_{2})^{\bar{*}} = X_{1}^{\bar{*}} \cup X_{2}^{\bar{*}}$ , and $(A_{1} \cup A_{2})^{\bar{*}} = A_{1}^{\bar{*}} \cup A_{2}^{\bar{*}}$ .

$(X_{1} \cap X_{2})^{\bar{*}} \supseteq X_{1}^{\bar{*}} \cup X_{2}^{\bar{*}}$ , and $(A_{1} \cap A_{2})^{\bar{*}} \supseteq A_{1}^{\bar{*}} \cup A_{2}^{\bar{*}}$ .

Definition 2.1.7. [22] If $X^{\bar{*}} = A$ and $A^{\bar{*}} = X$ , a pair (X, A) is called a N-concept. It is easy to know that $(X^{\bar{*} \bar{*}}, X^{\bar{*}})$ and $(A^{\bar{*}}, A^{\bar{*} \bar{*}})$ are N-concepts.

The family of all N-concepts forms a complete concept lattice denoted by NCL (U, V, R). Similarly, X is called the extension and A is called the intension of the N-concept (X, A). We use NCL_E (U, V, R) and NCL_I (U, V, R) to denote the set of the extensions and the set of the intensions of all the N-concepts, respectively.

Definition 2.1.8. [22] ∀ (X₁, A₁), (X₂, A₂) ∈ NCL (U, V, R), the partial order is defined by: $(X_{1}, A_{1}) \leq (X_{2}, A_{2}) \Leftrightarrow X_{1} \subseteq X_{2}, A_{1} \supseteq A_{2}$

the infimum and supremum are given by $\begin{matrix} (X_{1}, A_{1}) \land (X_{2}, A_{2}) = (X_{1} \cap X_{2}, (A_{1} \cup A_{2})^{\bar{*} \bar{*}}) \\ (X_{1}, A_{1}) \lor (X_{2}, A_{2}) = ((X_{1} \cup X_{2})^{\bar{*} \bar{*}}, A_{1} \cap A_{2}) . \end{matrix}$

Remark 2.1.2. In this paper, we call CL (U, V, R) and NCL (U, V, R) classical concept lattices, where P-concepts and N-concepts are also called classical concepts.

Example 2.1.2. For Example 2.1.1, all P-concepts and N-concepts are shown in Figs. 1 and 2, respectively.

Fig.1

CL (U, V, R) in Example 2.1.1.

Fig.2

NCL (U, V, R) in Example 2.1.1.

2.2 Basic notions of three-way concept analysis

Combing the operators * and $\bar{*}$ , a pair of three-way operators 〈· and ·〉 proposed by Qi et al. [22] are given in the following.

Definition 2.2.1. [22] Let (U, V, R) be a formal context. ∀X ⊆ U, and A, B ⊆ V, a pair of object-induced three-way operators, 〈 · : P (U) → DP (V) and ·〉 : DP (V) → P (U), are defined by:

$\begin{matrix} (A, B)^{\cdot 〉} & = & {x \in U | x \in A^{*} and x \in B^{\bar{*}}} \\ = & A^{*} \cap B^{\bar{*}} . \end{matrix}$

We abbreviate them as OE-operators.

The pair of OE-operators has the following properties.

Lemma 2.2.1. [22] Let (U, V, R) be a formal context, ∀X₁, X₂, X ⊆ U, and ∀A₁, A₂, A, B, B₁, B₂ ⊆ V, then

$X_{1} \subseteq X_{2} \Rightarrow X_{2}^{〈 \cdot} \subseteq X_{1}^{〈 \cdot} (A_{1}, B_{1}) \subseteq (A_{2}, B_{2}) \Rightarrow (A_{2}, B_{2})^{\cdot 〉} \subseteq (A_{1}, B_{1})^{\cdot 〉}$ .

X ⊆ X^〈··〉, and (A, B) ⊆ (A, B) ^·〉〈·.

X^〈· = X^{〈··〉〈·}, and (A, B) ^·〉 = (A, B) ^{·〉〈··〉}.

X ⊆ (A, B) ^·〉 ⇔ (A, B) ⊆ X^〈·.

((A₁, B₁) ∪ (A₂, B₂)) ^·〉 = (A₁, B₁) ^·〉 ∩ (A₂, B₂) ^·〉, $(X_{1} \cup X_{2})^{〈 \cdot} = X_{1}^{〈 \cdot} \cap X_{2}^{〈 \cdot}$ .

((A₁, B₁) ∩ (A₂, B₂)) ^·〉 ⊇ ((A₁, B₁) ^·〉 ∪ (A₂, B₂) ^·〉), $(X_{1} \cap X_{2})^{〈 \cdot} \supseteq X_{1}^{〈 \cdot} \cap X_{2}^{〈 \cdot}$ .

Definition 2.2.2. [22] If X^〈· = (A, B) and (A, B) ^·〉 = X, then we call (X, (A, B)) an object-induced three-way concept (for short, OE-concept), where A, B are called positive intension and negative intension. It is easy to know that (X^〈··〉, X^〈·) and ((A, B) ^·〉, (A, B) ^·〉〈·) are OE-concepts. In particular, for all x ∈ U, (x^〈··〉, x^〈·) is an OE-concept.

The OE-concept (X₁, (A₁, B₁)), (X₂, (A₂, B₂)), are ordered by $\begin{matrix} (X_{1}, (A_{1}, B_{1})) \leq (X_{2}, (A_{2}, B_{2})) \Leftrightarrow X_{1} \subseteq X_{2}, \\ and (A_{1}, B_{1}) \supseteq (A_{2}, B_{2}) . \end{matrix}$

The infimum and supremum are given by $\begin{matrix} (X_{1}, (A_{1}, B_{1})) \land (X_{2}, (A_{2}, B_{2})) \\ = (X_{1} \cap X_{2}, ((A_{1}, B_{1}) \cup (A_{2}, B_{2}))^{\cdot 〉〈 \cdot}), \\ (X_{1}, (A_{1}, B_{1})) \lor (X_{2}, (A_{2}, B_{2})) \\ = ((X_{1} \cap X_{2})^{〈 \cdot \cdot 〉}, (A_{1}, B_{1}) \cap (A_{2}, B_{2})) . \end{matrix}$

All OE-concepts constitute a complete lattice denoted by OEL (U, V, R). The set of all extensions and all positive intensions and all negative intensions of OEL (U, V, R) are denoted by OEL_E (U, V, R), ${OEL}_{I}^{+} (U, V, R)$ , ${OEL}_{I}^{-} (U, V, R)$ , respectively.

Analogously, here are the definitions of attribute-induced three-way concept as follows.

Definition 2.2.3. [22] Let (U, V, R) be a formal context. ∀A ⊆ V, and X, Y ⊆ U, a pair of attribute-induced three-way operators, ^〈· : P (V) → DP (U) and ^·〉 : DP (U) → P (V), are defined by: $\begin{matrix} (X, Y)^{\cdot 〉} = {a \in V | a \in X^{*} anda \in Y^{\bar{*}}} \\ = X^{*} \cap Y^{\bar{*}} . \end{matrix}$

We abbreviate them as AE-operators.

Lemma 2.2.2. [22] For ∀A, A₁, A₂ ⊆ V, and ∀X, X₁, X₂, Y, Y₁, Y₂ ⊆ U, the following properties hold.

(X₁, Y₁) ⊆ (X₂, Y₂) ⇒ (X₂, Y₂) ^·〉 ⊆ (X₁, Y₁) ^·〉, $A_{1} \subseteq A_{2} \Rightarrow A_{2}^{〈 \cdot} \subseteq A_{1}^{〈 \cdot}$ .

(X, Y) ⊆ (X, Y) ^·〉〈·, and A ⊆ A^〈··〉.

(X, Y) ^·〉 = (X, Y) ^{·〉〈··〉}, and A^〈· = A^{〈··〉〈·}.

(X, Y) ⊆ A^〈· ⇔ A ⊆ (X, Y) ^·〉.

((X₁, Y₁) ∪ (X₂, Y₂)) ^·〉 = (X₁, Y₁) ^·〉 ∩ (X₂, Y₂) ^·〉, $(A_{1} \cup A_{2})^{〈 \cdot} = A_{1}^{〈 \cdot} \cap A_{2}^{〈 \cdot}$ .

((X₁, Y₁) ∩ (X₂, Y₂)) ^·〉 ⊇ (X₁, Y₁) ^·〉 ∪ (X₂, Y₂) ^·〉 $(A_{1} \cap A_{2})^{〈 \cdot} \supseteq A_{1}^{〈 \cdot} \cap A_{2}^{〈 \cdot}$ .

Definition 2.2.4. [22] If (X, Y) ^·〉 = A and A^〈· = (X, Y), then we call ((X, Y), A) an attribute-induced three-way concept (for short, AE-concept), where X, Y are called positive extension and negative extension. It is easy to know that (A^〈·, A^〈··〉) and ((X, Y) ^·〉〈·, (X, Y) ^·〉) are AE-concepts. In particular, for all a ∈ V, (a^〈··〉, a^〈·) is an AE-concept.

The AE-concepts (X₁, Y₁), A₁), (X₂, Y₂), A₂) are ordered by $((X_{1}, Y_{1}), A_{1}) \leq ((X_{2}, Y_{2}), A_{2}) \Leftrightarrow A_{1} \supseteq A_{2},$

and (X₁, Y₁) ⊆ (X₂, Y₂).

The infimum and supremum are given by $\begin{matrix} ((X_{1}, Y_{1}), A_{1}) \land ((X_{2}, Y_{2}), A_{2}) \\ = ((X_{1}, Y_{1}) \cap (X_{2}, Y_{2}), (A_{1} \cup A_{2})^{〈 \cdot \cdot 〉}), \\ ((X_{1}, Y_{1}), A_{1}) \lor ((X_{2}, Y_{2}), A_{2}) \\ = ((X_{1}, Y_{1}) \cup (X_{2}, Y_{2})^{\cdot 〉〈 \cdot}, A_{1} \cap A_{2}) . \end{matrix}$

All AE-concepts constitute a complete lattice denoted by AEL (U, V, R). The set of all intensions, all positive extensions and all negative extensions of AEL (U, V, R) are denoted by AEL_I (U, V, R), ${AEL}_{E}^{+} (U, V, R)$ , ${AEL}_{E}^{-} (U, V, R)$ , respectively.

Example 2.2.1. For Example 2.1.1, all OE-concepts and AE-concepts are shown in Figs. 3 and 4, respectively.

Fig.3

OEL (U, V, R) in Example 2.1.1.

Fig.4

AEL (U, V, R) in Example 2.1.1.

3 Further discussions on classical concepts and three-way concepts

In order to obtain the relationship between the three-way concepts and the classical concepts, we need to discuss some relevant properties of the classical concept and three-way concept.

Firstly, we will discuss some properties of the classical concepts in section 3.1.

3.1 Some properties of classical concepts

Considering the Definition and Lemma of classical concepts, we can obtain the following conclusions. The proof process is omitted.

Lemma 3.1.1. Let (U, V, R) be a formal context.

If (X, X^*) is not a P-concept, there must exist X₀ ⊆ U such that $X_{0}^{*} = X^{*}$ , and (X₀, X^*) is a P-concept.

If X^* = A, and A^* = Y ⊇ X, then (Y, A) is a P-concept.

Analogously, in the same way, we can obtain the following conclusions.

Lemma 3.1.2. Let (U, V, R) be a formal context.

If $(Y, Y^{\bar{*}})$ is not a N-concept, there must exist Y₀ ⊆ U, such that $Y_{0}^{\bar{*}} = Y^{\bar{*}}$ , and $(Y_{0}, Y^{\bar{*}})$ is a N-concept.

If $Y^{\bar{*}} = B$ , and $B^{\bar{*}} = Z \supseteq Y$ , then (Z, B) is a N-concept.

According to the infimum and supremum of the classical concepts, Wille [2] have the following theorem.

Lemma 3.1.3. [2] Let (U, V, R) be a formal context. If X ∈ CL_E (U, V, R), X₀ ∈ CL_E (U, V, R), and X∩ X₀ ≠ ∅, then (X ∩ X₀) ∈ CL_E (U, V, R).

In the same way, we have the following conclusion.

Lemma 3.1.4. Let (U, V, R) be a formal context. If Y ∈ NCL_E (U, V, R), Y₀ ∈ NCL_E (U, V, R), and Y∩ Y₀ ≠ ∅, then (Y ∩ Y₀) ∈ NCL_E (U, V, R).

Proof. Since Y ∈ NCL_E (U, V, R), Y₀ ∈ NCL_E (U, V, R), and Y∩ Y₀ ≠ ∅. By Definition 2.1.7, we know that $(Y, Y^{\bar{*}})$ and $(Y_{0}, Y_{0}^{\bar{*}})$ are N-concepts. According to Definition 2.1.7, we also know that $((Y^{\bar{*}} \cup Y_{0}^{\bar{*}})^{\bar{*}}, (Y^{\bar{*}} \cup Y_{0}^{\bar{*}})^{\bar{*} \bar{*}})$ is a N-concept. And $(Y^{\bar{*}} \cup Y_{0}^{\bar{*}})^{\bar{*}} = Y^{\bar{*} \bar{*}} \cap Y_{0}^{\bar{*} \bar{*}} = Y \cap Y_{0}$ , thus, $(Y \cap Y_{0}, (Y^{\bar{*}} \cup Y_{0}^{\bar{*}})^{\bar{*} \bar{*}})$ is a N-concept, i.e., (Y ∩ Y₀) ∈ NCL_E (U, V, R).

3.2 Some properties of three-way concepts

Due to three-way concepts contain OE-concepts and AE-concepts, we will discuss some relevant properties of the OE-concept and AE-concept in order for reader to better understand.

Lemma 3.2.1. Let (U, V, R) be a formal context.

If (X, X^〈·) is not an OE-concept, there must exist X₀ ⊆ U, such that $X_{0}^{〈 \cdot} = X^{〈 \cdot}$ , and (X₀, X^〈·) is an OE-concept.

If X^〈· = (A, B), and (A, B) ^·〉 = Y ⊇ X, then (Y, (A, B)) is an OE-concept.

Proof. Considering the Definition 2.2.2 and Lemma 2.2.1, we can obtain the above conclusion.

Lemma 3.2.2. Let (U, V, R) be a formal context. If X ∈ OEL_E (U, V, R), X₀ ∈ OEL_E (U, V, R), and X∩ X₀ ≠ ∅, then X ∩ X₀ ∈ OEL_E (U, V, R).

Proof. From the Definition 2.2.2 and Lemma 2.2.1 can obtain the above conclusion.

Similar to OE-concepts, we also obtain the following lemma of AE-concepts.

Lemma 3.2.3. Let (U, V, R) be a formal context.

If (A^〈·, A) is not an AE-concept, there must exist A₀ ⊆ V, such that $A_{0}^{〈 \cdot} = A^{〈 \cdot}$ and (A^〈·, A₀) is an AE-concept.

If A^〈· = (X, Y), and (X, Y) ^·〉 = B ⊇ A, then ((X, Y), B) is an AE-concept.

Proof. From the Definition 2.2.4 and Lemma 2.2.2 can obtain the above conclusion.

Lemma 3.2.4. Let (U, V, R) be a formal context. If A ∈ AEL_I (U, V, R), B ∈ AEL_I (U, V, R), and A∩ B ≠ ∅, then (A ∩ B) ∈ AEL_I (U, V, R).

Proof. From the Definition 2.2.2 and Lemma 2.2.1 can obtain the above conclusion.

4 Relationships between three-way concepts and classical concepts

In this section, we discuss the relationship between OE-concepts and classical concepts, the relationship between AE-concepts and classical concepts.

4.1 Relationships between OE-concepts and classical concepts

Qi et al. [33] has discussed the connections between OE-concepts and classical concepts, and obtained $\begin{matrix} {CL}_{E} (U, V, R) \subseteq {OEL}_{E} (U, V, R), \\ {NCL}_{E} (U, V, R) \subseteq {OEL}_{E} (U, V, R), \\ {CL}_{E} (U, V, R) \cup {NCL}_{E} (U, V, R) \subseteq {OEL}_{E} (U, V, R) . \end{matrix}$

In this section, In order to get the equation relationship between the three concepts and the classical concepts, we first give the necessary lemma, based on this, we get four groups of OE-concepts, which can form a complete lattice.

As for set X, we write α (X) to denote the minimal set, which contains X. i.e., X ⊆ α (X), and there is not exist X₀ such that X ⊆ X₀ ⊆ α (X).

Lemma 4.1.1. Let (U, V, R) be a formal context. If (X, A) is a P-concept and (X, B) is a N-concept, then (X (A, B)) is an OE-concept.

Proof. Since (X, A) is a P-concept, we have X^* = A and A^* = X. According to (X, B) is a N-concept, we also have $X^{\bar{*}} = B$ and $B^{\bar{*}} = X$ . Thus, we can obtain X^* = A, $X^{\bar{*}} = B$ and $A^{*} \cap B^{\bar{*}} = X$ . It is not difficult to find that $X^{〈 \cdot} = (X^{*}, X^{\bar{*}}) = (A, B)$ , and $(A, B)^{\cdot 〉} = A^{*} \cap B^{\bar{*}} = X$ . Therefore, according to Definition 2.2.2, we know that (X, (A, B)) is an OE-concept.

Example 4.1.1. From Figs. 1 and 2, it is easy to observe that (U, ∅) is a P-concept and (U, ∅) is a N-concept, then (U, (∅, ∅)) is an OE-concept.

For brevity, the set of all concepts induced by Lemma 4.1.1 is denoted by $\begin{matrix} H_{1} = {(X, (A, B)) | (X, A) \in CL (U, V, R) \\ and (X, B) \in NCL (U, V, R)} . \end{matrix}$

Lemma 4.1.2. Let (U, V, R) be a formal context. If (X, A) is a P-concept, and (Y, B) is a N-concept, where X ∉ NCL_E (U, V, R), and Y = α (X) in NCL_E (U, V, R), then(X, (A, B)) is an OE-concept.

Proof. Since (X, A) is a P-concept, and (Y, B) is a N-concept, we have X^* = A, A^* = X, $Y^{\bar{*}} = B$ and $B^{\bar{*}} = Y$ . Obviously, by Definition 2.2.1, we know that $(A, B)^{\cdot 〉} = A^{*} \cap B^{\bar{*}} = X \cap Y = X$ . From Definition 2.2.2, the rest is to prove $X^{〈 \cdot} = (X^{*}, X^{\bar{*}}) = (A, B)$ , then (X, (A, B)) is an OE-concept.

In fact, on the one hand, from Lemma 2.1.2, we have $X \subseteq X^{\bar{*} \bar{*}}$ . Due to the fact Y is minimal among all extensions of NCL (U, V, R) which contains X, then we get $Y \subseteq X^{\bar{*} \bar{*}}$ . Further, by Lemma 2.1.2, we get $X^{\bar{*}} = X^{\bar{*} \bar{*} \bar{*}} \subseteq Y^{\bar{*}} = B$ . On the other hand, since X ⊂ Y, we have $B = Y^{\bar{*}} \subseteq X^{\bar{*}}$ . Therefore we obtain that $X^{\bar{*}} = B$ . Noting that X^* = A, we have $X^{〈 \cdot} = (X^{*}, X^{\bar{*}}) = (A, B)$ .

Example 4.1.2. From Figs. 1 and 2, it is easy to observe that (14,d) is a P-concept, and (124,e) is a N-concept. Obviously, {14} ∉ NCL_E (U, V, R), {14} ⊂ {124}, and {124} is minimal among all extensions of NCL (U, V, R), which contains {14}(there does not exist Y₁ ∈ NCL_E (U, V, R), such that {14} ⊂ Y₁ ⊂ {124}), i.e., {124} = α ({14}), thus (14,(d,e)) is an OE-concept.

For brevity, the set of all concepts induced by Lemma 4.1.2 is denoted by $\begin{matrix} H_{2} = {(X, (A, B)) | (X, A) \in CL (U, V, R), (Y, B) \\ \in NCL (U, V, R) \\ where \\ X \notin {NCL}_{E} (U, V, R), Y = α (X) {inNCL}_{E} (U, V, R)} . \end{matrix}$

Lemma 4.1.3. Let (U, V, R) be a formal context. If (Y, B) is a N-concept and Y ∉ CL_E (U, V, R), (X, A) is a P-concept, and X = α (Y) in CL_E (U, V, R), then (Y, (A, B)) is an OE-concept.

Proof. Since (X, A) is a P-concept, and (Y, B) is a N-concept, we have X^* = A, A^* = X, $Y^{\bar{*}} = B$ and $B^{\bar{*}} = Y$ . Obviously, by Definition 2.2.1, we know that $(A, B)^{\cdot 〉} = A^{*} \cap B^{\bar{*}} = X \cap Y = Y$ . From Definition 2.2.2, the rest is to prove $Y^{〈 \cdot} = (Y^{*}, Y^{\bar{*}}) = (A, B)$ , then (Y, (A, B)) is an OE-concept.

In fact, on the one hand, from Lemma 2.1.2, we have Y ⊆ Y^**. Due to the fact X is minimal among all extensions of CL (U, V, R), which contains Y, then we get X ⊆ Y^**. Furthermore, by Lemma 2.1.2, we get Y^* = Y^*** ⊆ X^* = A. On the other hand, since Y ⊂ X, we have A = X^* ⊆ Y^*. Therefore we obtain that $Y^{\bar{*}} = B$ . Noting that X^* = A, from Definition 2.2.2, we have $Y^{〈 \cdot} = (Y^{*}, Y^{\bar{*}}) = (A, B)$ .

Example 4.1.3. From Figs. 1 and 2, it is easy to observe that (23,d) is a N-concept, and (123,abc) is a P-concept, where {23} ∉ CL_E (U, V, R), {23} ⊂ {123}, and {123} is minimal among all extensions of CL (U, V, R), which contains {23} (there does not exist Y₁ ∈ CL_E (U, V, R), such that {23} ⊂ Y₁ ⊂ {123}), i.e., {123} = α ({23}), then (23, (abc, d)) is an OE-concept.

For brevity, the set of all concepts induced by Lemma 4.1.3 is denoted by $\begin{matrix} H_{3} = {(Y, (A, B)) | (Y, B) \in NCL (U, V, R), (X, A) \\ \in CL (U, V, R) \\ where \\ Y \notin {CL}_{E} (U, V, R), X = α (Y) {inCL}_{E} (U, V, R)} . \end{matrix}$

Lemma 4.1.4. Let (U, V, R) be a formal context. If (X, A) is a P-concept and (Y, B) is a N-concept, X ∩ Y ∉ CL_E (U, V, R) ∪ NCL_E (U, V, R), and X = α (X ∩ Y) in CL_E (U, V, R), Y = α (X ∩ Y) in NCL_E (U, V, R), then (X ∩ Y, (A, B)) is an OE-concept.

Proof. Since (X, A) is a P-concept and (Y, B) is a N-concept, we have X^* = A, A^* = X, $Y^{\bar{*}} = B$ and $B^{\bar{*}} = Y$ . In order to show that (X ∩ Y, (A, B)) is an OE-concept, the rest only need to prove (X ∩ Y) ^* = A, and $(X \cap Y)^{\bar{*}} = B$ .

Firstly, we try to prove (X ∩ Y) ^* = A. Since X ∩ Y ∉ CL_E (U, V, R), then (X ∩ Y, (X ∩ Y) ^*) is not a P-concept. According to Lemma 3.1.1(1), we know there must exist X₀ ⊆ U, such that $X_{0}^{*} = (X \cap Y)^{*}$ , and (X₀, (X ∩ Y) ^*) is a P-concept. Besides, by Lemma 2.1.1, we have (X ∩ Y) ⊆ (X ∩ Y) ^** = X₀. Assume X₀ ≠ X. Noting that (X, A) is a concept, by Lemma 2.1.1, we have X₀ = (X ∩ Y) ^** ⊆ X^** = X. Thus we get (X ∩ Y) ⊆ X₀ = A, which contradicts with the known conditions. So X₀ = X, and $(X \cap Y)^{*} = X_{0}^{*} = A$ .

Next, we need to prove $(X \cap Y)^{\bar{*}} = B$ . Since X ∩ Y ∉ NCL_E (U, V, R), then $(X \cap Y, (X \cap Y)^{\bar{*}})$ is not a N-concept. From Lemma 3.1.2(1), we know there must exist Y₀ ⊆ U, such that $Y_{0}^{\bar{*}} = (X \cap Y)^{\bar{*}}$ , and $(Y_{0}, (X \cap Y)^{\bar{*}})$ is an N-concept. Besides, by Lemma 2.1.2, we have $(X \cap Y) \subseteq (X \cap Y)^{\bar{*} \bar{*}} = Y_{0}$ . Assume Y₀ ≠ Y. Noting that (Y, B) is a N-concept, by Lemma 2.1.2, we have $Y_{0} = (X \cap Y)^{\bar{*} \bar{*}} \subseteq Y^{\bar{*} \bar{*}} = Y$ . Thus we get (X ∩ Y) ⊆ Y₀ ⊂ Y, which contradicts with the known conditions. So Y₀ = Y, and $(X \cap Y)^{\bar{*}} = Y_{0}^{\bar{*}} = B$ .

Combining the above arguments, we obtain that (X ∩ Y) ^* = A, $(X \cap Y)^{\bar{*}} = B$ , so, (X ∩ Y, (A, B)) is an OE-concept.

Example 4.1.4. From Figs. 1 and 2, it is easy to observe that (123,abc) is a P-concept, and (124,e) is a N-concept, {123} ∩ {124} = {12} ∉ CL_E (U, V, R) ∪NCL_E (U, V, R), and {123} = α ({12}) in CL_E (U, V, R), {124} = α ({12}) in NCL_E (U, V, R), then (12,(abc,e)) is an OE-concept.

For brevity, the set of all concepts induced by Lemma 4.1.4 is denoted by $\begin{matrix} H_{4} = {(X \cap Y, (A, B)) | (X, A) \in CL (U, V, R), (Y, B) \\ \in NCL (U, V, R), (X \cap Y) \notin {CL}_{E} (U, V, R) \cup \\ {NCL}_{E} (U, V, R), and X = α (X \cap Y) \\ in {CL}_{E} (U, V, R), \end{matrix}$ $\begin{matrix} Y = α (X \cap Y) in {NCL}_{E} (U, V, R)} . \end{matrix}$

Combining Lemma 4.1.1-4.1.4, we know that all OE-concepts can be obtained from H₁, H₂, H₃, and H₄.

Theorem 4.1.1. Let (U, V, R) be a formal context, CL (U, V, R) and NCL (U, V, R) be classical concept lattice, then $OEL (U, V, R) = H_{1} \cup H_{2} \cup H_{3} \cup H_{4}$

Proof. On the one hand, we need to prove OEL (U, V, R) ⊆ H₁ ∪ H₂ ∪ H₃ ∪ H₄, for ∀ (X, (A, B)) ∈ OEL (U, V, R), from Definition 2.2.2, we have X^〈· = (A, B) and (A, B) ^·〉 = A^* ∩ $B^{\bar{*}} = X$ . In fact, for $A^{*} \cap B^{\bar{*}} = X$ , there are four cases below: $\begin{matrix} (1) A^{*} = X, B^{\bar{*}} = X . \\ (2) A^{*} = X, B^{\bar{*}} = Y_{0} \supset X . \\ (3) A^{*} = X_{0} \supset X, B^{\bar{*}} = X . \\ (4) A^{*} = X_{0} \supset X, B^{\bar{*}} = Y_{0} \supset X . \end{matrix}$

For case (1). A^* = X, X^* = A, by Definition 2.1.3, we know (X, A) is a P-concept. Similarly, $B^{\bar{*}} = X$ , $X^{\bar{*}} = B$ , (X, B) is a N-concept according to Definition 2.1.7. However, for the right hand side of Equation (a), it is easy to know that $(X, (A, B)) = (X, (X^{*}, X^{\bar{*}}))$ . So, in this case, (X, (A, B)) belongs to H₁.

For case (2). A^* = X, X^* = A, by Definition 2.1.3, we know (X, A) is a P-concept, but $B^{\bar{*}} = Y_{0} \supset X$ , thus, according to Definition 2.1.7, we know (X, B) is not a N-concept, combining with $X^{\bar{*}} = B$ , according to the Lemma 3.1.2 (2), we have (Y₀, B) is a N-concept. For the right hand side of Equation (a), it is easy to know that $(X, (A, B)) = (X, (X^{*}, Y_{0}^{\bar{*}}))$ . So, in this case, (X, (A, B)) belongs to H₂.

For case (3). $B^{\bar{*}} = X$ , $X^{\bar{*}} = B$ by Definition 2.1.7, we know (X, B) is a N-concept, but A^* = X₀ ⊃ X, by Definition 2.1.3, we have (X, A) is not a P-concept, combining with $X^{\bar{*}} = A$ , according to the Lemma 3.1.1(2), we have (X₀, A) is a P-concept. For the right hand side of Equation (a), it is easy to know that $(X, (A, B)) = (X, (X_{0}^{*}, X^{\bar{*}}))$ . Thus, in this case, (X, (A, B)) belongs to H₃.

For case (4). X^* = A, A^* = X₀ ⊃ X, by Definition 2.1.3, we know (X, A) is not a P-concept, and according to the Lemma 3.1.1(1), we have (X₀, A) is a P-concept. Analogously, $X^{\bar{*}} = B$ , $B^{\bar{*}} = Y_{0} \supset X$ by Definition 2.1.7, we know (X, B) is not a N-concept, and according to the Lemma 3.1.2(2), we have (Y₀, B) is a N-concept. Due to X₀ ⊃ X, Y₀ ⊃ X, X₀ ∩ Y₀ = X, For the right hand side of Equation (a), it is easy to know that $(X, (A, B)) = (X_{0} \cap Y_{0}, (X^{*}, Y^{\bar{*}}))$ Thus, in this case, (X, (A, B)) belongs to H₄. Combining the above arguments, we have OEL (U, V, R) = H₁ ∪ H₂ ∪ H₃ ∪ H₄.

On the other hand, we need to prove OEL (U, V, R) ⊇ H₁ ∪ H₂ ∪ H₃ ∪ H₄. According to the Lemmas 4.1.1-4.1.4, we know H₁, H₂, H₃, and H₄ are OE-concepts. Thus, we have H₁ ∪ H₂ ∪ H₃ ∪ H₄ ⊆ OEL (U, V, R).

To sum up, we obtain OEL (U, V, R) = H₁ ∪ H₂ ∪ H₃ ∪ H₄. This is the complete proof.

According to the above theorems, we can obtain OEL (U, V, R) only by CL (U, V, R) and NCL (U, V, R).

Firstly, CL (U, V, R) and NCL (U, V, R) need to be derived from the classical Next Closure algorithm [34], which is essential for obtaining three-way concepts based on the classical concepts. The corresponding algorithm (see Algorithm 1) is given as follows.

Analysis: Qi et al. [33] obtain equivalence classes by using ∧-preserving order-embedding and ∨-preserving order-embedding, and find out all of the least elements, then obtain all OE-concepts, however, compute the equivalence classes are complex. By contrast, it is simpler to get all OE-concepts by using the above equation relationship (a). If the number of CL (U, V, R) and NCL (U, V, R) obtained by the classical Next Closure algorithm [34] is n, m, the worst case time complexity of the algorithm 1 is O (n × m).

Algorithm 1. Let (U, V, R) be a formal context.

Input: CL (U, V, R) and NCL (U, V, R) from the formal context

(U, V, R).

Output: All of OE-concepts OEL (U, V, R).

1: Initialize H₁ =∅, H₂ =∅, H₃ =∅, H₄ =∅;

2: for C_i1 ∩ NC_j1 = C

if C = C_i1 and C = NC_j1

then H₁ = H₁ ∪ (C, (C_i2, NC_j2));

//C_i1 and C_i2 represent the extension and intension

of P-concept C_i in CL (U, V, R), respectively. NC_j1 and

NC_j2 represent the extension and intension of N-concept

NC_j in NCL (U, V, R), respectively.//

else if C = C_i1 and C ≠ NC_j1, and NC_j1 = α (C_i1)

in NCL_E (U, V, R).

then H₂ = H₂ ∪ (C_i1, (C_i2, NC_j2));

else if C ≠ C_i1 and C = NC_j1, and C_i1 = α (NC_j1)

in CL_E (U, V, R).

then H₃ = H₃ ∪ (NC_j1, (C_i2, NC_j2));

else if C ∉ CL_E (U, V, R) ∪ NCL_E (U, V, R), and C_i1 = α (C)

in CL_E (U, V, R), and NC_j1 = α (C) in NCL_E (U, V, R).

then H₄ = H₄ ∪ (C, (C_i2, NC_j2));

end if

3: end if

4: OEL (U, V, R) = H₁ ∪ H₂ ∪ H₃ ∪ H₄;

5: Output OEL (U, V, R).

Example 4.1.5 Acute inflammations data set is taken from the UCI international public database. Here we choose five patients and five Symptoms, which are lumbar pain, urgency, dysuria, urethral swelling, and acute cystitis, respectively.

We used 1,2,3,4,5 represent five the name of the patient, respectively, and used a = lumbar pain, b = urgency, c = dysuria, d = urethral swelling, e = acute cystitis, respectively.

Let (U, V, R) be a formal context (see Tables 3, 4), where U = {1, 2, 3, 4, 5}, and V = {a, b, c, d, e}. The corresponding CL (U, V, R) and NCL (U, V, R) are shown in Figs. 5 and 6, respectively.

Fig.5

CL (U, V, R) in Example 4.1.5.

Fig.6

NCL (U, V, R) in Example 4.1.5.

Table 3

The formal context (U,V,R) in Example 4.1.5

U	a	b	c	d	e
1	×		×
2	×	×	×		×
3			×
4	×
5	×	×	×	×

Table 4

The complement context (U,V,R^C) in Example 4.1.5

U	a	b	c	d	e
1		×		×	×
2				×
3	×	×		×	×
4		×	×	×	×
5					×

Now, based on the context in Tables 3 and 4, we apply Algorithm 1 to obtain all OE-concepts, which form an complete lattice OEL (U, V, R).

Firstly, obtain CL (U, V, R) and NCL (U, V, R) from the formal context (U, V, R):

CL (U, V, R) = {(U, ∅), (1235, c), (1245, a), (125, ac), (25, abc), (2, abce), (5, abcd), (∅, V)},

NCL (U, V, R) = {(U, ∅), (1234, d), (1345, e), (134, bde), (3, abde), (4, bcde), (∅, V)},

CL_E (U, V, R) = {U, 1235, 1245, 125, 25, 2, 5, ∅},

NCL_E (U, V, R) = {U, 1234, 1345, 134, 3, 4, ∅}.

Next, by using Algorithm 1, we have

H₁ = H₁ ∪ (C, (C_i2, NC_j2)) = {(U, (∅, ∅)), (∅, (V, V))};

H₂ = H₂ ∪ (C_i1, (C_i2, NC_j2)) = {(2, (abce, d)), (5, (abcd, e)), (25, (abc, ∅)), (125, (ac, ∅)), (1235, (c, ∅)), (1245, (a, ∅))};

H₃ = H₃ ∪ (NC_j1, (C_i2, NC_j2)) = {(3, (c, abde)), (4, (a, bcde)), (134, (∅, bde)), (1234, (∅, d)), (1345, (∅, e))};

H₄ = H₄ ∪ (C, (C_i2, NC_j2)) = {(123, (c, d)), (135, (c, e)), (13, (c, bde)), (124, (a, d)), (145, (a, e)), (14, (a, bde)), (12, (ac, d)), (15, (ac, e)), (1, (ac, bde))};

Finally, we obtain $\begin{matrix} OEL (U, V, R) = H_{1} \cup H_{2} \cup H_{3} \cup H_{4} \\ = {(U, (\emptyset, \emptyset)), (1, (ac, bde)), (2, (abce, d)), \end{matrix}$ $\begin{matrix} (3, (c, abde)), (4, (a, bcde)), (5, (abcd, e)), \\ (12, (ac, d)), (13, (c, bde)), (14, (a, bde)), \\ (15, (ac, e)), (25, (abc, \emptyset)), (123, (c, d)), \\ (124, (a, d)), (125, (ac, \emptyset)), (134, (\emptyset, bde)), \\ (135, (c, e)), (145, (a, e)), (1234, (\emptyset, d)), \\ (1235, (c, \emptyset)), (1245, (a, \emptyset)), (1345, (\emptyset, e)), \\ (\emptyset, (V, V))}; \end{matrix}$

and the corresponding OEL (U, V, R) is shown in Fig. 7.

Obviously, the OE-concept obtained by Algorithm 1 is complete.

Fig.7

OEL (U, V, R) in Example 4.1.5.

4.2 Relationships between AE-concepts and classical concepts

In this section, we discuss the relationship between P-concepts, N-concepts and AE-concepts. Based on this, we get four types of AE-concepts, which can form an complete lattice, i.e., AEL (U, V, R). Due to the proofs of related theorems are similar to those in Section 4.1, for brevity, we omit the proof in this section.

Lemma 4.2.1. Let (U, V, R) be a formal context. If (X, A) is a P-concept and (Y, A) is a N-concept, then ((X, Y), A) is an AE-concept.

For short, the set of all concepts induced by Lemma 4.2.1 is denoted by $\begin{matrix} M_{1} = {(X, Y), A) | (X, A) \in CL (U, V, R) \\ and (Y, A) \in NCL (U, V, R)} . \end{matrix}$

Lemma 4.2.2. Let (U, V, R) be a formal context. If (X, A) is a P-concept and (Y, B) is a N-concept, where A ∉ NCL_I (U, V, R), and B = α (A) in NCL_I (U, V, R), then ((X, Y), A) is an AE-concept.

For short, the set of all concepts induced by Lemma 4.2.2 is denoted by $\begin{matrix} M_{2} = {(X, Y), A) | (X, A) \in CL (U, V, R), (Y, B) \\ \in NCL (U, V, R) \\ where \\ A \notin {NCL}_{I} (U, V, R), B = α (A) in {NCL}_{I} (U, V, R)} . \end{matrix}$

Lemma 4.2.3. Let (U, V, R) be a formal context. If (Y, B) is a N-concept and (X, A) is a P-concept, where B ∉ CL_I (U, V, R), and A = α (B) in CL_I (U, V, R), then ((X, Y), B) is an AE-concept.

For short, the set of all concepts induced by Lemma 4.2.3 is denoted by $\begin{matrix} M_{3} = {(X, Y), B) | (X, A) \in CL (U, V, R), (Y, B) \\ \in NCL (U, V, R) \\ where \\ B \notin {CL}_{I} (U, V, R), A = α (B) in {CL}_{I} (U, V, R)} . \end{matrix}$

Lemma 4.2.4. Let (U, V, R) be a formal context. If (X, A) is a P-concept, and (Y, B) is a N-concept, (A ∩ B) ∉ CL_I (U, V, R) ∪ NCL_I (U, V, R), A = α (A ∩ B) in CL_I (U, V, R), B = α (A ∩ B) in NCL_I (U, V, R), then ((X, Y), A ∩ B) is an AE-concept.

For short, the set of all concepts induced by Lemma 4.2.4 is denoted by $\begin{matrix} M_{4} = {((X, Y), A \cap B) | (X, A) \in CL (U, V, R), (Y, B) \\ \in NCL (U, V, R), (A \cap B) \notin {CL}_{I} (U, V, R) \cup \\ {NCL}_{I} (U, V, R), and A = α (A \cap B) in {CL}_{I} (U, V, R) \\ B = α (A \cap B) in {NCL}_{I} (U, V, R)} . \end{matrix}$

Theorem 4.2.1. Let (U, V, R) be a formal context, CL (U, V, R) and NCL (U, V, R) be classical concept lattice, then $AEL (U, V, R) = M_{1} \cup M_{2} \cup M_{3} \cup M_{4} (b)$

According to Lemmas 4.2.1-4.2.5, we can obtain AEL (U, V, R) only by CL (U, V, R) and NCL (U, V, R).

Algorithm 2. Let (U,V,R) be a formal context.

Input: CL (U, V, R) and NCL (U, V, R) from the formal context

(U, V, R).

Output: All of AE-concepts AEL (U, V, R).

1: Initialize M₁ =∅, M₂ =∅, M₃ =∅, M₄ =∅;

2: for C_i2 ∩ NC_j2 = C

if C = C_i2 and C = NC_j2

then M₁ = M₁ ∪ ((C_i1, NC_j1), C);

//C_i1 and C_i2 represent the extension and

intension of P-concept C_i in CL (U, V, R),

respectively. NC_j1 and NC_j2 represent the

extension and intension of N-concept NC_j

in NCL (U, V, R), respectively. //

else if C = C_i2 and C ≠ NC_j2, and NC_j2 = α (C_i2) in

NCL_I (U, V, R).

then M₂ = M₂ ∪ ((C_i1, NC_j1), C)

else if C ≠ C_i2 and C = NC_j2, and C_j2 = α (NC_i2) in

CL_I (U, V, R).

then M₃ = M₃ ∪ ((C_i1, NC_j1), C)

else if C ∉ CL_I (U, V, R) ∪ NCL_I (U, V, R), and C_i2 = α (C)

in CL_I (U, V, R), and NC_j2 = α (C) in NCL_I (U, V, R).

then M₄ = M₄ ∪ ((C_i1, NC_j1), C)

end if

3: end if

4: AEL (U, V, R) = M₁ ∪ M₂ ∪ M₃ ∪ M₄;

5: Output AEL (U, V, R).

Analysis: since algorithm 1 is to obtain OE-concepts, algorithm 2 is to obtain AE-concepts, the basic idea is the same, so the time complexity is only related to the number of classical concepts. The worst case time complexity of the algorithm 2 is O (n × m).

5 Conclusion

Firstly, some properties related to classical concepts and three-way concepts have been presented, respectively. Based on this, this paper has studied the relationships between two types of three-way concepts (i.e., object-induced three-way concepts and attribute-induced three-way concepts) and classical concepts (i.e., formal concepts induced by positive operators and negative operators). More specifically, all object-induced (attribute-induced) three-way concepts can be obtained through four relationships between all classical concepts and object-induced (attribute-induced) three-way concepts, where four theorems have been given to characterize the four relationships, obtain the equation relationship between the three-way concepts and the classical concepts. Finally, two algorithms have been proposed to build object-induced concept lattice and attribute-induced concept lattice, respectively, and these algorithms have been verified efficiently.

Future work will do research on the composite operators which combine a pair of classical concept lattices into a three-way concept lattices.

Footnotes

Acknowledgments

This research is granted by National Nature Science Foundation of China (61572011) and National Nature Science Foundation of Hebei Province (A2018201117).

References

Wille

, Restructuring lattice theory: An approach based on hierarchies of concepts, in: Rival

(Ed.), Ordered Sets, Reidel Publishing Company, Dordrecht- Boston, 1982, pp. 445–470.

Ganter

and Wille

, Formal Concept Analysis, Mathe matical Foundations, Springer, Berlin, Heidelberg, 1999.

, Xing

Z.Y.

and Yin

H.D.

, Attribute reductions and concept lattices in interval-valued intuitionistic fuzzy rough set theory: Construction and properties, Journal of Intelligent and Fuzzy Systems 30(2) (2016), 1231–1242.

Klime

, Using formal concept analysis for control in cyber-physical systems, Procedia Engineering 69(1) (2014), 1518–1522.

Poelmans

, Ignatov

D.I.

, Kuznetsov

S.O.

and Dedene

, Formal concept analysis in knowledge processing: A survey on applications, Expert Systems with Applications 40(16) (2013), 6538–6560.

Jia

, Shang

, Zhou

and Yao

, Generalized attribute reduction rough set theory, , Knowledge-Based Systems 91 (2016), 204–218.

, Mei

, Xu

and Qian

, Concept learning via granular computing: A cognitive viewpoint, Information Sciences 298(1) (2015), 447–467.

Wan

and Wei

, Approximate concepts acquisition based on formal contexts, , Knowledge-Based Systems 75 (2015), 78–86.

Tang

, Hui

S.C.

and Fong

A.C.

, A lattice- based approach for chemical structural retrieval, , Engineering Applications of Artificial Intelligence 39 (2015), 215–222.

10.

Yao

, An outline of a theory of three- way decisions, in: Yao

, Yang

, Slowinski

, Greco

, Li

, Mitra

and Pol- kowski

(Eds.), Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, vol. 7413, Springer, Berlin, Heidelberg, 2012, pp. 1–17.

11.

and Zhou

, Risk decision making based on decision-theoretic rough set: A three-way view decision model, International Journal of Computational Intelligence Systems 4(1) (2011), 1–11.

12.

Yao

, Granular computing and sequential three-way decisions, in: Lingras

, Wolski

, Cornells

, Mitra

and Wasilewski

(Eds.), Rough Sets and Knowledge Technology, Lecture Notes in Computer Science, vol. 8171, Springer, Berlin, Heidelberg, 2013, pp. 16–27.

13.

Yao

and Azam

, Web-based medical decision support systems for three-way medical decision making with game theoretic rough sets, IEEE Transactions on Fuzzy Systems 23(1) (2015), 3–15.

14.

, Wang

and Jiao

, A three-way decisions approach to density-based over lapping clustering, in: Peters

J.F.

, Skowron

, Li

, Yang

, Yao

and Nguyen

H.S.

(Eds.), Transactions on Rough Sets XVIII, Lecture Notes in Computer Science, vol. 8449, Springer, Berlin, Heidelberg, 2014, pp. 92–109.

15.

, Zhang

and Hu

, An incremental clustering approach based on three-way decisions, in: Cornells

, Kryszkiewicz

, Slezak

, Ruiz

, Bello

and Shang

(Eds.), Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, vol. 8536, Springer International Publishing, 2014, pp. 152–159.

16.

Deng

and Yao

, Decision-theoretic three-way approximations of fuzzy sets, , Information Sciences 279 (2014), 702–715.

17.

Luo

, Li

and Chen

, Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization, , Information Sciences 257 (2014), 210–228.

18.

Zhang

, Zou

, Chen

, Wang

, Tang

and Zhao

, Cost-sensitive three-way decisions model based on CCA, in: Cornells

, Kryszkiewicz

, Slezak

, Ruiz

, Bello

and Shang

(Eds.), Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, vol. 8536, Springer International Publishing, 2014, pp. 172–180.

19.

, Zhang

and Wang

, A tree-based in crèmental over lapping clustering method using the three-way decision theory, Knowledge-Based Systems 91 (2015), 189–203.

20.

Yao

, Three-way decisions with probabilistic rough sets, Information Sciences 180(3) (2010), 341–353.

21.

Yao

, Three-way decision: An interpretation of rules in rough set theory, in: Wen

, Li

, Polkowski

, Yao

, Tsumoto

and Wang

(Eds.), Rough Sets and Knowledge Technology, Lecture in Notes Computer Science, vol. 5589, Springer, Berlin, Heidelberg, 2009, pp. 642–649.

22.

, Wei

and Yao

, Three-way formal concept analysis, in: Miao

, Pedrycz

, Slezak

, Peters

, Hu

and Wang

(Eds.), Rough Sets and Knowledge Technology, Lecture Notes in Computer Science, vol. 8818, Springer International Publishing, 2014, pp.732–741.

23.

Yao

, The superiority of three-way decisions in probabilistic rough set models, Information Sciences 181(6) (2011), 1080–1096.

24.

B.Q.

, Three-way decisions space and three-way decisions, Information Sciences 281 (2014), 21–52.

25.

She

, On determination of thresholds in three-way approximation of many-valued nm-logic, in: Cornells

, Kryszkiewicz

, Slezak

, Ruiz

, Bello

and Shang

(Eds.), Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, vol. 8536, Springer International Publishing, 2014, pp. 136–143.

26.

Yao

, Interval sets and three-way concept analysis in incomplete contexts, &, Cybernetics (2016), 1–18.

27.

Ren

R.S.

and Wei

, The attribute reductions of three-way concept lattices, Knowledge -Based Systems 99 (2016), 92–102.

28.

M.Z.

and Wang

G.Y.

, Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts, Knowledge-Based Systems 91 (2016), 165–178.

29.

Singh

P.K.

, Three-way fuzzy concept lattice representation using neutrosophic set, International Journal of Machine Learning & Cybernetics 8(1) (2016), 69–79.

30.

Shivhare

and Cherukuri

A.K.

, Three-way conceptual approach for cognitive memory functionalities, International Journal of Machine Learning & Cybernetics 8(1) (2016), 21–34.

31.

Ren

, Wei

and Yao

, An analysis of three types of partially-known formal concepts, Cybernetics (2017), 1–17, 10.1007/s13042-017-0743-z

32.

, Huang

, Qi

, Qian

and Liu

, Three-way cognitive concept learning via muti-granularity, Information Sciences 378(1) (2017), 244–263.

33.

J.J.

, Qian

and Wei

, The connections between three-way and classical concept lattices, Knowledge-Based Systems 91 (2016), 143–151.

34.

Carpineto

and Romano

, Concept data analysis: Theory and application, John Wiley & Sons 2004, pp. 85–103.

Relationships between three-way concepts and classical concepts

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Basic notions of formal concept analysis

Table 1 The formal context in Example 2.1.1 U a b c d e 1 × × × × 2 × × × 3 × × × × 4 ×

3.1 Some properties of classical concepts

3.2 Some properties of three-way concepts

4 Relationships between three-way concepts and classical concepts

4.1 Relationships between OE-concepts and classical concepts

5 Conclusion

Footnotes

Acknowledgments

References

Table 1
The formal context in Example 2.1.1

U a b c d e

1 × × × ×

2 × × ×

3 × × × ×

4 ×