Attribute reduction based on directed graph in formal fuzzy contexts

Abstract

An attribute reduction can make the structure of concept lattices more convenient in formal fuzzy contexts. Thereby, it is beneficial to discover the knowledge. Based on the notion of “one-side fuzzy concept”, we propose a method of attribute reduction combining with the directed graph theory. Employing the proposed approach, a judgment theorem is given for determining concepts and irreducible elements in formal fuzzy contexts. According to the significance of attributes, these attributes are classified three types: core attributes, relatively necessary attributes and unnecessary attributes, which are referred to the attribute characteristics. Applying with the directed graph, We propose the judgment theorems and the corresponding algorithms for computing the three types of attributes sets. On this basis, a corresponding method of attribute reduction is given in a fuzzy-crisp formal context. The feasibility and effectiveness of the algorithm has been proved via an example. The approach presents a mew method for knowledge reducible in formal fuzzy contexts.

Keywords

Formal fuzzy contexts irreducible elements attribute characteristics attribute reduction directed graph

1 Introduction

The theory of formal concept analysis (FCA), proposed by Wille [1, 2], arouses mathematical approach for conceptual data analysis and knowledge processing. The main concern of FCA is the lattice structure, constructed by the formal concepts embedded in a concept hierarchy. As an effective tool for knowledge processing, FCA has been applied to a variety of fields such as information retrieval, knowledge discovery, data mining, machine learning, software engineering, etc. [3–8 , 17].

FCA is formulated on the basis of a formal context. In recent years, many people have learned theoretical investigations and practical applications of FCA. However, only crisp attributes are suitable for the formal context. In practical problems, formal fuzzy context are more common than their crisp counterparts. Several extensions of FCA theory via fuzzy logic reasoning or fuzzy set theory have been attempted over the years. For instance, Belohlavek [9] proposed fuzzy concepts based on a residuated lattice, and the proposed fuzzy concept lattices have almost all properties in classical concept lattice. Based on properties of m-polar fuzzy graphs, Ghorai and Pal [10, 11] discussed the applications. Medina and Ojeda-Aciego [12] developed the so-called t-concept lattice as a set of triples associated to graded tabular information interpreted in a non-commutative fuzzy logic. From the perspective of fuzzy graphs, Sarwar and Akram [13, 14] gave the application of m-Polar Fuzzy Concept Lattic and the metheod for computing strength of competition. On the other hand, Krajci [8] proposed a “one-side fuzzy concept”, and the crisply generated fuzzy concept lattice is isomorphic to the one-side fuzzy concept lattice [15, 16].

As is well known, knowledge reduction is an important issue by reducing attributes and objects while the concept lattice obtained from the reduced context is isomorphic to the induced from the original context. In the past decades, there have been a rapid growth of interests in knowledge reduction in FCA [1 , 18–24]. Hence, it is more meaningful to study the knowledge reduction in a formal fuzzy context which has a simpler. A little research has been done on attribute reduction in formal fuzzy contexts [20 , 32–34]. For instance, Shao [26] proposed a method for data reduction using meet-irreducible elements and attribute characteristics in formal fuzzy context. Since Wei [27] have studied the irreducible element judgement theory based on pictorial diagrams, the graph theory plays an important role in studying concepts. Up to now, many models of graphs have been proposed [40]. At the same time, Fuzzy graph theory is one of the developing area of research, which has a variety of applications in different fileds. A fuzzy set is an important mathematical structure to represent a collection of objects whose boundary is vague. There are some interesting applications of fuzzy graphs [35 –39].

However, we find that there are some lacks in finding meet-irreducible elements in formal fuzzy contexts. In order to deal with these problems, we will compare to the classical formal contexts and obtain irreducible elements and attribute characteristics combining with a directed graph on the basis of the nation of “one-side fuzzy concept” in formal fuzzy contexts. With the assistant of directed graphs, we propose judgment theorems of meet-irreducible elements and give corresponding algorithms for core attributes, relatively necessary attributes and unnecessary attributes. The proposed approach to compute attribute reduction based on the directed graph is an improvement to Shao’s method.

The paper is organized as follows. To facilitate our discussion, basic notions of fuzzy logic with their related work and graph theory are firstly introduced in Section 2. In Section 3, we introduce the directed graph and obtain the judgment theorems of meet-irreducible elements based on some properities of the directed graph in formal fuzzy contexts. In Section 4, using the directed graph, we analyze attribute characteristics and make up the corresponding algorithms in formal fuzzy contexts. After that, An attribute reduction method and the corresponding algorithm of formal fuzzy contexts are put forward in Section 5. We demonstrate the experiments using the proposed method with example. At the final part-Section 6, it concludes this paper and points out our further works.

2 Preliminaries

In this section, we review some basic notions and fuzzy-crisp formal concepts as well as the corresponding fuzzy-crisp concept lattice, and then give some notions about graphs which are used in this paper.

2.1 Fuzzy-crisp concept lattices

To promote our discussion, we firstly recall some relevant notions of fuzzy logic, and then discuss some properties of the crisply generated concept lattices.

Definition 2.1. [29] A complete residuated lattices is a structure L = (L, ∧ , ∨ , ⊗ , → , 0, 1) such that

(L, ∧ , ∨ , 0, 1) is a complete lattices with the least element 0 and the great element 1;

(L, ⊗ , 0, 1) is a commutative monoid, i.e, ⊗ is commutative, associative, and a ⊗ 1 =1 ⊗ a = a for each a ∈ L;

⊗, → from an adjoint pair, i.e. x ⊗ y ≤ z iff x ≤ y → z hold for all x, y, z ∈ L.

In what follows, the complete residuated lattices L = (L, ∧ , ∨ , ⊗ , → , 0, 1) is fixed with the supporting set [0,1] i.e. L = [0,1]. The notions of a residuated lattices provides a very general truth structure for fuzzy logic and fuzzy set theory.

