STAT605 CHAPTER 3

Basic Non-Parametric Supervised ML Methods for Regression

 Contents
CONTENTS
3.1) Regression Trees
3.2) K-Nearest Neighbour
SECTION 3.1

REGRESSION TREES
CONTENTS Split the sample into training and
test set

DATA Recode categorical variables using

PREPROCESSING dummy or indicator variables

STEPS
Attribute scaling (Standardization
of the attributes to be used in the
model)
CART Models
• Classification and regression trees (CART) are decision-tree procedures that are used
to classify cases and to make predictions

• Each decision tree is essentially a flow chart of a sequence of questions and answers:
o A classification tree is produced if the response is categorical
o A regression tree is produced if the response is quantitative

• During the training procedure of such trees, the data is recursively split into mutually
exclusive subgroups based on a set of ‘yes/no’ answers to questions pertaining to the
state of the attributes/predictors.

• CART can capture complex interactions and non-linear relationships in the data, which
traditional statistical techniques cannot easily deal with
• CART does not rely on any statistical
models and does not contain any
complex mathematical equations

• It is free from parameters and is thus

easy to interpret and understand

• In addition, the way in which the

attributes are ordered in splitting the
tree (or the training data) in to the
different subgroups pertaining to the
different values of the response variable
is somewhat related to the importance
of the attributes and how they interact CART model is represented as a tree displaying
with one another (downward flow) binary splits in the case of numeric predictors
• To construct a tree, the CART Root node
algorithm starts at the root node
where it partitions all of the Branches
observations into two mutually
exclusive groups according to the
split value of a given predictor

• These groups form two child

nodes, whereas the producing node
is called the parent node

• Commonly, the set of observations

to the left of the split correspond
to ‘Yes’, and those to the right
correspond to ‘No’. Leaf/terminal nodes
 Attributes can be reused at different levels of the tree
• As the tree grows downwards,
and based on different split values
further splitting takes place so that
the number of observations
contained within each leaf node
becomes less and less

• Attributes may be re-used at

any node or level in the tree, and
based on different splits, which
enables CART algorithms to
capture complex and non-linear
relationships in the data
𝑦ො =
• The terminal leaf nodes of the
The predicted target values are determined by taking the
tree contain a predicted value for average value of the target among the training observations
the target variable (y) remaining within that terminal node
Determining the split:
• Involves determining which attribute to split, as well as the best split point for that
variable
• The selection of which input variable/attribute to use and the specific split or cut-point
is chosen using a greedy algorithm to minimize a cost function.
• Tree construction ends using a predefined stopping criterion, such as a minimum
number of training instances/observations assigned to each leaf node of the tree

Greedy Splitting
• All input variables and all possible split points are evaluated and chosen in a greedy
manner (i.e. the very best split point is chosen each time).
• For regression trees (as opposed to classification trees), the cost function that is
minimized to choose split points is the sum of the squared error terms (SSE) across all
training samples that fall within the split.
Example:
A new drug has been developed to cure the common cold. However, we need to
determine the optimal dosage for patients. A clinical trial is carried out amongst a sample
of n=33 patients to determine the drug effectiveness (from 0 to 100%) according to
various dosages:

The data is split in to

training (n=19) and test
(n=14) subsets.
If the training data looked like this, we could easily fit some form of linear regression
model to accurately predict the drug effectiveness for different doses.
But what if the training data looked like this?
In this case it would not
make sense to fit a
straight line.

So we need to use
another method for
prediction, such as a
regression tree, given that
there are clearly visible
groupings of the target
value among the n=19
observations in the data.
For example, we could create a tree by splitting the observations in to groups as follows:
N=19

N=6 N=13

𝑦ො N=4 N=9

𝑦ത = 4.2 N=5 N=4

For example, we could create a tree by splitting the observations in to groups as follows:

𝑦ത = 2.5
For example, we could create a tree by splitting the observations in to groups as follows:

Dosage ≥ 14.5

𝑦ത = 52.8
Dosage < 29
 For example, we could create a tree by splitting the observations in to groups as follows:

𝑦ത = 100

Dosage ≥ 14.5

Dosage < 29

Dosage < 23

Question: How can we obtain such a tree without manually doing this, and including multiple
attributes, rather than for such a one-dimensional example?
Example using multiple attributes:

Dosage Age Gender Drug Efficiency

10 25 Female 98
20 73 Male 0
35 54 Female 6
5 12 Male 44
⋮ ⋮ ⋮ ⋮

At each node, every attribute is considered as a split candidate. The attribute that
produces the lowest SSE is selected.

NOTE: Only a binary split is considered when applying the CART method
How is the split in the attribute selected?
• The split in the attribute is selected based on the point at which the sum of the errors
between the predicted values and the actual values is minimized (SSE is minimized).

