# Rule Extraction Model Based on Decision Dependency Degree

Authors: Xinying Chen; Guanyu Li; Yunhao Sun
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Rule extraction is the core in rough set. Two procedures are contained in rule extraction: one is attribute reduction and another is attribute value reduction. It was proved through computational complexity perspective that obtaining all the reduction, minimum attribute reduction, and minimum attribute value reduction is an NP problem. So, generally, a heuristic reduction method is used to solve attribute reduction and attribute value reduction. However, for most heuristic methods, it is hard to put into practice and has high cost on computational complexity. Moreover, part of the methods extracted redundant rules. To approach a quick and effective model for rule extraction in decision systems, against the concept of distinguishable relation, relevant concepts and basic theorems of rule extraction are proposed. In order to get concise and accurate rules quickly, algorithms for finding conflict object set, finding duplicate object set, and finding redundant rules are given. After that, using decision dependency degree as attribute importance to determine the importance of each attribute in rule object, a new rule extraction model based on decision dependency degree is proposed in this paper. Compared with the previous models, this model does not generate matrix; instead, it finds conflict object set and duplicate object set by equivalence class, and consequently, improves the time performance tomaxOCU, OC2U/C, and OREDU/C/RED2. The theoretical analysis and experimental research show that the new model more accurately and effectively reduces the redundant data and extracts more concise decision rules from dataset.


---

## Body

## 1. Introduction

Today, in this ubiquitous and intelligent interconnection environment, after integration, cleansing, and transformation, the data information in the dataset (denoted by information system in this paper) from all kinds of perceived data and context data is not equally important [1]. Some are even redundant, which will interfere with policymakers and will seriously affect the efficiency on the followup operations. Hereby, it is necessary to perform attribute reduction and attribute value reduction or similar simplifying process on the dataset to reduce redundancy and extract decision rules before executing the followup operations.Rough set is a data induction tool, which can effectively process massive data [2, 3]. One of the main advantages of Rough Set is that it does not need any preliminary or additional information about data, such as dataset probability distribution or grade membership. Without any information other than the dataset itself, Rough Set can keep original classification information unchanged and start with the description set of a problem and then get the essential features and inherent law of the problem by deleting redundant information.Rule extraction is the core in Rough Set. By rule extraction, clarity of the knowledge system can be improved and decision knowledge underneath dataset can be found out. Two procedures are contained in rule extraction: one is attribute reduction [4–13] and another is attribute value reduction [14–28].By conducting the attribute reduction on the decision system, redundant information can be removed from the system. In the premise of ensuring decision system has the same distinguishability, attribute reduction can simplify and improve clarity of the original system to a certain extent. However, after attribute reduction on the whole system, the system is not the most simplified system. In the system, each rule object may contain redundant information; that is, all condition attribute values of each rule object are not equally important and are not necessary to impact decision rules extraction execution. Therefore, to improve the quality of data reduction, it is mandatory to evaluate all condition attribute values for each rule object and remove redundant condition attribute values which have no impact on performing rule extraction. This process is named as attribute value reduction in decision systems. Using attribute reduction and attribute value reduction, small and concise decision rules can be extracted from the original system. After that, data from the system can be simply presented as the valuable and straightforward information, which can be easily used.It was proved through computational complexity perspective that to get all the reduction, minimum attribute reduction, and minimum attribute value reduction is an NP problem by Wong and Ziarko [3]. Because of the computational complexity of getting core attributes and value-core attributes during the process of attribute reduction and attribute value reduction, moreover, with big volume of candidates for reduction, the NP problem indicates that it is easy to get combination explosion. So, generally, a heuristic reduction method is used to solve attribute reduction and attribute value reduction.Today, value reduction of decision systems is one of important topics in research and application of Rough Set. Researchers have done a lot of research work and gradually put forward some methods, primarily including value reduction algorithms based on discernibility matrix [14–22] and heuristic value reduction algorithms [23–28]. However, when using discernibility matrix to get value reduction on decision systems with massive data, a huge matrix is required, which leads to high cost on time-space complexity during constructing and traversing the matrix. Therefore, it needs furthermore research on discernibility matrix methods. For most heuristic methods, it is hard to put into practice and has high cost on computational complexity. Moreover, part of the methods extracted redundant rules, for example, methods in [23].To resolve the above problems and reduce the time-space complexity, with learning from tradition reduction algorithms, we propose a new heuristic value reduction and rule extraction model. The model will use an improved chain base sorting method to perform sorting and equivalence class partitioning on the system and then will compare rule objects. Moreover, it will use conditional equivalence class to determine conflict objects and duplicate objects. So, the time cost generated by comparison of rule objects is significantly decreased. At the same time, the model uses theory of decisive distinguishable matrix (but never create the interim result) to determine the importance of attributes, which effectively control the complexity. This model will perform attribute reduction before performing value reduction. After the reduction, the count of condition attributes in reduction will not be very big. Compared with the current known methods, even with massive data, this model can significantly reduce time-space complexity and improve efficiency.Term distinguishable object set is named under distinguishable relationship. Against this concept, theorems on distinguishable object set and consistency in decision system are given. With the theorems, formalized concept on attribute value reduction, theorem on value-core attribute of object, and formalized concepts on conflict object set and duplicate object set during value reduction are defined. After that, algorithms for conflict object set, duplicate object set, and redundant rules are proposed, respectively. With dependency based on distinguishable relation, an attribute value reduction and rule extraction model are given for decision systems. At last, the correctness and feasibility of the model are proved by specific examples and experiments. The model can provide effective solution on data value reduction and decision rule extraction for all kinds of intelligent networking systems and intelligent control systems.


## 2. Attribute Reduction of Decision Systems

Definition 1 (decision system).
LetS=U,A be an information system. U = x1,x2,…,xn is a nonempty finite object set, called universe. A = a1,a2,…,am is a nonempty finite attribute set, called attribute set. If A consists of a condition attribute set C and a decision attribute set D and two sets satisfy C∪D=A and C∩D = ∅, then S is a decision system which is denoted by U,C∪D. When there is only one decision attribute in D, the decision system is denoted by U,C∪d commonly.
In general, the basic structure of decision systemS = U,C∪d is shown in Table 1.Table 1
Basic structure of decision system.
U
Condition attributes
Decision attribute
a
1
a
2
a
3
…
a
j
…
a
m
d
x
1
0
1
1
…
1
…
3
1
x
2
1
1
0
…
1
…
2
1
…
…
…
…
…
…
…
…
…
x
i
3
1
0
…
1
…
4
1
…
…
…
…
…
…
…
…
…
x
n
0
1
3
…
1
…
1
0Definition 2 (equivalence class).
LetS=U,C∪D be a decision system. For any P⊆C∪D, P≠∅, define the indiscernibility relation as follows:(1)indP=xi,xjxi,xj∈U×U,∀ak∈P,fkxi=fkxj.And the equivalence class of object xii≤n according to attribute set P is defined as follows:(2)xiindP=xjxi,xj∈indP.
The indiscernibility relationindP corresponds to a partition of U, and the partition is denoted by U/indP. In general, U/P is used as the abbreviation.
Ifxi,xj∈indP, then xi and xj are indiscernible by P. xiindP contains all the objects that are indiscernible with xi by attribute set P. That is, an equivalence class is a set of objects with the same condition attributes and the same decision attributes in universe.Definition 3 (attribute reduction of decision system).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. If RP⊆RC (that is, indP⊆indC), then P is a consistent set of S [28]. Furthermore, if P is a consistent set and any Q⊂P is not a consistent set of S, then P is called as an attribute reduction of S [28].
The attribute reduction of a decision system is a reduction for its condition attributes. The attribute reduction is the smallest subset of the condition attribute set found on the premise of maintaining the original system classification ability.


## 3. Distinguishable Relation and Consistent Reduction with Distinguishability

