Decision Trees

Input: a set of observations \(S\) with input features that are classified into \(J\) classes

Output: a tree where the internal nodes are input features, the branches out of a node are the values that the feature can take, and the leaves are subsets of \(S\).

Algorithims: CART, ID3

The output tree can be used for classification. Given a new observation \(x\), traverse the tree according to the features of \(x\). When you reach a leaf, classify according to the distribution in the leaf.

Assume that all the input features are categorical. Beginning with \(S\) select an input feature that splits \(S\) into subsets. Recursively split the resulting subsets. The feature to split on is determined by information gain or Gini impurity