Decision Tree

Decision Trees

Decision trees are machine learning models that try to find patterns in the features of data points.

Decision Trees Construction

Decision Trees are usually constructed from top to bottom. At each level of the tree, the feature that best splits the training set labels is selected as the “question” of that level. Two different criteria are available to split a node, Gini Index and Information Gain. The convenience of one or the other depends on the problem.

Decision Trees in scikit-learn


The sklearn.tree module contains the DecisionTreeClassifier class.



Information Gain at decision trees

When making decision trees, two different methods are used to find the best feature to split a dataset on: Gini impurity and Information Gain. An intuitive interpretation of Information Gain is that it is a measure of how much information the individual features provide us about the different classes.

Gini impurity

When making decision trees, calculating the Gini impurity of a set of data helps determine which feature best splits the data. If a set of data has all of the same labels, the Gini impurity of that set is 0. The set is considered pure. Gini impurity is a statistical measure - the idea behind its definition is to calculate how accurate it would be to assign labels at random, considering the distribution of actual labels in that subset.

Decision trees leaf creation

 When making a decision tree, a leaf node is created when no features result in any information gain.


Decision Tree Representation

In a decision tree, leaves represent class labels, internal nodes represent a single feature, and the edges of the tree represent possible values of those features. 


Decision trees pruning

Decision trees can be overly complex which can result in overfitting. A technique called pruning can be used to decrease the size of the tree to generalize it to increase accuracy on a test set. Pruning is not an exact method, as it is not clear which should be the ideal size of the tree. This technique can be made bottom-up (starting at the leaves) or up-bottom (starting at the root). 

Decision Tree Limitations

 Our current strategy of creating trees is greedy. We assume that the best way to create a tree is to find the feature that will result in the largest information gain right now and split on that feature.

Another problem with our trees is that they potentially overfit the data. This means that the structure of the tree is too dependent on the training data and doesn’t accurately represent the way the data in the real world looks like.

One way to solve this problem is to prune the tree. The goal of pruning is to shrink the size of the tree.

Comments

Post a Comment

Popular posts from this blog

Support Vector Machines

Image
Support Vector Machines A Support Vector Machine (SVM) is a powerful supervised machine learning model used for classification. An SVM makes classifications by defining a decision boundary and then seeing what side of the boundary an unclassified point falls on. Decision boundaries get defined,  by using a training set of classified points.     Decision boundaries exist even when your data has more than two features. If there are three features, the decision boundary is now a plane rather than a line.   As the number of dimensions grows past 3, it becomes very difficult to visualize these points in space. Nonetheless, SVMs can still find a decision boundary. However, rather than being a separating line, or a separating plane, the decision boundary is called a separating hyperplane . Optimal Decision Boundaries In general, we want our decision boundary to be as far away from training points as possible. Maximizing the dis...
Read more

ACCURACY, RECALL, PRECISION, F1 SCORE

ACCURACY, RECALL, PRECISION, F1 SCORE Classifying a single point can result in a true positive ( truth = 1 , guess = 1 ), a true negative ( truth = 0 , guess = 0 ), a false positive ( truth = 0 , guess = 1 ), or a false negative ( truth = 1 , guess = 0 ). Accuracy measures how many classifications your algorithm got correct out of every classification it made. Recall measures the percentage of the relevant items your classifier was able to successfully find. Precision measures the percentage of items your classifier found that were actually relevant. Precision and recall are tied to each other. As one goes up, the other will go down. F1 score is a combination of precision and recall. F1 score will be low if either precision or recall is low. The decision to use precision, recall, or F1 score ultimately comes down to the context of your classification. Maybe you don’t care if your classifier has a lot of false positives. If that’s the case, precision doesn’t matter as m...
Read more

Random Forest

RANDOM FOREST A random forest is an ensemble machine learning model. It makes a classification by aggregating the classifications of many decision trees. Random forests are used to avoid overfitting. By aggregating the classification of multiple trees, having overfitted trees in a random forest is less impactful. Every decision tree in a random forest is created by using a different subset of data points from the training set. Those data points are chosen at random with replacement , which means a single data point can be chosen more than once. This process is known as bagging . When creating a tree in a random forest, a randomly selected subset of features are considered as candidates for the best splitting feature. If your dataset has n features, it is common practice to randomly select the square root of n features. Boosting Steps : Draw a random subset of training samples d1 without replacement from the training set D to train a weak learner C1 ...
Read more