1. bookAHEAD OF PRINT
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2444-8656
Pierwsze wydanie
01 Jan 2016
Częstotliwość wydawania
2 razy w roku
Języki
Angielski
access type Otwarty dostęp

Innovations to Attribute Reduction of Covering Decision System Based on Conditional Information Entropy

Data publikacji: 15 Apr 2022
Tom & Zeszyt: AHEAD OF PRINT
Zakres stron: -
Otrzymano: 28 Oct 2020
Przyjęty: 26 Nov 2020
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2444-8656
Pierwsze wydanie
01 Jan 2016
Częstotliwość wydawania
2 razy w roku
Języki
Angielski
Abstract

Traditional rough set theory is mainly used to reduce attributes and extract rules in databases in which attributes are characterised by partitions, which the covering rough set theory, a generalisation of traditional rough set theory, covers. In this article, we posit a method to reduce the attributes of covering decision systems, which are databases incarnated in the form of covers. First, we define different covering decision systems and their attributes’ reductions. Further, we describe the necessity and sufficiency for reductions. Thereafter, we construct a discernible matrix to design algorithms that compute all the reductions of covering decision systems. Finally, the above methods are illustrated using a practical example and the obtained results are contrasted with other results.

Keywords

Introduction

The Rough Set theory was proposed by Polish mathematician Zdzisław Pawlak in 1982 [1, 3, 17]. It can effectively handle uncertain, inaccurate and incomp Supposinge information. Recently, rough set theory has successfully been applied in many fields, including machine learning, pattern recognition, decision analysis, process control and data mining [4, 5, 10, 11, 12, 13, 14]. Therefore, this theory has received great attention from the international information science community, computer science and mathematics. A large number of studies in the literature have witnessed the development of rough sets in theory and application [26, 27, 28, 29]. Therefore, some scholars have extended the partition to encompass aspects explained in the above reasons, and the scope of rough set theory research has been greatly expanded. Although much attention is paid to the set approximation of cover, sparse research has been carried out in relation to the attribute reduction of covering rough sets. The attribute reduction under the algebraic point of view is generalised on the basis of the attribute reduction of conditional information entropy.

At present, certain scholars have studied the rough set theory based on their conclusions drawn from the information theory, and have proposed the information theory about rough set theory. Wang et al. [2] posited the reduction of the decision table and the common properties and different characteristics of information. Yang [6] proposed an approximate reduction method on basis of conditional information entropy in a decision table. On this basis, an approximate reduction method was proposed for vertical multi distribution decision tables [8]. Wang Yan et al also used a reduction algorithm on information entropy and identifiable Matrix, and presented a new combination algorithm [9]. After Hudan et al. added a probability measure to the rough set theory [7], some concepts and properties of information theory and rough set theory were compared, and a new method of rule extraction was obtained. Hu et al. [15] proposed a rough entropy method based on generalised rough set coverage reduction. Chen et al. [16] proposed an optimal section for reducing the superfluous cover. Yang [18] performed research on rough set methods, from the attribute reduction problem on inconsistent decision systems to the attribute reduction problem on consistent decision systems. Guo [19] studied knowledge reduction based on rough set theory for the inconsistent decision systems, such as generalised decision table, relative resolution and knowledge reduction. Shi et al. [20] proposed attribute reduction based on the Boolean matrix. Li and Yin [21] proposed a reduction algorithm of covering system on information theory. Ma [22] constructed a decision tree based on the covering rough set theory. Chen et al. [23] got a multi-label attribute reduction algorithm on neighbourhood rough set. Zhang et al. [24] developed the belief and plausibility functions from the evidence theory and these are employed to characterise attribute reductions in the covering decision information system. Zhang et al. [25] posited confidence-preserved attribute reduction and algorithms of rule acquisition in covering decision systems. Jiang et al. [30] presented an accelerator for multi-granularity attribute reduction knowledge-based systems from another angle. However, we resolve and analyse the problem in consistent and inconsistent covering decision systems based on conditional information entropy in this article.

In this article, we propose a method to reduce the attributes of covering decision systems, which are databases characterised by covers. First, we define two scenarios of covering decision systems and their attributes’ reductions. Second, we state the necessity and sufficiency for reductions. Third, we construct a discernible matrix to design algorithms that compute all the reductions of different covering decision systems. Finally, the above methods are illustrated using a practical example and the obtained results are in contrast to other results.

Preliminaries

We go over the basic concepts related to covering rough sets which can be found in the literature [1, 4, 11, 16, 17, 19, 21, 22, 24, 25].

Definition 1

The ordered pair (U,C), where U is any nonempty set called a universe, and C its finite covering (i.e. C is a finite family of nonempty subsets of U and ∪C = U), is what we define as the covering approximation space, or in short, the approximation space; the covering C is called then the family of approximating sets.

Definition 2

Supposing that (U,C) be a covering approximation space, and x belong to any element of U. The following set: M(x)={KC:xKSC(xSSKK=S)} \matrix{M(x) = \{K \in C:x \in K \wedge \forall S \in C(x \in S \wedge S \subseteq K \Rightarrow K = S)\} is called the minimal description of the object x.

Definition 3

Supposing that A = {A1, A2, …, An} be a set of covers of U, if ∀xU, Ax = ∩ {Aj;AjA,xAj} holds; then Cov(A) = {Ax; xU} is also a covering of U; so, we call it the leaded covering of A.

Definition 4

Supposing that π = {Ai : i = 1, … m} be a family of covers of U, if ∀xU, πx = ∩ {Aix;AixCov(Ai), xAix} holds; then Cov(π) = {πx; xU} is also a covering of U; so we call it the leaded covering of π.

Attribute reduction of consistent covering decision systems based on conditional information entropy

In this section, we focus on investigating the basic concepts and key results of consistent covering decision systems [1, 4, 16, 19, 21].

Basic definition of consistent covering decision systems based on conditional information entropy
Definition 5

Supposing that {π = Ai : i = 1, … m} be a set of covers of U, d is a decision attribute and U/d is a decision partition on U. If ∀ and ∃EjU/d such that πxdj, then decision system S = (U, π, d) is called a consistent covering decision system, and recorded as H(d|π) = 0, i.e. otherwise, S = (U, π, d) is called an inconsistent covering decision system. (Appendix:H(d|π)=1|U|xUlog|[x]dπx|πx) \left({{\rm{Appendix}}:H(d|\pi) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{{[x]}_d} \cap {\pi _x}} \right|} \over {{\pi _x}}}} \right)

The positive region of d relative to π is defined as POSπ(d)=XU/Dπ_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/D} \underline \pi (X) .

For ∀XU/d, if we believe every π¯XX \bar \pi X \Rightarrow X to be the possible rule and every πXX to be a certain rule, then all the decision rules extracted from a consistent covering decision system are consistent.

If every cover in π is a partition, then cov(π) is also a partition, and H(d|π) = 0 is just the case of a consistent decision system in traditional rough set theory. Supposing that fd(x) is a decision function fd : UVd of the universe U into value set Vd; then, for ∀xi, xjU, if πxiπxj, fd(xi) = fd([xi]d) = fd(πxi) = fd(πxj) = fd(xj) = fd([xj]d).

If fd(πxi) ≠ fd(πxj), then πxiπxj = ∅, i.e. πxiπxj and πxjπxi; on the other hand, if πxiπxj and πxjπxi, then either fd(πxi) ≠ fd(πxj) or fd(πxi) = fd(πxj) are possible.

On the other hand, if πxiπxj ≠ ∅, we get fd(πxi) = fd(πxj); to the contrary, if fd(πxi) = fd(πxj), then we have πxiπxj and πxjπxi, or πxiπxj or πxiπxj are possible.

Further, we define the relative reduction of a consistent covering decision system.

Definition 6

