cc -reduction in a fully fuzzy information system

1 Introduction

In 1982, Pawlak [11] proposed rough set theory. This theory is an important tool for the study of intelligent systems described by uncertain and incomplete information. The main idea is to make decision or classification rules through knowledge reduction under the condition of keeping the classification ability unchanged. So far, rough set theory has been applied to machine learning, decision analysis, process control, pattern recognition, inductive reasoning and data mining [12–15].

Information systems based on rough set theory was also introduced by Pawlak. They may reveal large databases and knowledge discovery process mathematically. It is well known that attributes in the same information system are not equally important, even some of them are redundant. Attribute reductions in of a given information system mean deleting irrelevant or unimportant attributes under the condition of keeping the classification ability of this information system. As one of the core contents of rough set theory, attribute reduction has attracted a great deal of attention.

In real life, fuzziness is a universal phenomenon. Thus, various kinds of fuzzy information systems have been studied by many scholars. For example, Zhang et al. [4] studied knowledge reduction with fuzzy decision information systems, Guan et al. [4] gave knowledge reduction methods in fuzzy objective information systems, Huang [5] investigated graded dominance interval-based fuzzy objective information systems, Huang et al. [7] proposed dominance-based rough set model in intuitionistic fuzzy information systems, Sun et al. [17] presented fuzzy rough set theory for interval-valued fuzzy information systems, Huang et al. [6] introduced a dominance relation in an interval-valued intuitionistic fuzzy information system and established a dominance-based rough set model for this fuzzy information system, Cheng et al. [1] considered rule extraction based on granulation order in interval-valued fuzzy information system, Feng et al. [2] studied belief functions on general intuitionistic fuzzy information systems, Lang et al. [9] researched homomorphisms-based attribute reduction of dynamic fuzzy covering information systems, Zhang et al. [20] obtained generalized dominance rough set models for the dominance intuitionistic fuzzy information systems. Zhang et al. [21] considered information structures and uncertainty measures in a fully fuzzy information system.

Fuzzy set was proposed by Zadeh [19] as an extension of classical set to depict fuzziness. A fully fuzzy information system is an information system where each of its attributes determines a fuzzy set on the object set. So far, however, attribute reduction in a fully fuzzy information system has not been reported. This paper will address this topic.

Given a fully fuzzy information system (U, A). For a ∈ A and two objects x, y of U, a (x) and a (y) is the information function values of the objects x and y on the attribute a, respectively. But, a (x) and a (y) are also the membership degrees of x and y to the fuzzy set a, respectively. It should be noted that a (x) and a (y) are two numbers in [0, 1]. Then, “a (x) = a (y) " is actually difficult to be achieved. For this reason, we may consider the concept of “class-consistent" and then propose the class-consistent relation on the object set U. The aim of this paper is to give an attempt to study attribute reduction based on class-consistent relations (for short, cc-reduction) for a fully fuzzy information system. And the work process of the paper is displayed in Fig. 1.

OPEN IN VIEWER

Fig.1

The work process of the paper.

The remaining part of this paper is organized as follows. In Section 2, we recall some concepts about rough sets and fully fuzzy information systems, and propose class-consistent, class-preserving mappings, class-consistent relations and homomorphisms. In Section 3, we introduce cc-reduction in a fully fuzzy information system and give its properties. In Section 4, we put forward an algorithm on cc-reduction in a fully fuzzy information system. In Section 5, we obtain some invariant characterizations of fully fuzzy information systems under homomorphisms. In Section 6, we give a numerical experiment on the Yeast data set. In Section 7, we summarize this paper.

In this section, we briefly recall basic concepts about rough sets and fully fuzzy information systems, introduce class-consistent, class-preserving mappings, class-consistent relations and homomorphisms, and give the related properties.

Throughout this paper, U and V denote two non-empty finite sets, 2 ^U expresses the family of all subsets of U and |X| means the cardinality of X ∈ 2 ^U .

Put U = { x 1 , x 2 , ⋯ , x n } , V = { y 1 , y 2 , ⋯ , y m } .

3 cc-reduction in a fully fuzzy informationsystem

Given a fully fuzzy information system (U, A), each subset P of A determines the equivalence relation (or indiscernibility relation) cc (P). cc (P) or U/cc (P) represents the classification ability of the subsystem (U, P). If cc (P) = cc (A), then the subsystem (U, P) and the system (U, A) have the same classification abilities. A class-consistent reduction means reducing the number of the attributes in (U, A) to the minimum without distorting the classification ability of (U, A), which plays a vital role in saving expensive tests and time when addressing decision-making problems.

Definition 3.1. Let (U, A) be a fully fuzzy information system. Given P ⊆ A.

(1) P is called a class-consistent coordinate (for short, cc-coordinate) subset of A, if cc (A) = cc (P).

(2) a ∈ P is called cc-independent in P, if cc (P - {a}) ≠ cc (P); P is called a cc-independent subset of A, if for each a ∈ P, a is cc-independent in P.

(3) P is called a class-consistent reduction (for short, cc-reduction) of A, if P is both cc-coordinate and cc-independent.

In this paper, the family of all cc-coordinate subsets (resp., cc-reductions) of A is denoted by co ^cc  (A) (resp., red ^cc  (A)).

Obviously,

P ∈ red ^cc  (A)    ⇔   P ∈ co ^cc  (A)  and  ∀  a ∈ P, P - {a} ∉ co ^cc  (A) .