In order to facilitate subsequent discussion and research, related concepts and theorems are given as follows.Among them, Definition4 “Distinguishable Relation of Attribute Set” is discussed from the perspective of distinguishability between objects, while Definition 2 “Indiscernibility Relation and Equivalence Class” in the previous section is discussed from the perspective of indiscernibility between objects.And, definitions “Consistent Reduction with Distinguishability” and “Decisive Distinguishable Matrix” are based on Definition4, while Definition 3 “Attribute Reduction of Decision System” in the previous section is based on Definition 2.Based on the distinguishable relation of attribute set, the traditional logical knowledge granulation process related to Definition3 can be transformed into matrix computing and the rapid reduction of redundant attributes can be realized.Definition 4 (distinguishable relation of attribute set).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. Define the distinguishable relation of P as follows:(3)DISP=xi,xjxi,xj∈U×U,∃ak∈P,fkxi≠fkxj.
DIS
P is used as the distinguishable relation of P.
Ifxi,xj∈DISP, then xi and xj are distinguishable by P. That is, there is a condition attribute, and the attribute values of the two objects are different.Definition 5 (distinguishable unit set of attribute set).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. If xi,xj∈DISP, then xi,xj is called a distinguishable unit. The distinguishable unit set of P is denoted by DISPU.
DIS
P
U contains all the units that can be distinguished by P.Definition 6 (distinguishable unit set of attribute).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. For any attribute ak∈C, let(4)DISak=xi,xjxi,xj∈U×U,fkxi≠fkxj.
DIS
a
k is used as the distinguishable relation of ak. The distinguishable unit set of ak is denoted by DISakU, which contains all the units that can be distinguished by ak.
Based on Definition4, Definition 5, and Definition 6, the definition of 7 “Consistent Reduction with Distinguishability” is given as follows.Definition 7 (consistent reduction with distinguishability).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. If DISP∩DISD=DISC∩DISD, then P is a consistent attribute set with distinguishability of S [28]. For any Q⊂P and Q≠∅, if DISP∩DISD=DISC∩DISD and DISQ∩DISD≠DISC∩DISD, then P is a consistent reduction with distinguishability of S [28].
Under the premise of keeping the system classification ability unchanged, a consistent reduction with distinguishability can be achieved after deleting the irrelevant or unimportant knowledge.Definition 8 (decisive distinguishable matrix).
LetS=U,C∪D,C=m, and U=n. For any attribute ak∈C, let(5)mk¯∗=xi,xjxi,xj∈DISD,xi,xj∈DISak.
m
k
¯
∗ is used as the kth column vector of the decisive distinguishable matrix Mk¯∗, which contains n2 rows and m columns.
m
k
¯
∗ is the intersection of DISD and DISak. Given a decision system S=U,P∪D, P⊆C and P≠∅, Mp¯∗ is used as the decisive distinguishable matrix of S.Definition 9 (core with distinguishability).
For a decision systemS=U,C∪D, which has r reductions, Pkk=1,2,…,r, a core set with distinguishability of S is defined as follows:(6)CORE∗=∩1≤k≤rPk.
In the process of attribute reduction, the core cannot be deleted from the attribute set. Because the distinguishability of the core cannot be replaced by other attributes, the core is indispensable in expressing the distinguishability of the system. The distinguishability of other noncore attributes can be replaced by other attributes.Theorem 1.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent:(1)
S is a consistent decision system(2)
DISC⊇DISD(3)
indC⊆indDProof.
(2)⟺ (3). Evidently, DISC⊇DISD is equivalent to U×U−DISP⊇U×U−DISC. That is, for any xi,xj∈U×U, if xi,xj∈U×U−DISC, then xi,xj∈U×U−DISD.
According to Definition5 and Definition 6, if xi,xj∈U×U−DISC, then xi and xj are indistinguishable by C. That is, xiindC=xjindC. Similarly, if xi,xj∈U×U−DISD, then xi and xj are indistinguishable by D. That is, xiindD=xjindD.
Thus,U×U−DISP⊇U×U−DISC is equivalent to any xi,xj∈U×U, if xiindC=xjindC, then xiindD=xjindD. That is, indC⊆indD. Therefore, (2) ⟺ (3).
Similarly, it can be proved that (1)⟺ (2).Theorem 2.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. DISP has the following properties.(1)
IfP1⊆P2⊆C, then DISP1⊆DISP2D⊆DISC(2)
DISP=∪ak∈PDISakProof.
The proof of Theorem2 is similar to that of Theorem 2 in [27].Theorem 3.
LetS=U,C∪D be a decision system, P⊆C and P≠∅, then MP∗=DISP∩DISD.Proof.
According to Definition8, for any ak∈P, mk∗¯=DISak∩DISD, and MP∗=∪mk¯∗. Thus, according to property 2 in Theorem 2, MP∗=DISP∩DISD.Theorem 4.
LetS=U,C∪D be a decision system; then, consistent reduction with distinguishability must exist.Theorem 5.
LetS=U,C∪D be a decision system. In decision system S, consistent set and consistent attribute set with distinguishability are equivalent.Theorem 6.
LetS=U,C∪D be a decision system. In decision system S, attribute reduction and consistent reduction with distinguishability are equivalent.Theorem 7.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent.(1)
P is a consistent attribute set with distinguishability(2)
DISP∩DISD⊇DISC∩DISD(3)
P≡CTheorem 8.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent.(1)
P is a consistent attribute set with distinguishability(2)
DISP∩DISD⊇DISC∩DISD, and ∀Q⊂P,DISQ∩DISD≠DISC∩DISD(3)
P≡C, and ∀Q⊂P, Q≡C is not true
The proof of above theorems is similar to the proof of Theorems 11 to 15 in [29] (not elaborated here).


## 4. Decision Dependency Degree Based on Distinguishable Relation

Based on the distinguishable relation, Definition10 and Definition 11 are proposed as follows. Definition 10 “Dependency Based on Distinguishable Relation” is used to determine whether there is a dependency relationship between the attribute sets P1 and P2. And Definition 11 “Dependency Degree based on Distinguishable Relation” is used to assess the extent of the dependency or replacement relationship that exists between P1 and P2.Definition 10 (dependency based on distinguishable relation).
LetS=U,C∪D be a decision system, P1,P2⊆C and P1,P2≠∅. Then, the definition “dependency based on distinguishable relation” is defined as follows:(1)
Attribute setP2 depends on attribute set P1 based on distinguishable relation iff DISP2∩DISD⊆DISP1∩DISD. This decision dependency can be denoted as P1⟹P2.(2)
Attribute setP2 is equivalent to attribute set P1 based on distinguishable relation iff P1⟹P2 and P2⟹P1. This equivalent relationship can be denoted as P1≡P2. It is obvious that P1≡P2, iff DISP2∩DISD⊆DISp1∩DISD.Definition 11 (distinguishable relation-based dependency degree).
LetS=U,C∪D be a decision system, P1,P2⊆C and P1,P2≠∅; if decision dependency degree k0≤k≤1 is denoted as(7)kp2P1=1−DISP2∩DISDDISP1∩DISD,then the extent to which P2 depends on attribute set P1 based on distinguishable relation is k0≤k≤1, called as P2. k depends on P1 (P2 depends on P1 in k decision dependency degree), or P1 can be substituted by P2 in 1−k decision substitution degree, which is denoted as P1⟹kP2.(1)
Ifk=0, named P2 does not depend on P1 based on distinguishable relation, or P1 can be completely replaced (substituted) by P2(2)
If0<k<1, named P2 partly depends on P1 based on distinguishable relation, or P1 can be partly replaced (substituted) by P2(3)
Ifk=1, named P2 completely depends on P1 based on distinguishable relation, or there does not exist decision substitution relationship between P1 and P2Theorem 9.
LetS=U,C∪D be a decision system, P1,P2⊆C, P1,P2≠∅, and P1⟹P2; then, the following propositions are true:(1)
Decision dependency degreekP2P1 is 0 if MP1∗=MP2∗(2)
Decision dependency degreekP2P1 is 1 if MP2∗=0 or DISP2∩DISD=∅Proof.
(1)
According to Theorem3, it is obvious that kP2P1=1−MP2∗/MP1∗. Thus, kP2P1 is 0 if MP1∗=MP2∗.
(2)
According to Definition11 and Theorem 3, it is obvious that kP2P1 is 1 if DISP2∩DISD=∅ or MP2∗=0.Theorem 10.
LetS=U,C∪D be a decision system, P1,P2⊆C, P1,P2≠∅, and P1⟹P2; MP2∗ is inversely proportional to decision dependency degree kP2P1 and is proportional to decision substitution degree.Proof.
According to Definition11 and Theorem 3, it is obvious that MP2∗ is inversely proportional to decision dependency degree kP2P1 and is proportional to decision substitution degree.
With the above analysis,kP2P1=1−MP2∗/MP1∗ can well reflect the decision dependency and decision substitution relationship between P1 and P2. Due to the denominator MC∗ being a fixed value and inversely proportional to kPC, the decision dependence degree of P can be directly calculated by MP∗.


## 5. Value-Core Attribute Set of Object and Attribute Value Reduction Set

