Concept - Information Gain (TWM)

Information Gain (Text & Web Mining)

Mutual information = information gain (02 Pre-processing s.81):

$I(X,Y)=E(X)-E(X|Y)=E(Y)-E(Y|X),E(X|Y)={\sum }_{i}p(Y=Y_i)E(X|Y=Y_i)$

Intuition: how much knowing $Y$ reduces uncertainty about $X$ (and vice versa). High IG = more entropy removed, so select high-IG features (s.81, s.87).

Worked example: Humidity (s.82-86)

Weather data, 9 Yes / 5 No: $E=0.94$. Humidity=Normal: 6 Yes, 1 No, $H_L=0.592$. Humidity=High: 3 Yes, 4 No, $H_R=0.985$.

$IG(Humidity)=0.94-\frac{7}{14}(0.592)-\frac{7}{14}(0.985)=0.1515$

Added context

Exercise on s.87 (not solved on slides): IG(Outlook)=0.247, IG(Windy)=0.048, IG(Temperature)=0.029; Outlook is the best feature. Working in 02 Pre-processing - Chunk 03 (s.61-90).

For terms in text mining (s.88)

IG of a term = expected reduction in entropy from partitioning the documents by presence/absence of the term:

$IG(t)=-{\sum }_{i=1}^{m}p(c_i)\log p(c_i)+p(t){\sum }_{i}p(c_i|t)\log p(c_i|t)+p(\bar{t}){\sum }_{i}p(c_i|\bar{t})\log p(c_i|\bar{t})$

$m$ = number of classes, $p(c_i)$ = share of docs in class $c_i$, $p(t)$ / $p(\bar{t})$ = share of docs containing / not containing $t$, $p(c_i|t)$, $p(c_i|\bar{t})$ = class probabilities given presence / absence.

Machine Learning course version: ML: Information Gain.

Related

Concept - Entropy (TWM) | Concept - Feature Selection | Concept - Dictionary Reduction

Appears in

• 02 Pre-processing - Chunk 03 (s.61-90)