Proposition 3.2. Given that (U, A) is a fully fuzzy information system. Then there always exists a cc-reduction of A.

Proof. Suppose that ∀ a ∈ A, A - {a} ∉ co ^cc  (A). Then A ∈ red ^cc  (A).

Suppose that ∃ a₁ ∈ A, A - {a₁} ∈ co ^cc  (A). Then, we consider A - {a₁}. Again suppose that ∀ a ∈ A - {a₁}, (A - {a₁}) - {a} ∉ co ^cc  (A). Then A - {a₁} ∈ red ^cc  (A). Again suppose that ∃ a₂ ∈ A - {a₁}, (A - {a₁}) - {a₂} ∈ co ^cc  (A). Then, we consider A - {a₁, a₂}. Repeat this process. Since A is finite, we can find a cc-reduction of A.

Thus, there always exists a cc-reduction of A. □

Definition 3.3 Let (U, A) be a fully fuzzy information system. For any x, y ∈ U, put D cc ( x , y ) = { a ∈ A : a ( x ) ≉ 1 a ( y ) } . Then

(1) D ^cc  (x, y) is called the cc-discernibility set on x and y.

(2) D cc ( A ) = ( d ij ) n × n is called the cc-discernibility matrix where U = {x₁, x₂, ·· · , x _n } and d _ij  = D ^cc  (x _i , x _j ) (1 ≤ i, j ≤ n).

Example 3.4. Table 2 depicts a fully fuzzy information system where U = {x₁, x₂, x₃, x₄, x₅, x₆} and A = {a₁, a₂, a₃, a₄}.

The cc-discernibility matrix D cc ( A ) of A is obtained as follows: ( ∅ { a 2 } A A { a 2 } { a 1 , a 4 } { a 2 } ∅ { a 1 , a 3 , a 4 } { a 1 , a 3 , a 4 } ∅ { a 1 , a 2 , a 4 } A { a 1 , a 3 , a 4 } ∅ ∅ { a 1 , a 3 , a 4 } { a 2 , a 3 } A { a 1 , a 3 , a 4 } ∅ ∅ { a 1 , a 3 , a 4 } { a 2 , a 3 } { a 2 } ∅ { a 1 , a 3 , a 4 } { a 1 , a 3 , a 4 } ∅ { a 1 , a 2 , a 4 } { a 1 , a 4 } { a 1 , a 2 , a 4 } { a 2 , a 3 } { a 2 , a 3 } { a 1 , a 2 , a 4 } ∅ )

Proposition 3.5. Given that (U, A) is a fully fuzzy information system. The for any x, y, z ∈ U,

(1) D ^cc  (x, x) =∅.

(2) D ^cc  (x, y) = D ^cc  (y, x).

(3) D ^cc  (x, y) ⊆ D ^cc  (x, z) ∪ D ^cc  (z, y).

Proof. (1) and (2) are obvious.

(3) Suppose that D ^cc  (x, y) notsubseteqD ^cc  (x, z) ∪ D ^cc  (z, y). Then D ^cc  (x, y) - D ^cc  (x, z) ∪ D ^cc  (z, y)≠∅. Pick a ∈ D cc ( x , y ) - D cc ( x , z ) ∪ D cc ( z , y ) .

a ∈ D ^cc  (x, y) implies (x, y) ∉ cc ({a}).

Since a ∉ D ^cc  (x, z) ∪ D ^cc  (z, y), we have a ∉ D ^cc  (x, z) and a ∉ D ^cc  (z, y). Then (x, z) ∈ cc ({a}) and (z, y) ∈ cc ({a}).

Thus D ^cc  (x, y) ⊆ D ^cc  (x, z) ∪ D ^cc  (z, y). □

Corollary 3.6. Let (U, A) be a fully fuzzy information system. Then d is a distance function on U where d ( x , y ) = | D cc ( x , y ) | ( x , y ∈ U ) .

Proof. This holds by Proposition 3.5. □

Proposition 3.7. Given that (U, A) is a fully fuzzy information system. Then P ∈ co cc ( A ) ⇔ if ( x , y ) ∉ cc ( A ) , then P ∩ D cc ( x , y ) ≠ ∅ .

Proof. “⇒”. Let (x, y) ∉ cc (A). Since P ∈ co ^cc  (A), we have cc (P) = cc (A) . Then (x, y) ∉ cc (P) . So there exists a ∈ P such that a (x) _notapprox1a (y). This implies a ∈ D ^cc  (x, y). Then a ∈ P ∩ D ^cc  (x, y).

Thus P ∩ D ^cc  (x, y) ≠ ∅ .

“⟸". Suppose P ∉ co ^cc  (A). Then cc (P) ≠ cc (A) . This implies cc (P) - cc (A) ≠ ∅ . Pick ( x , y ) ∈ cc ( P ) - cc ( A ) .

Since (x, y) ∉ cc (A), we have P ∩ D ^cc  (x, y) ≠ ∅ .

It should be noted that (x, y) ∈ cc (P). Then for each a ∈ P, a (x) ≈ ₁a (y). So a ∉ D ^cc  (x, y) . Thus P ∩ D ^cc  (x, y) = ∅ . This is a contradiction.

Hence P ∈ co ^cc  (A). □

cc-discernibility sets can easily determine cc-reductions.