Performing reduction on the decision system, a simplified attribute set can be achieved without impacting the distinguishability of the original system. However, for each object instance in the decision system after reduction, there still exists an attribute redundancy problem. Here, obtaining minimum attribute reduction for each object instance is equivalent to value reduction.Because the distinguishability of core attributes in the decision system cannot be substituted during attribute reduction, core attributes are objected to be removed. The others can be replaced. Similar to the existence of core attributes during attribute reduction, there are value-core attributes during attribute value reduction. The definition “value-core attribute” is defined in value reduction in Rough Set.After performing attribute reduction and deleting duplicate object instances, there is not any duplicate object instance in the system. Each object instance corresponds to a rule. These object instances are named as “rule object” (or simply “rule” for short) in this paper. At this point, the rule object has less clustering power, which is not conducive to matching object instances. In order to improve the clustering ability, similar to attribute reduction, for each rule object, the distinguishability of each condition attribute should be evaluated. Rules can be simplified and summarized by removing redundant and non-value-core condition attributes. Thus, the ability of rules to match instances is improved.Given a decision systemS′=U′,P∪D, U′⊆U and P⊆C. If S′ is a consistent decision system, then in S′, ∀xi∈U′ and ∀aj∈P, after removing aj from xi, the consistency of S′ will be changed. And there exist three scenarios as follows:(1)
After deletingaj from xi, in the S′, ∃xk∈U′, those remaining condition attribute values for xi and xk are the same while decision attribute values are not. That is, decision conflict occurs. In such a case, aj is a value-core attribute of xi and should not be deleted. Hereby, aj has to be recovered.Similarly, ifaj is removed from xk, in the S′, ∃xi∈U′, decision conflict is surely found between xi and xk. In such a case, aj is also a value-core attribute of xk and should not be deleted. Hereby, aj has to be recovered.This shows that in systemS′, ∀xi∈U′,∀aj∈P, if aj is removed, xi has decision conflict with other objects. That is, consistency of system S′ is changed after removing aj, which makes S′ to be an inconsistent system. In such a case, aj is the value-core attribute of xi and of other conflict objects with xi. aj can avoid decision conflict between xi and other objects. So it should not be removed from those objects.(2)
After deletingaj, in the S′, ∃xk∈U′, both condition attribute values and decision attribute values for xi and xk are the same. That is, no decision conflict is generated while duplicate objects arise. In such a case, aj is not a value-core attribute of xi and it will not impact the decision for new duplicate object. Hereby, aj can be removed.Similarly, ifaj is removed from xk, in the S′, ∃xi∈U′, both condition attribute values and decision attribute values for xi and xk are the same; that is, xk is the new duplicate object of xi. In such a case, aj is not a value-core attribute of xk. Hereby, aj can be removed.This shows that in systemS′, ∀xi∈U′,∀aj∈P, if aj is removed, there are new objects which are duplicate objects for xi; then, aj is not a value-core attribute for all duplicate objects including xi. So it can be removed.(3)
After deletingaj, in the S′, there is no decision conflict or duplicate objects. Hereby, according to existing information, it cannot be determined whether the deletion on aj of xi will impact decision consistency of the system or not. Additional information has to be considered on how to proceed on aj.Combined with above analysis, definitions “Distinguishable Set of Object”, theorems of “Distinguishable Set of Object” and “System Consistency” are given. With the theorems, formalized definitions “Attribute Value Reduction,” “Value-core Attribute of Object,” “Conflict Object Set,” and “Duplicate Object Set” during value reduction are proposed.Definition 12 (distinguishable set of object).
LetS=U,C∪D be a decision system, P⊆C and P≠∅. For any xi∈U, let(8)DISPxi=xjxi,xj∈U×U,xi,xj∈DISPU.
DIS
P
x
i is used as the distinguishable set of xi. Object xj belongs to distinguishable unit xi,xj which is generated by DISP in universe. Hereby, DISPxi can also be defined as(9)DISPxi=xjxi,xj∈U×U,∃ak∈P,fkxi≠fkxj.
LetS=U,C∪D be a decision system and S′=U′,RED∪D be a decision system after attribute reduction where RED is an attribute reduction of S. For ∀xi∈U′, DISREDxi=U′-1 is true.
It shows that after reduction, derived from attribute reductionRED, for ∀xi∈U′, the distinguishable set of xi is DISREDxi=U′−xi. That is, after reduction, for ∀xi∈U′, xi can be distinguishable with all the other objects in U′ by RED.Theorem 11.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent:(1)
S=U,P∪D is a consistent decision system(2)
DISP⊇DISD(3)
For∀xi∈U, DISPxi⊇DISDxiProof.
According to Theorem1, it is obvious that (1) ⟺ (2).(2)⟺ (3). According to Theorem 1, DISP⊇DISD is equivalent to indP⊆indD, that is, DISP⊇DISD is equivalent to ∀xi∈U, xiP⊆xiD (namely, xiindP⊆xiindD). As xiP=U−DISPxi and xiD=U−DISDxi, xiP⊆xiD is equivalent to U−DISPxi⊆U−DISDxi, that is equivalent to DISPxi⊇DISDxi. Thus, for ∀xi∈U, xiP⊆xiD is equivalent to DISPxi⊇DISDxi. Therefore, DISP⊇DISD is equivalent to ∀xi∈U, DISPxi⊇DISDxi.From the above theorems, if objects that can be distinguished withxi by condition attributes are more or at least equal to objects that can be distinguished with xi by decision attributes, the system is a consistent decision system. That is, only when all the distinguishable objects deduced by condition attribute set P contain those deduced by decision attribute set D, the system is a consistent decision system. In another word, if all the objects in system meet the condition DISPxi⊇DISDxi, the system is a consistent decision system.Theorem 12.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent:(1)
For∀xi∈U, DISPxi⊇DISDxi(2)
For∀xi∈U, DISPxi⊇DISP∪Dxi(3)
For∀xi∈U, DISPxi=DISP∪DxiProof.
(1)⟺ (2).According to Theorem1, it is obvious that ∀xi∈U and DISPxi⊇DISDxi is equivalent to S=U,P∪D, which is a consistent decision system; that is, DISP⊇DISD is true.According to Theorem1, DISP⊇DISD is equivalent to indP⊆indD, and DISP⊇DISD is equivalent to ∀xi∈U, xiP⊆xiD (that is, xiindP⊆xiindD). As xiP⊆xiD is equivalent to xiP∩xiP⊆xiD∩xiP, xiP⊆xiD, is equivalent to xiP⊆xiP∪D. Thus, DISP⊇DISD is equivalent to ∀xi∈U and xiP⊆xiP∪D.BecausexiP=U−DISPxi and xiP∪D=U−DISP∪Dxi, xiP⊆xiP∪D is equivalent to U−DISPxi⊆U−DISP∪Dxi. That is, xiP⊆xiP∪D is equivalent to DISPxi⊇DISP∪Dxi. Thus, ∀xi∈U, xiP⊆xiP∪D is equivalent to ∀xi∈U, and DISPxi⊇DISP∪Dxi.Therefore,∀xi∈U, DISPxi⊇DISDxi is equivalent to ∀xi∈U, and DISPxi=DISP∪Dxi.(2)⟺ (3).It is obvious thatP⊆P∪D. According to Theorem 2, DISPxi⊆DISP∪Dxi is true. Thus, DISPxi⊇DISP∪Dxi is equivalent to DISPxi=DISP∪Dxi.Theorem 13.
LetS=U,C∪D be a decision system, P⊆C and P≠∅. The following propositions are equivalent: (1) S=U,P∪D is a inconsistent decision system (2) ∃xi∈U, DISPxi⊂DISP∪Dxi (3) ∃xi∈U, DISPxi≠DISP∪Dxi.Proof.
(1)⟺ (2).
According to Theorem11, it is obvious that S=U,P∪D is a consistent decision system, which is equivalent to ∀xi∈U and DISPxi⊇DISDxi. Then, S=U,P∪D is a inconsistent decision system, which is equivalent to ¬∀xi∈U,DISPxi⊇DISDxi.
According to Theorem12, it is obvious that ∀xi∈U, DISPxi⊇DISDxi is equivalent to ∀xi∈U, and DISPxi⊇DISP∪Dxi:(10)so¬∀xi∈U,DISPxi⊇DISDxi,⟺¬∀xi∈U,DISPxi⊇DISP∪Dxi,⟺¬∀xi∈U,U−DISPxi⊆U−DISP∪Dxi.
BecausexiP=U−DISPxi and xiP∪D=U−DISP∪Dxi,(11)¬∀xi∈U,U−DISPxi⊆U−DISP∪Dxi,⟺¬∀xi∈U,xiP⊆xiP∪D.
BecausexiP∪D is equivalent to xiD∩​xiP, according to the definition and properties of equivalence class, xiP⊇xiP∪D is true, so the reasoning process is as follows:(12)¬∀xi∈U,xiP⊆xiP∪D,⟺∃xi∈U,xiP⊇xiP∪D,⟺∃xi∈U,U−DISPxi⊇U−DISP∪Dxi,⟺∃xi∈U,DISpxi⊂DISP∪Dxi.
S
=
U
,
P
∪
D is a inconsistent decision system ⟺∃xi∈UandDISpxi⊂DISP∪Dxi.
Thus, Proposition (1) is equivalent to Proposition (2).
(1)⟺ (3).
BecausexiP∪D is equivalent to xiD∩xiP, according to the definition and properties of equivalence class, xiP⊇xiP∪D is true, so the reasoning process is as follows:(13)¬∀xi∈U,xiP⊆xiP∪D,⟺¬∀xi∈U,xiP=xiP∪D,⟺∃xi∈U,xiP≠xiP∪D,⟺∃xi∈U,U−DISPxi≠U−DISP∪Dxi,⟺∃xi∈U,DISPxi≠DISP∪Dxi.
Alternatively, according to Theorem1, Theorem 2, and Theorem 12, the reasoning process is as follows:
S
=
U
,
P
∪
D is a consistent decision system:(14)⟺∀xi∈U,DISPxi⊇DISDxi,⟺∀xi∈U,DISPxi⊇DISP∪Dxi,⟺∀xi∈U,DISPxi=DISP∪Dxi.
Thus,S=U,P∪D is an inconsistent decision system:(15)⟺¬∀xi∈U,DISPxi=DISP∪Dxi,⟺∃xi∈U,DISPxi≠DISP∪Dxi.Definition 13 (value-core attribute set of object).
LetS=U,P∪D be a consistent decision system, if ∀xi∈U, ∃aj∈P⊆C, and P≠∅ satisfy DISP−aj∪Dxi≠DISP−ajxi, then attribute set CORExi=ajaj∈P⊆C,DISP−aj∪Dxi≠DISP−ajxi is called value-core attribute set of xi and P−CORExi is called non-value-core attribute set of xi.
The distinguishability of the value-core cannot be replaced by other condition attributes, while the distinguishability of non-value-core attributes can be replaced by other attributes. The rule can be simplified and generalized by evaluating and deleting redundant non-value-core attributes.Definition 14 (attribute value reduction set).
LetS=U,P∪D be a consistent decision system; if ∀xi∈U, ∃P⊆C, and P≠∅ satisfy DISPxi=DISP∪Dxi and satisfy DISPxi=DISP∪Dxi for ∀Q⊂P, then P is called an attribute value reduction set of xi.
Based on the above definitions and theorems, it can be proved that the distinguishability ofxi and the original consistency of S will not change based on the attribute value reduction set P only, and no objects can be found with the same condition attribute values and different decision attribute values with xi. For any xi∈U, if attribute set P⊆C arises and meets the conditions DISPxi=DISP∪Dxi, then the process is finished.Theorem 14.
LetS=U,C∪D be a decision system, xi∈U, if xi has r value reduction sets, Pkk=1,2,…,r, then value-core attribute sets and attribute value reduction sets of xi satisfy (comply with) the following formula:(16)CORExi=∩1≤k≤rPk.
The value-core attribute set is the intersection of all value reductions, and all attributes in it are essential and indispensable for every value reduction.


