Decision Trees

Used to decide what category an element, represented by a vector of attribute values, belongs to.
The attribute values must be discrete

Example - "Will the movie be a success?"

Film CountryOfOrigin BigStar Genre Success/Failure
--------------------------------------------------
1    USA             yes     scifi    Success
2    USA             no      comedy   Failure
3    USA             yes     comedy   Success
4    Europe          no      comedy   Success
5    Europe          yes     scifi    Failure
6    Europe          yes     romance  Failure
7    Australia       yes     comedy   Failure
8    Brazil          no      scifi    Failure
9    Europe          yes     comedy   Success
10   USA             yes     comedy   Success

Decision tree learning
- Supervised learning of trees, based on training data
- The goal is to build a tree that is as shallow as possible, to make quickest classifications (e.g., the movie example has depth two although three attributes are available).
```
                         CountryOfOrigin
                       /        |       \
                   USA/   Europe|        \Other
            _________/          |         \
     BigStar                  Genre     Failure
      /  \                  /   |   \
  yes/    \no        comedy/ romance \scifi
    /      \              /     |     \
Success  Failure    Success   Failure  Failure
```
- Best known is ID3
  - Builds tree top down, selecting attribute that provides the most information gain.
- Information gain
  - Information gain is the difference between the entropy before and after a decision.
  - Entropy = ∑_C∈Classes ( -p(C) * log₂(p(C)) )
    p(C) is the proportion of examples in class C
  - Entropy is minimal (0.0) when all examples are in one class, maximal (1.0) they are distributed evenly over all classes.
  - The entropy of a set of sets is the weighted sum of the entropies of the sets.
Example
- The initial entropy is 1.0, because there are 5 successes and 5 failures.
  - Information gain for CountryOfOrigin:
    Entropy(USA) = -3/4 * log2(3/4) -1/4 * log2(1/4) = 0.8113
    Entropy(Europe) = 1.0 (2 of each)
    Entropy(Other) = 0.0 (2 Failures)
    Entropy(CountryOfOrigin) = 4/10 * 0.8113 + 4/10 * 1.0 + 2/10 * 0.0 = 0.7245
    InformationGain(CountryOfOrigin) = 1.0 - 0.7245 = 0.2755
  - Information gain for BigStar:
    Entropy(yes) = -4/7 * log2(4/7) -3/7 * log2(3/7) = 0.9852
    Entropy(no) = -1/3 * log2(1/3) -2/3 * log2(2/3) = 0.9183
    Entropy(BigStar) = 7/10 * 0.9852 + 3/10 * 0.9183 = 0.9651
    InformationGain(BigStar) = 1.0 - 0.9651 = 0.0349
  - Information gain for Genre: Entropy(scifi) = -1/3 * log2(1/3) -2/3 * log2(2/3) = 0.9183
    Entropy(comedy) = -4/6 * log2(4/6) -1/6 * log2(1/6) = 0.9183
    Entropy(romance) = -0/1 * log2(0/1) -1/1 * log2(1/1) = 0.0
    Entropy(Genre) = 3/10 * 0.9183 + 6/10 * 0.9183 + 1/10 * 0.0 = 0.8265
    Information(Genre) = 1.0 - 0.8265 = 0.1735
  - Best initial split is CountryOfOrigin with information gain 0.2755
- For USA films
  - Information gain for BigStar:
    Entropy(yes) = 0.0 (all Success)
    Entropy(no) = 0.0 (all Failure)
    Entropy(USA:BigStar) = 0.0
    InformationGain(USA:BigStar) = 0.8113 - 0.0 = 0.8113
  - Information gain for Genre:
    Entropy(scifi) = 0.0 (all Success)
    Entropy(comedy) = -2/3 * log2(2/3) -1/3 * log2(1/3) = 0.9183
    Entropy(romance) = NA
    Entropy(USA:Genre) = 1/4 * 0.0 + 3/4 * 0.9183 + 0.00 * NA = 0.6887
    InformationGain(USA:Genre) = 0.8113 - 0.6887 = 0.1226
  - For USA films, best split is BigStar, and no entropy is left
  For Europe films, best split is Genre, and no entropy is left
- For Other films, no entropy is left
Once the decision tree is built new data can be classified (quickly).

Decision Trees

Exam Style Questions