Theorem 3.8. Let (U, A) be a fully fuzzy information system. Then P ∈ red ^cc  (A) ⇔ (i) if (x, y) ∉ cc (A), then P∩ D ^cc  (x, y) ≠ ∅ ;

             (ii) ∀ a ∈ P, ∃  (x _a , y _a ) ∈ cc (A), (P - {a})∩ D ^cc  (x _a , y _a ) = ∅.

Proof. This holds by Proposition 3.7. □

Definition 3.9. Given that (U, A) is a fully fuzzy information system. Put core cc ( A ) = ⋂ P ∈ red cc ( A ) P . Then core ^cc  (A) is called the cc-core of A. Moreover,

(1) a ∈ A is called a necessary cc-attribute, if a ∈ core ^cc  (A).

(2) a ∈ A is called a relatively necessary cc-attribute, if a ∈ ⋃ _{P∈red ^cc (A)}P - core ^cc  (A).

(3) a ∈ A is called an unnecessary cc-attribute, if a ∈ A - ⋃ _{P∈red ^cc (A)}P.

Proposition 3.10. Let (U, A) be a fully fuzzy information system. Then | red cc ( A ) | = 1 ⇔ core cc ( A ) ∈ red cc ( A ) .

Proof. “⇒” is obvious.

“⟸". Denote red ^cc  (A) = {P _k  : 1 ≤ k ≤ n}. We only need to prove n = 1.

Suppose n ≥ 2. Since core ^cc  (A) ∈ red ^cc  (A), there exists i such that core ^cc  (A) = P _i . Pick j ≠ i. Then P i = ⋂ k = 1 n P k ⊆ P j . Put P _i  ≠ P _j . Thus P _i  ⊂ P _j . Since P _j  ∈ red ^cc  (A), we have P _i  ∉ co ^cc  (A). Then P _i  ∉ red ^cc  (A). This is a contradiction.

Thus n = 1. □

cc-discernibility sets can easily determine the cc-core.

Proposition 3.11. Given that (U, A) is a fully fuzzy information system. Then the following conditions are equivalent:

(1) a is a necessary cc-attribute;

(2) a is cc-independent in A;

(3) ∃ x, y ∈ U, D ^cc  (x, y) = {a}.

Proof.

(1) ⇒ (2). Let a be a necessary cc-attribute. Suppose that a is not cc-independent in A. Then cc ( A - { a } ) = cc ( A ) . This implies A - {a} ∈ co ^cc  (A). Consider A - {a}, by Proposition 3.2, ∃ P ⊆ A - {a}, P ∈ red ^cc  (A).

P ⊆ A - {a} implies a ∉ P. Then a is not a necessary cc-attribute. This is a contradiction.

(2) ⇒ (1). Let a be cc-independent in A. Suppose that a is not a necessary cc-attribute. Then ∃ P ∈ red ^cc  (A), a ∉ P. So P ⊆ A - {a} ⊆ A. This implies cc ( P ) ⊇ cc ( A - { a } ) ⊇ cc ( A ) .

Since P ∈ red ^cc  (A), we have cc (P) = cc (A). Then cc (A - {a}) = cc (A) . So a is not cc-independent in A. This is a contradiction.

(2) ⇒ (3). Since a is cc-independent in A, we have cc (A - {a}) ≠ cc (A). Then cc (A - {a}) - cc (A)≠ ∅. Pick ( x , y ) ∈ cc ( A - { a } ) - cc ( A ) . Denote A = {a₁, a₂, …, a _n }. Then ∃ j, a = a _j . So ( x , y ) ∈ ⋂ 1 ≤ i ≤ n , i ≠ j cc ( { a i } ) - ⋂ 1 ≤ i ≤ n cc ( { a i } ) . This implies that (x, y) ∉ cc ({a _j }) and (x, y) ∈ cc ({a _i })   (i ≠ j) .

Then a _j  ∈ D ^cc  (x, y), a _i  ∉ D ^cc  (x, y)   (i ≠ j) .

Thus D ^cc  (x, y) = {a _j } = {a}.

(3) ⇒ (2). Since ∃ x, y ∈ U, D ^cc  (x, y) = {a}, we have ( x , y ) ∉ cc ( { a } ) , ( x , y ) ∈ cc ( { a ′ } ) ( a ′ ≠ a ) .

Then (x, y) ∈ cc (A - {a}). But (x, y) ∉ cc (A).

Thus cc (A - {a}) ≠ cc (A) . Hence a is cc-independent in A. □

Proposition 3.12. Let (U, A) be a fully fuzzy information system. Denote R ( a ) = ⋃ P ∈ co cc ( A ) cc ( P - { a } ) . Then the following conditions are equivalent:

(1) a is an unnecessary cc-attribute;

(2) ∀ P ∈ co ^cc  (A), P - {a}∈ co ^cc  (A) ;

(3) R (a) = cc (A);

(4) R (a) ⊆ cc ({a}).

Proof. (1) ⇒ (2). Given P ∈ co ^cc  (A). By Proposition 3.2, ∃ C ⊆ P, C ∈ red ^cc  (A). Since a is an unnecessary cc-attribute, we have a ∉ C, which implies C ⊆ A - {a}. Then C ⊆ P ∩ ( A - { a } ) = P - { a } ⊆ P . We have cc ( C ) ⊇ cc ( P - { a } ) ⊇ cc ( P ) .

It should be noted that P ∈ co ^cc  (A) and C ∈ red ^cc  (A). Then cc (P) = cc (A) = cc (C).