## 6. Algorithm for Conflict Object Set and Duplicate Object Set

Based on Theorem11, Theorem 12, and Theorem 13, the definitions of “Conflict Object Set” and “Duplicate Object Set” are given as follows.Definition 15 (conflict object set).
LetS=U,C∪D be a consistent decision system, RED be an attribute reduction of S, and S′=U′,RED∪D be a decision system after reduction. If ∀xi∈U′, ∃aj∈RED, and P=RED−aj satisfy DISPxi≠DISP∪Dxi (or DISPxi<DISP∪Dxi), then object set U−DISPxi (xiP) is called as conflict object set of P.
ConditionDISPxi≠DISP∪Dxi shows that DISPxi is not equal to U′−xi. Due to the lack of aj in P, DISPxi∪xi becomes a conflict object set. That is, ∃xk∈U′ satisfies xi,xk∉DISP (xk∉DISPxi) and xi,xk∈DISP∪D (xk∈DISP∪Dxi). In another word, xi and xk are indistinguishable by P only, but xi and xk are distinguishable by P∪D. In one word, S″=U′,P∪D is an inconsistent decision system. In the system, conflict objects exist which have the same condition attribute values and different decision attribute values. Moreover, the conflict objects lead to the inconsistency of S″.Definition 16 (duplicate object set).
LetS=U,P∪D be a consistent decision system, RED be an attribute reduction of S, and S′=U′,RED∪D be a decision system after reduction. If ∀xi∈U′, ∃aj∈RED, and P=RED−aj satisfy DISPxi=DISP∪Dxi (or DISPxi=DISP∪Dxi) and DISPxi≠DISREDxi (or DISPxi≠U′−1 or DISPxi<U′−1), then object set U−DISPxi (xiP) is called duplicate object set of S′ after reduction.
ConditionsDISPxi=DISP∪Dxi and DISPxi≠DISREDxi show that DISPxi=DISP∪Dxi≠U′−xi is true by P or by P∪D. Due to the lack of aj in P, DISPxi∪xi becomes an indistinguishable object set without any conflict. That is, ∃xk∈U′, which satisfies xi,xk∉DISP (xk∉DISPxi) and xi,xk∉DISP∪D (xk∉DISP∪Dxi) and xi,xk∈DISRED (xk∈DISREDxi). In another word, xi and xk are indistinguishable by P or P∪D, but xi and xk are distinguishable by RED. In one word, S″=U′,P∪D is a consistent decision system, where duplicate objects exist with the same condition attribute values and same decision attribute values, and the consistency of S″ is not changed while the distinguishability of S″ is changed by the conflict objects.
Based on the above formal analysis and definitions (especially, Definitions15 and 16), an algorithm for conflict object set and duplicate object set (ConDup algorithm) is designed in Algorithm 1.
In AlgorithmConDup, xj denotes the current condition equivalence class, C is used to count the base of xj, and D is used to count the number of decision values in xj.
Steps 3–30 are the main part of the algorithm. Steps 5–20 are used to calculate the conflict object set and duplicate object set ofxj. The condition “Cxj!=1&&Dxj==1” shows the base of xj is greater than 1, and all the objects in xj have the same decision attribute values, namely, xj is not a conflict equivalence class but a duplicated equivalence class. Then, all objects in xj should be added into U∗. If the condition “Cxj!=1&&Dxj==1” is not true while “Cxj!=1&&Dxj!=1” is true, it shows that the base of xj is greater than 1 and all the objects in xj have different decision attribute values, namely, xj is not a duplicated equivalence class but a conflict equivalence class. Then, all objects in xj should be added into U+. In addition, steps 21–24 are used to judge whether xj and xj+1 are duplicate objects or not. Steps 25–29 are used to judge whether xj and xj+1 are conflict objects or not.
The time complexity ofConDup is mainly decided by steps 3–30. Generally, D is 1 or far less than P. So, the time complexity is OPU+ODU = maxOPU,ODU=OPU.Algorithm 1:
ConDup algorithm.
Input: a sorted decision system S=U″,P∪D
Output: a duplicate object set U∗ and a conflict object set U+
(1)
Initialize arraysC and D to 1
(2)
Let pointers point to x1
(3)
for each xj,xj+1∈U do
(4)
Flag = 0
(5)
for each ai∈P do
(6)
if fixj≠fixj+1, then
(7)
if Cxj!=1&&Dxj==1, then
(8)
xj⟶U∗
(9)
end
(10)
if Cxj!=1&&Dxj!=1, then
(11)
xj⟶U∗
(12)
end
(13)
j = j + 1
(14)
Flag = 1
(15)
Let pointers point to xj
(16)
break
(17)
else
(18)
i = i + 1
(19)
end
(20)
end
(21)
if Flag == 0&&∀di∈Dfixj==fixj+1, then
(22)
Cxj++
(23)
j = j + 1
(24)
end
(25)
if Flag == 0&&∃di∈Dfixj≠fixj+1, then
(26)
Cxj++
(27)
Dxj++
(28)
j = j + 1
(29)
end
(30)
end
(31)
OutputU∗ and U+


## 7. Algorithm for Redundant Rule Object Set

