Fast algorithms of attribute reduction for covering decision systems with minimal elements in discernibility matrix

摘要

Covering rough sets, which generalize traditional rough sets by considering coverings instead of partitions, are introduced to deal with set-valued, missing-valued or real-valued data sets. For decision systems with such kinds of data sets, attribute reduction with covering rough sets aims to delete superfluous attributes, and fast algorithms of finding reducts are clearly meaningful for practical problems. In the existing study of attribute reduction with covering rough sets, the approach of discernibility matrix is the theoretical foundation. However, it always shares heavy computation load and large store space because of finding and storing all elements in the discernibility matrix. In this paper, we find that only minimal elements in the discernibility matrix are sufficient to find reducts. This fact motivates us in this paper to develop algorithms to find reducts by only employing minimal elements without computing other elements in the discernibility matrix. We first define the relative discernible relation of covering to characterize the relationship between minimal elements in the discernibility matrix and particular sample pairs in the covering decision system. By employing this relative discernible relation, we then develop algorithms to search the minimal elements in the discernibility matrix and find reducts for the covering decision system. Finally, experimental comparisons with other existing algorithms of covering rough sets on several data sets demonstrate that the proposed algorithms in this paper can greatly reduce the running time of finding reducts.