0
$\begingroup$

I asked this in a reply to an answer to another of my questions; but I think this merits its own question since I couldn't find an answer, and it's a pretty interesting question on its own.

Suppose we construct a decision tree for classification based on the Gini impurity function. Can we prove that the weighted average of the Gini impurities of children nodes is always <= the Gini impurity of the parent node?

More precisely:

Let G(S)=sum_i p_i(1-p_i), where S is a finite nonempty set of points with known classification, p_i is the proportion of points in S with classification i, and the sum is taken over all classes. In the special case of binary classification, this simplifies to G(S)=2p(1-p), where p is the proportion of one of the classes.

Assume that every point x has a feature f. Denote the value of this feature by x(f). A splitting of S is defined as a partition of S into {S_left, S_right}, where S_left = {x in S: x(f) <= c} and S_right = {x in S: x(f) > c}. We require both of these sets to be nonempty.

A splitting is called good if

|S_left|/|S| G(S_left) + |S_right|/|S| G(S_right) <= G(S)

  1. Must there always exist at least one good splitting?
  2. Must all splittings be good?
$\endgroup$
0
$\begingroup$

I think I've got a proof. Any node can be identified with the vector (p_1,...,p_k) that gives the proportion of points with each classification. The Gini impurity function can then be viewed as a function from R^k to R. The weighted average of the proportions of points in S_left and S_right belonging to a certain class is equal to the proportion of points in S belonging to that class. Thus the inequality is just stating that the Gini impurity function is concave. But that is true; its matrix of second derivatives is just a diagonal matrix whose diagonal entries are all -1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.