Finding Optimal Rough Set Reduct with A* Search Algorithm

EasyChair Preprint 5071

Abstract

Feature subset selection or reduct computation is an important application of rough set theory which can preserve the most predictive features of a decision system. A given decision system has several reducts. Computation of all possible reducts was achieved through the computation of prime implicants of the discernibility function. Currently, an optimal reduct based on any optimality criteria can only be obtained post-generation of all possible reducts. As this approach is an NP-complete problem, researchers have investigated several alternatives search strategies such as Genetic Algorithm, Ant Colony Optimization, Simulated Annealing, etc., for obtaining near optimal reducts. In this paper, we propose an admissible and consistent heuristic for computing the optimal reduct having least number of induced equivalence classes or granules. A*RSOR reduct computation algorithm is developed using the proposed consistent heuristic in A* search. The proposed approach is validated both theoretically and experimentally. The comparative results establish the relevance of the proposed optimality criterion as the achieved optimal reduct has resulted in inducing classifiers with significantly better accuracies.

Keyphrases: A* search, Optimal Reduct, attribute reduction, consistent heuristic, feature selection, reduct computation algorithm, reduct length, rough set, rough set optimal reduct, rough sets

@booklet{EasyChair:5071,
  author    = {Abhimanyu Bar and Anil Kumar and P.S.V.S Sai Prasad},
  title     = {Finding Optimal Rough Set Reduct with A* Search Algorithm},
  howpublished = {EasyChair Preprint 5071},
  year      = {EasyChair, 2021}}