Approximation operators for semiconcepts

Abstract

For a formal context, we define an equivalence relation on the set of attributes. Through this equivalence relation, we define the lower and upper approximation operators relative to the family of semiconcepts of the formal context. We study on the two operators with the further properties that are interesting and valuable in the theory of rough set. In addition, we research on the lattice properties of all of semiconcepts in a formal context. Using this lattice, we set up two operators, and find their approximation properties in the theory of rough set. The two ways for giving approximations generalize the idea of Pawlak rough set approximations from one universal set to two non-related universal sets. We provide examples to exam the correct of the two approximation ways in this paper.

Keywords

Semiconcept approximation equivalence relation lattice rough set

1. Introduction

The theory of rough set, proposed by Pawlak [1], is motivated by practical needs in classification, concept formation, and data analysis with insufficient and incomplete information (cf. Pawlak [2]). It is a very useful mathematical tool in classification of a collected data under equivalence relation (see [1 –3]). We interpret the rough set theory as an extension of set theory with two additional unary set-theoretic operators referred to as approximation operators (cf. Pawlak [1]). There are many generalized approximations of the standard Pawlak model (see [4 –9]) and the applied areas of Pawlak model and the generalized models (see [2 , 11]). Some of the generalized approximations are applied to formal concept analysis, e.g. Xu, Yao and Miao [6].

Formal concept analysis, proposed by Wille [12] as a mathematical theory of concepts, is used successfully in the area of knowledge representation and knowledge processing (cf. [13, 14]). With the development of formal concept analysis, Vormbrock and Wille point [15] that formal concept analysis has been formally enriched by introducing the notions of semiconcepts.

Semiconcepts have been first considered in the development of conceptual knowledge systems in Luksch and Wille [16]. After that, there are many results for researching on semiconcepts (cf. [14 , 17–21]). How to describe and define semiconcepts properly is a basic question of the philosophical doctrine of semiconcepts. If we can characterize semiconcepts with a new idea such as rough set which is different from that before, then for the theory semiconcepts, we will make advantage and give a good answer to the above basic question. We observe the fact that the existed applications of rough set in the research of formal concept analysis bring plentiful results. All of these applications are discussed on one universal set or on one universal set up to isomorphism as some existed results of rough set do. However, some information systems need to be described on two non-related sets at the same time. For example, a formal context is consisted by two non-related universal sets: one is the set of objects and another is the set of attributes. In addition, a semiconcept is described in a formal context by two parts: one is a subset of objects and another is a subset of attributes. Additionally, we hope to obtain a good success with rough set to semiconcept since rough set has been successful applied in many kinds of information systems. Up to now, for rough set theory, some informations are described by two sets such as Wong, Wang and Yao [22] generalized the rough set model using two distinct but related universal sets, and Liu [23] discussed some properties and applications of rough set based on two distinct but related universal sets as that in Wong, Wang and Yao [22]. In fact, the correspondent results in [22, 23] are expressed on ‘one’ set since there is a map between the two universal sets. If we use the standard Pawlak model or an existed extension of standard Pawlak model on rough set to describe semiconcept, it is a little difficult since all of these models are defined in one universal set, or two related universal sets. However a semiconcept needs to be expressed by two finite non-related sets such that the two finite sets do not have a map from one set to another one as that defined in Wong, Wang and Yao [22]. Based on this idea, we should solve the extension of the ground set of rough set from one set or two related sets to two non-related sets. We notice that Pawlak [1, 2] and Liu [23] said, one of the main directions of research in rough set theory is naturally the generalization of the Pawlak rough set approximations. Hence, in this paper, with the assistance of Pawlak standard model (see Pawlak [1]) and a lattice model (cf. Yao [4]) in rough set respectively, we will generalize standard Pawlak model and the lattice model to two finite and nonempty sets O and P for a formal context K=(O, P, I) in order to approximate every subset of O × P by the lower and upper approximation operators presented in this paper, and characterize the set of semiconcepts in K. We hope that the results here can not only generalize Pawlak model of rough set from one universal set to two non-related universal sets, but also be benefit for a formal context, and further, for the other information systems which need to be expressed in a two non-related sets or a more than two non-related sets.

The rest of this paper is arranged as follows: Section 2 is to review some notations and lemmas what we need later on. In Section 3, for the semiconcepts in a formal context, with respect to an equivalence relation on the attribute set, we can construct the approximation operators with the assistance of the family of equivalence classes. Another content is based on lattice theory to define approximation operators. We prove that any of the two kinds of approximations can characterize the set of semiconcepts, respectively. The last one is Section 4 which concludes this paper and leaves room for our future works.

2. Some notations and lemmas

This section will review some definitions and properties needed in the sequel. For more details, formal concept analysis is referred to Ganter and Wille [13], semiconcept is seen Vormbrock and Wille [15], and rough set is seen Pawlak [2].

Definition 2.1. (1)[13,pp.17-18] A formal context is a set structure K:=(O, P, I) for which O and P are nonempty sets while I is a binary relation between O and P, i.e. I ⊆ O × P; the elements of O and P are called objects and attributes, respectively, and gIm is (g, m) ∈ I. The derivation operators of K are defined as follows (X ⊆ O, Y ⊆ P): X′ : = {m ∈ P ∣ gIm for all g ∈ X} and Y′ : = {g ∈ O ∣ gIm for all m ∈ Y}.

(2)[15] In an arbitrary context K:=(O, P, I), a pair (A, B) with A ⊆ O and B ⊆ P is called a ⊓-semiconcept if A′ = B. Dually, a pair (C, D) with C ⊆ O and D ⊆ P is called a ⊔-semiconcept if D′ = C.

Remark 2.1. (1) In this paper, both O and P are finite and nonemtpy.

(2) Ganter and Wille [13,p.17] indicate that every formal context can be represented by a cross table. We may easily see that full rows and full columns are always reducible (see Ganter and Wille [13,p.24]); thereby we mean objects g with g′ = P and attributes m with m′ = O, respectively. Therefore, in this paper, we consider the formal contexts with no full rows and no full columns.

Lemma 2.1. (1)[13] The two derivation operators in a formal context K=(O, P, I) satisfy the following conditions for any Z, Z ₁, Z ₂ ⊆ O (or Z, Z ₁, Z ₂ ⊆ P):

(1.1) $Z_{1} \subseteq Z_{2} \Rightarrow Z_{1}^{'} \supseteq Z_{2}^{'}$ ; (1.2) Z ⊆ Z ^′′.

(2)[13,p.19] If T is an index set and, for every t ∈ T, A _t ⊆ O is a set of objects, then $(⋃_{t \in T} A_{t})^{'} = ⋂_{t \in T} A_{t}^{'}$ . The same holds for the sets of attributes.

Since the family of ⊓-semiconcepts has the dual property for the family of ⊔-semiconcepts, we only consider the set of ⊓-semiconcepts in this paper. Furthermore, we will say a semiconcept instead of a ⊓-semiconcept in what follows. All of ⊓-semiconcepts in a formal context K=(O, P, I) is denoted as ß(K).

Let K=(O, P, I) be a formal context, X ₁, X ₂ ⊆ O and Y ₁, Y ₂ ⊆ P. We give some notations as follows:

(1) (X ₁, Y ₁) ⊆ (X ₂, Y ₂) : ⇔ X ₁ ⊆ X ₂ and Y ₁ ⊆ Y ₂;

(2) (X ₁, Y ₁) ∪ (X ₂, Y ₂) : = (X ₁ ∪ X ₂, Y ₁ ∪ Y ₂);

(3) (X ₁, Y ₁) ∩ (X ₂, Y ₂) : = (X ₁ ∩ X ₂, Y ₁ ∩ Y ₂).

3. Generalized approximation operators

Pawlak’s standard rough set model [1] depends on an equivalence relation on a universal set. Many researchers have developed standard rough set model in many ways [4–7 , 25].

Xu, Yao and Miao [6] discussed the approximations in formal concept analysis with lattice-theoretic operators. But, it deals with the extent lattice and intent lattice respectively. In fact, it still defined on one dimension, that is on one universal set. Hence, all the discussions in [6] are similar to that in [4 , 11] if we consider the dimension in their background sets.

