Research Of Attribute Reduction Algorithm Based On Discernibility For Decision Table

Rough set theory is a data analysis tool which can effectively analyze and deal with inconsistent, imprecise and incomplete data that Z.Pawlak the famous professor in Poland proposed in the early 80’s. The attribute reduction is a key problem of rough set theory, as well as an important basis of the knowledge discovery and decision research, which idea is deleting knowledge that not important or not relevant in the condition of keeping the classification ability of the knowledge base constant. And SKM.Wong has proved that obtaining the best reduction or all reductions of the information table is a NP problem, so how to optimize the attribute reduction algorithm, how to improve efficiency, how to reduce complexity, and how to get better results, is still a main research topic of rough set.Attribute reduction is an important concept in rough set theory. The time complexity of algorithm based on discernibility is high. To overcome this shortcoming, we propose an improvement to quick reduction algorithm. For the decision table, we quantify discernibility of attributes by using the relative knowledge quantity. To get it more quickly, a method depends on the computational efficiency of equivalent class is proposed. And we use the relative knowledge quantity as the heuristic information to reduce attributes. The paper proposes two kinds of attribute reduction algorithms based on discernibility. One is that the relative knowledge quantity of decision table as a condition for ending reduction, another is the change of relative knowledge quantity of attribute set.In this paper, first of all, we describe the background and current situation of rough set theory; secondly, give a brief description of the basic idea and concept of Pawlak’s classical rough set model; then analyze the present classic attribute reduction algorithms and compare their advantages and disadvantages, which including four kinds of algorithms:the positive region, the important degree of attributes, the information entropy and the discernibility matrix; at last, introduce two kinds of improved heuristic attribute reduction algorithms of decision table based on the distinguish ability proposed in this paper, which mainly introduce the algorithm idea, describe the algorithm principle, show the algorithm flow, analyze the algorithm complexity, apply the algorithms to the example, analyze and compare the result. The main work of this paper is:(1) We introduce the concept that the relative knowledge quantity to quantify the distinguish ability of knowledge. We use the base of equivalence class to calculate the relative knowledge quantity recursively in this paper. Firstly, we compute the equivalence class division of condition attributes; then, calculate each the classification base of each sub class of equivalence class relative to decision attribute; finally, count the relative knowledge quantity of all sub classes according to the concept, and superpose them to obtain the relative knowledge quantity of the condition attributes.(2)In this paper, we the relative knowledge quantity as heuristic information to design two improved attribute reduction algorithms based on the distinguish ability are, which are the algorithm of adding attributes and the algorithm of updating attributes. One is that the relative knowledge quantity of decision table as a condition for ending reduction; another is the change of relative knowledge quantity of attribute set, and the algorithms efficiency are high.(3) We realize, analyze and compare the two proposed algorithms in the view of UCI data set, and the effectiveness of algorithms are illustrated in this paper. The attribute reduction algorithm based on distinguish ability of adding attribute is fit to the situation that there are a big difference between the number of original attributes and reduction attributes, while the other algorithm of updating attribute is suit for the number of similar cases comparably.