An Analysis of Rule Learning HeuristicsJohannes Furnkranz, Peter Flach, An Analysis of Rule Learning Heuristics. CSTR-03-002, Department of Computer Science, University of Bristol. February 2003. PDF, 178 Kbytes.
In this paper we analyze the most popular search heuristics for separate-andconquer rule learning algorithms. Our results show that all commonly used heuristics, including accuracy, weighted relative accuracy, entropy, Gini index and information gain, are equivalent to one of two fundamental prototypes: precision, which tries to optimize the area under the ROC curve for unknown costs, and a cost-eighted difference between covered positive and negative examples, which tries to find the optimal point under known or assumed costs. We also show that a straight-forward generalization of the m-heuristic is a means for trading off between these two prototypes.