Thus cc (P - {a}) = cc (A) .

Hence P - {a} ∈ co ^cc  (A) .

(2) ⇒ (3) ⇒ (4) are obvious.

(4) ⇒ (1). Suppose that a is not an unnecessary cc-attribute. Then ∃ P ∈ red ^cc  (A), a ∈ P. This implies P - {a} ⊂ P. Since P ∈ red ^cc  (A), we have P - {a} ∉ co ^cc  (A). Then cc (P - {a}) - cc (A) ≠ ∅ . P ∈ red ^cc  (A) implies cc (P) = cc (A). Then cc ( P - { a } ) - cc ( P ) ≠ ∅ .

Pick (x, y) ∈ cc (P - {a}) - cc (P). It should be noted that cc (P) = cc (P - {a}) ∩ cc ({a}). Then (x, y) ∉ cc ({a}).

Since P ∈ co ^cc  (A) and R (a) ⊆ cc ({a}), we have cc (P - {a}) ⊆ cc ({a}). Then (x, y) ∈ cc ({a}). This is a contradiction. □

Theorem 3.13. Given that (U, A) is a fully fuzzy information system. Then

(1) a is a necessary cc-attribute ⇔ A - {a} ∉ co ^cc  (A).

(2) a is a relatively necessary cc-attribute ⇔ A - {a} ∈ co ^cc  (A) and R (a) notsubseteqcc ({a}).

(3) a is an unnecessary cc-attribute ⇔ ∀ P ∈ co ^cc  (A), P - {a} ∈ co ^cc  (A) .

Proof. This holds by Propositions 3.11 and 3.12. □

Example 3.14. In Example 3.4, we have

  (1) a₂ is a necessary cc-attribute;

  (2) a₁ and a₄ are two relatively necessary cc-attributes;

  (3) a₁, a₃ and a₄ are three unnecessary cc-attributes.

It is more convenient to calculate all cc-reductions and the cc-core in a fully fuzzy information system by using the following cc-discernibility function.

Below, we give an algorithm on cc-reduction in a fully fuzzy information system by using mathematical logic.

“⋁”(disjunction), “⋀”(conjunction), “⟶”(implication), “↔”(biimplication) are propositional connectives in mathematical logic. They are read as “or”, “and”, “if-then”, “if and only if”, respectively.

Let (U, A) be a fully fuzzy information system. ∀ a ∈ A, we specify a Boolean variable “a”. If D ^cc  (x, y) = {a₁, a₂, ·· · , a _k } with x, y ∈ U, then we specify a Boolean function a₁ ∨ a₂ ∨ ·· · ∨ a _k .

Denote ⋁ { a 1 , a 2 , · · · , a k } or ⋁ i = 1 k a i = a 1 ∨ a 2 ∨ · · · ∨ a k , ⋀ { a 1 , a 2 , · · · , a k } or ⋀ i = 1 k a i = a 1 ∧ a 2 ∧ · · · ∧ a k .

We stipulate that ∨  ∅ =1 and ∧  ∅ =0 where 0 and 1 are two Boolean constants.

Definition 4.1. Let (U, A) be a fully fuzzy information system. Then the cc-discernibility matrix of A, denoted by D cc ( A ) = ( d ij ) n × n , is define as Δ cc ( A ) = ⋀ ( ⋁ d ij ) .

Example 4.2. In Example 3.4, we have

▵ (A) = a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₄) ∧ (a₁ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₂ ∨ a₄) ∧ (a₂ ∨ a₃) .

Denote L ( A ) = { ⋁ d ij : 1 ≤ i , j ≤ n } .

A binary relation “≤” on L (A) is defined as follows: ⋁ d ij ≤ ⋁ d kl ⇔ d ij ⊆ d kl for any ⋁ d ij , ⋁ d kl ∈ L ( A ) .

For any ⋁d _ij , ⋁ d _kl  ∈ L (A), we denote ( ⋁ d ij ) ⨆ ( ⋁ d kl ) = ⋁ ( d ij ∪ d kl ) , ( ⋁ d ij ) ⊓ ( ⋁ d kl ) = ⋁ ( d ij ∩ d kl ) .

Proposition 4.3. (L (A) ,   ≤) is a poset.

Proof. (1) ⋁d _ij  ≤ ⋁ d _ij for any ⋁d _ij  ∈ L (A).

(2) Given ⋁d _ij , ⋁ d _kl  ∈ L (A). Suppose that ⋁d _ij  ≤ ⋁ d _kl and ⋁d _kl  ≤ ⋁ d _ij . Then d _ij  ⊆ d _kl and d _kl  ⊆ d _ij . This implies that d _ij  = d _kl . So ⋁d _ij  = ⋁ d _kl .

(3) Given ⋁d _ij , ⋁ d _kl , ⋁ d _hv  ∈ L (A). Suppose that ⋁d _ij  ≤ ⋁ d _kl and ⋁d _kl  ≤ ⋁ d _hv . Then d _ij  ⊆ d _kl and d _kl  ⊆ d _hv . This implies that d _ij  ⊆ d _hv . So ⋁d _ij  ≤ ⋁ d _hv .

Thus (L (A) ,   ≤) is a poset. □

Proposition 4.4 Let (U, A) be a fully fuzzy information system. Given U = {x₁, x₂, ·· · , x _n }. If {d _ij  : 1 ≤ i, j ≤ n} is a topology on A, then (L (A) , ≤ , ⊔ , ⊓) is a lattice with top element and bottom element.