Let L be a residuated lattice and U a nonempty set. For X, Y ∈ L^U, X ⊆ Y if and only if X (x) ≤ Y (x) for all x ∈ U. operations ∧ and ∨ on L^U are defined as follows: $\begin{matrix} (X \land Y) (x) & = & X (x) \land Y (x), \forall x \in U; \\ (X \lor Y) (x) & = & X (x) \lor Y (x), \forall x \in U . \end{matrix}$

A formal fuzzy context is a triple $(U, R, \tilde{I})$ , where U and R are respectively, the object set and the attribute set, and $\tilde{I} \in L^{U \times R}$ is an L-fuzzy relation between U and R. In this paper, we assume that both U and R are finite. The following illustrative example is an extension of the formal fuzzy contexts in [30].

Let U be a finite and non-empty set called the universe of discourse. The class of all subsets (respectively, fuzzy subsets) of U will be donated by P (U). For any ${\tilde{X}}_{1}, {\tilde{X}}_{2} \in L^{U}$ , ${\tilde{X}}_{1} \subseteq {\tilde{X}}_{2}$ iff ${\tilde{X}}_{1} (x) \leq {\tilde{X}}_{2} (x) \forall x \in U$ , and operations ∧ and ∨ on L^U are given by $\begin{matrix} ({\tilde{X}}_{1} \land {\tilde{X}}_{2}) (x) = {\tilde{X}}_{1} (x) \land {\tilde{X}}_{2} (x); \\ ({\tilde{X}}_{1} \lor {\tilde{X}}_{2}) (x) = {\tilde{X}}_{1} (x) \lor {\tilde{X}}_{2} (x) . \end{matrix}$

Example 1. The ideas of formal fuzzy contexts can be illustrated by an example. A college has a simple survey of college students about the condition of physical quality. There are six students extracted from college: a, b, c, d, e, h. The physical quality of students is divided into five conditions: worse, bad, good, better, best. According to the result of the survey, a formal fuzzy context can be obtained, which is written as $FC = (U, R, \tilde{I})$ . Then, Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context with U = {x₁, x₂, x₃, x₄, x₅}, R = {a, b, c, d, e, h} and the fuzzy relation $\tilde{I}$ is defined as Table 1.

Table 1
A formal fuzzy context

U a b c d e h

x ₁ 0.5 0.7 0.7 0.5 0.7 0.5

x ₂ 0.6 0.7 1.0 0.5 1.0 0.6

x ₃ 1.0 0.9 1.0 0.1 1.0 0.9

x ₄ 1.0 0.9 0.9 0.1 0.9 0.9

x ₅ 1.0 0.9 0.9 0.1 0.9 0.9

U	a	b	c	d	e	h
x ₁	0.5	0.7	0.7	0.5	0.7	0.5
x ₂	0.6	0.7	1.0	0.5	1.0	0.6
x ₃	1.0	0.9	1.0	0.1	1.0	0.9
x ₄	1.0	0.9	0.9	0.1	0.9	0.9
x ₅	1.0	0.9	0.9	0.1	0.9	0.9

While (x₁: worse, x₂: bad, x₃: good x₄: better, x₅: best).

Definition 2.2. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context. For $\tilde{X} \in L^{U},$ B ∈ P (R), the operator g : L^U → P (R) and f : P (R) → L^U are defined respectively as follows: $\begin{matrix} g (\tilde{X}) = {a \in R | \forall x \in U, \tilde{X} (x) \leq \tilde{I} (x, a)}, \\ f (B) (x) = \land_{a \in B} \tilde{I} (x, a), x \in U . \end{matrix}$

By Definition 2, the following properties can be obtained.

Property 1.1. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context, $\tilde{X}, {\tilde{X}}_{1}, {\tilde{X}}_{2}, {\tilde{X}}_{i} \in L^{U}$ , and B, B₁, B₂, B_i ∈ P (R), i ∈ J(J is an index set). $\begin{matrix} (i) {\tilde{X}}_{1} \leq {\tilde{X}}_{2} \Rightarrow g ({\tilde{X}}_{1}) \subseteq g ({\tilde{X}}_{2}), B_{1} \subseteq B_{2} \Rightarrow \\ f (B_{2}) \leq f (B_{1}); \\ (ii) \tilde{X} \leq f \circ g (\tilde{X}), B \subseteq g \circ f (B); \\ (iii) g (\tilde{X}) \leq g \circ f \circ g (\tilde{X}), f (B) = f \circ g \circ f (B); \\ (iv) g (\lor_{i \in J} {\tilde{X}}_{i}) = \cap_{i \in J} g ({\tilde{X}}_{i}), f (\cup_{i \in J} B_{i}) \subseteq \land_{i \in J} \\ f (B_{i}) . \end{matrix}$

For a formal fuzzy context $FC = (U, R, \tilde{I})$ , a pair $(\tilde{X}, B) \in L^{U} \times P (R)$ satisfying $\tilde{X} = f (B)$ and $B = g (\tilde{X})$ is called a fuzzy-crisp concept of $(U, R, \tilde{I})$ (see [16]), For a set of objects $\tilde{X} \in L^{U}$ and a set of attributes R ∈ P (R), from Property 1(iii), we observe that $(f \circ g (\tilde{X}), g (\tilde{X}))$ and (f (B) , g ∘ f (B)) are fuzzy -crisp concepts. For two fuzzy-crisp concepts $({\tilde{X}}_{1}, B_{1})$ and $({\tilde{X}}_{2}, B_{2})$ , the partial order ≤ is defined by $({\tilde{X}}_{1}, B_{1}) \leq ({\tilde{X}}_{2}, B_{2})$ iff ${\tilde{X}}_{1} \subseteq {\tilde{X}}_{2}$ (or equivalently B₁ ⊇ B₂).

