Chinese Journal of Computers   Full Text
Title	Searching Algorithm for Attribute Reduction Based on Power Graph
Authors	CHEN Yu-Ming1),2) MIAO Duo-Qian1),2)
Address	1)(Department of Computer Science and Technology, Tongji University, Shanghai 201804) 2)(The Key Laboratory of Embedded System and Service Computing of Ministry of Education, Shanghai 201804)
Year	2009
Issue	No.8(1486—1492)
Abstract &   Background	Abstract Rough set theory is a new mathematical tool to deal with imprecise, incomplete and inconsistent data. Attribute reduction is one of important issues in rough sets. Most existing algorithms are studied under both algebra and information representations. As problem solving under different knowledge representations corresponding to different difficulties, the new knowledge representation, called power graph, is presented in this paper. Searching algorithms based on power graph are also proposed, which can translate computing problem of attribute reduction into searching problem in power graph. The algorithms will provide a new method in attribute reduction and the efficiency of the method has been proved in theoretical analysis. Keywords rough sets; attribute reduction; power graph; granular computing; knowledge representation Background Rough set theory has been successfully applied to several data analysis tasks in the field of artificial intelligence, such as data mining, knowledge discovery, pattern recognition, decision analysis, process control, image processing and medical diagnosis. Attribute reduction is one of the most important topics of rough set theory. Most existing algorithms are studied under both algebra and information representations. Under algebra representation, reduction algorithms mainly include positive region based algorithm, discernible matrix based algorithm and improved discernible matrix based algorithm. Under information representation, reduction algorithms mainly include information entropy based algorithm, conditional information entropy based algorithm and mutual information based algorithm. The main object of this paper is to provide a novel knowledge representation for attribute reduction question. As problem solving under different knowledge representations corresponding to different difficulties, power graph which is a graph representation is presented in the paper. Two kinds of searching ways based on power graph are also proposed, which are Top-down and Bottom-up. The search efficiency based on power graph is various according to different heuristic information. How to find more efficient heuristic information under the graph representation is future work. The research is supported by the National Natural Science Foundation of China under grant Nos.60475019, 60775036, and the Research Fund for the Doctoral Program of Higher Education of China under grant No.20060247039.