How to Implement ID3 Algorithm using Python
/ March 29, 2018

Introduction ID3 decision tree algorithm is the first of a series of algorithms created by Ross Quinlan to generate decision trees. Decision Tree is one of the most powerful and popular algorithm. Decision-tree algorithm falls under the category of supervised learning algorithms. It works for both continuous as well as categorical output variables. ID3 is a classification algorithm which for a given set of attributes and class labels, generates the model/decision tree that categorizes a given input to a specific class label ​$$C_k [C_1 C_2 C_3,…C_k].$$​. The algorithm follows a greedy approach by selecting a best attribute that yields maximum information gain ​$$(IG)$$​or minimum entropy ​$$(H).$$​. The algorithm then splits the data-set ​$$(S)$$​recursively upon other unused attributes until it reaches the stop criteria (no further attributes to split). The non-terminal nodes in the decision tree represents the selected attribute upon which the split occurs and the terminal nodes represent the class labels. ID3 Characteristics ID3 does not guarantee an optimal solution; it can get stuck in local optimums It uses a greedy approach by selecting the best attribute to split the dataset on each iteration (one improvement that can be made on the algorithm can be to use backtracking during…