ID3 algorithm

In decision tree learning, ID3 (Iterative Dichotomiser 3) is an algorithm invented by Ross Quinlan used to generate a decision tree from a dataset. ID3 is the precursor to the C4.5 algorithm, and is typically used in the machine learning and natural language processing domains.

The ID3 algorithm begins with the original set ${\displaystyle S}$ as the root node. On each iteration of the algorithm, it iterates through every unused attribute of the set ${\displaystyle S}$ and calculates the entropy ${\displaystyle H(S)}$ (or information gain ${\displaystyle IG(S)}$) of that attribute. It then selects the attribute which has the smallest entropy (or largest information gain) value. The set ${\displaystyle S}$ is then split by the selected attribute (e.g. age is less than 50, age is between 50 and 100, age is greater than 100) to produce subsets of the data. The algorithm continues to recurse on each subset, considering only attributes never selected before.
Recursion on a subset may stop in one of these cases:

...
Wikipedia