All the fuzzy-crisp concepts of $(U, R, \tilde{I})$ from a complete lattice denoted as $L (\tilde{U}, R, \tilde{I})$ , in which the infimum and supremum are defined as follows: $\begin{matrix} ({\tilde{X}}_{1}, B_{1}) \lor ({\tilde{X}}_{2}, B_{2}) \\ = (f \circ g ({\tilde{X}}_{1} \lor {\tilde{X}}_{2}), B_{1} \cap B_{2}) \\ = (f (B_{1} \cap B_{2}), B_{1} \cap B_{2}); \\ ({\tilde{X}}_{1}, B_{1}) \land ({\tilde{X}}_{2}, B_{2}) \\ = ({\tilde{X}}_{1} \land {\tilde{X}}_{2}, g \circ f (B_{1} \cup B_{2})) \\ = ({\tilde{X}}_{1} \land {\tilde{X}}_{2}, g ({\tilde{X}}_{1} \land {\tilde{X}}_{2})) . \end{matrix}$

Example 2. On the basis of the Table 1, all the corresponding fuzzy-crisp formal concepts determined by operator g and f are listed in Table 2 and the fuzzy-crisp concept lattice as $L (\tilde{U}, R, \tilde{I})$ is depicted in Fig. 1.

Fig.1

$L (\tilde{U}, R, \tilde{I})$ .

Table 2

Fuzzy-crisp formal concepts derived from Table 1

	(Objects, Attributes)
C₁	$({x_{1}^{1.0}, x_{2}^{1.0}, x_{3}^{1.0}, x_{4}^{1.0}, x_{5}^{1.0}}, φ)$
C₂	$({x_{1}^{0.7}, x_{2}^{1.0}, x_{3}^{1.0}, x_{4}^{0.9}, x_{5}^{0.9}}, {c, e})$
C₃	$({x_{1}^{0.7}, x_{2}^{0.7}, x_{3}^{0.9}, x_{4}^{0.9}, x_{5}^{0.9}}, {b, c, e})$
C₄	$({x_{1}^{0.5}, x_{2}^{0.6}, x_{3}^{1.0}, x_{4}^{1.0}, x_{5}^{1.0}}, {a})$
C₅	$({x_{1}^{0.5}, x_{2}^{0.6}, x_{3}^{1.0}, x_{4}^{0.9}, x_{5}^{0.9}}, {a, c, e})$
C₆	$({x_{1}^{0.5}, x_{2}^{0.5}, x_{3}^{0.9}, x_{4}^{0.9}, x_{5}^{0.9}}, {a, b, c, e, h})$
C₇	$({x_{1}^{0.5}, x_{2}^{0.5}, x_{3}^{0.1}, x_{4}^{0.1}, x_{5}^{0.1}}, {a, b, c, d, e, h})$

2.2 Graphs

In this paper, all used graphs are assumed to be finite. The definition of a directed graph D is referred to Bonby and Murty [31].

Definition 2.3. [31] If a is an arc and φ (a) = (u, v), then a is said to join u to v. The vertex u (v) is the tail (head) of a; They are the two ends of a. Occasionally, D is referred to the arc as an edge.

The number of arcs in D is denoted by |A (D) |. The vertices which dominated a vertex v are its in-neighbors, those which are dominated by the vertex its out-neighbors. These sets are denoted by N^- (v) and N⁺ (v), respectively.

Definition 2.4. [31] (1) The degree of d (v) of a vertex v in a digraph D is the degree of v in G (D). The indegree d^- (v) of v in D is the number of arcs with head v, and the outdegree d⁺ (v) of v is the number of arcs with tail v.

(2) If v is a vertex of a graph D, we may obtain a graph on |V (D) -1| vertics, by deleting from D the vertex v together with all edges incidents with v. The resulting graph is denoted by D ∖ {v}.

3 Attribute reduction based on the directed graph in formal fuzzy contexts

To realize the visualization of searching concepts in a context. Similarly, to realize the visualization of attribute reduction in a formal fuzzy context, the main outline of our work is the following:

To establish a directed graph $D (U, R, \tilde{I})$ on a formal fuzzy context $(U, R, \tilde{I})$ .

To find all the meet-irreducible elements in $L (\tilde{U}, R, \tilde{I})$ , all the fuzzy-crisp concept can be represented as the intersection of the meet- irreducible elements.

Explore attribute characteristics using the directed graph and give the theorems and the corresponding algorithms for judging the attribute characteristics in formal fuzzy context.

Give an approach to calculate the attribute reduction.

3.1 Directed graph in formal fuzzy contexts

In this section, we give the definition of the directed graph combining with graph theory, and present its properties.

Definition 3.1. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context.

The directed graph $D (U, R, \tilde{I})$ of $(U, R, \tilde{I})$ is defined as follows. The vertices set $V (D (U, R, \tilde{I}))$ is R and the edges set $E (D (U, R, \tilde{I}))$ is defined for a, b ∈ R as:

If ∀ x ∈ U, $\tilde{I} (x, a) = \tilde{I} (x, b)$ , then there is a bi-arc joining a and b, that is, a ↔ b.

If ∀ x ∈ U, $\tilde{I} (x, a) \leq \tilde{I} (x, b)$ , then there is an arc joining a to b, that is, a → b.

The Correlation matrix $M (D (U, R, \tilde{I}))$ is given as:

In any case, g (v_i, v_i) =1, the double-arrow v_i ↔ v_j, then g (v_i, v_j) = g (v_j, v_i) =1.

$\begin{matrix} N^{+} (v_{i}) & = & {v_{j} \in R | v_{i} \to v_{j}}; \\ O (v_{i}) & = & {v_{j} \in R | v_{i} \leftrightarrow v_{j}} . \end{matrix}$

A directed graph is proposed in a formal fuzzy context, and by | · | we denote the cardinality of set.

Example 3. Continuing from the Example 1 of the Table 1, we can obtain that $\begin{matrix} a & = & x_{1}^{0.5} + x_{2}^{0.6} + x_{3}^{1.0} + x_{4}^{1.0} + x_{5}^{1.0}; \\ b & = & x_{1}^{0.7} + x_{2}^{0.7} + x_{3}^{0.9} + x_{4}^{0.9} + x_{5}^{0.9}; \\ c & = & x_{1}^{0.7} + x_{2}^{1.0} + x_{3}^{1.0} + x_{4}^{0.9} + x_{5}^{0.9}; \\ d & = & x_{1}^{0.5} + x_{2}^{0.5} + x_{3}^{0.1} + x_{4}^{0.1} + x_{5}^{0.1}; \\ e & = & x_{1}^{0.7} + x_{2}^{1.0} + x_{3}^{1.0} + x_{4}^{0.9} + x_{5}^{0.9}; \\ h & = & x_{1}^{0.5} + x_{2}^{0.6} + x_{3}^{0.9} + x_{4}^{0.9} + x_{5}^{0.9}; \end{matrix}$

