ID3 algorithm

1. Calculate the entropy of every attribute ${\displaystyle a}$ of the data set ${\displaystyle S}$.
2. Partition ("split") the set ${\displaystyle S}$ into subsets using the attribute for which the resulting entropy after splitting is minimized; or, equivalently, information gain is maximum.
3. Make a decision tree node containing that attribute.
4. Recurse on subsets using the remaining attributes.

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value, vi, of A,
            Add a new tree branch below Root, corresponding to the test A = vi.
            Let Examples(vi) be the subset of examples that have the value vi for A
            If Examples(vi) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A})
    End
    Return Root

ID3-generated decision tree used to determine whether a particular nucleotide pair within a pre-mRNA sequence corresponds to an mRNA splice site. This tree has been shown to have a 95% correct prediction rate.[2]

ID3 does not guarantee an optimal solution. It can converge upon local optima. It uses a greedy strategy by selecting the locally best attribute to split the dataset on each iteration. The algorithm's optimality can be improved by using backtracking during the search for the optimal decision tree at the cost of possibly taking longer.

ID3 can overfit the training data. To avoid overfitting, smaller decision trees should be preferred over larger ones. This algorithm usually produces small trees, but it does not always produce the smallest possible decision tree.

ID3 is harder to use on continuous data than on factored data (factored data has a discrete number of possible values, thus reducing the possible branch points). If the values of any given attribute are continuous, then there are many more places to split the data on this attribute, and searching for the best value to split by can be time consuming.

The ID3 algorithm is used by training on a data set ${\displaystyle S}$ to produce a decision tree which is stored in memory. At runtime, this decision tree is used to classify new test cases (feature vectors) by traversing the decision tree using the features of the datum to arrive at a leaf node. The class of this terminal node is the class the test case is classified as.

Entropy ${\displaystyle \mathrm {H} {(S)}}$ is a measure of the amount of uncertainty in the (data) set ${\displaystyle S}$ (i.e. entropy characterizes the (data) set ${\displaystyle S}$).

${\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}$

Where,

• ${\displaystyle S}$ – The current dataset for which entropy is being calculated
  • This changes at each step of the ID3 algorithm, either to a subset of the previous set in the case of splitting on an attribute or to a "sibling" partition of the parent in case the recursion terminated previously.
• ${\displaystyle X}$ – The set of classes in ${\displaystyle S}$
• ${\displaystyle p(x)}$ – The proportion of the number of elements in class ${\displaystyle x}$ to the number of elements in set ${\displaystyle S}$

When ${\displaystyle \mathrm {H} {(S)}=0}$, the set ${\displaystyle S}$ is perfectly classified (i.e. all elements in ${\displaystyle S}$ are of the same class).

In ID3, entropy is calculated for each remaining attribute. The attribute with the smallest entropy is used to split the set ${\displaystyle S}$ on this iteration. Entropy in information theory measures how much information is expected to be gained upon measuring a random variable; as such, it can also be used to quantify the amount to which the distribution of the quantity's values is unknown. A constant quantity has zero entropy, as its distribution is perfectly known. In contrast, a uniformly distributed random variable (discretely or continuously uniform) maximizes entropy. Therefore, the greater the entropy at a node, the less information is known about the classification of data at this stage of the tree; and therefore, the greater the potential to improve the classification here.

As such, ID3 is a greedy heuristic performing a best-first search for locally optimal entropy values. Its accuracy can be improved by preprocessing the data.

Information gain ${\displaystyle IG(A)}$ is the measure of the difference in entropy from before to after the set ${\displaystyle S}$ is split on an attribute ${\displaystyle A}$. In other words, how much uncertainty in ${\displaystyle S}$ was reduced after splitting set ${\displaystyle S}$ on attribute ${\displaystyle A}$.

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}$

Where,

• ${\displaystyle \mathrm {H} (S)}$ – Entropy of set ${\displaystyle S}$
• ${\displaystyle T}$ – The subsets created from splitting set ${\displaystyle S}$ by attribute ${\displaystyle A}$ such that ${\displaystyle S=\bigcup _{t\in T}t}$
• ${\displaystyle p(t)}$ – The proportion of the number of elements in ${\displaystyle t}$ to the number of elements in set ${\displaystyle S}$
• ${\displaystyle \mathrm {H} (t)}$ – Entropy of subset ${\displaystyle t}$

In ID3, information gain can be calculated (instead of entropy) for each remaining attribute. The attribute with the largest information gain is used to split the set ${\displaystyle S}$ on this iteration.