A New and Efficent Algorithm to Attribute Reductionin Incomplete Decision Table

Attribute reduction is one of the most important issues and the focus of the research on efficient algorithms in rough sets. To obtain the most concise rule set from a decision table, the attribute reduction should have the least cardinality. But this is a NP-hard problem and heuristic algorithms of multinomial time complexity are introduced to get the approximately best solution. The paper studies the attribute reduction incomplete decision tables and a criterion to weigh the importance of attributes in incomplete decision tables is defined and a new attribute reduction algorithm based on the criterion is introduced. An efficient algorithm to seek the set of objects similar to the considered object based on sort and binary search is also advanced in the paper and the efficiency of the attribute reduction algorithm is improved accordingly. The work of the paper solve the attribute reduction problem satisfiedly.