Information Technology Journal

Year: 2014 | Volume: 13 | Issue: 6 | Page No.: 1140-1146
DOI: 10.3923/itj.2014.1140.1146

Acquisition and Reduction of Incomplete Decision Information System Based on Similarity and Dissimilarity Knowledge Granules

Weiyan Xu, Min Wei, Ming Zhang and Xibei Yang

Abstract: In the incomplete decision information systems, based on similarity relation, the concept of similarity and dissimilarity knowledge is firstly proposed. By the basic knowledge granule, two kinds of rough set model are defined and their properties are discussed. In these rough set models, based on similarity and dissimilarity knowledge, an approach is presented to acquire the positive and negative decision rules, respectively. The certainty factor is introduced to measure their certainty degree. Finally, to simplify these decision rules, this study introduces the heuristic algorithm of the attribute reduction based on the significant attributes and analyzes an illustrative example to prove its effectiveness.

Keywords: heuristic algorithm, Similarity relation, knowledge acquisition, decision rule and attribute reduction

INTRODUCTION

Rough set theory presented by Pawlak (1982) and Pawlak and Skowron (2007) is an effective mathematical method to analyze and deal with the imprecise, inconsistent and vague information. With over 30 year’s development, it has been widely used in the fields such as pattern recognition, machine learning, decision analysis, knowledge acquisition and data mining (Qian et al., 2010; Hu et al., 2007; Sen and Pal, 2009; Xu et al., 2012a; Liang et al., 2012; Gu et al., 2011) and so on.

The classical rough set theory is based on the complete information systems and there are no unknown values. However, the Incomplete Information Systems (IIS) (Yang et al., 2009a; Grzymala-Busse, 2004; Stefanowski and Tsoukias, 2001) can be found everywhere for a lot of unpredictable reasons. Therefore, mining rules from incomplete information systems is one of the important directions for the development of rough set. Most of decision rules are positive property (Pawlak, 1982; Xu et al., 2012b; Gu et al., 2011; Yang et al., 2009b; Grzymala-Busse, 2004; Stefanowski and Tsoukias, 2001), but we also need some form of negative rules, it means that if an object doesn’t satisfy the certain attribute-value pairs in the condition part, then we can exclude such object from the decision class, which was firstly proposed and successfully applied in the medical diagnosis expert system by Tsumoto (2000). Yao (2010, 2011) solved the acquisition of three-way decisions rule, such as the positive, negative and obtained decision rules based on the model of probabilistic rough sets, but it’s a pity that he didn’t pay attention to the reduction. To acquire the negative decision rule in IIS, Yang et al. (2009a) put forward the difference relationship based on rough set and Xu et al. (2012a) proposed the variable precision rough set model based on negative support set of descriptor, but their attribute reduction algorithm based on discernibility matrix, was not conducive to automatic realization by computer.

In this study, the notion of similarity and dissimilarity knowledge granule based on similarity relation in incomplete decision information system, is introduced firstly. The lower and upper approximation sets based on similarity and dissimilarity knowledge granule, are constructed to acquire the positive and negative decision rules from the incomplete decision information system. Secondly, to obtain a simplified decision rule, the heuristic algorithm of the attribute reduction based on the significant attributes is proposed. The final results of example analysis show that this algorithm is feasible and practical.

INCOMPLETE DECISION INFORMATION SYSTEM

A Decision Information System (DIS) is defined as a 4-tuple DIS = <U, AT, V, f>, where U is a non-empty finite set of objects, AT = C∪D is a non-empty finite set of attributes, C denotes the set of condition attributes and D denotes the set of decision attributes and C∩D = ø. Each attribute α∈AT is associated with a set V_a of its values, V_a is called the domain of α and then V = V_C∪V_D. For any x∈U, f (x,α) is the value that x holds on α (α∈AT). If D = {d}, DIS = <U, C∪{d}, V, f> is a single attribute decision information system, otherwise it is called a multiple attribute decision information system. To simplify our discussion, we only discuss the single attribute decision information system.

An Incomplete Decision Information System (IDIS) is a decision information system IDIS = <U, C∪{d}, V, f>, where the condition-attribute values for some objects are unknown. In this study, we consider the unknown value of the condition attributes as missing (Grzymala-Busse, 2004), which is denoted by the special symbol “*”. For instance, if f (x, α) = ‘>*” (x∈ U, α∈AT), here we assume that “*” only may appear in the values of C, thus, V = V_C∪V_d.∪{*}.

