Paper Info
Title
A set covering based approach to find the reduct of variable precision rough set.
Abstract
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) and (1-o(1))ln(U′) with a computational complexity having an upper bound as 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.
Year
DOI
Venue
2014
10.1016/j.ins.2014.02.023
Information Sciences
Keywords
Field
DocType
Variable precision rough set,Attribute reduct,Set covering problem,Relation matrix
Decision rule,Discrete mathematics,Set cover problem,Reduct,Logical matrix,Upper and lower bounds,Algorithm,Rough set,Combinatorial explosion,Mathematics,Computational complexity theory
Journal
Volume
ISSN
Citations 
275
0020-0255
14
PageRank 
References 
Authors
0.54
28
3
Name
Order
Citations
PageRank
James N. K. Liu152944.35
Yan-Xing Hu2795.74
Yu-Lin He3506.64