According to Definition 3.1, the directed graph $D (U, R, \tilde{I})$ appears, which is shown in Fig. 2. And we can have the correlation matrix $M (D (U, R, \tilde{I}))$ . $M (D (U, R, \tilde{I})) = [\begin{matrix} 1 & 0 & 0 & - 1 & 0 & - 1 \\ 0 & 1 & 1 & - 1 & 1 & - 1 \\ 0 & - 1 & 1 & - 1 & 1 & - 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & - 1 & 1 & - 1 & 1 & - 1 \\ 1 & 1 & 1 & - 1 & 1 & 1 \end{matrix}]$

Fig.2

$D (U, R, \tilde{I})$ .

A formal fuzzy context has two sets: objects and attributes. This illustrates that a directed graph cannot completely reflect a formal fuzzy context. However the meet-irreducible elements and the attribute characteristics are obtained from the directed graph.

3.2 The meet-irreducible elements

Irreducible elements play a vital role in the process of attribute reduction. In this section, we introduce the notion of meet-irreducible elements constituted by the fuzzy-crisp formal concepts, and present its properties.

Lemma 3.1. Let $FC = (U, R, \tilde{I})$ be a fuzzy formal context and a ∈ R, Then, $\begin{matrix} f (N^{+} (a)) (x) & = & f (a) (x), \forall x \in U . \\ f (O (a)) (x) & = & f (a) (x), \forall x \in U . \end{matrix}$

Proof. According to Definition 3.1, we know that N⁺ (a) = {b ∈ R|a → b}, then ∀ x ∈ U, $\tilde{I} (x, a) \leq \tilde{I} (x, b)$ .

When O (a) = {b ∈ R|a ↔ b}, then $\forall x \in U, \tilde{I} (x, a) = \tilde{I} (x, b) .$

By Definition 2.2 and property 1.1, we obtained $\begin{matrix} f (N^{+} (a)) (x) & = & \underset{b \in N^{+} (a)}{\land} \tilde{I} (x, b) \\ = & f (a) (x) \forall x \in U . \\ f (O (a)) (x) & = & \underset{b \in O (a)}{\land} \tilde{I} (x, b), \\ = & f (a) (x), \forall x \in U . \end{matrix}$

Theorem 3.1. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then, (f (a) , N⁺ (a) ∪ O (a)) is a fuzzy-crisp formal concept of FC and N⁺ (a) ∪ O (a) = g ∘ f (a).

Proof. From Lemma 3.1, we can obtain that $\begin{matrix} g \circ f (N^{+} (a) \cup O (a)) \\ = g \circ (f (N^{+} (a)) \land f (O (a))) = g \circ f (a) \end{matrix}$

By Property 1 (ii), we have $N^{+} (a) \cup O (a) \subseteq g \circ f (N^{+} (a) \cup O (a)) = g \circ f (a)$ (1)

For another, for any b ∈ g ∘ f (N⁺ (a) ∪ O (a)),

By Property 1.1 (i) and (iii), we conclude that $f (a) = f \circ g \circ f (N^{+} (a) \cup O (a)) \leq f ({b}) = f (b),$

That is f (a) ≤ f (b), which means $f (a) = \tilde{I} (x, a) \leq \tilde{I} (x, b) = f (b) \forall x \in U .$

Hence, b ∈ N⁺ (a). and from which we can conclude that $N^{+} (a) \cup O (a) \supseteq g \circ f (N^{+} (a) \cup O (a))$ (2)

It follows from Equations (1 and 2) that g ∘ f (N⁺ (a) ∪ O (a)) = g ∘ f (a) = N⁺ (a) ∪ O (a) and (f (a) , N⁺ (a) ∪ O (a)) is a fuzzy-crisp formal concept.

Definition 3.2. [1] Let L be a finite lattices. For any a ∈ L, define a^* by a^* = ∧ {x ∈ L|a < x}. We say a^* is a meet-irreducible elements.

Lemma 3.2. [27] Let L be a finite lattices. Then, every elements in L is meet of some meet-irreducible elements.

It should be noted that every fuzzy-crisp concept $(\tilde{X}, B)$ in the concept lattice $L (\tilde{U}, R, \tilde{I})$ can be represented as a meet of attribute concepts of its intention, that is, $(\tilde{X}, B) = \underset{b \in B}{\land} (f (b), g \circ f (b))$

Theorem 3.2. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then, the attribute concept (f (a) , N⁺ (a) ∪ O (a)) is a meet-irreducible element in $L (\tilde{U}, R, \tilde{I})$ if |N⁺ (a) |≤1.

Proof. Assume that |N⁺ (a) |≤1.

If |N⁺ (a) |=0. Then N⁺ (a) has no attribute b in R. Hence, by Definition 3.2, (f (a) , N⁺ (a) ∪ O (a)) itself is a meet-irreducible element.

If |N⁺ (a) |=1, then N⁺ (a) has only one attribute b, and we denote it as (f (b) , N⁺ (b) ∪ O (b)). By Definition 3.1, we know that f (a) ≤ f (b). It is evident that $(f (a), N^{+} (a) \cup O (a)) \leq (f (b), N^{+} (b) \cup O (b)) .$

By Definition 3.2, we can conclude that (f (a) , N⁺ (a) ∪ O (a)) is a meet-irreducible element.

Theorem 3.3. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then, the attribute concept (f (a) , N⁺ (a) ∪ O (a)) is a meet-irreducible element in $L (\tilde{U}, R, \tilde{I})$ , if |N⁺ (a) | = | {b₁, ⋯ , b_n} |>1 and $\land_{i = 1}^{n} f (b_{i}) \neq f (a) .$

