# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 3 Heuristic Attribute Reduction for Generalized Decision Preservation
### The Similarity Degree for Generalized Decision Preservation
This is contrary to \(\delta_{Q}(x_{is})\
eq\delta_{C}(x_{is})\). Thus, \((E_{P}(x_{i})\cap E_{C}(x_{i}))\subseteq\bigcup_{m=1}^{t}(E_{Q}(x_{im})\cap E _{C}(x_{i}))\) holds. It is obvious that \(|(E_{P}(x_{i})\cap E_{C}(x_{i}))|\leq|\bigcup_{m=1}^{t}(E_{Q}(x_{im})\cap E_{ C}(x_{im}))|\). Hence, \(|\bigcup_{i=1}^{|U|}(E_{P}(x_{i})\cap E_{C}(x_{i}))|\leq|\bigcup_{i=1}^{|U|} \bigcup_{m=1}^{t}(E_{Q}(x_{im})\cap E_{C}(x_{im}))|\); namely, \(|\bigcup_{i=1}^{|U|}(E_{P}(x_{i})\cap E_{C}(x_{i}))|\leq|\bigcup_{i=1}^{|U|}( E_{Q}(x_{i})\cap E_{C}(x_{i}))|\). Thus, we have \(\frac{|\bigcup_{i=1}^{|U|}(E_{P}(x_{i})\cap E_{C}(x_{i}))|}{|U|}\leq\frac{| \bigcup_{i=1}^{|U|}(E_{Q}(x_{i})\cap E_{C}(x_{i}))|}{|U|}\). Therefore, for all \(P\subseteq Q\subseteq C\), \(Sim(P,C)\leq Sim(Q,C)\). This completes the proof. An example is given to explain Theorem 2, as follows:  
**Example 1**. : _Consider the decision system shown in Table 1, \(P=\{a_{1},a_{2}\}\), we have_  
\(E_{P}(x_{1})=E_{P}(x_{2})=E_{P}(x_{3})=E_{P}(x_{4})=E_{P}(x_{5})=\{x_{1},x_{2},x_{3},x_{4},x_{5}\}\)_,_  
\(E_{P}(x_{6})=E_{P}(x_{7})=E_{P}(x_{8})=\{x_{6},x_{7},x_{8}\}\)_._  
_As \(U/D=\{\{x_{1},x_{6},x_{8}\},\{x_{2},x_{3},x_{4},x_{7}\},\{x_{5}\}\}\),_  
\(\delta_{P}(x_{1})=\delta_{P}(x_{2})=\delta_{P}(x_{3})=\delta_{P}(x_{4})=\delta_ {P}(x_{5})=\{1,2,3\}\)_,_  
\(\delta_{P}(x_{6})=\delta_{P}(x_{7})=\delta_{P}(x_{8})=\{1,2\}\)__  
_For \(C=\{a_{1},a_{2},a_{3},a_{4}\}\), we have_  
\(E_{C}(x_{1})=E_{C}(x_{2})=E_{C}(x_{3})=\{x_{1},x_{2},x_{3}\}\)_,_ \(E_{C}(x_{4})=E_{C}(x_{5})=\{x_{4},x_{5}\}\)_,_  
\(E_{C}(x_{6})=E_{C}(x_{7})=E_{C}(x_{8})=\{x_{6},x_{7},x_{8}\}\)_._  
_As \(U/D=\{\{x_{1},x_{6},x_{8}\},\{x_{2},x_{3},x_{4},x_{7}\},\{x_{5}\}\}\), we have_  
\(\delta_{C}(x_{1})=\delta_{C}(x_{2})=\delta_{C}(x_{3})=\delta_{C}(x_{6})=\delta_ {C}(x_{7})=\delta_{C}(x_{8})=\{1,2\}\)_,_  
\(\delta_{C}(x_{4})=\delta_{C}(x_{5})=\{1,  
**Definition 9**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), \(Q\subseteq C\) is a reduct for generalized decision preservation in \(DS\) if and only if_  
1. \(Sim(Q,C)=1\)_;_
2. \(\forall P\subset Q\)_,_ \(Sim(P,Q)\
eq 1\)_._  
The first condition means that the attribute subset \(Q\) has the same similarity degree as the original attribute set \(C\), and the second condition means that there is no dispensable or redundant attribute in \(Q\). It should be considered that dispensable or indispensable attributes are suited to the classification properties in a decision system. For example, a dispensable attribute for positive preservation may be indispensable for conditional entropy preservation. Considering monotonicity of the similarity degree for generalized decision preservation, we also have the following definition:  
**Definition 10**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), \(Q\subseteq C\) is a reduct for generalized decision preservation in \(DS\) if and only if_  
1. \(Sim(Q,C)=1\)_;_
2. \(\forall P\subset Q\)_,_ \(Sim(P,C)<SIM(Q,C)\)_._  
For all \(Q\subseteq C\), if \(\exists a\in Q\) such that \(Sim(Q,C)=Sim(Q-\{a\},C)\), then \(a\) is called a dispensable attribute for generalized decision preservation with respect to \(Q\); otherwise, \(a\) is an indispensable attribute for generalized decision preservation with respect to \(Q\). The set of all indispensable attributes regarding \(Q\) is called the core of \(Q\), denoted by \(Core(Q)\). In Table 1, if \(C=\{a_{1},a_{2},a_{3},a_{4}\}\), as \(Sim(C,C)=1>Sim(C-\{a_{3}\},C)=3/8\), then we have that \(a_{3}\) is an attribute in \(Core(C)\). \(Core(Q)\) can be calculated by the intersection of all reducts with respect to \(Q\). For Table 1, \(Core(C)=\{a_{1},a_{3}\}\cap\{a_{2},a_{3}\}=\{a_{3}\}\). In some cases, \(Core(Q)\) may be an empty set. **Theorem 3**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), for \(Q\subseteq C\), we have the following:_  
1. _If_ \(Q\) _is a reduct for generalized decision preservation in_ \(DS\)_, then_ \(Q\) _can leave the positive region unchanged in a_ \(DS\)_; and_
2.