Decision Tree Regression

-
Decision tree builds regression or classification 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), each representing values for the attribute tested. Leaf node (e.g., Hours Played) represents a decision on the numerical target. 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.



A decision tree is drawn upside down with its root at the top. In the image on the left, the bold text in black represents a condition/internal node, based on which the tree splits into branches/ edges. The end of the branch that doesn’t split anymore is the decision/leaf, wherein lies the prediction

Although, a real dataset will have a lot more features and this will just be a branch in a much bigger tree, but we can’t ignore the simplicity of this algorithm. The feature importance is clear and relations can be viewed easily. This methodology is more commonly known as learning decision tree from data and above tree is called Classification tree as the target is to classify passenger as survived or died. Regression trees are represented in the same manner, just they predict continuous values like the price of a house. In general, Decision Tree algorithms are referred to as CART or Classification and Regression Trees.

These algorithms are recursive in nature and every split will have a cost. The split that costs least is chosen and due to its recursive nature as the groups formed can be sub-divided using the same strategy.  Due to this procedure, this algorithm is also known as the greedy algorithm, as we have an excessive desire of lowering the cost. This makes the root node as best predictor/classifier.

When to stop splitting?
As a problem usually has a large set of features, it results in a large number of the split, which in turn gives a huge tree. Such trees are complex and can lead to overfitting. So, we need to know when to stop? One way of doing this is to set a minimum number of training inputs to use on each leaf. Another way is to set maximum depth of your model. Maximum depth refers to the length of the longest path from a root to a leaf.

Pruning
The performance of a tree can be further increased by pruning. It involves removing the branches that make use of features having low importance. This way, we reduce the complexity of the tree and thus increasing its predictive power by reducing overfitting.

Pruning can start at either root or the leaves. The simplest method of pruning starts at leaves and removes each node with the most popular class in that leaf, this change is kept if it doesn't deteriorate accuracy. Its also called reduced error pruning. More sophisticated pruning methods can be used such as cost-complexity pruning where a learning parameter (alpha) is used to weigh whether nodes can be removed based on the size of the sub-tree. This is also known as weakest link pruning.

Advantages of CART

  1. Simple to understand, interpret, visualize.
  2. Decision trees implicitly perform variable screening or feature selection.
  3. Can handle both numerical and categorical data. Can also handle multi-output problems.
  4. Decision trees require relatively little effort from users for data preparation.
  5. Nonlinear relationships between parameters do not affect tree performance.



Comments

Post a Comment

Popular posts from this blog

Finally built a text classifier - Part 1

-
Image
A text classifier primarily uses machine learning principles to classify text into different categories. These supervised learning based classifiers are used in a variety of different places such as spam filters, user comment categorization, etc.  Text categorization is the grouping of documents into a fixed number of predefined classes. Each document can be in multiple, exactly one, or no category at all. Using machine learning, the objective is to classifiers from examples which perform the category tasks automatically. This is a supervised learning problem. Since categories may overlap, each category is treated as a separate group. Supervised Learning for Text Classification. PART-I : Training 1) During training, a feature extractor is used to transform each input value to a feature set. 2) These feature sets, which capture the basic information about each input that should be used to categorize it. 3) Pairs of feature sets and labels are
Read more

Linear Regression Theory

-
Image
The term "linearity" in algebra refers to a linear relationship between two or more variables. If we draw this relationship in a two-dimensional space (between two variables, in this case), we get a straight line. Linear regression assumes a linear or straight line relationship between the input variables (X) and the single output variable (y). More specifically, that output (y) can be calculated from a linear combination of the input variables (X). When there is a single input variable, the method is referred to as a simple linear regression. In simple linear regression, we can use statistics on the training data to estimate the coefficients required by the model to make predictions on new data. The line for a simple linear regression model can be written as: y = b0 + b1 * x where b0 and b1 are the coefficients we must estimate from the training data. This reminds me of my high school geometry lessons. It's funny how this points out that when we write the e
Read more