An empirical evaluation of beam search and pruning in BEXA
Hendrik Theron, Ian Cloete · 2002
BEXA is a covering algorithm whose specialization model generalizes those of CN2 and members of Michalski's AQ family (1986) such as AQ15. All of these algorithms employ a time-consuming beam search to construct concept descriptions. It is shown that BEXA, using a beam search, rarely generates a better quality width of one. Three pruning strategies are also evaluated for BEXA, namely CN2's significance test, a novel stop-growth test, and Quinlan's post-pruning scheme for production rules (J. Quinlan, 1986). The stop-growth test produced better results than CN2's significance test for a beamwidth of one, while both schemes produced the best results for the same number of test databases when performing a beam search. Post-pruning produced better results than a stop-growth or significance test for a beam search, but the stop-growth test yielded similar results than post-pruning for a beamwidth of one.