Proof. Denote τ = {d _ij  : 1 ≤ i, j ≤ n}. By Proposition 4.3, (L (A) ,   ≤) is a poset. For ⋁d _ij , ⋁ d _kl  ∈ L (A), since τ is a topology on A, we have d _ij  ∪ d _kl  ∈ τ, d _ij  ∩ d _kl  ∈ τ. This implies ( ⋁ d ij ) ⊔ ( ⋁ d kl ) = ⋁ ( d ij ∪ d kl ) ∈ L ( A ) , ( ⋁ d ij ) ⊓ ( ⋁ d kl ) = ⋁ ( d ij ∩ d kl ) ∈ L ( A ) . Obviously, 1_L(A) = ∨ A, 0_L(A) =∨ ∅.

Thus (L (A) , ≤ , ⊔ , ⊓) is a lattice with top element and bottom element. □

Example 4.5. In Example 3.4, (⋁ d₂₃) ⊓ (⋁ d₆₃) = a₃ ∉ L (A). Then (L (A) , ≤ , ⊔ , ⊓) is not a lattice.

Definition 4.6. Given a fully fuzzy information system (U, A). If Δ cc ( A ) = ⋁ k = 1 q ( ⋀ l = 1 p k a kl ) , where every P _k  = {a _kl  : l ≤ p _k } ⊆ A has not repetitive elements, then ⋁ k = 1 q ( ⋀ l = 1 p k a kl ) is called the standard minimum formula of Δ ^cc  (A). We denote it by Δ * cc ( A ) . That is, Δ * cc ( A ) = ⋁ k = 1 q ( ⋀ l = 1 p k a kl ) .

Example 4.7. In Example 3.4, we have a 2 ≤ a 1 ∨ a 2 ∨ a 3 ∨ a 4 , a 2 ≤ a 1 ∨ a 2 ∨ a 4 , a 2 ≤ a 2 ∨ a 3 , a 1 ∨ a 4 ≤ a 1 ∨ a 3 ∨ a 4 .

Obviously, a 2 ∧ ( a 1 ∨ a 2 ∨ a 3 ∨ a 4 ) = a 2 , a 2 ∧ ( a 1 ∨ a 2 ∨ a 4 ) = a 2 , a 2 ∧ ( a 2 ∨ a 3 ) = a 2 , ( a 1 ∨ a 4 ) ∧ ( a 1 ∨ a 3 ∨ a 4 ) = a 1 ∨ a 4 . Then

Δ ^cc  (A) = a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₄) ∧ (a₁ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₂ ∨ a₄) ∧ (a₂ ∨ a₃)

          = a₂ ∧ (a₁ ∨ a₄)

          = (a₁ ∧ a₂) ∨ (a₂ ∧ a₄) . Thus Δ * cc ( A ) = ( a 1 ∧ a 2 ) ∨ ( a 2 ∧ a 4 ) .

Theorem 4.8. Given that (U, A) is a fully fuzzy information system. If Δ * cc ( A ) = ⋁ k = 1 q ( ⋀ l = 1 p k a kl ) is the standard minimum formula of Δ ^cc  (A), then red ^cc  (A) = {P _k  : k ≤ q} where P _k  = {a _kl  : l ≤ p _k }.

Proof. (1) Given P _{k 0}  ∈ {P _k  : k ≤ q}.

(i) Clearly, Δ * cc ( A ) = ⋁ k = 1 q ( ⋀ l = 1 p k a kl ) = ⋁ k = 1 q ( ⋀ P k ) . Then ⋀ P k 0 ⟶ Δ * cc ( A ) .

Since Δ * cc ( A ) = Δ cc ( A ) = ⋀ ( ⋁ d ij ) , we have Δ * cc ( A ) ⇔ ⋁ d ij for any 1 ≤ i , j ≤ n .

Then ∀ x, y ∈ U, ⋀P _{k 0}  ⟶ ⋁ D ^cc  (x, y).

So ∀  (x, y) ∉ cc (A), ⋀P _{k 0}  ⟶ ⋁ D ^cc  (x, y).

Now ⋀P _{k 0}  ⇔ a _{k 0 l} for any l ≤ p _{k 0} and ⋁D ^cc  (x, y) ↔ a for some a ∈ D ^cc  (x, y). Then ∀  (x, y) ∉ cc (A), a _{k 0 l} for any l ≤ p _{k 0}  ⟶ a for some a ∈ D ^cc  (x, y).

So ∀  (x, y) ∉ cc (A), there exists l₀ ≤ p _{k 0} such that a = a _{k 0 l 0} , i.e., a ∈ P _{k 0}  ∩ D ^cc  (x, y).

Thus ∀  (x, y) ∉ cc (A), P _{k 0} ∩ D ^cc  (x, y) ≠ ∅.

By Proposition 3.7, P _{k 0}  ∈ co ^cc  (A).

(ii) To prove P _{k 0}  ∈ red ^cc  (A), by Theorem 3.8, we only need to show that ∀ a ∈ P k 0 , ∃ ( x a , y a ) ∈ cc ( A ) , ( P k 0 - { a } ) ∩ D cc ( x a , y a ) = ∅ .

