Rough set theory has emerged as a robust soft computing paradigm for feature selection, commonly known as reduct computation. A decision system may contain multiple reducts of varying sizes, all offering equivalent classification capabilities. However, when model performance is a critical factor, the shortest reduct is generally preferred due to its simplicity and interpretability. The discernibility matrix method is a widely used technique for computing such reducts. Despite its effectiveness, this method is computationally intensive and classified as NP-hard, limiting its scalability for datasets where discernibility matrix computation becomes infeasible. This study addresses the limitations of traditional discernibility matrix-based approaches by introducing a novel method that combines a Breadth-First Search control strategy with an incremental approach to compute the absorbed discernibility matrix. The Breadth First Search strategy enables efficient exploration of the search space to identify the shortest optimal reduct early, while the incremental absorbed discernibility matrix enhances the computational scalability of the algorithm. To validate the proposed method, an experimental evaluation was conducted against two state-of-the-art algorithms: Breadth-First Search, representing the discernibility matrix-based strategy, and MinReduct, a benchmark for absorbed discernibility matrix-based approaches. Results demonstrate superior computational performance and earlier discovery of shortest reducts without compromising correctness or optimality.

In rough set–based feature selection, the discernibility matrix provides a mathematical framework for computing all or multiple reducts. However, for applications such as ensemble model induction, there is no need to generate an exhaustive set of reducts; instead, selecting a smaller subset with better individual performance and sufficient diversity tends to more effective. Diversity among base classifiers is critical for improving the predictive performance of ensemble models, yet most existing rough set–based methods do not explicitly address this aspect when generating multiple reducts. To overcome this limitation, this paper proposes two strategies that embed diversity directly into the reduct generation process. The first introduces a novel partition refinement cardinality heuristic that selects mutually exclusive reducts with maximum partition cardinality differences to promote classifier diversity. The second presents an efficient adaptation of an existing least overlap heuristic, combined with an incremental construction of the absorbed discernibility matrix to ensure scalability for large datasets where conventional discernibility matrix construction is infeasible. Finally, empirical analysis with state-of-the-art algorithms demonstrates that the diverse reducts generated by the proposed methods successfully achieve their goal of enhancing ensemble model performance through improved diversity and predictive accuracy.

Traditionally, the shortest length has been used as the optimality criterion in rough set based optimal / near-optimal reduct computation. A more generalizable alternative to the optimal reduct computation approach was recently introduced, with the coarsest granular space as the optimality criterion. However, owing to exponential time complexity, it is not scalable to even moderate-sized data sets. This article investigates to formulate two near-optimal reduct computation alternatives for scaling comparatively larger data sets. The first algorithm employs a controlled A∗ search based strategy to find a near-optimal reduct while reducing both space utilization and computational time. Whereas, the second algorithm employs a greedy sequential backward elimination (SBE) strategy on the higher granular space attribute ordering for achieving coarsest granular space based near-optimal reduct. The comparative experimental study is conducted among the proposed approaches with the coarsest granular space based optimal reduct algorithm A∗RSOR and state-of-the-art shortest length based optimal and near-optimal reduct algorithms. The experimental study amply validates the relevance of the proposed approaches in obtaining near-optimal reduct with increased scalability and comparable or improved generalizable classification models induction.

The optimal reduct computation problem aims to obtain the best reduct out of all possible reducts of a given decision system. In the rough set literature, two optimality criteria exist for computing an optimal reduct: shortest length based and coarsest granular space based. The coarsest granular space-based optimal reduct has the ability to induce a better generalizable classification model. The A∗RSOR is an existing A∗ search-based optimal reduct computation algorithm that uses the coarsest granular space as an optimality criterion. This article proposes an improved coarsest granularity-based optimal reduct approach MA∗_RSOR through analyzing the search process’s behaviour in A∗RSOR algorithm. To minimize the search space utilization and arrive at an optimal reduct in less time, suitable modifications are incorporated using the domain knowledge of rough set theory. The relevance of MA∗_RSOR is demonstrated through theoretical analysis and comparative experimental validation with state-of-the-art algorithms. The experimental results with benchmark data sets established that MA∗_RSOR achieves significant computational time gain (49 - 99 %) and space reduction (37 - 96 %) over A∗RSOR. The MA∗_RSOR could induce classification models with significantly better classification accuracies than state-of-the-art shortest length-based optimal/near-optimal reduct computation algorithms. In addition, a coefficient of variation based CVNonCore heuristic is proposed for predicting when the MA∗_RSOR algorithm is appropriate to use. Experimental results validate the relevance of the heuristic as its prediction turned out correctly in 8 out of 10 data sets.

Rough set theory has emerged as an influential soft-computing approach for feature subset selection (reduct computation) in the decision system amidst incompleteness and inconsistency. Multiple reducts computation using rough sets provide an elegant way for construction of ensemble classifier for better and stable classification. The existing approaches for multiple reducts computation are primarily based on the genetic algorithm and select diverse multiple reducts after generation of abundant candidate reducts. This work proposes an MRGA_MRC algorithm for multiple reducts computation by utilizing the systematically evolving search space of all reducts computation in the MRGA algorithm without generation of many candidate reducts. A novel heuristic is introduced for selection of diverse multiple reducts. Experiments conducted on the benchmark decision systems have established the relevance of the proposed approach in comparison to the genetic algorithm based multiple reducts computation approach REUCS.

Feature subset selection or reduct computation is a prominent domain for the classical 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 computing prime implicants of the discernibility function. Currently, an optimal reduct based on any optimality criteria can only be achieved post-generation of all possible reducts. Indeed, it is an NP-hard problem. Several researchers have extended the alternative aspects with 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 obtained significantly better accuracies with different classifiers.