1. [Decision Tree] You will build a decision tree to determine whether or not a child…
- User
- [Decision Tree] You will build a decision tree to determine whether or not a child goes out to play. Day Weather Temperature Humanity Wind Play 1 Sunny Hot High Weak No 2 Cloudy Hot High Weak Yes 3 Sunny Mild Normal Strong Yes 4 Cloudy Mild High Strong Yes 5 Rainy Mild High Strong No 6 Rainy Cool Normal Strong No 7 Rainy Mild High Weak Yes 8 Sunny Hot High Strong No 9 Cloudy Hot Normal Weak Yes 10 Rainy Mild High Strong No 1.1 Calculate the information gain for each feature and select the feature with the highest infor- mation gain to serve as the root of the decision tree. Draw a root and split the ten training data points into two groups based on the value of the selected root feature. k∗ = arg max k I(Xk; Y ) = H(Y ) − H(Y |Xk) 1.2 Repeat the two procedures: (1) selecting a feature and (2) splitting the data points until the leaf nodes of the tree achieve complete purity. 1.3 [Extra Points: 10 points] Try pruning your tree. You need to find a subtree (T ′) minimizing the criterion C(T ′) below. Based on the criterion computation, do you think we need to prune the tree found in 4.2? C(T ′) = T ′ X τ =1 Q(τ ) + λ · |num of leaves in T ′| Q(τ ) = entropy of a leaf in T ′ (measure of impurity
- Assistant
Problem 1: Building a Decision Tree to Determine Play
You are tasked with constructing a decision tree based on the provided dataset to decide whether a child goes out to play. The dataset includes features such as Weather, Temperature, Humidity, Wind, and the target variable Play (Yes/No).
1.1 Calculate Information Gain for Each Feature and Select the Root
Step 1: Calculate the Entropy of the Entire Dataset
Entropy ( H(Y) ) measures the impurity or uncertainty in the dataset regarding the target variable Play.
[ H(Y) = - \sum_{i=1}^{c} P(y_i) \log_2 P(y_i) ]
Where:
- ( c ) is the number of classes (Yes, No)
- ( P(y_i) ) is the probability of class ( y_i )
Given:
- Total instances: 10
- Play = Yes: 5
- Play = No: 5
[ H(Y) = - \left( \frac{5}{10} \log_2 \frac{5}{10} + \frac{5}{10} \log_2 \frac{5}{10} \right) = 1 \text{ bit} ]
Step 2: Calculate Information Gain (IG) for Each Feature
Information Gain helps in selecting the feature that best separates the data into target classes.
[ IG(X) = H(Y) - H(Y|X) ]
Where ( H(Y|X) ) is the conditional entropy of Y given feature X.
Let's compute ( IG ) for each feature:
A. Weather
Possible Values: Sunny, Cloudy, Rainy
| Weather | Yes | No | Total | Entropy ( H(Y|Weather) ) | |---------|-----|----|-------|----------------------------| | Sunny | 1 | 2 | 3 | 0.9183 | | Cloudy | 3 | 0 | 3 | 0.0000 | | Rainy | 1 | 3 | 4 | 0.8113 |
[ H(Y|Weather) = \frac{3}{10} \times 0.9183 + \frac{3}{10} \times 0 + \frac{4}{10} \times 0.8113 = 0.6000 \text{ bits} ]
[ IG(Weather) = 1 - 0.6 = 0.4 \text{ bits} ]
B. Temperature
Possible Values: Hot, Mild, Cool
| Temperature | Yes | No | Total | Entropy ( H(Y|Temperature) ) | |-------------|-----|----|-------|---------------------------------| | Hot | 2 | 2 | 4 | 1.0000 | | Mild | 3 | 2 | 5 | 0.97095 | | Cool | 0 | 1 | 1 | 0.0000 |
[ H(Y|Temperature) = \frac{4}{10} \times 1 + \frac{5}{10} \times 0.97095 + \frac{1}{10} \times 0 = 0.8855 \text{ bits} ]
[ IG(Temperature) = 1 - 0.8855 = 0.1145 \text{ bits} ]
C. Humidity
Possible Values: High, Normal
| Humidity | Yes | No | Total | Entropy ( H(Y|Humidity) ) | |----------|-----|----|-------|------------------------------| | High | 3 | 4 | 7 | 0.9852 | | Normal | 2 | 1 | 3 | 0.9183 |
[ H(Y|Humidity) = \frac{7}{10} \times 0.9852 + \frac{3}{10} \times 0.9183 = 0.9651 \text{ bits} ]
[ IG(Humidity) = 1 - 0.9651 = 0.0349 \text{ bits} ]
D. Wind
Possible Values: Weak, Strong
| Wind | Yes | No | Total | Entropy ( H(Y|Wind) ) | |--------|-----|----|-------|--------------------------| | Weak | 3 | 1 | 4 | 0.8113 | | Strong | 2 | 4 | 6 | 0.9183 |
[ H(Y|Wind) = \frac{4}{10} \times 0.8113 + \frac{6}{10} \times 0.9183 = 0.8754 \text{ bits} ]
[ IG(Wind) = 1 - 0.8754 = 0.1246 \text{ bits} ]
Summary of Information Gains:
- Weather: 0.4 bits
- Wind: 0.1246 bits
- Temperature: 0.1145 bits
- Humidity: 0.0349 bits
Conclusion: The feature Weather has the highest Information Gain and is selected as the root node of the decision tree.
1.2 Recursive Splitting Until Leaf Nodes Achieve Complete Purity
We now recursively apply the process to each branch created by splitting on the root feature.
A. Split on Weather
Weather / | \ Sunny Cloudy Rainy1. Weather = Sunny
Instance Weather Temperature Humidity Wind Play 1 Sunny Hot High Weak No 3 Sunny Mild Normal Strong Yes 8 Sunny Hot High Strong No - Play Distribution: 1 Yes, 2 No
Action: Since the subset is not pure, select the best feature based on Information Gain.
Available Features: Temperature, Humidity, Wind
Calculating Information Gain for Sunny Subset:
- Entropy of Sunny Subset:
[ H(Y|Sunny) = - \left( \frac{1}{3} \log_2 \frac{1}{3} + \frac{2}{3} \log_2 \frac{2}{3} \right) \approx 0.9183 \text{ bits} ]
-
Information Gain for Remaining Features:
-
Temperature:
Temperature Yes No Total Entropy Hot 0 2 2 0 Mild 1 0 1 0 [ H(Y|Temperature) = \frac{2}{3} \times 0 + \frac{1}{3} \times 0 = 0 \text{ bits} ]
[ IG(Temperature) = 0.9183 - 0 = 0.9183 \text{ bits} ]
-
Humidity:
Humidity Yes No Total Entropy High 0 2 2 0 Normal 1 0 1 0 [ H(Y|Humidity) = \frac{2}{3} \times 0 + \frac{1}{3} \times 0 = 0 \text{ bits} ]
[ IG(Humidity) = 0.9183 - 0 = 0.9183 \text{ bits} ]
-
Wind:
Wind Yes No Total Entropy Weak 0 1 1 0 Strong 1 1 2 1 [ H(Y|Wind) = \frac{1}{3} \times 0 + \frac{2}{3} \times 1 \approx 0.6667 \text{ bits} ]
[ IG(Wind) = 0.9183 - 0.6667 \approx 0.2516 \text{ bits} ]
-
Conclusion: Both Temperature and Humidity have the highest Information Gain (0.9183 bits). You can choose either; for this example, we'll select Temperature.
Subtree for Weather = Sunny:
Temperature / \ Hot Mild / \ No Yes- Hot: Predict No
- Mild: Predict Yes
2. Weather = Cloudy
Instance Weather Temperature Humidity Wind Play 2 Cloudy Hot High Weak Yes 4 Cloudy Mild High Strong Yes 9 Cloudy Hot Normal Weak Yes - Play Distribution: 3 Yes, 0 No
Action: The subset is pure (all Yes). No further splitting is required.
Subtree for Weather = Cloudy:
Yes
3. Weather = Rainy
Instance Weather Temperature Humidity Wind Play 5 Rainy Mild High Strong No 6 Rainy Cool Normal Strong No 7 Rainy Mild High Weak Yes 10 Rainy Mild High Strong No - Play Distribution: 1 Yes, 3 No
Action: Since the subset is not pure, select the best feature based on Information Gain.
Available Features: Temperature, Humidity, Wind
Calculating Information Gain for Rainy Subset:
- Entropy of Rainy Subset:
[ H(Y|Rainy) = - \left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4} \right) \approx 0.8113 \text{ bits} ]
-
Information Gain for Remaining Features:
-
Temperature:
Temperature Yes No Total Entropy Mild 1 2 3 0.9183 Cool 0 1 1 0 [ H(Y|Temperature) = \frac{3}{4} \times 0.9183 + \frac{1}{4} \times 0 = 0.6887 \text{ bits} ]
[ IG(Temperature) = 0.8113 - 0.6887 \approx 0.1226 \text{ bits} ]
-
Humidity:
Humidity Yes No Total Entropy High 1 3 4 0.8113 Normal 0 1 1 0 [ H(Y|Humidity) = \frac{4}{4} \times 0.8113 + \frac{0}{4} \times 0 = 0.8113 \text{ bits} ]
[ IG(Humidity) = 0.8113 - 0.8113 = 0 \text{ bits} ]
-
Wind:
Wind Yes No Total Entropy Weak 1 0 1 0 Strong 0 3 3 0 [ H(Y|Wind) = \frac{1}{4} \times 0 + \frac{3}{4} \times 0 = 0 \text{ bits} ]
[ IG(Wind) = 0.8113 - 0 = 0.8113 \text{ bits} ]
-
Conclusion: Wind has the highest Information Gain (0.8113 bits) for the Rainy subset.
Subtree for Weather = Rainy:
Wind / \ Weak Strong / \ Yes No- Weak: Predict Yes
- Strong: Predict No
Final Decision Tree:
Weather / | \ Sunny Cloudy Rainy / | \ Temperature Yes Wind / \ / \ Hot Mild Weak Strong / \ | | No Yes Yes No
1.3 Pruning the Decision Tree
Objective: Simplify the tree to prevent overfitting by removing branches that provide little to no additional information.
Pruning Criterion:
[ C(T') = \sum_{\tau=1}^{T'} Q(\tau) + \lambda \times \text{(number of leaves in } T' \text{)} ]
Where:
- ( Q(\tau) ) is the entropy of leaf ( \tau )
- ( \lambda ) is a regularization parameter balancing entropy and tree complexity
Assessment:
-
Current Tree Leaves:
- Weather = Sunny:
- Temperature = Hot → No (Entropy = 0)
- Temperature = Mild → Yes (Entropy = 0)
- Weather = Cloudy → Yes (Entropy = 0)
- Weather = Rainy:
- Wind = Weak → Yes (Entropy = 0)
- Wind = Strong → No (Entropy = 0)
- Weather = Sunny:
-
Total Entropy ( Q(T') ): 0 (All leaves are pure)
-
Number of Leaves: 5
Pruning Impact:
-
Pruning Decision:
- Removing any branch would lead to misclassification since all leaves currently classify perfectly.
- For example, replacing the "Sunny" subtree with a single node predicting "No" would incorrectly classify Instance3 (Sunny, Mild, Normal, Strong, Yes) as "No".
-
Criterion Computation:
- Current ( C(T') = 0 + \lambda \times 5 = 5\lambda )
- Pruned Tree would have higher entropy ( Q(T') > 0 ) and fewer leaves, but at the cost of accuracy.
Conclusion:
Pruning the current tree would introduce classification errors as all leaves are already pure. Therefore, pruning is not necessary for this tree.
Final Decision Tree Without Pruning:
Weather / | \ Sunny Cloudy Rainy / | \ Temperature Yes Wind / \ / \ Hot Mild Weak Strong / \ | | No Yes Yes NoThis tree perfectly classifies all training instances with complete purity at each leaf node.