A Multiclass Tree Construction Workshop

Introduction

A classification tree turns predictor values into a sequence of branches, ending at a terminal node. For a multiclass outcome, each node can contain observations from several classes. A useful tree construction therefore requires more than choosing a branch: at each node, we need to measure how the split changes the mix of classes and keep track of the class probabilities in the leaves.

This workshop uses the Gini impurity to compare candidate binary splits. The calculations apply to hypothetical labeled data, with each training observation assigned to exactly one class and one child of each proposed split. They are aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.

Definition: At a node \(t\), let \(n_{tk}\) be the number of training observations in class \(k\), and let \(n_t=\sum_{k=1}^{K}n_{tk}\) be the total number at the node. The empirical class proportion is \(\hat p_{tk}=n_{tk}/n_t\). The node's class-probability vector is \((\hat p_{t1},\ldots,\hat p_{tK})\). Its Gini impurity is \(G(t)=1-\sum_{k=1}^{K}\hat p_{tk}^{\,2}\).

The class-probability vector describes the observed class mix at that node. A predicted class is a separate summary: it is usually the class with the largest proportion, subject to any prespecified tie rule. A node containing observations from more than one class is not necessarily a mistake; it simply has a non-pure empirical class mix.

How a Split Is Scored

A candidate binary split divides the observations at node \(t\) into a left child \(L\) and a right child \(R\). Write \(n_L\) and \(n_R\) for their sizes, so \(n_t=n_L+n_R\). The weighted child impurity gives each child a weight equal to its share of the parent observations. The Gini gain is the parent impurity minus this weighted average.

G_{\mathrm{children}}=\frac{n_L}{n_t}G(L)+\frac{n_R}{n_t}G(R), \qquad \Delta G=G(t)-G_{\mathrm{children}}.

A larger positive gain means the candidate makes a greater reduction in Gini impurity at this node. The weighting matters: a child containing many observations contributes more to the post-split impurity than a small child. A split with zero gain leaves the weighted class mix no purer than before; a negative gain increases the weighted impurity and would not be preferred by a rule that maximizes Gini gain.

Justification: The parent proportions are the weighted averages of the child proportions: \(\hat p_{tk}=(n_L/n_t)\hat p_{Lk}+(n_R/n_t)\hat p_{Rk}\). More generally, for children \(j\) with weights \(w_j=n_j/n_t\), this gives

G(t)-\sum_j w_jG(j) = \sum_j w_j\sum_{k=1}^{K}(\hat p_{jk}-\hat p_{tk})^2.

To verify the identity, substitute \(G=1-\sum_k\hat p_k^2\) into the left side. The constant terms cancel, leaving \(\sum_jw_j\sum_k\hat p_{jk}^2-\sum_k\hat p_{tk}^2\). Expanding the right side gives that same expression because \(\sum_jw_j\hat p_{jk}=\hat p_{tk}\) and \(\sum_jw_j=1\). Every squared term on the right is nonnegative. Thus the gain is nonnegative, and it is zero exactly when each child has the same class proportions as the parent for every class with positive weight. A split gains impurity reduction by creating children whose class mixes differ from the parent mix.

Worked Example: Choose Between Two Root Splits

A hypothetical equipment-monitoring study classifies service events as Routine, Urgent, or Critical. At the root, the class counts are \((6,4,2)\), in that order. Compare two candidate binary splits using Gini gain, and report the terminal-node probability vectors for the better split.

Method and root impurity. The root has \(n_t=12\). Its class-probability vector is \((6/12,4/12,2/12)=(1/2,1/3,1/6)\), so

G(t)=1-\left(\frac{6^2+4^2+2^2}{12^2}\right) =1-\frac{56}{144} =\frac{11}{18}.

Candidate A. The left and right child counts are \((4,1,1)\) and \((2,3,1)\), each of size 6. Their impurities are

G(L)=1-\frac{4^2+1^2+1^2}{6^2}=\frac{1}{2}, \qquad G(R)=1-\frac{2^2+3^2+1^2}{6^2}=\frac{11}{18}.

The weighted child impurity is \((6/12)(1/2)+(6/12)(11/18)=5/9\). Therefore Candidate A has gain \(11/18-5/9=1/18\), approximately \(0.0556\).

Candidate B. The children have counts \((5,3,0)\), of size 8, and \((1,1,2)\), of size 4. Their impurities are

