next up previous
Next: Pessimistic Pruning Up: Overview of WIDC Previous: Explicit Solution in the

Pruning a DC

The algorithm is a single-pass algorithm: each rule is tested only once, from the first rule to the last one. For each possible rule, a criterion Criterion(.) returns ``TRUE'' or ``FALSE'' depending on whether the rule should be removed or not. There are two versions of this criterion. The first one, which we call ``pessimistic'', is based on conventional error minimization. The second one, called ``optimistic'', is derived from a previous work on pruning decision-trees [Kearns Mansour1998].


2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.