# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 3 Heuristic Attribute Reduction for Generalized Decision Preservation
### The Similarity Degree for Generalized Decision Preservation  
In studies of heuristic attribute reduction, the attribute similarity measure (heuristic information, dependency degree) is an important factor. Recently, to obtain the various reducts, different similarity measures have been proposed in rough set theory, such as the positive dependency degree [1], information entropy [35], conditional entropy [40], and maximum decision entropy [41]. However, there have been few studies on the similarity measure for generalized decision preservation. Thus, to evaluate the similarity of different attributes for generalized decision preservation, we define the similarity degree for generalized decision preservation as follows:  
**Definition 8**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), \(\forall Q\subseteq C\), if \(E_{Q}(x_{i})\in U/Q\), \(E_{C}(x_{i})\in U/C\), the similarity degree for generalized decision preservation is defined as_  
\[Sim(Q,C)= \begin{cases}\frac{|\bigcup_{i=1}^{|U|}(E_{Q}(x_{i}) \cap E_{C}(x_{i}))|}{|U|},&\delta_{Q}(x_{i})=\delta_{C}(x_{i}).\\ 0,&\text{otherwise}.\end{cases}  \tag{8}\]  
To express the monotonic theorem of the similarity degree for generalized decision preservation, we need the following theorem. **Theorem 1**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), if, for all \(x_{i}\in U\), \(P\subseteq Q\subseteq C\), \(E_{P}(x_{i})\), \(E_{Q}(x_{i})\), and \(E_{C}(x_{i})\) are the equivalence classes that contain the object \(x_{i}\) with respect to \(P\), \(Q\), and \(C\), then we have_  
\[\delta_{C}(x_{i})\subseteq\delta_{Q}(x_{i})\subseteq\delta_{P}(x_{i}). \tag{9}\]  
Proof. : From the basic properties of rough set theory, for \(x_{i}\in U\), \(\forall Q\subseteq C\), it is easy to get \(E_{C}(x_{i})\subseteq E_{Q}(x_{i})\). Suppose that \(\delta_{C}(x_{i})\supset\delta_{Q}(x_{i})\). Then, there exists \(x_{j}\in U\) such that \(d(x_{j})\in\delta_{C}(x_{i})\) but \(d(x_{j})\
otin\delta_{Q}(x_{i})\). Then, \(x_{j}\in E_{C}(x_{i})\) but \(x_{j}\
otin E_{Q}(x_{i})\). Therefore, we have \(E_{C}(x_{i})\
ot\subseteq E_{Q}(x_{i})\). This is contrary to \(E_{C}(x_{i})\subseteq E_{Q}(x_{i})\). Then, \(\delta_{C}(x_{i})\subseteq\delta_{Q}(x_{i})\). Similarly, we have \(\delta_{Q}(x_{i})\subseteq\delta_{P}(x_{i})\). From the discussion above, \(\delta_{C}(x_{i})\subseteq\delta_{Q}(x_{i})\subseteq\delta_{P}(x_{i})\) holds. This completes the proof. Definition 8 provides a similarity measure between different condition attribute sets for generalized decision preservation. For all \(Q\subseteq C\), we have \(0\leq Sim(Q,C)\leq 1\). The monotonicity of the similarity degree for generalized decision preservation is presented as follows:  
**Theorem 2**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), \(\forall P\subseteq Q\subseteq C\), we have_  
\[Sim(P,C)\leq Sim(Q,C). \tag{10}\]  
Proof. : For all \(P\subseteq Q\subseteq C\), \(x_{i}\in U\), if \(E_{P}(x_{i})\in U/P\), \(E_{Q}(x_{i})\in U/Q\) and \(E_{C}(x_{i})\in U/C\), then \(E_{C}(x_{i})\subseteq E_{Q}(x_{i})\subseteq E_{P}(x_{i})\). If \(x_{im}\in E_{P}(x_{i})\), then we have \(E_{P}(x_{i})=E_{Q}(x_{i1})\cup E_{Q}(x_{i2})\cup...\cup E_{Q}(x_{it})=\bigcup _{m=1}^{t}E_{Q}(x_{im})\), where \(1\leq t\leq|E_{P}(x_{i})|\). If \(\delta_{P}(x_{i})\
eq\delta_{C}(x_{i})\), then \(E_{P}(x_{i})\cap E_{C}(x_{i})=0\). For \(x_{im}\in E_{P}(x_{i})\), if \(\delta_{Q}(x_{im})\
eq\delta_{C}(x_{im})\), then \(E_{Q}(x_{im})\cap E_{C}(x_{im})=0\). Suppose that \((E_{P}(x_{i})\cap E_{C}(x_{i}))\supset\bigcup_{m=1}^{t}(E_{Q}(x_{im})\cap E_{ C}(x_{im}))\). There must exist \(x_{is}\) such that \(x_{is}\in(E_{P}(x_{i})\cap E_{C}(x_{i}))\) but \(x_{is}\
ot\in\bigcup_{m=1}^{t}(E_{Q}(x_{im})\cap E_{C}(x_{im}))\). Then, \(\delta_{P}(x_{is})=\delta_{C}(x_{is})\), but \(\delta_{Q}(x_{is})\
eq\delta_{C}(x_{is})\). From Theorem 1, for all \(x_{is}\in U\), we have \(\delta_{C}(x_{is})\subseteq\delta_{Q}(x_{is})\subseteq\delta_{P}(x_{is})\). As \(\delta_{P}(x_{is})=\delta_{C}(x_{is})\), then \(\delta_{Q}(x_{is})=\delta_{C}(x_{is})\).