Supposing that S = (U, π, d) be a consistent covering decision system and there exists Aiπ if H(d|π − {Ai}) = 0, then Ai is called a superfluous relative to d in π; otherwise, Ai is known as a indispensable relative to d in π. For every Bπ satisfying H(d|B) = 0, if every element in B is indispensable, i.e. for ∀AiB,H(d|B − {Ai}) = 0 being not true, then B is called a reduction of π relative to d, in short known as relative reduction. The collection of all the indispensable elements in π is called the core of π relative to d, denoted as Cored(π).

The relative reduction of a consistent covering decision system is the minimal set of conditional covers (attributes) which ensure that every decision rule is still consistent. For a single cover Ai, we give out some equivalence conditions to judge whether it is indispensable.

The key points of consistent covering decision system based on conditional entropy
Theorem 1

Suppose H(d|π) = 0, if and only if for every x, yU, if xπy, then x ∈ [y]d.

Proof

Since for every yU, H(d|π)=1|U|yUlog|[y]dπy||πy|=0 H(d|\pi) = - {1 \over {\left| U \right|}}\sum\limits_{y \in U} \log {{\left| {{{[y]}_d} \cap {\pi _y}} \right|} \over {\left| {{\pi _y}} \right|}} = 0 , such that πy ⊆ [y]D. If for every x, yU, xπy, then x ∈ [y]d. On the other hand, for every x, yU, if xπy, we have x ∈ [y]d, hence πy ⊆ [y]d. Therefore, for every yU, H(d|π) = 0.

Theorem 2

Suppose H(d|π) = 0 if and only if POSπ (d) = U.

Proof

⇒ For every yPOSπ (d), then πy ⊆ [x]d, therefore y ∈ [x]d, and so we have [y]d = [x]d, i.e. πy ∩ [y]d ≠ ∅.

For every xπy, then x ∈ [y]d and by the Theorem 1, we get H(d|π) = 0.

⇐ Since POSπ(d)=XU/dπ_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline \pi (X) , we have π(X) ⊆ X, hence ∪π(X) ⊆ ∪X = U, and so we get POSπ (d) ⊆ U. On the other hand, since POSπ(d)=XU/dπ_(X)=π_([x]d) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline \pi (X) = \cup \underline \pi ({[x]_d}) , for every yPOSπ (d), then πy ⊆ [x]d. By Theorem 1, H(d|π) = 0 if and only if for every x, yU, xπy, then x ∈ [y]d; hence U ⊆ [y]d; then by πy ⊆ [x]d and [y]d ⊆ [x]d, we have U ⊆ [x]d; hence xPOSπ (d) such that UPOSπ (d). So, the result is true.

By the above two theorems of discussions, we obtain the following two corollaries.

Corollary 1

Suppose H(d|π) = 0, Bπ is a positive-region consistent set on S; then (U, B, d) is a consistent covering decision system.

Corollary 2

Suppose H(d|π) = 0, Bπ is a positive-region reduction on S; then B is a minimal set such that decision system (U, B, d) is a consistent covering decision system.

Theorem 3

Suppose H(d|π) = 0, Aiπ and Cov(π − {Ai}) = {Bx : xU}; then Ai is indispensable, i.e. H(d|π − {Ai}) = 0 is not true if and only if there exists xU such that Bx ⊆ [x]D is not true.

Proof

If there exists xU such that Bx ⊆ [x]D is not true, by xBx, then for every yU such that Bx ⊆ [y]D is not true. So H(d|π − {Ai}) = 0 is not true.

If H(d|π − {Ai}) = 0 is not true, then there exists, for ∀yU such that Bx ⊆ [y]D is not true. Especially, Bx ⊆ [x]D is also not true.

It should be indicated that Bx ⊆ [x]D not being true means that (U, π − {Ai}, d) is an inconsistent decision system, i.e. H(d|π − {Ai}) ≠ 0, Ai is thus indispensable implies it is a key cover to ensure (U, π, d) is a consistent decision system, i.e. H(d|π) = 0.

Theorem 4

Suppose H(d|π) = 0, Aiπ, and Cov(π − {Ai}) = {Bx : xU}, then H({Ai}|π − {Ai}) > 0, i.e. Ai is absolutely indispensable.

In other words, H({Ai}|π − {Ai}) > 0 is not true if and only if Ai is called superfluous in B.

Proof

We assume that Cov(π − {Ai}) = {Bx : xU} and Cov({Ai}) = {Aix : xU}, If Ai is called superfluous in B, for xU, Bx have equivalence values on Ai, i.e. for every Bx(xU) there is Ai(xU) such that BxAix, so H({Ai}|π{Ai})=1|U|xUlog|AixPx||Px|=0 H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {P_x}} \right|} \over {\left| {{P_x}} \right|}} = 0 .