Proof. Assume that |N⁺ (a) | = | {b₁, ⋯ , b_n} |>1 and $\land_{i = 1}^{n} f (b_{i}) \neq f (a) .$

If |N⁺ (a) | = | {b₁, ⋯ , b_n} |>1, then according to the Definition 3.1, we can know that $\begin{matrix} N^{+} (a) = {b_{1}, \dots, b_{n}}, n > 1 and \\ f (b_{1}) > f (a), \dots, f (b_{n}) > f (a) . \end{matrix}$

It is evident that ∀ i, = 1, ⋯ , n . $(f (a), N^{+} (a) \cup O (a)) < (f (b_{i}), N^{+} (b_{i}) \cup O (b_{i})) .$ (3)

That is $\land_{i = 1}^{n} f (b_{i}) \neq f (a)$ , which means $\begin{matrix} \land_{i = 1}^{n} (f (b_{i}), N^{+} (b_{i}) \cup O (b_{i})) \\ \neq (f (a), N^{+} (a) \cup O (a)) . \end{matrix}$

By Definition 3.2, we can conclude that (f (a) , N⁺ (a) ∪ O (a)) is a meet-irreducible element.

From the directed graph in a formal fuzzy context, We can compute all attribute concepts to judge whether or not an attribute concept is a meet-irreducible element in $L (\tilde{U}, R, \tilde{I})$ .

Example 4. Continuing from the Example 3, from the directed graph in Fig. 2, we can obtain that $\begin{matrix} | N^{+} (a) | = | {\emptyset} | = 0, \\ | N^{+} (b) = {c, e} | = 2, | N^{+} (c) | = | {\emptyset} | = 0, \\ | N^{+} (d) = {a, b, c, e, h} | = 5, \\ | N^{+} (e) | = | \emptyset | = 0, \\ | N^{+} (h) = {a, b, c, e} | = 4 \end{matrix}$

Due to |N⁺ (a) |=0, |N⁺ (c) |=0, |N⁺| (e) |=0, by Theorem 3.2, we can conclude that

(f (c) , N⁺ (c) ∪ O (c)) = (f (c) , ce) and

(f (a) , N⁺ (a) ∪ O (a)) = (f (a) , a) are meet-irreducible elements.

|N⁺ (b) | = | {c, e} |=2 > 1, and f (c) ∧ f (e) ≠ f (b)

|N⁺ (d) | = | {a, b, c, e, h} |=5 and

f (c) ∧ f (e) ∧ f (a) ∧ f (b) ∧ f (h) ≠ f (d)

|N⁺ (h) | = | {a, b, c, e} |=4 and

f (a) ∧ f (b) ∧ f (c) ∧ f (e) = f (h)

by Theorem 3.3., we can conclude that (f (b) , bce) and (f (d) , abcdeh) are meet-irreducible elements.

3.3 Explore attribute characteristics using directed graph in formal fuzzy contexts

According to the importance of attributes, we classify the attributes into three types: core attributes, relatively necessary attributes and unnecessary attributes in parallel with the definitions of attribute characteristics in rough set theory. we will establish judgment theorems for classifying attributes. Moreover, we will propose the corresponding algorithms for the characteristic of the three attribute types stated above.

Definition 3.3. [26] Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and B ⊆ R. We say that B is a consistent set of $L (\tilde{U}, R, \tilde{I})$ , if $M_{R}^{E} = M_{B}^{E}$ . If B is a consistent set and there is no proper subset C ⊆ B such that C is a consistent set, then B is referred to as an attribute reduct of $L (\tilde{U}, R, \tilde{I})$ .

Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context. By M we denoted the set of all meet-irreducible elements of $L (\tilde{U}, R, \tilde{I})$ , by M^E we denoted the set of extents of M, i.e. $M^{E} = {f (a) | (f (a), N^{+} (a) \cup O (a)) \in M} .$

Definition 3.4. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. We say a is a core attribute in $L (\tilde{U}, R, \tilde{I})$ if $M_{R - {a}}^{E} \neq M_{R}^{E}$ ; a is referred to as unnecessary in $L (\tilde{U}, R, \tilde{I})$ if $f (a) \notin M_{R}^{E}$ ; a is referred to as relatively necessary in $L (\tilde{U}, R, \tilde{I})$ if $M_{R - {a}}^{E} = M_{R}^{E}$ and $f (a) \in M_{R}^{E}$ . By Red(FC), we denote the set of all attribute reducts of $FC = (U, R, \tilde{I})$ .

From the results stated about, the core attributes are included in every reduct. A relatively necessary attribute is included in some reducts and unnecessary attribute is not in any reducts. Thus, according to the attribute reducts, the attribute set R is divided into three disjoint parts:

Core attribute set C = ∩ Red (FC);

Relatively necessary attribute set K = ∪ Red (FC) - ∩ Red (FC);

Unnecessary attributes set U = R - ∪ Red (FC).

Theorem 3.4. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then a is an unnecessary attribute if

|N⁺ (a) | = | {b₁, ⋯ , b_n} |>1 and $\land_{i = 1}^{n} f (b_{i}) = f (a)$ .

Proof. Assume that |N⁺ (a) | = | {b₁, ⋯ , b_n} |>1 and $\land_{i = 1}^{n} f (b_{i}) = f (a)$ .

According to Theorem 3.3, we can know that (f (a) , N⁺ (a) ∪ O (a)) is not a meet-irreducible element, then, $f (a) \notin M_{R}^{E}$ . By Definition 3.4, we conclude that a is an unnecessary attribute.

Based on the judgment Theorem 3.4, one can get all unnecessary attribute using the directed graph in a formal fuzzy context. The produce for computing unnecessary attributes is shown in algorithm 1. Then, the time complexity of Algorithm 1 is $O (\frac{| R |^{2}}{2} | U |)$ .

