K-size partial reduct: Positive region optimization for attribute reduction

摘要

Optimal reduct is one of the challenging problems in rough set theory, and most of the existing algorithms cannot achieve the optimal reduct on high dimensional data sets. To explore an efficient algorithm for the optimal reduct problem, this paper proposes its generalization problem, which is defined as the K-size partial reduct problem. For this type of problem, an inefficient enumeration algorithm is first proposed. Then we enhance the enumeration algorithm through three improvements with the local search algorithm, i.e., fast initial solution construction, generation rules of solution, and dynamic object weighting strategy. The fast initial solution construction dramatically reduces the number of iterations, the generation rules of solution define a reasonable neighborhood structure and an effective candidate solution transfer model, and the dynamic object weighting strategy adjusts the iterative process to guide the algorithm to jump out of the local optimal solution. On the basis of these three improvements, an efficient local search-based K-size partial reduct algorithm is raised. Finally, a K-size partial reduct-based attribute reduction algorithm is designed by using the relationship between optimal reduct and K-size partial reduct. To validate the effectiveness of our proposed algorithms, we implemented a broad range of experimental simulations. The results of the experiments show the superiorities and innovations of the proposed algorithms compared with state-of-the-art algorithms.