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

Jie ZHAO, Daiyang WU, JiaXin WU, Eric W. K. SEE-TO, Faliang HUANG*

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

Abstract

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%.
Original languageEnglish
Article number110962
JournalApplied Soft Computing
Volume149
Early online date21 Oct 2023
DOIs
Publication statusPublished - Dec 2023

Bibliographical note

Publisher Copyright:
© 2023 Elsevier B.V.

Keywords

  • Dominance-based rough set approach
  • Dual information granule
  • Fast approximation calculation

Fingerprint

Dive into the research topics of 'Fast Calculation for approximations in Dominance-based Rough Set Approach using Dual Information Granule'. Together they form a unique fingerprint.

Cite this