[MLE]Decision Trees

Overview

  • Decision Trees
  • Linear vs non-linear classifiers
  • Entropy
  • C4.5
  • Random Forests
  • Some fundamental concepts

The process of selecting a specific model, given a new input x, can be described by a sequential decision making process corresponding to the traversal of a binary tree (one that splits into two branches at each node). Here we focus on a particular tree-based framework called classification and regression trees

Basic Decision Trees

Decision trees apply a sequence of linear decisions, that often depend on only a single variable at a time. Such trees partition the input space into cuboid regions, gradually refining the level of detail of a decision until a leaf node has been reached, which provides the final predicted label

enter image description here
enter image description here

As the above figure indicates, we should follow the rules for tree classification:

  • Start at root node
  • Evaluate relevant attribute of that node
  • Follow branch according to attribute evaluation to descendent node
  • Descendent node can then be considered to be the root node of a subtree
  • Repeat until a Leaf node is reached, and assign associated label

Learning trees

  • Given a set of data D = {X,y}, we want to find a tree structure and decision criteria for each node n
  • Each node splits D into two(or more) disjoint subsets \(D_{l,i}\)
  • If all labels \(y_{l,i}\) are of the same label \(c_j\)∈ C, the subset is said to be pure, and this would signify a leaf node and termination of(this part of) the tree generation procedure.
  • otherwise node will be used to further split data
  • It is not always desirable to reach pure subsets, so termination strategies need to be a bit more sophisticated

CART

  • CART = Classification And Regression Trees
  • Generic framework for designing decision tree algorithms
  • Six general questions to decide algorithm(not list here)
  • We prefer simple, compact trees, following Occam’s Razor
  • To do so, we will seek to minimise impurity of data reaching descendent nodes

There are two kinds of ways of calculate impurity:

Entropy Impurity

enter image description here
Say node N has 10 examples of class C1, and 30 examples of class C2. Calculate the entropy impurity:
\(i(N) = -(10/40 log_2(10/40) + 30/40log_2(30/40))\) = 0.8113

Gini/Variance Impurity

enter image description here

  • upper one is variance, lower one is Gini

Misclassification impurity

enter image description here

The graph of three impurity measures

enter image description here

Twoing Criterion

  • Strategy for dealing with large multi-class problems
  • Split data for all classes C at node N into groups with subsets of classes \(C_1\) and \(C_2\), where \(C_2 = C - C_1\)
  • Then proceed to treat the problem to be binary classification with \(\widehat{C_1} = C_1 and \widehat{C_2} = C_2\)
  • Repeat with assigning \(C_1\) until you find the class with the highest information gain
  • Once a node is determined to be a leaf node, it has to be assigned a category label \(C_l\)
  • This is done by simply looking at the majority category of all examples in this leaf node \(N_l\)
  • \(C_l = argmax_j P(C_j)\)

Overfitting

A hypothesis is said to be overfit if its prediction performance on the training data is overoptimistic compared to that on unseen data.
It presents itself in complicated decision boundaries that depend strongly on individual training examples.
enter image description here

  • The first graph seems to be more accurate, but it is overfitting

Stopping Criteria

Reaching a node with a pure sample is always possible but usually not desirable as it usually causes over-fitting
Three common ways to decide to stop splitting:

  • Validation set
  • Cross-validation
  • Hypothesis testing
    enter image description here
  • What we’ve got now is Training set, Validation set and Test set
  • Keep splitting nodes level by level, or even node by node, using only the training data to learn decisions, until the error on the validation set stops going down

Cross-validation

In n-fold cross-validation, a dataset is split into n roughly equally sized partitions, such that each example is assigned to one and only one fold. At each iteration a hypothesis is learned using n-1 folds as the training set and predictions are made on the n’th fold.This is repeated until a prediction is made for all n examples, and an error rate for the entire dataset is obtained.
Cross-validation maximises the amount of data available to train and test on, at cost of increased time to perform the evaluation.
enter image description here

  • Split training data in a number of folds
  • For each fold, train on all other folds and make predictions on the held-out test fold
  • Combine all predictions and calculate error
  • If error has gone down, continue splitting nodes, otherwise, stop

Pruning

  • First fully train a tree, without stopping criterion
  • After training, prune tree by eliminating pairs of leaf nodes for which the impurity penalty is small
  • More complex methods are also possible

Missing attributes

  • It is common to have examples in your dataset with missing attributes/variables
  • One way of training a tree in the presence of missing attributes is removing all data points with any missing attributes
  • A better method is to only remove data points that miss a required attribute when considering the test for a given node for a given attribute

Random forests

enter image description here

  • Variety of methods to create random forest:
  • Use bootstrapping/bagging to initialise each tree with different data
  • Use only a subset of variables at each node
  • Use a random optimisation criterion at each node
  • Project feature on a random different manifold at each node

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an...
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If...
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t...
阅读全文