įinally, we choose the option with the lowest weighted average entropy. Now we compute the weighted entropy for marital status. įor marital status = married, we get zero. We need to calculate the entropies of these three distributions.įor marital status = single, we get entropy =. For marital status = divorced, we have 2 data points, one with refund = no and one with refund = yes. For marital status = married, we have 4 data points, all of which have refund = no. For marital status = single, we have 4 data points, two of which have cheat = no and two have cheat = yes. If we choose marital status at the top, there will be three edges out of this node: marital status = single, marital status = married and marital status = divorced. We take the entropy for refund = yes and weigh it by the proportion of data points that have refund = yes (3 out of 10), and add the entropy for refund = no, weighted by the proportion of data points that have refund = no (7 out of 10). įinally, we compute the weighted average entropy for refund. Now we will calculate the entropies of these two distributions (of the class variable cheat, assuming that refund = yes or no, respectively).įor refund = yes, we have a distribution of cheat where cheat=no is the only possible outcome, so the entropy is zero.įor refund = no, we have a distribution of cheat where P(cheat=no) = 4/7 and P(cheat=yes) = 3/7. For refund = no, we have 7 data points, of which four have cheat=no and 3 have cheat=yes. For refund = yes, we have 3 data points, of which all three have cheat=no. If we choose refund at the top, there will be two edges out of this node: refund=yes and refund=no. In our example, the root node can be refund or marital status. The first step is to decide on the root node of the decision tree. Decision trees can handle both categorical and numerical data. The topmost decision node in a tree which corresponds to the best predictor called root node. refund) has two or more branches (e.g., yes or no) and the leaf node (e.g., cheat) represents a classification or decision. The objective is to predict if someone will cheat on their income tax return based on their marital status and whether they are due a tax refund.Ī decision node (e.g. The two features are refund and marital status, and the class attribute (to be predicted) is cheat. The final result is a tree with decision nodes and leaf nodes.įor an example, we will use the same labeled data set as in the naive Bayes classification. It breaks down the dataset into smaller and smaller subsets as the tree is incrementally developed.

Decision tree builds classification or regression models in the form of a tree structure. Before discussing the algorithm, please fully read the background information on entropy here. Quinlan) that relies on the information-theoretic concept of entropy and information gain. While many decision tree algorithms exist, we will learn a decision tree construction algorithm (ID3 by J. Data Science Guide About Index Map outline posts Decision tree

Decision tree entropy