DM: Re: Minimal rule covering

[Monte Hancock]

You said:
>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.
>
>Thanks
>
>Augusto
>

>From your question it's not clear whether you're inducing 
>propositional
rules or predicate rules with variables. In the latter case, we have 
had
some experience in rewriting redundant rules (syntatically different 
but
semantically equivalent) for the purpose of minimizing the size of a
ruleset. (In one case we were able to reduce a ruleset containing 
about
50000 redundant rules to about 800 normalized rules).

Our approach was fairly simple: use pattern matching to recognize a 
sets
of rule patterns. We have developed a rule-making language called RML
which can do this pattern matching with or without depending on word
order. It partitions the ruleset into clusters of rules. RML then
simulates firing the rules generating a semantic pattern which further
classifies the rules into smaller clusters which constitute are 
equivalence classes for the normalized rules.

Quinlan and his colleague Cameron-Jones have done a lot of research 
on 
generating optimal rulesets (both propositional and predicate). Try:
                  http://www.cs.su.oz.au/ML/

Hope that helps.

John C. Day, jday@csihq.com
Principal Staff Scientist
Computer Science Innovations
Melbourne, Fl 32904
Web: http://www.csi.cc  
     http://www.csi.cc/rml