After performing value reduction, some rule objects may contain the same decision attributes. Moreover, the attribute value set of one object may be the subset of another object’s. Namely, inclusion relation may exist among these rule objects. Actually, the longer rule objects are redundant, which should be removed from the current system.With the removal of the redundant rules, the rule generalization can be promoted in the system and a more simplified system can be achieved.Based on the above analysis, for∀xt∈U∗, the condition that rule object xt is a redundant rule is that at least one rule object xs∈U∗ exists, which complies with the following conditions:(1)xs and xt belong to the same decision equivalent class. (2) xs and xt have the same values among their condition attribute intersection. (3) The rule length of xs (that is, the number of xs’s condition attributes with value) is less than xt’s.If there existxs and xt satisfying condition (3), it means there exists proper relationship between the attribute values set of xs and xt’s. If there exist xs and xt satisfying all the three conditions, it means that xt is a redundant rule and should be added into redundant rule object set U−.In [29], algorithm RedSetU,P∪D sorts objects based on D+P firstly and then adds the first objects of consistent condition equivalent classes into U′ to get U/P. According to RedSetU,P∪D and the characteristic of redundant rules, an algorithm for redundant rule object set (RedRul algorithm) is designed in Algorithm 2.Algorithm 2:
RedRul algorithm.
Input: marked decision system S∗=U∗,RED∪D
Output: redundant rule object set U−
(1)
Min_rule =x1
(2)
for each xj∈U do
(3)
Flag = 0
(4)
for each di∈D do
(5)
if fiMin_rule ≠ fixj then
(6)
Min_rule =xj
(7)
Flag = 1
(8)
Break
(9)
else
(10)
i=i+1
(11)
end
(12)
end
(13)
ifFlag == 0&& Min_rule and xj have the same exact values among their condition attribute setthen
(14)
ifthe rule length of xj is less than Min_rule’sthen
(15)
Min_rule ⟶U−
(16)
Min_rule =xj
(17)
else
(18)
xj⟶U−
(19)
end
(20)
end
(21)
ifFlag == 0&& Min_rule and xj do not have the same exact values among their condition attribute setthen
(22)
Min_rule =xj
(23)
end
(24)
j=j+1
(25)
end
(26)
OutputU−


## 8. Rule Extraction Model against Decision Dependency Degree

### 8.1. Rule Extraction Model

As the core problem in Rough Set, many scholars have studied the value reduction and rule extraction algorithms and achieved more results [14–28].After analyzing most of the existing algorithms, it is found that some algorithms are unreasonable for the selection and deletion of condition attributes, and some algorithms have more complicated calculation processes. These algorithms have a higher time and space complexity due to the construction of a discernibility matrix or discernibility function. Moreover, most algorithms are based on algorithms in [23]. The basic principle of those algorithms in [23] is as follows: when performing value reduction on the decision system, for each row of the decision system, where attribute reduction has been finished, it is treated as one decision rule object. For each rule object, its attributes are deleted one by one; at the same time, decision conflict is determined to verify if the deletion is valid or not. With the above principle repeated, value reduction will be achieved finally.Compared with the previous models, the rule extraction model designed in this paper does not generate matrix and its basic idea is when seeking the minimum reduction, the decision dependency degree is achieved and the value-core attributes that have the greatest impact on decision-making are achieved. After achieving the value-core attributes of the object, the decision dependency degree is used as the attribute importance information to determine the importance of other attributes. Under the premise of without causing a decision conflict or maintaining system consistency, subsequent attribute values are evaluated by the decision dependency degree. With the above principle repeated, a more refined decision rules set (abbreviated asDRS) is achieved and the rule extraction process is completed.Based on the above basic idea, a rule extraction model against decision dependency degree (DecDep_Rul Algorithm) is designed as follows.


### 8.2. Related Algorithms

LetS=U,C∪D be a decision system, P⊆C. Several algorithms from [29] will be used in the rule extraction model proposed in this paper. Here is a brief introduction.Generally, the sorting algorithm mainly implements the sorting process by comparing and moving keywords. The average time complexity of the sorting process is preferablyOUlogU. For example, Liu Shao-Hui et al. [30] use the quick sort method against condition attribute set C to perform equivalence class partitioning on universe, which results in time complexity OCUlogU for the reduction model. However, it is not necessary to compare key in pair for base sort. One universe sorting method RadSortU,P∪D is given in [29] against static chain base sorting, which has time complexity OPU (normally D equals to 1 or far less than P in reality).In [29], the algorithm RedSetU,P∪D extracts the first element of all equivalence classes of the universe. During the extraction from the whole universe, RadSort ensures the consistency of the system and has time complexity OPU. Working with the sorting method RadSort, the algorithm RedSet can effectively reduce the size of universe from U to U/P.In [29], the algorithm DecDep_DegU′,P∪D is used for obtaining MP∗ of P. When obtaining MP∗, DecDep_Deg uses the idea of Definition 9 (corresponding to the Definition 8 in this paper), which does not create decisive distinguishable matrix as the interim result; hereby, the complexity is controlled to OPU′ (Algorithm 3).Algorithm 3:
DecDep_Rul algorithm.
Input: decision system S=U,C∪D
Output: the decision rule set DSR
(1)
CallDecDep_Red U,C∪D reduction model in [29] to get S′=U′,RED∪D; initialize rule set DSR
(2)
CallRadSort U′,RED∪D and RedSet (U′, RED∪D) in [29] to get S″=U″,RED∪D
(3)
for each ai∈RED do
(4)
LetP=RED−ai; call RadSort U″,P∪D and DecDep_Deg U″,P∪D in [29] to get MP∗ of P
(5)
end
(6)
Add relevant attributes intoArray in descending order according to the achieved MP∗ values
(7)
for each ai∈RED do
(8)
LetP=RED−ai and call RadSort U″,P∪D
(9)
CallConDup U″,P∪D to get U+ and U∗
(10)
Execute a mark procedure to getS∗=U″,RED∪D
(11)
end
(12)
for each xi∈S∗ do
(13)
if P!==∅, then
(14)
For all attributes ofxi++, add attributes with original value to P, add attributes with “!” to P!
(15)
end
(16)
if P==∅, then
(17)
LetP=aArray0; Restore faArray!fxi to its original value and update P!
(18)
end
(19)
for each aj∈P! do
(20)
Arrayaj⟶Array!
(21)
end
(22)
CallRadSort U″,P∪D and get U+xi
(23)
while U+xi!=0
(24)
RestorefaArray!j++xi to its original value
(25)
UpdateP and P!
(26)
CallRadSort U″,P∪D and update U+xi
(27)
end
(28)
Replace each “!” with “∗” for all attribute value of xi; and update S∗=U″,RED∪D
(29)
end
(30)
CallRedSort U″,RED∪D
(31)
CallRedSet U″,RED∪D, delete duplicate rules, and delete rules only with “∗” to update U∗ of S∗
(32)
CallRedSort U∗,RED∪D
(33)
CallRedRul U∗,RED∪D to get U−
(34)
ForS∗ = U∗,RED∪D, update U∗=U∗− U−
(35)
Delete “∗” in each rule of U∗ to get DSRIn [29], the attribute importance reduction model based on decision dependency degree is given with Theorems 11 to 15 (corresponding to Theorems 4 to 8 in this paper). The model DecDep_RedU,C∪D uses the bottom-up method, with core CORE as fundamentals and with decision dependency degree τaiC−CORE as heuristic information. The time complexity of the model is maxOCU,OC2U/C.


### 8.3. Analyzing the Rule Extraction Model Based on Decision Dependency

