Decision Tree: a decision tree consists of Nodes, Edges & Leaves

In Decision Tree Learning, a new example is classified by submitting it to a series of tests that determine the class label of the example. These tests are organized in a hierarchical structure called a decision tree.

The training examples are used for choosing appropriate tests in the decision tree. Typically, a tree is built from top to bottom, where tests that maximize the information gain about the classification are selected first.

To classify a sample:

1. Start at the root
2. Perform the test
3. Follow the edge corresponding to outcome
4. Go to 2 unless leaf
5. Predict that outcome associated with the leaf

Rule induction

• Decision rules can be generated from a decision tree
• Each path from the root of the tree to a leave is a rule that classifies a set of examples
• It is also possible to generate a set of rules without creating a decision tree
• These algorithms learn the rules sequentially and not all at once like in a decision tree
• Some of these algorithm can even learn first order logic rules
• The key point of these methods is how to learn the best rule given a set of examples
• One possibility is to use the idea from decision trees and search in the space of conjunctions
• We start with the empty rule and each step we select the best new conjunction for the rule using an heuristic (eg. entropy) and a greedy strategy (eg. keep the best)
• To avoid local optima, a more exhaustive search can be performed, for example using beam search and storing the k best rules The majority class of the examples selected is assigned as the rule Prediction
• There are also other formalisms of rules that can be used
  • Decision tables
  • Decision lists
  • Ripple down rules
  • Defaukt Rules

Application: A sample Task