Attribute Reduction in Soft Contexts Based on Soft Sets and Its Application to Formal Contexts

Abstract

We introduce the notion of the reduct of soft contexts, which is a special notion of a consistent set for soft contexts. Then, we study its properties and show that this notion is well explained by the two classes, $1^0$ and $2^0$, of independent attributes. In particular, we describe in detail how to extract a reduct from a given consistent set. Then, based on this extraction process, we propose a six-step method for constructing a reduct from a given consistent set. Additionally, to apply this method to formal contexts, we examine the relationship between the reducts of a given formal context and the reducts of the associated soft context. We finally illustrate the process of obtaining reducts in a formal context using this relationship and the six-step method using an example.

1. Introduction

Formal Concept Analysis (FCA) [1] was introduced by Wille in 1982, which is a theory that was designed to study the hierarchical structure induced by a binary relationship between objects and attributes. Basically, the FCA consists of three notions: formal contexts, formal concepts, and formal concept lattices. A formal context is a kind of information system that expresses object–attribute value relationships in a tabular form [2,3,4,5]. The formal concept consists of expansion and tension. The former is the set of all objects belonging to a given concept and the latter is the set of all attributes that are valid for all of those objects. The set of all formal concepts with the order relation is a lattice, called a formal concept lattice [1,5]; it is a complete lattice. Until recently, the FCA consisting of the three concepts described above has been widely applied in many areas and its notion has been extended to various applications [6,7,8,9,10,11]. In particular, Guo et al. introduced the six types of lifting on a relationally enriched context and the notion of power contexts [11]. Various types of research related to FCA are being actively conducted to solve the problems necessary for the practical applications of the FCA in the real world [5,12,13,14,15,16,17,18,19,20,21]. Other studies on knowledge reduction have been actively conducted in information systems as well as in FCA [13,22,23,24,25,26,27,28].

The attribute reduction in the formal context aims to find a minimal subset of attributes that preserves the structure of formal concept lattice constructed by the given original attributes. Ganter and Wille [3] first introduced the notions of reducible attributes and reducible objects in a formal context. They also introduced the notions of clarification and reduction induced by any process of removal duplicate attributes and reducible attributes. Various methods for the attribute reduction for the formal context are currently actively being studied for applications in the classical formal context as well as in the generalized formal context: Zhang et al. [29] introduced the discernibility matrix and function of a concept lattice and presented how to obtain the attribute reduction in concept lattice by the discernibility matrix. Qi [30] proposed a method based on a new discernibility matrix for the reduction of concept lattices in formal contexts and showed that all the reducts of a formal context are constructed by the new discernibility matrix. Kumar et al. [31] investigated the knowledge reduction in FCA and proposed a method based on non-negative matrix factorization (NMF). Liu et al. [7] proposed a novel approach using the CUR matrix decomposition technique, which decomposes the original context in terms of dimensionally reduced low-rank matrices of actual columns and rows. Recently, Konecny et al. [32] theoretically compared the original method proposed by Ganter and Wille with the discrimination matrix method. In some cases, the original method is superior to the discriminant matrix method.

Various methods other than the method using the discrimination matrix have been studied [33,34,35,36,37,38]. Wu et al. [39] investigated a new reduction in a formal context in terms of object granulation as did many researchers in this field [15,19,21,27,40,41]. Particularly, Chen et al. [33] studied the granular reduction in formal contexts using a framework based on graph theory. Another current area of active study of attribute reduction is the reduction for formal decision contexts with decision attributes [9,14,42,43,44,45,46,47].

As seen above, attribute reduction in the formal context is an important issue in formal conceptual analysis and is a necessary tool for discovering knowledge in the formal context. However, in the formal context, most reduction methods are complex to execute and compute. To overcome these problems, we propose a new attribute reduction method using the soft set defined by a set-valued mapping for formal contexts in this paper.

In 1999, Molodtsov [48] introduced the soft set defined by a set-valued mapping as follows: Let U be an initial universe set consisting of objects, A a collection of properties of objects in U, and $P\left(U\right)$ the set of all subsets of U. Then a pair $(F,A)$ is called a soft set over U if F is a set-valued mapping from A into $P\left(U\right)$. Soft sets are useful concepts that deal with complex problems and uncertainties that arise in various fields such as social problems, information science, economics, and medical science. Maji et al. [49] introduced some basic operators for soft set theory similar to traditional set theory such as equality, subset, superset, complement, empty set, etc. To address the uncertainty more effectively, Ali et al. [50] proposed new operations that modified some of the concepts defined by Maji.

In 2019, to efficiently deal with FCA using soft set theory, we combined the notion of soft sets with FCA and introduced soft contexts, soft concepts, and soft concept lattices [51]. These concepts are specifically related to formal contexts, formal concepts, and formal concept lattices. It is also well-known that an associated soft context is always induced by a given formal context. From this, we found the following meaningful relationship between a given formal context and the associated soft context: (1) there is a bijective mapping between the set of all formal concepts in a formal context and the set of all soft concepts in the associated soft context, and (2) the formal concept lattice of a formal context is order-isomorphic to the soft concept lattice of the associated soft context.

To more easily deal with consistent sets of a formal context, we [52] studied the notion of consistent sets and independent attributes in a soft context. We also introduced two classes $1^0$ and $2^0$ of independent attributes and showed that all consistent sets must include the class $1^0$.

In this work, we studied the notion of the reduct of soft contexts and investigated its properties, which is a special notion of a consistent set of soft contexts. First, we define the notion of reduct of soft contexts and show that the reduct can be described by the two classes, $1^0$ and $2^0$, of independent attributes. In detail, we describe how to extract a reduct from a given consistent set using its properties. The purpose of this detailed description is to find a new method of constructing a reduct from a consistent set of soft context. Based on the detailed description, we propose a six-step method for constructing a reduct from a given consistent set. In order to apply this method to formal context, we examine the relationship between the reducts of a given formal context and the reducts of the associated soft context, and reveal the following: D is a reduct of a given formal context if and only if D is a reduct of the associated soft context. Finally, we illustrate the process of obtaining reducts in a formal context using the information above using an example.