Suppose that ∃ a₀ ∈ P _{k 0} such that (P _{k 0}  - {a₀})∩ D ^cc  (x, y) ≠ ∅ for any (x, y) ∉ cc (A). Pick a _xy  ∈ (P _{k 0}  - {a₀}) ∩ D ^cc  (x, y). Then ⋀ (P _{k 0}  - {a₀}) ⟶ a _xy and a _xy  ⟶ ⋁ D ^cc  (x, y).

Thus ∀  (x, y) ∉ cc (A), ⋀ (P _{k 0}  - {a₀}) ⟶ ⋁ D ^cc  (x, y) .

∀  (x, y) ∈ cc (A), we have D ^cc  (x, y) =∅. Then ⋀ (P _{k 0}  - {a₀}) ⟶ ⋁ D ^cc  (x, y) .

It follows that ∀ x, y ∈ U, ⋀ ( P k 0 - { a 0 } ) ⟶ ⋁ D cc ( x , y ) .

Since Δ * cc ( A ) contains all true explanations of Δ ^cc  (A), we have P _{k 0}  - {a₀} ∈ {P _k  : k ≤ q}. Then

(⋀ P _{k 0} ) ⋁ (⋀ (P _{k 0}  - {a₀}))

= ((⋀ (P _{k 0}  - {a₀})) ⋀ {a₀}) ⋁ ((⋀ (P _{k 0}  - {a₀})) ⋀1)

= (⋀ (P _{k 0}  - {a₀})) ⋀ ({a₀} ⋁1)

= (⋀ (P _{k 0}  - {a₀})) ⋀1

= ⋀ (P _{k 0}  - {a₀}).

So P _{k 0}  ∉ {P _k  : k ≤ q}. This is a contradiction.

Thus P _{k 0}  ∈ red ^cc  (A). This shows that red ^cc  (A) ⊇ {P _k  : k ≤ q}.

(2) Let P ∈ red ^cc  (A). Then P ∈ co ^cc  (A). By Proposition 3.7, P∩ D ^cc  (x, y) ≠ ∅ for any (x, y) ∉ cc (A).

Similar to the proof of (1)   (ii), we can show that P ∈ {P _k  : k ≤ q} .

Thus red ^cc  (A) ⊆ {P _k  : k ≤ q}.

Hence red ^cc  (A) = {P _k  : k ≤ q} . □

Algorithm 4.9. Given a fully fuzzy information system (U, A). Then an algorithm on cc-reduction of A is shown as follows:

OPEN IN VIEWER

Example 4.10. (Continued from Example 3.4) In Step 1, we input a fully fuzzy information system (U, A).

In Step 2, we give the cc-discernibility matrix D cc ( A ) of A.

In Step 3, we get

Δ ^cc  (A) = a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₄) ∧ (a₁ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₂ ∨ a₄) ∧ (a₂ ∨ a₃) .

In Step 4, we gain Δ * cc ( A ) = ( a 1 ∧ a 2 ) ∨ ( a 2 ∧ a 4 ) .

In Step 5, we obtain red ^cc  (A) = {{a₁, a₂} , {a₂, a₄}} and core ^cc  (A) = {a₂}.

5 Invariant characterizations of fully fuzzyinformation systems underhomomorphisms

Proposition 5.1. Suppose (U, A) ∼  _h  (V, B). Given P ⊆ A. Then [ h 1 ( x ) ] cc ( h 2 ( P ) ) = h 1 ( [ x ] cc ( P ) ) .

Proof. Obviously, [ x ] cc ( P ) = { u ∈ U : ∀ a ∈ P , a ( x ) ≈ 1 a ( u ) } , [ h 1 ( x ) ] cc ( h 2 ( P ) ) = { v ∈ V : ∀ a ∈ P , h 2 ( a ) ( h 1 ( x ) ) ≈ 1 h 2 ( a ) ( v ) } .

Suppose that v ∈ [h₁ (x)] _cc(h2(P)). Then ∀ a ∈ P,  h₂ (a) (h₁ (x)) ≈ ₁h₂ (a) (v) . Let h₁ (u) = v. Then ∀ a ∈ P,  h₂ (a) (h₁ (x)) ≈ ₁h₂ (a) (h₁ (u)).

It should be noted that (U, A) ∼  _h  (V, B). Then ∀ a ∈ P, h 2 ( a ) ( h 1 ( x ) ) ≈ 1 h 3 ( a ( x ) ) , h 2 ( a ) ( h 1 ( u ) ) ≈ 1 h 3 ( a ( u ) ) .

So ∀ a ∈ P, h₃ (a (x)) ≈ ₁h₃ (a (u)) .

Since h₃ is class-preserving, ∀ a ∈ P, a (x) ≈ ₁a (u). Then u ∈ [x] _cc(P). This implies that v ∈ h₁ ([x] _cc(P)).

Conversely, suppose that v ∈ h₁ ([x] _cc(P)). Then ∃ u ∈ U, v = h₁ (u), u ∈ [x] _cc(P). So ∀ a ∈ P,  a (x) ≈ ₁a (u). Since h₃ is class-preserving, ∀ a ∈ P, h₃ (a (x)) ≈ ₁h₃ (a (u)) .

It should be noted that (U, A) ∼  _h  (V, B). Then ∀ a ∈ P, h 2 ( a ) ( h 1 ( x ) ) ≈ 1 h 3 ( a ( x ) ) , h 2 ( a ) ( h 1 ( u ) ) ≈ 1 h 3 ( a ( u ) ) .

