Attribute reduction in intuitionistic fuzzy formal concepts

Abstract

Knowledge acquisition in intuitionistic fuzzy information systems is of importance because those fuzzy information systems are often encountered in many real-life problems. Formal concept analysis is a simple and effective tool for knowledge acquisition. However, there is still little work on introducing knowledge acquisition methods based on formal concept analysis into intuitionistic fuzzy information systems. This paper mainly extends the formal concept theory into intuitionistic fuzzy information systems. Firstly, two pairs of adjoint mappings are defined in intuitionistic fuzzy formal contexts. It is verified that both pairs of adjoint mappings form Galois connections. Secondly, two types of intuitionistic fuzzy concept lattices are constructed. After that, we also present the main theorems and propositions of the intuitionistic fuzzy concept lattices. Thirdly, we deeply discuss the attribute characteristics for type-1 generalized one-sided intuitionistic fuzzy concept lattice. Furthermore, a discernibility matrix-based algorithm is proposed for attribute reduction and the effectiveness of this algorithm is demonstrated by a practical example. The construction of intuitionistic fuzzy conceptS is meaningful for the complex and fuzzy information in real life.

Keywords

Formal concept analysis attribute reduction galois connection intuitionistic fuzzy formal context

1 Introduction

Formal concept analysis (short for FCA), as an effective and simple tool for knowledge acquisition and data analysis, was first initiated by Wille in 1982 [1]. The fundamental issue in FCA is to acquire formal concepts from the discussed formal context. According to a hierarchical order, these formal concepts form a complete lattice (also called concept lattice). The complete lattice is usually expressed by a Hasse diagram, which vividly and succinctly embodies the relationship between those formal concepts. Over the past three decades, FCA has drawn more attention, many scholars have done a lot of research works on the theory and application of FCA. Now it has been successfully applied in machine learning [2], knowledge acquisition [3], data mining [4] and many other disciplines [5].

In the classical FCA theory, a formal context is always expressed by a triple (G, M, I), where G and M are nonempty, finite object and attribute sets, respectively. I ⊆ G × M is a crisp binary relation, and is usually expressed as “1” or “0” (depending on whether the object has the attribute). This is also denoted as a one-valued context. However, with the further research of FCA, many scholars [6] have found this theory is too restrictive for many real-life problems. In other words, most of the attributes are many-valued or fuzzy-valued between 0 and 1. In such circumstances, many extended models have been proposed, among which fuzzy FCA theory is the most popular one introduced by Burusco and Fuentes-Gonzáles [7]. By considering complete residuated lattice, Belohlavek [8] developed a fuzzy logical framework for FCA. Inspired by Belohlavek’s work, Georgescu and Popescu [9] further extended the fuzzy logic framework by the view of non-commutative logic. Recently, many efforts [10, 11] are still attempting to extend FCA to fuzzy formal contexts. Jaoua and Elloumi [12] constructed the corresponding Galois connection to generalize FCA to a real binary relation. Yahia et al. [13] generalized the FCA and proposed a so-called one-sided fuzzy concept. In order to handle various truth-value structures of attributes, Halaš and Pócs [14] put forward the generalized one-sided formal concept.

Attribute reduction is both important for rough sets and formal concept analysis. Ferone [15] introduced a new attribute reduction approach based on attribute granulation. In order to meet the requirement of complex problems, Li et al. [16] defined a multi-objective attribute reduction method. To minimize various types of costs, Fang and Min [17] proposed the cost-sensitive approximate attribute reduction method. According to attribute dependency calculated by direct dependency calculation, Raza and Qamar [18] presented a rough set-based attribute reduction method. On the other hand, with the increasing of attributes and objects, the concept lattice will become larger and larger, and its computation will become more and more complex. Many scholars [19 –21] have made great efforts to develop new approaches for attribute reduction with different purposes. For instance, by the view of object granule, Wu et al. [22] proposed a method to acquire attribute reduction in formal contexts. In order to reduce the size of the concept lattice, Kumar and Srinivas [23] presented a K-means clustering-based approach. To keep the maximum rules unchanged, Shao [24] introduced a model to acquire attribute reduction in fuzzy formal decision contexts. Based on the notion of congruence on lattices, Aragón and Medina [25] introduced a special kind of equivalence relation to reduce concept lattices. In [26], Wang proposed four kinds of attribute reduction of SE-ISI concept lattices based on different criteria. On the other hand, to maintain lattice structure unchanged, many attribute reduction approaches have been proposed [27]. However, calculating all reducts based on the Boolean approach is still an NP-hard [28]. Based on graph theory, Chen et al. [29] designed an approximation algorithm for obtaining a minimum reduct in formal decision contexts, which avoided generating all the formal concepts.

No matter the classical or fuzzy formal context, the acquisition of information is often a single aspect. However, in the process of cognition, people tend to show positive, negative, and hesitant results. Intuitionistic fuzzy (short for IF) set [30] is a natural generalization of the fuzzy set. The membership and the non-membership are adopted to express the ambiguities of the real world. Recently, the combination of IF set theory and rough set theory has been studied intensively. Those works mainly focused on model extension [31], property discussion [32] and measure description [33, 34]. Meantime, the study on the relationship between FCA theory and rough set theory has attracted the attention of many researchers [35]. Those studies show that both FCA theory and rough set theory have common goals and methodologies. Both theories provide formal tools for representing and acquiring knowledge from similar types of information systems (or formal contexts) [36]. One of the emerging problems in the usage of concept lattices is connected to make a rational decision. The information data corresponding to these real-life multi-attribute decision-making problems are usually represented as fuzzy (or intuitionistic fuzzy) attribute sets. IF sets and FCA are two important ways of data mining and knowledge representation in the real world. In recent years, some scholars have tried to combine IF sets and FCA together to generalize the concept lattice models. According to the attribute correlation degree, Xin and Song [37] proposed an IF three-way formal concept analysis model. Based on the intuitionistic fuzzy lattice implication algebra, Zhou and Lin [38] proposed linguistic-valued intuitionistic fuzzy layer concept lattice. Using dominance relation, Hong and Hong [39] turned the intuitionistic fuzzy information systems into 0-1 formal contexts and then get the formal concept lattices in the IF information systems. In essence, this method is still classical formal concept analysis. Using Intuitionistic L-fuzzy Sets, Kridlo and Ojeda-Aciego [40] extended formal concept analysis. However, to construct a Galois connection, the IF formal context has to provide values without indetermination.

The main contribution of this paper is to present a way to combine the IF theory and FCA theory. We then formulate an approach to acquire attribute reduction from the obtained IF concept lattice. Finally, we apply the proposed method to the multi-attribute decision-making problems. The remainder paper is organized as follows. Section 2 briefly reviews some basic definitions and notions in this study. In Section 3, we propose two types of IF concept lattices. Some related theorems and propositions have been also checked. Section 4 deeply discusses attribute characteristics for type-1 generalized one-sided IF concept lattice. After that, an algorithm is formulated to compute the attribute reduction for type-1 generalized one-sided IF concept lattice. At last, we conclude this paper and give an outlook for further work in Section 5.

2 Preliminaries

This section briefly recalls the preliminary notions and concepts, such as FCA, Galois connections, and generalized one-sided concept lattice.

2.1 FCA and Galois connections

A formal context is known as a triple K = (G, M, I), where G = {x₁, x₂, ⋯ , x_n} and M = {a₁, a₂, ⋯ , a_m} are nonempty finite sets of objects and attributes, respectively. I ⊆ G × M, if (x, a) ∈ I, we say that the object x holds the attribute a.

Definition 1 [1]. Let K = (G, M, I) be a formal context. For object subset $X \in P (G)$ and attribute subset $A \in P (M)$ , we define two mappings $* : P (G) \to P (M)$ and $* : P (M) \to P (G)$ as following:

X^∗ = {a ∈ M : ∀ x ∈ X, (x, a) ∈ I},

A^★ = {x ∈ G : ∀ a ∈ A, (x, a) ∈ I},

where $P (G)$ and $P (M)$ represent the power sets of object and attribute, respectively.

If X^∗ = A and A^★ = X, then the pair (X, A) is referred to as a formal concept of K = (G, M, I).

All formal concepts of K = (G, M, I) form a complete lattice (or concept lattice) with the partial order ≤, which is defined as:

(X₁, A₁) ≤ (X₂, A₂) ⇔ X₁ ⊆ X₂ (A₂ ⊆ A₁).

The complete lattice is denoted by B (G, M, I), and the infimum (∧) and the supremum (∨) for any two formal concepts are calculated by:

(X₁, A₁) ∧ (X₂, A₂) = (X₁ ∩ X₂, (A₁ ∪ A₂) ^★∗);

