# 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
By Algorithm 2, a reduct of \(DS\) can be calculated as follows:_  
**1:**_CORE \(=\emptyset\), \(\delta_{C}(x_{1})=\delta_{C}(x_{2})=\delta_{C}(x_{3})=\{1,2\}\), \(\delta_{C}(x_{4})=\delta_{C}(x_{5})=\{1,3\}\), and \(\delta_{C}(x_{6})=\delta_{C}(x_{7})=\delta_{C}(x_{8})=\{1,2\}\)._ **2-3:** _As \(Sim(C-\{a_{1}\},C)=1\), \(Sim(C-\{a_{2}\},C)=1\), \(Sim(C-\{a_{4}\},C)=1\), and \(Sim(C-\{a_{3}\},C)=3/8<1\). Therefore, \(Q=Core(C)=\{a_{3}\}\)._ **4-6:** _\(Sig^{outer}(a_{1},Q,C)=5/8\), \(Sig^{outer}(a_{2},Q,C)=5/8\), and \(Sig^{outer}(a_{4},Q,C)=0\). We put \(a_{1}\) into \(Q\) and get \(Q=\{a_{1},a_{3}\}\). By Definition 8, we can obtain \(Sim(Q,C)=1\)._ **7-10:** _As \(Sig^{inner}(a_{1},Q,C)>0\) and \(Sig^{inner}(a_{3},Q,C)>0\). there exists no dispensable attributes in \(Q\)._ **11:** _Return the reduct \(Q=\{a_{1},a_{3}\}\) of the \(DS\)._  
Unlike the add-deleting research strategy used in Algorithm 2, we adopt a deleting strategy to find a reduct. Attribute reduction using a deleting strategy begins with the original condition attribute set. We construct an ascending sequence of condition attributes by the similarity degree for generalized decision preservation. If the inner significance measure of an attribute is 0, we remove this attribute from the condition attribute set. Based on this strategy, we develop a backward greedy reduction algorithm for generalized decision preservation, shown in Algorithm 3. ```
0: A decision system \(DS=(U,C\cup D,V_{a},f_{a})\);
0: An attribute reduct \(Q\). 1: Calculate \(\delta_{C}(x_{i})\) for all \(x_{i}\in U\);
2: Calculate \(Sim(\{a_{i}\},C)\) for all \(a_{i}\in C\);
3: Construct an ascending sequence \(\{a_{1}^{{}^{\prime}},a_{2}^{{}^{\prime}},\ldots,a_{|C|}^{{}^{\prime}}\}\) by \(Sim(\{a_{i}\},C)\);
4: Let \(Q=C\);
5:for\(j=1\)to\(|Q|\)do
6:if\(Sig^{inner}(a_{j}^{{}^{\prime}},Q,C)=0\)then
7:\(Q=Q-\{a_{j}^{{}^{\prime}}\}\)
8:endif
9:endfor
10:return\(Q\). ```  
**Algorithm 3** A backward greedy reduction algorithm for generalized decision preservation (BGRAG)  
Assuming that \(m=|C|\) and \(n=|U|\), the generalized decision of each object is calculated in Step 1 (Line 1), and the time complexity is \(O(mn)\). Step 2 (Lines 2-3) is to construct an ascending sequence of condition attributes by similarity degree for generalized decision preservation, with time complexity of \(O(m^{2}n)+O(m^{2})\). Step 3 (Lines 4-9) is the key step in Algorithm 3, where dispensable attributes will be removed. The time complexity of Step 3 is \(O(m^{2}n)\). Due to using a deleting research strategy, we need not delete redundant attributes. Therefore, the time complexity of Algorithm 3 is \(O(m^{2}n)\). **Example 3**. : _Table 1 is the decision system, where \(DS=(U,C\cup D,V_{a},I_{a})\), \(U=\{x_{1},x_{2},...,x_{8}\}\), \(C=\{a_{1},a_{2},a_{3},a_{4}\}\), and \(D=\{d\}\). By Algorithm 3, a reduct of \(DS\) can be calculated as follows:_  
_1:_\(\delta_{C}(x_{1})=\delta_{C}(x_{2})=\delta_{C}(x_{3})=\{1,2\}\), \(\delta_{C}(x_{4})=\delta_{C}(x_{5})=\{1,3\}\), and \(\delta_{C}(x_{6})=\delta_{C}(x_{7})=\delta_{C}(x_{8})=\{1,2\}\)._ **2:** \(Sim(\{a_{1}\},C)=3/8\), \(Sim(\{a_{2}\},C)=3/8\), \(Sim(\{a_{3}\},C)=3/8\), and \(Sim(\{a_{4}\},C)=0\)._ **3-4:** _According to the value of \(Sim(\{a_{i}\},C)\), we have an ascending sequence: \(Sim(\{a_{4}\},C)=0\), \(Sim(\{a_{1}\},C)=3/8\), \(Sim(\{a_{2}\},C)=3/8\), and \(Sim(\{a_{3}\},C)=3/8\); and \(Q=C=\{a_{1},a_{2},a_{3},a_{4}\}\)._ **5-9:** _\(Sig^{inner}(a_{4},Q,C)=0\), so we delete \(a_{4}\) from \(Q\). Then, we have \(Q=\{a_{1},a_{2},a_{3}\}\)._ \(Sig^{inner}(a_{1},Q,C)=0\)so we delete \(a_{1}\) from \(Q\). Hence, we have \(Q=\{a_{2},a_{3}\}\). As \(Sig^{inner}(a_{2},Q,C)>0\) and \(Sig^{inner}(a_{3},Q,C)>0\), there are no dispensable attributes in \(Q\). **10:** Return the reduct \(Q=\{a_{2},a_{3}\}\) of \(DS\)._  
Attribute reduction for generalized decision preservation is an important attribute reduction model in RST. By using the algorithms FGRAG and BGRAG proposed in this section, the feature subsets of each decision rule can be obtained quickly.