This paper is organized as follows: Section 2 reviews some basic notions related to FCA, soft sets, and soft contexts. In Section 3, we first review basic notions related to the consistent sets of a soft context. Then, we introduce the notion of reducts and study its properties. In this section, we propose the six-step method for constructing a reduct from a given consistent set of a soft context. Section 4 shows the relationship between reducts of a given formal context and the reducts of the associated soft context, and how to apply the six-step method in the formal context. In addition, we illustrate the process of obtaining reducts in a formal context using the six-step method using an example. Finally, the conclusion is provided in Section 5.

2. Preliminaries

We briefly review several notions and terminology related to FCA, soft set, and soft context used throughout the paper. First, we recall that the notions and notations introduced in [1,3,5]. Let U be a finite set of objects, A a finite set of attributes or properties, and let $I\subseteq U\times A$ be a relation from U to A. Then, the triplet $(U,A,I)$ is called a formal context. In a formal context $(U,A,I)$, if $(x,a)\in I$, we simply write $xIa$ and say that x has the property a, or a is possessed by object x. $x\in U$ and $a\in A$ is denoted by: $x^{*}=\{a\in A|xIa\};a^{*}=\{x\in U|xIa\}.$

For $X\subseteq U$, $X^{*}$ is the maximal set of attributes shared by all objects in X, denoted as:

$X^{*}=\{a\in A|\forall x\in X,xIa\};$

for $B\subseteq A$, $B^{*}$ is the maximal set of objects that all have attributes in B, denoted as:

$B^{*}=\{x\in U|\forall b\in B,xIb\}.$

Let $P\left(U\right)$ and $P\left(A\right)$ be the power sets of U and A, respectively. Let us consider operators $\mathcal{E},\mathcal{I}$ between $P\left(U\right)$ and $P\left(A\right)$ as follows:

$\mathcal{E}:P\left(U\right)\to P\left(A\right),\mathcal{E}\left(X\right)=X^{*}$; $\mathcal{I}:P\left(A\right)\to P\left(U\right),\mathcal{I}\left(B\right)=B^{*}$.

Then, $(\mathcal{E},\mathcal{I})$ is a contravariant Galois connection between $P\left(U\right)$ and $P\left(A\right)$.

For $X\in P\left(U\right)$ and $B\in P\left(A\right)$, a pair $(X,B)$ is called a formal concept of a context $(U,A,I)$ if $X=B^{*}$ and $B=X^{*}$. Then X is called the extension of the formal concept $(X,B)$, and B is called the intension of the formal concept $(X,B)$.

For a formal context $(U,A,I)$, the order between two formal concepts of $(U,A,I)$ is defined as follows: For two concepts $(X,B),(Y,C)$,

$$(X,B)\le (Y,C)\iff X\subseteq Y(\iff C\subseteq B).$$

The ordered set of all formal concepts in $(U,A,I)$ is a complete lattice. The ordered set is denoted by $L(U,A,I)$ and is called the formal concept lattice of $(U,A,I)$.

For the notion of soft set, let U be an initial universe set and E be a collection of all possible properties of objects in U.

A pair $(F,A)$ is called a soft set [48] over U if $F:A\to P\left(U\right)$ is a set-valued mapping defined by $F\left(a\right)\in P\left(U\right)$ for $a\in A$. A soft set $(F,A)$ is called pure [53] if it satisfies ${\cap }_{a\in A}F\left(a\right)=\varnothing$, ${\cup }_{a\in A^{\prime }}F\left(a\right)=U^{\prime }$, $F\left(a\right)\ne U$ and $F\left(a\right)\ne \varnothing$ for every $a\in A$. In this paper, we assume that every soft set is pure and $\left|X\right|$ is the cardinal number of X for a set X.

In Author et al. [51], we combined the notion of soft sets with FCA and investigated soft contexts, soft concepts, soft concept lattices, and so on. Now, we recall the related notions introduced in [51].

Let $U=\{x_1,x_2,\cdots ,x_n\}$ be a finite set of objects, $A=\{a_1,a_2,\cdots ,a_m\}$ be a finite set of attributes, and $(F,A)$ be a soft set. Then, the triple $(U,A,F)$ is called a soft context. For $D\subseteq A$, define a set-valued mapping ${F|}_D:D\to P\left(U\right)$ by ${F|}_D\left(d\right)=F\left(d\right)$ for each $d\in D$. Then, $(F{|}_D,D)$ is also a soft set, so $(U,D,F{|}_D)$ becomes a soft context. For a soft context $(U,A,F)$,

(1)

${\mathbf{F}}^{+}:P\left(A\right)\to P\left(U\right)$ is an operator defined as ${\mathbf{F}}^{+}\left(B\right)={\cap }_{b\in B}F\left(b\right)$;

(2)

${\mathbf{F}}^{-}:P\left(U\right)\to P\left(A\right)$ is an operator defined as ${\mathbf{F}}^{-}\left(X\right)=\{a\in A:X\subseteq F\left(a\right)\}$.

(3)

$\Psi :P\left(U\right)\to P\left(U\right)$ is an operator defined as $\Psi \left(X\right)={\mathbf{F}}^{+}{\mathbf{F}}^{-}\left(X\right)$ for $X\in P\left(U\right)$.

Now X is called a soft concept in $(U,A,F)$ if $\Psi \left(X\right)={\mathbf{F}}^{+}{\mathbf{F}}^{-}\left(X\right)=X$. We denote the set of all soft concepts by $sC(U,A,F)$.

Let us define an order between $X,Y\in sC(U,A,F)$ as follows: For $X,Y\in sC(U,A,F)$, $X\precsim Y$ if and only if $X\subseteq Y$.

In the ordered set $\left(sC\right(U,A,F),\precsim )$, ∧ and ∨ are defined as follows:

$$X\wedge Y=X\cap Y;X\vee Y=\Psi (X\cup Y)=F^{+}{F}^{-}(X\cup Y).$$

Then, $\left(sC\right(U,A,F),\precsim ,\wedge ,\vee )$ is a complete lattice. The ordered set $\left(sC\right(U,A,F),\precsim ,\wedge ,\vee )$ is called the soft concept lattice and denoted by $sL(U,A,F)$.

For two soft concept lattices $sL(U,A,F_A)$ and $sL(U,B,F_B)$, $sL(U,A,F_A)$ is said to be finer than $sL(U,B,F_B)$ if $sC(U,B,F_B)\subseteq sC(U,A,F_A)$, which is denoted by $sL(U,A,F_A)\le sL(U,B,F_B)$. If $sL(U,A,F_A)\le sL(U,B,F_B)$ and $sL(U,B,F_B)\le sL(U,A,F_A)$, then they are said to be isomorphic to each other, and denoted by $sL(U,A,F_A)\cong sL(U,B,F_B).$

For any soft concept $X\in sC(U,A,F)$,

(1)

X is said to be dependent on $sC(U,A,F)$ if there exists $X_1,\cdots ,X_n\in sC(U,A,F)$ satisfying $X⊊X_i$ and $X=\cap X_i$, $i=1,\cdots ,n$ ($n\geqq 2$). We denote $sD=\{X\in sC(U,A,F)\mid X\mathrm{as}\mathrm{dependent}\mathrm{on}sC(U,A,F\left)\right\}.$

(2)

X is said to be independent of $sC(U,A,F)$ if X is not dependent. $sI=\{X\in sC(U,A,F)\mid X\mathrm{is}\mathrm{independent}\mathrm{of}sC(U,A,F\left)\right\}.$

For $X\in sD$, there is $B\subseteq A)$ such that ${\mathbf{F}}^{+}\left(B\right)={\cap }_{b\in B}F\left(b\right)=X$ for $b\in B$ and $X⊊F\left(b\right)$.

3. Reducts on Soft Contexts

For a given soft context, a reduct is a special notion induced from a consistent set. So, we first recall some notions and basic properties related to consistent sets for a soft context $(U,A,F)$ investigated in [52].

For $C\subseteq A$, C is called a consistent set of $(U,A,F)$ if $sC(U,A,F)=sC(U,C,F{|}_C)$. A subfamily $\mathcal{S}$ of $sC(U,A,F)$ is called a base for $sC(U,A,F)$ if, for each $X\in sC(U,A,F)$, there exists ${\mathcal{S}}^{\prime }\subseteq \mathcal{S}$ such that $X=\cap {\mathcal{S}}^{\prime }$. Then, ${\mathcal{F}}_A=\{F\left(a\right)\mid a\in A\}$ is a base for $sC(U,A,F)$.

Put $G_a=\{g\in A\mid F\left(a\right)⊊F\left(g\right)\}$ for $a\in A$. Then $d\in A$ is said to be dependent on A if there is $G_d\ne \varnothing$ such that $F\left(d\right)={\mathbf{F}}^{+}\left(G_d\right)={\cap }_{g\in G_d}F\left(g\right)$. We denote $A_D=\{a\in A\mid a\mathrm{as}\mathrm{dependent}\mathrm{on}A\}$. Otherwise, we say that d is independent on A and denote $A_I=\{a\in A\mid a\mathrm{is}\mathrm{independent}\mathrm{on}A\}.$ Then d is dependent on A if and only if there exists $B\subseteq A$ such that for $b\in B$, $F\left(d\right)⊊F\left(b\right)$ and ${\cap }_{b\in B}F\left(b\right)=F\left(d\right)$.

For $A_I\subseteq A$, let $n\left(a\right)=\left|\right\{b\in A_I\mid F\left(a\right)=F\left(b\right)\left\}\right|$. We define the two sets $1^{\circ }\left(A\right),2^{\circ }\left(A\right)$ as follows: $1^{\circ }\left(A\right)=\{a\in A_I\mid n\left(a\right)=1\}$ and $2^{\circ }\left(A\right)=\{a\in A_I\mid n\left(a\right)>1\}$.

Theorem 1

([52]). For a soft context $(U,A,F)$ and $C\subseteq A$, the following holds:

(1)

C is a consistent set of $(U,A,F)$ if and only if $\mathcal{C}=\left\{F\right(d)\mid d\in C\}$ is a base of $sC(U,A,F)$.

(2)

If a mapping $\phi :C\to sI$ defined as $\phi \left(c\right)=F\left(c\right)$ for $c\in C$ is surjective, then C is a consistent set.

(3)

Every consistent set C has to contain $1^{\circ }\left(A\right)$.

Definition 1.

[Reduct] For a soft context $(U,A,F)$, let C be a consistent set of $(U,A,F)$. If $sC(U,A,F)\ne sC(U,C-\left\{d\right\},F_{C-\left\{d\right\}})$ for each $d\in C$, then the consistent set C is called a reduct of $(U,A,F)$.

Example 1.

For $U=\{1,2,3,4\}$ and $A=\{a,b,c,d,e,f\}$, let us consider a soft set $(F,A)$ defined as:

$$F\left(a\right)=F\left(b\right)=\{1,2,4\};F\left(c\right)=\{2,3,4\};F\left(d\right)=F\left(f\right)=\{1,3\};F\left(e\right)=\{2,4\}.$$

Then $(U,A,F)$ is a soft context. We can easily find the set $sC(U,A,F)$ of all soft concepts as follows:

$sC(U,A,F)$=$\left\{{\cap }_{b\in B}F\left(b\right)\right|B\subseteq A\}$=$\{\varnothing ,\{1\},\{3\},\{1,3\},\{2,4\},\{1,2,4\},\{2,3,4\},U\}$.

For $D=\{b,c,d\}$, $sC(U,D,F_D)$=$\left\{{\cap }_{b\in B}F\left(b\right)\right|B\subseteq D\}$=$\{\varnothing ,\{1\},\{3\},\{1,3\},\{2,4\},\{1,2,4\},\{2,3,4\},U\}$. So, D is a consistent set of $(U,A,F)$ and it is also easy to see that D is a reduct.