DECISION RULES

In the rough set theory, the knowledge hidden in IDIS = <U, C∪{d}, V, f>, will be extracted by the form of decision rules. Through the investigation to the object x∈U, we can get the decision rule such as:

where, des([x]_C) is the condition part of the rule, it shows the description of object x under the condition-attribute set C, i.e., des ([x]_C) =∧ _c∈C(c, v_c) and v_c ≠ *; des ([x]_d) is the decision part of the rule, it shows the description of object x under the decision attribute d, i.e., des([x]_d) = ∨_i∈Vd(d, i), here i∈V_d is the label of the class. On the basic of des([x]_C)→des([x]_d), we can conclude that the object x belongs to some certain decision class, therefore, des ([x]_C)→des([x]_d) is called a positive decision rule.

For each positive decision rule r_x, the certainty factor Cer (r_x) is defined to measure it’s decision ability:

where, card (X) is the cardinal number of the set X, ||[x]_C|| is the set of those elements having the same description as x on the condition attribute set C, denoted as ||[x]_C|| = {y∈U: f (y, c) = f (x, c), ∀c∈C} and ||[x]_d|| is the set of those elements having the same description as x on the decision attribute d, it is recorded as ||[x]_d|| = {y∈U: f (y, d) = f (x, d)}.

If Cer (r_x) = 1, then, r_x is a definite positive decision rule; if 0<Cer (r_x)<1, r_x is an indefinite positive decision rule. The degree of certainty is measured by the value of Cer (r_x).

In addition to the above positive decision rule, we always need such decision rule called negative decision rule as, if an object’s condition attribute-value pairs don’t satisfy some certain condition in the condition part, then we can conclude that the object x is not belong to the certain decision class, in other words, we can exclude it from some decision class. The negative rule can be described as:

Accordingly, the general form of the negative decision can be expressed as:

where, des(¬[x]_C) is the condition part of the negative decision rule and shows the description of the object x under the condition-attribute set C, that is to say des (¬[x]_C) = ∧_c∈C¬(c, v_c) and v_c ≠ *; correspondingly des (¬[x]_d) is the decision part of the negative decision rule and shows the description of the object x under the decision attribute d, i.e., des¬ ([x]_d) = ∨_I∈Vd¬ (d, i), here I∈V_d is the label of the class. Similarly, for each negative decision rule, the certainty factor can be denoted by:

where, ||¬[x]_C|| is the set of those elements with the same description as x on the condition attribute set C, recorded as ||¬[x]_C|| = {y∈U: f (y, c) ≠ f (x, c), ∀c∈C} and ||¬[x]_d|| is the set of those elements having the same description as x on the decision attribute d, recorded as ||¬[x]_d|| = {y∈U: f (y, d) ≠ f (x, d)}. If Ncer (r_x) = 1, then, r_x is a definite negative decision rule; if 0<NCer (r_x)<1, then, r_x is an indefinite negative decision rule. The degree of certainty is measured by the value of Ncer (r_x).

RULE ACQUISITION

For a lot of unpredictable reasons in real word, the study is mostly in incomplete decision information system. Therefore, the study mainly discussed how to acquire the positive and negative decision rules in incomplete decision information system.

Similarity knowledge and positive rule
Definition 1: Let IDIS = <U, C∪{d},V, f>, for any A⊆C, S (A) is a similarity relation on the universe U, decided by the attribute subset A and define as:

Obviously, the binary relation S (A) is reflexivity and transitivity, but not necessarily symmetric. Let SIM_A (x) = {y∈U: (x, y)∈S (A)} be the set of those elements similar to x, regarded SIM_A (x) as the basic knowledge granule (i.e., similar knowledge granule), the lower and upper approximations of X can be constructed to acquire the positive decision rule.

Definition 2: Suppose IDIS = <U,C∪{d},V, f>, for any X⊆U, A⊆C, the lower and upper approximations of X with regard to A, can be defined with SIM_A (x) as the basic knowledge granule:

Based on the similar knowledge granule SIM_A (x), the ordered pair <, > is definded as the rough set of X with regard to A. Through the lower and upper approximation of X, the positive, boundary and negative region can be, respectively described as follows:

