A set covering based approach to find the reduct of variable precision rough set

Attribute reduction is one of the core problems in Rough Set (RS) theory. In the Variable Precision Rough Set (VPRS) model, attribute reduction faces two difficulties: firstly, in the VPRS model, a reduct anomaly problem may arise and it may cause an inconsistency of positive regions and decision rules after attribute reduction. Secondly, the attribution reduction problem has been proved an NP-hard problem; accordingly, we would need to find a tradeoff between calculating the minimal reduct and reducing computing complexity to avoid the combinatorial explosion problem. We propose a new approach to calculate the reduct in VPRS model. This new method focuses on calculating a ββ-distribution reduct while avoiding the anomaly problem in the VPRS model. The basic idea of the proposed approach is to convert the reduct problem into a Set Covering Problem (SCP) according to the positive regions in the VPRS model; and consequently, a Set-Covering Heuristic Function (SCHF) algorithm is applied to calculate the reduct after this conversion. This approach keeps the positive regions consistent after the attribute reduction and moreover, based on the SCP, the performance ratio of the proposed method to calculate the minimal reduct ranges between ln(|U′|)-lnln(|U′|)+o(1)ln(U′)-lnln(U′)+o(1) and (1-o(1))ln(|U′|)(1-o(1))ln(U′) with a computational complexity having an upper bound as o(MN(M+N)2)o(MN(M+N)2). Finally, we demonstrate the practical application of the VPRS model using real case scenario from China’s electricity power yield to verify the validity of our proposed approach. We then apply statistical evaluation to explain the economic significance of the attributes.