LetS=U,C∪D be a decision system, P⊆C. The steps of model DecDep_Rul are analyzed in the order of execution as follows.Firstly, an attribute reduction modelDecDep_RedU,C∪D as defined in [29] is called in step 1 to complete the attribute reduction and to get reduced decision system S′=U′,RED∪D. After that, in step 2, RadSortU′,RED∪D and RedSetU′,RED∪D in [29] are called to complete extraction on global universe. With deletion of redundant object, new system S″=U″,RED∪D is achieved.Meanwhile, based on decision dependency degree, in steps 3–5,MP∗ of attribute set P=RED−ai is achieved for any ai∈RED, where MP∗ is distinguishability of P. Since the distinguishability of RED is constant, so when MP∗ is smaller, it means without ai the distinguishable relationship of P becomes more weak. That is, the smaller the MP∗ is, the stronger distinguishability of ai is. In step 6, the count of MP∗ is RED, and relevant attributes are added into Array according to each MP∗ in the descending order.Steps 7–11 are to mark the system. For each object in the system, its useless attributes are marked as redundant attributes with “∗,” its value-core attributes whose absence will lead to decision conflict are kept the original values, and the rest are marked with “!” for further assessment on whether to keep or remove. In step 8, RadSortU″,P∪D is called to sort all rule objects by D+P, which can make step 9 efficient. In step 9, ConDupU″,P∪D is called. It determines whether current equivalence class is conflict equivalence class or duplicate equivalence class and gets conflict object set U+ and duplicate object set U∗. After that, the mark procedure is executed in step 10. The step replaces the value of ai with “∗” for objects in U∗, keeps the original value of ai for objects in U+, and replaces the value of ai with “!” for objects in U″−U∗−U+.In steps 12–29, for each object, its non-value-core attributes are evaluated and marked with “!” to decide whether to keep or remove. The attribute setP! is used to store attributes marked as “!.” And relevant attributes are added into Array! in descending order according to the MP∗ values. Array!j is the sequence number of the relevant attribute for each object. In step 22, RadSortU″,P∪D is called. As system S″ is sorted by RadSortU″,P∪D, where attribute set P of xi keeps original values, it is easy and fast to get conditional equivalence of xi. In this condition equivalence class, objects which have the same condition attribute values with P of xi and have different decision attribute values are counted to get decision conflict set U+xi of xi. In steps 23–27, the attribute of xi with the minimum MP∗ is restored to original value, where Array!j is the sequence number of that attribute for xi. After that, attribute set P is updated by adding attribute aArray!j and attribute set P! is updated by deleting aArray!j. RadSortU″,P∪D is called to sort unmarked system S″ by D+P and to update conflict set U+xi of xi. At the end of the loop processing, U+xi is empty. At that time, the decision can be determined by all of the attributes with original value from xi. At last in steps 28-29, all “!” of xi are set to “∗” to achieve a new marked system S∗=U″,RED∪D.AlgorithmRadSortU″,P∪D is called in step 30 to sort universe U″ of the marked system S∗=U″,RED∪D by D+RED. RadSetU″,P∪D is called in step 31 to delete full rule and to delete potentially duplicate decision rules and then update universe U∗ of the marked system S∗=U∗,RED∪D.R
a
d
S
o
r
t uses two operations distribution and collection in [29] to sort object in universe by attribute set. In short, RadSort mainly adopts the base sort method, where “distribution” is actually to find equivalence class. Together with the characteristics of redundancy rules, if rule objects in universe can be aggregated according to decision attribute after the sorting, that is, rule objects with the same decision attribute can be adjacent; then, it is easy for searching and deleting redundancy rules. Thereafter, all the rule objects can be “distributed” and “collected” by condition attributes; after that, all the objects can be “distributed” and “collected” by decision attributes to sort the whole universe by decision equivalence class and sort decision equivalence class by conditional equivalence class.To this end,RadSortU∗,RED∪D is called in step 32 to sort rule objects in current universe U∗ by RED+D (which is not by D+P as mentioned in [29]). That is, when sorting by RED+D, for any ai∈RED+D, if columns 0 to m − 2 from RED+D are condition attributes after reduction and column m − 1 is a decision attribute, then i can take values from 0 to m − 1 in ascending order. As RadSort will perform base sort by condition attributes firstly, followed by the decision attribute, rule objects with the same decision value will be gathered in groups; then, it is easy to get decision equivalence class. Therefore, it is easy to determine inclusion relationship among rule instances.The importance ofai will be evaluated by MP∗ and attribute with smaller MP∗ will give preference to change from “!” to original value. Similarly, when sorting rule objects by RED, it is reasonable to perform the sort later for those attributes with smaller MP∗. As a result, after sorting universe, attributes of rule objects with original value will be found in the top column (top column attribute with stronger distinguishability). Then, it is convenient to compare, search, and locate multiple redundancy rule objects, among which exist inclusion relationships.After sorting the whole universe byRED∪D with RadSortU∗,RED∪D, rule objects will be aggregated by decision equivalence class and condition equivalence class. In step 33, RedRulU∗,RED∪D is called to get redundancy rules set U− from U∗. At last, in step 34, the difference between rule objects set U∗ and redundancy rules set U− is nonredundancy rules set. After deleting “∗” in this nonredundancy rules set, a rule set DSR is finally achieved after reduction.


### 8.4. Analysis of Model Time Complexity

Step 1 is the attribute reduction model in [29]. The time complexity of the model is maxOCU,OC2U/C. The other steps, that is, steps 2–35, are composed of attribute value reduction model.Thereinto, time complexity of step 2 isOREDU′. Time complexity of steps 3–5 is ORED×ORED−1U″+ORED−1U″=OREDRED−1U″=ORED2U″. The time complexity of ConDup is mainly decided by steps 3–30. Generally, D is 1 or far less than P. So, the time complexity is OPU+ODU=maxOPU,ODU=OPU. Time complexity of steps 7–11 is mainly decided by steps 8 and 9, so time complexity of steps 7–11 is ORED×ORED−1U″+ORED−1U″=OREDRED−1U″=ORED2U″. Time complexity of steps 12–29 is mainly decided by steps 22–27, so time complexity of steps 12–29 is OU″×OPU″+OU″×OPxiP+OU+xi×OPU″+OPxiP=OPU″2. Because P is the attribute set of keeping original value of object and maxP = RED, so time complexity of steps 12–29 is OPU″2=OREDU″2. Time complexity of step 30 is OREDU″. Time complexity of step 31 is OREDU″. And time complexity of steps 32–34 is OREDU∗+OREDU∗=OREDU∗.Given the above analysis, time complexity of steps 2–35 ismaxOREDU′, ORED2U″, and OREDU″2.AsU′ is U/C and U″ is U′/RED, U′=U/C and U″=U′/RED=U/C/RED. That is, time complexity of the rule extraction model is maxOCU, OC2U/C, OREDU′, ORED2U″, OREDU″2 = maxOCU, OC2U/C, OREDU″2 = maxOCU, OC2U/C, OREDU/C/RED2.


## 8.1. Rule Extraction Model

As the core problem in Rough Set, many scholars have studied the value reduction and rule extraction algorithms and achieved more results [14–28].After analyzing most of the existing algorithms, it is found that some algorithms are unreasonable for the selection and deletion of condition attributes, and some algorithms have more complicated calculation processes. These algorithms have a higher time and space complexity due to the construction of a discernibility matrix or discernibility function. Moreover, most algorithms are based on algorithms in [23]. The basic principle of those algorithms in [23] is as follows: when performing value reduction on the decision system, for each row of the decision system, where attribute reduction has been finished, it is treated as one decision rule object. For each rule object, its attributes are deleted one by one; at the same time, decision conflict is determined to verify if the deletion is valid or not. With the above principle repeated, value reduction will be achieved finally.Compared with the previous models, the rule extraction model designed in this paper does not generate matrix and its basic idea is when seeking the minimum reduction, the decision dependency degree is achieved and the value-core attributes that have the greatest impact on decision-making are achieved. After achieving the value-core attributes of the object, the decision dependency degree is used as the attribute importance information to determine the importance of other attributes. Under the premise of without causing a decision conflict or maintaining system consistency, subsequent attribute values are evaluated by the decision dependency degree. With the above principle repeated, a more refined decision rules set (abbreviated asDRS) is achieved and the rule extraction process is completed.Based on the above basic idea, a rule extraction model against decision dependency degree (DecDep_Rul Algorithm) is designed as follows.


## 8.2. Related Algorithms

LetS=U,C∪D be a decision system, P⊆C. Several algorithms from [29] will be used in the rule extraction model proposed in this paper. Here is a brief introduction.Generally, the sorting algorithm mainly implements the sorting process by comparing and moving keywords. The average time complexity of the sorting process is preferablyOUlogU. For example, Liu Shao-Hui et al. [30] use the quick sort method against condition attribute set C to perform equivalence class partitioning on universe, which results in time complexity OCUlogU for the reduction model. However, it is not necessary to compare key in pair for base sort. One universe sorting method RadSortU,P∪D is given in [29] against static chain base sorting, which has time complexity OPU (normally D equals to 1 or far less than P in reality).In [29], the algorithm RedSetU,P∪D extracts the first element of all equivalence classes of the universe. During the extraction from the whole universe, RadSort ensures the consistency of the system and has time complexity OPU. Working with the sorting method RadSort, the algorithm RedSet can effectively reduce the size of universe from U to U/P.In [29], the algorithm DecDep_DegU′,P∪D is used for obtaining MP∗ of P. When obtaining MP∗, DecDep_Deg uses the idea of Definition 9 (corresponding to the Definition 8 in this paper), which does not create decisive distinguishable matrix as the interim result; hereby, the complexity is controlled to OPU′ (Algorithm 3).Algorithm 3:
DecDep_Rul algorithm.
Input: decision system S=U,C∪D
Output: the decision rule set DSR
(1)
CallDecDep_Red U,C∪D reduction model in [29] to get S′=U′,RED∪D; initialize rule set DSR
(2)
CallRadSort U′,RED∪D and RedSet (U′, RED∪D) in [29] to get S″=U″,RED∪D
(3)
for each ai∈RED do
(4)
LetP=RED−ai; call RadSort U″,P∪D and DecDep_Deg U″,P∪D in [29] to get MP∗ of P
(5)
end
(6)
Add relevant attributes intoArray in descending order according to the achieved MP∗ values
(7)
for each ai∈RED do
(8)
LetP=RED−ai and call RadSort U″,P∪D
(9)
CallConDup U″,P∪D to get U+ and U∗
(10)
Execute a mark procedure to getS∗=U″,RED∪D
(11)
end
(12)
for each xi∈S∗ do
(13)
if P!==∅, then
(14)
For all attributes ofxi++, add attributes with original value to P, add attributes with “!” to P!
(15)
end
(16)
if P==∅, then
(17)
LetP=aArray0; Restore faArray!fxi to its original value and update P!
(18)
end
(19)
for each aj∈P! do
(20)
Arrayaj⟶Array!
(21)
end
(22)
CallRadSort U″,P∪D and get U+xi
(23)
while U+xi!=0
(24)
RestorefaArray!j++xi to its original value
(25)
UpdateP and P!
(26)
CallRadSort U″,P∪D and update U+xi
(27)
end
(28)
Replace each “!” with “∗” for all attribute value of xi; and update S∗=U″,RED∪D
(29)
end
(30)
CallRedSort U″,RED∪D
(31)
CallRedSet U″,RED∪D, delete duplicate rules, and delete rules only with “∗” to update U∗ of S∗
(32)
CallRedSort U∗,RED∪D
(33)
CallRedRul U∗,RED∪D to get U−
(34)
ForS∗ = U∗,RED∪D, update U∗=U∗− U−
(35)
Delete “∗” in each rule of U∗ to get DSRIn [29], the attribute importance reduction model based on decision dependency degree is given with Theorems 11 to 15 (corresponding to Theorems 4 to 8 in this paper). The model DecDep_RedU,C∪D uses the bottom-up method, with core CORE as fundamentals and with decision dependency degree τaiC−CORE as heuristic information. The time complexity of the model is maxOCU,OC2U/C.


