Decision Trees

Decision tree is the most powerful and popular tool for classification and prediction. A Decision tree is a flowchart-like tree structure, where each internal node denotes a test on an attribute, each branch represents an outcome of the test, and each leaf node (terminal node) holds a class label.

Simple Decision Tree Example

Construction of Decision Tree :
A tree can be “learned” by splitting the source set into subsets based on an attribute value test. This process is repeated on each derived subset in a recursive manner called recursive partitioning. The recursion is completed when the subset at a node all has the same value of the target variable, or when splitting no longer adds value to the predictions.

Decision trees classify instances by sorting them down the tree from the root to some leaf node, which provides the classification of the instance. An instance is classified by starting at the root node of the tree, testing the attribute specified by this node, then moving down the tree branch corresponding to the value of the attribute.

Split techniques for decision trees :

Gini index:

The Gini Index is calculated by subtracting the sum of the squared probabilities of each class from one.

• Uses squared proportion of classes.
  Perfectly classified, Gini Index would be zero.
• The Gini index is used in the classic CART(classification and regression)

Entropy:

Entropy is the measure of impurity, disorder or uncertainity in a system.

Information Gain:

Information gain measures how much information a feature gives us about the class.

Strengths and Weakness of Decision Tree approach
The strengths of decision tree methods are:

• Decision trees are able to generate understandable rules.
• Decision trees perform classification without requiring much computation.
• Decision trees are able to handle both continuous and categorical variables.
• Decision trees provide a clear indication of which fields are most important for prediction or classification.

The weaknesses of decision tree methods :

• Decision trees are less appropriate for estimation tasks where the goal is to predict the value of a continuous attribute.
• Decision trees are prone to errors in classification problems with many class and relatively small number of training examples.