===================================================================== /------------------------------------------------\ < Electronic Bulletin of the Rough Set Community > \------------------------------------------------/ ===================================================================== A Brief Introduction to Rough Sets ---------------------------------- (Copyright 1993, EBRSC) I. Background [Quoted with permission from: ] [ The First International Workshop on Rough Sets: ] [ State of the Art and Perspectives ] [ by Wojciech Ziarko, U. of Regina, Saskatchewan ] The theory of rough sets has been under continuous development for over 12 years now, and a fast growing group of researchers and practitioners are interested in this methodology. The theory was originated by Zdzislaw Pawlak in 1970's as a result of a long term program of fundamental research on logical properties of information systems, carried out by him and a group of logicians from Polish Academy of Sciences and the University of Warsaw, Poland. The methodology is concerned with the classificatory analysis of imprecise, uncertain or incomplete information or knowledge expressed in terms of data acquired from experience. The primary notions of the theory of rough sets are the approximation space and lower and upper approximations of a set. The approximation space is a classification of the domain of interest into disjoint categories. The classification formally represents our knowledge about the domain, i.e. the knowledge is understood here as an ability to characterize all classes of the classification, for example, in terms of features of objects belonging to the domain. Objects belonging to the same category are not distinguishable, which means that their membership status with respect to an arbitrary subset of the domain may not always be clearly definable. This fact leads to the definition of a set in terms of lower and upper approximations. The lower approximation is a description of the domain objects which are known with certainty to belong to the subset of interest, whereas the upper approximation is a description of the objects which possibly belong to the subset. Any subset defined through its lower and upper approximations is called a rough set. It must be emphasized that the concept of rough set should not be confused with the idea of fuzzy set as they are fundamentally different, although in some sense complementary, notions. The main specific problems addressed by the theory of rough sets are: 1. representation of uncertain or imprecise knowledge 2. empirical learning and knowledge acquisition from experience 3. knowledge analysis 4. analysis of conflicts 5. evaluation of the quality of the available information with respect to its consistency and the presence or absence of repetitive data patterns. 6. identification and evaluation of data dependencies 7. approximate pattern classification 8. reasoning with uncertainty 9. information-preserving data reduction A number of practical applications of this approach have been developed in recent years in areas such as medicine, drug research, process control and others. The recent publication of a monograph on the theory and a handbook on applications facilitate the development of new applications [2,3]. One of the primary applications of rough sets in AI is for the purpose of knowledge analysis and discovery in data [4]. * * * * * References (A more extensive bibliography appears in the archive file rs.bib.txt) 1. Slowinski, R. and Stefanowski J. (eds.) Foundations of Computing and Decision Sciences. Vol. 18. no. 3-4, Fall 1993. 2. Pawlak, Z., Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer Academic Publishers, Dordrecht, 1991. 3. Slowinski, R. (ed.) Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory. Kluwer Academic Publishers, Dordrecht, 1992. 4. Ziarko, W. The Discovery, Analysis and Representation of Data Dependencies in Databases. In Piatesky-Shapiro, G. and Frawley, W.J. (eds.) Knowledge Discovery in Databases, AAAI Press/MIT Press, 1991, pp. 177-195. ------------------------------------------------------------------------------ II. A Simple and Informal Example [mh] This is a informal example of a rough set-based system. Obviously, this is not the place to go into overly formal details. Some basic definitions appear below, followed by a somewhat trivial example to demonstrate some basic concepts. * * * * Given a set of objects, OBJ, a set of object attributes, AT, a set of values, VAL, and a function f:OBJ x AT -> VAL, so that each object is described by the values of its attributes, we define an equivalence relation R(A), where A is a subset of AT: given two objects, o1 and o2, o1 R(A) o2 <=> f(o1,a) = f(o2, a), forall a in A We say o1 and o2 are indiscernible (with respect to attributes in A). Now, we use this relation to partition the universe into equivalence classes, {e_0, e_1, e_2, ... , e_n} = R(A)*. The pair (OBJ, R) form an _approximation space_ with which we approximate arbitrary subsets of OBJ referred to as _concepts_. Given O, an arbitrary subset of OBJ, we can approximate O by a union of equivalence classes: the LOWER approximation of O (also known as the POSITIVE region): LOWER(O) = POS(O) = Union_{e_i subset O} e_i the UPPER approximation of O: UPPER(O) = Union_{e_i \interset O \not= empty} e_i NEG(O) = OBJ - POS(O) BND(O) = UPPER(O) - LOWER(O) (boundary) There are several versions of the exact definition of a rough set (unfortunately), the most common is that a roughly definable set is a set, O, such that BND(O) is non-empty. So a rough set is a set defined only by its lower and upper approximation. A set, O, whose boundary is empty is exactly definable. If a subset of attributes, A, is sufficient to create a partition R(A)* which exactly defines O, then we say that A is a _reduct_. The intersection of all reducts is known as the _core_. This is the simplest model. There are several probabilistic versions. Many researchers have used rough set theory for inductive learning systems, generating rules of the form: description(POS(O)) --> positive decision class description(NEG(O)) --> negative decision class description(BND(O)) ~~> (probabilistically) positive decision class === A Short (trivial) Example === Name Education Decision (Good Job Prospects) -------------------------------------------------------------- Joe | High School | No Mary | High School | Yes Peter | Elementary | No Paul | University | Yes Cathy | Doctorate | Yes So, the set of positive examples of people with good job prospects: O = {Mary, Paul, Cathy} The set of attributes: A = AT = {Education} The equivalence classes: R(A)* = {{Joe, Mary}, {Peter}, {Paul}, {Cathy}} The lower approximation and positive region: POS(O) = LOWER(O) = {Paul, Cathy} The negative region: NEG(O) = {Peter} The boundary region: BND(O) = {Joe, Mary} The upper approximation: UPPER(O) = POS(O) + BND(O) = {Paul, Cathy, Joe, Mary} Decision rules we can derive: des(POS(O)) --> Yes des(NEG(O)) --> No des(BND(O)) ~~> Yes (equivalently ~~> No) That is: (Education, University) or (Education, Doctorate) --> Good prospects (Education, Elementary) --> No good prospects (Education, High School) ~~> Good prospects (i.e. possibly) ===End of Example=== * End of File * //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\