Local Search for Attribute Reduction

Two new attribute reduction algorithms based on iterated local search and rough sets are proposed. Both algorithms start with a greedy construction of a relative reduct. Then attempts to remove some attributes to make the reduct smaller. Process of attributes selection is the main difference between the algorithms. It is random for the first one, and a sophisticated selection procedure is used for the second algorithm. Moreover a fixed number of iterations is assumed for the first algorithms whereas the second stops when a local optimum is reached. Various experiments using eight well-known data sets from UCI have been made and they show substantial superiority of our algorithms.