Then ∀ a ∈ P,  h₂ (a) (h₁ (x)) ≈ ₁h₂ (a) (h₁ (u)) = h₂ (a) (v). This implies that v ∈ [h₁ (x)] _cc(h2(P)).

Therefore, [h₁ (x)] _cc(h2(P)) = h₁ ([x] _cc(P)). □

Theorem 5.2. Suppose (U, A) ∼  _h  (V, B).

(1) If P ∈ co ^cc  (A), then h₂ (P) ∈ co ^cc  (B).

(2) If h₁ is injective, h₂ (P) ∈ co ^cc  (B), then P ∈ co ^cc  (A).

Proof. (1) ∀ j, let h₁ (x _i ) = y _j . Since P ∈ co ^cc  (A), we have cc (P) = cc (A) . This implies that [x _i ] _cc(P) = [x _i ] _cc(A). Then h₁ ([x _i ] _cc(P)) = h₁ ([x _i ] _cc(A)) . By Proposition 5.1, [ h 1 ( x i ) ] cc ( h 2 ( P ) ) = [ h 1 ( x i ) ] cc ( h 2 ( A ) ) . Thus ∀ j,   [y _j ] _cc(h2(P)) = [y _j ] _cc(B).

By Theorem 2.8, cc (h₂ (P)) = cc (B).

Therefore, h₂ (P) ∈ co ^cc  (B).

(2) ∀ i, let y _j  = h₁ (x _i ). Since h₂ (P) ∈ co ^cc  (B), we have cc ( h 2 ( P ) ) = cc ( B ) = cc ( h 2 ( A ) ) .

This implies [y _j ] _cc(h2(P)) = [y _j ] _cc(h2(A)), i.e., [ h 1 ( x i ) ] cc ( h 2 ( P ) ) = [ h 1 ( x i ) ] cc ( h 2 ( A ) ) .

By Proposition 5.1, h 1 ( [ x i ] cc ( P ) ) = h 1 ( [ x i ] cc ( A ) ) .

Since h₁ is injective, ∀ i,   [x _i ] _cc(P) = [x _i ] _cc(A).

By Theorem 2.8, cc (P) = cc (A).

Therefore, P ∈ co ^cc  (A). □

Corollary 5.3. Suppose (U, A) ∼  _h  (V, B). If h₁ is injective, then

(1) P ∈ co ^cc  (A) ⇔ h₂ (P) ∈ co ^cc  (B) .

(2) h₂ (co ^cc  (A)) = co ^cc  (B) , where h₂ (co ^cc  (A)) = {h₂ (P) : P ∈ co ^cc  (A)} .

Proof. (1) This holds by Theorem 5.2.

(2) This follows from (1). □

Theorem 5.4 Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then P ∈ red cc ( A ) ⇔ h 2 ( P ) ∈ red cc ( B ) .

Proof. “⇒". Since P ∈ red ^cc  (A), we have P ∈ co ^cc  (A). By Theorem 5.2, h₂ (P) ∈ co ^cc  (B).

∀ b ∈ h₂ (P), let h₂ (a) = b. Since P ∈ red ^cc  (A), we have P - {a} ∉ co ^cc  (A).

By Corollary 5.3, h₂ (P - {a}) ∉ co ^cc  (B) . Since h₂ is injective, we have h 2 ( P - { a } ) = h 2 ( P ) - { h 2 ( a ) } = h 2 ( P ) - { b } .

Then h₂ (P) - {b} ∉ co ^cc  (B) .

Hence, h₂ (P) ∈ red ^cc  (B).

“⟸". Since h₂ (P) ∈ red ^cc  (B), we have h₂ (P) ∈ co ^cc  (B). By Corollary 5.3, P ∈ co ^cc  (A).

∀ a ∈ P, let b = h₂ (a). Then b ∈ h₂ (P). Since h₂ (P) ∈ red ^cc  (B), we have  h₂ (P) - {b} ∉ co ^cc  (B).

It should be noted that h₂ is injective. Then h 2 ( P ) - { b } = h 2 ( P ) - { h 2 ( a ) } = h 2 ( P - { a } ) .

This implies h₂ (P - {a}) ∉ co ^cc  (B) .

By Corollary 5.3, P - {a} ∉ co ^cc  (A) .

Hence P ∈ red ^cc  (A). □

Corollary 5.5. Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then h 2 ( red cc ( A ) ) = red cc ( B ) , where h₂ (red ^cc  (A)) = {h₂ (P) : P ∈ red ^cc  (A)} .

Proof. This holds by Theorem 5.4. □

Theorem 5.6. Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then a ∈ core cc ( A ) ⇔ h 2 ( a ) ∈ core cc ( B ) .

Proof. “ ⇒ ". Since a ∈ core ^cc  (A), by Theorem 3.13, A - {a} ∉ co ^cc  (A).

By Corollary 5.3, h₂ (A - {a}) ∉ co ^cc  (B).

Since h₂ is injective, we have h 2 ( A - { a } ) = h 2 ( A ) - { h 2 ( a ) } = B - { h 2 ( a ) } .

Then B - {h₂ (a)} ∉ co ^cc  (B) .

By Theorem 3.13, h₂ (a) ∈ core ^cc  (B).

“ ⟸ ". Since h₂ (a) ∈ core ^cc  (B), by Theorem 3.13, B - {h₂ (a)} ∉ co ^cc  (B), i.e., h₂ (A) - {h₂ (a)} ∉ co ^cc  (B).