Naturally, there is the question of whether there are always reducts for every soft context. To solve this question, we first look at the following theorem:

Theorem 2.

Every consistent set of a soft context can be reduced to a reduct.

Proof. 

For a soft context $(U,A,F)$, suppose that a consistent set C cannot be reduced to a reduct of $(U,A,F)$ and $\left|C\right|=m\ne 0$. Then by hypothesis, there is some $c\in C$ (say, $c=c_1$) such that $sC(U,A,F)=sC(U,C-\left\{c_1\right\},F_{C-\left\{c_1\right\}})$ and $C-\left\{c_1\right\}$ is a consistent set but not a reduct. Next, we can choose $c_2\in C-\left\{c_1\right\}$ satisfying $sC(U,A,F)=sC(U,C-\{c_1,c_2\},F_{C-\{c_1,c_2\}})$, and $C-\{c_1,c_2\}$ is a consistent set but not a reduct. Repeating the above process, we obtain: $sC(U,A,F)=sC(U,C-\{c_1,c_2,\cdots ,c_{m-1}\},F_{C-\{c_1,c_2,\cdots ,c_{m-1}\}})$. Finally, we can choose $c_m\in C-\{c_1,c_2,\cdots ,c_{m-1}\}$ such that $sC(U,A,F)=sC(U,\varnothing ,F_{\varnothing })$. However, since the soft set $(F,A)$ is pure, i.e., $F\left(a\right)\ne \varnothing$ for every $a\in A$, it is impossible. So, every consistent set must be reduced to a nonempty reduct. □

Example 2.

In Example 1, let us consider $C=\{b,c,d,e\}\subseteq A$. Then, $sC(U,C,F_C)=\{\varnothing ,\left\{1\right\},\left\{3\right\},\{1,3\},\{2,4\},\{1,2,4\},\{2,3,4\},U\}$, and so C is a consistent set of $(U,A,F)$. However, for $e\in C$, since $C-\left\{e\right\}=\{b,c,d,e\}-\left\{e\right\}=D$ and $sC(U,C-\left\{e\right\},F_{C-\left\{e\right\}})=sC(U,D,F_D)=sC(U,A,F)$, C is not a reduct. However, we can see that C is reduced to a reduct D.

For any soft context $(U,A,F)$, ${\mathcal{F}}_A=\{F\left(a\right)\mid a\in A\}$ is a base for $(U,A,F)$, so A is obviously a consistent set. From this, and Theorem 2, we obtain the following theorem:

Theorem 3.

There is at least one reduct for any soft context.

Lemma 1.

For a soft context $(U,A,F)$ and $C\subseteq A$, if C is a consistent and $C\subseteq A_I$, then there exists a surjective mapping $\phi :C\to sI$ defined by $\phi \left(c\right)=F\left(c\right)$ for $c\in C$.

Proof. 

Let us define a mapping $\phi :C\to sI$ as follows: $\phi \left(c\right)=F\left(c\right)$ for $c\in C$. Then, since C is a consistent, $\phi \left(C\right)=\left\{F\right(c\left)\right|c\in C\}$ is a base and $\mathcal{C}\subseteq sI$. Since $sI$ is the smallest base (see Theorem 3.24 in [36]), $\mathcal{C}=sI$, so $\phi$ is surjective. □

In Lemma 1, the condition $C\subseteq A_I$ is necessary as shown in the next example. We remind the reader that:

(1)

$X\in sD$ if and only if there is $D\subseteq A$ such that ${\cap }_{d\in D}F\left(d\right)=X⊊F\left(d\right)$ for $d\in D$ [51].

(2)

$a\in A_D$ if and only if there is $D\subseteq A$ such that for $d\in D$, $F\left(a\right)⊊F\left(d\right)$ and ${\cap }_{d\in D}F\left(b\right)=F\left(a\right)$ [52].

(3)

$sI=sC(U,A,F)-sD$; $A_I=A-A_D$.

Example 3.

For a soft context $(U,A,F)$ in Example 1, $A_D=\left\{e\right\}$ and $s_D=\{\varnothing ,\left\{1\right\},\left\{3\right\},\{2,4\},U\}$. So, we find that $A_I=\{a,b,c,d,f\}$ and $s_I=\{\{1,3\},\{1,2,4\},$$\{2,3,4\}\}$. For a consistent set $C=\{b,c,d,e\}$, $C⊈A_I$, and it is impossible that a mapping $\phi :C\to s_I$ is well defined as follows $\phi \left(c\right)=F\left(c\right)$ for $c\in C$. So, the condition $C\subseteq A_I$ is necessary.

Theorem 4

([52]). Let $(U,A,F)$ be a soft context and $C\subseteq A$. Let C be a consistent set of $(U,A,F)$. Then, $e\in 1^{\circ }\left(C\right)$ if and only if $C-\left\{e\right\}$ is not a consistent set of $(U,A,F)$.

Theorem 5.

[Equivalence conditions of reducts] Let $(U,A,F)$ be a soft context. For a consistent set C of $(U,A,F)$, the following things are equivalent:

(1)

C is a reduct of $(U,A,F)$.

(2)

For each $c\in C$, $C-\left\{c\right\}$ is not consistent set of $(U,A,F)$.

(3)

$C=1^{\circ }\left(C\right)$.

(4)

The mapping $\phi :C\to sI$ defined by $\phi \left(d\right)=F\left(d\right)$ for $d\in C$ is bijective.

Proof. 

(1) ⇔ (2) Obvious.

(2) ⇔ (3) It follows from by Theorem 4.