G(L)=1-\frac{5^2+3^2+0^2}{8^2}=\frac{15}{32}, \qquad G(R)=1-\frac{1^2+1^2+2^2}{4^2}=\frac{5}{8}.

The weighted child impurity is

\frac{8}{12}\cdot\frac{15}{32}+\frac{4}{12}\cdot\frac{5}{8} =\frac{5}{16}+\frac{5}{24} =\frac{25}{48}.

Candidate B has gain \(11/18-25/48=13/144\), approximately \(0.0903\). Since \(13/144>1/18=8/144\), choose Candidate B if the decision rule is to maximize Gini gain among these candidates. The terminal probability vectors are \((5/8,3/8,0)\) and \((1/4,1/4,1/2)\). Their predicted classes are Routine on the left and Critical on the right.

Common mistake avoided: Comparing the two child impurities without weighting them by child size ignores that Candidate B's left child has twice as many observations as its right child.

Constructing Successive Levels

At a later node, the split comparison uses the class counts and impurity at that node—not the counts or impurity of the original root. Each child probability vector is calculated from the observations that reach that child. The next example follows this procedure through two levels, with the selected candidate splits treated as the available growth choices.

Worked Example: Build a Three-Class Tree One Node at a Time

A hypothetical claims-triage exercise labels cases as Standard, Review, or Escalated. The root counts are \((8,5,3)\), for a total of 16. A proposed first split creates nodes \(L=(6,2,0)\) and \(R=(2,3,3)\). At \(L\), the proposed children are \((5,1,0)\) and \((1,1,0)\). At \(R\), they are \((1,3,2)\) and \((1,0,1)\). Calculate each gain and give the four terminal probability vectors.

Root split. The root impurity is

G(t)=1-\frac{8^2+5^2+3^2}{16^2} =1-\frac{98}{256} =\frac{79}{128}.

At \(L\), the impurity is \(1-(6^2+2^2)/8^2=3/8\). At \(R\), it is \(1-(2^2+3^2+3^2)/8^2=21/32\). Both children have size 8, so the weighted child impurity is

\frac{8}{16}\cdot\frac{3}{8}+\frac{8}{16}\cdot\frac{21}{32} =\frac{33}{64}.

The root gain is \(79/128-33/64=13/128\), approximately \(0.1016\).

Split at \(L\). The parent impurity is \(3/8\). The child \((5,1,0)\) has impurity \(1-(25+1)/36=5/18\); the child \((1,1,0)\) has impurity \(1-(1+1)/4=1/2\). Their sizes are 6 and 2, so

G_{\mathrm{children}}=\frac{6}{8}\cdot\frac{5}{18}+\frac{2}{8}\cdot\frac{1}{2} =\frac{1}{3}, \qquad \Delta G=\frac{3}{8}-\frac{1}{3}=\frac{1}{24}.

Split at \(R\). The parent impurity is \(21/32\). The child \((1,3,2)\) has impurity \(1-(1+9+4)/36=11/18\), while \((1,0,1)\) has impurity \(1-(1+1)/4=1/2\). Their sizes are 6 and 2:

G_{\mathrm{children}}=\frac{6}{8}\cdot\frac{11}{18}+\frac{2}{8}\cdot\frac{1}{2} =\frac{7}{12}, \qquad \Delta G=\frac{21}{32}-\frac{7}{12}=\frac{7}{96}.

Terminal vectors. Divide each terminal count by its own node size. In the order Standard, Review, Escalated, the four vectors are \((5/6,1/6,0)\), \((1/2,1/2,0)\), \((1/6,1/2,1/3)\), and \((1/2,0,1/2)\). The second and fourth vectors have ties for their largest component. A predicted label in either tied leaf requires a prespecified tie rule; the probability vector itself does not resolve the tie.

Check. Each vector sums to 1, and the two child count vectors at each split sum class by class to their parent: \((5,1,0)+(1,1,0)=(6,2,0)\) and \((1,3,2)+(1,0,1)=(2,3,3)\).

Unequal Child Sizes and Probability Vectors

The next comparison highlights a frequent source of incorrect split rankings. The children in the first candidate have different sizes, so their impurities must not receive equal weight. The count vectors also provide a direct check that both candidate splits partition the same parent observations.

Worked Example: Compare Unequal-Size Splits

