Penalised impurity

Topic: Classification trees · more questions on this topic
‹ Affine invariance A tempting wrong turn ›

Tree 1 has two leaves with weighted impurities 0.30 and 0.20. Tree 2 has five leaves with impurities 0.05, 0.05, 0.10, 0.00, and 0.10. Compute the penalised impurity for \alpha=0.15 and for \alpha=0.05, and say which tree is preferred in each case.

Worked answer (click to show)

Tree 1 has leaf-impurity sum 0.30+0.20=0.50, plus 2\alpha. Tree 2 has leaf-impurity sum 0.05+0.05+0.10+0+0.10=0.30, plus 5\alpha. At \alpha=0.15, tree 1 scores 0.80 and tree 2 scores 1.05, so tree 1 is preferred. At \alpha=0.05, tree 1 scores 0.60 and tree 2 scores 0.55, so tree 2 is preferred. A larger penalty favours the smaller tree. The break-even solves 0.50+2\alpha=0.30+5\alpha, so \alpha=0.20/3=0.0667.