Generating Accurate Rule Sets Without Global Optimization

Eibe FrankIan H. Witten

article1998ICML1,514 citations

Presents PART, a fast rule-learning algorithm that avoids complex global optimization by deriving rules from partial decision trees within a separate-and-conquer framework to achieve accuracy and compact model sizes matching or exceeding C4.5 and RIPPER.

Listen

Rule-based models are widely valued across organizations because their straightforward if-then format allows human experts to interpret, audit, and validate machine-derived decisions. However, standard rule-generation systems—most notably C4.5 and RIPPER—rely on complex, computationally demanding multi-stage global optimization procedures to clean up or adjust rules after they are initially created. These post-processing phases add engineering overhead, run slowly on noisy datasets, and risk oversimplifying rules through hasty generalizations.

The article demonstrates a streamlined rule-learning algorithm called PART, which builds accurate and compact rule sets one rule at a time without requiring any global optimization post-processing. It evaluates whether integrating partial decision trees into an iterative rule-learning framework can match or surpass established industry benchmarks in accuracy, simplicity, and computational efficiency.

The authors designed an algorithm that repeatedly generates partial decision trees—exploring only the minimum structure needed to identify a stable rule—and extracts the single most general leaf rule before removing the covered examples and repeating the process. To test its credibility across diverse domains, the method was benchmarked against C4.5, C5.0, and RIPPER across 34 standard datasets from the UCI repository using rigorous ten-fold cross-validation and statistical significance testing.

The evaluation revealed three key operational findings. First, PART achieved statistically superior predictive accuracy over RIPPER on 14 datasets while underperforming on only 6, providing strong evidence of its higher overall accuracy. Second, PART matched the accuracy of full-tree optimization methods, performing competitively against C4.5 (9 wins versus 6 losses) and C5.0 (6 wins versus 10 losses), differences that are not statistically significant. Third, PART generated rule sets of comparable size—producing smaller rule sets than C4.5 and C5.0 on 18 of the 34 datasets—while avoiding severe performance bottlenecks, exhibiting subquadratic execution times even on pathological datasets where C4.5 scales cubically.

These findings indicate that organizations do not need to choose between computational efficiency, implementation simplicity, and model accuracy. System developers can eliminate complex multi-step rule optimization pipelines without sacrificing the interpretability or precision of the resulting models. This substantially reduces processing latency, engineering risk, and maintenance overhead for rule-based systems deployed on noisy or large-scale data.

Decision-makers building or maintaining interpretable classification workflows should consider adopting partial-tree induction as an alternative to complex two-stage systems. As a next step, the article suggests investigating alternative pruning and stopping criteria, such as reduced error pruning or description length principles, to evaluate whether rule set sizes can be reduced further without hurting predictive performance.

While the algorithm produces slightly larger rule sets on average than RIPPER, confidence in PART's accuracy and speed advantages remains high given the breadth of the 34-benchmark evaluation. Stakeholders should note that the results are established on standard offline classification datasets and evaluate performance on their specific domain-specific streaming or large-scale data before full operational replacement.

University of Waikato optimization optimization problems compiler optimizations partial decision trees rule induction global optimization

Frank et al (1998).pdf

Paper: Fast Effective Rule Induction, William W. Cohen (1995). This paper introduces RIPPER and its global optimization post-processing stage, which serves as the primary rule-learning baseline and conceptual foil for the proposed method.
Paper: Induction of Decision Trees, J. R. Quinlan (1986). This foundational work establishes the top-down decision tree induction paradigm upon which the partial decision tree generation method directly builds.
Paper: The CN2 Induction Algorithm, Peter Clark et al. (1989). This paper introduces the separate-and-conquer rule induction strategy that the source combines with decision tree induction to build rule sets iteratively.
Paper: Improved Use of Continuous Attributes in C4.5, J. R. Quinlan (1996). This paper details the continuous attribute handling mechanisms in C4.5, whose complex multi-stage rule post-processing is directly critiqued and improved upon in the source.
Paper: Very Simple Classification Rules Perform Well on Most Commonly Used Datasets, ROBERT C. HOLTE (1993). This work establishes benchmarks for rule simplicity and demonstrates that simple classification rules often rival complex decision models on standard datasets.

Paper: Logistic Model Trees, Niels Landwehr et al. (2003). This work develops Logistic Model Trees by integrating standard tree induction with leaf-level logistic regression models to deliver compact, interpretable classifiers without extensive manual tuning.
Paper: An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Thomas G. Dietterich (2000). This paper extends tree-based learning by evaluating how randomization, bagging, and boosting modify decision-tree induction under varying noise conditions.
Paper: Integrating Classification and Association Rule Mining, Bing Liu et al. (1998). This study explores an alternative rule-learning paradigm by integrating class association rule mining with classification heuristics to bypass standard decision tree post-processing.
Paper: Rotation Forest: A New Classifier Ensemble Method, Juan J. Rodríguez et al. (2006). This paper introduces Rotation Forests, extending decision tree induction methods through axis rotations to enhance diversity and predictive accuracy in tree-based models.
Paper: Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms, Chris J. Thornton et al. (2012). This work incorporates rule-learning algorithms, including PART and RIPPER implementations from WEKA, into an automated framework for combined algorithm selection and hyperparameter optimization.