But how is SSE obtained?

The first split considered
is between the two
Consider finding smallest observations for
the optimal dosage…
binary split for
the attribute
drug dose:
The dosage value at this split is the average between the dosages of the two observations:

𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑑𝑜𝑠𝑎𝑔𝑒 = 3 Dosage < 3

N=1 N=18

𝑦ො = 0 𝑦ො = 38.0

The (average) drug The average drug

effectiveness (𝑦)
ത of the effectiveness (𝑦)
ത among
one observation to the the 18 observations to
left of the line the right of the line
Now let’s find the error for this split….
Dosage < 3
Let’s start by considering the error to the left of the split:

Dosage < 3
𝑦ො = 0 𝑦ො = 38.0

∴ 𝐸𝑟𝑟𝑜𝑟 = 𝑦 − 𝑦ො
𝑦=0 =0−0
=0
Next, let’s find the error for all of the observations to
the right of the split (dosage ≥ 3), using the
predicted drug effectiveness 𝑦ො = 38: Dosage < 3
Dosage ≥ 3

𝑦ො = 0 𝑦ො = 38.0

The error between the predicted

𝑦ො = 38 and actual drug effectiveness is then
the vertical distance between each
point and the line for 𝑦ො = 38.
To obtain SSE associated with this first candidate split
value of 3, we add the square of all of the errors to Dosage < 3
both the left and the right of the split:
Average Dosage = 3
𝑦ො = 0 𝑦ො = 38.0

SSE = (0-0)2
+

𝑦ො = 38
= 27 468.5

The same process is followed for

the next split…
The second split considered is between the next two Dosage < 5
observations: This gives an average dosage of 5

𝑦ො = 0 𝑦ො = 41.1

This gives us new

𝑦ො = 41.1 predictions, and new
errors/residuals.

SSE is then calculated

for this split.
This process is then repeated for all possible splits of dosage between two observations...

For this example, we can graph SSE for each split of dosage:

The lowest value

of SSE is 19564.

SSE is minimized for a split

14.5
dosage value of 14.5.
This exact process is followed for every other attribute.

However, for gender, there is only one split point:

𝑦ത = 12 𝑦ത = 40 N=9 N=10

Thus, there will only be

one SSE for this attribute.
SSE is then compared for each attribute (based on the best split for each):

…and we pick the

candidate with the
lowest value.
• Since a threshold value of 50 for age had the lowest SSE, it becomes the root node

• Then we continue to grow the tree in the same manner, where every attribute is again
considered as a candidate for splitting the new nodes

Age > 50

• However, at each of these new nodes, the data is a subset based on the split at the
parent node. Hence, we have to completely redo the exercise as a split value of 14.5
for dosage may no longer be the best split value amongst the sub-divided observations

• When a leaf has less than a minimum number of observations, we stop dividing them
For example, suppose we stop growing the tree when a leaf contains less than 7
observations...
Age > 50

N=6 N=13

𝑦ത = 4 𝑦ො = 4%

For age > 50, we only have 6 observations

which yield an average drug effectiveness of
𝑦ത = 4%.
This then is the stopping point for that
node, which becomes a leaf with a
predicted drug effectiveness of 4%.
However, for age ≤ 50, since there are more than 7 observations, the process of splitting
these observations continues.
Age > 50

N=6 N=13

𝑦ො = 4%

Note: This new subset of N=13

observations will produce different SSE
values for the candidate splits points of
each attribute.
Pruning Regression Trees:
To increase the generalizability of a regression tree to unseen data, a process called pruning
is performed. To explain this process, consider the original example of using just drug
dosage to predict drug effectiveness:
This tree does a good job on the training data, as the predicted effectiveness at each
terminal node is very close to the actual effectiveness of the various observations in each
respective terminal node (predicted value is given by the black line in the graph, which is
the average of those observations).
However, how does the tree perform on the testing set given by the red circles?
Remember, we need to compare actual observed target values (drug effectiveness)
against the predicted which is represented by the black line….
The first and last group of test observations are fairly close to the predicted. However,
for the middle groups, there is a much bigger error…
Now the original training points look like outliers.

This means that the regression tree is overfit to the training data!
One way to prevent overfitting of a regression tree to the training data, is to remove
some of the leaves i.e. to have fewer splits or groupings in the data.

N=19

N=6 N=13

N=4 N=9

N=5 N=4
We then replace the split with a leaf or terminal node that is the average of the new
larger subset of observations.

N=19

N=6 N=13

N=4 N=9
This will result in higher errors on the training data.
This will result in higher errors on the training data.

