How Decision Tree - Classification, Works Using Entropy

Decision Tree - Classification

Decision tree builds classification or regression models in the form of a tree structure. It breaks down a dataset into smaller and smaller subsets while at the same time an associated decision tree is incrementally developed. The final result is a tree with decision nodes and leaf nodes. A decision node (e.g., Outlook) has two or more branches (e.g., Sunny, Overcast and Rainy). Leaf node (e.g., Play) represents a classification or decision. The topmost decision node in a tree which corresponds to the best predictor called root node. Decision trees can handle both categorical and numerical data. 
  

Algorithm

The core algorithm for building decision trees called ID3 by J. R. Quinlan which employs a top-down, greedy search through the space of possible branches with no backtracking. ID3 uses Entropy and Information Gain to construct a decision tree. In ZeroR model there is no predictor, in OneR model we try to find the single best predictor, naive Bayesian includes all predictors using Bayes' rule and the independence assumptions between predictors but decision tree includes all predictors with the dependence assumptions between predictors.
Entropy
A decision tree is built top-down from a root node and involves partitioning the data into subsets that contain instances with similar values (homogenous). ID3 algorithm uses entropy to calculate the homogeneity of a sample. If the sample is completely homogeneous the entropy is zero and if the sample is an equally divided it has entropy of one.
 
To build a decision tree, we need to calculate two types of entropy using frequency tables as follows:
a) Entropy using the frequency table of one attribute:
b) Entropy using the frequency table of two attributes:
 
Information Gain
The information gain is based on the decrease in entropy after a dataset is split on an attribute. Constructing a decision tree is all about finding attribute that returns the highest information gain (i.e., the most homogeneous branches).
Step 1: Calculate entropy of the target. 
Step 2: The dataset is then split on the different attributes. The entropy for each branch is calculated. Then it is added proportionally, to get total entropy for the split. The resulting entropy is subtracted from the entropy before the split. The result is the Information Gain, or decrease in entropy. 
Step 3: Choose attribute with the largest information gain as the decision node, divide the dataset by its branches and repeat the same process on every branch.
Step 4a: A branch with entropy of 0 is a leaf node.
Step 4b: A branch with entropy more than 0 needs further splitting.
Step 5: The ID3 algorithm is run recursively on the non-leaf branches, until all data is classified.
 

Decision Tree to Decision Rules

A decision tree can easily be transformed to a set of rules by mapping from the root node to the leaf nodes one by one.

Decision Trees - Issues

 
Exercise
 

Comments

Post a Comment

Popular posts from this blog

Maxpooling vs minpooling vs average pooling

Image
Pooling is performed in neural networks to reduce variance and computation complexity. Many times, beginners blindly use a pooling method without knowing the reason for using it. Here is a comparison of three basic pooling methods that are widely used. The three types of pooling operations are: Max pooling: The maximum pixel value of the batch is selected. Min pooling: The minimum pixel value of the batch is selected. Average pooling: The average value of all the pixels in the batch is selected. The batch here means a group of pixels of size equal to the filter size which is decided based on the size of the image. In the following example, a filter of 9x9 is chosen. The output of the pooling method varies with the varying value of the filter size. The operations are illustrated through the following figures. Average, Max and Min pooling of size 9x9 applied on an image We cannot say that a particular pooling method is better over others generally. The choice of pooling operation is made
Read more

Percentiles, Deciles, and Quartiles

Image
Percentiles Percentile: the value below which a percentage of data falls. Example: You are the fourth tallest person in a group of 20 80% of people are shorter than you: That means you are at the  80th percentile . If your height is 1.85m then "1.85m" is the 80th percentile height in that group. In Order Have the data  in order , so you know which values are above and below. To calculate percentiles of height: have the data in height order (sorted by height). To calculate percentiles of age: have the data in age order. And so on. Grouped Data When the data is grouped: Add up all percentages  below  the score, plus  half  the percentage  at  the score. Example: You Score a B! In the test 12% got D, 50% got C, 30% got B and 8% got A You got a B, so add up all the 12% that got D, all the 50% that got C, half of the 30% that got B, for a total percentile of 12% + 50% + 15% =  77% In other words you did "as well or better than
Read more

Understand the Softmax Function in Minutes

Image
Learning machine learning? Specifically trying out neural networks for deep learning? You likely have run into the  Softmax function, a wonderful  activation function  that turns numbers aka logits into probabilities that sum to one. Softmax function outputs a vector that represents the probability distributions of a list of potential outcomes.  It’s also a core element used in  deep learning   classification  tasks. We will help you understand the Softmax function in a beginner friendly manner by showing you exactly how it works — by coding your very own Softmax function in python. If you are implementing Softmax in Pytorch and you already know Pytorch well, scroll down to the Deep Dive section and grab the code. This article has gotten really popular: 5800+ claps. It is updated constantly. Latest update Jan 2020 added a TL;DR section for busy souls. Dec 2019 (Softmax with Numpy Scipy Pytorch functional. Visuals indicating the location of Softmax function in Neural Network architectur
Read more