Entropy, Information Gain & Gini Impurity

Entropy (H)

Shannon's entropy is defined for a system with N possible states as follows:

S=−∑i=1Npilog2pi,

where pi

is the probability of finding the system in the i-th state. This is a very important concept used in physics, information theory, and other areas. Entropy can be described as the degree of chaos in the system. The higher the entropy, the less ordered the system and vice versa.

Information Gain (IG)

 The information gain (IG) for a split based on the variable Q is defined as

IG(Q)=SO−∑i=1qNiNSi,

 where q -

is the number of groups after the split, Ni is number of objects from the sample in which variable Q is equal to the i-th value.

Entropy allows us to formalize partitions in a decision tree. But this is only one heuristic. There exists others

Gini Uncertainty (Impurity):  G=1−∑k(pk)2 

Maximizing this criterion can be interpreted as the maximization of the number of pairs of objects of the same class that are in the same subtree (not to be confused with the Gini index).

Misclassification error: E=1−maxkpk

             

In practice, misclassification error is almost never used, and Gini uncertainty and information gain work similarly

For binary classification, entropy and Gini uncertainty take the following form:
S=−p+log2p+−p−log2p−=−p+log2p+−(1−p+)log2(1−p+);
G=1−p2+−p2−=1−p2+−(1−p+)2=2p+(1−p+).

where (p+
is the probability of an object having a label +).

In practice, misclassification error is almost never used, and Gini uncertainty and information gain work similarlyIn practice, misclassification error is almost never used, and Gini uncertainty and information gain work similarlywdfewifgweofjewofIn practice, misclassification error is almost never used, and Gini uncertainty and information gain work similarly