Algorithm 1
Computing the unnecessary attribute set of $L (\tilde{U}, R, \tilde{I})$

Input: A formal fuzzy context $FC = (\tilde{U}, R, I)$

Output: U // the unnecessary attribute set;

1: Initialize U← ∅;

2: Compute the family set {N⁺ (a) : a ∈ R};

3: for each a ∈ Rdo

4: Compute |N⁺ (a) | = | {b₁, …, b_n} |;

5: if |N⁺ (a) |>1 and $\cap_{i = 1}^{n} f (b_{i}) = f (a)$ then

6: U ← U_∪ {a};

7: end if

8: end if

9: return U_k.

Example 5. Continuing from the Example 4, we can know that |N⁺ (b) |>1, |N⁺ (d) |>1, |N⁺ (h) |>1.

For N⁺ (b) = {c, e} and f (c) ∩ f (e) ≠ f (a); N⁺ (d) = {a, b, c, e, h} and f (a) ∩ f (b) ∩ f (c) ∩ f (e) ∩ f (h) ≠ f (d); since a, d are not unnecessary attributes.

For N⁺ (h) = {a, b, c, e} and f (a) ∧ f (b) ∧ f (c) ∧ f (e) = f (h).

By Theorem 3.4, we can conclude that h is an unnecessary attribute in $L (\tilde{U}, R, \tilde{I})$ .

Theorem 3.5. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then a is a relatively necessary attribute if |N⁺ (a) |≤1 and |O (a) |>1.

Proof. Assume that |N⁺ (a) |≤1 and |O (a) |>1.

By Theorem 2, we can conclude that (f (a) , N⁺ (a) ∪ O (a)) ∈ M_R and ∃ b ∈ R - {a} such that f (a) = f (b).

According to the Definition 3.4, we know that $f (a) \in M_{R}^{E}$ and $M_{R}^{E} = M_{R - {a}}^{E}$ . Therefore, a is a relative necessary in $L (\tilde{U}, R, \tilde{I})$ .

The pseudocode of the procedure for computing the relatively necessary attributes is shown in Algorithm 2, and its time complexity is $O (\frac{| R |^{2}}{2} | U |)$ .

Algorithm 2

Computing the relatively necessary attribute set of $L (\tilde{U}, R, \tilde{I})$

Input: A formal fuzzy context

FC = (U, R, \tilde{I})

;

Output: R // the relatively necessary attribute set;

1: Initialize R← ∅;

2: Compute the family set {N⁺ (a) : a ∈ R} and

{O (a) : a ∈ R};

3: for each a ∈ Rdo

4: Compute |N⁺ (a) | and |O (a) |;

5: if |N⁺ (a) |≤1 and |O (a) |>1 then

6: R ← R_∪ {a};

7: end if

8: end if

9: retun R_k.

Example 6. Continuing from the Example 4, we know that |N⁺ (c) |=0 ≤ 1 and |O (c) = {c, e} |>1. By Theorem 3.5, we can conclude that c and e are relative necessary attributes in $L (\tilde{U}, R, \tilde{I})$ .

Theorem 3.6. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context and a ∈ R. Then a is a core necessary attribute if |N⁺ (a) |≤1 and |O (a) |=1.

Proof. Assume that |N⁺ (a) |≤1 and |O (a) |=1.

By Theorem 3.2, we can conclude that (f (a) , N⁺ (a) ∪ O (a)) ∈ M_R, and there has no b ∈ R - {a} such that f (a) = f (b).

According to Definition 3.5, we know that $f (a) \in M_{R}^{E} and f (a) \neq f (b) (\forall b \in R - {a}),$

Then, $M_{R - {a}}^{E} \neq M_{R}^{E}$ . Hence, a is a core attribute.

Based on Theorem 3.6, one can obtained all core attributes. The pseudocode of the procedure for computing the core attributes is shown in Algorithm 3, and its time complexity is $O (\frac{| R |^{2}}{2} | U |)$ .

Algorithm 3

Computing the core attribute set of $L (\tilde{U}, R, I)$

Algorithm 3 Computing the core attribute set of

Input: A formal fuzzy context

FC = (U, R, \tilde{I})

;

Output: C_k// the core attribute set;

1: Initialize C← ∅;

2: Compute the family set{N⁺ (a) : a ∈ R} and

{O (a) : a ∈ R};

3: for each a ∈ Rdo

4: Compute |N⁺ (a) | and |O (a) |;

5: if |N⁺ (a) |≤1 and |O (a) |=1 then

6: C ← C_∪ {a};

else if |N⁺ (a) |>1,

\cap_{i = 1}^{n} f (b_{i}) = f (a)

and |O (a) |=1

C ← C_∪ {a};

7: end if

8: end if

9: retun C_k.

Example 7. Continuing from the Example 4, we can know that $| N^{+} (a) | = | {\emptyset} | = 0 and | O (a) = {a} | = 1 .$

Hence, a is a core attribute.

For N⁺ (b) = {c, e} =2 and |O (b) = {b} |=1, then $f (c) \land f (e) \neq f (b)$

|N⁺ (d) | = | {a, b, c, e, h} |=5 and |O (d) = {d} |=1, $f (c) \land f (e) \land f (a) \land f (b) \land f (h) \neq f (d) .$

By Theorem 3.6, we can conclude that a, b and d are core attributes in $L (\tilde{U}, R, \tilde{I})$ .

3.4 Attribute reduction in formal fuzzy contexts

As we know, discernibility function is a useful tool in the calculation of all reducts of an information system in rough set theory. In order to compute all attribute reducts, we construct distribution function of formal fuzzy contexts based on fuzzy-crisp concept lattices in this section. Then we propose an approach and an algorithm for attribute reduction in a formal fuzzy context.

Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context. By ∨ we denote the disjunction of all literals, and by ∧ we denote the conjunction of all literals. A distribution function D_F for the fuzzy context is a Boolean function defined by $F_{K} = \land \underset{a \in R - I_{k}}{\lor} (O (a)) = \land_{k = 1}^{t} (\lor_{s = 1}^{z_{k}} a_{s}),$

