Fast calculation for approximations in Dominance-based Rough Set Approach using Dual Information Granule

The Dominance-based Rough Set Approach (DRSA) is an extension of RST, which utilizes the dominance relation in attributes. However, traditional DRSA-based methods do not exploit the properties and logical structure in depth, which causes a high computational cost in lower and upper approximations. Besides, these methods are object-based, leading to repeated calculations from identical instances, and they involve numerous redundant computations to approximate different decisions. Therefore, we propose a novel approach, called DIGAC (Dual Information Granule-based Approximation Calculation), to improve DRSA by replacing the object-based calculation with the granule-based calculation. It effectively reduces the time complexity by constructing a granule-based ordered decision system. Additionally, this novel approach uses three types of Dual Information Granules (DIGs) to avoid repeated calculations from identical samples. In the process of lower and upper approximation, we leverage their transitivity to put forward a Distributed Storage-based Lower Approximation Calculation (DSLAC) strategy and a Query-based Upper Approximation Calculation (QUAC) strategy to eliminate redundant computations. Importantly, we theoretically prove that the DIG-based approach extensively reduces the time complexity of the approximations and obtains the same approximations as the original counterpart. Our approach is investigated on 23 datasets, and the experimental results show that it outperforms existing algorithms in terms of efficiency and stability, especially for large-scale and high-dimensional datasets, where the average decrease in execution time is up to 99%.