An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory

摘要

Attribute reduction is an important preprocessing step in data mining and knowledge discovery. The effective computation of an attribute reduct has a direct bearing on the efficiency of knowledge acquisition and various related tasks. In real-world applications, some attribute values for an object may be incomplete and an object set may vary dynamically in the knowledge representation systems, also called decision systems in rough set theory. There are relatively few studies on attribute reduction in such systems. This paper mainly focuses on this issue. For the immigration and emigration of a single object in the incomplete decision system, an incremental attribute reduction algorithm is developed to compute a new attribute reduct, rather than to obtain the dynamic system as a new one that has to be computed from scratch. In particular, for the immigration and emigration of multiple objects in the system, another incremental reduction algorithm guarantees that a new attribute reduct can be computed on the fly, which avoids some re-computations. Compared with other attribute reduction algorithms, the proposed algorithms can effectively reduce the time required for reduct computations without losing the classification performance. Experiments on different real-life data sets are conducted to test and demonstrate the efficiency and effectiveness of the proposed algorithms.