(X₁, A₁) ∨ (X₂, A₂) = ((X₁ ∪ X₂) ^∗★, A₁ ∩ A₂).

In fact, the pair of operators (∗ , ★) forms a Galois connection between the power sets of object and attribute. The original use of the Galois connections [41] was to express transformations that reverse (rather than preserve) order in symmetric but contravariant form. Wille studied the Galois connection and introduced formal concepts and concept lattices. Inspired by Wille, Belohlavek [42] and Pollandt [43] defined a pair of fuzzy derivation operators in residuated lattice and formal fuzzy context, and developed the notion of formal fuzzy concept and fuzzy concept lattice. Later, another type of operators framework of conceptual structures was proposed by addressing the objectives of knowledge processing, which form an isotone Galois connection. Gediga and Düntsch [44] put forward a new type of concept lattice called the attribute-oriented concept lattice by the isotone Galois connection. Yao [45] defined the notion of object-oriented concept lattice in a similar way. Now we recall the basic definitions of Galois connection and isotone Galois connection, respectively.

Definition 2 [46]. Consider posets (P, ≤) and (Q, ≤). If φ : P → Q and φ : Q → P are functions such that for all p ∈ P and all q ∈ Q,

p ≤ φ (q) ⇔ q ≤ φ (p),

then (φ, φ) is called an Galois connection between (P, ≤) and (Q, ≤).

Proposition 1 [46]. Let (P, ≤) and (Q, ≤) be two order sets. A pair (φ, φ) is an antitione Galois connection between the two ordered sets (P, ≤) and (Q, ≤). For all p ∈ P and all q ∈ Q, we have:

(1) p₁ ≤ p₂ ⇒ φ (p₁) ≥ φ (p₂);

(2) q₁ ≤ q₂ ⇒ φ (q₁) ≥ φ (q₂);

(3) p ≤ φ (φ (p)) and q ≤ φ (φ (q)).

Definition 3 [47]. Consider posets (P, ≤) and (Q, ≤). If φ : P → Q and φ : Q → P are functions such that for all p ∈ P and all q ∈ Q,

p ≤ φ (q) ⇔ φ (p) ≤ q,

then (φ, φ) is called an isotone Galois connection between (P, ≤) and (Q, ≤).

Proposition 2 [47]. Let (P, ≤) and (Q, ≤) be two order sets. A pair (φ, φ) is an isotone Galois connection between the two ordered sets (P, ≤) and (Q, ≤). For all p ∈ P and all q ∈ Q, we have:

(1) p₁ ≤ p₂ ⇒ φ (p₁) ≤ φ (p₂);

(2) q₁ ≤ q₂ ⇒ φ (q₁) ≤ φ (q₂);

(3) p ≤ φ (φ (p)) and q ≥ φ (φ (q)).

An intuitionistic fuzzy information system (IFIS) is defined as IFIS = (U, AT, {V_a : a ∈ AT} , {f_a : a ∈ AT}), in which U and AT are nonempty, finite object set and attribute set respectively. V_a consists of all IF values of a ∈ AT, f_a is an information function, such that f_a(x) = 〈μ_a(x), ν_a(x), and ∀x ∈ U, ∀a ∈ AT, 0 ≤ μ_a (x) + ν_a (x) ≤1.

Moveover, if C and D are conditional and decision attribute sets with C∩ D = ∅ and AT = C ∪ D, then IFIS is denoted as intuitionistic fuzzy decision information system (short for IFDS).

2.2 Generalized one-sided formal contexts

Considering the multi-valued formal contexts, Butka and Pócs [9] proposed generalized one-sided formal context.

Definition 4 [48]. A 4-tuple $K = (G, M, L, R)$ is known as a generalized one-sided formal context if it satisfies the following conditions:

(1) G and M are non-empty sets of objects and attributes, respectively.

(2) $L : M \to CL$ is a mapping from M to the class of all complete lattices, where $L (a)$ means a structure of truth values for any attribute a ∈ M.

(3) R is a generalized incidence relation between G and M such that $R (x, a) \in L (a)$ for all x ∈ G, a ∈ M. R (x, a) represents a degree from the structure $L (a)$ in which the element x ∈ G has the attribute a.

According to Definition 4, two operations are defined between $P (G)$ and $\prod_{a \in M} L (a)$ .

Definition 5 [48]. Let $K = (G, M, L, R)$ be a generalized one-sided formal context. For $X \in P (G)$ and $g \in \prod_{a \in M} L (a)$ , a pair of mappings $▽ : P (G) \to \prod_{a \in M} L (a)$ and $△ : \prod_{a \in M} L (a) \to P (G)$ are defined as follows:

X^▽ (a) = ⋀ _x∈XR (x, a) , a ∈ M,

g^△ = {x ∈ G : ∀ a ∈ M, g (a) ≤ R (x, a)}.

It is clear that the pair of operators (^▽, ^△) forms a Galois connection between $P (G)$ and $\prod_{a \in M} L (a)$ .

According to Shao’s definition [49], if we use ⋁_x∈XR (x, a) instead of ⋀_x∈XR (x, a) in operator ^▽, and g (a) ≥ R (x, a) instead of g (a) ≤ R (x, a) in operator ^△, then the Shao’s definition of adjoint operators on $K = (G, M, L, R)$ can be rewritten as follows:

X^↑ (a) = ⋁ _x∈XR (x, a) , a ∈ M,

g^↓ = {x ∈ G : ∀ a ∈ M, g (a) ≥ R (x, a)}.

From the results in [49], the pair (^↑, ^↓) forms a isotone Galois connection between $P (G)$ and $\prod_{a \in M} L (a)$ .

Let $K = (G, M, L, R)$ be a generalized one-sided formal context. For $X \in P (G)$ and $g \in \prod_{a \in M} L (a)$ , a pair (X, g) is called a generalized one-sided concept of $K = (G, M, L, R)$ if X^▽ = g and g^△ = X (or X^↑ = g and g^↓ = X), where X and g are interpreted as the extent and intent of the generalized one-sided concept, respectively.

Example 1. Table 1 is a generalized one-sided formal context, where G = {x₁, x₂, x₃, x₄} and M = {a, b, c, d}. The generalized incidence relation R is shown in Table 1.

Table 1
A generalized one-sided formal context $K = (G, M, L, R)$

R a b c d

x ₁ 2 1 1 1

x ₂ 3 2 2 3

x ₃ 1 2 1 2

x ₄ 3 3 2 3

R	a	b	c	d
x ₁	2	1	1	1
x ₂	3	2	2	3
x ₃	1	2	1	2
x ₄	3	3	2	3

According to Definition 4, we have $L (a) = L (b) = L (d) = 3$ , $L (c) = 2$ , where 3 and 2 denote 3 elements and 2 elements chain, respectively. ∀x ∈ G, R (x) denotes the x-th row in Table 1. Let X = {x₁, x₂, x₄} and g = {2, 1, 1, 1}, it is easy to check that X^▽ = g and g^△ = X. Thus, (X, g) is a generalized one-sided concept as defined by Butka and Pĺöcs. Let X = {x₁, x₃} and g = {2, 2, 1, 2}, it is easy to check that X^↑ = g and g^↓ = X. Thus, (X, g) is a generalized one-sided concept as defined by Shao. Other important conclusions for generalized one-sided concept lattices can be also found in the literatures [48, 49].

Generalized one-sided concept lattice is a special case of fuzzy FCA, where the extents are considered as crisp subsets of objects and intent sets are fuzzy values of attributes. The interpretation of the one-sided concept is straightforward as in the classical FCA.

2.3 IF sets and triangular norms

Let G be a nonempty set of objects, and an IF set A on G is defined by A = {〈μ_A (x) , ν_A (x) 〉 : x ∈ G}.

The two mappings μ_A : G → [0, 1] and ν_A : G → [0, 1] represent the membership and nonmembership degrees of the element x ∈ G to A, respectively. ∀x ∈ G, 0 ≤ μ_A (x) + ν_A (x) ≤1. 1 - μ_A (x) - ν_A (x) is the hesitancy degree of x ∈ U to A. All IF subsets of G are represented by $IFS (G)$ , we call A (x) = 〈μ_A (x) , ν_A (x) 〉 an intuitionistic fuzzy number.

According to Xu [50], the score function and accuracy function are applied to rank intuitionistic fuzzy numbers. The score function is defined as the difference of the certainty degree to which one alternative is preferred to another. The accuracy function is defined as the sum of the certainty degree to which one alternative is non-preferred to another. The relation between the score function and the accuracy function is similar to the relation between mean and variance in statistics. There are some problems in the practical application of this method. For example: in an election, if a candidate’s support rate is 60% and the opposition rate is 40%, the candidate wins the election. If the candidate’s support rate is 40% and the opposition rate is 0%, the candidate’s election fails. That means <0.6, 0.4>> <0.4, 0.0 >. However, we can easily verify that <0.4, 0.0>> <0.6, 0.4 > by score function and accuracy function. Now we introduce a new sort method of intuitionistic fuzzy numbers.