## 8.3. Analyzing the Rule Extraction Model Based on Decision Dependency

LetS=U,C∪D be a decision system, P⊆C. The steps of model DecDep_Rul are analyzed in the order of execution as follows.Firstly, an attribute reduction modelDecDep_RedU,C∪D as defined in [29] is called in step 1 to complete the attribute reduction and to get reduced decision system S′=U′,RED∪D. After that, in step 2, RadSortU′,RED∪D and RedSetU′,RED∪D in [29] are called to complete extraction on global universe. With deletion of redundant object, new system S″=U″,RED∪D is achieved.Meanwhile, based on decision dependency degree, in steps 3–5,MP∗ of attribute set P=RED−ai is achieved for any ai∈RED, where MP∗ is distinguishability of P. Since the distinguishability of RED is constant, so when MP∗ is smaller, it means without ai the distinguishable relationship of P becomes more weak. That is, the smaller the MP∗ is, the stronger distinguishability of ai is. In step 6, the count of MP∗ is RED, and relevant attributes are added into Array according to each MP∗ in the descending order.Steps 7–11 are to mark the system. For each object in the system, its useless attributes are marked as redundant attributes with “∗,” its value-core attributes whose absence will lead to decision conflict are kept the original values, and the rest are marked with “!” for further assessment on whether to keep or remove. In step 8, RadSortU″,P∪D is called to sort all rule objects by D+P, which can make step 9 efficient. In step 9, ConDupU″,P∪D is called. It determines whether current equivalence class is conflict equivalence class or duplicate equivalence class and gets conflict object set U+ and duplicate object set U∗. After that, the mark procedure is executed in step 10. The step replaces the value of ai with “∗” for objects in U∗, keeps the original value of ai for objects in U+, and replaces the value of ai with “!” for objects in U″−U∗−U+.In steps 12–29, for each object, its non-value-core attributes are evaluated and marked with “!” to decide whether to keep or remove. The attribute setP! is used to store attributes marked as “!.” And relevant attributes are added into Array! in descending order according to the MP∗ values. Array!j is the sequence number of the relevant attribute for each object. In step 22, RadSortU″,P∪D is called. As system S″ is sorted by RadSortU″,P∪D, where attribute set P of xi keeps original values, it is easy and fast to get conditional equivalence of xi. In this condition equivalence class, objects which have the same condition attribute values with P of xi and have different decision attribute values are counted to get decision conflict set U+xi of xi. In steps 23–27, the attribute of xi with the minimum MP∗ is restored to original value, where Array!j is the sequence number of that attribute for xi. After that, attribute set P is updated by adding attribute aArray!j and attribute set P! is updated by deleting aArray!j. RadSortU″,P∪D is called to sort unmarked system S″ by D+P and to update conflict set U+xi of xi. At the end of the loop processing, U+xi is empty. At that time, the decision can be determined by all of the attributes with original value from xi. At last in steps 28-29, all “!” of xi are set to “∗” to achieve a new marked system S∗=U″,RED∪D.AlgorithmRadSortU″,P∪D is called in step 30 to sort universe U″ of the marked system S∗=U″,RED∪D by D+RED. RadSetU″,P∪D is called in step 31 to delete full rule and to delete potentially duplicate decision rules and then update universe U∗ of the marked system S∗=U∗,RED∪D.R
a
d
S
o
r
t uses two operations distribution and collection in [29] to sort object in universe by attribute set. In short, RadSort mainly adopts the base sort method, where “distribution” is actually to find equivalence class. Together with the characteristics of redundancy rules, if rule objects in universe can be aggregated according to decision attribute after the sorting, that is, rule objects with the same decision attribute can be adjacent; then, it is easy for searching and deleting redundancy rules. Thereafter, all the rule objects can be “distributed” and “collected” by condition attributes; after that, all the objects can be “distributed” and “collected” by decision attributes to sort the whole universe by decision equivalence class and sort decision equivalence class by conditional equivalence class.To this end,RadSortU∗,RED∪D is called in step 32 to sort rule objects in current universe U∗ by RED+D (which is not by D+P as mentioned in [29]). That is, when sorting by RED+D, for any ai∈RED+D, if columns 0 to m − 2 from RED+D are condition attributes after reduction and column m − 1 is a decision attribute, then i can take values from 0 to m − 1 in ascending order. As RadSort will perform base sort by condition attributes firstly, followed by the decision attribute, rule objects with the same decision value will be gathered in groups; then, it is easy to get decision equivalence class. Therefore, it is easy to determine inclusion relationship among rule instances.The importance ofai will be evaluated by MP∗ and attribute with smaller MP∗ will give preference to change from “!” to original value. Similarly, when sorting rule objects by RED, it is reasonable to perform the sort later for those attributes with smaller MP∗. As a result, after sorting universe, attributes of rule objects with original value will be found in the top column (top column attribute with stronger distinguishability). Then, it is convenient to compare, search, and locate multiple redundancy rule objects, among which exist inclusion relationships.After sorting the whole universe byRED∪D with RadSortU∗,RED∪D, rule objects will be aggregated by decision equivalence class and condition equivalence class. In step 33, RedRulU∗,RED∪D is called to get redundancy rules set U− from U∗. At last, in step 34, the difference between rule objects set U∗ and redundancy rules set U− is nonredundancy rules set. After deleting “∗” in this nonredundancy rules set, a rule set DSR is finally achieved after reduction.


## 8.4. Analysis of Model Time Complexity

Step 1 is the attribute reduction model in [29]. The time complexity of the model is maxOCU,OC2U/C. The other steps, that is, steps 2–35, are composed of attribute value reduction model.Thereinto, time complexity of step 2 isOREDU′. Time complexity of steps 3–5 is ORED×ORED−1U″+ORED−1U″=OREDRED−1U″=ORED2U″. The time complexity of ConDup is mainly decided by steps 3–30. Generally, D is 1 or far less than P. So, the time complexity is OPU+ODU=maxOPU,ODU=OPU. Time complexity of steps 7–11 is mainly decided by steps 8 and 9, so time complexity of steps 7–11 is ORED×ORED−1U″+ORED−1U″=OREDRED−1U″=ORED2U″. Time complexity of steps 12–29 is mainly decided by steps 22–27, so time complexity of steps 12–29 is OU″×OPU″+OU″×OPxiP+OU+xi×OPU″+OPxiP=OPU″2. Because P is the attribute set of keeping original value of object and maxP = RED, so time complexity of steps 12–29 is OPU″2=OREDU″2. Time complexity of step 30 is OREDU″. Time complexity of step 31 is OREDU″. And time complexity of steps 32–34 is OREDU∗+OREDU∗=OREDU∗.Given the above analysis, time complexity of steps 2–35 ismaxOREDU′, ORED2U″, and OREDU″2.AsU′ is U/C and U″ is U′/RED, U′=U/C and U″=U′/RED=U/C/RED. That is, time complexity of the rule extraction model is maxOCU, OC2U/C, OREDU′, ORED2U″, OREDU″2 = maxOCU, OC2U/C, OREDU″2 = maxOCU, OC2U/C, OREDU/C/RED2.


## 9. Simulation Example Analysis

