21
$\begingroup$

I am studying classification and regression trees, and one of the measures for the split location is the GINI score.

Now I am used to determining best split location when the log of the likelihood ratio of the same data between two distributions is zero, meaning the likelihood of membership is equally likely.

My intuition says that there must be a connection of some sort, that GINI has to have a good foundation in a mathematical theory of information (Shannon) but I don't understand GINI well enough to derive the relationship myself.

Questions:

  • What is the "first principles" derivation of GINI impurity score as a measure for splitting?
  • How does the GINI score relate to log of likelihood ratio or other information-theoretic fundamentals (Shannon Entropy, pdf, and cross entropy are part of those)?

References:

Shannon's entropy is described as:

$$ H \left(x \right) = \Sigma_{i} P\left(x_{i} \right)\log_{b} P\left(x_{i} \right) $$

Extending this to the multivariate case we get:

$$ H \left(X,Y \right)= \Sigma_{x}\Sigma_{y} P\left(x,y \right)\log_{b} P\left(x,y \right) $$

Conditional Entropy is defined as follows:

\begin{align} H \left(X|Y \right) &= \Sigma_{y} p\left(x,y \right)\log_{b} \frac {p\left(x \right)} {p\left(x,y \right)} \newline &\text{or,} \newline H \left(X|Y \right) &= H \left(X,Y \right) - H \left(Y \right) \end{align}

The log of the ratio of likelihoods is used for abrupt change detection and is derived using these. (I don't have derivation in front of me.)

GINI Impurity:

  • The general form of GINI impurity is $ I = \sum_{i=1}^m f_{i} \cdot \left( 1-f_{i}\right) $

Thoughts:

  • Splitting is done on a measure of impurity. High "purity" is likely the same as low entropy. The approach is likely related to entropy minimization.
  • It is likely that the assumed basis distribution is uniform, or possibly with hand-waving, Gaussian. They are likely making a mixture of distributions.
  • I wonder if the Shewhart chart derivation can apply here?
  • The GINI Impurity looks like the integral of the probability density function for a binomial distribution with 2 trials, and one success. $P(x=k)= \begin{pmatrix} 2\\ 1\end{pmatrix} p \left( 1-p \right) $

(additional)

  • The form is also consistent with a Beta-binomial distribution which is a conjugate prior for a Hypergeometric distribution. Hypergeometric tests are often used to determine which samples are over or under represented in a sample. There is also a relationship to Fisher's exact test, whatever that is (note to self, go learn more about this).

Edit: I suspect that there is a form of the GINI that works very well with digital logic and/or rb-trees. I hope to explore this in a class project this fall.

$\endgroup$
  • 1
    $\begingroup$ Is it problematic if I answer my own question? $\endgroup$ – EngrStudent - Reinstate Monica Apr 28 '14 at 1:40
  • 1
    $\begingroup$ No, not at all. If you have come up with what you think is a reasonable answer, fire away. $\endgroup$ – gung - Reinstate Monica Apr 28 '14 at 1:56
  • $\begingroup$ @EngrStudent. good question but the first link you provide in the references section relates to the Gini coefficient, which has nothing to do with the Gini measure used in CART $\endgroup$ – Antoine Jul 18 '15 at 15:51
  • $\begingroup$ Concerning Gini index I just posted a simple interpretation: stats.stackexchange.com/questions/308885/… $\endgroup$ – Picaud Vincent Oct 24 '17 at 20:33
11
$\begingroup$

I will use the same notation I used here: Mathematics behind classification and regression trees

Gini Gain and Information Gain ($IG$) are both impurity based splitting criteria. The only difference is in the impurity function $I$:

  1. $\textit{Gini}: \mathit{Gini}(E) = 1 - \sum_{j=1}^{c}p_j^2$
  2. $\textit{Entropy}: H(E) = -\sum_{j=1}^{c}p_j\log p_j$

They actually are particular values of a more general entropy measure (Tsallis' Entropy) parametrized in $\beta$:

$$H_\beta (E) = \frac{1}{\beta-1} \left( 1 - \sum_{j=1}^{c}p_j^\beta \right) $$

$\textit{Gini}$ is obtained with $\beta = 2$ and $H$ with $\beta \rightarrow 1$.

The log-likelihood, also called $G$-statistic, is a linear transformation of Information Gain:

$$G\text{-statistic} = 2 \cdot |E| \cdot IG$$

Depending on the community (statistics/data mining) people prefer one measure or the the other (Related question here). They might be pretty much equivalent in the decision tree induction process. Log-likelihood might give higher scores to balanced partitions when there are many classes though [Technical Note: Some Properties of Splitting Criteria. Breiman 1996].

Gini Gain can be nicer because it doesn't have logarithms and you can find the closed form for its expected value and variance under random split assumption [Alin Dobra, Johannes Gehrke: Bias Correction in Classification Tree Construction. ICML 2001: 90-97]. It is not as easy for Information Gain (If you are interested, see here).

$\endgroup$
1
$\begingroup$

Good question. Unfortunately I don't have enough reputation yet to upvote or comment, so answering instead!

I'm not very familiar with the ratio test, but it strikes me that it is a formalism used to compare the likelihood of data arising from two (or more) different distributions, whereas the Gini coefficient is a summary statistic of a single distribution.

A useful way to think of the Gini coefficient (IMO) is as the area under the Lorenz curve (related to the cdf).

It may be possible to equate Shannon's entropy with Gini using the definition given in the OP for entropy:

$H = \Sigma_{i} P\left(x_{i} \right)\log_{b} P\left(x_{i} \right)$

and the definition of Gini:

$G = 1 - \frac{1}{\mu}\Sigma_i P(x_i)(S_{i-1} + S_i)$, where

$S_i = \Sigma_{j=1}^i P(x_i)x_i$ (i.e. the cumulative mean up to $x_i$).

It doesn't look like an easy task though!

$\endgroup$
  • $\begingroup$ A log likelihood ratio is operated on the same data. One of the distributions can be the same general form as the other, but its parameters were fitted to data when some other criterion was true. For instance, you could have one distribution whose parameters describe healthy production process variation (not necessarily Gaussian) and another that is fit to current production process values, and operate both on current production process values compare the log-likelihood ratio to a threshold value indicating possibility of excursion. It can the actual to be compared with the ideal. $\endgroup$ – EngrStudent - Reinstate Monica Apr 25 '14 at 14:50

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.