Preporato

Gini impurity of a node

Easy7 min11 hidden tests

A loan-approval tree is choosing its next split. At each node, a box that holds some of the training applicants, it asks how mixed their outcomes are. Write gini_impurity(labels) that returns the Gini impurity of the labels in one node: 0.0 when every applicant has the same outcome, and higher the more mixed they are.

Tap an applicant to change the outcome

Gini = 1 − Σ share²
AapproveDdenyRrefer

9 approve, 3 deny. Gini = 1 − (0.75² + 0.25²) = 0.375: draw an applicant, put them back, draw again, and the outcomes differ 37.5% of the time.

9 approve, 3 deny. Gini impurity 0.375.

Examples

Three approvals and one denial

gini_impurity(["approve", "deny", "approve", "approve"])

returns 0.375

A pure node has impurity 0.0

gini_impurity([0, 0, 0])

returns 0

Requirements

  • labels is a list or 1-D array of class labels, ints or strings. It may be empty.
  • Return a float: 1 minus the sum, over the classes present, of each class's share squared.
  • An empty node has impurity 0.0.
The idea behind it

A decision tree splits the data again and again, and each split should leave purer groups behind. Gini impurity measures how mixed a group is. If you pick two applicants from the node at random, with replacement, it is the chance they have different outcomes. For class shares p_1 to p_c the formula is 1 - (p_1^2 + ... + p_c^2). A pure node scores 0. Two classes split evenly score 0.5, the maximum for two classes, and c classes split evenly score 1 - 1/c. CART, the algorithm behind scikit-learn's DecisionTreeClassifier, uses Gini by default because it needs no logarithm and ranks splits almost the same way entropy does.

pythonCtrl+Enter runs
import numpy as np

def gini_impurity(labels):
"""Gini impurity of the labels in one tree node.

labels: list or 1-D array of n class labels (ints or strings), n >= 0
Returns 1 - sum over classes of (count / n) ** 2, as a float.
An empty node returns 0.0.
"""
raise NotImplementedError

Stuck? Reveal one rung at a time

Worked solution

Give it a real try first. Then read the solution and why each line is there.