It should be noted that h₂ is injective. Then h 2 ( A ) - { h 2 ( a ) } = h 2 ( A - { a } ) . This implies h₂ (A - {a}) ∉ co ^cc  (B).

By Corollary 5.3, A - {a} ∉ co ^cc  (A).

by Theorem 3.13, a ∈ core ^cc  (A). □

Corollary 5.7. Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then h 2 ( core cc ( A ) ) = core cc ( B ) .

Proof. This holds by Theorem 5.6. □

Theorem 5.8. Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then

a is an unnecessary cc - attribute  ⇔  h₂ (a)  is an unnecessary cc - attribute .

Proof. “ ⇒ ". ∀ Q ∈ co ^cc  (B), by Corollary 5.3(2), there exists P ∈ co ^cc  (B) such that Q = h₂ (P).

Since a is an unnecessary cc-attribute, by Theorem 3.13(3), P - {a} ∈ co ^cc  (A). By Theorem 5.2(1), h₂ (P - {a}) ∈ co ^cc  (B).

Since h₂ is injective, we have h 2 ( P - { a } ) = h 2 ( P ) - { h 2 ( a ) } = Q - { h 2 ( a ) } .

Then Q - {h₂ (a)} ∈ co ^cc  (B).

By Theorem 3.13(3), h₂ (a) is an unnecessary cc-attribute.

“ ⟸ ". ∀ P ∈ co ^cc  (A), By Theorem 5.2(1), h₂ (P) ∈ co ^cc  (B).

Since h₂ (a) is an unnecessary cc-attribute, by Theorem 3.13(3), h₂ (P) - {h₂ (a)} ∈ co ^cc  (A).

Since h₂ is injective, we have h 2 ( P - { a } ) = h 2 ( P ) - { h 2 ( a ) } .

Then h₂ (P - {a}) ∈ co ^cc  (B). By Theorem 5.2(2), P - {a} ∈ co ^cc  (A).

By Theorem 3.13(3), a is an unnecessary cc-attribute.

□

Corollary 5.9. Suppose (U, A) ∼  _h  (V, B). If h₁ and h₂ are injective, then

a is a relatively necessary cc-attribute ⇔ h₂ (a) is a relatively necessary cc-attribute.

Proof. This holds by Theorems 5.6 and 5.8. □

6 A numerical experiment

In order to illustrate the practical significance and possible applications for cc-reduction in a fully fuzzy information system, we present a numerical experiment in this section.

Example 6.1 The following Table 3 shows the Yeast data set (see Fig. 2(A,B)) that comes from UCI Repository of machine learning databases. Its experiment data is a portion randomly selected from the Yeast data set. Table 3 can be expressed as the fully fuzzy information system (U, A) of Yeast where U = {u₁, u₂, u₃, u₄, u₅, u₆, u₇, u₈, u₉, u₁₀, u₁₁, u₁₂, u₁₃, u₁₄, . 8ptu₁₅, . 8ptu₁₆, . 8ptu₁₇, . 8ptu₁₈, . 8ptu₁₉, . 8ptu₂₀, . 8ptu₂₁, . 8ptu₂₂, . 8ptu₂₃, . 8ptu₂₄, u₂₅} is the set of Yeast and A = {mcg = “ McG-eoch′s method for signal sequence recognition", gvh=“von Heijne’s method for signal sequence recognition", alm=“Score of the ALOM membrane spanning region prediction program", mit=“Score of discriminant analysis of the amino acid content of the N-terminal region (20 residues long) of mitochondrial and non-mitochondrial proteins", erl=“Presence of “HDEL" substring (thought to act as a signal for retention in the endoplasmic reticulum lumen)", pox=“Peroxisomal targeting signal in the C-terminus", vac=“Score of discriminant analysis of the amino acid content of vacuolar and extracellular proteins", nuc=“Score of discriminant analysis of nuclear localization signals of nuclear and non-nuclear proteins" } = {a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈} is the set of attributes.

OPEN IN VIEWER

Fig.2

Yeast.

The cc-discernibility matrix D cc ( A ) is obtained as follows:

D cc ( u 1 , u 1 ) = ∅ ;

D cc ( u 2 , u 1 ) = { a 1 , a 2 , a 3 , a 5 , a 8 } , D cc ( u 2 , u 2 ) = ∅ ;

D cc ( u 3 , u 1 ) = { a 1 , a 3 , a 4 , a 5 , a 8 } , D cc ( u 3 , u 2 ) = { a 1 , a 2 , a 3 , a 4 } , D cc ( u 3 , u 3 ) = ∅ ;

D cc ( u 4 , u 1 ) = { a 1 , a 2 , a 4 , a 5 , a 7 , a 8 } , D cc ( u 4 , u 2 ) = { a 1 , a 2 , a 3 , a 4 , a 7 } , D cc ( u 4 , u 3 ) = { a 1 , a 2 , a 3 , a 4 , a 7 } , D cc ( u 4 , u 4 ) = ∅ ;

D cc ( u 5 , u 1 ) = { a 1 , a 2 , a 5 } , D cc ( u 5 , u 2 ) = { a 1 , a 2 , a 3 , a 8 } , D cc ( u 5 , u 3 ) = { a 1 , a 2 , a 3 , a 4 , a 8 } , D cc ( u 5 , u 4 ) = { a 1 , a 2 , a 4 , a 7 , a 8 } , D cc ( u 5 , u 5 ) = ∅ ;