Though there are covering approximation spaces (see Safari and Hooshmandasl [24]) which are a generalization of equivalence-based rough set theories. They still consider the approximation spaces defined on one dimension space. That is to say, these covering approximation spaces generalized Pawlak’s standard model with one dimension space only.

Mao and Kang [25] studied the approximations for concept lattice with the aid of variable precision rough set which is an extension of rough set (see Ziarko [26]). However, it needs to know all of concepts in a formal context, and then to approximate the sets not concepts. In fact, it approximates the sets in the family of objects or the family of attributes respectively. Hence, it also generalized the idea of Pawlak’s standard model only in one dimension space.

In the above, we analyze the approximation operators defined on several typical rough sets respectively. As a result, we find that none of them is defined on two non-related universal sets, though it is important to the theory of approximation in formal concept analysis.

We know from Vormbrock [14] that in a formal context, every concept is a semiconcept and not vice versa. Up to now, there does not find the approximation operators for semiconcepts. All of these existed approximation results in [4–7 , 25] for formal concept analysis come from the thought of Pawlak’s standard model on one universal set. Hence, it is necessary to consider approximation operators for semiconcept with the assistance of Pawlak’s standard model from one universal set to two dimensions space, i.e. two non-related universal sets. In addition, we may be assured that lattice theory is important also to the research of semiconcepts.

All the results provided here are useful for concept lattice since every concept is a semiconcept.

When we consider the approximations on the family of semiconcepts in a formal context K, we should first consider how to express Pawlak’s standard model on the family of semiconcepts of K. That is to say, we should solve how to use an equivalence relation to obtain approximation operators for the family of semiconcepts of K. After that, we will consider a development model of approximations on the family of semiconcepts of K by lattice theory.

From Pawlak’s standard model for rough set in [1, 2] and the other extension models, we determine that in an information system IS, two operators are called the lower and upper approximation operators if the following conditions are satisfied.

(p1) it should give a family of subsets on a background set S defined by IS as the set of fundamental sets;

(p2) the lower approximation operator of X is contained in X, and X is contained in the upper approximation operator of X, for any subset X of S;

(p3) the lower and upper approximation operators can characterize the fundamental sets.

In this paper, we will pay attention to semiconcepts in a formal context K=(O, P, I). Hence, the background set is O × P, and the family ß(K) of all of semiconcepts in K is the set of fundamental sets. That is to say, every semiconcept is a fundamental set, and vice versa. Hence, (p1) is done. Additionally, we need to approximate every (X, Y) ⊆ (O, P) with the lower and upper approximation operators presented in this paper. The works (p2) and (p3) will be done in Subsections 3.1 and 3.2 in two different ways.

3.1 Approximation operators relevant to an equivalence relation

First, we will discuss some special elements in ß(K).

Lemma 3.1. Let K = (O, P, I) be a formal context and (X, Y) ⊆ (O, P). Then the following statements are correct.

(1) X = O ⇒ (X, ∅) ∈ B (K).

(2) (∅ , Y) ∈ ß (K) ⇔ Y=P.

Proof. To prove item (1).

By Definition 2.1(1) and Remark 2.1, we may easily obtain X = O⇒ X′ = ∅. Thus, (X, ∅) ∈ ß (K) holds according to Definition 2.1(2).

To prove item (2).

By Definition 2.1 and Remark 2.1, we may easily see ∅′ = P if ∅ ⊆ O. Thus, (∅ , Y) ∈ ß (K) implies Y = P.

Conversely, according to the given Y = P and Remark 2.1, we find that if X′ = P for X ⊆ O, then X =∅. Hence, we obtain the correct of (∅ , Y) ∈ ß (K).

We will use an example to show the converse of item (1) in Lemma 3.1 not to be true.

Example 3.1. Let a formal context K ₁ be used by Vormbrock and Wille [15], in which the object set is {Kempinski, Hilton, Ibis, ISSY} and the set of attributes is {Guest House, Hotel, First Class, Luxus}, and the relation is shown as Table 1.

Table 1

Guest House Hotel First Class Luxus

Kempinski × × ×

Hilton × ×

Ibis ×

ISSY ×

	Guest House	Hotel	First Class	Luxus
Kempinski		×	×	×
Hilton		×	×
Ibis		×
ISSY	×

We set: Kempinski=a ₁, Hilton=a ₂, Ibis=a ₃ and ISSY=a ₄; Guest House=b ₁, Hotel=b ₂, First Class=b ₃ and Luxus=b ₄. Then Table 1 is expressed as Table 2.

Table 2

	b ₁	b ₂	b ₃	b ₄
a ₁		×	×	×
a ₂		×	×
a ₃		×
a ₄	×

Using Definition 2.1, we can obtain all of X′ for any X ⊆ O ₁ = {a ₁, a ₂, a ₃, a ₄} as follows. In fact, we see P ₁ = {b ₁, b ₂, b ₃, b ₄}.

∅′ = P ₁; {a ₁} ′ = {b ₂, b ₃, b ₄} , {a ₂} ′ = {b ₂, b ₃}, {a ₃} ′ = {b ₂} , {a ₄} ′ = {b ₁}; {a ₁, a ₂} ′ = {b ₂, b ₃}, {a ₁, a ₃} ′ = {b ₂} , {a ₁, a ₄} ′ = ∅ , {a ₂, a ₃} ′ = {b ₂}, {a ₂, a ₄} ′ =∅ , {a ₃, a ₄} ′ = ∅; {a ₁, a ₂, a ₃} ′ = {b ₂} , {a ₁, a ₂, a ₄} ′ =∅ , {a ₂, a ₃, a ₄} ′ = ∅, {a ₁, a ₃, a ₄} ′ =∅; {a ₁, a ₂, a ₃, a ₄} ′ =∅.

All of semiconcepts are (X, X′) for any X ⊆ O ₁.

We see {a ₂, a ₄} ′ =∅. This means ({a ₂, a ₄} , ∅) ∈ ß (K ₁) though {a ₂, a ₄} ≠ O ₁.

Next, we define a relation on P for a formal context K=(O, P, I).

Definition 3.1. Let E ⊆ P × P be a relation on P defined as follows:

b ₁ Eb ₂ if and only if {b ₁} ′ = {b ₂} ′.

We may easily prove E to be an equivalence relation on P. The equivalence class containing x for x ∈ P is given by [x] _E.

From Definition 3.1, we find that [b] _E is the set which is indistinguishable with b ∈ P. In the coming discussion, we will find that we only need to pay attention to [b] _E for any b ∈ P. This hints that whether | [b] _E|>1 or | [b] _E|=1 will not affect our discussion. Additionally, for the set of attributes, it is easy to obtain {_E ∣ b ∈ P}. Hence, we omit to show how to obtain [b] _E for any b ∈ P in a formal context K=(O, P, I). This is the reason why we choose K ₁ to be a running formal context. That is to say, K ₁, in which satisfies | [b] _E|=1 for any b ∈ P ₁, is enough to express what we attend to study on.

Second, for the case of X≠ ∅ and Y≠ ∅, we will find the characterization of (X, Y) ∈ ß (K). To do this duty, we define two operators on K as follows.

Definition 3.2. Let K=(O, P, I) be a formal context and E be the relation defined in Definition 3.1. For (X, Y) ⊆ (O, P) and X≠ ∅ and Y≠ ∅, let L (X, Y) = {({x} , [b] _E ∩ Y) ∣ x ∈ X, b ∈ P satisfies b ∈ {x} ′} and U (X, Y) = {({x} , [b] _E ∪ Y) ∣ x ∈ X, b ∈ P satisfies b ∈ {x} ′}. We have two operators $\underline{R}$ and $\bar{R}$ be defined as follows: let X = {x ₁, …, x _n},

$\underline{R} (X, Y) = (⋃_{\exists [b]_{E} satisfies ({x}, [b]_{E} \cap Y) \in L (X, Y)} x,$ $⋂_{j = 1}^{n} (⋃_{({x_{j}}, [b]_{E} \cap Y) \in L (X, Y)} ([b]_{E} \cap Y)))$ ;

$\bar{R} (X, Y) = (⋃_{\exists [b]_{E} satisfies ({x}, [b]_{E} \cup Y) \in U (X, Y)} x,$ $⋂_{j = 1}^{n} (⋃_{({x_{j}}, [b]_{E} \cup Y) \in U (X, Y)} ([b]_{E} \cup Y)))$ .

