7.txt

This complete matlab for neural network

发信人: sn (小龙), 信区: DataMining
标  题: a brief introduction to rough sets
发信站: 南京大学小百合站 (Tue Jan 22 14:30:03 2002), 站内信件

=====================================================================
          /------------------------------------------------\
         <  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 *
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\


--
 人是生而自由的，却无往不在枷锁之中。

※ 来源:．南京大学小百合站 bbs.nju.edu.cn．[FROM: 61.154.242.125]