Let decision systemS=U,RED∪D, which is the reduction result after performing steps 1-2, where U=x1,x2,…,x27, RED=a,b,c,d, and D=E. Illustrated below with demo in Figure 1(a) (rule objects in the table is processed by “ordering whole universe U by D+RED” and “the full universe extraction”) is the detail on rule extraction procedure.Figure 1
Simulation example analysis. (a) The reduction result after performing steps 1-2. (b) The result after performing steps 3–8. (c) The marked system after performing steps 9-10. (d) The marked system after performing steps 7–11 for all attributes in RED. (e) The marked system after performing steps 12–29. (f) The marked system after performing steps 30–32. (g) The rule set after deleting redundant rules.Firstly,MP∗ for each ai∈RED is achieved by completing steps 3–5. The result is as follows: MRED−a∗ = 151 + 26 + 21 ∗ 2 = 219, MRED−b∗ = 152 + 26 + 21 ∗ 2 = 220, MRED−c∗ = 149 + 24 + 21 + 19 = 213, and MRED−d∗ = 146 + 25 + 21 + 20 = 212. Thereafter, in step 6, the order of attributes in Array (in descending order according to attribute importance) is d⟶c⟶a⟶b. Perform steps 7–11 for any ai∈RED. In step 8, RadSortU″,RED−a∪D is called to sort universe by D+P. When P=RED−a, results are specified in Figure 1(b).In step 9,ConDupU″,RED−a∪D is called to get conflict object set U+ and duplicate object set U∗. Then, get U+=x1,x10,x18 ∪ x3,x12,x20 ∪ x4,x13,x21 ∪ x5,x14,x24 ∪ x6,x15,x25 ∪ x7,x16,x26 and U+ = x2,x11,x19 ∪ x8,x17,x27. After marking the value column of a in step 10, a marked system is specified in Figure 1(c).In a similar way, steps 7–11 are performed for other attributes inRED to get marked results, respectively, specified in Figure 1(d).Steps 12–29 are called to evaluate rule objects. LetP=aArray0=d and faArray!f=fdx9 be restored to original value “2,” then P!=a,b,c and Array!=c,a,b. In step 22, according to the value of x9, RadSortU″,P∪D is called to sort unmarked system S″ by D+P. With reference to Figure 1(a), the conflict set of x1 is U+x9≠∅. Then, steps 23–27 are performed to restore the value of attribute c for x9 to 3 and to update P=c,d and P!=a,b. According to the value of x9, RadSortU″,P∪D is called to sort the unmarked system S″ by D+P. The sorted result is x3,x1,x6,x4,x5,x2. With reference to Figure 1(a), conflict set U+x9=x23 of x9 is achieved. Repeat execution on steps 23–27, a of x9 is restored to original value “2,” P=c,d,a, P!=b, and Array!=b. At that time, according to the value of x9, conflict set U+x9=∅. At the completion of loop execution on steps 23–27, the remaining “!” of xi is restored to “∗.”Similarly, rule objectsx22 and x23 are processed by sequence. The two objects can make decision in the original decision system according to current value, so the remaining “!” of x22 and x23 is restored to “∗.”Get marked systemS∗=U″,RED∪D specified in Figure 1(e). After steps 30-31, perform step 32 to order U∗ by RED+D and get marked system S∗ specified in Figure 1(f). In Figure 1(f), rule objects with strikethrough are duplicate objects. Then, a rule set specified in Figure 1(g) is achieved after deleting redundant rules in steps 32–34.Thereafter, for all rules, “∗” in each rule are deleted and a reduced rule set DSR = c1⟶E3; d1⟶E3; c1d2⟶E2; c2d2⟶E1; c3d1⟶E0; c3d2⟶E1; a2b2c2⟶E3; a3b2c2⟶E3 is achieved.


## 10. Experiment Analysis

Dataset “Iris Plants Database” fromUCI database [31] is used to compare rule extraction methods. Method A (proposed in this paper), method B (proposed in [22]), and method C (proposed in [23]) are compared on accuracy and effectiveness. There are 150 instances in Iris Plants Database, including 4 condition attributes “sepal length,” “sepal width,” “petal length,” and “petal width” and one decision attribute “class.” All the instances in the dataset are categorized into 3 decision classes. Because all the condition attribute data are continuous attribute data, the “discretization” method in ROSE [32] is used to discrete them as Rough Set has limited processing capacity on continuous data.Experimental comparison results of three methods are given in Tables2–4 and Figure 2. All of the instances are separated into two parts: one is for training set and another is for testing set randomly. One part is treated as the training set of random objects and it is used as learning samples. The other part is treated as the testing set which is the difference set of whole dataset and training set.Table 2
Groups.
Groups
Training set
Testing set
(count of instances)
(count of instances)
Group 1
80
70
Group 2
100
50
Group 3
120
30Table 3
Test results of method A.
Groups
Method A
Count of rules
Average length of rules
Average accuracy (%)
Group 1
6.5
2.50
94.5
Group 2
7.2
2.00
96.3
Group 3
8.4
1.88
98.5Table 4
Test results of method B and method C.
Groups
Method B
Method C
Count of rules
Average length of rules
Average accuracy (%)
Count of rules
Average length of rules
Average accuracy (%)
Group 1
7.1
2.57
93.1
7.5
3.2
92.3
Group 2
8.0
2.12
96.5
8.2
2.85
93.6
Group 3
10.1
1.90
98.0
10.5
2.32
93.8Figure 2
Experiment analysis.
(a)
(b)
(c)
(d)
(e)
(f)Testing of three groups is performed on the set, including(1)
Count of instances in training set/count of instances in testing set = 80/70(2)
Count of instances in training set/count of instances in testing set = 100/50(3)
Count of instances in training set/count of instances in testing set = 120/30Count of rules, average length of rules, and average accuracy of all the rules by each method are calculated in each testing, where average accuracy is∑i=1i=rule set deducedaccuracy ofrulei/rule set deduced. At the same time, to avoid randomness of a single experiment, it is executed 10 times for each group experiences and then the average value is obtained.The comparison results are shown in Tables2–4 and Figure 2: average accuracy of methods A and B in three-group testing is almost the same and average accuracy from two-group testing result is a bit higher by method A. Moreover, count of rules and average length of rules from method A are less than of methods B and C. With the practice instance increasing, count of rules getting from method A is not significantly increased.Considering run time, “Geriatric Care Medical Dataset” and other 3UCI datasets are used as testing datasets in Table 5. The “Geriatric Care Medical Dataset” is from the Canadian Study of Health and Aging. Detailed description of the dataset is available in [33]. The dataset has 8,547 instances, in which 5,089 are female and the rest are male. And, the dataset has 44 attributes, such as chest, diabetes, and dental. Its class or decision attribute is a binary value indicating whether an individual instance has died during follow-up.Table 5
Comparison of run time.
Testing dataset
Run time (S)
Name
Count of instances
Count of attributes
Method A
Method B
Method C
Method D
Wine quality
4,898
11
0.805
0.947
1.135
0.933
Mushroom
8,124
22
1.246
1.562
1.921
1.601
Letter recognition
20,000
16
2.537
2.871
3.906
3.281
Geriatric care medical
8,547
44
3.201
4.251
5.163
4.592LEM2 algorithm (Learning from Examples Module, version (2) [34]) is a rule extraction algorithm based on Rough Set. Since the LEM2 algorithm does not change the content and structure of the original system, and the extracted rules are not affected by the default values, and it has become one of the most commonly used rule extraction algorithms in recent years. Method D (LEM2 algorithm) and other three methods are compared on time.Experimental comparison results of four methods are given in Table5. The blind selection of attribute-value pairs and the multiple traversal of multiple cycles leads to the inefficiency of LEM2 algorithm. From the analysis in section “Analysis of model time complexity”, time performance of method A is obviously better than other three comparison methods. And the experimental results also show that the proposed method A is better than other methods in terms of running time.


## 11. Challenges

The modelDecDep_Rel calls algorithm RedSet, which can extract the first element of all equivalence classes in the universe to complete extraction and get U/P. And before calling algorithms ConDup and RedRul, the model DecDep_Rul calls algorithm RedSort or algorithm RedSet. These two algorithms can effectively complete the extraction of the universe.Therefore, the modelDecDep_Rul is more suitable for processing datasets that contain more duplicate data and redundant data, while it is not well suitable for processing datasets that contain very few duplicate object instances or redundant data.And, we also find the rule extraction model itself cannot work well in larger than or equal toPB dataset scales, because it takes too long to get rules. We believe that in combination with parallel processing, the model DecDep_Rul could better handle PB dataset scales. This is also what we will study further in the future.


## 12. Conclusion

In this paper, based on formalized definitions “Attribute Value Reduction” and “Value-Core Attribute,” the algorithmConDup for conflict object set and duplicate object set and the algorithm RedRul for redundant rule object set are proposed. Combined with algorithms in [29] and related theorems on attribute value reduction, the rule extraction model based on decision dependency degree DecDep_Rul is given. As the model does not generate matrix during reduction and uses object equivalent class to get conflict and duplicate object set, its time-space complexity is effectively controlled. The analysis results of simulation example and testing sets show that the new model can reduce redundant data more accurately and effectively while keeping the system classification ability unchanged. In conclusion, the new model can extract concise and key information and is effective and fast.



---

*Source: 5850410-2019-11-29.xml*