Definition 6. A fuzzy complement (fuzzy negation) N : [0, 1] → [0, 1] is a mapping, which fulfills the following axioms, ∀a, b ∈ [0, 1],

(1) Boundary condition: N (1) =0, N (0) =1;

(2) Monotonicity: a ≤ b ⇒ N (a) ≥ N (b).

∀a ∈ [0, 1], if N (a) =1 - a is always established, the fuzzy complement N is called the standard fuzzy complement, and is denoted by N_S.

Definition 7 [52]. A triangular norm (short for t-norm) T : [0, 1] × [0, 1] → [0, 1] is a binary mapping, which fulfills, ∀a, b, c ∈ [0, 1],

(1) Boundary condition: T (a, 1) = a;

(2) Monotonicity: b ≤ c ⇒ T (a, b) ≤ T (a, c);

(3) Commutative: T (a, b) = T (b, a);

(4) Associativity: T (a, T (b, c)) = T (T (a, b) , c).

Definition 8 [52]. A fuzzy union (short for t-conorm) S : [0, 1] × [0, 1] → [0, 1] is a binary mapping, which fulfills the following axioms, ∀a, b, c ∈ [0, 1],

(1) Boundary condition: S (a, 0) = a;

(2) Monotonicity: if b ≤ c ⇒ S (a, b) ≤ S (a, c);

(3) Commutative: S (a, b) = S (b, a);

(4) Associativity: S (a, S (b, c)) = S (S (a, b) , c).

∀a, b ∈ [0, 1], if N (T (a, b)) = S_T (N (a) , N (b)) or N (S_T (a, b)) = T (N (a) , N (b)), we call T and S_T satisfy the duality w.r.t. a fuzzy complement N. (T, S_T, N) is called the dual triples. Some particular dual triples are as following [10]:

min-max dual triples: (min {a, b} , max {a, b} , N_S);

product dual triples: (ab, a + b - ab, N_S);

Łukasiewicz dual triples: (max {0, a + b - 1} , min {1, a + b} , N_S).

Let α = 〈μ_α, ν_α〉 be an intuitionistic number. According to t-norm and t-conorm, we have following operators:

T (α) = T (μ_α, N_S (ν_α));

S (α) = S (μ_α, N_S (ν_α)).

For α = 〈μ₁, ν₁〉 and β = 〈μ₂, ν₂〉, if T (α) > T (β), then α > β; if T (α) = T (β) and

S_T (α) = S_T (β), then α = β;

S_T (α) > S_T (β), then α > β;

S_T (α) < S_T (β), then α < β.

3 Generalized one-sided IF concept lattices

In this section, two kinds of IF concept lattices are introduced in an IF formal context. We first give the notion of IF formal contexts.

A 4-tuple IFK = (G, M, V, f) is called an IF formal context (also called an IF information system), where object set G and attribute set M are all finite, nonempty sets. V is the range of the attributes and defined in [0, 1] × [0, 1]. Mapping f : G × M → V is defined as an intuitionistic fuzzy mapping, where f (x, a) = 〈μ_a (x) , ν_a (x) 〉 and ∀x ∈ U, a ∈ M, 0 ≤ μ_a (x) + ν_a (x) ≤1.

Example 2. Table 2 is an IF formal context, G = {x₁, x₂, x₃, x₄}, M = {a, b, c, d}, then f (x₂, b) = 〈0.3, 0.5〉.

Table 2
An IF formal context IFK = (G, M, V, f)

a b c d

x ₁ 〈0.5, 0.3〉〈0.2, 0.6〉〈0.7, 0.3〉〈0.7, 0.3〉

x ₂ 〈0.7, 0.2〉〈0.3, 0.5〉〈0.3, 0.5〉〈0.4, 0.5〉

x ₃ 〈0.1, 0.8〉〈0.1, 0.6〉〈0.3, 0.4〉〈0.2, 0.5〉

x ₄ 〈0.3, 0.6〉〈0.6, 0.2〉〈0.5, 0.2〉〈0.5, 0.4〉

	a	b	c	d
x ₁	〈0.5, 0.3〉	〈0.2, 0.6〉	〈0.7, 0.3〉	〈0.7, 0.3〉
x ₂	〈0.7, 0.2〉	〈0.3, 0.5〉	〈0.3, 0.5〉	〈0.4, 0.5〉
x ₃	〈0.1, 0.8〉	〈0.1, 0.6〉	〈0.3, 0.4〉	〈0.2, 0.5〉
x ₄	〈0.3, 0.6〉	〈0.6, 0.2〉	〈0.5, 0.2〉	〈0.5, 0.4〉

Definition 9. Let IFK = (G, M, V, f) be an IF formal context. Define two mappings $↑ : P (G) \to \sum_{a \in M} V$ and $↓ : \sum_{a \in M} V \to P (G)$ between $P (G)$ and ∑_a∈MV. For any $X \in P (G)$ and g ∈ ∑_a∈MV, that is,

$X^{↑} (a) = {f (x, a) : f (x, a) = \min_{y \in X} f (y, a)}$ ;

g^↓ = {x ∈ G : ∀ a ∈ M, g (a) ≤ f (x, a)}.

Proposition 3 Let IFK = (G, M, V, f) be an IF formal context. $X, X_{1}, X_{2}, X_{i} \in P (G)$ and g, g₁, g₂, g_i ∈ ∑_a∈MV, then we have the following results:

(1) $X_{1} \subseteq X_{2} \Rightarrow X_{1}^{↑} \geq X_{2}^{↑}$ , $g_{1} \leq g_{2} \Rightarrow g_{1}^{↓} \supseteq g_{2}^{↓}$ ;

(2) X ⊆ X^↑↓, g ≤ g^↓↑;

(3) X^↑ = X^↑↓↑, g^↓ = g^↓↑↓;

(4) $(⋃_{i \in I} X)^{↑} = ⋀_{i \in I} X_{i}^{↑} (a)$ , $(⋁_{i \in I} g_{i})^{↓} = ⋂_{i \in I} g_{i}^{↓}$ ,

where I is an index set.

Proof.(1) From Definition 9, one can easily obtain the result.

(2) For any $X \in P (G)$ , we have $\begin{matrix} X^{↑ ↓} & = {y \in G : \forall a \in M, X_{1}^{↑} (a) \leq f (y, a)} \\ = {y \in G : \forall a \in M, \min_{x \in X} f (x, a) \leq f (y, a)} . \end{matrix}$

We know that ∀x ∈ X, a ∈ M, $\min_{y \in X} f (y, a) \leq f (x, a)$ . Therefore, X ⊆ X^↑↓.

∀a ∈ M, $g^{↓ ↑} (a) = {f (y, a) : f (y, a) = \min_{x \in g ↓} f (x, a)}$ . If x ∈ g^↓, then ∀a ∈ M, f (x, a) ≥ g (a), thus, $\min_{x \in g^{↓}} f (x, a) \geq g (a)$ . Therefore, g ⊆ g^↓↑.

(3) First, it is evident that X^↑ ≥ X^↑↓↑ and g^↓ ⊇ g^↓↑↓ from (1) and (2). Then, according to Definition 9, X^↑ ∈ ∑_a∈MV and $g^{↓} \in P (G)$ . By Proposition 3 (2), we obtain X^↑ ≤ (X^↑) ^↓↑ and g^↓ ⊆ (g^↓) ^↑↓. Hence, we conclude that X = X^↑↓↑ and g = g^↓↑↓.

(4) It is straightforward.□

As a consequence of Proposition 3, we have the following conclusion.

Theorem 1. Let IFK = (G, M, V, f) be an IF formal context. Then the mapping pair (^↑, ^↓) forms a Galois connection.

Definition 10. Let IFK = (G, M, V, f) be an IF formal context. Define two mappings $△ : P (G) \to \sum_{a \in M} V$ and $▽ : \sum_{a \in M} V \to P (G)$ between $P (G)$ and ∑_a∈MV. For any $X \in P (G)$ and g ∈ ∑_a∈MV, that is,

$X^{△} (a) = {f (x, a) : f (x, a) = \max_{y \in X} f (y, a)}$ ;

g^▽ = {y ∈ G : ∀ a ∈ M, g (a) ≥ f (y, a)}.

Proposition 4 Let IFK = (G, M, V, f) be an IF formal context. $X, X_{1}, X_{2}, X_{i} \in P (G)$ and g, g₁, g₂, g_i ∈ ∑_a∈MV, then we have the following results:

