Rule Learning in a Nutshell
This chapter gives a brief overview of inductive rule learning and may therefore serve as a guide through the rest of the book. Later chapters will expand upon the material presented here and discuss advanced approaches, whereas this chapter only presents
- PDF / 1,431,688 Bytes
- 37 Pages / 439.36 x 666.15 pts Page_size
- 10 Downloads / 203 Views
Rule Learning in a Nutshell
This chapter gives a brief overview of inductive rule learning and may therefore serve as a guide through the rest of the book. Later chapters will expand upon the material presented here and discuss advanced approaches, whereas this chapter only presents the core concepts. The chapter describes search heuristics and rule quality criteria, the basic covering algorithm, illustrates classification rule learning on simple propositional learning problems, shows how to use the learned rules for classifying new instances, and introduces the basic evaluation criteria and methodology for rule-set evaluation. After defining the learning task in Sect. 2.1, we start with discussing data (Sect. 2.2) and rule representation (Sect. 2.3) for the standard propositional rule learning framework, in which training examples are represented in a single table, and the outputs are if–then rules. Section 2.4 outlines the rule construction process, followed by a more detailed description of its parts: the induction of individual rules is presented as a search problem in Sect. 2.5, and the learning of rule sets in Sect. 2.6. One of the classical rule learning algorithms, CN2, is described in more detail in Sect. 2.7. Section 2.8 shows how to use the induced rule sets for the classification of new instances, and the subsequent Sect. 2.9 discusses evaluation of the classification quality of the induced rule sets and presents cross-validation as a means for evaluating the predictive accuracy of rules. Finally, Sect. 2.10 gives a brief historical account of some influential rule learning systems.
This chapter is partly based on (Flach & Lavraˇc, 2003).
J. F¨urnkranz et al., Foundations of Rule Learning, Cognitive Technologies, DOI 10.1007/978-3-540-75197-7 2, © Springer-Verlag Berlin Heidelberg 2012
19
20
2 Rule Learning in a Nutshell
Given: – a data description language, defining the form of data, – a hypothesis description language, defining the form of rules, – a coverage function Covered(r, e), defining whether rule r covers example e, – a class attribute C, and – a set of training examples E , instances for which the class labels are known, described in the data description language. Find: a hypothesis in the form of a rule set R formulated in the hypothesis description language which is – complete, i.e., it covers all the examples, and – consistent, i.e., it predicts the correct class for all the examples.
Fig. 2.1 Definition of the classification rule learning task
2.1 Problem Definition Informally, we can define the problem of learning classification rules as follows: Given a set of training examples, find a set of classification rules that can be used for prediction or classification of new instances.
Note that we distinguish between the terms examples and instances. Both are usually described by attribute values. Examples refer to instances labeled by a class label, whereas instances themselves bear no class label. An instance is covered by a rule if its description satisfies the rule conditio
Data Loading...