If H({Ai}|π − {Ai}) > 0 is not true, then H({Ai}|π{Ai})=1|U|xUlog|AixBx||Bx| H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} , and for every x, i, 1|U|xUlog|AixBx||Bx|0 {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} \le 0 and 1|U|>0 {1 \over {\left| U \right|}} > 0 , so xUlog|AixBx||Bx|0 \sum\limits_{x \in U} \log {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} \le 0 is true; if there exists a certain j such that 0<|AjxBx||Bx|<1 0 < {{\left| {{A_{jx}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} < 1 ; otherwise it implies H({Ai}|π{Ai})=1|U|xUlog|AjxBx||Bx|>0 H(\{{A_i}\} |\pi - \{{A_i}\}) = - {1 \over {\left| U \right|}}\sum\limits_{x \in U} \log {{\left| {{A_{jx}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} > 0 , which is a contradiction. So for every x, i there is |AixBx||Bx|=1 {{\left| {{A_{ix}} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} = 1 , i.e. PxAix, hence H({Ai}|π − {Ai}) > 0 such that H({Ai} π − {Ai}) > 0 is not true.

Theorem 4 implies that the superfluous knowledge in question could not supply new and useful information to the concerned information system. However, the necessary knowledge could give helpful information for information systems.

Corollary 3

Suppose H(d|π) = 0, Aiπ, then Ai is superfluous relative tod in π if and only if H(d|π − {Ai}) = H(d|π) = 0.

Theorem 5

Assume that H(d|π) = 0, Bπ is called a reduction of π relative tod if and only if

H(d|B) = H(d|π), and

for every AiB, then H({Ai}|B − {Ai}) > 0.

Proof

Bπ is called a reduction of π relative to d if and only if for every AiB such that H(d|B−{Ai}) = 0 is not true and B is independent. As we know, it implies that Ai is indispensable attribute in B such that H(d|B) = 0; therefore we get H(d|B) = H(d|π).

By Theorem 4, Ai is independent in B if and only if for every AiB, then H({Ai}|B−{Ai}) > 0.

Based on the discussion of the above theorems, we could consider indicial form of information entropy as being equivalent to expressions of algebra for attribute reduction.

Theorem 6

Assume that H(d|π) = 0,Aiπ,Ai is then indispensable, i.e. H(d|π − {Ai}) = 0 is not true if and only if there is at least a pair of xi, xjU satisfying fd(πxi) ≠ fd(πxj), and the factor which has the foremost relation to π transfers behind Ai and is removed from π.

Proof

⇒ We note that if Cov(π − {Ai}) = {Bx : xU}, if H(d|π − {Ai}) = 0 is not true, then there are x0, y0U such that y0Bx0 and y0 ∉ [x0]d, which implies By0Bx0 and πx0πy0,πy0πx0, respectively, and x0, y0 satisfying fd(πx0) ≠ fd(πy0), so the factor that has the foremost relation of x0, y0 with regard to π transfers behind Ai and is removed from π.

⇐ Suppose x0, y0U satisfying fd(πxi) ≠ fd(πxj), which implies [x0]d ∩ [y0]d = ∅, and πx0πy0,πy0πx0, if their foremost relation x0, y0 with regard to π transfers behind Ai removing from π, which implies Bx0By0 or By0Bx0 is not effective. Thus if By0Bx0, then By0 ⊆ [y0]d is not effective, otherwise it points out x0 ∈ [y0]d which is a contradiction; if Bx0By0, then Bx0 ⊆ [x0]d is not virtual; if Bx0 = By0 then By0 ⊆ [y0]d and Bx0 ⊆ [x0]d are not effective. Hence H(d|π − {Ai}) = 0 is not true.

Theorem 6 implies that an indispensable cover can be characterised by the foremost relation between two elements in the universe. Thus, we have the following theorem to characterise a consistent decision system.

Theorem 7

Suppose H(d|π) = 0, Bπ, then H(d|B) = 0 if and only if for every xi, xjU satisfying fd(πx0) ≠ fd(πy0), the relation xi, xj with regard to π is equivalent to their relation with regard to B, i.e. πxiπxj, πxjπxiBxiBxj, BxjBxi.

Proof

Since the proof is similar, here there is no need to repeat it.

Attribute reduction of consistent covering decision system

The intention of relative reduction of covering attribute π is to discover the minimal subset of π to preserve every decision rule invariant. Through the theorems stated in the previous section, we understand that it is coordinative to preserve the foremost relation of every two elements to which variant decision values are invariant. Based on this understanding, we could construct an algorithm to compute all the relative reductions. Definition 7 can be found in the literature [16, 21, 23].

Definition 7

Supposing (U, π, d) be a consistent decision system. Assume U = {x1, x2, … xn}; by M(U, π, d), we mark a n × n matrix (mij), called the discernibility matrix of (U, π, d), and defined as follows: Aπ : (Axi ≠ Axj) ∧ (AxiAxj) ∧ (AxjAxi), fd(πxi) ≠ fd(πxj)=mij π, fd(πxi) = fd(πxj) for .xi, xjU

Theorem 8

Supposing (U, π, d) be a consistent covering decision system, then we obtain

(1) For every Bπ, Bmij ≠ ∅ is a valid result for every i, jn if and only if H(d|π) = 0.

(2) Cored(π) = {∀Aπ ∧ (∃mijMn×n(S) ∧mij = {A}} for some i, j.

Proof

Assume H(d|π) = 0. If fd(πxi) = fd(πxj), then mij = π, hence Bmij ≠ ∅ is true for every Bπ. If fd(πxi) ≠ fd(πxj), and since πxiBxi ⊆ [xi]d, πxjBxj ⊆ [xj]d, then, we have fd(Bxi) ≠ fd(Bxj). By the Theorem 7, πxiπxj, πxjπxiBxiBxj, BxjBxi, there is a Ai0B such that Ai0xAj0y, i.e. Ai0xAj0y,Aj0yAi0x and so we have Bmij ≠ ∅.

On the contrary, if Bmij ≠ ∅, for x, yU satisfying fd(πx) ≠ fd(πy), it points out that there are enough covers in B to maintain the relation of x, y with regard to π equivalent to the relation of x, y with regard to B. Thus we obtain H(d|π) = 0.

If every, then H(d|π − {Ai}) = 0 is not true, which means there exists at least a pair of x, yU satisfying fd(πx) ≠ fd(πy) whose foremost relation with regard to π transfer behind A is removed from π. Thus A is the only cover in π satisfying (AxiAxj) ∧ (AxjAxi). By the Definition 7, we have mij = {A}.

Hence we have CoreD(π)⊆{∀Aπ ∧ (∃mijMn×n(S) ∧mij = {A}}. If mij = {A} for some i, j, it is obvious ACoreD(π).

The value of core in information system is exclusive, which is the most important part of knowledge category in the information system.

By the Theorem 8(2), a method is used which can directly obtain Cored(π), for any ACored(π) if and only if there is at least a mij satisfying mij = A for 1 ≤ jin of the discernibility matrix M(S). Suppose E = πCored(π), then covering attribute on E can be reduced from the known values of core set, but it cannot be reduced at the same time. If π have a minimal subset, i.e. Core(π) = Min(π), then, we could reduce covering attribute synchronously. Generally speaking, π have several minimal subsets.

Theorem 9

Supposing (U, π, d) be a consistent covering decision system. Suppose E1E,E = πCored(π), then H(d|π − {Ei}) = 0 is true if and only if mijE1 for all mij,1 ≤ jin.

Proof

⇐ Since E1E, then any element of E cannot contain in Cored(π), or in other words, it could be reduced. mijE1 for all mij, 1 ≤ jin means that we could guarantee H(d|π − {Ei}) = 0 after the attributes on E1 are reduced.

⇒ If the attributes on E1 could be reduced at the same time, and there also exists a mij such that mijE1, then we obtain mij = ∅ after the attributes on E1 are reduced at the same time, which point out the attributes on E1 could not be reduced at the same time.

Attribute reduction of inconsistent covering decision systems based on information entropy

In many of practical problems, we always have inconsistent covering decision system. In this section, we propose attribute reductions for inconsistent covering decision systems. We understand that some rules extracted from inconsistent decision systems may not be consistent. As to covering decision system, experts can still give the decision-making in the case of inconsistent information, so it can be assumed that the decision-making property is not empty. So we have the following definition of attribute reduction. We always suppose U is a finite universe and π = {Ai : i = 1, … m} is a family of covers of U. Then, the induced cover of π is defined as in terms of Cov(π) = {πx : xU}, U/d = {[x]d : xU} is the decision partition, d is a decision attribute and POSπ (d) ≠ ∅.

Key definitions of inconsistent covering decision systems based on information entropy

In this subsection, we discuss the key definition of inconsistent covering decision systems which can be found in the literature [7, 16, 17, 19].

Definition 8

Suppose U is a finite universal set and π = Ai : i = 1, ..., m is a family of covers of U, Aiπ, d is a decision attribute relative to π on U and fd : UVd is the decision function, denoted by fd(x) = [x]d, then, Icds = U, π, d is an inconsistent covering decision system, i.e. H(d|π) ≠ 0 or POSπ (d) ≠ U.

Definition 9

Suppose Icds = U, π, d is an inconsistent covering decision system. For Bπ, we define the limitary entropy, d, and limitary conditional entropy, π, as to attribute decision by LH(d|π)=1|K|xKlog|[x]dπx||πx|;LH(d)=1|K|xKlog[x]d|K|; \matrix{{LH(d|\pi) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{\left| {{{[x]}_d} \cap {\pi _x}} \right|} \over {\left| {{\pi _x}} \right|}};} \cr {LH(d) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{{{[x]}_d}} \over {\left| K \right|}};} \cr} the limitary mutual information of B and d is defined as follows LI(B;d)=LH(d)LH(d|B)=1|K|xKlog[x]d|K|1|K|xKlog|[x]dBx||Bx| LI(B;d) = LH(d) - LH(d|B) = - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{{{[x]}_d}} \over {\left| K \right|}} - {1 \over {\left| K \right|}}\sum\limits_{x \in K} \log {{\left| {{{[x]}_d} \cap {B_x}} \right|} \over {\left| {{B_x}} \right|}} where K = {xU : πx ⊆ [x]d}.

Definition 10

Suppose Icds = U, π, d is an inconsistent covering decision system. For every Aiπ and LH(d|π − {Ai}) = LH(d|π), then Ai is superfluous relative to d in π. For every and, then is independent relative to in.

Definition 11

Suppose is an inconsistent covering decision system. For every Bπ, if two following conditions are met:

LI(B; d) = LI(π; d),

If ∀AiB, then LH(d|B) < LH(d|B − {Ai}),

Then B is a reduct of π relative to d, denoted by BRedπ (d).

Basic properties of inconsistent covering decision system based on positive region
Proposition 1

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For every WBπ, then POSW (d) ⊆ POSB(d).

Proof

Suppose Cov(B) = {Bx : xU} and Cov(W) = {Wx : xU}. For every xPOSW (d), then there exists XU/d, such that xW (X). There exists yWx, for every x such that WxX. Suppose B = W ∪ {b1, …, bt}, then the following attribute sets are made: B1=W{b1};B2=B1{b2};Bt=Bt1{bt}; \matrix{{{B_1} = W \cup \{{b_1}\} ;} \cr {{B_2} = {B_1} \cup \{{b_2}\} ;} \cr \ldots \cr {{B_t} = {B_{t - 1}} \cup \{{b_t}\} ;} \cr}

Obviously, we can get WB1Bt = B. For ∀bB, there exists Bx ⊆ (B − {b})x such that Bx = BtxB(t−1)xB1xWx, i.e. BxWx. Based on the covering lower approximation, we can have xB(X), then xPOSB(d). So for every WB, then POSW (d) ⊆ POSB(d).

Theorem 10

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For Bπ,|POSπ (d)| = |POSB(d)| is true if and only if POSπ (d) = POSB(d).

Proof

Here we will not prove it.

Theorem 11

Suppose Icds = (U, π, d) is an inconsistent covering decision system, for every Bπ, if b is a superfluous attribute relative to d in π, then CoreB(d) ⊆ CoreB−{b}(d) is true.

Proof

If aCoreB(d) and B − {a} ⊂ Bπ, then POSπ (d) ⊇ POSB−{a}(d). Since a is an indispensable attribute, then POSπ (d) ≠ POSB−{a}(d), thus we can get x1POSB−{a}(d) such that x1B−{a}(X, we can further get (B−{a})x1X. For every (B − {a})x1X and (B − {a})x1 ⊆ ((B − {a}) − {b})x1, then ((B−{b}) − {a})x1 ((B−{a}) − {b})x1X, which shows that x1POS(B−{b})−{a}(d). Since X have arbitrary, x1POS(B−{b})−{a}(d), thus POS(B−{b})−a(d) ≠ POSB−{a}(d). By the given condition, we will get CoreB−{b}(d) = POSπ (d) and aCoreB−{b}(d). Thus CoreB(d) ⊆ CoreB−{b}(d).

Properties of inconsistent covering decision system based on limimtary information entropy
Lemma 1

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For B, Qπ and POSB(d) = POSQ(d), then LI(B; d) = LI(Q; d).

Proof

For every XU/d, by the definition of positive region, we get POSπ(d)=XU/dB_(X) {POS}_\pi(d) = \mathop \cup \limits_{X \in U/d} \underline B (X) . If every y in U, there exists xiU then By ⊆ [xi]dQy ⊆ [xi]d. Since B(x) = {x : ∀yU (xByByX)}, Q(X) = {x : ∀y ∈ (xQyQyX)} and POSB(d) = POSQ(d), thus we obtain B(X) = π(X). Clearly, we get LD(d|B) = LD(d|Q). By the definition of mutual information, we can obtain I(B; d) = I(Q; d).

Lemma 2

Suppose Icds = (U, π, d) is an inconsistent covering decision system. For every BQπ, if LI(B; d) = LI(Q; d) is true, then POSB(d) = POSQ(d).

Proof

The same is true; here we will not prove it.

Corollary 4

Supposing Icds = (U, π, d) be an inconsistent decision system. For every BQπ, if LI(B; d) = LI(Q; d) is true if and only if POSB(d) = POSQ(d).

Theorem 12

Suppose Icds = (U, π, d) is an inconsistent covering decision system, for every Aiπ, Ai is a superfluous element relative to d in π, if and only if LH(d|π) = LH(d|π − {Ai}).

Proof

If Ai is a superfluous element relative to d in π, by the definition of positive region, we can get POSπ (d) = POSπ−{Ai}(d). And by Lemma 2, we have LI(π − {Ai}; d), thus LH(d|π − {Ai}) = LH(d|π).

If LI(π − {Ai}; d) = LH(d|π) ⇒ I(π; d) = I(π − {Ai}; d) and π − {Ai} ∈ π, by Theorem 10, we can obtain POSπ (d) = POSπ−{Ai}. Therefore, Ai is a superfluous element relative to d in π.

Corollary 5

Supposing Icds = (U, π, d) be an inconsistent decision system. For every Aiπ, Ai is dispensable relative to d in π, if and only if LH(d|C) < LH(d|π − {Ai}).

Corollary 6

Supposing Icds = (U, π, d) be an inconsistent decision system. For every Aiπ, Ai is independent relative to d in π, if and only if LH(d|C) < LH(d|π − {Ai}).

Theorem 13

Suppose Icds = (U, π, d) is an inconsistent decision system, for every B, Qπ, if BQ, then LH(d|B) > LH(d|Q).

Proof

Suppose Cov(B) = {Bx : xU} and Cov(Q) = {Qx : xU}. If B precQ, there exists BxQx for every xU.

Since LH(d|B)LH(d|Q)=1|K|xKlog|[x]dBx||Bx|1|K|xKlog|[x]dQx||Qx|=1|K|2xKlog|[d]dBx||Bx|×|[x]dQx||Qx| LH(d|B) - LH(d|Q) = - {1 \over {|K|}}\sum\limits_{x \in K} \log {{|{{[x]}_d} \cap {B_x}|} \over {|{B_x}|}} - {1 \over {|K|}}\sum\limits_{x \in K} \log {{|{{[x]}_d} \cap {Q_x}|} \over {|{Q_x}|}} = - {1 \over {|K{|^2}}}\sum\limits_{x \in K} \log {{|{{[d]}_d} \cap {B_x}|} \over {|{B_x}|}} \times {{|{{[x]}_d} \cap {Q_x}|} \over {|{Q_x}|}}

If (1) met Bx ⊆ [x]d, Qx ⊆ [x]d and BxQx, then LH(d|B) = LH(d|Q).

If (1) only met BxQx, we obviously can get LH(d|B) > LH(d|Q).

Therefore, LH(d|B) ≥ LH(d|Q).

Theorem 14

Supposing Icds = (U, π, d) be an inconsistent covering decision system, if B precQ for every B, Qπ, then LI(B; d) ≥ LI(Q; d).

Proof

Here we will not prove it.

Theorem 15

Supposing Icds = (U, π, d) be an inconsistent covering decision system. For every B, Qπ, if LH(d|B) > LH(d|Q) and LH(Q|B) = 0, then B ≺ 0.

Proof

Suppose Cov(B) = {Bx : xU} and Cov(Q) = {Qx : xU}. If LH(d|B) > LH(d|Q) is true, then BxQx must be wrong (If BxQx is true, then LH(d|B) ≤ LH(d|Q) by Theorem 13, which is contradiction!), thus we could obtain BxQx or BxQx. If BxQx is true, there at least exists Bx1(x1U), for every Qy1(y1U), then Bx1Qy1, if BxQx ≠ ∅ is true for every xU, then H(Q|B)=1|K|xK|QxBx||Bx|>0 H(Q|B) = - {1 \over {|K|}}\sum\nolimits_{x \in K} {{|{Q_x} \cap {B_x}|} \over {|{B_x}|}} > 0 , which implies a contradiction, thus BxQx is true.

Similarly, we can prove the following theorem:

Theorem 16

Suppose Icds = (U, π, d) is an inconsistent covering decision system. If LI(B; d) ≥ LI(Q; d) and LH(Q B) = 0, B, Qπ, then BQ.

From the description of Theorem 13 through Theorem 16, we know that there exists corresponding relation for one to one between rough of knowledge and information entropy in inconsistent covering decision system.

Based on split policy inconsistent covering decision system for attribute reduction

Well-known scholars in Poland initially proposed discernibility matrix [11], or discernibility function can be used to calculate all attribute reduction in the decision table. Although the resolution matrix and its approach have been widely used, but due to the definition of resolution matrix, the data regarding the degree of inconsistency and its effects are not fully taken into account, so there are limitations. Literature [4, 20, 21] improved methods and discussed the case of inconsistent decision table, so that the former method can obtain the correct (all) attribute reduction results. Hence, such research is of great significance and, ultimately, a new application used in inconsistent decision tables to distinguish Matrices. Further, a method is proposed to distinguish matrix in the literature [31] based on the past, that is, split-based strategies and to distinguish Matrices decision table attribute reduction. Literature [19, 30] presents rough set theory, algorithms and applications, but also specifically pointed out that the resulting matrix method to distinguish demand for inconsistent decision tables is relatively simple errors in the nuclear, and also presented the results of a detailed analysis. Please refer to literature [19, 30].

Supposing U 1 = ∑X inU/d π (X) and U 2 = UU 1

Definition 12

Suppose Icds = (U, π, d) is an inconsistent covering decision system, all subjects on universe, U, are divided into consistent covering sub-table π|U1d|U1 and inconsistent covering sub-table π|U2d|U2. We denote a x× n matrix (mij), called the discernibility matrix of Icds, such that if xu, xjU satisfies {Aπ:(AxiAxj)(AxjAxi)}{ApAq:(ApxiApxj)(AqxjAqxi)} \{A \in \pi :({A_{xi}} \not\subset {A_{xj}}) \wedge ({A_{xj}} \not\subset {A_{xi}})\} \vee \{{A_p} \wedge {A_q}:({A_{pxi}} \subset {A_{pxj}}) \wedge ({A_{qxj}} \subset {A_{qxi}})\}

Theorem 17

Supposing Icds = (U, π, d) be an inconsistent covering decisive system, denoted by IM(π) = {mij} where mij is a single attribute, IM(π) = Cored(π) is true if and only if ∃mij ∈ a single attribute such that mijCored(π).

Proof

We denote Cov(π − {Ai}) = {Bx : xU}, if AiIM(π) is true, then there exists mij = {Ai} for every Ajπ − {Ai} such that Ayj = Axj is true.

Suppose xjπ([xs]d)(s ∈ [1, l]), we will divide them to two parts for further discussion: first we prove IM(π) ⊆ Cored(π). If yjU 1 and fd(xj) ≠ fd(yj) are true, then there exists t ∈ [1, l] and t ≠ s such that yjπ([xy]d) and Bxjπ([xt]d) ≠ ∅.

By Definition 12, Ai is indispensable. If yjU 2 is true, then BxjU 2 = ∅ is true such that ai is indispensable. So IM(π) ⊆ Cored(π) is true.

On the other hand, if AiCored(π) is true, then there exists xsπ([xi]d)(i ∈ [1, k]) such that one of the following conditions is true:

(1) there exists j ∈ [1, k] and ji such that Bxs ∩ [xj]d ≠ ∅;

(2) Bxs ∩ (U − ∑xU ([x]d)) ≠ ∅

If Condition (1) is true, then there exists xt [xj]d and Ajπ − {Ai} such that Axsj = Axij and AxsiAxti, and because of xs ∈ ([xi]d), xt ∈ ([xt ]d), then we can obtain fd(xs) ≠ fd(xt) for xsU 1, xtU 2 such that mst ∈ {Ai}.

If Condition (2) is true, then there exists xrU 2, for every Aj ∈ − π − {Ai} such that Axsj = Axrj and AxsiAxri for xsU 1, xyU 2, therefore we could get msr = {Ai}. So Cored(π) ⊆ IM(π) is true.

Theorem 18

Supposing Icds = (U, π, d) be an inconsistent covering decision system, denoted by subset E = πCore(π), E1E, then POSπ (d) = POSπ−{E1}(d1) is true if and only if for every mij(1 ≤ jin) such that mijE1 is true.

Proof

If there exists E1E such that any element of E1 does not belong to Cored(π), so E1 can be reduced. If for every mij and 1 ≤ jin, then we could get mijE1, which still ensure POSπ (d) = POSπ−{E1}(d1) after reduction of properties on E1 at the same time.

If there exists mij after reduction by properties on E1 contemporarily such that mij and mij = ∅ is true, which implies properties on E1 cannot be reduced at the same time.

Theorem 18 implies that as long as there is a simple observation and treatment for discernibility matrix, we will have cores and reducts in the inconsistent covering decision system. The following Corollary 7 can be founded in the literature [21, 25].

Corollary 8

Suppose Bπ, then B is a relative reduct of π if and only if it is the minimal set satisfying Bmij ≠ ∅ for mij ≠ ∅, i, jn.

Experimental analysis: a test application
Example 1

Here is a car which is to be considered for analysis. Suppose U = {x1, … , x10} to be a set of ten cars, and E ={price; colour; quality; oil-consumption} to be a set of attributes. The values of ‘price’ are {high; middle; low}, the values of ‘colour’ are {pretty; ordinary; poor}, the values of ‘quality’ are {good; bad}, the values of ‘oil-consumption’ are {tiny; relative-tiny; reasonable; numerous}. We have four specialists E = {A, B,C, D} to evaluate the attributes of these cars. Moreover, their evaluation results are not the same when compared with one another. The evaluation results are listed below.

For attribute price: A:high={x1,x2,x4,x6,x7,x8,x9,x10},middle={x3},low={x5};B:high={x1,x2,x3,x5,x6,x8,x9,x10},middle={x4},low={x6,x7};C:high={x1,x2,x3,x4,x8,x9,x10},middle={x8},low={x3,x4,x5,x6,x9};D:high={x1,x2,x3,x5,x6,x8,x9,x10},middle={x7},low={x5,x6}; \matrix{{A:high = \{{x_1},{x_2},{x_4},{x_6},{x_7},{x_8},{x_9},{x_{10}}\},\;\;middle = \{{x_3}\},\;\;low = \{{x_5}\} ;} \cr {B:high = \{{x_1},{x_2},{x_3},{x_5},{x_6},{x_8},{x_9},{x_{10}}\},\;\;middle = \{{x_4}\},\;\;low = \{{x_6},{x_7}\} ;} \cr {C:high = \{{x_1},{x_2},{x_3},{x_4},{x_8},{x_9},{x_{10}}\},\;\;middle = \{{x_8}\},\;\;low = \{{x_3},{x_4},{x_5},{x_6},{x_9}\} ;} \cr {D:high = \{{x_1},{x_2},{x_3},{x_5},{x_6},{x_8},{x_9},{x_{10}}\},\;\;middle = \{{x_7}\},\;\;low = \{{x_5},{x_6}\} ;} \cr}

For attribute color: A:pretty={x1,x2,x3,x4,x5},ordinary={x6,x7,x8,x9},low={x10};B:pretty={x1,x2,x3,x4,x5,x6},ordinary={x7,x8,x9},low={x10};C:pretty={x1,x2,x3,x4,x5,x6,x7},ordinary={x8,x9},low={x10};D:pretty={x1,x2,x3,x4,x5,x7},ordinary={x6,x8,x9},low={x10}; \matrix{{A:pretty = \{{x_1},{x_2},{x_3},{x_4},{x_5}\},\;\;ordinary = \{{x_6},{x_7},{x_8},{x_9}\},\;\;low = \{{x_{10}}\} ;} \cr {B:pretty = \{{x_1},{x_2},{x_3},{x_4},{x_5},{x_6}\},\;\;ordinary = \{{x_7},{x_8},{x_9}\},\;\;low = \{{x_{10}}\} ;} \cr {C:pretty = \{{x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7}\},\;\;ordinary = \{{x_8},{x_9}\},\;\;low = \{{x_{10}}\} ;} \cr {D:pretty = \{{x_1},{x_2},{x_3},{x_4},{x_5},{x_7}\},\;\;ordinary = \{{x_6},{x_8},{x_9}\},\;\;low = \{{x_{10}}\} ;} \cr}

For attribute quality: A:good={x1,x2,x3,x6,x8,x19},bad={x4,x5,x7,x9};B:good={x1,x2,x3,x8,x10},bad={x4,x5,x6,x7,x9};C:good={x1,x6,x8,x9,x10},bad={x2,x3,x4,x5,x7};D:good={x1,x2,x6,x8,x10},bad={x3,x4,x5,x7,x9} \matrix{{A:good = \{{x_1},{x_2},{x_3},{x_6},{x_8},{x_{19}}\},\;\;bad = \{{x_4},{x_5},{x_7},{x_9}\} ;} \cr {B:good = \{{x_1},{x_2},{x_3},{x_8},{x_{10}}\},\;\;bad = \{{x_4},{x_5},{x_6},{x_7},{x_9}\} ;} \cr {C:good = \{{x_1},{x_6},{x_8},{x_9},{x_{10}}\},\;\;bad = \{{x_2},{x_3},{x_4},{x_5},{x_7}\} ;} \cr {D:good = \{{x_1},{x_2},{x_6},{x_8},{x_{10}}\},\;\;bad = \{{x_3},{x_4},{x_5},{x_7},{x_9}\}} \cr}

For attribute oil-consumption: A:tiny={x1,x2},relativetiny={x3,x4,x5},reasonable={x3,x4,x5},numerous={x7,x9};B:tiny={x1,x3},relativetiny={x2,x4,x5,x6},reasonable={x7,x8,x10},numerous={x9};C:tiny={x1,x3},relativetiny={x2,x4,x5,x7},reasonable={x6,x8,x10},numerous={x9};D:tiny={x1,x2,x6},relativetiny={x3,x4,x5},reasonable={x8,x9,x10},numerous={x7,}; \matrix{{A:tiny = \{{x_1},{x_2}\},\;relative - tiny = \{{x_3},{x_4},{x_5}\},\;reasonable = \{{x_3},{x_4},{x_5}\},\;numerous = \{{x_7},{x_9}\} ;} \cr {B:tiny = \{{x_1},{x_3}\},\;relative - tiny = \{{x_2},{x_4},{x_5},{x_6}\},\;reasonable = \{{x_7},{x_8},{x_{10}}\},\;numerous = \{{x_9}\} ;} \cr {C:tiny = \{{x_1},{x_3}\},\;relative - tiny = \{{x_2},{x_4},{x_5},{x_7}\},\;reasonable = \{{x_6},{x_8},{x_{10}}\},\;numerous = \{{x_9}\} ;} \cr {D:tiny = \{{x_1},{x_2},{x_6}\},\;relative - tiny = \{{x_3},{x_4},{x_5}\},\;reasonable = \{{x_8},{x_9},{x_{10}}\},\;numerous = \{{x_7},\} ;} \cr}

We think that the evaluation of every index is has the same importance. Therefore, we get a cover rather than a partition for every car attribute, which implies a certain uncertainty caused by the interpretation of the data. price:A1={{x1,x2,x3,x4,x6,x7,x8,x9,x10},{x3,x4,x6,x7},{x3,x4,x5,x6,x7},colour:A2={{x1,x2,x3,x4,x5,x6,x7},{x6,x7,x8,x9},{x10}},quality:A3={{x1,x2,x3,x6,x8,x9,x10},{x2,x3,x4,x5,x6,x7,x9},}oilconsumption:A4={{x1,2,x3,x6},{x2,x3,x4,x5,x6,x7},{x6,x8,x9,x10},{x6,x7,x9}} \matrix{{price:\;{A_1} = \{\{{x_1},{x_2},{x_3},{x_4},{x_6},{x_7},{x_8},{x_9},{x_{10}}\},\{{x_3},{x_4},{x_6},{x_7}\},\{{x_3},{x_4},{x_5},{x_6},{x_7}\},} \cr {colour:\;{A_2} = \{\{{x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7}\},\{{x_6},{x_7},{x_8},{x_9}\},\{{x_{10}}\} \},} \cr {quality:\;{A_3} = \{\{{x_1},{x_2},{x_3},{x_6},{x_8},{x_9},{x_{10}}\},\{{x_2},{x_3},{x_4},{x_5},{x_6},{x_7},{x_9}\},\}} \cr {oil - consumption:\;{A_4} = \{\{{x_1}{,_2},{x_3},{x_6}\},\{{x_2},{x_3},{x_4},{x_5},{x_6},{x_7}\},\{{x_6},{x_8},{x_9},{x_{10}}\},\{{x_6},{x_7},{x_9}\} \}} \cr}

Final decision d is given as U/d = {sale; further evaluation for sale; against sale}; sale= {x1, x2, x4, x6}, further evaluation for sale= {x4, x5, x7}, against sale= {x1, x2, x4, x6}. Suppose π = {Ai : i = 1, …, 4}, πxi, abridges πi, Bi means Bxi for short, then we can obtain: π1={x1,x2,x3,x6},π2={x3,x2,x6},π3={x3,x6}π4={x3,x4,x6,x7},π5={x3,x4,x5,x7},π6={x6},π7={x6,x7}π8={x6,x8,x9},π9={x6,x9},π10={x10}. \matrix{{{\pi _1} = \{{x_1},{x_2},{x_3},{x_6}\},{\pi _2} = \{{x_3},{x_2},{x_6}\},{\pi _3} = \{{x_3},{x_6}\}} \cr {{\pi _4} = \{{x_3},{x_4},{x_6},{x_7}\},{\pi _5} = \{{x_3},{x_4},{x_5},{x_7}\},{\pi _6} = \{{x_6}\},{\pi _7} = \{{x_6},{x_7}\}} \cr {{\pi _8} = \{{x_6},{x_8},{x_9}\},{\pi _9} = \{{x_6},{x_9}\},{\pi _{10}} = \{{x_{10}}\}.} \cr}

The positive domain of d relative to π is: POSπ(D)=xU/Dπ_(X)={x1,x2,x3,x6,x10} {POS}_\pi(D) = \bigcup\limits_{x \in U/D} \underline \pi (X) = \{{x_1},{x_2},{x_3},{x_6},{x_{10}}\}

Supposing B = πA1, then B1 = {x1, x2, x3, x6}, B2 = B3 = {x2, x3, x6}, B4 = B5 = {x2, x3, x4, x5, x6, x7}, B6 = {x6}, B7 = {x6, x7}, B8 = {x6, x8, x9}, B9 = {x5, x9}, B10 = {x10}, the positive domain of d relative to B is: POSB(D)=xU/DB_(X)={x1,x2,x3,x6,x10} {POS}_B(D) = \bigcup\limits_{x \in U/D} \underline B (X) = \{{x_1},{x_2},{x_3},{x_6},{x_{10}}\}

As to (1) and (2), we could obtain POSB(D) = POSπ (D). By the Definition 12, Ai is a superfluous relative to d in π. Here we can see πx1πx4,πx4πx1Bx1Bx4,Bx4Bx1, {\pi _{x1}} \not\subset {\pi _{x4}},{\pi _{x4}} \not\subset {\pi _{x1}} \Rightarrow {B_{x1}} \not\subset {B_{x4}},{B_{x4}} \not\subset {B_{x1}}, and πx2πx4,πx4πx2Bx2Bx4,πx3πx4Bx3Bx4. {\pi _{x2}} \not\subset {\pi _{x4}},{\pi _{x4}} \not\subset {\pi _{x2}} \Rightarrow {B_{x2}} \subset {B_{x4}},{\pi _{x3}} \subset {\pi _{x4}} \Rightarrow {B_{x3}} \subset {B_{x4}}.

The uppermost relation of x2, x4 to π changes after Ai is deSupposinged from π. A1 is a superfluous element of π relative to D, so it is an exemplar of inconsistent covering decision system.

Suppose U 1 = {x1, x2, x3, x6, x10} and U 2 = {x4, x5, x7, x8, x9}. By the Definition 12, we have the discernibility matrix of inconsistent covering decision system (U, π, D), which is follows (covers have been distinguished i instead of Ai, otherwise 0 instead of π): [0000{2,4}{3,4}{1,3,4}{3,4}{2,4}{2,4}0000{2,4}{13,23,3,4}{1,3,4}{23,13,3,4}{2,4}{2,4}0000{2,4}{3,4}{1,3,4}{23,3,4}{1,2,4}{1,2,4}0000{2,3,4}{3,4}{1,2,3,4}{3,4}{1,2,4}{1,2,4}{2,4}{2,4}{2,4}{2}0{2,3,4}{1,2,3,4}{2,3,4}{2}{2}] \left[ {\matrix{0 & 0 & 0 & 0 & {\{2,4\}} & {\{3,4\}} & {\{1,3,4\}} & {\{3,4\}} & {\{2,4\}} & {\{2,4\}} \cr 0 & 0 & 0 & 0 & {\{2,4\}} & {\{1 \wedge 3,2 \wedge 3,3,4\}} & {\{1,3,4\}} & {\{2 \wedge 3,1 \wedge 3,3,4\}} & {\{2,4\}} & {\{2,4\}} \cr 0 & 0 & 0 & 0 & {\{2,4\}} & {\{3,4\}} & {\{1,3,4\}} & {\{2 \wedge 3,3,4\}} & {\{1,2,4\}} & {\{1,2,4\}} \cr 0 & 0 & 0 & 0 & {\{2,3,4\}} & {\{3,4\}} & {\{1,2,3,4\}} & {\{3,4\}} & {\{1,2,4\}} & {\{1,2,4\}} \cr {\{2,4\}} & {\{2,4\}} & {\{2,4\}} & {\{2\}} & 0 & {\{2,3,4\}} & {\{1,2,3,4\}} & {\{2,3,4\}} & {\{2\}} & {\{2\}} \cr {} & {} & {} & {} & {} & {} & {} & {} & {} & {} \cr}} \right] and f (U, π)(Ā1, Ā2, Ā3, Ā1) = ∧{∨mij : 1 ≤ j < i ≤ 10, mij ≠ ∅ } = (A1A3A4) ∧ (A2A4) ∧ (A3A4) ∧ (A2A4) ∧ (A1A3A4) ∧ ((A1A3) ∨ (A2A3) ∨ A3A4) ∧ (A1A2A4) ∧ ((A2A3) ∨ A3A4) ∧ (A1A3A4) ∧ (A2A3A4) ∧ (A3A4) ∧ (A1A2A3A4) ∧{A2} = (A2A4) ∨ (A2A3), so Red(π)={{A3,A4},{A2,A3}},CoreD(π)={A2}. {Red} (\pi) = \{\{{A_3},{A_4}\},\{{A_2},{A_3}\} \},\;{Core}_D(\pi) = \{{A_2}\}.

It should be pointed out that if the covering decision system is consistent, then the method proposed in this section is equivalent to the one in Section 4. If is a partition, then the method adopted in this section is just the method for computing relative reducts of traditional rough sets in the literature [32] to ensure that we find the smallest reduction.

If these ten cars are trial samples, then we have two different kinds of evaluation references for other input samples: {colour; oil-consumption}, {colour; quality}. Clearly, the attribute is the key attribute for the evaluation of cars.

To illustrate the methods of space and computational complexity in the section, we will compare our methods with the methods of literature [21, 23, 24], such that if n = |U1| + |U2| satisfies,

(1) The space complexity can be compared: without considering compression and storage of symmetric matrix, the elements of discernibility matrix in the section are |U1| × n, while the elements in the literature [21] are n × n.

(2) The computational complexity can be compared: the computational complexity in literature [21, 23, 24] is O(m × n × logn) + O(m × n2), while the method in this section is O(m × n × logn) + O(m × |U1| × n).

It is evident that the space and computational complexity in the section are lower than the literature [21]. Therefore, the methods in this section could be used effectively not only to reduce the computational cost, but also in providing a new framework to certain extent based on the covering rough sets theory.

Conclusions

According to classical rough sets theory, attributes of decision systems consist of two parts namely conditional attributes and decision attributes. Every conditional attribute decide a partition in a complete decision system. The abstract information systems which come from reality problems are mostly incomplete decision system. Every conditional attribute in this decision system determines a cover of U. This paper mainly studies theories and methods of systems and discusses about related attribute reduction for covering decision information reduction algorithms on the basis of conditional information entropy. Moreover, attribute reduction of covering decision systems also have wide applications in the three-way, which indicates the importance of the direction of research currently.

Z. Pawlak. Rough sets. Computer and Information Sciences 11(1982) 341–356. PawlakZ. Rough sets Computer and Information Sciences 11 1982 341 356 10.1007/BF01001956 Search in Google Scholar

H. Yu, D.C. Yang. Decision Table Reduction based on Conditional Information Entropy 07(2002) 759–756. YuH. YangD.C. Decision Table Reduction based on Conditional Information Entropy 07 2002 759 756 Search in Google Scholar

J.N. Mordeson, Rough set theory applied to (fuzzy) ideal theory, Fuzzy Sets and Systems 121(2001) 315–324. MordesonJ.N. Rough set theory applied to (fuzzy) ideal theory Fuzzy Sets and Systems 121 2001 315 324 10.1016/S0165-0114(00)00023-3 Search in Google Scholar

G. Cattaneo. Abstract approximate spaces for rough theories[M], in: Polkowski, Skowron (Eds.), Rough Sets in Knowledge Discovery 1: Methodology and Applications, Physicaverlaf, Heidelberg, 1998, pp. 59–98. CattaneoG. Abstract approximate spaces for rough theories[M] in: PolkowskiSkowron (Eds.), Rough Sets in Knowledge Discovery 1: Methodology and Applications Physicaverlaf Heidelberg 1998 59 98 Search in Google Scholar

H.S. Nguyen, D. Slezak. Approximation reducts and association rules correspondence and complexity results, in: N. Zhong, A. Skowron, S. Oshuga (Eds.), Proceedings of RSFDGrC’99[C]. Japan: LNAI1711, 1999. NguyenH.S. SlezakD. Approximation reducts and association rules correspondence and complexity results in: ZhongN. SkowronA. OshugaS. (Eds.), Proceedings of RSFDGrC’99[C] Japan LNAI1711 1999 Search in Google Scholar

M. Yang. Approximate Reduction Based on Conditional information Entropy in Decision Tables. Acta Electronica Sinica 11(2007) 2156–2160. YangM. Approximate Reduction Based on Conditional information Entropy in Decision Tables Acta Electronica Sinica 11 2007 2156 2160 Search in Google Scholar

Z.W. Mo. Some Notes on Entropy and Rough Set Theory. Journal of Sichuan Normal University (Natural Science) 03(2002) 257–260. MoZ.W. Some Notes on Entropy and Rough Set Theory Journal of Sichuan Normal University (Natural Science) 03 2002 257 260 Search in Google Scholar

P. Yang. Approximate reduction based on conditional information entropy over vertically partitioned multi-decision table. Control and Decision 10(2008) 1103–1108. YangP. Approximate reduction based on conditional information entropy over vertically partitioned multi-decision table Control and Decision 10 2008 1103 1108 Search in Google Scholar

Y. Wang. A Knowledge Reduction Method Based on Information Entropy and Discernibility Matrix. Journal of Sichuan College of Education 3(2008) 07–10. WangY. A Knowledge Reduction Method Based on Information Entropy and Discernibility Matrix Journal of Sichuan College of Education 3 2008 07 10 Search in Google Scholar

Z. Pawlak. Rough sets: Theoreticsl Aspects of Reasoning About Data[M]. Dordrecht: Kluwer Academic Publishing, 1991. PawlakZ. Rough sets: Theoreticsl Aspects of Reasoning About Data[M] Dordrecht Kluwer Academic Publishing 1991 10.1007/978-94-011-3534-4 Search in Google Scholar

Z. Pawlak, Andrzej Skowron. Rudiments of rough sets, Information Sicences 177(2006) 3–27. PawlakZ. SkowronAndrzej Rudiments of rough sets Information Sicences 177 2006 3 27 10.1016/j.ins.2006.06.003 Search in Google Scholar

Z. Pawlak, Andrzej Skowron. Rough sets and Boolean reasoning. Information Sciences 177(2006) 28–40. PawlakZ. SkowronAndrzej Rough sets and Boolean reasoning Information Sciences 177 2006 28 40 10.1016/j.ins.2006.06.007 Search in Google Scholar

W. Ziarko. Variable precision rough set model. Computer and System Sciences 46(1993) 39–59. ZiarkoW. Variable precision rough set model Computer and System Sciences 46 1993 39 59 10.1016/0022-0000(93)90048-2 Search in Google Scholar

W.-X. Zhang, W.-Z. Wu, J.-Y. Liang, D.-Y. Li. Theory and method of rough sets[J]. Beijing: Science Press, 2001. ZhangW.-X. WuW.-Z. LiangJ.-Y. LiD.-Y. Theory and method of rough sets[J] Beijing Science Press 2001 Search in Google Scholar

B. Huang, X. He, X.Z. Zhou. Rough Entropy Based on Generalized Rough sets Covering Reduction. Journal of software 15(2004) 215–218. HuangB. HeX. ZhouX.Z. Rough Entropy Based on Generalized Rough sets Covering Reduction Journal of software 15 2004 215 218 Search in Google Scholar

D.G. Chen, C.Z. Wang Chang, Q.H. Hu. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets. Information Sciences 177(20–07) 3500–3518. ChenD.G. Wang ChangC.Z. HuQ.H. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets Information Sciences 177 20–07 3500 3518 10.1016/j.ins.2007.02.041 Search in Google Scholar

Z. Bonikowski, E. Bryniarski, U. Wybraniec, Extensions and intensions in the rough set theory, Information Sciences 107(1998) 149–167. BonikowskiZ. BryniarskiE. WybraniecU. Extensions and intensions in the rough set theory Information Sciences 107 1998 149 167 10.1016/S0020-0255(97)10046-9 Search in Google Scholar

C.D. Yang. Research on decision systems reduction with rough sets. Harbin Engineering University 2011, PP:1–120. YangC.D. Research on decision systems reduction with rough sets Harbin Engineering University 2011 1 120 Search in Google Scholar

H. Guo. Research on knowledge reduction based on rough set theory for the inconsistent decision systems 2016, pp:1–150. GuoH. Research on knowledge reduction based on rough set theory for the inconsistent decision systems 2016 1 150 Search in Google Scholar

Y.P. Shi, Y. Huang, C.Z. Wang, Q. He. Attribute reduction based on the Boolean matrix. Granular Computing 4(2019) 313–322. ShiY.P. HuangY. WangC.Z. HeQ. Attribute reduction based on the Boolean matrix Granular Computing 4 2019 313 322 10.1007/s41066-018-0108-3 Search in Google Scholar

F. Li, Y.Q. Yin. Approaches to knowledge reduction of reduction of covering decision systems based on information theory. Information Sciences 179(2009) 694–1704. LiF. YinY.Q. Approaches to knowledge reduction of reduction of covering decision systems based on information theory Information Sciences 179 2009 694 1704 10.1016/j.ins.2008.12.025 Search in Google Scholar

D.L. Ma. The construction of decision tree based on the covering rough set theory[J]. Beijing: North China Electric University 2016:1–41. MaD.L. The construction of decision tree based on the covering rough set theory[J] Beijing North China Electric University 2016 1 41 Search in Google Scholar

M.P. Chen, et al. Multi-label attribute reduction algorithm based on neighborhood rough set. Journal of Minnan Normal University (Natural Science) 31(2018) 1–11. ChenM.P. Multi-label attribute reduction algorithm based on neighborhood rough set Journal of Minnan Normal University (Natural Science) 31 2018 1 11 Search in Google Scholar

Y.L. Zhang, et al. Attribute reduction of covering decision information system based on evidence theory. Pattern recognition and artificial intelligence 31(2018) 797–808. ZhangY.L. Attribute reduction of covering decision information system based on evidence theory Pattern recognition and artificial intelligence 31 2018 797 808 Search in Google Scholar

X. Zhang, et al. Algorithms of rule acquisition and confidence-preserved attribute reduction in covering decision systems. Journal of Shangdong University (Natural Science) 53(2018)120–126. ZhangX. Algorithms of rule acquisition and confidence-preserved attribute reduction in covering decision systems Journal of Shangdong University (Natural Science) 53 2018 120 126 Search in Google Scholar

M.R. Forster, Key concepts in model selection: performance and generalizabilitu, J. Math. Psychol. 44(2000) 205–231. ForsterM.R. Key concepts in model selection: performance and generalizabilitu J. Math. Psychol. 44 2000 205 231 10.1006/jmps.1999.128410733865 Search in Google Scholar

P.W. Woodward, J.C. Naylor, An application of Bayesian methods in SPC, Statisitician 42(1993) 461–469 WoodwardP.W. NaylorJ.C. An application of Bayesian methods in SPC Statisitician 42 1993 461 469 10.2307/2348478 Search in Google Scholar

H. Yu, Z.G. Liu, G. Y. Wang. An automatic method to determine the number of clusters using decision-theoretic rough sets, Int. J. Approx. Reason 55(2014) 101–115. YuH. LiuZ.G. WangG. Y. An automatic method to determine the number of clusters using decision-theoretic rough sets Int. J. Approx. Reason 55 2014 101 115 10.1016/j.ijar.2013.03.018 Search in Google Scholar

B. Zhou, Y.Y. Yao. J.G. Luo, Cost-sensitive three-way email spam filtering, J. Intell. Inf. syst 42(20–14) 19–45. ZhouB. YaoY.Y. LuoJ.G. Cost-sensitive three-way email spam filtering J. Intell. Inf. syst 42 20–14 19 45 10.1007/s10844-013-0254-7 Search in Google Scholar

Z.H. Jiang, X.B. Yang, H.L. Yu, D. Liu, P.X. Wang, Y.H. Qia. Accelerator for multi-granularity attribute reduction. Knowledge-Based Systems 04(2019) 145–158. JiangZ.H. YangX.B. YuH.L. LiuD. WangP.X. QiaY.H. Accelerator for multi-granularity attribute reduction Knowledge-Based Systems 04 2019 145 158 10.1016/j.knosys.2019.04.014 Search in Google Scholar

Y.L. Zhang, J.J. Li. Relative reduction of covering decision systems. Journal of engineering mathematics 05(2009) 930–935. ZhangY.L. LiJ.J. Relative reduction of covering decision systems Journal of engineering mathematics 05 2009 930 935 Search in Google Scholar

Lech Polkowski, Shusaku Tsumoto, Tsau Y. Lin. Rough set methods and applicaftions: new developments in knowledge discovery in information systems[M]. NewYork: Physical-Verlag, 2000. PolkowskiLech TsumotoShusaku LinTsau Y. Rough set methods and applicaftions: new developments in knowledge discovery in information systems[M] NewYork Physical-Verlag 2000 10.1007/978-3-7908-1840-6 Search in Google Scholar

Polecane artykuły z Trend MD

Zaplanuj zdalną konferencję ze Sciendo