Efficient Attribute Reduction Algorithm Based on Incomplete Decision Table
Rough set theory is emerging as a powerful toll for reasoning about data. Attribute reduction is one of important topics in the research on the rough set theory. At present, there is few researchers investigated attribute reduction based on incomplete decision table. Since computing attribute reduction of the incomplete decision table is more difficult than that of complete decision table, the designed attribute reduction algorithms based on incomplete decision table are no better than those based on complete decision table. The time complexity of the existed algorithm of attribute reduction based on incomplete decision table is O(|C|3|U|2). To lower the time complexity, we first analyzed the shortcoming of those algorithms. And we provided an efficient algorithm for computing the tolerance class. Then we use the above algorithm to design an efficient algorithm of attribute reduction based on information quantity. The time complexity of the new is O(|C|2|U|2).
rough set attribute reduction incomplete decision table tolerance relation
Qingguo Zhang Xuefeng Zheng Zhangyan Xu
School of information engineering,University of Science and Technology Beijing,Beijing, 10083, China College of Computer Science & Information Engineering,Guangxi Normal University,Gulin 541004, China
国际会议
长沙
英文
3171-3174
2009-10-10（万方平台首次上网日期，不代表论文的发表时间）