ID3 Iterative Dichotomiser 3

ID3  Iterative  Dichotomiser  3

-Decision Tree represents a Function that takes as  Input and  return  a Decision (Single Output Value)

-Input/Output Value can be  

    Discrete /Continuous 

-Decision Tree Algorithms

• ID3(Iterative Dichotomiser 3)
• C4.5  (Successor of ID3) 
• CART (Classification & Regression Tree)
• CHAID  (Chi Squared  Automatic  Interaction Detector)

-By Performing Sequence of Tests Decision Tree reaches its  Decision.

Example:-

                                                

                                             Outlook(Each Node Test an Attribute)

Sunny                                         Overcast                           Rain  ------(Each Branch Corresponds 

                                                                                                                                  to Attribute Value Node ) 

No                                                    Yes                                No ---------(Each Leaf assigns a                                                                                                                              Classification)        

-ID3  is the most Common Decision Tree Algorithm

-Dichotomiser means 

                                     Dividing  into Two Completely Opposite Things 

-ID3 Algorithm Iteratively  divides Attributes into  2 Groups 

• Most  Dominant Attribute
• Others to Construct a Tree 

-Now Calculates  Entropy & Information Gain for  each Attribute 

• Entropy

The entropy is a measure of the uncertainty associated with a random variable

• Information Gain 

Information gain is used as an attribute selection measure

-In this way most Dominant one is put on tree   as Decision Node 

-Again Entropy and Information Gain Scores  Calculated among Attributes .

-This Procedure continues until reaching a Decision for  that Branch.

-Calculate  Entropy for every Attribute using Data set "S"

Entropy (S) ≡ ∑− p_i log₂ ( p_i )

-Split S into subsets using Attribute for  which resulting  

Entropy  (after splitting) is Minimum / Equivalently Information Gain is Maximum.

Gain (S, A) =  Entropy(S) − ∑[ p(S/A) . Entropy(S/A)]

-Make Decision Tree node Containing that attribute 

-Recurse /Subsets using  remaining Attributes 

Example:-

Table 6_.1 Class_‐labeled training tuples from AllElectronics customer database_.

17

•          Class P: buys_computer = “yes”

•          Class N: buys _{_}computer = _“no_”

Entropy(D) = -9/14  log₂ (9/14) − (5/₁₄ )log₂ (5/₁₄ ) =0.940

•          Compute the expected information requirement for each attribute: start with the attribute age

Gain(age,D)= Entropy(D)	∑	| Sv | /	.  Entropy(Sv)
	v∈{Youth,Middle−aged ,Senior}         | S |

=    Entropy(D) − (5/₁₄₎ Entropy(Syouth)  − (4/14) Entropy(Smiddle _ aged )  −   (5/₁₄₎ Entropy(Ssenior)

=   0.246

Gain (income, D) = 0.029
Gain (student, D) = 0.151
Gain (credit _ rating, D) = 0.048	18