Gini Impurity

easyFREEDecision TreesMachine Learning 1

Compute the Gini impurity of a set of labels.

Gini impurity measures how often a randomly chosen element would be incorrectly classified:

$Gini = 1 - \sum_{k=1}^{K} p_k^2$

where $p_k$ is the proportion of class $k$ in the dataset.

A pure node (all same class) has Gini = 0. Maximum impurity for binary classification is 0.5.

Return the Gini impurity rounded to 4 decimal places.

Example

Input

labels = [1, 1, 0, 0, 0]

Output

0.48

Reasoning

labels is a list of 5 class labels: two belong to class 1 and three to class 0. Only how often each class appears matters, not the order or the label values themselves.
The class proportions are $p_0 = \frac{3}{5} = 0.6$ and $p_1 = \frac{2}{5} = 0.4$ ; they always add up to 1.
Squaring each gives $p_0^2 = 0.36$ and $p_1^2 = 0.16$ . Their sum, $0.52$ , is the probability that two elements drawn at random (with replacement) share a class.
So $Gini = 1 - 0.52 = 0.48$ , the chance that the two draws disagree, which is how often a random element gets mislabelled by a random guess from the same distribution.
The output 0.48 is a single float, already exact at 4 decimal places.
Notice that it sits just below the binary maximum of $0.5$ , reached only at a perfect $50/50$ split of two classes. A pure list (every label the same) gives 0.0, and an empty list also returns 0.0 by convention.

Constraints

labels is a list of class labels (integers or strings)
Return a float rounded to 4 decimal places
Handle empty lists (return 0.0)

Learn this in

Decision TreesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

The Gini impurity is a measure used in Decision Trees to determine the best split for a node. It calculates the probability of incorrectly classifying a randomly chosen element from the dataset. The concept of Gini impurity is based on the idea that a pure node (all elements belong to the same class) has zero impurity, while a node with equal proportions of all classes has maximum impurity. In the context of binary classification, the maximum impurity is 0.5, which occurs when both classes have an equal proportion of elements.

The formula for calculating Gini impurity is $Gini = 1 - \sum_{k=1}^{K} p_k^2$ , where $p_k$ is the proportion of class $k$ in the dataset. This formula represents the probability of incorrectly classifying a randomly chosen element. The proportion of each class ( $p_k$ ) is calculated by dividing the number of elements in each class by the total number of elements in the dataset.

Understanding the concept of probability and proportions is essential to calculate the Gini impurity. The Gini impurity is a measure of the uncertainty or impurity of a node in a Decision Tree. It helps in determining the best split for a node by choosing the attribute that results in the lowest Gini impurity.

Algorithm/Approach

The general approach to solving this problem involves calculating the proportion of each class in the dataset and then using these proportions to calculate the Gini impurity. This can be achieved by iterating over the dataset, counting the occurrences of each class, and then using these counts to calculate the proportions.

Step-by-Step Strategy

To implement the solution, follow these steps:

Count the occurrences of each class in the dataset.
Calculate the proportion of each class by dividing the count of each class by the total number of elements.
Calculate the Gini impurity using the formula $Gini = 1 - \sum_{k=1}^{K} p_k^2$ .
Round the result to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the proportions are calculated correctly by dividing the count of each class by the total number of elements.
Use the correct formula for calculating the Gini impurity.
Round the result to the correct number of decimal places.

Time & Space Complexity

The time complexity of this solution is O(n), where n is the number of elements in the dataset, since we need to iterate over the dataset to count the occurrences of each class. The space complexity is O(k), where k is the number of classes, since we need to store the counts of each class.

solution.py

Python 3.13

Test results