Recursive Classification Tree Builder

Hard

A classification tree is a powerful hierarchical structure used in machine learning to make predictions by recursively partitioning data based on feature values. At each internal node, the tree selects the most informative attribute to split the data, creating branches that lead to either further decision nodes or terminal leaf nodes containing class predictions. The construction of an optimal classification tree relies on information theory concepts, specifically entropy and information gain. Entropy measures the impurity or uncertainty in a dataset—a set where all examples belong to the same class has zero entropy (perfectly pure), while a set with equally distributed classes has maximum entropy (maximum uncertainty). Entropy Formula: For a set S with class proportions p₁, p₂, ..., pₖ: $$H(S) = -\sum_{i=1}^{k} p_i \log_2(p_i)$$ Note: When p = 0, the term is defined as 0. Information Gain: The information gain of splitting on attribute A measures the reduction in entropy: $$IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$ where Sᵥ is the subset of S for which attribute A has value v. Tree Construction Algorithm: If all examples have the same target class, return that class as a leaf node If no attributes remain for splitting, return the majority class as a leaf node Select the attribute with the highest information gain Create a decision node for this attribute For each possible value of the selected attribute: Create a branch for that value Recursively build a subtree for the subset of examples with that value Remove the used attribute from consideration in that subtree Your Task: Implement a function that constructs a classification tree from a dataset. The function should: Accept a list of example dictionaries (each containing attribute-value pairs including the target) Accept a list of attribute names to consider for splitting (excluding the target) Accept the name of the target attribute Return a nested dictionary representing the tree structure, or a string class label for leaf nodes

Example 1

Input