Cover for Generating Accurate Rule Sets Without Global Optimization

Abstract

The two dominant schemes for rule-learning, C4.5 and RIPPER, both operate in two stages. First they induce an initial rule set and then they refine it using a rather complex optimization stage that discards (C4.5) or adjusts (RIPPER) individual rules to make them work better together. In contrast, this paper shows how good rule sets can be learned one rule at a time, without any need for global optimization. We present an algorithm for inferring rules by repeatedly generating partial decision trees, thus combining the two major paradigms for rule generation—creating rules from decision trees and the separate-and-conquer rule-learning technique. The algorithm is straightforward and elegant: despite this, experiments on standard datasets show that it produces rule sets that are as accurate as and of similar size to those generated by C4.5, and more accurate than RIPPER's. Moreover, it operates efficiently, and because it avoids postprocessing, does not suffer the extremely slow performance on pathological example sets for which the C4.5 method has been criticized.

Topics

optimization optimization problems compiler optimizations rule base naive bayes

Keywords

partial decision trees rule induction global optimization decision lists pessimistic pruning minimum description length principle subtree replacement hasty generalization class noise

1 Introduction
2 Related Work
3 Obtaining Rules From Partial Decision Trees
4 Experimental Results
5 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — PART Rule Induction Algorithm
algorithm
The PART algorithm induces an ordered list of rules (a decision list) from a training dataset by combining the separate-and-conquer strategy with decision tree construction, without requiring a global post-pruning optimization stage.
Input: A dataset $D$ of training instances labeled with classes
Output: An ordered decision list $L$ of rules
$L \leftarrow$ empty list
while $D$ is not empty do
     $T \leftarrow$ BuildPartialTree( $D$ )
     $leaf \leftarrow$ FindExpandedLeafWithMaxCoverage( $T$ )
     $R \leftarrow$ ExtractRuleFromLeafPath( $leaf$ )
    Append $R$ to $L$
     $D_{covered} \leftarrow$ instances in $D$ that satisfy the antecedent of $R$
     $D \leftarrow D \setminus D_{covered}$
    Discard tree $T$
end while
return $L$
Unlike traditional separate-and-conquer learners that build rules condition-by-condition and prune them immediately, PART builds a partial decision tree for the current set of instances, extracts the single rule corresponding to the leaf with the greatest coverage among all fully expanded paths, and discards the remaining tree structure. Covered training instances are removed, and the process repeats on the remaining data until all instances are covered.
Knowl 2 — Partial Decision Tree Construction and Pruning
algorithm
A partial decision tree is a decision tree containing branches that lead to undefined (unexpanded) subtrees. Tree construction integrates recursive expansion with subtree replacement pruning so that tree generation terminates as soon as an unpruned subtree is encountered, avoiding the need to build a full decision tree.
Procedure ExpandSubset( $S$ ):
Input: A subset of training examples $S$
Output: A node representing a leaf or a partial subtree
Choose an attribute split on $S$ using the C4.5 gain ratio criterion to divide $S$ into subsets $S_1, \dots, S_m$
Compute the average class entropy for each subset $S_i$
Sort the subsets $S_1, \dots, S_m$ in ascending order of average class entropy
all_leaves $\leftarrow$ true
for each subset $S_i$ in sorted order do
    Expand $S_i$ into child node $C_i$ by calling ExpandSubset( $S_i$ )
    if $C_i$ is not a leaf then
        all_leaves $\leftarrow$ false
        break
    end if
end for
if all_leaves is true then
    subtree_error $\leftarrow$ estimated pessimistic error of the subtree over children $\{C_1, \dots, C_m\}$
    node_error $\leftarrow$ estimated pessimistic error if $S$ is replaced by a single leaf
    if subtree_error $\ge$ node_error then
        Undo the split and return a single leaf node for $S$
    end if
end if
return the internal node with expanded children and any unexpanded subsets left undefined
Subsets with the lowest average entropy are expanded first because low-entropy subsets are more likely to terminate in small subtrees and generate general rules. If an internal node has all its children expanded into leaves, subtree replacement pruning is evaluated using C4.5's pessimistic error heuristic. If pruning is not accepted for a node, tree generation backtracks and stops expanding remaining sibling branches, leaving them undefined.
Knowl 3 — Hasty Generalization in Rule Induction
definition
Hasty generalization is a failure mode inherent in standard separate-and-conquer rule learning algorithms that prune individual rules incrementally before exploring alternative subtrees. When pruning occurs (using either reduced error pruning or pessimistic pruning) in the presence of noise, deleting conditions from a candidate rule increases its apparent coverage and may lower its estimated error rate on the pruning set compared to keeping more specific conditions.