However, the new sub-tree will do much better on the testing set.
• Therefore, the main idea behind pruning a regression tree is to prevent overfitting of
the training data so that the tree does better in generalizing to new unseen data.
• The tree could be pruned even more :

• In theory, the pruning can continue until there is only one leaf in the tree (which results
in a predicted response that is simply equal to the average of all of the observations in
the training set).
Question: How do we decide which trained regression tree to use?

• We could obtain the total error sum of squares (SSE) for each tree

• HOWEVER, SSE naturally gets larger and larger on the training data as the tree is
pruned more and more

• This makes sense as the whole point in pruning a tree is so that it does not fit the
training data as well as the full sized tree.
• A method called Weakest Link Pruning is used to determine the optimal size tree
by calculating a Tree Score:
Any further splitting that does not
decrease the overall lack of fit (i.e.
Tree Score = SSE + Tree Complexity Penalty SSE) by a factor of α should not be
attempted as it will increase the
= SSE + 𝛼T Tree Score.

where the complexity penalty is a function of the number of leaves/terminal nodes

(T) in the tree, and 𝛼 > 0, a hyperparameter (known as the complexity parameter).

• The tree complexity penalty compensates for the difference in the number of leaves.
• The tree/subtree with the lowest score is then used for prediction as it is deemed to
have found the optimal balance between bias and variance
• Cross validation is used to determine the optimal tree size and the associated 𝛼 > 0
• The main role of the complexity parameter is to save computing time by pruning off
splits that are obviously not worthwhile.
SECTION 3.2

K-NEAREST NEIGHBOUR
CONTENTS Split the sample into training
and test set

DATA Recode categorical variables

using dummy or indicator
PREPROCESSING variables
STEPS
Feature scaling (Standardization
of the variables to be used in
the model)
Eager Learners:

• The regression methods discussed so far – linear regression, regression trees – are all
examples of eager learners

• Support Vector Machines and Neural Networks are also eager learners

• When given a set of training data points, eager learners will construct a generalization
model before receiving new (e.g. test) data points to predict

• We can think of the learned or trained model as being ready and eager to predict the
response for new unseen data points
Lazy Learners:
• Consider a contrasting lazy approach, in which the learner instead waits until the last
minute before doing any model construction to predict the response for a given test
data point

• That is, when given a set of training data points, a lazy learner (also known as an
instance-based learner) simply stores it (or does only a little minor processing) and
waits until it is given a test data point

• Only when it sees the test data point does it perform generalization to predict the
response for the data point based on its similarity to the stored training data points

• Unlike eager learning methods, lazy learners do less work when a training data point is
presented and more work when making a classification or numeric prediction

• The 𝑘-Nearest Neighbour (KNN) method is a lazy learner

K-Nearest Neighbour:
• KNN is a simple algorithm that stores all available labelled cases in the training data
and predicts the numerical target for unseen data according to the average response
value observed in the training data among a predefined number (𝑘) of nearest
neighbours to the unseen data point
• The nearest neighbours can be based on
different proximity measures.
Consider the example alongside:
We could fit a linear regression model to
these observations.
However, we can also approximate the results
of the linear method in a conceptually simpler
way using the KNN approach
In the case of using KNN for prediction, our
‘regression’ in this case won’t be a single
formula like an OLS model would give us, but
rather a best predicted output value for any
given input.

Consider the value of -0.75 on the x-axis,

which is marked with a vertical line…
i.e. imagine an unseen data point whose true
y-value is unknown, but which has an x-value
of -0.75…
-0.75
Without solving any equations, we can
come to a reasonable approximation of
what the y-value for the unseen data point
is likely to be just by considering the
nearby points in the training set…
It makes sense that the predicted value
should be near these points, not much
lower or higher.

A good prediction may be the average y-

value of the nearby training points.
You can imagine doing this for all the
possible input values and coming up
with predictions (red dots)
everywhere…
 Connecting all these predictions (red dots) with a line gives us our regression:

In this case, the results aren’t a clean line, but

they do trace the upward slope of the data
reasonably well.

This may not seem terribly impressive, but

one benefit of the simplicity of this KNN
implementation is that it handles non-
linearity well, and is highly flexible.

*Note that when there is more than one attribute being considered, you need
to visualize the location of these points being in a higher dimensional space.
Consider another example which shows a non-linear relationship now:

• There are parametric extensions to the

linear regression model that can be applied
to handle this type of relationship
• However, it requires the use of non-linear
or interaction terms, meaning that the data
scientist has to make some decisions about
what sort of data engineering to perform
• The KNN approach requires no such
decisions — the same algorithm used on
the linear example can be re-used entirely
on the new data to yield a workable set of
predictions
How is 𝒌 chosen?
• There is no structured method to find the best value for “𝑘”. It is determined via trial
and error (i.e. through cross-validation) using several different values of k