(3) ⇒ (4) Let $C\subseteq A$ be a consistent set of $(U,A,F)$ and $C=1^{\circ }\left(C\right)\subseteq A_I$. Then, by Lemma 1, there exists a surjective mapping $\phi :C\to sI$ defined as $\phi \left(d\right)=F\left(d\right)$ for $d\in C$. For $c,d\in C$, if $c\ne d$, then from $1^{\circ }\left(C\right)=C$, we obtai $F\left(c\right)\ne F\left(d\right)$. Hence, $\phi$ is injective.

(4) ⇒ (3) Suppose that the mapping $\phi :C\to sI$ defined as $\phi \left(d\right)=F\left(d\right)$ for $d\in C$ is bijective. First, since $\phi$ is surjective, C is a consistent set of $(U,A,F)$. Second, since $\phi$ is injective, for each $a\in C$, there is no element $b\in C-\left\{a\right\}$ such that $F\left(a\right)=F\left(b\right)$. It implies $n\left(a\right)=1$ and $a\in 1^{\circ }\left(C\right)$. Consequently, $C=1^{\circ }\left(C\right)$. □

In Author et al. [52], we showed that $A_I\subseteq A$ is a consistent set of a soft context $(U,A,F)$. From this, we obtain:

Corollary 1.

Let $(U,A,F)$ be a soft context and $C\subseteq A$. If C is a consistent set, then $C_I$ is also a consistent set of $(U,A,F)$.

Proof. 

By hypothesis, $sC(U,A,F)=sC(U,C,F_C)$. Additionally, since $C_I\subseteq C$ is a consistent set of $(U,C,F_C)$, we obtain the relation $sC(U,A,F)=sC(U,C,F_C)=sC(U,C_I,F_{C_I})$. Consequently, $C_I$ is also a consistent set of $(U,A,F)$. □

We showed in Theorem 2 that every consistent set can be reduced to a nonempty reduct. Based on this, we introduce a method of extracting a reduct from a given consistent set in the following theorem.

Theorem 6.

[Construction of Reduct] Let $(U,A,F)$ be a soft context. For a consistent set C, we can always construct a reduced reduct from C.

Proof. 

First, using Corollary 1, we take a consistent set $C_I$, which is smaller than C. Then, if $2^{\circ }\left(C_I\right)=\varnothing$, from $C_I=1^{\circ }\left(C_I\right)$ and Theorem 5, $C_I$ is a reduct. If $2^{\circ }\left(C_I\right)\ne \varnothing$, then $|2^{\circ }\left(C_I\right)|=m\ge 2$. Now, for $x,y\in 2^{\circ }\left(C_I\right)$, we can define a relation $x\sim y$ on $2^{\circ }\left(C_I\right)$ as follows: $x\sim y$ if and only if $F\left(x\right)=F\left(y\right)$. Then, the relation “∼” is an equivalence relation on $2^{\circ }\left(C_I\right)$. Put $\left[x\right]=\{y\in 2^{\circ }\left(C_I\right)\mid F\left(x\right)=F\left(y\right)\mathrm{for}x\in 2^{\circ }\left(C_I\right)\}$. Then the set $\mathcal{M}=\{\left[x_i\right]\mid x_i\in 2^{\circ }\left(C_I\right),i=1,2,\cdots ,k(k<m)\}$ becomes a partition of $2^{\circ }\left(C_I\right)$. Now, put $\mathbf{M}=\{m_i\mid m_i\mathrm{is}\mathrm{one}\mathrm{element}\mathrm{chosen}\mathrm{in}\left[x_i\right]\in \mathcal{M}\mathrm{for}\mathrm{each}i=1,2,\cdots ,k\}$ and $E=1^{\circ }\left(C_I\right)\cup \mathbf{M}$. Then, $n\left(m_i\right)=1$ for every $m_i\in \mathbf{M}$, which implies that $E=1^{\circ }\left(E\right)\subseteq C_I$.

Now, to apply Theorem 5, we show that E is a consistent set of $(U,A,F)$. For a consistent set $C_I$, by Lemma 1, the mapping $\phi :C_I\to sI$ defined as $\phi \left(d\right)=F\left(d\right)$ is surjective. Let us define a mapping ${\phi }^{\prime }:E\to sI$ by ${\phi }^{\prime }\left(e\right)=\phi \left(e\right)$ for each $e\in E$. For $X\in sI$, there exists $c\in C_I=1^{\circ }\left(C_I\right)\cup 2^{\circ }\left(C_I\right)$ such that $\phi \left(c\right)=F\left(c\right)$. If $c\in 1^{\circ }\left(C_I\right)$, then $c\in E$, and so ${\phi }^{\prime }\left(c\right)=\phi \left(c\right)=F\left(c\right)=X$. If $c\in 2^{\circ }\left(C_I\right)$, since $\mathcal{M}$ is a partition of $2^{\circ }\left(C_I\right)$, there exists an equivalent class $\left[x_i\right]$ in $\mathcal{M}$ such that $c\in \left[x_i\right]$ and $1\le i\le k$. By the property of the set $\mathbf{M}$, there exists one element $m_i$ in $\mathbf{M}$ such that $F\left(m_i\right)=F\left(x_i\right)=F\left(c\right)$. So, for $m_i\in \mathbf{M}\subseteq E$, ${\phi }^{\prime }\left(m_i\right)=\phi \left(m_i\right)=F\left(m_i\right)=F\left(c\right)=X$. Hence, ${\phi }^{\prime }$ is surjective, and by Theorem 1, E is a consistent set of $(U,A,F)$. Finally, from $E=1^{\circ }\left(E\right)$ and (3) of Theorem 5, E is a reduct. □

Using Theorem 6, to obtain the attribute reduct of a soft context $(U,A,F)$, we adopt a six-step attribute reduction method for the set $sC(U,A,F)$ as follows. At this point, the following two properties are useful: (1) $a\in A_D$ if and only if there exists $B\subseteq A$ such that for $b\in B$, $F\left(a\right)⊊F\left(b\right)$ and ${\cap }_{b\in B}F\left(b\right)=F\left(a\right)$; (2) $A_I=A-A_D$.

Remark 1.