(1) $X_{1} \subseteq X_{2} \Rightarrow X_{1}^{△} \leq X_{2}^{△}$ , $g_{1} \leq g_{2} \Rightarrow g_{1}^{▽} \subseteq g_{2}^{▽}$ ;

(2) X ⊆ X^△▽, g ⊇ g^▽△;

(3) X^△ = X^△▽△, g^▽ = g^▽△▽;

(4) $(⋃_{i \in I} X_{i})^{△} = ⋁_{i \in I} X_{i}^{△}$ , $(⋀_{i \in I} g_{i})^{▽} = ⋂_{i \in I} g_{i}^{▽}$ ,

where I is an index set.

Proof. By the similar proof of Proposition 3, and it is omitted. □

As a consequence of the Proposition 4 and Definition 2, we have the following conclusion.

Theorem 2. Let IFK = (G, M, V, f) be an IF formal context. Then the mapping pair (^△, ^▽) forms an isotone Galois connection.

Definition 11. Let IFK = (G, M, V, f) be an IF formal context. If X^↑ = g and g^↓ = X, the pair (X, g) is called a type-1 generalized one-sided IF concept of IFK = (G, M, V, f). X is called the extent of the type-1 generalized one-sided IF concept, while g is the intent.

Example 3. We use min-max adjoint triple in Example 2. Let X = {x₂, x₄} and g = {〈0.3, 0.6〉, 〈0.3, 0.5〉, 〈0.3, 0.5〉, 〈0.4, 0.5〉}, one can easily check that X^↑ = {〈0.3, 0.6〉, 〈0.3, 0.5〉, 〈0.3, 0.5〉, 〈0.4, 0.5〉} = g and g^↓ = {x₂, x₄} = X.

It is clear that (X, g) is a type-1 generalized one-sided IF concept.

All type-1 generalized one-sided IF concepts of IFK = (G, M, V, f) form a set of concepts, we represent it as ${IFB}^{1} (G, M, V, f)$ , that is ${IFB}^{1} (G, M, V, f) = {(X, g) \in P (G) \times \sum_{a \in M} V : X^{↑} = g, g^{↓} = X}$ .

$\forall (X, g_{1}), (Y, g_{2}) \in {IFB}^{1} (G, M, V, f)$ , the partial order ≤ defined on ${IFB}^{1} (G, M, V, f)$ is (X, g₁) ≤ (Y, g₂) iff X ⊆ Y (iff g₁ ≥ g₂). In this case, (X, g₁) is recognized as the sub-concept of (Y, g₂), and (Y, g₂) is the super-concept of (X, g₁).

Theorem 3. Let IFK = (G, M, V, f) be an IF formal context. ${IFB}^{1} (G, M, V, f)$ forms a complete lattice with partial order ≤. We call it the type-1 generalized one-sided IF concept lattice. $\forall (X_{i}, g_{i}) \in {IFB}^{1} (G, M, V, f)$ , the meet and the join are given by

⋀_i∈I (X_i, g_i) = (⋂ _i∈IX_i, (⋁ _i∈Ig_i) ^↓↑);

⋁_i∈I (X_i, g_i) = ((⋃ _i∈IX_i) ^↑↓, ⋀ _i∈Ig_i).

Proof. According to Proposition 3 (3) and (4), one can easily prove that $(⋁_{i \in I} g_{i})^{↓ ↑ ↓} = (⋁_{i \in I} g_{i})^{↓} = ⋂_{i \in I} g_{i}^{↓} = ⋂_{i \in I} X_{i}$ . Additionally, $(⋂_{i \in I} X_{i})^{↑} = (⋂_{i \in I} g_{i}^{↓})^{↑} = (⋁_{i \in I} g_{i})^{↓ ↑}$ . Thus, we have that $(⋂_{i \in I} X_{i}, (⋁_{i \in I} g_{i})^{↓ ↑}) \in {IFB}^{1} (G, M, V, f)$ . Similarly, we have $((⋃_{i \in I} X_{i})^{↑ ↓}, ⋀_{i \in I} g_{i}) \in {IFB}_{1} (G, M, V, f)$ .

Now, we need to check that ⋀_i∈I (X₁, g₁) is the infimum of (X_i, g_i) (i ∈ I) while ⋁_i∈I (X₁, g₁) is the supremum.

Note that ⋂_i∈IX_i ⊆ X_i, by Proposition 3 (1), ⋀_i∈I (X₁, g₁) = (⋂ _i∈IX_i, (⋁ _i∈Ig_i) ^↓↑) ≤ (X_i, g_i). That means ⋀_i∈I (X₁, g₁) is a lower bound of all type-1 generalized one-sided IF concepts (X_i, g_i). Suppose that (X, g) is an arbitrary lower bound of all type-1 generalized one-sided IF concepts (X_i, g_i). ∀i ∈ I, X_i ⊇ X, this means ⋂_i∈IX_i ⊇ X. According to Proposition 3 (1), ⋀_i∈I (X_i, g_i) ≥ (X, g). Thus, we conclude that ⋀_i∈I (X_i, g_i) is the infimum of all concepts (X_i, g_i).

By the same way, ⋁_i∈I (X₁, g₁) is the supermum of all concepts (X_i, g_i).□

Example 4. By calculating all type-1 generalized one-sided IF concepts in Example 2, an IF concept lattice ${IFB}^{1} (G, M, V, f)$ is shown in Fig. 1.

Fig. 1

Type-1 generalized one-sided IF concept lattice ${IFB}^{1} (G, M, V, f)$ .

Definition 12. Let IFK = (G, M, V, f) be an IF formal context. If X^△ = g and g^▽ = X, the pair (X, g) is called a type-2 generalized one-sided IF concept of IFK = (G, M, V, f). X is called the extent of the type-2 generalized one-sided IF concept, while g is the intent.

Example 5. Continued from Example 2, we use min-max adjoint triple. Let X = {x₂, x₃} and g = {〈0.7, 0.2〉, 〈0.3, 0.5〉, 〈0.3, 0.4〉, 〈0.4, 0.5〉}, one can easily check that g^▽ = {x₂, x₃} = X and X^△ = {〈0.7, 0.2〉, 〈0.3, 0.5〉, 〈0.3, 0.4〉, 〈0.4, 0.5〉} = g;

It is clear that (X, g) is a type-2 generalized one-sided IF concept.

All type-2 generalized one-sided IF concepts of IFK = (G, M, V, f) form a set of concepts, we represent it as ${IFB}^{2} (G, M, V, f)$ , that is ${IFB}^{2} (G, M, V, f) = {(X, g) \in P (G) \times \sum_{a \in M} V : X^{△} = g, g^{▽} = X}$ .

$\forall (X, g_{1}), (Y, g_{2}) \in {IFB}^{2} (G, M, V, f)$ , the partial order ≤ defined on ${IFB}^{2} (G, M, V, f)$ is (X, g₁) ≤ (Y, g₂) iff X ⊆ Y ( iff g₁ ≤ g₂). In this case, (X, g₁) is recognized as the sub-concept of (Y, g₂) and (Y, g₂) is recognized as the super-concept of (X, g₁).

Theorem 4. Let IFK = (G, M, V, f) be an IF formal context. ${IFB}^{2} (G, M, V, f)$ forms a complete lattice with partial order ≤. We call it the type-2 generalized one-sided IF concept lattice. $\forall (X_{i}, g_{i}) \in {IFB}^{2} (G, M, V, f)$ , the meet and the join are given by

⋀_i∈I (X₁, g₁) = (⋀ _i∈IX_i, (⋀ _i∈Ig_i) ^▽△);

⋁_i∈I (X₁, g₁) = ((⋁ _i∈IX_i) ^△▽, ⋁ _i∈Ig_i).

Proof. By the similar proof with Theorem 3. □

Example 6. By calculating all type-2 generalized one-sided IF concepts in Example 5, we obtain an IF concept lattice ${IFB}^{2} (G, M, V, f)$ as shown in Fig.2.

Fig. 2

Type-ćò generalized one-sided IF concept lattice ${IFB}^{2} (G, M, V, f)$ .

4 Attribute reduction in an IF formal context

4.1 Attribute reduction

Now we mainly discuss the basic issue of attribute reduction for type-1 generalized one-sided IF concept lattice in an IF formal concept. In the same way, one can also obtain the attribute reduction for type-2.

Theorem 5. Let IFK = (G, M, V, f) be an IF formal context. If ∃a ∈ M, x ∈ G, ∀y ∈ G - {x} such that f (y, a) < f (x, a), then $({x}, {x}^{↑}) \in {IFB}^{1} (G, M, V, f)$ .