• Choosing smaller values for 𝑘 can be noisy and usually yields less stable results as it
tends to lead to over-fitting on the training data, and high variance

• Larger values of 𝑘 will have smoother models which mean a lower variance but
increased bias

• However, larger values of 𝑘 are computationally expensive (requires a lot of computing

power and time)
Setting a higher value of 𝑘 helps to avoid
overfitting, though you may start to lose
predictive power on the margin, particularly
around the edges of the data set.

Consider the first example dataset with

nearest-neighbour predictions made with 𝑘
set to 1:

• The predictions jump around erratically as

the model jumps from one point in the
dataset to the next!
By contrast, setting 𝑘=10 yields a much smoother ride:
• Generally, the regression looks smoother, but
there is something of a problem near the ends

• Because the model is taking so many points into

account for any given prediction, accuracy drops
close to the ends of the range of the attribute/s,
because the predictions only become influenced
by nearest observations either to the right or to
the left of the data point (rather than being
influenced by nearest observations all around)

• It is possible to address this issue by applying

weightings to the predictions to the nearer
points, though this comes with its own trade-offs.
When setting up a KNN model, there are only a handful of parameters that need to be
chosen, or that can be tweaked to improve performance:

1. Weights:
o When weights are applied, nearer points will contribute more to the average
prediction than points further away (weighted average of observed response values)
2. k (the number of neighbours):
o As discussed, increasing 𝑘 will tend to smooth out decision boundaries, avoiding
overfit at the cost of some resolution
o There is no single value of 𝑘 that will work for every single dataset
3. Distance Metric:
o There are different ways to measure how ‘close’ two points are to each other
o The differences between these methods can become significant in higher
dimensions when there are many predictors or attributes
Distance Metrics: Measures the Euclidean distance
between points i and j when there
are p attributes.
Most commonly used is Euclidean distance:
2 2 2
𝑑 𝑖, 𝑗 = 𝑥𝑖1 − 𝑥𝑗1 + 𝑥𝑖2 − 𝑥𝑗2 + ⋯ + 𝑥𝑖𝑝 − 𝑥𝑗𝑝

Another measure is the Manhattan distance:

𝑑 𝑖, 𝑗 = 𝑥𝑖1 − 𝑥𝑗1 + 𝑥𝑖2 − 𝑥𝑗2 + ⋯ + 𝑥𝑖𝑝 − 𝑥𝑗𝑝

More generally, these are actually both forms of what is called Minkowski distance:
ℎ ℎ ℎ ℎ
𝑑 𝑖, 𝑗 = 𝑥𝑖1 − 𝑥𝑗1 + 𝑥𝑖2 − 𝑥𝑗2 + ⋯ + 𝑥𝑖𝑝 − 𝑥𝑗𝑝

where ℎ is a real number such that ℎ ≥ 1. It represents the Manhattan distance when
ℎ = 1 and Euclidean distance when ℎ = 2.
Scaling/normalizing:
• Similar to regularization methods, KNN models can be thrown off if different features
or attribute variables have very different scales

• Consider a model that tries to predict the sales price of a house using the KNN
approach by taking the average sales price of other houses with very similar features to
the house in question, in terms of number of bedrooms, and total area in square feet:
o In reality, a 2000 sq. foot house with 2 bedrooms is essentially identical to a 2010 sq. foot house with
two bedrooms — 10 sq. feet hardly makes a difference
o By contrast, a 2000 sq. foot house with 3 bedrooms is very different, and represents a possibly less
cramped layout
o A naive computer wouldn’t have the context to understand that, however. It would identify the 3-
bedroom house as being only ‘one’ unit away from the 2-bedroom house, and would therefore treat
it as a closer neighbour than the 2010 sq. foot house

• Attributes must therefore be scaled before implementing a KNN model.

Strengths of KNN:

• KNN models are easy to implement and handle non-linearities well

• Fitting the model also tends to be quick as the computer doesn’t have to calculate any
particular parameters or values
Weaknesses of KNN:
• While the model is quick to set up, it is slower to predict, since in order to predict an
outcome for a new value, it will need to search through all the points in its training set
to find the nearest ones

• For large datasets, KNN can be a relatively slow method compared to other
regressions that may take longer to fit but then make their predictions with relatively
straightforward computations

• One other issue with a KNN model is that it lacks interpretability. An OLS linear
regression will have clearly interpretable coefficients that can themselves give some
indication of the direction and ‘effect size’ of a given attribute

• KNN models cannot be used for feature selection, in the way that a linear regression
with an added cost function term, like ridge or lasso, can be, or the way that a decision
tree implicitly chooses which features seem most important