A novel attribute reduction algorithm based on granular sequential three-way decision

Attribute reduction plays a crucial role in knowledge discovery, and sequential three-way decision (S3WD) provides a new method for attribute reduction. However, the three regions of the S3WD model are usually represented as three sets, which leads to two disadvantages. On one hand, it is difficult to obtain the condition of a decision rule when multiple equivalence classes are merged into a set because different equivalence classes have different descriptions. On the other hand, if the boundary region of the upper level of S3WD is a set, one has to partition the upper level with all the acquired attributes rather than the newly added attribute. That is, there is double counting. Therefore, this paper focuses on how to retain the topology of equivalence classes in S3WD, and how to use this topology to enhance semantic interpretation and improve computational efficiency. To this end, a granular version of S3WD, called granular sequential three-way decision (GS3WD), is first developed to retain the information structure of equivalence classes. And then, three acceleration strategies and an efficient granular sequential three-way reduction (GS3WR) are proposed. Finally, a concept tree can be generated simultaneously in the process of GS3WR, and the decision rules with multi-granularity can be extracted from this concept tree directly. Experimental results show that GS3WR can obtain the same core attributes and reducts as the representative attribute reduction algorithms in rough sets and the computational efficiency is improved by hundreds of times.