# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 3 Heuristic Attribute Reduction for Generalized Decision Preservation
### Heuristic Attribute Reduction Algorithms for Generalized Decision Preservation  
Usually, there are two attribute significance measures in heuristic attribute reduction; namely, the inner significance measure and the outer significance measure. The inner significance of an attribute is usually used for designing a backward greedy algorithm, while the outer significance of an attribute is usually used for designing a forward greedy algorithm. Based on the similarity degree (as proposed in the last subsection), we define the inner significance measure for generalized decision preservation, as follows:  
**Definition 11**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), \(Q\subseteq C\) and \(a\in Q\), the inner significance measure for generalized decision preservation is defined as_  
\[Sig^{inner}(a,Q,C)=Sim(Q,C)-Sim(Q-\{a\},C). \tag{11}\]  
**Theorem 4**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), for \(Q\subseteq C\), if \(\exists a\in Q\) such that \(Sig^{inner}(a,Q,C)>0\), then \(a\in Core(Q)\)._  
Proof. : If \(Sig^{inner}(a,Q,C)>0\) (i.e., \(Sim(Q,C)>Sim(Q-\{a\},C)\)), then the attribute \(a\) is called an indispensable attribute for generalized decision preservation and belongs to \(Core(Q)\). This completes the proof. **Definition 12**. : _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\) and \(Q\subset C\), \(\forall a\in C-Q\) the outer significance measure for generalized decision preservation is defined as_  
\[Sig^{outer}(a,Q,C)=Sim(Q\cup\{a\},C)-Sim(Q,C). \tag{12}\]  
From Definition 12, we calculate the outer significance of \(a\)\((a\in C)\) by adding \(a\) into a subset \(Q\subset C\). By the outer significance of an attribute, we add an attribute with the maximal outer significance iteratively until the similarity degree between this attribute set and the original attribute set is 1. Based on this strategy, a forward greedy reduction algorithm for generalized decision preservation is proposed in Algorithm 2. ```
0: A decision system \(DS=(U,C\cup D,V_{a},I_{a})\);
0: An attribute reduct \(Q\). 1: Let \(Core=\emptyset\), and calculate \(\delta_{C}(x_{i})\) for all \(x_{i}\in U\);
2: Put \(a_{i}\) into \(Core\) where \(Sim(C-\{a_{i}\},C)<1\), \(i\in\{1,2,\ldots,|C|\}\);
3: Let \(Q=Core\);
4:while\(Sim(Q,C)\
eq 1\)do
5:\(Q=Q\cup\{a\}\), where \(Sig^{outer}(a^{{}^{\prime}},Q,C)=max\{Sig^{outer}(a_{j},Q,C),a_{j}\in C-Q\}\);
6:endwhile
7:for\(k=1\)to\(|Q|\)do // remove redundant attributes
8:if\(Sig^{inner}(a_{k},Q,C)=0\)then\(Q=Q-\{a_{k}\}\);
9:endif
10:endfor
11:return\(Q\). ```  
**Algorithm 2** A forward greedy reduction algorithm for generalized decision preservation (FGRAG)  
Using Algorithm 2, we can calculate a reduct of a decision system based on an add-deleting research strategy. Algorithm 2 contains the main steps, as follows: Step 1 (Lines 1-3) is to calculate the generalized decision for each object and obtain \(Core(C)\) by deleting dispensable attributes from a condition attribute set, where the time complexity is \(O(mn)+O(m^{2}n)\), where \(m\) and \(n\) present the numbers of condition attributes and the universe, respectively. We iteratively add an attribute withthe maximal outer significance into \(Q\) until this attribute reduction satisfies the stopping criterion \(Sim(Q,C)=1\) in Step 2 (Lines 4-6), whose time complexity is \(O(m^{3}n)\). Step 3 (Lines 7-10) is to remove dispensable attributes and obtain an attribute reduct, with corresponding time complexity of \(O(m^{2}n)\). If dispensable attributes are not removed, we may get the superset of an attribute reduct, in some cases. From the discussion above, the time complexity of Algorithm 2 is \(O(m^{3}n)\). **Example 2**. : _If \(DS=(U,C\cup D,V_{a},I_{a})\) is the decision system presented in Table 1, \(U=\{x_{1},x_{2},...,x_{8}\}\), \(C=\{a_{1},a_{2},a_{3},a_{4}\}\), and \(D=\{d\}\).