Journal of Data Science

Feature selection methods in Rough Set Theory and Logical Combinatorial Pattern Recognition commonly rely on simplified binary discernibility matrices to represent the condition attributes that distinguish objects from different decision classes. However, the original discernibility matrix involves a large number of redundant object comparisons, which severely limits computational efficiency and scalability. Although several algorithms have been proposed to compute the simplified matrix, most of them first construct the full discernibility matrix and then simplify it, making these approaches impractical for large-scale datasets. In this paper, we introduce ISBMA, an incremental algorithm based on a deterministic finite automaton that directly constructs the simplified binary discernibility and discernibility/similarity matrices without explicitly generating the full matrix. Experimental comparisons with the fastest reported method demonstrate that ISBMA significantly reduces redundant computations, requires substantially less memory, and achieves superior runtime performance, remaining feasible on large decision tables where existing approaches fail.