Machine Learning II: Decision Trees and Information Theory (ID3)

Overview of Decision Trees

• Learning Decision Trees: Inductive learning is a form of supervised learning that involves learning from examples. It is considered one of the simplest yet most successful forms of learning algorithms.

• Functionality: A decision tree takes a set of properties (attributes) as input and provides a classification output (e.g., a "YES/NO" decision).

• Structure of the Tree:

  • Non-leaf nodes: Represent an attribute test.

  • Links/Branches: Labeled with possible values associated with the attribute.

  • Leaf nodes: Represent the final classification or decision (e.g., Yes or No).

• Expressiveness: Decision trees are fully expressive within the class of propositional languages.

• Goal: The aim of decision tree learning is to find a small tree that is consistent with the training examples provided by (recursively) choosing the "most significant" attribute as the root of the (sub)tree.

Case Study: Restaurant Waiting Decision

• Goal Predicate: The target variable is WillWait (Yes/No).

• Attributes Used for Decision Making:

  1. Alternate: Whether there is a suitable alternative restaurant nearby.

  2. Bar: Whether the restaurant has a comfortable bar area to wait in.

  3. Fr/Sat: True on Fridays and Saturdays.

  4. Hungry: Whether the patrons are currently hungry.

  5. Patrons: How many people are in the restaurant (Values: None, Some, Full).

  6. Price: The price range of the restaurant (Values: $, $`, `$).

  7. Raining: Whether it is raining outside.

  8. Reservation: Whether a reservation was made.

  9. Type: Kind of food served (French, Italian, Thai, Burger).

  10. WaitEstimate: The host's estimated wait time (0-10, 10-30, 30-60, >60 minutes).

• Complexity Management: While a dataset may include 10 attributes, a learned tree might be substantially simpler than the "true" tree if a more complex hypothesis isn't justified by a small amount of data. For instance, a model might only use 4 attributes (Patrons, Hungry, Type, and Fri/Sat) instead of all 10 to classify 12 examples.

Information Theory and the ID3 Algorithm

• ID3 (Iterative Dichotomiser 3): An algorithm used to choose the best attribute for splitting the data at each node using information theory.

• Entropy (Information Content): A formula used to calculate the homogeneity (purity) of a sample.

  • A completely homogeneous sample (all same class) has an entropy of $0$.

  • An equally divided sample (e.g., half positive, half negative) has an entropy of $1$.

  • Entropy Formula (for a set with $p$ positive and $n$ negative examples):       $Entropy = - \frac{p}{p+n} \log_2 \left(\frac{p}{p+n}\right) - \frac{n}{p+n} \log_2 \left(\frac{n}{p+n}\right)$

• Performing Logarithm Base 2: Since most calculators use Log base 10, the conversion formula is:     $\log_b(x) = \frac{\log_a(x)}{\log_a(b)}$     $\log_2(x) = \frac{\log_{10}(x)}{\log_{10}(2)}$

• Information Gain (IG): This is the measurement of the decrease in entropy after a dataset is split on an attribute.

  • First, calculate the entropy of the total dataset.

  • Split the dataset on different attributes.

  • Calculate the entropy for each resulting branch.

  • Add branch entropies proportionally to get the total entropy for the split.

  • Subtract the split entropy from the original entropy to find the gain.

  • Decision Criterion: The attribute that yields the largest Information Gain is chosen for the decision node.

• Recursion: If a branch has an entropy of 0, it becomes a leaf node. If not, the ID3 algorithm is run recursively on that branch until all data is classified.

Case Study: The Simpsons Classification

• Objective: Classify characters as Male (M) or Female (F).

• Initial Dataset (9 Samples):

  • Homer: Hair 0", Weight 250, Age 36, Class M

  • Marge: Hair 10", Weight 150, Age 34, Class F

  • Bart: Hair 2", Weight 90, Age 10, Class M

  • Lisa: Hair 6", Weight 78, Age 8, Class F

  • Maggie: Hair 4", Weight 20, Age 1, Class F

  • Abe: Hair 1", Weight 170, Age 70, Class M

  • Selma: Hair 8", Weight 160, Age 41, Class F

  • Otto: Hair 10", Weight 180, Age 38, Class M

  • Krusty: Hair 6", Weight 200, Age 45, Class M

• Step 1: Calculate Total System Entropy:

  • $p = 4$ (Females), $n = 5$ (Males), Total = 9.

  • $Entropy(4F, 5M) = - \left(\frac{4}{9}\right) \log_2 \left(\frac{4}{9}\right) - \left(\frac{5}{9}\right) \log_2 \left(\frac{5}{9}\right) = 0.9911$

• Step 2: Evaluate Attribute Splits:

  • Hair Length Split (Threshold: $5$ inches):

    • $\le 5"$: 1 Female, 3 Males. $Entropy = 0.8113$

    • > 5": 3 Females, 2 Males. $Entropy = 0.9710$

    • $IG = 0.9911 - \left(\frac{4}{9} \times 0.8113 + \frac{5}{9} \times 0.9710\right) = 0.0911$

  • Weight Split (Threshold: $160$ kg):

    • $\le 160$: 4 Females, 1 Male. $Entropy = 0.7219$

    • > 160: 0 Females, 4 Males. $Entropy = 0$

    • $IG = 0.9911 - \left(\frac{5}{9} \times 0.7219 + \frac{4}{9} \times 0\right) = 0.5900$

  • Age Split (Threshold: $40$):

    • $\le 40$: 3 Females, 3 Males. $Entropy = 1$

    • > 40: 1 Female, 2 Males. $Entropy = 0.9183$

    • $IG = 0.9911 - \left(\frac{6}{9} \times 1 + \frac{3}{9} \times 0.9183\right) = 0.0183$

• Step 3: Root Node Selection:

  • Since Weight has the highest IG ($0.5900$), it is chosen as the root of the decision tree.

• Step 4: Sub-Tree Development (Weighted branch $\le 160$):

  • The subset contains: Marge, Bart, Lisa, Maggie, Selma (4F, 1M). Previous $Entropy = 0.71$.

  • Testing Age < 30:

    • < 30: 2F, 1M. $Entropy = 0.85$

    • $\ge 30$: 2F, 0M. $Entropy = 0$

    • $IG = 0.2$

  • Testing Hair Length \le 2":

    • $\le 2"$: 0F, 1M (Bart). $Entropy = 0$

    • > 2": 4F, 0M. $Entropy = 0$

    • $IG = 0.71 - (0) = 0.71$

  • Result: Hair Length is chosen as the next attribute because its IG ($0.71$) is higher than Age ($0.2$).

Final Decision Model and Rules

• Final Decision Tree Strategy:

  1. Test: Is Weight greater than $160$?

     • If No ($\le 160$): Test: Is Hair Length less than or equal to $2$?

       • If Yes: Classify as Male.

       • If No: Classify as Female.

     • If Yes (> 160): Classify as Male.

• Rule Conversion: Decisions can be converted into standard conditional logic:

  • \text{If Weight > 160, then Male}

  • $\text{Elseif Hair Length } \le 2\text{, then Male}$

  • $\text{Else Female}$

• Prediction Practice:

  • Comic Guy (Hair 8", Weight 290, Age 38): Classified as Male because Weight is > 160.