Theorem 1: Suppose IDIS = <U, C∪{d}, V, f>, U/d = {D₁, D₂,…,D_i} is the partition of U induced by decision attribute d, D_i = {x∈U: f (x, d) = i} and i is the label of the class. Then, for any x∈U, we have:

Proof 1: Since, SIM_A (x)⊆POS_DIM(D_i), for any x∈SIM_A (x), then SIM_A (x)≠ø and SIM_A (x)⊆D_i. By the definition of SIM_A (x), the elements whose description is same as x in X, have the same decision attribute-value i, i∈V_d. So, Cer (r_x) = 1 sets up, then, r_x is a definite positive decision rule.

Proof 2: The proof is similar to proof 1.

Dissimilarity knowledge and negative rule: Through the similarity knowledge induced by a similarity relation, we can obtain the positive decision rule, but can’t get the negative decision rule. Below is the acquisition of the negative rules.

Definition 3: Suppose IDIS = <U,C∪{d},V, f>, for any A⊆C, S (A) is a similarity relation on the universe U determined by the condition attribute subset A, DIM_A (x) is the set of those elements dissimilar to x and defined as:

To acquire the negative decision rules, the following discussion studies how to construct the lower and upper approximations of X, based on DIM_A (x) as the basic knowledge granule (that is the dissimilar knowledge granule).

Definition 4: Suppose IDIS = <U,C∪{d},V, f>, for any X⊆U, A⊆C, the lower and upper approximations of X with regard to A, can be definded with DIM_A (x) as the basic knowledge granule:

Based on the dissimilar knowledge granule DIM_A (x), the ordered pair (, is defined as the rough set of X with regard to A. Through the lower and upper approximations of X, the positive, boundary and negative region can be respectively described as follows:

Theorem 2: Let IDIS = <U, C∪{d}, V, f>, U/¬d = {¬D₁, ¬D₂,…,¬D_i} is the cover of U induced by the decision attribute d, ¬D_i = {x∈U: f (x,d) ≠ i} and i is the label of the class. Then, for any x∈U, we have:

Proof 1: Since, DIM_A (x)⊆POS_DIM (¬D_i), for any x∈DIM_A (x), then, DIM_A (x) ≠ ø and DIM_A (x)⊆¬D_i. By the definition of DIM_A (x), the elements whose description is different from x in X, all don’t take the decision-value i, i∈V_d. So, Ncer (r_x) = 1 sets up, then, r_x is a definite negative decision rule.

Proof 2: The proof is similar to proof 1.

REDUCTION

Reduction is also called attribute reduction or feature selection and it is the key issue to study the rough set theory [3-4,6,9]. Through the attribute reduction, the simplified decision rule can be obtained. In this section, the heuristic algorithm based on the importance is introduced to simplify the positive and negative decision rules.

Definition 5: Suppose IDIS = <U,C∪{d},V, f>, A⊆C, D = {D₁,D₂,…,D_r} is the partition of U induced by the decision attribute d, where D_i = {x∈U: f (x,d) = i} and ¬D_i = {x∈U: f (x,d)≠i}. we define:

How to obtain the distribution reduction based on similar and dissimilar knowledge granule, it is focused on how to look for all of the lower and upper approximation distribution reductions of the decision classes. The heuristic algorithm of the attribute reduction based on the significant attributes is introduced in the following discussion.

Suppose DIS = <U, C∪{d},V, f>, D = {D₁,D₂,…,D_r} is the partition of U induced by decision attribute d, where D_i = {x∈U: f (x,d) = i} and ¬D_i = {x∈U: f (x,d) ≠ i}. For any condition attribute α∈C , based on the similar knowledge granule and dissimilar knowledge granule, it’s dependence degrees on the lower and upper approximation of decision class D are, respectively expressed as follows:

Obviously, S_a (SIM,D), S^a (SIM,D), S_a (DIM,D) and S^a (DIM,D) are all greater than or equal to zero.

If S_a (SIM,D) = 0 (or S^a (SIM,D) = 0), after eliminating attribute α, we can conclude that the lower (or upper) approximation distribution of decision class D based on the similar knowledge granule doesn’t change.

If S_a (SIM,D)>0 (or S^a (SIM,D)>0), after eliminating attribute α, we can find that the lower (or upper) approximation distribution of decision class D based on the similar knowledge granule will be changed, then the attribute α can’t be reducted.

If S_a (DIM,D) = 0 (or S^a (DIM,D) = 0), after eliminating attribute α, we can conclude that the lower (or upper) approximation distribution of decision class D based on the dissimilar knowledge granule doesn’t change.

If S_a (DIM,D)>0 (or S^a (DIM,D)>0), after eliminating attribute α, we can find that the lower (or upper) approximation distribution of decision class D based on the dissimilar knowledge granule will be changed, then the attribute α can’t be reducted.

Based on the definition 5, to obtain the distribution reduction of similar and dissimilar knowledge, the key is finding out their lower and upper approximation distribution reduction. Below is a heuristic algorithm of the attribute reduction based on the significant attributes.

Algorithm 1: The lower/upper approximation distribution reduction about the similar knowledge.

Suppose IDIS = <U, C∪{d}, V, f>, C = {α₁, α₂,…,α_i} is the set of attributes, D = {D₁,D₂,…,D_r} is the partition of U induced by decision attribute d. The steps to obtain the lower approximation distribution reduction of C which is denoted by R, can be described as follows:

Note: If the judgment condition L_SIM (R) = L_SIM (C) in step 2 is replaced by U_SIM (R) = U_SIM (C) and the S_ai (SIM,D) is replaced by S^ai (SIM,D), then we can get R, where R is an upper approximation distribution reduction of condition attribute set C about the similar knowledge.

Algorithm 2: The lower/upper approximation distribution reduction about the dissimilar knowledge.

Suppose IDIS = <U,C∪{d}V,f>, C = {α₁, α₂,…,α_i} is the set of attributes, U/¬d = {¬D₁, ¬D₂,…, ¬D_i} is the cover of U induced by decision attribute d and ¬D_i = {x∈U: f (x,d) ≠ i}. The lower approximation distribution reduction of condition attribute set C, is denoted by R. The steps of acquiring Reduction R are as follows:

Note: If the judgment condition L_DIM (R) = L_DIM (C) in step 2 is replaced by U_DIM (R) = U_DIM (C) and S_ai (DIM,D) becomes S^ai (DIM,D), then we can get R, where R is an upper approximation distribution reduction of condition attribute set C about the dissimilar knowledge.

Example: Table 1 is an IDIS, compute all of the definite positive and negative decision rules.

By Table 1, we know that U = {x₁, x₂, x₃, x₄, x₅, x₆ ,x₇} is the domain of discourse, C = {a, b, c} is the set of condition attributes, d is the single decision attribute and V_a = V_b = V_c = V_d = {1, 2, 3}. By definition 1, we can draw the following sets:

By the single decision attribute d, U/d = {D₁, D₂ D₃} = {{x₁, x₇},{x₃, x₄},{ x₂, x₅, x₆}}

By definition 2,

According to the heuristic algorithm 1, we can consider {a, b} as a reduction of the condition-attribute set C through the program. Combining theorem 1, we can obtain the following definite positive decision rule:

By the Table 1, U/¬d = {¬D₁, ¬D₂, ¬D₃} = {{x₂,x₃, x₄, x₅, x₆}, {x₁ x₂, x₅,x₆,x₇}, {x₁, x₃, x₄, x₇}}, By definition 3, we can draw the following sets:

By definition 4, we have:

According to the heuristic algorithm of lower approximation distribution reduction, we can consider {a, c} as a reduction of the condition-attribute set C through the program. Further, we can obtain the following definite negative decision rule:

CONCLUSION

In this study, the notion of similarity and dissimilarity knowledge granule based on the similarity relation is firstly introduced in IDIS. The lower and upper approximation sets based on similarity and dissimilarity knowledge granule, are constructed to acquire the positive and negative decision rules. By the properties of the new rough set model, we discuss the acquisition of the positive and negative decision rules, respectively. Finally, to obtain a simplified decision rule, we further introduce the heuristic algorithm of the attribute reduction based on the significant attributes and an example shows its effectiveness and feasibility.

ACKNOWLEDGMENTS

This study is supported by the Natural Science Foundation of China (No. 61100116), Natural Science Foundation of Jiangsu Province of China (No. BK2011492), Natural Science Foundation of Jiangsu Higher Education Institutions of China (No. 11KJB520004).

REFERENCES