Where $\land_{s = 1}^{z_{k}} a_{s}$ (k ≤ t) are all the prime implicants of F_K.

Theorem 3.7. Let $FC = (U, R, \tilde{I})$ be a formal fuzzy context. Then, an attribute subset C is an attribute reduct of $L (\tilde{U}, R, \tilde{I})$ iff ∧_c∈Cc is a prime implicant of the distribution function F_K.

We denote W_k = {a_s|s = 1, ⋯ , z_k}. By Theorem 3.7, we obtain that {W_k|k = 1, ⋯ , t} is the set of all attribute reducts of $L (\tilde{U}, R, \tilde{I})$ .

Using Theorem 3.7, one can obtained all the attribute reducts of $L (\tilde{U}, R, \tilde{I})$ . The pseudocode of the procedure for computing all attribute reducts is shown in Algorithm 4, and its time complexity is $O (\frac{| R |^{2}}{2} | U | + 2^{\frac{| R |}{2}})$ .

Algorithm 4
Computing all attribute reduction of $L (\tilde{U}, R, \tilde{I})$

Input: A formal fuzzy context $(U, R, \tilde{I})$ ;

Output: Red(FC) // the set of attribute reducts of $L (\tilde{U}, R, \tilde{I})$ ;

1: Initialize U_k← ∅;

2: Compute the family set{N⁺ (a) : a ∈ R} and

{O (a) : a ∈ R};

3: for each a ∈ Rdo

4: Compute |N⁺ (a) | = | {b₁, ⋯ , b_n} |;

5: if |N⁺ (a) |>1 and $\cap_{i = 1}^{n} f (b_{i}) = f (a)$ then

6: U_k ← U_k∪ {a};

7: if |N⁺ (a) |≤1;

8: U_k ← U_k;

9: end if

10: end for

11: Compute $F_{K} = \land (\underset{a \in R - U_{k}}{\lor} O (a))$ ;

12: Compute $F_{K} = \lor_{K = 1}^{s} (\land_{t}^{q} a_{t})$ ;

13: set D_k = {a_t|t ≤ q} and Red (K) = {D_K|K ≤ s};

14: return Red (K).

Example 8. Continuing from the Example 4 and Example 5, we obtain U_K = {h}, i.e., h is the unique unnecessary attribute in $L (\tilde{U}, R, \tilde{I})$ .

Combing this fact with the results in Example 3, we have $\begin{matrix} F_{k} & = & \land \underset{a \in R - I_{k}}{\lor} (O (a)) = \land \underset{a \in R - {h}}{\lor} (O (a)) \\ = & a \land b \land d \land (a \lor c) \\ = & (a \land b \land c \land d) \lor (a \land b \land d \land e) . \end{matrix}$

Therefore, {a, b, c, d} and {a, b, d, e} are relative attribute reducts in $L (\tilde{U}, R, \tilde{I})$ .

4 Conclusion

In this paper, we discuss the issue of attribute reduction using the directed graph based on the fuzzy-crisp concept in formal fuzzy contexts. A reducible attribute must have a special characterization in some path in the directed graph. According to the important of the attributes, we have classified the attributes into three types: core attributes, relatively necessary attributes and unnecessary attributes. Therefore, we obtain the meet-irreducible elements and the attribute characteristics combining to the properties of the directed graph such as the optimal path in a directed graph.

Most importantly, we have given the judgment theorems and the corresponding algorithms for computing the three types of attribute sets. Finally, the proposed approaches and algorithms in this paper are used to conduct knowledge reduction in formal fuzzy contexts, which is complement to the existing methods. Studying on attribute reduction in a formal fuzzy context becomes more meaningful. Since an example is given as an application of the results of this paper, we hope that other researchers can obtain some good applications and consequences. As we know, fuzzy graph plays a vital role in many fileds. Therefore, we can try to study how to find the method of knowledge reduction using to fuzzy graph in our further works. There still remain some interesting problems worthy of our further researches.

Footnotes

Acknowledgments

The author sincerely acknowledges the financial support from the Nature Science Foundation of China (61572011) and Nature Science Foundation of Hebei Province (A201820117).

References

Ganter

and Willer

, Formal concept analysis: Mathematics foundations, Springer, Berlin, 1999.

Wille

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

(Ed), ordered sets, Reidel Dordrecht-Boston, 1982, pp. 445–470.

J.H.

, Mei

C.L.

, and Lv

Y.J.

, Knowledge reduction in real decision formal contexts, Information Sciences 189 (7) (2012), 191–207.

Dias

, Zairate

and Vieira

, Using iceberg concept lattices and implications implications rules to extract knowledge from ann, Intelligent Automation and Soft Computing 19 (3) (2013), 361–372.

Mao

, A graph-theoretic method to representing a concept lattices, Applied Mathematics and Information Sciences 8 (2) (2014), 553–561.

Medina

, Relating attribute reduction in formal, object-oriented and property-oriented concept lattices, Computers and Mathematics Application 64 (6) (2012), 1992–2002.

Mao

Y.J.

, Zhang

and Chen

M.R.

, Efficient attribute based encryption schemes for secure communications in cyber defense, Intelligent Automation and Soft Computing 22 (3) (2016), 397–403.

Y.J.

and Li

H.M.

, Strategy for mining association rule for web pages based on formal concept analysis, Application Soft Computing 10 (3) (2010), 772–783.

Belohlavek

, Lattices generated by binary fuzzy relations, pp. , Int Conf on Fuzzy Set Theory and Applications (1999), 11–19.

10.

Ghorai

, Pal

, A note on ”Regular bipolar fuzzy graphs, Neural Computing and Applications 21 (1) (2016), 197–205.

11.

Ghorai

and Pal

, Some isomorphic properties of m-polar fuzzy graphs with applications, Springer Plus 5 (1) (2016), 1–21.

12.

Medina

and Ojeda-Aciego

, Multi-adjoint t-concept lattices, Information Sciences 180 (5) (2010), 712–725.

13.

Akram

and Sarwar

