Current Slide

• Attribute Selection Measure: Information Gain (ID3/C4.5)

• Select the attribute with the highest information gain
• Let pi be the probability that an arbitrary tuple in D belongs to class Ci, estimated by

\[ \frac{ |C_{i,D}|} {|D|}\]

• Expected information (entropy) needed to classify a tuple in D:

\[Info(D)=-\sum_{i=1}^{m} p_{i}log_{2}(p_{i})\]

• Information needed (after using A to split D into v partitions) to classify D:

\[Info_{A}(D)=-\sum_{j=1}^{v} \frac{|D_{j}|}{D}\times Info (D_{j})\]

• Information gained by branching on attribute A

\[Gain(A)=Info(D)-Info_{A}(D)\]