ID3 algorithm is a greedy algorithm, which is used to construct decision trees. ID3 algorithm originated from the Concept Learning System (CLS), and takes the descending speed of information entropy as the criterion for selecting test attributes, that is, selecting the attribute with the highest information gain that has not been used for classification at each node as the classification criterion, and then continuing this process until the generated decision tree can classify the training samples perfectly.

Background of ID3 algorithm

ID3 algorithm was first proposed by J. Ross Quinlan of the University of Sydney in 1975. The core of the algorithm is information entropy. By calculating the information gain of each attribute, ID3 algorithm thinks that the attribute with high information gain is a good attribute, selects the attribute with the highest information gain as the division standard for each division, and repeats this process until a decision tree that can perfectly classify training samples is generated.