A dynamic attribute reduction algorithm based on 0-1 integer programming

Attribute reduction is an important research concept in rough set theory. Many attribute reduction algorithms were designed for the static information system in the past years. However, many real-world data are generated dynamically. Then a new dynamic attribute reduction algorithm based on a 0-1 integer programming is proposed to deal with the dynamic data in this paper. When multiple objects in the information system evolve over time, instead of treating the changed information table as a new one and finding the reduct again like rough set reduction algorithm does, the proposed algorithm just updates the original reduct. Therefore, its computational speed improves greatly. In addition, an approach of constraint preprocessing is also presented in this paper. Numerical experiments on twelve benchmark datasets testify the feasibility and validity of the proposed algorithm.

► A new static attribute reduction algorithm based on 0-1 integer programming is presented, and the attribute reduction problem is converted into a 0-1 integer programming problem.
► A new dynamic attribute reduction algorithm based on 0-1 integer programming is proposed to deal with the dynamic data, and we can achieve the dynamic reduct just by updating the original reduct.
► In order to improve the efficiency of attribute reduction, an approach of constraint preprocessing is presented, and large numbers of redundant constraints will be deleted by this approach.
► The relation between the optimal solution of 0-1 integer programming and the reduct in rough set is discussed.