Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

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

Henrik BoströmContact Information and Lars AskerContact Information

(3)  Dept. of Computer and Systems Sciences, Stockholm University and Royal Institute of Technology, Electrum 230, 164 40 Kista, Sweden
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.

Contact Information Henrik Boström
Email: henke@dsv.su.se

Contact Information Lars Asker
Email: asker@dsv.su.se
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)