Swati Varma's Notes

Decision Tree Solved Example

Apply decision tree classifier and hence classify following tuple, <Old, Yes, Hardware>

Solution:

Here the output column is Profit with 2 values(Down and Up)

Entropy of the whole Dataset is:

=−510log2⁡(510)−510log2⁡(510)∴Entropy(S)=1= -\frac{5}{10}\log_2\left(\frac{5}{10}\right) -\frac{5}{10}\log_2\left(\frac{5}{10}\right) \therefore Entropy(S)=1

Step 2: Information Gain for Age

For (Age=Old), all 3 records have Profit = Down, Entropy(SOld)=0

For (Age=Mid), there are 2 Down and 2 Up, Entropy(SMid)=1

For (Age=New), all 3 records have Profit = Up, Entropy(SNew)=0

∴Gain(S,Age)=1−[310(0)+410(1)+310(0)]=1−0.4=0.6\therefore\quad Gain(S,Age)=1-[ \frac{3}{10}(0) +\frac{4}{10}(1) +\frac{3}{10}(0) ]=1-0.4=0.6

Calculate Information Gain for Competition

For(Competition=Yes):−35log2⁡(35)−25log2⁡(25)≈0.971For (Competition=Yes): -\frac{3}{5}\log_2\left(\frac{3}{5}\right) -\frac{2}{5}\log_2\left(\frac{2}{5}\right) \approx0.971
For(Competition=No):−25log2⁡(25)−35log2⁡(35)≈0.971For (Competition=No): -\frac{2}{5}\log_2\left(\frac{2}{5}\right) -\frac{3}{5}\log_2\left(\frac{3}{5}\right) \approx0.971
∴Gain(S,Competition)=1−[510(0.971)+510(0.971)]=1−0.971=0.029\therefore\quad Gain(S,Competition)=1-\left[ \frac{5}{10}(0.971) +\frac{5}{10}(0.971) \right] =1-0.971=0.029

Calculate Information Gain for Type

For (Type=Software), there are 3 Down and 3 Up, Entropy(SSoftware)=1

For (Type=Hardware), there are 2 Down and 2 Up, Entropy(SHardware)=1

∴Gain(S,Type)=1−[610(1)+410(1)]=1−1=0\therefore\quad Gain(S,Type)=1-\left[ \frac{6}{10}(1) +\frac{4}{10}(1) \right] =1-1=0

Compare all the 3 gains to choose the root node

AttributeInformation GainAge0.600Competition0.029Type0.000\begin{array}{|c|c|} \hline \text{Attribute} & \text{Information Gain} \\ \hline Age & 0.600 \\ Competition & 0.029 \\ Type & 0.000 \\ \hline \end{array}

The root node selected is Age:

For Old branch and New branch we can assign labels but not for Mid branch:

Consider Mid dataset:

CompetitionTypeProfitYesSoftwareDownYesHardwareDownNoHardwareUpNoSoftwareUp\begin{array}{c|c|c} Competition & Type & Profit \\ \hline Yes & Software & Down \\ Yes & Hardware & Down \\ No & Hardware & Up \\ No & Software & Up \end{array}

Consider Competition:

For Yes, it is Down, Entropy(Syes)= 0

For No, it is Up, Entropy(Sno)=0

∴Gain(SMid,Competition)=1−[24(0)+24(0)]=1−0=1\therefore\quad Gain(S_{Mid},Competition)=1-\left[ \frac{2}{4}(0) +\frac{2}{4}(0) \right] =1-0=1

Consider Type:

For (Type=Software), there is 1 Down and 1 Up, Entropy(SSoftware)=1

For (Type=Hardware), there is 1 Down and 1 Up, Entropy(SHardware)=1

∴Gain(SMid,Type)=1−[24(1)+24(1)]=1−1=0\therefore\quad Gain(S_{Mid},Type)=1-\left[ \frac{2}{4}(1) +\frac{2}{4}(1) \right] =1-1=0

Compare all the gains:

AttributeInformation GainCompetition1.000Type0.000\begin{array}{|c|c|} \hline \text{Attribute} & \text{Information Gain} \\ \hline Competition & 1.000 \\ Type & 0.000 \\ \hline \end{array}

Choose Competition as it has maximum gain.