, Transversals of m-polar fuzzy hypergraphs with applications, Journal of Intelligent and Fuzzy Systems 33 (1) (2017), 351–364.

14.

Sarwar

and Akram

, Certain algorithms for aomputing strength of competition in bipolar fuzzy graphs, International Journal of Uncertainty Fuzziness and Knowledge Based Systems 25 (6) (2017), 877–896.

15.

Belohlavek

and Vychodil

, What is a fuzzy concept lattice proceedings of international conferences on concept lattices and their applications, Springer (5) (2005), 34–45.

16.

Zhang

W.X.

, Ma

J.M.

and Fan

S.Q.

, Variable threshold concept lattices, Information Sciences 17 (22) (2007), 4883–4892.

17.

J.H.

, Huang

C.H.C.H.

, and Lin

C.H.

, An intensive on rule acquisition in formal decision contexts, Intelligent Automation and Soft Computing (2016), 1–15.

18.

Sarwar

and Akram

, Novel applications of m-Polar fuzzy concept lattic, New Mathematics and Natural Computation 13 (3) (2017), 261.

19.

Akram

and Waseem

, Certain metrics in m-polar fuzzy graphs, Mathematics and Natural Computation 12 (2) (2016), 135.

20.

L.F.

and Zhang

, Attribute reduction in fuzzy context concept lattices based on the T implication, Knowledge-Based Systems 23 (6) (2010), 497–503.

21.

Liu

, Shao

M.W.

and Zhang

W.X.

, Reduction method for method for concept lattices based on rough set theory and its application, Computers and Mathematics Application 53 (9) (2007), 1390–1410.

22.

J.S.

, Leung

and Wu

W.Z.

, Approaches to attribute reduction in concept lattices induced by axialities, Knowledge-Based System 23 (6), 504–511.

23.

Shao

M.W.

and Leung

, Relations between granular reduct and dominance reduct in formal contexts, Knowledge-Based System 65 (2014), 1–11.

24.

W.Z.

, Leung

and Mi

J.S.

, Granular computing and knowledge reduction in formal contexts, IEEE Transactions on Knowledge and Data Engineering 21 (10) (2009), 1461–1474.

25.

Shao

M.W.

, Yang

H.Z.

and Wu

W.Z.

, Knowledge reduction in formal fuzzy contexts, Knowledge based System 73 (2015), 265–275.

26.

, Shao

M.W.

and Wu

W.Z.

, A data reduction method in formal fuzzy contexts, International Journal of Machine Learning and Cybernetics (2016), 1–11.

27.

Wei

and Wang

, Granular transformation and irreducible element judgment theory based on pictorial diagrams, IEEE Transactions on Cybernetices 46 (2) (2016), 380–387.

28.

Jaoua

and Elloumi

, Galois connection, formal concepts and Galois lattices in real relations: Application in a real classifier, Journal of System and Software 60 (2) (2002), 149–163.

29.

Belohlavek

, Fuzzy galois connection, Mathematical Logic Quarterly 45 (4) (2015), 497–504.

30.

Wang

X.Z.

, Xing

H.J.

and Li

, A study on relationship between Generalization abilities and fuzziness of base classifiers in Ensemble learning, EEE Transaction on Fuzzy systems 23 (5) (2015), 1638–1654.

31.

Bondy

J.A.

, Murty

U.S.B.

, Graph theory. Springer, San FranCisico, 2008.

32.

Kumar

C.A.

and Srinivas

, Concepts lattice reduction using fuzzy k-means clustering, Expert System withApplications 37 (3) (2010), 2696–2704.

33.

Zhang

and Ren

H.L.

, Attribute topology of formal context, Journal of Chinese Computer Systems 14 (1) (2014), 1–37.

34.

Ghorai

and Pal

, Novel concepts of strongly edge irregular m-polar fuzzy graphs, International Journal of Applied and Computational Mathematics 3 (4) (2016), 1–12.

35.

Akram

and Luqman

, Certain networks models using single-valued neutrosophic directed hypergraphs, Journal of Intelligent and Fuzzy Systems 33 (1) (2017), 575–588.

36.

Ghorai

and Pal

, A study on m-polar fuzzy planar graphs, International Journal of Computing Science and Mathematics 7 (3) (2016), 283–292.

37.

Sarwar

and Akram

, An algorithm for computing certain metrics in intuitionistic fuzzy graph, Journal of Intelligent and Fuzzy Systems 30 (4) (2016), 2405–2416.

38.

Ghorai

and Pal

, Faces and dual of m-polar fuzzy planar graphs, Journal of Intelligent and Fuzzy Systems 31 (3) (2016), 2043–2049.

39.

Akram

and Nawaz

, Fuzzy soft graphs with application, Journal of Intelligent and Fuzzy Systems 30 (6) (2016), 3619–3632.

40.

Mao

, Representing attribute reduction and concepts in concept lattice using graphs, Soft Computing 21 (24) (2017), 7293–7311.

Attribute reduction based on directed graph in formal fuzzy contexts

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Fuzzy-crisp concept lattices

Table 1 A formal fuzzy context U a b c d e h x 1 0.5 0.7 0.7 0.5 0.7 0.5 x 2 0.6 0.7 1.0 0.5 1.0 0.6 x 3 1.0 0.9 1.0 0.1 1.0 0.9 x 4 1.0 0.9 0.9 0.1 0.9 0.9 x 5 1.0 0.9 0.9 0.1 0.9 0.9

3 Attribute reduction based on the directed graph in formal fuzzy contexts

3.1 Directed graph in formal fuzzy contexts

Footnotes

Acknowledgments

References

Table 1
A formal fuzzy context

U a b c d e h

x ₁ 0.5 0.7 0.7 0.5 0.7 0.5

x ₂ 0.6 0.7 1.0 0.5 1.0 0.6

x ₃ 1.0 0.9 1.0 0.1 1.0 0.9

x ₄ 1.0 0.9 0.9 0.1 0.9 0.9

x ₅ 1.0 0.9 0.9 0.1 0.9 0.9