A Decision Tree is a supervised learning algorithm
Supervised Learning means we give input as well as output to the model. (We say in presence of a supervisor – here your output acts like a supervisor).
Classification predicts categorical class labels. Typical applications are Credit/loan approval, Medical diagnosis: if a tumor is cancerous or benign, Fraud detection: if a transaction is fraudulent, Web page categorization: which category it is(multiclass classification)
ID3 stands for Iterative Dichotomiser 3
It is a classification algorithm that follows a greedy approach of building a decision tree by selecting a best attribute that yields max information gain (IG) or min Entropy (H).
Steps:
1.Calculate entropy for dataset.
2.For each attribute/feature.
a.Calculate entropy for all its categorical values.
b.Calculate information gain for the feature.
3.Find the feature with maximum information gain.
4.Repeat it until we get the desired tree.
Entropy – It is a measure of randomness or uncertainty.
E.g. Consider a coin toss problem. Probability of getting a head or tail is the same. i.e. 0.5.
The formula of entropy is − p l o g 2 p − q l o g 2 q -p log_2 p – q log_2 q
Here both have the same probability i.e. 0.5
∴ E n t r o p y = − 0.5 l o g 2 0.5 − 0.5 l o g 2 0.5 = 1 ∴Entropy=-0.5 log_2 0.5 – 0.5 log_2 0.5 =1 Entropy is highest when chances of happening of both the outcomes are equal. So we got highest entropy
Let’s say we have a biased coin. The coin will always give a tail. Here, entropy=0 as there is no uncertainty.
●Information Gain is calculated for a split by subtracting the weighted entropies of each branch from the original entropy Information Gain IG(A) tells us how much uncertainty in S was reduced after splitting set S on attribute A.
I G ( S , A ) = H ( S ) − ∑ v | S v | | S | H ( S v ) IG(S,A)=H(S)-\sum_{v}\frac{|S_v|}{|S|}H(S_v)
Consider the following dataset:
Solution:
Step 1: Calculate entropy of the dataset:
There are 9 yesses and 5 nos, [9+,5-]
∴ Entropy ( S ) = − 9 14 log 2 ( 9 14 ) − 5 14 log 2 ( 5 14 ) = 0.94 \therefore\ \text{Entropy}(S)=-\frac{9}{14}\log_2\left(\frac{9}{14}\right)-\frac{5}{14}\log_2\left(\frac{5}{14}\right)=0.94 Step 2:
Consider Outlook , values (Sunny, Overcast, Rain)
Consider Sunny value, count how many sunny and yesses are there and sunny and nos, there are 2 Yesses and 3 nos in the dataset
S sunny ← [ 2 + , 3 − ] S_{\text{sunny}} \leftarrow [2^+, 3^-]
Entropy ( S sunny ) = − 2 5 log 2 ( 2 5 ) − 3 5 log 2 ( 3 5 ) = 0.5288 + 0.4422 = 0.971 \text{Entropy}(S_{\text{sunny}})=-\frac{2}{5}\log_2\left(\frac{2}{5}\right)-\frac{3}{5}\log_2\left(\frac{3}{5}\right)=0.5288+0.4422=0.971 S overcast ← [ 4 + , 0 − ] ∴ E n t r o p y ( S o v e r c a s t ) = 0 S_{\text{overcast}} \leftarrow [4^+, 0^-] ∴ Entropy (Sovercast )=0 S rain ← [ 3 + , 2 − ] , Entropy ( S rain ) = − 3 5 log 2 ( 3 5 ) − 2 5 log 2 ( 2 5 ) = 0.4422 + 0.5288 = 0.971 S_{\text{rain}} \leftarrow [3^+, 2^-], \text{Entropy}(S_{\text{rain}})=-\frac{3}{5}\log_2\left(\frac{3}{5}\right)-\frac{2}{5}\log_2\left(\frac{2}{5}\right)=0.4422+0.5288=0.971
Gain ( S , Outlook ) = Entropy ( S ) − ∑ v ∈ { sunny, overcast, rain } | S v | | S | ⋅ Entropy ( S v ) \text{Gain}(S, \text{Outlook})=\text{Entropy}(S)-\sum_{v \in \{\text{sunny, overcast, rain}\}}\frac{\vert S_v\vert}{\vert S\vert}\cdot\text{Entropy}(S_v) Gain ( S , Outlook ) = 0.94 − ( 5 14 × 0.971 + 4 14 × 0 + 5 14 × 0.971 ) \text{Gain}(S, \text{Outlook})=0.94-\left(\frac{5}{14}\times0.971+\frac{4}{14}\times0+\frac{5}{14}\times0.971\right)
= 0.94 − 0.693 = 0.2464 =0.94-0.693=\boxed{0.2464} We calculate weighted entropies for all its categorical values, sum it up and then subtract that from the entropy of the dataset.
Consider Temperature , Values (Hot, Mild, Cool)
S ← [ 9 + , 5 − ] , Entropy ( S ) = 0.94 S \leftarrow [9^+,5^-], \text{Entropy}(S)=0.94
S Hot ← [ 2 + , 2 − ] , Entropy ( S Hot ) = 1 S_{\text{Hot}} \leftarrow [2^+,2^-],
\text{Entropy}(S_{\text{Hot}})=1 S Mild ← [ 4 + , 2 − ] , Entropy ( S Mild ) = − 4 6 log 2 ( 4 6 ) − 2 6 log 2 ( 2 6 ) = 0.9183 S_{\text{Mild}} \leftarrow [4^+,2^-], \text{Entropy}(S_{\text{Mild}})
=-\frac{4}{6}\log_2\left(\frac{4}{6}\right)
-\frac{2}{6}\log_2\left(\frac{2}{6}\right)
=0.9183 S Cool ← [ 3 + , 1 − ] , Entropy ( S Cool ) = − 3 4 log 2 ( 3 4 ) − 1 4 log 2 ( 1 4 ) = 0.8113 S_{\text{Cool}} \leftarrow [3^+,1^-], \text{Entropy}(S_{\text{Cool}})
=-\frac{3}{4}\log_2\left(\frac{3}{4}\right)
-\frac{1}{4}\log_2\left(\frac{1}{4}\right)
=0.8113 Gain ( S , Temperature ) = Entropy ( S ) − [ 4 14 Entropy ( S Hot ) + 6 14 Entropy ( S Mild ) + 4 14 Entropy ( S Cool ) ] \text{Gain}(S,\text{Temperature})
=
\text{Entropy}(S)
–
\left[
\frac{4}{14}\text{Entropy}(S_{\text{Hot}})
+
\frac{6}{14}\text{Entropy}(S_{\text{Mild}})
+
\frac{4}{14}\text{Entropy}(S_{\text{Cool}})
\right] = 0.94 − [ 4 14 ( 1 ) + 6 14 ( 0.9183 ) + 4 14 ( 0.8113 ) ] =
0.94
–
\left[
\frac{4}{14}(1)
+
\frac{6}{14}(0.9183)
+
\frac{4}{14}(0.8113)
\right]
= 0.94 − 0.9111 = 0.029 =0.94-0.9111 = 0.029
Consider Humidity , Values(High, Normal)
Entropy ( S high ) = − 3 7 log 2 ( 3 7 ) − 4 7 log 2 ( 4 7 ) = 0.985 \text{Entropy}(S_{\text{high}})=-\frac{3}{7}\log_2\left(\frac{3}{7}\right)-\frac{4}{7}\log_2\left(\frac{4}{7}\right)=0.985
S normal ← [ 6 + , 1 − ] , Entropy ( S normal ) = − 6 7 log 2 ( 6 7 ) − 1 7 log 2 ( 1 7 ) = 0.592 S_{\text{normal}} \leftarrow [6^+, 1^-], \text{Entropy}(S_{\text{normal}})=-\frac{6}{7}\log_2\left(\frac{6}{7}\right)-\frac{1}{7}\log_2\left(\frac{1}{7}\right)=0.592 Gain ( S , Humidity ) = 0.94 − ( 7 14 × 0.985 + 7 14 × 0.592 ) \text{Gain}(S,\text{Humidity})=0.94-\left(\frac{7}{14}\times0.985+\frac{7}{14}\times0.592\right) = 0.94 − 0.7885 = 0.1515 =0.94-0.7885 =\boxed{0.1515} Consider Wind, values(Strong, Weak)
S strong ← [ 3 + , 3 − ] , Entropy ( S strong ) = − 3 6 log 2 ( 3 6 ) − 3 6 log 2 ( 3 6 ) = 1 S_{\text{strong}} \leftarrow [3^+, 3^-], \text{Entropy}(S_{\text{strong}})=-\frac{3}{6}\log_2\left(\frac{3}{6}\right)-\frac{3}{6}\log_2\left(\frac{3}{6}\right)=1 S weak ← [ 6 + , 2 − ] , Entropy ( S weak ) = − 6 8 log 2 ( 6 8 ) − 2 8 log 2 ( 2 8 ) = 0.811 S_{\text{weak}} \leftarrow [6^+, 2^-], \text{Entropy}(S_{\text{weak}})=-\frac{6}{8}\log_2\left(\frac{6}{8}\right)-\frac{2}{8}\log_2\left(\frac{2}{8}\right)=0.811 Gain ( S , Wind ) = 0.94 − ( 8 14 × 0.811 + 6 14 × 1 ) \text{Gain}(S,\text{Wind})=0.94-\left(\frac{8}{14}\times0.811+\frac{6}{14}\times1\right)
= 0.94 − 0.892 = 0.048 =0.94-0.892 =\boxed{0.048} Compare all the Gains obtained:
Gain ( S , Outlook ) = 0.246 \text{Gain}(S,\text{Outlook})=0.246
Gain ( S , Temperature ) = 0.029 \text{Gain}(S,\text{Temperature})=0.029
Gain ( S , Humidity ) = 0.152 \text{Gain}(S,\text{Humidity})=0.152
Gain ( S , Wind ) = 0.048 \text{Gain}(S,\text{Wind})=0.048 In a Decision Tree, the attribute with the highest Information Gain is selected as the node because it gives the greatest reduction in uncertainty (entropy) and produces the best split of the data. Here, Outlook has the highest Information Gain of 0.246 , compared with Humidity (0.152 ), Wind (0.048 ), and Temperature (0.029 ). Therefore, Outlook is selected as the root node .
Consider Sunny Dataset now instead of the whole dataset
Day Temp Humidity Wind Play D 1 Hot High Weak No D 2 Hot High Strong No D 8 Mild High Weak No D 9 Cool Normal Weak Yes D 11 Mild Normal Strong Yes \begin{array}{c|c|c|c|c}
\text{Day} & \text{Temp} & \text{Humidity} & \text{Wind} & \text{Play} \\
\hline
D1 & \text{Hot} & \text{High} & \text{Weak} & \text{No} \\
D2 & \text{Hot} & \text{High} & \text{Strong} & \text{No} \\
D8 & \text{Mild} & \text{High} & \text{Weak} & \text{No} \\
D9 & \text{Cool} & \text{Normal} & \text{Weak} & \text{Yes} \\
D11 & \text{Mild} & \text{Normal} & \text{Strong} & \text{Yes}
\end{array} S sunny ← [ 2 + , 3 − ] , ∴ Entropy ( S sunny ) = − 2 5 log 2 2 5 − 3 5 log 2 3 5 = 0.97 S_{\text{sunny}} \leftarrow [2^+,3^-], \therefore\ \text{Entropy}(S_{\text{sunny})}=-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5}=0.97
Attribute: Temperature
S Hot ← [ 0 + , 2 − ] , ∴ Entropy ( S Hot ) = 0 S_{\text{Hot}} \leftarrow [0^+,2^-], \therefore\ \text{Entropy}(S_{\text{Hot}})=0 S Mild ← [ 1 + , 1 − ] , ∴ Entropy ( S Mild ) = 1 S_{\text{Mild}} \leftarrow [1^+,1^-], \therefore\ \text{Entropy}(S_{\text{Mild}})=1
S Cool ← [ 1 + , 0 − ] , ∴ Entropy ( S Cool ) = 0 S_{\text{Cool}} \leftarrow [1^+,0^-], \therefore\ \text{Entropy}(S_{\text{Cool}})=0 Gain ( S sunny , Temp ) = Entropy ( S sunny ) − ∑ v ∈ { Hot , Mild , Cool } | S v | | S | ⋅ Entropy ( S v ) \text{Gain}(S_{\text{sunny}},\text{Temp})=\text{Entropy}(S_{\text{sunny}})-\sum_{v\in\{\text{Hot},\text{Mild},\text{Cool}\}}\frac{|S_v|}{|S|}\cdot\text{Entropy}(S_v)
= 0.97 − ( 2 5 ⋅ 0 + 2 5 ⋅ 1 + 1 5 ⋅ 0 ) = 0.57 =0.97-\left(\frac{2}{5}\cdot0+\frac{2}{5}\cdot1+\frac{1}{5}\cdot0\right)=0.57
Attribute: Humidity
S sunny ← [ 2 + , 3 − ] ∴ Entropy ( S sunny ) = 0.97 S_{\text{sunny}} \leftarrow [2^+,3^-]\quad\therefore\ \text{Entropy}(S_{\text{sunny}})=0.97
S High ← [ 0 + , 3 − ] , ∴ Entropy ( S High ) = 0 S_{\text{High}} \leftarrow [0^+,3^-], \therefore\ \text{Entropy}(S_{\text{High}})=0 S Normal ← [ 2 + , 0 − ] , ∴ Entropy ( S Normal ) = 0 S_{\text{Normal}} \leftarrow [2^+,0^-], \therefore\ \text{Entropy}(S_{\text{Normal}})=0 ∴ Gain ( S sunny , Humidity ) = Entropy ( S sunny ) − [ 3 5 ⋅ 0 + 2 5 ⋅ 0 ] = 0.97 \therefore\ \text{Gain}(S_{\text{sunny}},\text{Humidity})=\text{Entropy}(S_{\text{sunny}})-\left[\frac{3}{5}\cdot0+\frac{2}{5}\cdot0\right]=0.97 Attribute: Wind
S sunny ← [ 2 + , 3 − ] ∴ Entropy ( S sunny ) = 0.97 S_{\text{sunny}} \leftarrow [2^+,3^-]\quad\therefore\ \text{Entropy}(S_{\text{sunny}})=0.97
S Weak ← [ 1 + , 2 − ] , ∴ Entropy ( S Weak ) = − 2 3 log 2 2 3 − 1 3 log 2 1 3 = 0.9183 S_{\text{Weak}} \leftarrow [1^+,2^-], \therefore\ \text{Entropy}(S_{\text{Weak}})=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.9183 S Strong ← [ 1 + , 1 − ] , ∴ Entropy ( S Strong ) = 1 S_{\text{Strong}} \leftarrow [1^+,1^-], \therefore\ \text{Entropy}(S_{\text{Strong}})=1 ∴ Gain ( S sunny , Wind ) = Entropy ( S sunny ) − ∑ v ∈ { Strong , Weak } | S v | | S sunny | ⋅ Entropy ( S v ) \therefore\ \text{Gain}(S_{\text{sunny}},\text{Wind})=\text{Entropy}(S_{\text{sunny}})-\sum_{v\in\{\text{Strong},\text{Weak}\}}\frac{|S_v|}{|S_{\text{sunny}}|}\cdot\text{Entropy}(S_v) = 0.97 − ( 3 5 ⋅ 0.9183 + 2 5 ⋅ 1 ) = 0.0192 =0.97-\left(\frac{3}{5}\cdot0.9183+\frac{2}{5}\cdot1\right)=0.0192 Gain ( S sunny , Humidity ) = 0.97 \text{Gain}(S_{\text{sunny}},\text{Humidity})=0.97 Gain ( S sunny , Temp ) = 0.57 \text{Gain}(S_{\text{sunny}},\text{Temp})=0.57 Gain ( S sunny , Wind ) = 0.0192 \text{Gain}(S_{\text{sunny}},\text{Wind})=0.0192 ∴ Humidity is selected as the next node for Sunny \therefore\ \boxed{\text{Humidity is selected as the next node for Sunny}} Consider Rain dataset now,
Day Temp Humidity Wind Play T D 4 Mild High Weak Yes D 5 Cool Normal Weak Yes D 6 Cool Normal Strong No D 10 Mild Normal Weak Yes D 14 Mild High Strong No \begin{array}{|c|c|c|c|c|}
\hline
\text{Day} & \text{Temp} & \text{Humidity} & \text{Wind} & \text{Play T} \\
\hline
D4 & \text{Mild} & \text{High} & \text{Weak} & \text{Yes} \\
\hline
D5 & \text{Cool} & \text{Normal} & \text{Weak} & \text{Yes} \\
\hline
D6 & \text{Cool} & \text{Normal} & \text{Strong} & \text{No} \\
\hline
D10 & \text{Mild} & \text{Normal} & \text{Weak} & \text{Yes} \\
\hline
D14 & \text{Mild} & \text{High} & \text{Strong} & \text{No} \\
\hline
\end{array} Consider Temperature
S Rain = [ 3 + , 2 − ] ∴ Entropy ( S Rain ) = 0.971 S_{\text{Rain}}=[3^+,2^-]\quad\therefore\ \text{Entropy}(S_{\text{Rain}})=0.971
S Hot = [ 0 + , 0 − ] ∴ E ( S Hot ) = 0 as no hot examples S_{\text{Hot}}=[0^+,0^-]\quad\therefore\ E(S_{\text{Hot}})=0\ \text{as no hot examples} S Mild = [ 2 + , 1 − ] ∴ E ( S Mild ) = − 2 3 log 2 2 3 − 1 3 log 2 1 3 = 0.9183 S_{\text{Mild}}=[2^+,1^-]\quad\therefore\ E(S_{\text{Mild}})=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.9183 S Cool = [ 1 + , 1 − ] ∴ E ( S Cool ) = 1 S_{\text{Cool}}=[1^+,1^-]\quad\therefore\ E(S_{\text{Cool}})=1 Gain ( S Rain , Temp ) = 0.971 − ( 0 × 0 + 3 5 × 0.9183 + 2 5 × 1 ) = 0.0192 \text{Gain}(S_{\text{Rain}},\text{Temp})=0.971-\left(0\times0+\frac{3}{5}\times0.9183+\frac{2}{5}\times1\right)=0.0192 Consider Humidity
S Rain = [ 3 + , 2 − ] ∴ Entropy ( S Rain ) = 0.971 S_{\text{Rain}}=[3^+,2^-]\quad\therefore\ \text{Entropy}(S_{\text{Rain}})=0.971 S High = [ 1 + , 1 − ] ∴ E ( S High ) = 1 S_{\text{High}}=[1^+,1^-]\quad\therefore\ E(S_{\text{High}})=1 S Normal = [ 2 + , 1 − ] ∴ E ( S Normal ) = − 2 3 log 2 2 3 − 1 3 log 2 1 3 = 0.9183 S_{\text{Normal}}=[2^+,1^-]\quad\therefore\ E(S_{\text{Normal}})=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.9183 ∴ Gain ( S Rain , Humidity ) = 0.971 − 2 5 × 1 − 3 5 × 0.9183 = 0.0192 \therefore\ \text{Gain}(S_{\text{Rain}},\text{Humidity})=0.971-\frac{2}{5}\times1-\frac{3}{5}\times0.9183=0.0192 Consider Wind
S Rain = [ 3 + , 2 − ] ∴ Entropy ( S Rain ) = 0.971 S_{\text{Rain}}=[3^+,2^-]\quad\therefore\ \text{Entropy}(S_{\text{Rain}})=0.971 S Weak = [ 3 + , 0 − ] ∴ E ( S Weak ) = 0 S_{\text{Weak}}=[3^+,0^-]\quad\therefore\ E(S_{\text{Weak}})=0 S Strong = [ 0 + , 2 − ] ∴ E ( S Strong ) = 0 S_{\text{Strong}}=[0^+,2^-]\quad\therefore\ E(S_{\text{Strong}})=0 Gain ( S Rain , Wind ) = 0.971 − 3 5 × 0 − 2 5 × 0 = 0.971 \text{Gain}(S_{\text{Rain}},\text{Wind})=0.971-\frac{3}{5}\times0-\frac{2}{5}\times0=0.971 Gain ( S Rain , Temp ) = 0.0192 \text{Gain}(S_{\text{Rain}},\text{Temp})=0.0192 Gain ( S Rain , Humidity ) = 0.0192 \text{Gain}(S_{\text{Rain}},\text{Humidity})=0.0192 Gain ( S Rain , Wind ) = 0.971 \text{Gain}(S_{\text{Rain}},\text{Wind})=0.971 ∴ Wind is selected as the next node for Rain \therefore\ \boxed{\text{Wind is selected as the next node for Rain}}
Swati Varma 