A mushroom forager sorts her finds into baskets and wants a number that says how mixed a basket is. Two measures are common. If p₁, p₂, … are the proportions of the different labels in the basket:
- the Gini impurity is
1 - Σ pᵢ², the chance that two finds drawn at random (with replacement) have different labels; - the entropy is
-Σ pᵢ · log₂(pᵢ), in bits.
Write impurity(labels) that returns the tuple (gini, entropy) for the list labels. An empty basket has (0.0, 0.0).
Examples
Input: labels = ["cep", "cep", "cep", "cep"]
Output: (0.0, 0.0)
Input: labels = ["cep", "chanterelle", "cep", "chanterelle"]
Output: (0.5, 1.0)
Input: labels = ["cep", "cep", "cep", "morel"]
Output: (0.375, 0.8112781244591328)
Explanation: the proportions are 3/4 and 1/4: 1 - (9/16 + 1/16) = 0.375, and
-(0.75·log₂ 0.75 + 0.25·log₂ 0.25) = 0.8113.
Constraints
0 <= len(labels) <= 10**5; labels are strings or integers- floats are compared with a tolerance of
1e-6
Goals
- Compute the class proportions of a list of labels
- Compute the Gini impurity and the entropy in bits from those proportions
- Recognise that both are 0 for a pure group and largest for an even mix