Quick attribute reduct algorithm for neighborhood rough set model

摘要

In this paper, we propose an efficient quick attribute reduct algorithm based on neighborhood rough set model. In this algorithm we divide the objects (records) of the whole data set into a series of buckets based on their Euclidean distances, and then iterate each record by the sequence of buckets to calculate the positive region of neighborhood rough set model. We also prove that each record’s h-neighborhood elements can only be contained in its own bucket and its adjacent buckets, thus it can reduce the iterations greatly. Based on the division of buckets, we then present a new fast algorithm to calculate the positive region of neighborhood rough set model, which can achieve a complexity of O(m|U|); m is the number of attributes, |U| is the number of records containing in the data set. Furthermore, with the new fast positive region computation algorithm, we present a quick reduct algorithm for neighborhood rough set model, and our algorithm can achieve a complexity of O(m~2|U|). At last, the efficiency of this quick reduct algorithm is proved by comparable experiments, and especially this algorithm is more suitable for the reduction of big data.