Short note: Decision tree

A decision tree is a flowchart-like tree used for classification and prediction. Each internal node tests an attribute, each branch is an outcome of the test, and each leaf node holds a class label. The topmost node is the root.

How it works

To classify a tuple, start at the root, follow the branch matching the tuple's attribute value at each node, until a leaf is reached; its label is the predicted class.

        [Age?]
      /   |    \
  young  middle  senior
    |      |       |
[Student?] YES  [Credit?]
  /   \          /    \
 no   yes     fair   excellent
 NO   YES     YES       NO

Construction

The tree is built top-down by recursive partitioning (greedy, divide and conquer). The best splitting attribute at each step is chosen using a measure such as information gain (ID3), gain ratio (C4.5) or Gini index (CART). Growing stops when all records of a node have the same class, no attributes remain, or no records are left.

Features

• Does not need domain knowledge or parameter setting; handles numeric and categorical data.
• Fast to build and to classify, with accuracy comparable to other methods.
• Easy to understand and convert into IF-THEN rules.
• May overfit noisy data, so pruning (pre- or post-pruning) is used.

Common algorithms: ID3, C4.5, CART.