# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 2 Preliminaries
### Discernibility Matrix-Based Attribute Reduction for Generalized Decision Preservation  
In this section, we review the concept of generalized decision and attribute reduction for generalized decision preservation based on the discernibility matrix. In inconsistent information systems, objects with the same condition attribute values may have different decision values. The set of these decision values is called the generalized decision [12], which is defined as follows:  
**Definition 4**. : _[_12_]_ _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), for all \(x_{i},x_{j}\in U\), \(\forall Q\subseteq C\), \(E_{Q}(x_{i})\in U/Q\), the generalized decision for an object \(x_{i}\), with respect to \(Q\), is defined as_  
\[\delta_{Q}(x_{i})=\{f(x_{j},d)|x_{j}\in E_{Q}(x_{i})\}. \tag{5}\]  
For all \(x_{i}\in U\), it is easy to observe that \(1\leq|\delta_{Q}(x_{i})|\leq|U|\). For all \(x_{i}\in U\), if \(|\delta_{Q}(x_{i})|=1\), then an arbitrary object in a decision system has a unique decision value. Then, \(DS\) is a consistent decision system (or, we say that \(DS\) is consistent); otherwise, \(DS\) is inconsistent. In an inconsistent decision system, there exists at least one object with multiple decision values. A reduct can provide a minimal attribute subset which contains the same classification properties as the original condition attribute set. Attribute reduction for generalized decision preservation can keep the possible decision values of each object unchanged. Therefore, a reduct for generalized decision preservation [12] can be defined as follows:  
**Definition 5**. : _[_12_]_ _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), for all \(x_{i}\in U\), \(\exists x_{j}\in U\), \(Q\subseteq C\) is a reduct for generalized decision preservation in \(DS\) if and only if_  
1. \(\delta_{Q}(x_{i})=\delta_{C}(x_{i})\)_;_
2. \(\forall P\subset Q,\delta_{P}(x_{j})\
eq\delta_{Q}(x_{j})\)_._  
To get all reducts of a decision system for generalized decision preservation, [PERSON] et al. [12] described the discernibility matrix and its function for generalized decision preservation, as follows:  
**Definition 6**. : _[_12_]_ _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), for all \(x_{i},x_{j}\in U\), \(a\in C\), the discernibility matrix for generalized decision preservation is given by_  
\[M_{decision}(x_{i},x_{j})= \begin{cases}\{a|f(x_{i},a)\
eq f(x_{j},a)\},& \delta_{C}(x_{i})\
eq\delta_{C}(x_{j}).\\ \emptyset,&\text{otherwise}.\end{cases}  \tag{6}\]  
**Definition 7**. : _[_12_]_ _Given a decision system \(DS=(U,C\cup D,V_{a},I_{a})\), if \(M_{decision}(x_{i},x_{j})\
eq\emptyset\), then the discernibility function of \(DS\) can be denoted by_  
\[DF_{decision}(a_{1},a_{2},\ldots,a_{|C|})=\wedge\{\vee(M_{decision}(x_{i},x_{j}))| 1\leq i\leq j\leq|U|\}. \tag{7}\]  
A discernibility matrix provides a matrix description of discernible attributes. Regarding discernible attributes as literals in a clause, we construct a discernibility function, which is a conjunctive normal form. We translate a conjunctive normal form (CNF) into a disjunctive normal form (DNF) by using Boolean operation laws. For a DNF, the set of literals in a clause is a reduct in a decision system. Based on the discernibility matrix and its function for generalized decision preservation, [PERSON] et al. [12] introduced a discernibility matrix-based attribute reduction method for generalized decision preservation in Algorithm 1. Suppose that \(m\) denotes the number of condition attributes and \(n\) indicates the number of objects. Then, the time complexity of constructing a discernibility matrix is \(O(mn^{2})\). The time complexities of simplifying a discernibility function and converting a discernibility function into a disjunctive normal form are \(O(mn^{4})\) and \(m^{C[n/2]}\). Thus, the time complexity of Algorithm 1 is \(O(m^{C[n/2]}+mn^{4})\).