Attribution reduction based on sequential three-way search of granularity

Most existing results about attribute reduction are reported by considering one and only one granularity, especially for the strategies of searching reducts. Nevertheless, how to derive reduct from multi-granularity has rarely been taken into account. One of the most important advantages of multi-granularity based attribute reduction is that it is useful in investigating the variation of the performances of reducts with respect to different granularities. From this point of view, the concept of Sequential Granularity Attribute Reduction (SGAR) is systemically studied in this paper. Different from previous attribute reductions, the aim of SGAR is to find multiple reducts which are derived from a family of ordered granularities. Assuming that a reduct related to the previous granularity may offer the guidance for computing a reduct related to the current granularity, the idea of the three-way is introduced into the searching of sequential granularity reduct. The three different ways in such process are: (1) the reduct related to the previous granularity is precisely the reduct related to the current granularity; (2) the reduct related to the previous granularity is not the reduct related to the current granularity; (3) the reduct related to the previous granularity is possible to be the reduct related to the current granularity. Therefore, a three-way based forward greedy searching is designed to calculate the sequential granularity reduct. The main advantage of our strategy is that the number of times to evaluate the candidate attributes can be reduced. Experimental results over 12 UCI data sets demonstrate the following: (1) three-way based searching is superior to some state-of-the-art acceleration algorithms in time consumption of deriving reducts; (2) the sequential granularity reducts obtained by proposed three-way based searching will provide well-matched classification performances. This study suggests new trends concerning the problem of attribute selection.