examples = [
    {'Outlook': 'Sunny', 'Wind': 'Weak', 'PlayTennis': 'No'},
    {'Outlook': 'Overcast', 'Wind': 'Strong', 'PlayTennis': 'Yes'},
    {'Outlook': 'Rain', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Sunny', 'Wind': 'Strong', 'PlayTennis': 'No'},
    {'Outlook': 'Sunny', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Overcast', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Rain', 'Wind': 'Strong', 'PlayTennis': 'No'},
    {'Outlook': 'Rain', 'Wind': 'Weak', 'PlayTennis': 'Yes'}
]
attributes = ['Outlook', 'Wind']
target_attr = 'PlayTennis'

Output

{
    'Outlook': {
        'Overcast': 'Yes',
        'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}},
        'Sunny': {'Wind': {'Strong': 'No', 'Weak': 'No'}}
    }
}

Explanation

**Step-by-step construction:** 1. **Calculate initial entropy:** The target 'PlayTennis' has 5 'Yes' and 3 'No' → H(S) = -5/8·log₂(5/8) - 3/8·log₂(3/8) ≈ 0.954 2. **Calculate information gain for each attribute:** - For 'Outlook': Provides the highest information gain - For 'Wind': Provides lower information gain 3. **'Outlook' is selected as the root** (highest gain) 4. **Branch 'Overcast':** All 2 examples have 'Yes' → Pure leaf node 'Yes' 5. **Branch 'Sunny':** 2 'No' and 1 'Yes' → Not pure, split on 'Wind' - 'Strong': 1 'No' → Leaf 'No' - 'Weak': 1 'Yes', 1 'No' → Majority is 'No' (Leaf 'No') 6. **Branch 'Rain':** 2 'Yes' and 1 'No' → Not pure, split on 'Wind' - 'Strong': 1 'No' → Leaf 'No' - 'Weak': 2 'Yes' → Leaf 'Yes'

Example 2

Input

examples = [
    {'Color': 'Red', 'Size': 'Big', 'Label': 'Positive'},
    {'Color': 'Red', 'Size': 'Small', 'Label': 'Positive'},
    {'Color': 'Blue', 'Size': 'Big', 'Label': 'Negative'},
    {'Color': 'Blue', 'Size': 'Small', 'Label': 'Negative'}
]
attributes = ['Color', 'Size']
target_attr = 'Label'

Output

{
    'Color': {
        'Blue': 'Negative',
        'Red': 'Positive'
    }
}

Explanation

**Analysis:** 1. **Initial entropy:** 2 'Positive', 2 'Negative' → H(S) = -1/2·log₂(1/2) - 1/2·log₂(1/2) = 1.0 (maximum entropy) 2. **Information gain calculation:** - 'Color' splits perfectly: Red→all Positive, Blue→all Negative → IG = 1.0 (perfect split!) - 'Size' provides no discriminative power: Both Big and Small have 1 of each class → IG = 0 3. **'Color' selected as root** (IG = 1.0) 4. **Both branches lead to pure subsets:** - 'Red': 2 'Positive' → Leaf 'Positive' - 'Blue': 2 'Negative' → Leaf 'Negative' The tree achieves perfect classification with just one split because 'Color' perfectly separates the classes.

Example 3

Input

examples = [
    {'Feature': 'A', 'Class': 'Yes'},
    {'Feature': 'B', 'Class': 'Yes'},
    {'Feature': 'C', 'Class': 'Yes'}
]
attributes = ['Feature']
target_attr = 'Class'

Output

'Yes'

Explanation

**Base case activation:** Since all 3 examples belong to the same class 'Yes', the dataset is already pure (entropy = 0). The algorithm immediately returns the class label 'Yes' as a leaf node without any splitting. This demonstrates the first termination condition: when all examples share the same target value, return that value directly without creating a decision node.

Constraints

1 ≤ number of examples ≤ 500
1 ≤ number of attributes ≤ 15
Each attribute can have between 2 and 20 distinct values
Target attribute has between 2 and 10 distinct classes
All examples are complete (no missing attribute values)
Attribute names and values are non-empty strings
When information gains are equal, choose the attribute that comes first in the attributes list
When determining majority class for ties, choose the class that appears first alphabetically

Preparing your editor. You can read the problem while it loads.

Recursive Classification Tree Builder

Hard

A classification tree is a powerful hierarchical structure used in machine learning to make predictions by recursively partitioning data based on feature values. At each internal node, the tree selects the most informative attribute to split the data, creating branches that lead to either further decision nodes or terminal leaf nodes containing class predictions. The construction of an optimal classification tree relies on information theory concepts, specifically entropy and information gain. Entropy measures the impurity or uncertainty in a dataset—a set where all examples belong to the same class has zero entropy (perfectly pure), while a set with equally distributed classes has maximum entropy (maximum uncertainty). Entropy Formula: For a set S with class proportions p₁, p₂, ..., pₖ: $$H(S) = -\sum_{i=1}^{k} p_i \log_2(p_i)$$ Note: When p = 0, the term is defined as 0. Information Gain: The information gain of splitting on attribute A measures the reduction in entropy: $$IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$ where Sᵥ is the subset of S for which attribute A has value v. Tree Construction Algorithm: If all examples have the same target class, return that class as a leaf node If no attributes remain for splitting, return the majority class as a leaf node Select the attribute with the highest information gain Create a decision node for this attribute For each possible value of the selected attribute: Create a branch for that value Recursively build a subtree for the subset of examples with that value Remove the used attribute from consideration in that subtree Your Task: Implement a function that constructs a classification tree from a dataset. The function should: Accept a list of example dictionaries (each containing attribute-value pairs including the target) Accept a list of attribute names to consider for splitting (excluding the target) Accept the name of the target attribute Return a nested dictionary representing the tree structure, or a string class label for leaf nodes

Example 1

Input

examples = [
    {'Outlook': 'Sunny', 'Wind': 'Weak', 'PlayTennis': 'No'},
    {'Outlook': 'Overcast', 'Wind': 'Strong', 'PlayTennis': 'Yes'},
    {'Outlook': 'Rain', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Sunny', 'Wind': 'Strong', 'PlayTennis': 'No'},
    {'Outlook': 'Sunny', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Overcast', 'Wind': 'Weak', 'PlayTennis': 'Yes'},
    {'Outlook': 'Rain', 'Wind': 'Strong', 'PlayTennis': 'No'},
    {'Outlook': 'Rain', 'Wind': 'Weak', 'PlayTennis': 'Yes'}
]
attributes = ['Outlook', 'Wind']
target_attr = 'PlayTennis'

Output

{
    'Outlook': {
        'Overcast': 'Yes',
        'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}},
        'Sunny': {'Wind': {'Strong': 'No', 'Weak': 'No'}}
    }
}

Explanation

Example 2

Input

examples = [
    {'Color': 'Red', 'Size': 'Big', 'Label': 'Positive'},
    {'Color': 'Red', 'Size': 'Small', 'Label': 'Positive'},
    {'Color': 'Blue', 'Size': 'Big', 'Label': 'Negative'},
    {'Color': 'Blue', 'Size': 'Small', 'Label': 'Negative'}
]
attributes = ['Color', 'Size']
target_attr = 'Label'

Output

{
    'Color': {
        'Blue': 'Negative',
        'Red': 'Positive'
    }
}

Explanation

Example 3

Input

examples = [
    {'Feature': 'A', 'Class': 'Yes'},
    {'Feature': 'B', 'Class': 'Yes'},
    {'Feature': 'C', 'Class': 'Yes'}
]
attributes = ['Feature']
target_attr = 'Class'

Output

'Yes'

Explanation

Constraints

1 ≤ number of examples ≤ 500
1 ≤ number of attributes ≤ 15
Each attribute can have between 2 and 20 distinct values
Target attribute has between 2 and 10 distinct classes
All examples are complete (no missing attribute values)
Attribute names and values are non-empty strings
When information gains are equal, choose the attribute that comes first in the attributes list
When determining majority class for ties, choose the class that appears first alphabetically