00:00:00

Description

Editorial

Recursive Classification Tree Builder

HARD30 pts

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

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:

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
Calculate information gain for each attribute:
- For 'Outlook': Provides the highest information gain
- For 'Wind': Provides lower information gain
'Outlook' is selected as the root (highest gain)
Branch 'Overcast': All 2 examples have 'Yes' → Pure leaf node 'Yes'
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')
Branch 'Rain': 2 'Yes' and 1 'No' → Not pure, split on 'Wind'
- 'Strong': 1 'No' → Leaf 'No'
- 'Weak': 2 'Yes' → Leaf 'Yes'

Example

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:

Initial entropy: 2 'Positive', 2 'Negative' → H(S) = -1/2·log₂(1/2) - 1/2·log₂(1/2) = 1.0 (maximum entropy)
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
'Color' selected as root (IG = 1.0)
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

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.

Accepted0/0·0% Acceptance

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

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

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"

Loading problem...

101

00:00:00

Description

Editorial

Recursive Classification Tree Builder

HARD30 pts

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

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:

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
Calculate information gain for each attribute:
- For 'Outlook': Provides the highest information gain
- For 'Wind': Provides lower information gain
'Outlook' is selected as the root (highest gain)
Branch 'Overcast': All 2 examples have 'Yes' → Pure leaf node 'Yes'
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')
Branch 'Rain': 2 'Yes' and 1 'No' → Not pure, split on 'Wind'
- 'Strong': 1 'No' → Leaf 'No'
- 'Weak': 2 'Yes' → Leaf 'Yes'

Example

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:

Initial entropy: 2 'Positive', 2 'Negative' → H(S) = -1/2·log₂(1/2) - 1/2·log₂(1/2) = 1.0 (maximum entropy)
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
'Color' selected as root (IG = 1.0)
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

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.

Accepted0/0·0% Acceptance

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

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

examples =

attributes =

["Outlook","Wind"]

target_attr =

"PlayTennis"

Recursive Classification Tree Builder

Hints

Recursive Classification Tree Builder

Hints