An empirical evaluation of beam search and pruning in BEXA

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