Re: DM: Minimal rule covering

[Dr. M. Hadjimichael]

> At 03:38 PM 10/9/98 -0300, Jose Augusto Baranauskas wrote:
> >Hi!
> >
> >I'd like to know about about minimal subset rule covering 
>algorithms. I
> >mean, after genetaring lots of induced rules, I'd like to get a 
>minimal
> >robust subset that covers the majority of instances. 

You may want to consider Rough Set Theory-based machine learning
methodologies.  I've attached some descriptive material from the web
page of the Electronic Bulletin of the Rough Set Community, where
extensive information about Rough Sets may be found.

                http://www.cs.uregina.ca/~roughset

-Mike.
 
______________________________________________________________________
 . Mike Hadjimichael, Ph.D.                  hadjimic@nrlmry.navy.mil 
.
 . NCAR/RAP Scientific Visitor                          mikeh@acm.org 
.
 . Naval Research Laboratory, Monterey                   831-656-6010 
.
 . 7 Grace Hopper Ave                                fax 831-656-4769 
.
 . Monterey, CA 93943-5502       http://www.nrlmry.navy.mil/~hadjimic 
.
 
----------------------------------------------------------------------


[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.


                             * * * * *