A hyper-heuristic for descriptive rule induction

Abstract

Rule induction from examples is a machine learning technique that finds rules of the form condition → class, where condition and class are logic expressions of the form variable1, = value1, ∧ variable2 = value2 ∧... ∧ variablek = valuek. There are in general three approaches to rule induction: exhaustive search, divide-and-conquer and separate-and-conquer (or its extension as weighted covering). Among them, the third approach, according to different rule search heuristics, can avoid the problem of producing many redundant rules (limitation of the first approach) or non-overlapping rules (limitation of the second approach). In this chapter, we propose a hyper-heuristic to construct rule search heuristics for weighted covering algorithms that allows producing rules of desired generality. The hyper-heuristic is based on a PN-space, a new ROC-like tool for analysis, evaluation, and visualization of rules. Well-known rule search heuristics such as entropy, Laplacian, weight relative accuracy, and others are equivalent to ones proposed by the hyper-heuristic. Moreover, it can present new non-linear rule search heuristics, some are especially appropriate for description tasks. The non-linear rule search heuristics have been experimentally compared with others on the generality of rules induced from UCI datasets and used to learn regulatory rules from microarray data. Copyright © 2007, Idea Group Inc.