# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 1 Introduction
[29] gave a feature selection algorithm which can find minimal subset of the features. [PERSON] et al. [30] investigated a partial-complete searching method for ant colony optimization and developed an algorithm for time-cost sensitive attribute reduction. [PERSON] et al. [36] researched minimum cost attribute reduction by using simulated annealing and genetic algorithms. Metaheuristic attribute reduction is an active and important research field in attribute reduction. Compared with heuristic attribute reduction methods, some significant research results by using metaheuristic attribute reduction methods have been achieved. [PERSON] et al. [25] developed a metaheuristic attribute reduction algorithm for real-valued data, called the hybrid ABC-EFTSBPSD. Comparative experiments were conducted to verify the performance of the hybrid ABC-EFTSBPSD and the following two conclusions were obtained: (1) The length of a reduct calculated by the hybrid ABC-EFTSBPSD was shorter than those of reducts calculated by the heuristic reduction algorithms (ACO-RST [27], Q-MDRA [38], and IMCVR [39]), in most cases. (2) By employing C4.5 and SVM classifiers, the hybrid ABC-EFTSBPSD had higher classification accuracies than the heuristic reduction algorithms (Q-MDRA, ACO-RST, and IMCVR). Compared with the heuristic attribute reduction methods MIBR [14] and QUICKREDUCT [24], the algorithm RSFSACO, based on ant colony optimization, proposed by [PERSON] et al. [29] could obtain a minimal reduct in most cases. In a decision system, objects with the same condition attribute values may have different decision values. To keep these decision values unchanged, [PERSON] et al. [12] proposed an attribute reduction method for generalized decision preservation based on the discernibility matrix. Based on this method, one can find all reducts for generalized decision preservation from a decision system. In constructing a discernibility matrix and translating a conjunctive normal form (CNF) into a disjunctive normal form (DNF) in a discernibility function, discernibility matrix-based reduction algorithms for generalized decision preservation are computationally time-consuming and impractical when dealing with large amounts of data. To address this problem, we introduce the similarity degree for generalized decision preservation. By using the inner and outer significance measures, we develop two quick reduction algorithms for generalized decision preservation. Theoretical analyses and experimental results show that two proposed algorithms are feasible and efficient. The novelties and contributions of this paper can be summarized as follows: First, a similarity measure for generalized decision preservation has not yet been proposed so far. Hence, in order to measure the similarity of attributes for generalized decision preservation, we introduce a novel monotonic similarity degree in this paper. Second, to evaluate the significance of an attribute for generalized decision preservation, we propose two significance measures (the inner and outer significance measures for generalized decision preservation), based on the proposed similarity degree. Third, we use the add-deleting and deleting strategies to design forward and backward greedy reduction algorithms for generalized decision preservation (FGRAG and BGRAG). If \(m\) denotes the number of condition attributes and \(n\) indicates the number of objects, the time complexities of FGRAG and BGRAG are \(O(m^{3}n)\) and \(O(m^{2}n)\), respectively. The time complexity of the discernibility matrix-based reduction algorithm for generalized decision preservation (DMRAG) proposed by [PERSON] et al. [12] is \(O(m^{c_{m}^{\left[m/2\right]}}+mn^{4})\). The running time of DMRAG increases distinctively when the number of attributes and objects increase. Meanwhile, the running time of FGRAG (BGRAG) is less than that of DMRAG, relatively. Thus, the proposed reduction algorithms (FGRAG and BGRAG) are more efficient.