[Attribute Reduction Method of Soft Contexts ] Let $(U,A,F)$ be a soft context.

Step 1:

Find the set-valued map $F:A\to P\left(U\right)$.

Step 2:

Find $A_I$.

Step 3:

Find $1^{\circ }\left(A\right)$ and $2^{\circ }\left(A\right)$ using $A_I$.

Step 4:

Find the partition $\mathcal{M}$ on $2^{\circ }\left(A\right)$ as follows:

$\mathcal{M}=\{\left[x_i\right]\mid x_i\in 2^{\circ }\left(A\right),i=1,2,\cdots ,k(k<|2^{\circ }\left(A\right)\left|\right\}$ where an equivalence class

$\left[x_i\right]=\{y\mid F\left(x\right)=F\left(y\right)\mathrm{for}y\in 2^{\circ }\left(A\right)\}$.

Step 5:

Construct a set $\mathbf{M}$ as follows:

$\mathbf{M}=\{m_i\mid m_i\mathrm{is}\mathrm{one}\mathrm{element}\mathrm{chosen}\mathrm{in}\left[x_i\right]\in \mathcal{M}\mathrm{for}\mathrm{each}i=1,2,\cdots ,k\}$.

Finally, by Theorem 6, we can construct a reduct D.

Step 6:

Construct a reduct $D=1^{\circ }\left(A\right)\cup \mathbf{M}$.

Example 4.

For $U=\{1,2,3,4\}$ and $A=\{a,b,c,d,e,f\}$, let us consider a soft context $(U,A,F)$ as Example 1. Now, we try to obtain a reduct of the soft context $(U,A,F)$ using the six-step method mentioned above.

Step 1:

From Example 1, we know that $F:A\to P\left(U\right)$ is a set-valued mapping defined as follows:

$$F\left(a\right)=F\left(b\right)=\{1,2,4\};F\left(c\right)=\{2,3,4\};F\left(d\right)=F\left(f\right)=\{1,3\};F\left(e\right)=\{2,4\}.$$

Step 2:

For $e\in A$, $F\left(e\right)⫅F\left(a\right)\left(F\right(b),F(c)$) and $F\left(e\right)=F\left(a\right)\cap F\left(b\right)\cap F\left(c\right)$. So, $A_D=\left\{e\right\}.$ From $A_I=A-A_D$,

$$A_I=\{a,b,c,d,f\}.$$

Step 3:

For $A_I$, note that: $n\left(a\right)=n\left(b\right)=2$; $n\left(c\right)=1$; $n\left(d\right)=n\left(f\right)=2$. So,

$$1^{\circ }\left(A\right)=\left\{c\right\};2^{\circ }\left(A\right)=\{a,b,d,f\}.$$

Step 4:

On $2^{\circ }\left(A\right)$,

$\mathcal{M}=\{\left[x_i\right]\mid x_i\in 2^{\circ }\left(A\right),i=1,2,3,4\}=\{\left[a\right],\left[d\right]\}$, where $\left[a\right]=\{a,b\}$, $\left[d\right]=\{d,f\}$.

Step 5:

Put $\mathbf{M}=\{a,d\}$; where a is one element chosen in $\left[a\right]=\{a,b\}\in \mathcal{M}$ and d is one element chosen in $\left[d\right]=\{d,f\}\in \mathcal{M}$.

Step 6:

Finally, $D=1^{\circ }\left(A\right)\cup \mathbf{M}=1^{\circ }\left(A\right)\cup \{a,d\}=\{a,c,d\}$ is a reduct.

In the same way, we obtain all reducts:

$D_1=1^{\circ }\left(A\right)\cup \{a,d\};$

$D_2=1^{\circ }\left(A\right)\cup \{a,f\};$

$D_3=1^{\circ }\left(A\right)\cup \{b,d\};$

$D_4=1^{\circ }\left(A\right)\cup \{b,f\}.$

4. Application to the Formal Context

In this section, we show how to apply the six-step method in the formal context. First, we examine the relationship between the reducts of a given formal context and the reducts of the associated soft context. Then the process of obtaining reducts in a formal context is illustrated using an example.

For a formal context $(U,A,I)$, the associated soft context $(U,A,F_I)$ [51] is induced by the formal context $(U,A,I)$, where the soft set $(F_I,A)$ is induced by a mapping $F_I:A\to P\left(U\right)$ defined as $F_I\left(a\right)=\{x\in U:(x,a)\in I\}$.

For a formal context and the associated soft context, we obtained the following meaningful properties:

Theorem 7.

Let $(U,A,I)$ be a formal context. Then,

(1)

the formal concept lattice $L(U,A,I)$ is order-isomorphic to the associated soft concept lattice $sL(U,A,F_I)$ [51];

(2)

$L(U,A,I)=\left\{(X,{\mathbf{F}}^{-}\left(X\right))\right|X\mathrm{is}\mathrm{any}\mathrm{element}\mathrm{of}sC(U,A,F)\}$ [51];

(3)

C is a consistent of a formal context $(U,A,I)$ if and only if C is a consistent set of the associated soft context $(U,A,F_I)$ [52].

In a way similar to (3) in Theorem 7, we reveal the relationship between the reduct defined in a formal context and the reduct defined in a soft context. For this discussion, we first recall the following notions and basic properties:

For a formal context $(U,A,I)$ and a consistent set D of $(U,A,I)$, D is called a reduct [18] of $(U,A,I)$ if $L(U,A,I)\ncong L(U,D-\left\{d\right\},I_{D-\left\{d\right\}})$ for every $d\in D$.

For a soft context $(U,A,F)$, let $sL(U,A,F_A)$ and $sL(U,B,F_B)$ be soft concept lattices. $sL(U,A,F_A)$ is said to be finer [51] than $sL(U,B,F_B)$ if $sC(U,B,F_B)\subseteq sC(U,A,F_A)$, which is denoted by $sL(U,A,F_A)\le sL(U,B,F_B)$. If $sL(U,A,F_A)\le sL(U,B,F_B)$ and $sL(U,B,F_B)\le sL(U,A,F_A)$, then these two soft concept lattices are said to be isomorphic to each other, and denoted by $sL(U,A,F_A)\cong sL(U,B,F_B).$

$sL(U,A,F_A)\cong sL(U,B,F_B)$ if and only if $sC(U,A,F_A)=sC(U,B,F_B)$.

Theorem 8.

For a formal context $(U,A,I)$, C is a reduct of $(U,A,I)$ if and only if C is a reduct of the associated soft context $(U,A,F_I)$.

Proof. 

Let C be a reduct of a formal context $(U,A,I)$. Then, since C is a consistent set of $(U,A,I)$, by Theorem 7, C is also a consistent set of the associated soft context $(U,A,F_I)$. Now, suppose that C is not a reduct of $(U,A,F_I)$. Then, by Theorem 10, there is $c\in C$ such that $C-\left\{c\right\}$ is a consistent set of $(U,A,F_I)$, so, $sC(U,A,F_I)=sC(U,C,F_{I_C})=sC(U,C-\left\{c\right\},F_{I_{C-\left\{c\right\}}})$. From this and Theorem 7, it follows that $sC(U,A,F_I)=sC(U,C-\left\{c\right\},F_{I_{C-\left\{c\right\}}})$ if and only if $sL(U,A,F_I)\cong sL(U,C-\left\{c\right\},F_{I_{C-\left\{c\right\}}})$ if and only if $L(U,A,I)\cong L(U,C-\left\{c\right\},I_{C-\left\{c\right\}})$. Eventually, we obtain that $L(U,A,I)\cong L(U,C-\left\{c\right\},I_{C-\left\{c\right\}})$. However, this contradicts C being a reduct of a formal context $(U,A,I)$. Therefore, C is also a reduct of $(U,A,F_I)$.

Similarly, we can prove the converse. □

In the following example, we describe the process of obtaining a reduct of a formula concept lattice using Theorems 7 and 8.

Example 5.

For $U=\{1,2,3,4,5\}$ and $A=\{a,b,c,d,e,f,g,h,k\}$, let

Table 1. A formal context.

-	a	b	c	d	e	f	g	h	k
1	1	1	0	1	1	1	1	0	1
2	0	1	1	0	0	0	0	1	0
3	1	0	0	1	1	0	0	0	1
4	0	1	1	0	0	0	0	0	0
5	1	1	0	1	0	1	1	0	0

be a formal context $(U,A,I)$. We sometimes write $xyz$ instead of a set $\{x,y,z\}$.

First, let us find the formal concept lattice $L(U,A,I)$ using the method proposed in [51]. For the method, let us define a set-valued mapping $F_I:A\to P\left(U\right)$ by $F_I\left(a\right)=\{x\in U|xIa\}$ for the formal context $(U,A,I)$. Then $(F_I,A)$ is a soft set and $(U,A,F_I)$ is the associated soft context. We simply write the mapping $F_I$ as F.

Now, from the associated soft context $(U,A,F)$, we have the following:

(1) $F\left(a\right)=F\left(d\right)=135;F\left(b\right)=1245;F\left(c\right)=24;$$F\left(e\right)=F\left(k\right)=13;F\left(f\right)=F\left(g\right)=15;F\left(h\right)=2.$

(2) ${\mathcal{F}}_A=\left\{F\left(a\right)\right|a\in A\}=\{2,13,15,24,135,1245\}$.

(3) $sC(U,A,F)=\{\cap \mathbf{S}|\mathbf{S}\subseteq {\mathcal{F}}_A\}=\{\varnothing ,1,2,13,15,24,135,1245,U\}$.

(4) For $X\in sC(U,A,F)$, from ${\mathbf{F}}^{-}\left(X\right)=\{a\in A|X⊊F\left(a\right).\}$,

${\mathbf{F}}^{-}(\varnothing )=A,{\mathbf{F}}^{-}\left(1\right)=abdefgk,{\mathbf{F}}^{-}\left(2\right)=bch,{\mathbf{F}}^{-}\left(13\right)=adek,{\mathbf{F}}^{-}\left(15\right)=abdfg,$

${\mathbf{F}}^{-}\left(24\right)=bc,{\mathbf{F}}^{-}\left(135\right)=ad,{\mathbf{F}}^{-}\left(1245\right)=b,{\mathbf{F}}^{-}\left(U\right)=\varnothing .$

From the above and Theorem 7, we obtain the formal concept lattice $L(U,A,I)$, which is shown in the following diagram:

$(U,\varnothing )$

$\nearrow \nwarrow$

$(1245,b)(135,ad)$

$\uparrow \nwarrow \nearrow \nwarrow$

$(24,bc)(15,abdfg)(13,adek)$

$\uparrow \nwarrow \nearrow$

$(2,bch)(1,abdefgk)$

$\nwarrow \nearrow$

$(\varnothing ,A)$

$L(U,A,I)$

Secondly, using the six-step method presented in Remark 1, let us obtain the reducts of the associated soft context $(U,A,F)$.

Step 1:

From the above in (1),

$F\left(a\right)=F\left(d\right)=135;F\left(b\right)=1245;F\left(c\right)=24;$

$F\left(e\right)=F\left(k\right)=13;F\left(f\right)=F\left(g\right)=15;F\left(h\right)=2.$

Step 2:

For $f,g\in A$, $F\left(f\right)=F\left(g\right)⫋F\left(a\right)\left(F\right(d),F(b\left)\right)$ and $F\left(f\right)=F\left(g\right)=F\left(a\right)\cap F\left(d\right)\cap F\left(b\right)$, and $A_D=fg$. Thus, $A_I=A-A_D=abcdehk$.

Step 3:

For $A_I$, $n\left(b\right)=n\left(c\right)=n\left(h\right)=1$ and $n\left(a\right)=n\left(d\right)=n\left(e\right)=n\left(k\right)=2$.

Thus, $1^{\circ }\left(A\right)=bch;2^{\circ }\left(A\right)=adek.$

Step 4:

On $2^{\circ }\left(A\right)$, the partition $\mathcal{M}=\left\{\right[a],[e\left]\right\}$, where $\left[a\right]=\{a,d\}$ and $\left[e\right]=\{e,k\}$.

Step 5:

Now, we can choose one element a in the class $\left[a\right]$ and one element k in the class $\left[e\right]$.

Thus, the set $\mathbf{M}=\{a,k\}$.

Step 6:

Finally, we obtain a reduct $D=1^{\circ }\left(A\right)\cup \mathbf{M}=\{b,c,h\}\cup \{a,k\}=\{a,b,c,h,k\}$.

Similarly, we obtain all reducts of the associated soft context:

$D_1=1^{\circ }\left(A\right)\cup \{a,k\};$

$D_2=1^{\circ }\left(A\right)\cup \{a,e\};$

$D_3=1^{\circ }\left(A\right)\cup \{d,e\};$

$D_4=1^{\circ }\left(A\right)\cup \{d,k\}.$

Consequently, by Theorem 8, the above four reducts are also reducts of the formal concept lattice $L(U,A,I)$.

Finally, for a reduct $D=\{a,b,c,h,k\}$, we explain how to construct $L(U,D,I_D)$ using the following theorem:

Theorem 9

([24]). Let $(U,A,I)$ be a formal context and $D\subseteq A$. Then,

$L(U,D,I_D)=\left\{(X,{{\mathbf{F}}_{I_D}}^{-}\left(X\right))\right|X\mathit{is}\mathit{any}\mathit{element}\mathit{of}sC(U,D,F_{I_D})\}$.

Let us first check the three statements below:

(1)

${{\mathbf{F}}_{I_D}}^{-}\left(X\right)={{\mathbf{F}|}_D}^{-}\left(X\right)\}$ where ${F|}_D:D\to P\left(U\right)$.