Proof. It is clear that {x} ⊆ {x} ^↑↓. We only need to prove {x} ^↑↓ ⊆ {x}. ∀x ∈ G, {x} ^↑ = ∑_a∈Mf (x, a). If ∃a ∈ M such that f (y, a) < f (x, a) , (∀ y ∈ G - {x}) then {x} ^↑↓ = {y ∈ G : ∀ a ∈ M, f (x, a) ≤ f (y, a)} ⊆ {x}. Therefore, $({x}, {x}^{↑}) \in {IFB}^{1} (G, M, V, f)$ . □

Theorem 6. Let IFK = (G, M, V, f) be an IF formal context, x₁, x₂ ∈ G. If ∀a ∈ M, f (x₁, a) ≤ f (x₂, a), then {x₂} ^↑↓ ⊇ {x₁} ^↑↓.

Proof. For any y ∈ {x₁} ^↑↓, according to Definition 9, $\begin{matrix} y \in {x_{1}}^{↑ ↓} & \Leftrightarrow {y \in G : \forall a \in M, {x_{1}}^{↑} (a) \leq f (y, a)} \\ \Leftrightarrow {y \in G : \forall a \in M, f (x_{1}, a) \leq f (y, a)} \\ \Rightarrow {y \in G : \forall a \in M, f (x_{2}, a) \leq f (y, a)} \\ \Leftrightarrow {y \in G : \forall a \in M, {x_{2}}^{↑} (a) \leq f (y, a)} \\ \Leftrightarrow y \in {x_{2}}^{↑ ↓} \end{matrix}$

Therefore, {x₁} ^↑↓ ⊆ {x₂} ^↑↓. □

Given an IF formal context IFK = (G, M, V, f), for D ⊆ M, IFK_D = (G, D, V_D, f_D) is denoted as the sub-context of IFK = (G, M, V, f), where f_D = f ⋂ (U × D). In the sub-context (G, D, V_D, f_D), we use ^↑D and ^↓D instead of ^↑ and ^↓, respectively. It is clear that ^↑M = ^↑ and ^↓M = ^↓.