Lemma 3.2. In a formal context (O, P, I), let (X, Y) ⊆ (O, P) satisfy X≠ ∅ and Y≠ ∅. Then, $\underline{R} (X, Y) = (X, X^{'} \cap Y)$ and $\bar{R} (X, Y) = (X, X^{'} \cup Y)$ hold.

Proof. By Remark 2.1, we decide that for any x ∈ X, there exists b _x ∈ P satisfying xIb _x, i.e. b _x ∈ {x} ′. Hence, we determine ⋃_{∃[b]_E satisfies ({x},[b]_E∩Y)∈L(X,Y)} x = ⋃_{∃[b]_E satisfies ({x},[b]_E∪Y)∈U(X,Y)} x = X.

According to Lemma 2.1 and Definitions 2.1 and 3.1, we find $X^{'} = (⋃_{x \in X} x)^{'} = ⋂_{x \in X} x^{'} = ⋂_{x \in X} (⋃_{xIb} b) = ⋂_{x \in X} (⋃_{xIb} [b]_{E}) = ⋂_{j = 1}^{n} (⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} [b]_{E})$ . This follows

$X^{'} \cap Y = (⋂_{j = 1}^{n} (⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} [b]_{E})) \cap Y = ⋂_{j = 1}^{n} (⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} ([b]_{E} \cap Y))$

= $⋂_{j = 1}^{n} (⋃_{({x_{j}}, [b]_{E} \cap Y) \in L (X, Y)} ([b]_{E} \cap Y))$ and $X^{'} \cup Y = (⋂_{j = 1}^{n} (⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} [b]_{E})) \cup Y = ⋂_{j = 1}^{n} ((⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} [b]_{E}) \cup Y) =$ $⋂_{j = 1}^{n} (⋃_{\exists x_{j} \in X satisfies b \in x_{j}^{'}} ([b]_{E} \cup Y)) =$ $⋂_{j = 1}^{n} (⋃_{({x_{j}}, [b]_{E} \cup Y) \in U (X, Y)} ([b]_{E} \cup Y))$ .

Summing up the above, we obtain $\underline{R} (X, Y) = (X, X^{'} \cap Y)$ and $\bar{R} (X, Y) = (X, X^{'} \cup Y)$ .

We will demonstrate the two operators defined in Definition 3.2 to fulfil the works (p2) and (p3) for (X, Y) ⊆ (O, P) with X≠ ∅ and Y≠ ∅.

Theorem 3.1. Let (X, Y) ⊆ (O, P) satisfy X≠ ∅ and Y≠ ∅ in a formal context K=(O, P, I). Then, the following statements are correct.

(1) $\underline{R} (X, Y) \subseteq (X, Y) \subseteq \bar{R} (X, Y)$ .

(2) $\underline{R} (X, Y) = \bar{R} (X, Y) = (X, Y)$ if and only if (X, Y) ∈ ß (K).

Proof. Combining X′ ∩ Y ⊆ Y ⊆ X′ ∪ Y and Lemma 3.2, we may easily obtain the correct of item (1).

Next, we will prove item (2) with two steps.

Step 1. If $\underline{R} (X, Y) = \bar{R} (X, Y) = (X, Y)$ .

$\underline{R} (X, Y) = (X, Y)$ and Lemma 3.2 together implies Y = X′ ∩ Y. This follows Y ⊆ X′. On the other hand, $\bar{R} (X, Y) = (X, Y)$ and Lemma 3.2 together implies Y = X′ ∪ Y. This follows X′ ⊆ Y. The above two hands infer to X′ = Y. According to Definition 2.1, this means (X, Y) ∈ ß (K).

Step 2. If (X, Y) ∈ ß (K).

In view of Definition 2.1, we obtain Y = X′. Combining Lemma 3.2, we receive $\underline{R} (X, Y) = (X, X^{'} \cap Y) = (X, Y \cap Y) = (X, Y)$ and $\bar{R} (X, Y) = (X, X^{'} \cup Y) = (X, Y \cup Y) = (X, Y)$ . Summarizing, we see $\underline{R} (X, Y) = \bar{R} (X, Y) = (X, Y)$ .

Third, we will give two approximation operators and discuss the properties relative to (p2) and (p3) for (X, Y) ⊆ (O, P) such that at least one of X and Y is ∅ in the following.

After we analyze Lemmas 3.1 and 3.2, we can provide some definitions as follows for (X, Y) ⊆ (O, P) such that at least one of X and Y is an empty set.

(D1) If X =∅, then we define $\underline{R} (\emptyset, Y) = (\emptyset, Y)$ and $\bar{R} (\emptyset, Y) = (\emptyset, P)$ .