(2)

${{\mathbf{F}|}_D}^{-}\left(X\right)={\mathbf{F}}^{-}\left(X\right)\cap D$ [36].

(3)

For a reduct D, $sC(U,D,F_{I_D})=sC(U,A,F).$

From the three statements above, for $X\in sC(U,A,F)$, we can find the pair $(X,{{\mathbf{F}|}_D}^{-}\left(X\right))$ from the following:

${{\mathbf{F}|}_D}^{-}\left(U\right)={\mathbf{F}}^{-}\left(U\right)\cap D=\varnothing \cap D=\varnothing ;$

${{\mathbf{F}|}_D}^{-}(\varnothing )={\mathbf{F}}^{-}(\varnothing )\cap D=A\cap D=D;$

${{\mathbf{F}|}_D}^{-}\left(1\right)={\mathbf{F}}^{-}\left(1\right)\cap D=abdefgk\cap D=abk;$

${{\mathbf{F}|}_D}^{-}\left(2\right)={\mathbf{F}}^{-}\left(2\right)\cap D=bch\cap D=bch;$

${{\mathbf{F}|}_D}^{-}\left(13\right)={\mathbf{F}}^{-}\left(13\right)\cap D=adek\cap D=ak;$

${{\mathbf{F}|}_D}^{-}\left(15\right)={\mathbf{F}}^{-}\left(15\right)\cap D=abdfg\cap D=ab;$