A hypothetical monitoring system sorts 15 alerts into Low, Moderate, and Severe classes. The root counts are \((7,5,3)\). Candidate A splits into \((4,1,0)\) and \((3,4,3)\); Candidate B splits into \((5,2,2)\) and \((2,3,1)\). Compare Gini gains, select a candidate, and report its leaf probability vectors.

Root and Candidate A. The root impurity is

G(t)=1-\frac{7^2+5^2+3^2}{15^2}=\frac{142}{225}.

Candidate A's child impurities are \(1-(16+1)/25=8/25\) and \(1-(9+16+9)/100=33/50\). Their sizes are 5 and 10. Thus

G_{\mathrm{children,A}} =\frac{5}{15}\cdot\frac{8}{25}+\frac{10}{15}\cdot\frac{33}{50} =\frac{41}{75}, \qquad \Delta G_A=\frac{142}{225}-\frac{41}{75} =\frac{19}{225}.

The terminal vectors under Candidate A are \((4/5,1/5,0)\) and \((3/10,4/10,3/10)\). Their components are the proportions of Low, Moderate, and Severe alerts within each leaf.

Candidate B. Its child impurities are \(1-(25+4+4)/81=16/27\) and \(1-(4+9+1)/36=11/18\). The child sizes are 9 and 6:

G_{\mathrm{children,B}} =\frac{9}{15}\cdot\frac{16}{27}+\frac{6}{15}\cdot\frac{11}{18} =\frac{3}{5}, \qquad \Delta G_B=\frac{142}{225}-\frac{3}{5} =\frac{7}{225}.

Since \(19/225>7/225\), Candidate A has the larger Gini gain. As a check on the inputs, Candidate A's child counts sum to \((7,5,3)\), and Candidate B's child counts also sum to \((7,5,3)\).

Common mistake avoided: Giving Candidate A's two children equal weight would produce \(((8/25)+(33/50))/2=49/100\), rather than the correct weighted impurity \(41/75\). A comparison based on that unweighted value does not measure the impurity across the parent observations.

Reading the Result Carefully

The split with the greatest calculated gain is the preferred candidate under the stated criterion and candidate set. This calculation alone does not specify which candidate splits are eligible, when growth should stop, or whether a built tree should later be simplified. Those are separate decisions. Here, the main task is to calculate each candidate's gain correctly and to interpret the class mix of the resulting leaves.

For an actuarial application, a terminal vector can communicate uncertainty that a single predicted label conceals. For example, a hypothetical claims leaf with probabilities \((0.45,0.40,0.15)\) for three risk categories has a largest component of only \(0.45\); describing it only by its predicted category would omit the substantial representation of the other classes. The vector is empirical for the observations reaching that leaf. It is not, by itself, a guarantee that future observations will have exactly those probabilities.

Key takeaway: For each node, use its own class counts to calculate proportions and Gini impurity. For each binary split, weight child impurities by child size before subtracting from the parent impurity. At each terminal node, report the class proportions in a consistent class order; state a tie rule separately if a predicted label is needed.

Check Your Understanding

Work each problem using the class order stated. Round decimal gains to four decimal places where requested.

A node has class counts \((5,3,2)\) for classes A, B, and C. What is its class-probability vector? (Answer: \((0.5000,0.3000,0.2000)\))
A node has counts \((4,2,2)\) in three classes. Calculate its Gini impurity. (Answer: \(5/8=0.6250\))
A parent has counts \((5,3,2)\) and splits into \((4,1,1)\) and \((1,2,1)\). Calculate the weighted child impurity and Gini gain. (Answer: weighted impurity \(0.5500\); gain \(0.0700\))
A parent has counts \((5,4,3)\). Candidate A gives children \((4,1,1)\) and \((1,3,2)\); Candidate B gives \((3,3,0)\) and \((2,1,3)\). Compare the gains. (Answer: both gains are \(7/72\), approximately \(0.0972\); the candidates tie on Gini gain.)
A root with counts \((5,3,2)\) splits into \(L=(4,1,0)\) and \(R=(1,2,2)\). The \(R\) node then splits into \((1,1,0)\) and \((0,1,2)\). Give the three terminal probability vectors and the Gini gain at \(R\). (Answer: vectors \((4/5,1/5,0)\), \((1/2,1/2,0)\), and \((0,1/3,2/3)\); gain at \(R\) is \(13/75\), approximately \(0.1733\).)

What You'll Learn