Because the covering heuristic permanently removes all instances covered by the generalized rule, the rule learner is precluded from discovering smaller, highly accurate sub-concepts that were swallowed by the premature generalization. Generating rules from partial decision trees avoids hasty generalization because pruning decisions (subtree replacements) are evaluated only after all immediate child subtrees have been expanded and their implications in the data are known.
Knowl 4 — Rule Selection and Missing Value Handling in PART
model/method
PART applies specific heuristics for rule selection from partial trees and for handling missing attribute values:
1. Rule Selection: Once a partial tree is built, every expanded leaf represents a possible candidate rule. PART selects the leaf that covers the greatest number of training instances, producing the most general rule available from the stable subtree. Selecting the leaf with the lowest estimated error rate (via C4.5's Bernoulli heuristic) does not yield superior rule set accuracy.
2. Missing Values During Training: When splitting a node during tree construction, an instance with a missing value on the test attribute is split fractionally across all child branches. The fractional weight assigned to branch $j$ is proportional to the number of training instances with known values traversing branch $j$ , normalized by the total number of training instances with known values at that node.
3. Missing Values During Classification: During evaluation, an unseen instance with total weight $w = 1.0$ is passed down the ordered decision list. If an antecedent condition involves a missing attribute, the instance is fractionally split across the rule and the remainder of the list. The portion matching the rule antecedent receives the rule's predicted class distribution, and the residual weight is passed to subsequent rules. When the unassigned weight reaches zero, the class probability distributions are combined according to their fractional weights.
Knowl 5 — Computational Complexity of Partial Decision Tree Induction
theoretical result
Let $n$ be the number of training examples, $a$ the number of attributes, and $k$ the total number of rules in the resulting decision list.

Building a decision tree takes $O(a n \log n)$ time. Consequently, generating a rule set of size $k$ by repeatedly constructing partial decision trees has a worst-case computational complexity of:

$O(k \cdot a n \log n)$

Under the assumption that the size $k$ of the learned theory remains constant as $n$ grows, the overall time complexity is $O(a n \log n)$ .

In the worst-case scenario where the number of rules $k$ grows linearly with the number of training instances ( $k = O(n)$ ), the runtime of PART is bounded by $O(a n^2 \log n)$ . This contrasts with C4.5rules, whose global optimization phase exhibits $O(n^3)$ runtime on noisy datasets, and RIPPER, which scales as $O(a n \log^2 n)$ .

Knowl 6 — Pairwise Accuracy Comparison Across UCI Benchmark Datasets

data/table

The performance of PART was evaluated against C4.5 (Revision 8), C5.0, and RIPPER across 34 standard datasets from the UCI Machine Learning Repository using 10 runs of 10-fold cross-validation. Pairwise statistical significance was determined using a two-sided paired $t$ -test at the $p = 0.01$ significance level.

In this matrix, each entry $(i, j)$ represents the number of datasets on which the algorithm in column $j$ is statistically significantly more accurate ( $p < 0.01$ ) than the algorithm in row $i$ :

PART outperforms C4.5 on 9 datasets, while C4.5 outperforms PART on 6 (sign test $p = 0.30$ , indicating comparable overall performance).
PART outperforms C5.0 on 6 datasets, while C5.0 outperforms PART on 10 (sign test $p = 0.23$ ).
PART outperforms RIPPER on 14 datasets, while RIPPER outperforms PART on 6 (sign test $p = 0.06$ , providing strong evidence of PART's superior accuracy over RIPPER).

Knowl 7 — Rule Set Compactness of PART Compared to C4.5, C5.0, and RIPPER
empirical result
In cross-validation experiments across 34 UCI datasets, the compactness of rule sets produced by PART was compared to those produced by C4.5, C5.0, and RIPPER:
- Compared to C4.5 and C5.0, PART produces smaller rule sets on 18 datasets and larger rule sets on 16 datasets, showing that PART generates models of comparable size to full tree-to-rule systems with global optimization.
- RIPPER consistently produces smaller rule sets than PART across all evaluated datasets, reflecting RIPPER's aggressive minimum description length (MDL) stopping heuristic at the cost of classification accuracy.
Knowl 8 — PART Scalability Under Class Noise on Pathological Datasets
empirical result
On an artificial Boolean domain defined by the target concept $(ab + bcd + defg)$ with 12 irrelevant binary attributes and uniformly distributed examples (evaluated at sample sizes from 625 up to 40,000 instances):
1. In the noise-free case, PART exhibits near-linear empirical scaling with CPU time growing proportional to $n \log n$ .
2. In the presence of 20% class noise, where C4.5rules exhibits cubic runtime scaling ( $O(n^3)$ ) due to its rule subset selection and simulated annealing post-processing stages, PART exhibits strictly subquadratic scaling bounded by $O(n^2)$ .

Coverage note — None was omitted. All key algorithmic components, theoretical complexity bounds, inductive bias explanations (hasty generalization), and empirical benchmark results (accuracy, model size, noise scalability) have been captured.

References

1.Cohen, W. W. (1995). Fast effective rule induction. In Proceedings of the 12th International Conference on Machine Learning (pp. 115–123). Morgan Kaufmann.
2.F¨urnkranz, J. (1996). Separate-and-conquer rule learning. Technical Report TR-96-25, Austrian Research Institute for Artificial Intelligence, Vienna. [ftp://ftp.ai.univie.ac.at/papers/oefai-tr-96-25.ps.Z].
3.F¨urnkranz, J. (1997). Pruning algorithms for rule learning. Machine Learning, 27(2), 139–171.
4.F¨urnkranz, J. & Widmer, G. (1994). Incremental reduced error pruning. In Proceedings of the 11th International Conference on Machine Learning (pp. 70–77). Morgan Kaufmann.
5.Holte, R. (1993). Very simple classification rules perform well on most commonly used datasets. Machine Learning, 11, 63–91.
6.Merz, C. J. & Murphy, P. M. (1996). UCI Repository of Machine Learning Data-Bases. Irvine, CA: University of California, Department of Information and Computer Science. [http://www.ics.uci.edu/∼mlearn/MLRepository.html].
7.Michalski, R. S. (1969). On the quasi-minimal solution of the covering problem. In Proceedings of the 5th International Symposium on Information Processing (FCIP-69), Vol. A3 (Switching Circuits) (pp. 125–128). Bled, Yugoslavia.
8.Pagallo, G. & Haussler, D. (1990). Boolean feature discovery in empirical learning. Machine Learning, 5(1), 71–99.
9.Quinlan, J. R. (1987a). Generating production rules from decision trees. In Proceedings of the 10th International Joint Conference on Artificial Intelligence (pp. 304–307). Morgan Kaufmann.
10.Quinlan, J. R. (1987b). Simplifying decision trees. International Journal of Man-Machine Studies, 27, 221–234.
11.Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann.
12.Rissanen, J. (1978). Modelling by shortest data description. Automatica, 14, 465–471.
13.Rivest, R. L. (1987). Learning decision lists. Machine Learning, 2, 229–246.

Citation

MLA

Frank, E., and I. H. Witten. “Generating Accurate Rule Sets Without Global Optimization”. Research Commons (University of Waikato), 1998, pp. 144–51, https://hdl.handle.net/10289/16861.

APA

Frank, E., & Witten, I. H. (1998). Generating Accurate Rule Sets Without Global Optimization. Research Commons (University of Waikato), 144–151. https://hdl.handle.net/10289/16861

Chicago

Frank, E., and I. H. Witten. 1998. “Generating Accurate Rule Sets Without Global Optimization”. Research Commons (University of Waikato), 144–51. https://hdl.handle.net/10289/16861.

Harvard

Frank, E. and Witten, I.H. (1998) “Generating Accurate Rule Sets Without Global Optimization”, Research Commons (University of Waikato), pp. 144–151. Available at: https://hdl.handle.net/10289/16861.

Vancouver

1. Frank E, Witten IH (1998) Generating Accurate Rule Sets Without Global Optimization. Research Commons (University of Waikato) 144–151

BibTeX

@article{frank1998generating,
  title = {Generating Accurate Rule Sets Without Global Optimization},
  author = {Frank, Eibe and Witten, Ian H.},
  year = {1998},
  journal = {Research Commons (University of Waikato)},
  pages = {144-151},
  url = {https://hdl.handle.net/10289/16861}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Method	PART	C4.5	C5.0	RIPPER
PART	–	6	10	6
C4.5	9	–	9	4
C5.0	6	5	–	4
RIPPER	14	10	12	–

Generating Accurate Rule Sets Without Global Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — PART Rule Induction Algorithm

Knowl 2 — Partial Decision Tree Construction and Pruning

Knowl 3 — Hasty Generalization in Rule Induction

Knowl 4 — Rule Selection and Missing Value Handling in PART

Knowl 5 — Computational Complexity of Partial Decision Tree Induction

Knowl 6 — Pairwise Accuracy Comparison Across UCI Benchmark Datasets

Knowl 7 — Rule Set Compactness of PART Compared to C4.5, C5.0, and RIPPER

Knowl 8 — PART Scalability Under Class Noise on Pathological Datasets

References

Citation

BibTeX

Access the Paper