${{\mathbf{F}|}_D}^{-}\left(24\right)={\mathbf{F}}^{-}\left(24\right)\cap D=bc\cap D=bc;$

${{\mathbf{F}|}_D}^{-}\left(135\right)={\mathbf{F}}^{-}\left(135\right)\cap D=ad\cap D=a;$

${{\mathbf{F}|}_D}^{-}\left(1245\right)={\mathbf{F}}^{-}\left(1245\right)\cap D=b\cap D=b.$

Thus, $L(U,D,I_D)$=$\left\{\right(\varnothing ,D),(1,abk),(2,bch),(13,ak),(15,ab),(24,bc),(135,a),(1245,b),(U,\varnothing \left)\right\}$ and the next diagram is obtained:

$\begin{array}{ccc}A=\{a,b,c,d,e,f,g,h,k\}& \supseteq & D=\{a,b,c,h,k\}\\ \hfill (U,\varnothing )\hfill & \hfill \hfill & \hfill (U,\varnothing )\hfill \\ \hfill \nearrow \nwarrow \hfill & \hfill \hfill & \hfill \nearrow \nwarrow \hfill \\ \hfill (1245,b)(135,ad)\hfill & \hfill \hfill & \hfill (1245,b)(135,a)\hfill \\ \hfill \uparrow \nwarrow \nearrow \nwarrow \hfill & \hfill \hfill & \hfill \uparrow \nwarrow \nearrow \nwarrow \hfill \\ \hfill (24,bc)(15,abdfg)(13,adek)\hfill & \hfill \cong \hfill & \hfill (24,bc)(15,ab)(13,ak)\hfill \\ \hfill \uparrow \nwarrow \nearrow \hfill & \hfill \hfill & \hfill \uparrow \nwarrow \nearrow \hfill \\ \hfill (2,bch)(1,abdefgk)\hfill & \hfill \hfill & \hfill (2,bch)(1,abk)\hfill \\ \hfill \nwarrow \nearrow \hfill & \hfill \hfill & \hfill \nwarrow \nearrow \hfill \\ \hfill (\varnothing ,A)\hfill & \hfill \hfill & \hfill (\varnothing ,D)\hfill \\ \hfill L(U,A,I)\hfill & \hfill \cong \hfill & \hfill L(U,D,I_D)\hfill \end{array}$

5. Conclusions

We investigated the notion of reduct of a soft context and the new method of constructing reducts using independent attributes containing the class $1^0$. Using these results, we applied the method of constructing reducts in soft contexts to the attribute reduction of formal context.

In the next study, we will study the various characteristics of reducts and the criteria for determining reducts. In particular, we will focus on applying these results to attribute reduction for formal contexts, data analysis, and knowledge discovery.