Rough Set Theory In Knowledge Discovery Applications

Rough set theory is a newly-emerging mathematical tool to deal with vague and uncertain knowledge, which can analyze the rule hidden in the data without any additional information. It wins more and more attention because of its special advantage, and is applied in various kinds of domains. The main research of this paper is as follows:(1) Optimal reduct under preference: The algorithm to get all reducts of rough set theory is a typical NP-complete problem, which limits the application of rough set in real life. The reason is that there are more than one attributes that is dispensable in the procedure of getting reducts, deleting different ones will get different reducts, so there is conflicts when we decide to delete attributes. In our research, we adopt the common method to avoid conflicts in AI, which is preference. After we add preference relation on attributes, reducts are ordered under this relation. Through the induction of special cases, we design a kind of tree, and get the algorithm to retrieve optimal reduct under preference. Eventually, we create relationship between the dispensable property and functional dependency, through which we improve the algorithm and its efficiency.(2) Rough set theory and entropy: In rough set theory, knowledge is seen as the ability of classification, which is the ability to construct partitions over universe. From the view of information theory, knowledge is information which is useful to us, while information is retrieved from data. With respected to information, there exists uncertainty, which is measured by entropy. Therefore, it is feasible to measure uncertainty in rough set theory. In our research, we propose the concept of knowledge entropy, discuss algebraic property, and create relationship between basic concepts in rough set theory and knowledge entropy, through which we can get such basic concepts in rough set theory as reduct, core, and etc.(3) Extension of rough set theory based on partial order: Of all results present, there are many theories to generalize rough set, such as extension under tolerance, under similarity and etc. This research present a framework of rough set under partial order, with respect to the method to mine OIT proposed by Sai, Ying and Yao,Y.Y., and can mine any ordered information. The analysis and experiment show that the complexity is only one to n~2 of the former method, while n is the number of the entities.