ID3, which stands for ``Induction of Decision Trees'', is a supervised learning system which constructs classification rules in the form of a decision tree. It takes a set of objects, the training set, as input, and builds the decision tree by partitioning the training set. Attributes are chosen to split the set, and a tree is build for each subset, until all members of the subsets belong to the same class.
A heuristic function is used to choose the best attribute to split on based on the training set. ID3 is a greedy algorithm, and thus a bad choice of one attribute, may affect the final result. The original version of ID3 handled only a small number of discrete values, but was later modified to handle both ordered and continuous attributes. Other variations of the ID3 algorithm include the ability to handle noise. Using a test, only attributes whose irrelevance can be rejected are used for splitting the set. If attributes are lacking during classification, all possible branches are explored, and the most probable classification is chosen.
ID3 was developed by Quinlan [Qui79, Qui86] and is the perhaps most used ML algorithm in scientific literature and commercial systems. A quick introduction is given in [LS93, HS94]. In conclusion, ID3 is an algorithm which has high classification accuracy even in noisy data sets. It has a fast learning phase, and low time complexity. ID3 must be supplied with the entire training set at once, but variations with incremental learning exist. The decision three resulting from ID3 is not very simple for humans to cope with when large amounts of data are used.