Definition 13. For two type-1 generalized one-sided IF concept lattices ${IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ and ${IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ , $\forall (X_{1}, g_{1}) \in {IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ , there always exits $(X_{2}, g_{2}) \in {IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ , such that X₁ = X₂, then we call ${IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ is finer then ${IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ , and is denoted by ${IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2}) \leq {IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ . If ${IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2}) \leq {IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ and ${IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1}) \leq {IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ , then ${IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ and ${IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ are isomorphic, and is denoted by ${IFB}_{1}^{1} (G, M_{1}, V_{1}, f_{1})$ $≅ {IFB}_{2}^{1} (G, M_{2}, V_{2}, f_{2})$ .

Theorem 7. Let IFK = (G, M, V, f) be an IF formal context. For any D ⊆ M and D≠ ∅, then ${IFB}^{1} (G, M, V, f) \leq {IFB}^{1} (G, D, V_{D}, f_{D})$ .

Proof. For any $(X, X^{↑ D}) \in {IFB}^{1} (G, M, V_{D}, f_{D})$ , we have $(X^{↑ ↓}, X^{↑}) \in {IFB}^{1} (G, M, V, f)$ . From Proposition 3 (2), X ⊆ X^↑↓. In the following, we need to show that X^↑↓ ⊆ X.

Suppose that y ∉ X, then ∃a ∈ D such that f (y, a) < X^↑D (a). Since D ⊆ M, then ∃a ∈ M, such that f (y, a) < X^↑ (a). Therefore, x ∉ X^↑↓. That is X^↑↓ ⊆ X. Thus, we conclude that X = X^↑↓. According to Definition 13, ${IFB}^{1} (G, M, V, f) \leq {IFB}^{1} (G, D, V_{D}, f_{D})$ . □

Definition 14. Let IFK = (G, M, V, f) be an IF formal context. If there exists D ⊆ M, such that ${IFB}^{1} (G, M, V, f) ≅ {IFB}^{1} (G, D, V_{D}, f_{D})$ , then D is a type-1 generalized one-sided consistent set of IFK = (G, M, V, f). Furthermore, if ∀C ⊂ D, ${IFB}^{1} (G, M, V, f) ≅ {IFB}^{1} (G, C, V_{Citsc}, f_{Citsc})$ is not satisfied, then D is called a type-1 generalized one-sided reduct.

Corollary 1. Let IFK = (G, M, V, f) be an IF formal context. For any subset D ⊆ M, D is a type-1 generalized one-sided consistent set it iff X^↑↓ = X^↑D↓D, ∀X ⊆ G.

Corollary 2. Let IFK = (G, M, V, f) be an IF formal context. For any subset D ⊆ M, D is a type-1 generalized one-sided consistent set it iff ${IFB}^{1} (G, D, V_{D}, f_{D}) \leq {IFB}^{1} (G, M, V, f)$ .

Corollaries 1 and 2 follow immediately from Definition 14 and Theorem 7.

Theorem 8. Let IFK = (G, M, V, f) be an IF formal context. For any true subset D ⊂ M, D≠ ∅ and E = M - D, D is a type-1 generalized one-sided consistent set it iff $\forall (X, g) \in {IFB}^{1} (G, M, V, f)$ , ∀F ⊆ E,F≠ ∅, g^↓F = g^↓F↑D↓D.

Proof (⇒) For any $(X, g) \in {IFB}^{1} (G, M, V, f)$ , ∀F ⊆ E and F≠ ∅. According to Proposition 3 (2), it is clear that g^↓F ⊆ g^↓F↑↓. Suppose that x ∉ g^↓F, then ∃a ∈ F such that g (x, a) > f (x, a), we obtain $\min_{y \in g^{↓ F}} f (y, a) \geq f (x, a)$ , which means x ∉ g^↓F↑↓, that is g^↓F↑↓ ⊆ g^↓F. Thus, g^↓F↑↓ = g^↓F. Since D is a type-1 generalized one-sided consistent set, by Corollary 1, g^↓F↑D↓D = g^↓F↑↓. Therefore, we conclude that g^↓F = g^↓F↑D↓D.

(⇐) Suppose that D is not a type-1 generalized one-sided consistent set. We know that ${IFB}^{1} (G, M, V, f) \leq {IFB}^{1} (G, D, V_{D}, f_{D})$ . $\forall (g^{↓ F}, g^{↓ F ↑}) \in {IFB}^{1} (G, M, V, f)$ , there exists $(g^{↓ F}, g^{↓ F ↑ D}) \in {IFB}^{1} (G, D, V_{D}, f_{D})$ , according to Definition 13, we obtain g^↓F↑↓ = g^↓F↑D↓D, which also contradicts with the assumption. □

From Theorem 8, we obtain the following conclusion.

Corollary 3. Let IFK = (G, M, V, f) be an IF formal context. For any true subset D ⊂ M, D≠ ∅ and E = M - D, D is a type-1 generalized one-sided consistent set it iff $\forall (X, g) \in {IFB}^{1} (G, M, V, f)$ , ∀a ∈ E, g^{↓{a}↑D↓D} = g^↓{a}.

Theorem 9. Let IFK = (G, M, V, f) be an IF formal context. For any true subset D ⊂ M, D≠ ∅ and E = M - D, D is a type-1 generalized one-sided consistent set it iff $\forall (X, g) \in {IFB}^{1} (G, M, V, f)$ , and ∀F ⊆ E, F≠ ∅, ∃B ⊆ D such that g^↓F = g^↓B.

Proof. (⇒) According to Theorem 8, we can easily prove it.

(⇐) For any type-1 generalized one-sided concept $(X, g) \in {IFB}^{1} (G, M, V, f)$ , we obtain that $(g^{↓ F ↑ ↓}, g^{↓ F ↑}) \in {IFB}^{1} (G, M, V, f)$ and $(g^{↓ B ↑ D ↓ D}, g^{↓ B ↑ D}) \in {IFB}^{1} (G, D, V_{D}, f_{D})$ . If g^↓F = g^↓B, then g^↓F↑↓ ⊆ g^↓B↑D↓D. By Proposition 3 (2), we have g^↓F ⊆ g^↓F↑↓ ⊆ g^↓B↑D↓D ⊆ g^↓B. Thus, g^↓F↑↓ = g^↓B↑↓ = g^↓B↑D↓D. Therefore, from Corollary 1, D is a type-1 generalized one-sided consistent set. □

From Theorem 9, one can easily prove the following results.

Corollary 4. Let IFK = (G, M, V, f) be an IF formal context. For any true subset D ⊂ M, D≠ ∅ and E = M - D, D is a type-1 generalized one-sided consistent set it iff $\forall (X, g) \in {IFB}^{1} (G, M, V, f)$ , ∀ {a} ⊆ E, ∃B ⊆ D such that g^{↓{a}=g^↓B}.

Suppose that (X, g₁) , (Y, g₂) are two type-1 generalized one-sided IF concepts in ${IFB}^{1} (G, M, V, f)$ and (X, g₁) ≤ (Y, g₂). If $\forall (Z, g) \in {IFB}^{1} (G, M, V, f)$ , (X, g₁) ≤ (Z, g) ≤ (Y, g₂) is not satisfied, then (Y, g₂) is called an supper-close concept of (X, g₁), denoted by (X, g₁) ≺ (Y, g₂). For any $(X, g) \in {IFB}^{1} (G, M, V, f)$ , all supper-close concepts of (X, g) form a concept set, we denote it as Θ (X).

Theorem 10. Let IFK = (G, M, V, f) be an IF formal context. For any true subset D ⊂ M, D is a type-1 generalized one-sided consistent set it iff $X_{1}^{↑ D} \neq X^{↑ D}$ for all $(X, g) \in {IFB}^{1} (G, M, V, f)$ and (X₁, g₁) ∈ Θ (X).

Proof (⇒) Suppose that D is a type-1 generalized one-sided consistent set. If there exists $(X, g) \in {IFB}^{1} (G, M, V, f)$ and (X₁, g₁) ∈ Θ (X) such that $X^{↑ D} = X_{1}^{↑ D}$ , then $(X_{1}^{↑ D ↓ D}, X_{1}^{↑ D}) = (X^{↑ D ↓ D}, X^{↑ D})$ , which means ${IFB}^{1} (G, D, V_{D}, f_{D}) \leq {IFB}^{1} (G, M, V, f)$ , it conflicts the assumption. Therefore, $X^{↑ D} \neq X_{1}^{↑ D}$ for all $(X, g) \in {IFB}^{1} (G, M, V, f)$ and (X₁, g₁) ∈ Θ (X).

(⇐) Suppose that D is not a type-1 generalized one-sided consistent set, then ${IFB}^{1} (G, D, V_{D}, f_{D}) \geq {IFB}^{1} (G, M, V, f)$ , which means there exists $(Y, Y^{↑}) \in {IFB}^{1} (G, M, V, f)$ and $(Y, Y^{↑ D}) \notin {IFB}^{1} (G, D, V_{D}, f_{D})$ . We know that $(Y^{↑ D ↓ D}, Y^{↑ D}) \in {IFB}^{1} (G, D, V_{D}, f_{D})$ , thus, Y^↑D↓D ≠ Y. According to Proposition 3(2), we have Y ⊆ Y^↑D↓D. Two cases are needed to be considered:

Case 1. If there exists (Y^↑D↓D, Y^↑D) ∈ Θ (Y), then it is easy to know that Y^↑D = Y^↑D↓D↑D = (Y^↑D↓D) ^↑D, which means Y^↑D↓D = Y. It contradicts with the assumption that D is not a type-1 generalized one-sided consistent set.

Case 2. If (Y^↑D↓D, Y^↑D) ∉ Θ (Y), then there exist $(X, g) \in {IFB}^{1} (G, M, V, f)$ and (X, g) ∈ Θ (Y) such that Y ⊂ X ⊂ Y^↑D↓D. According to Proposition 3(1) we have Y^↑D ⊃ X^↑D ⊃ (Y^↑D↓D) ^↑D. From Proposition 3(3), Y^↑D = (Y^↑D↓D) ^↑D. Thus, X^↑D = Y^↑D, which also contradicts the assumption.

Therefore, D is a type-1 generalized one-sided consistent set. □

Definition 15. Let IFK = (G, M, V, f) be an IF formal context. For a ∈ M, a is a type-1 generalized one-sided dispensable attribute in ${IFB}^{1} (G, M, V, f)$ if ${IFB}^{1} (G, M, V, f) ≅ {IFB}^{1} (G, M - {a}, V_{M - {a}}, f_{M - {a}})$ ; otherwise, a is an indispensable attribute.

Corollary 5. Let IFK = (G, M, V, f) be an IF formal context. For a ∈ M, a is a type-1 generalized one-sided dispensable attribute in ${IFB}^{1} (G, M, V, f)$ it iff $\forall (X, g) \in {IFB}^{1} (G, M, V, f)$ , X^↑↓ = X^{↑M-{a}↓M-{a}}.

Proof. According to Definition 13, Definition 15 and Corollary 1, it is straightforward. □

Corollary 6. Let IFK = (G, M, V, f) be an IF formal context. For any a ∈ M, a is a type-1 generalized one-sided dispensable attribute in ${IFB}^{1} (G, M, V, f)$ it iff $X_{1}^{↑ M - {a}} \neq X^{↑ M - {a}}$ for all $(X, g) \in {IFB}^{1} (G, M, V, f)$ and (X₁, g₁) ∈ Θ (X).

Proof. It is easy to get the result by Definition 15 and Theorem 8. □

Definition 16. Let IFK = (G, M, V, f) be an IF formal context and $(X_{i}, g_{i}), (X_{j}, g_{j}) \in {IFB}^{1} (G, M, V, f)$ . Let

$Dis (X_{i}, X_{j}) = {\begin{matrix} {a \in M : g_{j} (a) < g_{i} (a)}, & (X_{j}, g_{j}) \in Θ (X_{i}), \\ \emptyset, & otherwise . \end{matrix}$

Dis (X_i, X_j) is called the type-1 generalized one-sided discernibility attribute set of (X_i, g_i) and (X_j, g_j). $M = (Dis (X_{i}, X_{j}) : (X_{i}, g_{i}), (X_{j}, g_{j}) \in {IFB}^{1} (G, M, V, f))$ is denoted as the type-1 generalized one-sided discernibility matrix of ${IFB}^{1} (G, M, V, f)$ .

Theorem 11. Let IFK = (G, M, V, f) be an IF formal context. For any D ⊆ M, D is a type-1 generalized one-sided consistent set it iff ∀Dis (X_i, X_j) ∈ M and Dis (X_i, X_j)≠ ∅, Dis (X_i, X_j)∩ D ≠ ∅.

Proof. (⇒) ∀Dis (X_i, X_j) ∈ M and Dis (X_i, X_j)≠ ∅, if D is a consistent set of ${IFB}^{1} (G, M, V, f)$ , according to Theorem 8 we obtain $X_{i}^{↑ D} \neq X_{j}^{↑ D}$ . By Definition 16, we have D∩ Dis (X_i, X_j) ≠ ∅.

(⇐) Suppose that D is not a type-1 generalized one-sided consistent set, by Theorem 8, there exist $(X, g) \in {IFB}^{1} (G, M, V, f))$ and (X₁, g₁) ∈ Θ (X) such that $X^{↑ D} = X_{1}^{↑ D}$ . It contradicts with D∩ Dis (X_i, X_j) ≠ ∅. Thus, D is a type-1 generalized one-sided consistent set. □

Theorem 12. Let IFK = (G, M, V, f) be an IF formal context. For any a ∈ M, a is a type-1 generalized one-sided indispensable attribute in ${IFB}^{1} (G, M, V, f)$ it iff there exist $(X_{i}, g_{i}), (X_{j}, g_{j}) \in {IFB}^{1} (G, M, V, f)$ such that Dis (X_i, X_j) = {a}.

Proof. According to Definition 16 and Corollary 6, it can be easily proved. □

Let IFK = (G, M, V, f) be an IF formal context. The discernibility function of the IF formal context is defined by

Δ = ⋀ ⋁ Dis (X_i, X_j),

where Dis (X_i, X_j) ∈ M and Dis (X_i, X_j)≠ ∅. All reducts of ${IFB}^{1} (G, M, V, f)$ can be acquired by monotonic Boolean discernibility function Δ. Now we present an algorithm to get all reducts of ${IFB}^{1} (G, M, V, f)$ .

Algorithm 1 Computing all reducts of ${IFB}^{1} (G, M, V, f)$ .
Input:IFK = (G, M, V, f), G = {x₁, x₂, ⋯ , x_n},
M = {a₁, a₂, ⋯ , a_m};
Input: Reduct of ${IFB}^{1} (G, M, V, f)$ (short for Red).
1: Compute ${IFB}^{1} (G, M, V, f)$ ;
2: Compute the attribute discernibility matrix M;
3: Compute the Boolean discernibility function Δ;
4: Compute
$Δ = ⋀ ⋁ Dis (X_{i}, X_{j}) = \lor_{k = 1}^{t} (\land_{s = 1}^{q_{k}} a_{s})$ ;
5: Let D_k = {a_s\|s ≤ q_k} and Red = {D_k\|k ≤ t};
6: Return Red

4.2 Case study

Now, we would like to verify the feasibility of attribute reduction in IF concept lattices and apply the conclusions to a real multi-attribute decision-making problem.

Example 7. Suppose G = {x₁, x₂, x₃, x₄, x₅} represent five cars for sale, M = {a₁, a₂, a₃, a₄} is the set of some important characteristics about cars such as safety, oil consumption, comfort and price. We invite 10 people to evaluate the cars according to the above characteristics. The evaluation results are shown in Table 3. Consumer needs to choose a car according to his own requirements for each attribute.

Table 3
An IF formal context IFK = (G, M, V, f)

a ₁ a ₂ a ₃ a ₄

x ₁ 〈1.0, 0.0〉〈0.8, 0.1〉〈0.9, 0.0〉〈0.9, 0.1〉

x ₂ 〈0.9, 0.1〉〈0.9, 0.0〉〈0.6, 0.2〉〈0.7, 0.1〉

x ₃ 〈0.8, 0.1〉〈0.9, 0.1〉〈0.8, 0.0〉〈0.8, 0.1〉

x ₄ 〈0.8, 0.2〉〈0.6, 0.3〉〈0.5, 0.3〉〈0.7, 0.2〉

x ₅ 〈0.7, 0.0〉〈0.8, 0.0〉〈0.8, 0.1〉〈0.8, 0.2〉

	a ₁	a ₂	a ₃	a ₄
x ₁	〈1.0, 0.0〉	〈0.8, 0.1〉	〈0.9, 0.0〉	〈0.9, 0.1〉
x ₂	〈0.9, 0.1〉	〈0.9, 0.0〉	〈0.6, 0.2〉	〈0.7, 0.1〉
x ₃	〈0.8, 0.1〉	〈0.9, 0.1〉	〈0.8, 0.0〉	〈0.8, 0.1〉
x ₄	〈0.8, 0.2〉	〈0.6, 0.3〉	〈0.5, 0.3〉	〈0.7, 0.2〉
x ₅	〈0.7, 0.0〉	〈0.8, 0.0〉	〈0.8, 0.1〉	〈0.8, 0.2〉

Using the min-max dual triple, by Definition 10, all extents of type-1 generalized one-sided IF concepts are as shown in the following:

∅ =∅;

X₁ = {x₁}; X₂ = {x₂};

X₃ = {x₃}; X₄ = {x₁, x₂};

X₅ = {x₁, x₃}; X₆ = {x₂, x₃};

X₇ = {x₁, x₂, x₃}; X₈ = {x₁, x₂, x₃, x₄};

X₉ = {x₁, x₂, x₃, x₅}; G = G.

From Definition 16, we can compute the discernibility matrix, as shown in Table 4.

Table 4

The discernibility matrix M of ${IFB}^{1} (G, M, V, f)$

M	∅	X ₁	X ₂	X ₃	X ₄	X ₅	X ₆	X ₇	X ₈	X ₉	G
∅	∅	{a₂}	{a₁, a₃, a₄}	{a₁, a₂, a₃, a₄}	∅	∅	∅	∅	∅	∅	∅
X ₁	∅	∅	∅	∅	{a₁, a₃, a₄}	{a₁, a₃, a₄}	∅	∅	∅	∅	∅
X ₂	∅	∅	∅	∅	{a₂}	{a₁, a₂}	∅	∅	∅	∅	∅
X ₃	∅	∅	∅	∅	∅	{a₂, a₃}	{a₃, a₄}	∅	∅	∅	∅
X ₄	∅	∅	∅	∅	∅	∅	∅	{a₁}	∅	∅	∅
X ₅	∅	∅	∅	∅	∅	∅	∅	{a₃, a₄}	∅	∅	∅
X ₆	∅	∅	∅	∅	∅	∅	∅	{a₂}	∅	∅	∅
X ₇	∅	∅	∅	∅	∅	∅	∅	∅	{a₁, a₂, a₃, a₄}	{a₁}	∅
X ₈	∅	∅	∅	∅	∅	∅	∅	∅	∅	∅	{a₁}
X ₉	∅	∅	∅	∅	∅	∅	∅	∅	∅	∅	{a₂, a₃, a₄}
G	∅	∅	∅	∅	∅	∅	∅	∅	∅	∅	∅

Based on discernibility function, we can obtain two reducts. $\begin{matrix} Δ & = ⋀_{Dis (X_{i}, X_{j}) \in M \land Dis (X_{i}, X_{j}) \neq \emptyset} ⋁ Dis (X_{i}, X_{j}) \\ = a_{2} \land (a_{1} \lor a_{3} \lor a_{4}) \land (a_{1} \lor a_{2} \lor a_{3} \lor a_{4}) \land (a_{1} \lor a_{2}) \\ \land (a_{2} \lor a_{3}) \land (a_{3} \lor a_{4}) \land a_{1} \land (a_{2} \lor a_{3} \lor a_{4}) \\ = (a_{1} \land a_{2} \land a_{3}) \lor (a_{1} \land a_{2} \land a_{4}) . \end{matrix}$

Therefore, {a₁, a₂, a₃} and {a₁, a₂, a₄} are two reducts of ${IFB}^{1} (G, M, V, f)$ , in which a₁ and a₂ are indispensable attributes.

We know that if each performance attribute of a car is higher than the consumer’s expectation, the consumer will buy the car. Let M = {< μ_{a
₁}, ν_{a
₁} > , < μ_{a
₂}, ν_{a
₂} > , < μ_{a
₃}, ν_{a
₃} > , < μ_{a
₄}, ν_{a
₄} >} stand for the consumer’s minimum requirements for each characteristic of the car, (X, g) is a type-1 generalized one-sided IF concept. If g ≥ M, the consumer can choose any car in X.

In this example, if M = {<0.8, 0.2 > , <0.7, 0.2 > , <0.8, 0.2 > , <0.8, 0.2 >}, then g₅ ≥ M, the consumer can choose x₁ and x₃; if M = {<0.9, 0.1 > , <0.8, 0.2 > , <0.9, 0.1 > , <0.9, 0.1 >}, then g₁ ≥ M, the consumer can only choose x₁; if M = {<0.9, 0 > , <0.9, 0 > , <0.9, 0.1 > , <1, 0 >}, ∀i ≤ 8, we know that g_i < M, then all cars can not meet the needs of the consumer.

In addition, the reduction obtained above conveys the relations between these characteristics. In a way, the attribute reduction of type-1 generalized one-sided IF concept lattice, presented in the paper, can be used to facilitate the consumer to make a decision, since he only needs to consider attributes in the reduction.

5 Conclusion and further work

Based on the concept of one-sided concept lattice, this paper extended and developed the formal concept lattice theory in an intuitionisitc fuzzy formal context. After defining two types of Galois connections, two types of generalized one-sided intuitionistic fuzzy concept lattices were constructed. Relative theorems and properties were also examined. By discussing and analyzing the attribute characteristics for the type-1 generalized one-sided intuitionistic fuzzy concept lattice, we constructed the type-1 generalized one-sided discernibility matrix to acquire the attribute reduction. The proposed approach keeps the hierarchy of concepts and the number of concepts unchanged without loss of the required knowledge, which can be used to deal with practical problems such as rule acquisition, data processing, and classification. With data constantly changing, dynamic approach for updating the generalized one-sided intuitionistic fuzzy concept lattice and the fast lattice-keep-based attribute reduction algorithm should be an issue for further research.

Footnotes

Acknowledgements

This paper is supported by the National Natural Science Foundation of China (No. 62076088,72101082) and by the Natural Science Foundation of Hebei Province (No. A2020208004).

References

Wille

Restructuring lattice theory: an approach based on hierarchies of concepts, in: I. Rival (Ed.), Ordered Sets, Reidel, Dordrecht-Boston, 1982, pp. 445–470.

Formica

, Semantic web search based on rough sets and fuzzy formalconcept analysis, Knowl. Based Syst. 26 (2012), 40–47.

Dua

Y.J.

and Li

H.M.

, Strategy for mining association rules for webpages based on formal concept analysis, Appl. Soft Comput. 10 (2010), 772–783.

Belohlavek

, Sigmund

and Zacpal

, Evaluation of IPAQ questionnaires supported by formal concept analysis, Inf. Sci. 181 (2011), 1774–1786.

Sampath

, Sprenkle

, Gibson

, Pollock

and Greenwald

A.S.

, Applying concept analysis to user-session-based testing of web applications, IEEE Trans. Softw. Eng. 33(10) (2007), 643–658.

Zhang

, Constructing L-fuzzy concept lattices without fuzzy Galoisclosure operation, Fuzzy Sets Syst. 333 (2018), 71–86.

Burusco

and Fuentes-Gonzíćlez

, Concept lattices defined from implication operators, Fuzzy Sets Syst. 114(3) (2000), 431–436.

Belohlavek

and Vychodil

, Formal concept analysis withbackground knowledge: attribute priorities, IEEE Trans. Syst.,Man, Cybern., Cybern.-Part C: Appl. Rev. 39(4) (2009), 399–409.

Georgescu

and Popescu

, Non-dual fuzzy connections, Arch.Math. Logic. 43(8) (2004), 1009–1039.

10.

Konecny

, Isotone fuzzy Galois connections with hedges, Inf.Sci. 181(10) (2011), 1804–1817.

11.

Medina

, Ojeda-Aciego

and Ruiz-Calvino

, Formal conceptanalysis via multi-adjoint concept lattices, Fuzzy Sets Syst. 160(2) (2009), 130–144.

12.

Jaoua

and Elloumi

, Galois connection, formal concepts andgalois lattice in real relations: application in a real classifier, J. Syst. Softw. 60 (2002), 149–163.

13.

Yahia

S.B.

and Jaoua

, Discovering knowledge from fuzzy conceptlattice, Data Mining and Comput. Intell. 68 (2001), 167–190.

14.

Halas

and Píőcs

, Generalized one-sided conceptlattices with attribute preferences, Inf. Sci. 303 (2015), 50–160.

15.

Ferone

, Feature selection based on composition of rough setsinduced by feature granulation, Int. J. Approx. Reason. 101 (2018), 276–292.

16.

, Jia

, Wang

and Zhou

, Multi-objective attributereduction in three-way decision-theoretic rough set model, Int.J. Approx. Reason. 105 (2019), 327–341.

17.

Fang

and Min

, Cost-sensitive approximate attribute reductionwith three-way decisions, Int. J. Approx. Reason. 104 (2019), 148–156.

18.

Raza

M.S.

and Qamar

, Feature selection using rough set-baseddirect dependency calculation by avoiding the positive region, Int. J. Approx. Reason. 92 (2018), 175–197.

19.

Dias

S.M.

and Vieira

N.J.

, Concept lattices reduction: definition,analysis and classification, Expert Syst. Appl. 42 (2015), 7084–7097.

20.

Cornejo

M.E.

, Medina

and Ramíre-Poussa

, Characterizingreducts in multi-adjoint concept lattices, Inf. Sci. 422 (2018), 364–376.

21.

Chen

J.K.

, Mi

J.S.

and Lin

Y.J.

, A graph approach for fuzzy-roughfeature selection, Fuzzy Sets Syst. 391 (2019), 96–116.

22.

W.Z.

, Leung

and Mi

J.S.

, Granular computing and knowledgereduction in formal contexts, IEEE Trans. Knowl. Data Eng. 21(10) (2009), 1461–1474.

23.

Kumar

C.A.

and Srinivas

, Concept lattice reduction using fuzzyk-means clustering, Expert Syst. Appl. 37 (2010), 2696–2704.

24.

Shao

M.W.

, Yang

H.Z.

and Wu

W.Z.

, Knowledge reduction in formalfuzzy contexts, Knowl. Based Syst. 73 (2015), 265–275.

25.

Aragón

R.G.

, Medina

and Ramírez-Poussa

, Reducingconcept lattices by means of a weaker notion of congruence, Fuzzy Sets Syst. 418(1) (2021), 153–169.

26.

Wang

, Wei

, Qi

J.J.

et al. Attribute reduction of SE-ISIconcept lattices for incomplete contexts, Soft Comput. 24 (2020), 15143–15158.

27.

Shao

M.W.

, Yang

H.Z.

and Wu

W.Z.

, Knowledge reduction in formalfuzzy contexts, Knowl. Based Syst. 73 (2015), 265–275.

28.

J.H.

, Mei

C.L.

and Lv

Y.J.

, Knowledge reduction in decisionformal contexts, Knowl. Based Syst. 24 (2011), 709–715.

29.

Chen

J.K.

, Mi

J.S.

, Xie

and Lin

Y.J.

, A fast attribute reductionmethod for large formal decision contexts, Int. J. Approx. Reason. 106 (2019), 1–17.

30.

Atanassov

K.T.

, Intuitionistic fuzzy sets, Fuzzy Sets Syst. 20(1) (1986), 87–96.

31.

Liang

M.S.

, Mi

J.S.

and Feng

, Multi-adjoint based groupdecision-making under an intuitionistic fuzzy information system, Int. J. Comput. Intell. Syst. 12 (2018), 172–182.

32.

Sun

B.Z.

, Ma

and Liu

, An approach to decision making based onintuitionistic fuzzy rough sets over two universes, J. Oper.Res. Soc. 64(7) (2017), 1079–1089.

33.

Das

, Acharjya

and Patr

, Multi criterion decision makingusing intuitionistic fuzzy rough set on two universal sets, Int. J. Intell. Syst. Appl. 7(4) (2015), 26–33.

34.

Liang

M.S.

, Mi

J.S.

and Feng

, Optimal granulation selection forsimilarity measure-based multigranulation intuitionistic fuzzydecision-theoretic rough sets, J. Intell. Fuzzy Syst. 36(3) (2019), 2495–2509.

35.

J.H.

, Ren

, Mei

C.L.

, Li

, Qian

Y.H.

and Yang

X.B.

, Acomparative study of multigranulation rough sets and conceptlattices via rule acquisition, Knowl. Based Syst. (91) (2016), 152–164.

36.

Ciobanu

and Văideanu

, A note on similarity relationsbetween fuzzy attribute-oriented concept lattices, Inf. Sci. 460–461 (2018), 254–263.

37.

Xin

X.W.

, Song

J.H.

, Xue

Z.A.

et al. Intuitionistic fuzzy three-wayformal concept analysis based attribute correlation degree, J.Intell. Fuzzy Syst. 40 (2021), 1567–1583.

38.

Zou

, Lin

H.M.

, Song

X.Y.

et al. Rule extraction based onlinguistic-valued intuitionistic fuzzy layered concept lattice, Int. J. Approx. Reason. 133 (2021), 1–16.

39.

Hong

and Hong

J.Z.

, Attribute reduction of intuitionistic fuzzyconcept lattices, Applied Mechanics and Materials. 713–715 (2015), 1649–1654.

40.

Kridlo

and Ojeda-Aciego

, Extending formal concept analysisusing intuitionistic l-fuzzy sets, 2017 IEEE Int. Conf. FuzzySyst. (FUZZ-IEEE) (2017), 1–6.

41.

Everett

C.J.

, Closure operators and Galois theory in lattices, Trans. Amer. Math. Soc. 55(3) (1944), 514–525.

42.

Belohlavek

, Dvorak

and Outrata

, Fast factorization bysimilarity in formal concept analysis of data with fuzzy attributes, J. Comput. Syst. Sci. 73 (2007), 1012–1022.

43.

Pollandt

Fuzzy Begriffe,, Springer-Verlag, Berlin /Heidelberg, 1997.

44.

Gediga

, Düntsch

Modal-style operators in qualitative data analysis, in: Proc. IEEE International Conference on Data Mining (2002), 155–162.

45.

Yao

Y.Y.

, A comparative study of formal concept analysis and roughset theory in data analysis, in: Lecture Notes in Artificial Intell. 3066 (2004), 59–68.

46.

Erné

, Koslowski

, Melton

and Strecker

G.E.

, A primer ongalois connections, Annals of the New York Academy of Sciences. 704(1) (1993), 103–125.

47.

Vychodil , Vilem , Closure structures parameterized by systems ofisotone Galois connections, Int. J. Approx. Reason. 91(2017), 1–27.

48.

Butka

and Pŏocs

, Generalization of one-sided conceptlattices, Comput. Inform. 32 (2013), 355–370.

49.

Shao

M.W.

and Li

K.W.

, Attribute reduction in generalized one-sidedformal contexts, Inf. Sci. 378 (2017), 317–327.

50.

Z.S.

, Intuitionistic preference relations and their application in group decision making, Inf. Sci. 177(11) (2007), 2363–2379.

51.

Klir

G.J.

, Yuan

Fuzzy sets and fuzzy logic: theory and applications, Prentice Hall of India, 2008.

52.

Rahman

, On cuts of Atanassov’s intuitionistic fuzzy sets withrespect to fuzzy connectives, Inf. Sci. 340–341 (2016), 262–278.

Attribute reduction in intuitionistic fuzzy formal concepts

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 FCA and Galois connections

2.2 Generalized one-sided formal contexts

Table 1 A generalized one-sided formal context K = ( G , M , L , R ) R a b c d x 1 2 1 1 1 x 2 3 2 2 3 x 3 1 2 1 2 x 4 3 3 2 3

3 Generalized one-sided IF concept lattices

4.1 Attribute reduction

4.2 Case study

Footnotes

Acknowledgements

References

Table 1
A generalized one-sided formal context $K = (G, M, L, R)$

R a b c d

x ₁ 2 1 1 1

x ₂ 3 2 2 3

x ₃ 1 2 1 2

x ₄ 3 3 2 3