(D2) If Y =∅, then we define $\underline{R} (X, \emptyset) = (X, \emptyset)$ and $\bar{R} (X, \emptyset) = (X, X^{'})$ .

We will obtain the following results relative to (D1) and (D2).

Lemma 3.3. Let (X, Y) ⊆ (O, P) such that at least one of X and Y is ∅. Then the following statements are correct.

(1) $\underline{R} (\emptyset, Y) \subseteq (\emptyset, Y) \subseteq \bar{R} (\emptyset, Y)$ ;

$\underline{R} (X, \emptyset) \subseteq (X, \emptyset) \subseteq \bar{R} (X, \emptyset)$ .

(2) $\underline{R} (\emptyset, Y) = \bar{R} (\emptyset, Y) \Leftrightarrow (\emptyset, Y) \in ß (K)$ ;

$\underline{R} (X, \emptyset) = \bar{R} (X, \emptyset) \Leftrightarrow (X, \emptyset) \in ß (K)$ .

Proof. To prove item (1).

We easily find $\underline{R} (\emptyset, Y) = (\emptyset, Y) \subseteq (\emptyset, Y) \subseteq (\emptyset, P) = \bar{R} (\emptyset, Y)$ since Y ⊆ P and (D1).

We also easily find $\underline{R} (X, \emptyset) = (X, \emptyset) \subseteq (X, \emptyset) \subseteq (X, X^{'}) = \bar{R} (X, \emptyset)$ since ∅ ⊆ X′ and (D2).

To prove item (2).

When $\underline{R} (\emptyset, Y) = \bar{R} (\emptyset, Y)$ . Then we decide (∅ , Y) = (∅ , P) since $\underline{R} (\emptyset, Y) = (\emptyset, Y)$ and $\bar{R} (\emptyset, Y) = (\emptyset, P)$ . This means Y = P. Using Lemma 3.1, we obtain (∅ , Y) ∈ ß (K).

When (∅ , Y) ∈ ß (K). Using Lemma 3.1, we obtain Y = P. That is to say, (∅ , Y) = (∅ , P) holds. Hence, we obtain $\underline{R} (\emptyset, Y) = (\emptyset, Y) = (\emptyset, P) = \bar{R} (\emptyset, Y)$ .

When $\underline{R} (X, \emptyset) = \bar{R} (X, \emptyset)$ . Then we decide (X, ∅) = (X, X′) since $\underline{R} (X, \emptyset) = (X, \emptyset)$ and $\bar{R} (X, \emptyset) = (X, X^{'})$ . This means X′ =∅. Using Definition 2.1, we obtain (X, ∅) ∈ ß (K).

When (X, ∅) ∈ ß (K). Then, by Definition 2.1, this means X′ =∅. Hence, we determine $\underline{R} (X, \emptyset) = \bar{R} (X, \emptyset)$ since $\underline{R} (X, \emptyset) = (X, \emptyset)$ and $\bar{R} (X, \emptyset) = (X, X^{'}) = (X, \emptyset)$ .

Analyzing the approximations for (∅ , Y) and (X, ∅) where X ⊆ O and Y ⊆ P, we may easily find the following statements.

(i) $\underline{R} (\emptyset, Y) = (\emptyset, \emptyset^{'} \cap Y)$ since ∅′ = P.

(ii) $\bar{R} (\emptyset, Y) = (\emptyset, \emptyset^{'} \cup Y)$ since ∅′ = P.

(iii) $\underline{R} (X, \emptyset) = (X, X^{'} \cap \emptyset)$ since X′∩ ∅ = ∅.

(iv) $\bar{R} (X, \emptyset) = (X, X^{'} \cup \emptyset)$ since X′ ∪ ∅ = X′.

Combining the statements (i)-(iv), Theorem 3.1 and Lemma 3.3, we can state that for any (X, Y) ⊆ (O, P), $\underline{R} (X, Y) = (X, X^{'} \cap Y)$ and $\bar{R} (X, Y) = (X, X^{'} \cup Y)$ are two approximation operators. We can call them lower approximation operator and upper approximation operator, respectively. The two operators satisfy $\underline{R} (X, Y) \subseteq (X, Y) \subseteq \bar{R} (X, Y)$ and $\underline{R} (X, Y) = \bar{R} (X, Y) = (X, Y) \Leftrightarrow (X, Y) \in ß (K)$ . Therefore, we may state that the two operators $\underline{R}$ and $\bar{R}$ provided above fulfil the works (p2) and (p3).

Next, we will analyze the rationality of $\underline{R}$ and $\bar{R}$ .

(A1) From Definition 3.2, we see that using equivalence relation, we define $\underline{R}$ and $\bar{R}$ for X ₀≠ ∅ and Y ₀≠ ∅, though ({x} , [b] _E ∩ Y ₀) ∈ L (X ₀, Y ₀) and ({x} , [b] _E ∪ Y ₀) ∈ U (X ₀, Y ₀) perhaps do not belong to ß (K). We still confirm that they have some relation with ß (K) since ({x} , {x} ′) ∈ ß (K) and b ∈ {x} ′.

(A2) Considering Lemmas 3.2 and 3.3 and the statements (i)-(iv), for any (X, Y) ⊆ (O, P), we find $\underline{R} (X, Y) = (X, X^{'} \cap Y) = (X, X^{'}) \cap (X, Y)$ and $\bar{R} (X, Y) = (X, X^{'} \cup Y) = (X, X^{'}) \cup (X, Y)$ . According to (X, X′) ∈ ß (K), we may state that $\underline{R}$ and $\bar{R}$ are defined with the assistance of ß (K), and $\underline{R}$ and $\bar{R}$ reflect the closeness between (X, X′) and (X, Y) from lower and upper, respectively.

(A3) In view of Theorem 3.1 and Lemma 3.3, we can point that $\underline{R}$ and $\bar{R}$ fulfil the works (p2) and (p3). Hence, $\underline{R}$ and $\bar{R}$ are the lower and upper approximation operators according to (p1)-(p3).

(A4) Based on the above analysis (A1)-(A3), we can express that $\underline{R}$ and $\bar{R}$ are the generalization of Pawlak standard rough set approximations (cf. Pawlak [1]) to the two non-related universal sets for a formal context with respect of the family of semiconcepts.

We will use an example to express the results in this subsection.

Example 3.2. Let the formal context K ₁ be defined as Example 3.1. By Definition 3.1, we obtain [b ₁] _E = {b ₁} , [b ₂] _E = {b ₂} , [b ₃] _E = {b ₃} and [b ₄] _E = {b ₄}.

Let X ₁ = {a ₁, a ₂} and Y ₁ = {b ₄}. From Example 3.1, we find $X_{1}^{'} = {b_{2}, b_{3}}$ . Using Definition 3.2 and X ₁≠ ∅ and Y ₁≠ ∅, we obtain L (X ₁, Y ₁) = {({a ₁} , [b ₂] _E ∩ Y ₁) , ({a ₁} , [b ₃] _E ∩ Y ₁) , ({a ₁} , [b ₄] _E ∩ Y ₁) , ({a ₂} , [b ₂] _E ∩ Y ₁) , ({a ₂} , [b ₃] _E ∩ Y ₁)} = ({a ₁} , ∅) , ({a ₁} , {b ₄}) , ({a ₂} , ∅)} ≠ ∅ and U (X ₁, Y ₁) = {({a ₁} , [b ₂] _E ∪ Y ₁) , (a ₁, [b ₃] _E ∪ Y ₁) , ({a ₁} , [b ₄] _E ∪ Y ₁) , ({a ₂} , [b ₂] _E ∪ Y ₁) , ({a ₂}, [b ₃] _E∪ Y ₁)} ≠ ∅.

Furthermore, by Definition 3.2, we attain $\underline{R} (X_{1}, Y_{1}) = ({a_{1}} \cup {a_{2}}, (\emptyset \cup {b_{4}}) \cap (\emptyset))) = ({a_{1}, a_{2}}, {b_{4}} \cap \emptyset) = ({a_{1}, a_{2}}, \emptyset)$ and $\bar{R} (X_{1}, Y_{1}) = ({a_{1}, a_{2}}, ([b_{2}]_{E}$ ∪ [b ₃] _E ∪ [b ₄] _E ∪ {b ₄}) ∩ ([b ₂] _E ∪ [b ₃] _E ∪ {b ₄})) = ({a ₁, a ₂} , {b ₂, b ₃, b ₄}). That is to say, $\underline{R} (X_{1}, Y_{1}) \subseteq (X_{1}, Y_{1}) \subseteq \bar{R} (X_{1}, Y_{1})$ holds since {a ₁, a ₂} ⊆ {a ₁, a ₂} and ∅ ⊆ {b ₄} ⊆ {b ₂, b ₃, b ₄}. From $\underline{R} (X_{1}, Y_{1})$ $\neq \bar{R} (X_{1}, Y_{1})$ , we can point (X ₁, Y ₁) ∉ ß (K ₁) by Theorem 3.1. On the other hand, using Definition 2.1 and $X_{1}^{'} \neq Y_{1}$ , we also obtain (X ₁, Y ₁) ∉ ß (K ₁). In addition, we also see $(X_{1}, X_{1}^{'} \cap Y_{1}) = (X_{1}, {b_{2}, b_{3}} \cap {b_{4}}) = (X_{1}, \emptyset) = ({a_{1}, a_{2}}, \emptyset) = \underline{R} (X_{1}, Y_{1})$ and $(X_{1}, X_{1}^{'} \cup Y_{1}) = (X_{1}, {b_{2}, b_{3}} \cup {b_{4}}) = ({a_{1}, a_{2}}, {b_{2}, b_{3}, b_{4}}) = \bar{R} (X_{1}, Y_{1})$ .

Let X ₂ = {a ₁, a ₂, a ₃} and Y ₂ = {b ₂}. Then, there is L (X ₂, Y ₂) = {({a ₁} , [b ₂] _E ∩ {b ₂}) , ({a ₁} , [b ₃] _E ∩ {b ₂}) , ({a ₁} , [b ₄] _E ∩ {b ₂}) , ({a ₂} , [b ₂] _E ∩ {b ₂}), ({a ₂} , [b ₃] _E ∩ {b ₂}) , ({a ₃} , [b ₂] _E ∩ {b ₂})} = {({a ₁} , {b ₂}) , ({a ₁} , ∅) , ({a ₂} , {b ₂}) , ({a ₂} , ∅) , ({a ₃} , {b ₂})} and U (X ₂, Y ₂) = {({a ₁} , [b ₂] _E ∪ {b ₂}) , ({a ₁} , [b ₃] _E ∪ {b ₂}) , ({a ₁} , [b ₄] _E ∪ {b ₂}) , ({a ₂} , [b ₂] _E ∪ {b ₂}) , ({a ₂} , [b ₃] _E ∪ {b ₂}) , ({a ₃} , [b ₂] _E ∪ {b ₂})} = {({a ₁} , {b ₂}) , ({a ₁} , {b ₂, b ₃}) , ({a ₁} , {b ₂, b ₄}) , ({a ₂} , {b ₂}) , ({a ₂} , {b ₂, b ₃}) , ({a ₃} , {b ₂})}. Hence, using Definition 3.2, we obtain $\bar{R} (X_{2}, Y_{2})$ = ({a ₁, a ₂, a ₃} , ({b ₂} ∪ {b ₂, b ₃} ∪ {b ₂, b ₄}) ∩ ({b ₂} ∪ {b ₂, b ₃}) ∩ ({b ₂})) = ({a ₁, a ₂, a ₃} , {b ₂}) and $\underline{R} (X_{2}, Y_{2}) = ({a_{1}, a_{2}, a_{3}}, ({b_{2}} \cup \emptyset) \cap ({b_{2}} \cup \emptyset) \cap ({b_{2}})) = ({a_{1}, a_{2}, a_{3}}, {b_{2}})$ . This implies $\underline{R} (X_{2}, Y_{2}) = \bar{R} (X_{2}, Y_{2}) = (X_{2}, Y_{2})$ . So, by Theorem 3.1, we confirm (X ₂, Y ₂) ∈ ß (K ₁). In fact, using Definition 2.1 and $X_{2}^{'} = {a_{1}, a_{2}, a_{3}}^{'} = {b_{2}}$ , we also obtain (X ₂, Y ₂) ∈ ß (K ₁). Additionally, we see $(X_{2}, X_{2}^{'} \cap Y_{2}) = ({a_{1}, a_{2}, a_{3}}, {b_{2}}) = \underline{R} (X_{2}, Y_{2})$ and $(X_{2}, X_{2}^{'} \cup Y_{2}) = ({a_{1}, a_{2}, a_{3}}, {b_{2}}) = \bar{R} (X_{2}, Y_{2})$ .

Example 3.2 shows the correct of Theorem 3.1 and Lemma 3.2.

3.2 Approximation operators relative to lattice

By similar means of the discussion for double Boolean algebras for the set of ⊓-semiconcepts and ⊔-semiconcepts in Vormbrack and Wille [15], we will obtain the following results.

Theorem 3.2. Let K=(O, P, I) be a formal context and ß (K) be the set of all of semiconcepts in K. We define some operations on ß (K):

(1) (A ₁, B ₁) ⊑ (A ₂, B ₂) : ⇔ A ₁ ⊆ A ₂ and B ₁ ⊇ B ₂.

(2) (A ₁, B ₁) ∧ (A ₂, B ₂) : = (A ₁ ∩ A ₂, (A ₁ ∩ A ₂) ′) , (A ₁, B ₁) ∨ (A ₂, B ₂) : = (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′).

Then, (ß (K) , ⊑) is a poset and (ß (K) , ∨ , ∧) is a lattice.

Proof. According to Lemma 3.1, we infer ß (K)≠ ∅. Let (A _j, B _j) ∈ ß (K), (j=1,2,3). This means $A_{j}^{'} = B_{j} (j = 1, 2, 3)$ in view of Definition 2.1.

First, we will prove that (ß (K, ⊑) is a poset.

We may easily see A ₁ ⊆ A ₁ and B ₁ ⊇ B ₁ from A ₁ = A ₁ and B ₁ = B ₁. Thus, we can decide (A ₁, B ₁) ⊑ (A ₁, B ₁).

If (A ₁, B ₁) ⊑ (A ₂, B ₂) and (A ₂, B ₂) ⊑ (A ₁, B ₁). Then, we obtain A ₁ ⊆ A ₂ and B ₁ ⊇ B ₂ from (A ₁, B ₁) ⊑ (A ₂, B ₂), and meanwhile, we attain A ₂ ⊆ A ₁ and B ₂ ⊇ B ₁ from (A ₂, B ₂) ⊑ (A ₁, B ₁). Summarizing, we obtain A ₁ = A ₂ and B ₁ = B ₂. So, (A ₁, B ₁) = (A ₂, B ₂) holds.

If (A ₁, B ₁) ⊑ (A ₂, B ₂) and (A ₂, B ₂) ⊑ (A ₃, B ₃). Then, we obtain A ₁ ⊆ A ₂ and B ₁ ⊇ B ₂ from (A ₁, B ₁) ⊑ (A ₂, B ₂), and at the same time, we receive A ₂ ⊆ A ₃ and B ₂ ⊇ B ₃ from (A ₂, B ₂) ⊑ (A ₃, B ₃). Thus, we receive A ₁ ⊆ A ₂ ⊆ A ₃ and B ₁ ⊇ B ₂ ⊇ B ₃. This follows (A ₁, B ₁) ⊑ (A ₃, B ₃).

In one word, owing to Ganter and Wille [13,p.2], (ß (K) , ⊑) is a poset.

Second, we will prove that (ß (K) , ∨ , ∧) is a lattice.

We may easily know A ₁ ∩ A ₂ ⊆ A _j (j = 1, 2). From (A _j, B _j) ∈ ß (K) (j=1,2) and Definition 2.1, we attain $B_{j} = A_{j}^{'} (j = 1, 2)$ . Considering A ₁ ∩ A ₂ ⊆ A _j (j = 1, 2) and Lemma 2.1(1), we can say $(A_{1} \cap A_{2})^{'} \supseteq A_{j}^{'} (j = 1, 2)$ . That is to say, we receive (A ₁ ∩ A ₂) ′ ⊇ B _j since $B_{j} = A_{j}^{'} (j = 1, 2)$ . In addition, (A ₁ ∩ A ₂, (A ₁ ∩ A ₂) ′) ∈ ß (K) holds by Definition 2.1. Hence, we obtain (A ₁ ∩ A ₂, (A ₁ ∩ A ₂) ′) ⊑ (A _j, B _j) (j = 1, 2). Let (A ₁, B ₁) ⊑ (A ₃, B ₃) and (A ₂, B ₂) ⊑ (A ₃, B ₃). Then we receive A _j ⊆ A ₃ (j = 1, 2). This means A ₁ ∩ A ₂ ⊆ A ₃ since A ₁ ∩ A ₂ ⊆ A ₁ and A ₁ ⊆ A ₃. Combining Lemma 2.1(1) and Definition 2.1, we find $(A_{1} \cap A_{2})^{'} \supseteq A_{3}^{'} = B_{3}$ . So, we may be assured (A ₁ ∩ A ₂, (A ₁ ∩ A ₂) ′) ⊑ (A ₃, B ₃). Hence, (A ₁ ∩ A ₂, (A ₁ ∩ A ₂) ′) is the infimum of (A ₁, B ₁) and (A ₂, B ₂) in (ß (K, ⊑).

Using Lemma 2.1(2) and Definition 2.1, we infer to $(A_{1} \cup A_{2})^{'} = A_{1}^{'} \cap A_{2}^{'} = B_{1} \cap B_{2} \subseteq B_{j} (j = 1, 2)$ . In addition, we easily find A _j ⊆ A ₁ ∪ A ₂ (j = 1, 2). Thus, (A _j, B _j) ⊑ (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′) holds (j = 1, 2) in view of (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′) ∈ ß (K) and the above discussion. Let (A _j, B _j) ⊑ (A ₃, B ₃) (j = 1, 2). This means A _j ⊆ A ₃ and B _j ⊇ B ₃ (j = 1, 2). So, we obtain A ₁ ∪ A ₂ ⊆ A ₃ and B ₁ ∩ B ₂ ⊇ B ₃. From $B_{j} = A_{j}^{'} (j = 1, 2)$ and Lemma 2.1, we attain $(A_{1} \cup A_{2})^{'} = A_{1}^{'} \cap A_{2}^{'} = B_{1} \cap B_{2} \supseteq B_{3}$ . Hence, according to (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′) ∈ ß (K), we can indicate (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′) ⊑ (A ₃, B ₃). That is to say, (A ₁ ∪ A ₂, (A ₁ ∪ A ₂) ′) is the supremum of (A ₁, B ₁) and (A ₂, B ₂) in (ß (K) , ⊑).

Therefore, according to Ganter and Wille [13,p.5], we confirm that (ß (K) , ∨ , ∧) is a lattice.

Vormbrock and Wille [15] provided basic theorem on semiconcept algebra, which is a complete pure double Boolean algebra for the family of ⊓-semiconcepts and ⊔-semiconcepts. That is to say, the two operators of meet and join for the semiconcept algebra in [15] are defined for the set of ⊓-semiconcepts and ⊔-semiconcepts. Hence, it does not confirm that the set of ⊓-semiconcepts is closed for the two operators of meet and join for semiconcept algebra in [15]. Furthermore, Theorem 3.2 is necessary for ß (K) and different from the correspondent results in [15].

Yao [4] discussed the approximation operators for a finite Boolean algebra defined on one dimension. We are known that a finite Boolean algebra is a complete lattice and not vice versa. Theorem 3.2 shows that the lattice property of (ß (K) , ∨ , ∧). It is easy to see (ß (K) , ∨ , ∧) to be complete since |O|, |P|< ∞ though (ß (K) , ∨ , ∧) is perhaps not a Boolean algebra. Yao [4] also provided some approximation operators for a poset which is defined on one universal set, and did not consider the approximation operators defined on two non-related sets.

Yao [27] discussed some approximation operators for formal concept analysis. However, it dealt those approximation operators on extension set and intension set, respectively. Thus, we can state that those approximation operators in [27] are defined on one dimension set respectively.

Therefore, it is an essential duty for formal concept analysis to define approximation operators on two dimensions. Meanwhile, the new operators should keep the original characteristic that in one dimension such as that in [4,27, 4,27]. Since every concept is a semiconcept, we will consider the essential duty on the set of semiconcepts in a formal context. Based on these analysis, we can define the approximation operators for semiconcepts lattice (ß (K) , ∨ , ∧) on two dimensions analogously to the technique in Yao [4] and [27] as follows.

Definition 3.3. In a formal context K=(O, P, I), for X ⊆ O and Y ⊆ P, we define $\underline{apr} (X, Y) = \lor {(A, B) ∣ (A, B) \in ß (K), (A, B) \subseteq (X, Y)}$ and $\bar{apr} (X, Y) = \land {(C, D) ∣ (C, D) \in ß (K), (X, Y) \subseteq (C, D)}$ , where ∨, ∧ is defined in Theorem 3.2, respectively.

Let X ⊆ O and Y ⊆ P. We set $\underline{l} (X, Y) = {(A, B) ∣ (A, B) \in ß (K), (A, B) \subseteq (X, Y)}$ and $\bar{u} (X, Y) = {(C, D) ∣ (C, D) \in ß (K), (X, Y) \subseteq (C, D)}$ . We may easily find $\underline{apr} (X, Y) = ⋁ \underline{l} (X, Y)$ and $\bar{apr} (X, Y) = ⋀ \bar{u} (X, Y)$ , where ⋁, ⋀ is defined in Theorem 3.2 respectively.

The operators $\underline{apr}$ and $\bar{apr}$ in Definition 3.3 have the following properties:

Lemma 3.4. In a formal context K=(O, P, I), let (X, Y) ⊆ (O, P).

(1) If $\underline{l} (X, Y) = \emptyset$ , then $\underline{apr} (X, Y) = \lor \emptyset = (\emptyset, P)$ .

(2) If $\bar{u} (X, Y) = \emptyset$ , then $\bar{apr} (X, Y) = \land \emptyset = (O, \emptyset)$ .

(3) (∅ , P) ⊆ (X, Y) ⊆ (O, ∅) is not correct. That is, if $\underline{l} (X, Y) = \bar{u} (X, Y) = \emptyset$ , then $⋁ \underline{l} (X, Y) \subseteq (X, Y) \subseteq ⋀ \bar{u} (X, Y)$ is wrong.

(4) If $\underline{l} (X, Y) = \bar{u} (X, Y) = \emptyset$ , then $\underline{apr} (X, Y) \neq \bar{apr} (X, Y)$ holds, and (X, Y) ∈ ß (K) does not exist.

(5) If (X, Y) ∈ ß (K), then $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ .

(6) If $\underline{l} (X, Y) = \emptyset$ , then (X, Y) ∉ ß (K).

(7) If $\bar{u} (X, Y) = \emptyset$ , then (X, Y) ∉ ß (K).

Proof. To prove item (1) and item (2).

By Lemma 3.1, we find (∅ , P) , (O, ∅) ∈ ß (K).

Let (M, N) ∈ ß (K). Then we easily find ∅ ⊆ M and P ⊇ N. This means (∅ , P) ⊑ (M, N). In other words, (∅ , P) is the smallest element in (ß (K) , ⊑). Hence, we obtain the true of item (1).

Additionally, it is easy to see M ⊆ O and N⊇ ∅. This implies (M, N) ⊑ (O, ∅). That is to say, (O, ∅) is the greatest element in (ß (K) , ⊑). Hence, we confirm the correct of item (2).

To prove item (3).

If (∅ , P) ⊆ (X, Y). Then we obtain P ⊆ Y. According to Y ⊆ P, we receive Y = P. This means (X, Y) = (X, P). So, we determine (X, P) notsubseteq (O, ∅) since P≠ ∅ follows Pnotsubseteq∅. Hence, (∅ , P) ⊆ (X, Y) ⊆ (O, ∅) does not hold. Considered this result with items (1) and (2), we confirm $⋁ \underline{l} (X, Y) = (\emptyset, P) \subseteq (X, Y) \subseteq ⋀ \bar{u} (X, Y) = (O, \emptyset)$ not to be correct if $\underline{l} (X, Y) = \bar{u} (X, Y) = \emptyset$ . Therefore, we have demonstrated the correct of item (3).

To prove item (4).

From the above item (1) and $\underline{l} (X, Y) = \emptyset$ , we obtain $\underline{apr} (X, Y) = (\emptyset, P)$ . Combining item (2) and $\bar{u} (X, Y) = \emptyset$ , we obtain $\bar{apr} (X, Y) = (O, \emptyset)$ . Considering Definition 2.1, we believe O≠ ∅ and P≠ ∅. Summing up the above, we decide $\underline{apr} (X, Y) \neq \bar{apr} (X, Y)$ .

If (X, Y) ∈ ß (K). From (X, Y) ⊆ (X, Y), we obtain $(X, Y) \in \underline{l} (X, Y)$ and $(X, Y) \in \bar{u} (X, Y)$ . This is a contradiction to $\underline{l} (X, Y) = \emptyset = \bar{u} (X, Y)$ .

Therefore, item (4) is demonstrated.

To prove item (5).

According to (X, Y) ⊆ (X, Y) and (X, Y) ∈ ß (K), we obtain $(X, Y) \in \underline{l} (X, Y)$ and $(X, Y) \in \bar{u} (X, Y)$ . This means $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ .

To prove items (6) and (7).

When $\underline{l} (X, Y) = \emptyset$ (or $\bar{u} (X, Y) = \emptyset$ ). Then using item (5), we may easily confirm (X, Y) ∉ ß (K).

From Lemma 3.4, we can state that for any (X, Y) ⊆ (O, P), if we hope to characterize (X, Y) ∈ ß (K) with $\underline{apr}$ and $\bar{apr}$ , then there will be the following cases to happen:

(1) $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ ;

(2) $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) = \emptyset$ ;

(3) $\underline{l} (X, Y) = \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ .

The following example will show that for (X, Y) ⊆ (O, P), if $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) = \emptyset$ , or $\underline{l} (X, Y) = \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ , then we can not decide $\bar{apr} (X, Y) = \underline{apr} (X, Y)$ , and meanwhile, we can not demonstrate (X, Y) ∈ ß (K).

Example 3.3. Let the formal context K ₁ be defined in Example 3.1.

Let X ₁ = {a ₁, a ₂, a ₄} and Y ₁ = {b ₁, b ₄}. Combining Example 3.1, we can obtain $\bar{u} (X_{1}, Y_{1}) = \emptyset$ and $\underline{l} (X_{1}, Y_{1}) = {({a_{1}, a_{2}, a_{4}}, \emptyset)} \neq \emptyset$ . Using Lemma 3.4, we find $\bar{apr} (X_{1}, Y_{1}) = (O, \emptyset)$ . By Definition 3.3, we receive $\underline{apr} (X_{1}, Y_{1}) = ({a_{1}, a_{2}, a_{4}}, \emptyset)$ . Thus, we obtain $\underline{apr} (X_{1}, Y_{1}) \neq \bar{apr} (X_{1}, Y_{1})$ . In addition, (X ₁, Y ₁) ∉ ß (K ₁) holds owing to $X_{1}^{'} = \emptyset \neq Y_{1}$ and Definition 2.1.

Let X ₂ = {a ₁} and Y ₂ = {b ₂, b ₄}. From Example 3.1, we see $X_{2}^{'} = {b_{2}, b_{3}, b_{4}} Y_{2}$ . Considering 2^{X
₂} = {∅ , X ₂} and ∅′ = P ₁ = {b ₁, b ₂, b ₃, b ₄} notsubseteqY ₂ with the above, we obtain $\underline{l} (X_{2}, Y_{2}) = \emptyset$ . However, $(X_{2}, X_{2}^{'} = {b_{2}, b_{3}, b_{4}}) \in ß (K_{1})$ satisfies X ₂ ⊆ X ₂ and $Y_{2} \subseteq X_{2}^{'}$ . This means $\bar{u} (X_{2}, Y_{2}) \neq \emptyset$ . In fact, we may easily receive $\bar{apr} (X_{2}, Y_{2}) = ({a_{1}}, {b_{2}, b_{3}, b_{4}})$ . Using Lemma 3.4(1), we find $\underline{apr} (X_{2}, Y_{2}) = (\emptyset, {b_{1}, b_{2}, b_{3}, b_{4}})$ . Hence, we attain $\underline{apr} (X_{2}, Y_{2}) \neq \bar{apr} (X_{2}, Y_{2})$ . By Definition 2.1, we receive (X ₂, Y ₂) ∉ ß (K ₁).

Combining Lemma 3.4 and Example 3.3, we find that for (X, Y) ∈ (O, P), we only need to pay our attention to the case of $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ to determine (X, Y) ∈ ß (K).

Theorem 3.3. Let (X, Y) ⊆ (O, P) satisfy (X, Y) ∉ {(∅ , P) , (O, ∅)} in a formal context K=(O, P, I). If $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ , then the following statements are correct.

(1) $\underline{apr} (X, Y) \subseteq (X, Y) \subseteq \bar{apr} (X, Y)$ .

(2) $\underline{apr} (X, Y) = \bar{apr} (X, Y) \Leftrightarrow (X, Y) \in ß (K)$ .

Proof. To prove item (1).

Let $\underline{l} (X, Y) = {(A_{j}, B_{j}), j \in J}$ and $\bar{u} (X, Y) = {(C_{i}, D_{i}), i \in I}$ . Since $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ , we receive J and I. Then according to Definition 3.3, we may be assured (A, B) ⊆ (X, Y) ⊆ (C, D) for any $(A, B) \in \underline{l} (X, Y)$ and $(C, D) \in \bar{u} (X, Y)$ . This means A ⊆ X ⊆ C and B ⊆ Y ⊆ D.

Considering Theorem 3.2, Lemma 2.1 with Definition 2.1, we infer to $⋁_{(A, B) \in \underline{l} (X, Y)} (A, B) = (⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j},$ $(⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j})^{'}) = (⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j},$ $⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j}^{'}) =$ $(⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j}, ⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} B_{j})$ ⊆ (X, B _j) ⊆ (X, Y) since A _j ⊆ X (j ∈ J) follows $⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j} \subseteq X$ , and $⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} B_{j}$ ⊆B _j ⊆ Y (j ∈ J) follows $⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} B_{j} \subseteq Y$ . This means $\underline{apr} (X, Y) = ⋁ l (X, Y) \subseteq (X, Y)$ .

Combining Theorem 3.2, we obtain $⋀ \bar{u} (X, Y) = (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i}, (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i})^{'}) \subseteq$ $(C_{i}, (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i})^{'})$ for any i ∈ I. Using $⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i} \subseteq C_{i}$ for any i ∈ I and Lemma 2.1, we attain $C_{i}^{'} \subseteq (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i})^{'}$ . Additionally, in light of (C _i, D _i) ∈ ß (K) for any i ∈ I, we see $D_{i} = C_{i}^{'} \subseteq (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i})^{'}$ . Applying (X, Y) ⊆ (C _i, D _i) (i ∈ I), we obtain Y ⊆ D _i for any i ∈ I. Thus, we can indicate $Y \subseteq (⋂_{(C_{i}, D_{i}) \in \bar{u} (X, Y), i \in I} C_{i})^{'}$ . Owing to (X, Y) ⊆ (C _i, D _i) (i ∈ I), we infer to X ⊆ C _i (i ∈ I). Moreover, we find X ⊆ ⋂ _i∈I C _i. Taking the above and Definition 3.3 with Theorem 3.2, we can say $(X, Y) \subseteq ⋀ \bar{u} (X, Y) = \bar{apr} (X, Y)$ .

Therefore, we receive the item (1) to be correct.

To prove item (2).

(⇒) If $\underline{apr} (X, Y) = \bar{apr} (X, Y)$ .

Considering item (1) and the given, we decide $(X, Y) = \underline{apr} (X, Y)$ . In addition, using Theorem 3.2 and Definition 3.3, we confirm $\underline{apr} (X, Y) \in ß (K)$ . Hence, we attain (X, Y) ∈ ß (K).

(⇐) If (X, Y) ∈ ß (K).

According to Definition 3.3, we obtain $\underline{apr} (X, Y) = ⋁ \underline{l} (X, Y)$ . Taking with Theorem 3.2, we find $⋁ \underline{l} (X, Y) = (⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j},$ $(⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j})^{'})$ . Using Lemma 2.1, we will attain $⋁ \underline{l} (X, Y) =$ $(⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j}, ⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j}^{'})$ . Applying (A _j, B _j) ∈ ß (K) for any j ∈ J and Definition 2.1, we will confirm

$⋁ \underline{l} (X, Y) = (⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j},$ $⋂_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} B_{j})$ . Since (A _j, B _j) ⊆ (X, Y) holds for any $(A_{j}, B_{j}) \in \underline{l} (X, Y) (j \in J)$ , we obtain A _j ⊆ X for any j ∈ J. Hence, we infer to $⋃_{(A_{j}, B_{j}) \in \underline{l} (X, Y), j \in J} A_{j} \subseteq X$ . On the other hand, in light of (X, Y) ∈ ß (K) and (X, Y) ⊆ (X, Y), we obtain $(X, Y) \in \underline{l} (X, Y)$ . This implies A _{j
₀} = X for some j ₀ ∈ J. Furthermore, ⋃_j∈J A _j = X holds since A _j ⊆ X (j ∈ J). Considered (A _j, B _j) ∈ ß (K) (j ∈ J) and Theorem 3.2, we obtain $⋁ \underline{l} (X, Y) \in ß (K)$ . Thus, we attain $⋁ \underline{l} (X, Y) = (X, T) \in ß (K)$ . Taking (X, T) ∈ ß (K) and Definition 2.1, we know X′ = T. In view of (X, Y) ∈ ß (K) and the unique of X′ in K, we receive Y = X′ = T. Therefore, $\underline{apr} (X, Y) = ⋁ \underline{l} (X, Y) = (X, Y)$ holds.

By the definition of $\bar{u} (X, Y)$ , we can express (X, Y) ⊆ (C _i, D _i) (i ∈ I). This implies X ⊆ C _i and Y ⊆ D _i (i ∈ I). So, X ⊆ ⋂ _i∈I C _i holds. On the other hand, according to (X, Y) ∈ ß (K) and (X, Y) ⊆ (X, Y), we may be assured $(X, Y) \in \bar{u} (X, Y)$ . Thus, in light of Definition 3.3, we obtain $\bar{apr} (X, Y) = ⋀ \bar{u} (X, Y) ⊑ (X, Y)$ . Furthermore, taking Theorem 3.2, we receive ⋂_i∈I C _i ⊆ X. Combining X ⊆ ⋂ _i∈I C _i and ⋂_i∈I C _i ⊆ X, we attain X = ⋂ _i∈I C _i. So, X′ = (⋂ _i∈I C _i) ′ holds. Thus, we can say Y = (⋂ _i∈I C _i) ′ since (X, Y) ∈ ß (K) follows X′ = Y. Therefore, using Theorem 3.2, we obtain $\bar{apr} (X, Y) = ⋀ \bar{u} (X, Y) = (⋂_{i \in I} C_{i}, (⋂_{i \in I} C_{i})^{'}) = (X, Y)$ .

Summing up the above, we can express $\underline{apr} (X, Y) = \bar{apr} (X, Y)$ .

Actually, from the proof in Theorem 3.3, we may easily obtain the following result.

Corollary 3.1. If $\underline{l} (X, Y) \neq \emptyset$ and $\bar{u} (X, Y) \neq \emptyset$ . Then $\underline{apr} (X$ ,Y)= $\bar{apr}$ (X,Y)=(X,Y)⇔(X,Y)∈ ß(K).

Theorem 3.3, Corollary 3.1 and Lemma 3.4 taken together implies that for any (X, Y) ⊆ (O, P), $\underline{apr} (X, Y) = ⋁ \underline{l} (X, Y)$ and $\bar{apr} (X, Y) = ⋀ \bar{u} (X, Y)$ carry out the works (p2) and (p3). In other words, $\underline{apr}$ and $\bar{apr}$ are the extension of Pawlak rough set approximations on two non-related universal sets for a formal context with the family of semiconcepts. Hence, we can call $\underline{apr}$ and $\bar{apr}$ a lower approximation operator and an upper approximation operator, respectively.

Example 3.4. Let K ₁ be described in Example 3.1.

Let X ₃ = {a ₁, a ₂} and Y ₃ = {b ₂, b ₃}. Then there are $\underline{l} (X_{3}, Y_{3}) = {(a_{2}, {b_{2}, b_{3}}), ({a_{1}, a_{2}}, {b_{2}, b_{3}})}$ and $\bar{u} (X_{3}, Y_{3}) = {({a_{1}, a_{2}}, {b_{2}, b_{3}})}$ . So, we obtain $\underline{apr} (X_{3}, Y_{3}) = ⋁ \underline{l} (X_{3}, Y_{3}) = ({a_{1}, a_{2}}, {b_{2}, b_{3}})$ and $\bar{apr} (X_{3}, Y_{3}) = ⋀ \bar{u} (X_{3}, Y_{3}) = ({a_{1}, a_{2}}, {b_{2}, b_{3}})$ . Hence, $\underline{apr} (X_{3}, Y_{3}) = \bar{apr} (X_{3}, Y_{3}) = (X_{3}, Y_{3})$ holds. This follows (X ₃, Y ₃) ∈ ß (K ₁) according to Theorem 3.3.

In fact, using Definition 2.1, we obtain (X ₃, Y ₃) ∈ ß (K ₁) since $X_{3}^{'} = Y_{3}$ .

Example 3.4 shows the correct of Theorem 3.3 and Corollary 3.1.

4. Conclusion

In a formal context K=(O, P, I), we use two methods to define the approximations for the known knowledge ß (K). One of the two methods is the extension of Pawlak’s standard model from one set to two non-related sets (e.g. O and P). Another method is defined with the help of lattice theory. The two pairs of approximation operators provided here basically satisfy the properties of Pawlak rough set approximations, respectively, that is, for any (X, Y) ⊆ (O, P):

(1) the lower approximation of (X, Y)⊆ (X, Y) ⊆ the upper approximation of (X, Y);

(2) the lower approximation of (X, Y) equals to the upper approximation of (X, Y) if and only if (X, Y) ∈ ß (K).

Therefore, we can state that the approximation methods provided in this paper for a formal context are the generalizations of Pawlak’s correspondent idea from one set to two non-related sets with respect to the family of semiconcepts. We hope that our methods here can give a thinking to generalize rough set from one universal set to two or more than two non-related universal sets in the future. These will be done in our future works.

Footnotes

Acknowledgement

This research was supported by National Natural Science Foundation of China [grant number 61572011] and Natural Science Foundation of Hebei University [grant number A2018201117]. The author is grateful to Professor Y.Y. Yao for giving some discussions to semiconcepts during the author’s visiting at University of Regina in 2017.

References

Pawlak , Rough sets, International Journal of Computer and Information Sciences 11 (1982), 341–356.

Pawlak , Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.

V.W.

Marek , Characterizing Pawlak’s approximation operators, In: Peters,

J.F.

Skowron,

Marek,

V.W.

Orlowska,

Slowinski

Ziarko

(Eds.), Transactions on Rough Sets VII, Springer Berlin, Heidelberg, 7, 2007, pp. 140–150.

Y.Y.

Yao , On generalizing Pawlak approximation operators, In: Polkowski,

Skowron,

(Eds.), Rough Sets and Current Trends in Computing, Proceedings ofthe First International Conference, RSCTC’98, LNAI1424,1998, pp. 298–307.

E.A.

Marei , Rough set approximations on a semi bitopolog-ical view, International Journal of Scientific and Innovative Mathematical Research 3(12) (2015), 59–70.

F.F.

Xu ,

Y.Y.

Yao and

D.Q.

Miao , Rough set approximations in formal concept analysis and knowledge spaces, In: An,

et al. (Eds.), ISMIS 2008, LNAI 4994, Springer-Verlag Berlin, Heidelberg, 2008, pp. 319–328.

Y.Y.

Yao , Relational interpretations of neighborhood operators and rough set approximation operators, Information Sciences 111(1-4) (1998), 239–259.

Y.Y.

Yao , The two sides of the theory of rough sets, Knowledge-Based Systems 80 (2015), 67–77.

Pawlak and

Skowron , Rough sets: Some extensions, Information Sciences 177(1) (2007), 28–40.

10.

Qian ,

Liang ,

Pedrycz and

Dang , Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intellignece 174 (2010), 597–618.

11.

H.M.

Abu-Donia , New rough set approximation spaces, Abstract and Applied Analysis 2013 (2013), 7. Article ID 189208.

12.

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

In: (Eds.), Ordered Sets, Reidel, Dordrecht, 1982, pp. 445–470.

13.

Ganter and

Wille , Formal Concept Analysis, Mathematical Foundations, Springer-Verlag Berlin, Heidelberg, 1999.

14.

Vormbrock , Complete subalgebras of semiconcept algebras and protoconcept algebras, Ganter,

Godin,

In: (Eds.), ICFCA 2005, LNAI 3403, Springer-Verlag Berlin, Heidelberg, 2005, pp. 329–343.

15.

Vormbrock and

Wille , Semiconcept and protoconcept algebras: The basic theorems, Ganter,

In: et al. (Eds.) Formal Concept Analysis, LNAI 3626, SpringerVerlag Berlin, Heidelberg, 2005, pp. 34–48.

16.

Luksch and

Wille , A mathematical model for conceptual knowledge systems, Bock,

H.H.

and Ihm,

In: (Eds.) Classification, Data Analysis, and Knowledge Organisation, Springer-Verlag Berlin, Heidelberg, 1991, pp. 156–162.

17.

Pollandt , Relational constructions on semiconcept graphs, http://ceur-ws.org/Vol-41/Pollandt.pdf

18.

Klinger , Simple semiconcept graphs: A Boolean logic approach, In: Delugach,

and Stumme,

(Eds.), ICCS 2001, LNAI 2120, Springer-Verlag Berlin, Heidelberg, 2001, pp. 101–114.

19.

Klinger , Semiconcept graphs with variables, In: U.

Priss,

Corbett

and G.

Angelova

(Eds.), ICCS2002, LNAI2393, Springer-Verlag Berlin, Heidelberg, 2002, pp. 369–381.

20.

Malik , An extension of the theory of information flow to semiconcept and protoconcept graphs, In: Wolff,

K.E.

et al. (Eds.), ICCS2004, LNAI3I27, Springer-Verlag Berlin, Heidelberg, 2004, pp. 213–226.

21.

Balbiani , Deciding the word problem in pure double Boolean algebras, Journal of Applied Logic 19 (2012), 260–273.

22.

S.K.M.

Wong ,

L.S.

Wang and

Y.Y.

Yao , Interval structure: A frame work for representing uncertain information, Dubois,

Wellman,

M.P.

In: (Eds.), Proceedings of the Eighth Annual Conference on Uncertainty in Artificial Intelligence, 1992, pp. 336–343.

23.

G.L.

Liu , Rough set theory based on two universal sets and its applications, Knowledge-Based Systems 23 (2010), 110–115.

24.

Safari and

Hooshmandasl , On twelve types of covering-based rough sets, Springer Plus 5 (2016), 1003.

25.

Mao and

Kang , Variable precision rough set approximations in concept lattice, Journal of Progressive Research in Mathematics 2(1) (2015), 47–56.

26.

Ziarko , Variable precision rough set model, Journal of Computer and System Sciences 46 (1993), 39–59.

27.

Y.Y.

Yao , Rough set approximations: A concept analysis point of view, In: Ishibuchi,

(Eds.), Computational Intelligence—Volume I, Eycyclopedia of Life Support Systems (EOLSS), Abu Dhabi, U.A.E., 2015, pp. 282–296.

Approximation operators for semiconcepts

Abstract

Keywords

1. Introduction

2. Some notations and lemmas

3. Generalized approximation operators

3.1 Approximation operators relevant to an equivalence relation

Table 1 Guest House Hotel First Class Luxus Kempinski × × × Hilton × × Ibis × ISSY ×

4. Conclusion

Footnotes

Acknowledgement

References

Table 1

Guest House Hotel First Class Luxus

Kempinski × × ×

Hilton × ×

Ibis ×

ISSY ×