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

Attributeamp;Information GainAgeamp;0.600Competitionamp;0.029Typeamp;0.000\begin{array}{|c|c|} \hline \text{Attribute} &amp; \text{Information Gain} \\ \hline Age &amp; 0.600 \\ Competition &amp; 0.029 \\ Type &amp; 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:

Competitionamp;Typeamp;ProfitYesamp;Softwareamp;DownYesamp;Hardwareamp;DownNoamp;Hardwareamp;UpNoamp;Softwareamp;Up\begin{array}{c|c|c} Competition &amp; Type &amp; Profit \\ \hline Yes &amp; Software &amp; Down \\ Yes &amp; Hardware &amp; Down \\ No &amp; Hardware &amp; Up \\ No &amp; Software &amp; 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:

Attributeamp;Information GainCompetitionamp;1.000Typeamp;0.000\begin{array}{|c|c|} \hline \text{Attribute} &amp; \text{Information Gain} \\ \hline Competition &amp; 1.000 \\ Type &amp; 0.000 \\ \hline \end{array}

Choose Competition as it has maximum gain.