Variable Neighborhood Search for Attribute Reduction in Rough Set Theory

Attribute reduction is a combinational optimization problem in data mining domain that aims to find a minimal subset from a large set of attributes. The typical high dimensionality of datasets precludes the use of greedy methods to find reducts because of its poor adaptability, and requires the use of stochastic methods. Variable Neighborhood Search (VNS) is a recent metaheuristic and have been successfully applied to solve combinational and global optimization problems. In our paper, the Variable Neighborhood Search scheme combined with a local search scheme called Variable Neighborhood Descent (VND) is adopted to find the reduction. We also use conditional entropy as metric to measure the quality of reduction. To verify the efficiency of our method, experiments are carried out on some standard UCI datasets. The results demonstrate the efficiency of our method.