Combining Divide-and-Conquer and
Separate-and-Conquer for Efficient and Effective
Rule Induction

Henrik Bostrm and Lars Asker

Dept. of Computer and Systems Sciences
Stockholm University and Royal Institute of Technology
Electrum 230, 164 40 Kista, Sweden
{henke,asker}@dsv.su.se



Abstract. Divide-and-Conquer (DAC) and Separate-and-Conquer
(SAC) are two strategies for rule induction that have been used extensively. 
When searching for rules DAC is maximally conservative w.r.t.
decisions made during search for previous rules. This results in a very
efficient strategy, which however suffers from difficulties in effectively inducing 
disjunctive concepts due to the replication problem. SAC on the
other hand is maximally liberal in the same respect. This allows for a
larger hypothesis space to be searched, which in many cases avoids the
replication problem but at the cost of lower efficiency. We present a hybrid 
strategy called Reconsider-and-Conquer (RAC), which handles the
replication problem more effectively than DAC by reconsidering some of
the earlier decisions and allows for more efficient induction than SAC
by holding on to some of the decisions. We present experimental results
from propositional, numerical and relational domains demonstrating that
RAC significantly reduces the replication problem from which DAC suffers 
and is several times (up to an order of magnitude) faster than SAC.
References

1.	Blake C., Keogh E. and Merz C.J., UCI Repository of machine learning databases,
Irvine, CA: University of California, Department of Information and Computer
Science (1998)
2.	Bostrm H., Covering vs. Divide-and-Conquer for Top-Down Induction of Logic
Programs, Proc. of the Fourteenth International Joint Conference on Artificial
Intelligence, Morgan Kaufmann (1995) 11941200
3.	Bratko I., Prolog Programming for Artificial Intelligence ,(2nd edition), Addison-
Wesley (1990)
4.	Cohen W. W., Fast Effective Rule Induction, Machine Learning: Proc. of the
12th International Conference, Morgan Kaufmann (1995) 115123
5.	Fayyad U. and Irani K., On the Handling of Continuos-Valued Attributes in
Decision Tree Generation, Machine Learning 8 (1992) 87102
6.	Frank E. and Witten I. H., Generating Accurate Rule Sets Without Global Optimization, 
Machine Learning: Proc. of the Fifteenth International Conference,
Morgan Kaufmann (1998) 144151
7.	Frnkranz J., Separate-and-Conquer Rule Learning, Articial Intelligence Review
13(1) (1999)
8.	Frnkranz J. and Widmer G., Incremental Reduced Error Pruning, Machine
Learning: Proc. of the Eleventh International Conference, Morgan Kaufmann
(1994)
9.	Kohavi R. and Li C-H., Oblivious Decision Trees, Graphs and Top-Down Pruning, 
Proc. of the Fourteenth International Joint Conference on Artificial Intelligence, 
Morgan Kaufmann (1995) 10711077
10.	Lavrac N. and Dzeroski S., Inductive Logic Programming: Techniques and Applications, 
Ellis Horwood (1994)
11.	Lloyd J. W., Foundations of Logic Programming, (2nd edition), Springer-Verlag
(1987)
12.	Martin J. K., An Exact Probability Metric for Decision Tree Splitting and Stopping, 
Machine Learning 28 (1997) 257291
13.	Pagallo G. and Haussler D., Boolean Feature Discovery in Empirical Learning,
Machine Learning 5 (1990) 7199
14.	Quinlan J. R., Induction of Decision Trees, Machine Learning 1 (1986) 81106
15.	Quinlan J. R., Learning Logical Definitions from Relations, Machine Learning 5
(1990) 239266
16.	Quinlan J. R., C4.5: Programs for Machine Learning, Morgan Kaufmann (1993)
