Accelerated Feature Selection via Discernibility Hashing: A Rough Set Approach

Abstract

As a foundational analytical tool, the discernibility matrix plays a pivotal role in the systematic reduction of knowledge in rough set-based systems. Recent advancements in rough set theory have witnessed the proliferation of discernibility matrix-based knowledge reduction algorithms, with notable applications in classical, neighborhood, covering, and fuzzy rough set models. However, the quadratic growth of the discernibility matrix’s complexity (relative to domain size) imposes fundamental scalability limits, rendering it inefficient for real-world applications with massive datasets. To address this issue, we introduced a discernibility hashing strategy to limit the growth scale of the discernibility attributes and proposed a feature selection algorithm via discernibility hash based on rough set theory. First, on the premise of keeping the information of the original discernibility matrix unchanged, the method maps the discernibility attribute set of all objects to the storage unit through a hash function and records the number of collisions to construct a discernibility hash. By using this mapping, the two-dimensional matrix space can be reduced to a one-dimensional hash space, which greatly removes invalid and redundant elements. Secondly, based on the discernibility hash, an efficient knowledge reduction algorithm is proposed. The algorithm avoids invalid and redundant element attribute sets to participate in the knowledge reduction process and improves the efficiency of the algorithm. Finally, the experimental results show that the method is superior to the discernibility matrix method in terms of storage space and running time.