An Integrated Strategy for Accelerating Attribute Reduction in Neighborhood Rough Set

Neighborhood rough set model has received much attention in Granular Computing due to its ability to show the process of information granulation more intuitively. As an important application of this model, the problems related to attribute reduction have also attracted wide attention, especially its time consumption. To reduce the time consumption, various acceleration algorithms have been proposed. However, most of the existing acceleration algorithms accelerate the procedure of deriving reduct from only one perspective of the sample or conditional attribute, so the acceleration efficiency still needs to be improved. In order to solve this problem, this paper accelerates from the integrated perspectives of sample and conditional attribute and then proposes a new attribute reduction algorithm. First, the samples are randomly divided into multiple sample subsets and then sorted in ascending order based on their granularities, the higher the order, the finer its granularity. Next, the granularities of the conditional attributes within each sample subset are calculated and these conditional attributes are also sorted in ascending order of granularity. For the sample subsets with the same sorting results of conditional attributes, one of the subsets will be retained randomly. Finally, the reduct is obtained from the finest granularity sample subset by sequentially adding conditional attributes to the reduct pool based on granularity, which guides the coarser granularity sample subset. To verify the effectiveness of the proposed algorithm, it is compared with four acceleration algorithms using 9 UCI data sets. The results show that the proposed algorithm has superior performance in both execution efficiency and the quality of reduct.