Classification (1)

COMP9417 Machine Learning & Data Mining

Aims

This lecture will introduce you to machine learning approaches to the

problem of classification. Following it you should be able to reproduce
theoretical results, outline algorithmic techniques and describe practical
applications for the topics:
• a framework for solving classification problems
• the use of a linear model as a 2-class classifier
• logistic regression classification algorithm
• describing issues of generalisation and evaluation for classification
• describing distance measures and how using them in classification
• the basic k-nearest neighbour classification method

COMP9417 1
Introduction

Classification (sometimes called concept learning) methods dominate

machine learning . . .

. . . however, they often don’t have convenient mathematical properties

like regression, so are more complicated to analyse. The idea is to
learn a classifier, which is usually a function mapping from an input
data point to one of a set of discrete outputs, i.e., the classes.

We will mostly focus on classifier advantages and disadvantages as

learning methods first and point to unifying ideas and approaches
where applicable.

COMP9417 2
Classification

Example: Imagine that we want to automate the process of sorting

incoming fish in a fish-packing plant. And as a pilot, we start by
separating sea bass from salmon using some information collected
through sensing.

COMP9417 3
Classification
Example: classifying sea bass vs. salmon
Features that can be used: width, length, weight, lightness, fins,
eyes/mouth position, etc.
Question: how to separate these two classes?
Width Sea bass

Salmon

Lightness

COMP9417 4
Classification

Example: Maybe we can find a line that separates the two classes.

Width Sea bass

Salmon

Lightness

COMP9417 5
Classification
Example: If we find the line that separated the two classes, then how
our algorithm makes prediction?

The line equation will look like: X2 : Width Sea bass

𝑎𝑥1 + 𝑏𝑥2 + 𝑐 = 0
We can define 𝑎, 𝑏 & 𝑐 such that:
for any point above the line: Salmon
𝑎𝑥1 + 𝑏𝑥2 + 𝑐 > 0
and for any point below the line:
𝑎𝑥1 + 𝑏𝑥2 + 𝑐 < 0
X1 : Lightness
This type of classifier is called linear classifier. It is also a type of
discriminative learning algorithm.

COMP9417 6
Classification

Example:
Can we do something different than finding the discriminative line (or
some boundary) to be able to separate the two groups?

Width Sea bass

Salmon

Lightness

COMP9417 7
Classification
Example:
Instead of finding a discriminative line, maybe we can focus on one class at a time and build a model
that describes how that class looks like; and then do the same for the other class. This type of models
are called generative learning algorithm.

Width

Lightness

COMP9417 8
Classification
Generative algorithm: builds some models for each of
the classes and then makes classification predictions
based on looking at the test example and see it is more
similar to which of the models.
– Learns 𝑝(𝑥|𝑦) (and also 𝑝 𝑦 , called class prior)
– So, we can get 𝑝 𝑥, 𝑦 = 𝑝 𝑥 𝑦 𝑝(𝑦)
– It learns the mechanism by which the data has
been generated

Discriminative algorithm: Do not build models for

different classes, but rather focuses on finding a
decision boundary that separates classes
– Learns 𝑝(𝑦|𝑥)

COMP9417 9
Classification

• In a generative algorithm, to predict the output for sample 𝑥, we

have to estimate 𝑝(𝑦|𝑥):
𝑝 𝑥 𝑦 = 0 𝑝(𝑦 = 0)
𝑝 𝑦=0𝑥 =
𝑝(𝑥)
𝑝 𝑥 𝑦 = 1 𝑝(𝑦 = 1)
𝑝 𝑦=1𝑥 =
𝑝(𝑥)

If 𝑝 𝑦 = 0 𝑥 > 𝑝 𝑦 = 1 𝑥 , then 𝑥 belongs to class 𝑦 = 0 and

otherwise to class 𝑦 = 1.

• In a discriminative algorithm, we can directly have 𝑝 𝑦 = 0 𝑥 and

𝑝 𝑦 = 1 𝑥 and similar to above, if 𝑝 𝑦 = 0 𝑥 > 𝑝 𝑦 = 1 𝑥 , then 𝑥
belongs to class 𝑦 = 0 and otherwise to class 𝑦 = 1.

COMP9417 10
Linear classification in two dimensions
x2 : Width
Positive class

w Negative class

x1 : Lightness

• We find the line that separates the two class: 𝑎𝑥1 + 𝑏𝑥2 + 𝑐 = 0
• We define a weight vector 𝑤 𝑇 = [𝑎, 𝑏], 𝑥 𝑇 = [𝑥1 , 𝑥2 ]
• So, the line can be defined by 𝑥 𝑇 𝑤 = −𝑐 = 𝑡
• 𝑤 is perpendicular to decision boundary (in direction of positive
class)
• 𝑡 is the decision threshold (if 𝑥 𝑇 𝑤 > t then 𝑥 belongs to positive
class and if 𝑥 𝑇 𝑤 < t then 𝑥 belongs to negative class)
COMP9417 11
Basic Linear Classifier

The basic linear classifier constructs a decision boundary by half-way

intersecting the line between the positive and negative centres of mass.

Width Sea bass

Salmon

Lightness

COMP9417 12
Basic Linear Classifier

The basic linear classifier is described by the equation 𝑥 𝑇 𝑤 = 𝑡, and

𝑤 =𝑝−𝑛
𝑝+𝑛
As we know, 2
is on the decision boundary, so we have:
𝑝+𝑛 𝑇 | 𝑝 |2 − ||𝑛||2
𝑡= (𝑝 − 𝑛) =
2 2
Where | 𝑥 |, denotes the length of vector 𝑥

COMP9417 13
 Logistic Regression
a probabilistic linear classifier

COMP9417 14
Logistic Regression

• In a binary classification problem with one input variable, if we show the

output on y-axis we may get something like below:

• Can we use a linear regression to model this data?

COMP9417 15
Logistic Regression

Why regular regression doesn’t work here:

• Univariate or multivariate regressions are to predict a real-valued output

from one or more independent variables
• Binary data doesn’t have a normal distribution which is a condition
needed for most other types of regression
• What we expect to get is an output of 0 or 1, but linear regression
obviously can produce values beyond that range.

COMP9417 16
Logistic Regression
• In binary classification, we can transform the y values into probability values
(values are in range [0,1])

P(y=1|x)
• We can model this with a s-curve (sigmoid curve)
as above:

1 x
𝑃 𝑦=1𝑥 =
1 + 𝑒 −𝑓(𝑥)

𝑓 𝑥 = 𝑥𝑇𝛽

1
Consequently: 𝑃 𝑦 = 0 𝑥 = 1 − 𝑃 𝑦 = 1 𝑥 = 1 −
1+𝑒 −𝑓(𝑥)

COMP9417 17
Logistic Regression

Logistic regression seeks to:

• Model the probability of a class given the values of independent input

variables
• Estimate the probability that a class occurs for a random observation
(versus the probability that the class doesn’t occur)
• Classify an observation based on the probability estimations

COMP9417 18
Logistic Regression
1
𝑃෠ 𝑦 = 1 𝑥 = 𝑇𝛽
1 + 𝑒 −𝑥

If 𝑃 𝑦 = 1 𝑥 ≥ 0.5 (same as saying 𝑥 𝑇 𝛽 ≥ 0) then predict as class 1

If 𝑃 𝑦 = 1 𝑥 < 0.5 (same as saying 𝑥 𝑇 𝛽 < 0) then predict as class 0

• Interpretation of this model in the input space (feature space) is equivalent

of having a linear decision boundary (𝑥 𝑇 𝛽 = 0) separating the two classes

• Now we have a linear solution to our problem, and this is what makes
Logistic Regression a linear model.

COMP9417 19
Logistic Regression Parameter Estimation

Let’s define 𝑃෠ 𝑦 = 1 𝑥 = ℎ𝛽 (𝑥) and 𝑃෠ 𝑦 = 0 𝑥 = 1 − ℎ𝛽 (𝑥)

• We can define this probability in one line using 𝑦 ∈ {0, 1}:

1−𝑦
𝑃෠ 𝑦 𝑥 = ℎ𝛽 𝑥 𝑦 1 − ℎ𝛽 𝑥

• And use the maximum likelihood principle:

𝑚
෠
ℓ 𝛽 = log ℒ 𝛽 = log ෑ 𝑃(𝑦|𝑥)
𝑖=1
𝑚
𝑦(𝑖) 1−𝑦(𝑖)
= log ෑ ℎ𝛽 𝑥 (𝑖) 1 − ℎ𝛽 𝑥 (𝑖)
𝑖=1
𝑚
= ෍[𝑦 (𝑖) log ℎ𝛽 𝑥 𝑖 + 1−𝑦 𝑖 log(1 − ℎ𝛽 𝑥 𝑖 )]
𝑖=1

COMP9417 20
Logistic Regression Parameter Estimation
𝑚
1
𝐽 𝛽 = − ෍[𝑦 (𝑖) log ℎ𝛽 𝑥 𝑖 + 1−𝑦 𝑖 log(1 − ℎ𝛽 𝑥 𝑖 )]
𝑚
𝑖=1

• This cost function is convex (single global minimum) but there is no closed
form solution
• We can use the Gradient Descent algorithm.
• We can not use a similar cost function as we used in linear regression here,
because it will result a non-convex function with many local minimums and
would be very difficult to find the global minimum.

COMP9417 21
Logistic Regression
Pros:
– Relatively easy to implement
– Easy to interpret
– Relatively fast at training and very fast at testing
– Can easily extend to multi-classes
– Provide probabilistic predictions
Cons:
–Prone to overfitting in high-dimensional data (one remedy:
regularization)
– It provides a linear decision boundary. For non-linear decision
boundaries, feature transformation is required
– Requires moderate or no correlation (collinearity) between input
variables, and may lead to poor model (dimensionality reduction is
useful)
– Sensitive to outlier

COMP9417 22
How solve a task with machine learning

An overview of how machine learning is used to address a given task. A

task (red box) requires an appropriate mapping – a model – from data
described by features to outputs. Obtaining such a mapping from
training data is what constitutes a learning problem (blue box).

COMP9417 23
Generalisation
Generalisation is a key objective of machine learning.

What we are really interested in is generalising from the sample of data

in our training set.

In machine learning, generalisation means how well a trained model

can classify or forecast unseen data. Training a generalised machine
learning model means, in general, it works for all subsets of unseen
data.

E.g., when we train a model to classify between dogs and cats, if the
model is provided with a dog image dataset with only two breeds, it
may obtain a good performance during training; But, it possibly gets a
low classification score when it is tested by other breeds of dogs as
well.
COMP9417 24
Generalisation

There are three basic assumptions for generalisation:

▪ Examples are drawn independently and identically (i.i.d) at
random from the distribution;
▪ The distribution is stationary; that is, the distribution doesn't
change within the data set
▪ We always pull from the same distribution (for training, validation
and test samples)

In practice, we sometimes violate these assumptions.

COMP9417 25
Train-and-test

Also known as out-of-sample testing is validation technique to assess the

results of a model to an independent data set

1. Holdout method:

Train Test

COMP9417 26
 Train-and-test

2. Leave-One-Out Cross validation (LOOCV):

Test
Iteration 1

Iteration 2

Iteration 3

Iteration 4
.
.
.
Iteration m

COMP9417 27
 Train-and-test

3. K-fold Cross Validation

Iteration 1

Iteration 2

Iteration 3

Iteration 4
.
.
.
Iteration 7

COMP9417 28
Cross-validation

There are certain parameters that need to be estimated during learning.

We use the data, but NOT the training set, OR the test set. Instead, we
use a separate validation or development set.

COMP9417 29
Cross-validation
Validation set: To make the hyperparameter tuning and model selection
independent from the test set, we define another set within the train set

Train Validation Test

COMP9417 30
Data Types

In Machine Learning world, in general two types of data is defined:

o Numerical: Anything represented by numbers (e.g., integer ,
floating point)
o Categorical: everything that is not numerical (e.g. discrete
labeled groups)

In general, for machine learning algorithms, data has to be represented

in numeric form

COMP9417 31
Data Types

Another taxonomy of data types:

[Link]: it might be represented with strings or numbers

but has no relationship with the outcome (e.g. participants
name or code)
[Link]: discrete values with no numerical relationship
between different categories (e.g. animal types, colors,
nationality)
[Link]: discrete data with only two possibilities (e.g
cancerous vs. non-cancerous)

COMP9417 32
Data Types

4. Ordinal: discrete integers that can be ranked, but the

relative distance between any two number can not be
defined (e.g., students rank based on GPA)
5. Count: discrete whole numbers without any negatives
6. Time: a cyclical, repeating continuous form of data (e.g
days, weeks)
7. Interval: data that the we can measure the distance
between different values and is measured against a scale.
(e.g., temperature, income)

COMP9417 33
Binary Classification task

In a binary classification (or binomial classification) task, we always

want to classify the data of a given set into two groups. We usually
define one of the classes as positive and one as negative.
o Sometimes the classes are equally important (e.g.,
recognition of dog vs cat in image classification
o Sometimes misclassification in one of the classes is more
costly than misclassification in the other class (e.g.,
predicting that someone has cancer while (s)he doesn’t have
vs predicting that someone doesn’t have cancer while (s)he
has) therefore we may prefer to have a better classification in
one class in the cost of more errors in the other class.

COMP9417 34
Evaluation of error

If we have a binary classification, then we have two classes of y ∈

{0,1}, where we call the class 𝑦 = 1, positive class and 𝑦 = 0, negative
class.

Some evaluation metrics:

o True positive: number of instances from class one that have
been predicted as one
o True negative: number of instances from class zero that
have been predicted as zero
o False positive: number of instances from class zero that
have been predicted as one
o False negative: number of instances from class one that
have been predicted as zero

COMP9417 35
Contingency table

For two-class prediction case:

Positive Negative

Positive

Negative

This is also called confusion matrix

COMP9417 36
Classification Accuracy

Classification Accuracy on a sample of labelled pairs (𝑥, 𝑐(𝑥)) given a

learned classification model that predicts, for each instance 𝑥, a class
value 𝑐(𝑥):
Ƹ
1
𝑎𝑐𝑐 = ෍ 𝐼[𝑐Ƹ 𝑥 = 𝑐(𝑥)]
|𝑇𝑒𝑠𝑡|
𝑥∈𝑇𝑒𝑠𝑡

where 𝑇𝑒𝑠𝑡 is a test set and 𝐼[] is the indicator function which is 1 iff its
argument evaluates to true, and 0 otherwise.

𝐶𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝐸𝑟𝑟𝑜𝑟 𝑖𝑠 = 1 − 𝑎𝑐𝑐.

COMP9417 37
Other evaluation metrics

Precision/correctness
– is the number of relevant objects classified
correctly divided by the total number of relevant
objects classified
𝑇𝑃
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
𝑇𝑃 + 𝐹𝑃

Recall/sensitivity/completeness/true positive rate

(TPR)
– is the number of relevant objects classified
correctly divided by total number of
relevant/correct objects [Link]

𝑇𝑃
𝑅𝑒𝑐𝑎𝑙𝑙 =
𝑇𝑃 + 𝐹𝑁

COMP9417 38
Other evaluation metrics

F1 score: a measure of accuracy, which is the harmonic mean of

precision and recall and is defined as:
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 × 𝑟𝑒𝑐𝑎𝑙𝑙
𝐹1 = 2
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 + 𝑟𝑒𝑐𝑎𝑙𝑙
This measure gives equal importance to precision and recall which is
sometime undesirable; so, we have to decide which metric to use
depending on the task and what’s important for the task.

COMP9417 39
Other evaluation metrics

AUC-ROC curve: Area Under the Curve (AUC) – Receiver Operating

Characteristics (ROC) curve is one of the most important evaluation
metric for performance of classification models. This metric evaluates
the model at different threshold settings and can inform us on the
capability of the model in distinguishing between classes.

𝑇𝑃
• 𝑇𝑃𝑅 = 𝑇𝑃+𝐹𝑁
𝐹𝑃
• 𝐹𝑃𝑅 = 𝐹𝑃+𝑇𝑁 AUC

• A good model has 𝐴𝑈𝐶 close to 1

• A very poor model has 𝐴𝑈𝐶 close to 0
• 𝐴𝑈𝐶 = 0.5 means no class separation

COMP9417 40
Missing Value: An issue to consider

COMP9417 41
Missing Values

• In practice it rarely happens that the data is complete and

homogenous.
• Why data is incomplete:

o Human errors
o Sensor errors
o Software bugs
o Faulty preprocessing
o…

COMP9417 42
Missing Values

How to handle missing values (common approaches):

o Deleting samples with missing values

o Replacing the missing value with some statistics from the
data (mean, median, …)
o Assigning a unique category
o Predicting the missing values
o Using algorithms that support missing values

COMP9417 43
Missing Values

Deleting samples with missing values:

– Pros:
o A robust and probably more accurate model if missing is
random
– Cons:
o Loss of information and data
o Works poorly if the percentage of missing values is high

COMP9417 44
Missing Values

Replacing the missing value with mean/median/mode:

– Pros:
o When the data size is small, it is better than deleting
o It can prevent data loss
– Cons:
o Imputing the approximations adds bias to the model (it
reduces the variance of the variable)
o Works poorly compared to other methods

COMP9417 45
Missing Values

If categorical, assigning a unique category or the most frequent

category:
– Pros:
o Works well with small datasets and easy to implement
o No loss of data
– Cons:
o Unique category works only for categorical features
o Adding another feature (e.g., a new unique category) to the
model may result higher variance in the model
o Adding the most frequent category can increase the bias in
the model

COMP9417 46
Missing Values

Predicting the missing values:

– Pros:
o Imputing the missing variable is an improvement as long as
the bias from it is smaller than the omitted variable bias
o Yields unbiased estimates of the model parameters
– Cons:
o Bias also arises when an incomplete conditioning set is used
for a categorical variable
o Considered only as a proxy for the true values

COMP9417 47
Missing Values

Using algorithms that support missing values:

– Pros:
o Does not require creation of a predictive model
o Correlation of the data is neglected
– Cons:
o Some of these algorithms are very time-consuming and it can
be critical in data mining where large databases are being
extracted

COMP9417 48
Nearest Neighbor Algorithm for Classification

COMP9417 49
Nearest Neighbour

Nearest Neighbour

• Nearest Neighbour is a regression or classification algorithm that predicts whatever is

Nearest Neighbour is a
the output value regression
of the or point
nearest data classification algorithm that predicts
to some query.
whatever is the output value of the nearest data point to some query.
• To find the nearest data point, we have to find the distance between the query and
other points. So we have to decide how to define distance.
COM P9417 M L & DM Classificat ion (1) Term 2, 2019 33 / 72
COMP9417 50
Minkowski distance

Minkowski distance If 𝒳 → ℝ𝑑 , 𝑥, 𝑦 ∈ 𝜒, the Minkowski distance of order

𝑝 > 0 is defined as:
𝑑
𝑝 1ൗ𝑝
𝐷𝑖𝑠𝑝 𝑥, 𝑦 = (෍ |𝑥𝑗 − 𝑦𝑗 | ) = ||x − y||𝑝
𝑗=1

1
Where | 𝑧 |𝑝 = (σ𝑑𝑗=1 |𝑧𝑗 |𝑝 ) ൗ𝑝 is the 𝑝 − 𝑛𝑜𝑟𝑚 (sometimes denoted 𝐿𝑝
norm) of the vector 𝑧.

COMP9417 51
Minkowski distance

• The 2-norm refers to the familiar Euclidean distance

𝑛

𝐷𝑖𝑠2 𝑥, 𝑦 = ෍(𝑥𝑗 − 𝑦𝑗 )2 = (𝑥 − 𝑦)𝑇 (𝑥 − 𝑦)

𝑗=1

• The 1-norm denotes Manhattan distance, also called cityblock

distance:
𝑛

𝐷𝑖𝑠1 𝑥, 𝑦 = ෍ |𝑥𝑗 − 𝑦𝑗 |
𝑗=1

COMP9417 52
Minkowski distance

• If we now let 𝑝 grow larger, the distance will be more and more
dominated by the largest coordinate-wise distance, from which we
can infer that 𝐷𝑖𝑠∞ = 𝑚𝑎𝑥𝑗 |𝑥𝑗 − 𝑦𝑗 |; this is also called Chebyshev
distance.

• You will sometimes see references to the 0-norm (or 𝐿0 norm) which
counts the number of non-zero elements in a vector. The
corresponding distance then counts the number of positions in which
vectors x and y differ. This is not strictly a Minkowski distance;
however, we can define it as:
𝑑 𝑑

𝐷𝑖𝑠0 𝑥, 𝑦 = ෍(𝑥𝑗 − 𝑦𝑗 )0 = ෍ 𝐼[𝑥𝑗 ≠ 𝑦𝑗 ]

𝑗=1 𝑗=1

under the understanding that 𝑥 0 = 0 for 𝑥 = 0 and 1 otherwise.

COMP9417 53
Minkowski distance

Sometimes the data is not naturally in ℝ𝑑 , but if we can turn it into

Boolean features, or character sequences, we can still apply distance
measures. For example:

• If 𝑥 and 𝑦 are binary strings, this is also called the Hamming

distance. Alternatively, we can see the Hamming distance as the
number of bits that need to be flipped to change 𝑥 into 𝑦.

• For non-binary strings of unequal length this can be generalised to

the notion of edit distance or Levenshtein distance.

COMP9417 54
Circles and ellipses

Unite circles with different order-p Minkowski distance

• Notice that for points on the coordinate axes all

distances agree
• If we require a rotation invariant distance metric,
then Euclidean distance is our only choice

COMP9417 55
 Distance metric
Distance metric: Given an instance space 𝒳 , a distance metric is a
function 𝐷𝑖𝑠 ∶ 𝒳 × 𝒳 → 0, ∞ such that for any 𝑥, 𝑦, 𝑧 ∈ 𝒳:
1. distances between a point and itself are zero: 𝐷𝑖𝑠(𝑥, 𝑥) = 0
2. all other distances are larger than zero: if 𝑥 ≠ 𝑦 then 𝐷𝑖𝑠(𝑥, 𝑦) > 0
3. distances are symmetric: 𝐷𝑖𝑠(𝑦, 𝑥) = 𝐷𝑖𝑠(𝑥, 𝑦)
4. detours can not shorten the distance (triangle inequality):
𝐷𝑖𝑠(𝑥, 𝑧) ≤ 𝐷𝑖𝑠(𝑥, 𝑦) + 𝐷𝑖𝑠(𝑦, 𝑧)
o It can be shown that triangle inequality does not hold for 𝑝 < 1

If the second condition is weakened to a non-strict inequality – i.e.,

𝐷𝑖𝑠(𝑥, 𝑦) may be zero even if 𝑥 ≠ 𝑦 – the function 𝐷𝑖𝑠 is called a
pseudo-metric.
COMP9417 56
Exemplar

• Exemplar refers to a point that is used to summarise or represent a

larger group of data

• Exemplars are chosen because they are considered representative

of the patterns or characteristics found in the group they represent.

• In distance-based leaning, exemplars can be selected based on

their proximity to other points, with the aim of minimizing the
distance between the exemplar and each point in its cluster.

COMP9417 57
Exemplar

• E.g., the arithmetic mean of a set of data can be used as an

exemplar

• It can be shown that the arithmetic mean is the unique point that
minimizes the sum of squared Euclidean distances to those data
points

• If one looks for a point that minimizes the sum of Euclidean

distances, then that is geometric median

COMP9417 58
Means and distances

• In certain situations, it makes sense to restrict an exemplar to be

one of the given data points. In that case, we speak of a medoid, to
distinguish it from a centroid which is an exemplar that doesn’t have
to occur in the data.
• Finding a medoid requires us to calculate, for each data point, the
total distance to all other data points, in order to choose the point
that minimises it. Regardless of the distance metric used, this is an
𝑂 𝑛2 operation for 𝑛 points.

• So, for medoids there is no computational reason to prefer one

distance metric over another.

• There may be more than one medoid.

COMP9417 59
Distance-based models

To summarise, the main ingredients of distance-based models are:

• distance metrics, which can be Euclidean, Manhattan, Minkowski or

Mahalanobis, among many others;
• exemplars: centroids that find a centre of mass according to a
chosen distance metric, or medoids that find the most centrally
located data point.

COMP9417 60
Nearest Centroid Classifier

COMP9417 61
Nearest Centroid Classifier
• This is a classifier based on minimum distance principle, where the
class exemplars are just the centroids (or means)

• Training: for training sample pairs { 𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 , … , 𝑥𝑚 , 𝑦𝑚 }

where 𝑥𝑖 is the feature vector for sample 𝑖 and 𝑦𝑖 is the class label,
class centroids are:
1
𝜇𝑘 = ෍ 𝑥𝑗
|𝐶𝑘 |
𝑗∈𝐶𝑘
• Test: a new unknown object with feature vector 𝑥 is classified as
class 𝑘 if it is much closer to the mean vector of class 𝑘 than to any
other class mean vector

COMP9417 62
Basic Linear Classifier & Nearest Centroid
Classifier
• The basic linear classifier is distance-based.
• An alternative, distance-based way to classify instances without
direct reference to a decision boundary is by the following decision
rule: if 𝑥 is nearest to 𝜇 ⊕ then classify it as positive, otherwise as
negative; or equivalently, classify an instance to the class of the
nearest exemplar.
• If we use Euclidean distance as our closeness measure, simple
geometry tells us we get exactly the same decision boundary.
• So the basic linear classifier can be interpreted from a distance-
based perspective as constructing exemplars that minimise squared
Euclidean distance within each class, and then applying a nearest-
exemplar decision rule.

COMP9417 63
Nearest Centroid Classifier

• What happens if a class has more than one mode? (similar to the
image)
1. If there is only one centroid per class, then it will perform poorly
2. If we can somehow find different modes, we can define one
centroid per each mode which helps the classifier
generalizability

(1) (2)

COMP9417 64
Nearest Centroid Classifier

Advantages:
o Simple
o Fast
o works well when classes are compact and far from each
other.

COMP9417 65
Nearest Centroid Classifier

Disadvantages:
o For complex classes (e.g., Multimodal, non-spherical) may
give very poor results
o Can not handle outliers and noisy data well
o Can not handle missing data

COMP9417 66
Nearest neighbour classification

COMP9417 67
Nearest neighbour classification
• Related to the simplest form of learning: rote learning or
memorisation
o Training instances are searched for instance that most
closely resembles new or query instance
o The instances themselves represent the knowledge
o Called: instance-based, memory-based learning or case-
based learning; often a form of local learning

• The similarity or distance function defines “learning”, i.e., how to go

beyond simple memorisation

COMP9417 68
Nearest neighbour classification

• Intuitive idea — instances “close by”, i.e., neighbours or exemplars,

should be classified similarly

• Instance-based learning is lazy learning

o Methods: nearest-neighbour, k-nearest-neighbour, …

• Ideas also important for unsupervised methods, e.g., clustering

(later lectures)

COMP9417 69
Nearest Neighbour

Stores all training examples 𝑥𝑗 , 𝑓(𝑥𝑗 ) .

Nearest neighbour:

o Given query instance 𝑥𝑞 , first locate nearest training example

መ 𝑞 ) ← 𝑓(𝑥𝑛 )
𝑥𝑛 , then estimate 𝑓(𝑥

𝑘-Nearest neighbour:
o Given 𝑥𝑞 , take vote among its 𝑘 nearest neighbours (if
discrete-valued target function) (see next slide)
o take mean of 𝑓 values of 𝑘 nearest neighbours (if real-
valued)
σ𝑘𝑗=1 𝑓(𝑥𝑗 )
መ 𝑞) ←
𝑓(𝑥
𝑘

COMP9417 70
K-Nearest Neighbour (KNN) Algorithm

Training algorithm:
o For each training example 𝑥𝑗 , 𝑓(𝑥𝑗 ) , add the example to the
list training _examples.
Classification algorithm:
– Given a query instance 𝑥𝑞 to be classified,
o Let 𝑥1 ,…,𝑥𝑘 be the 𝑘 instances from training examples that
are nearest to 𝑥𝑞 by the distance function
o Return
𝑘
መ 𝑞 ) ← arg max ෍ 𝛿(𝜐, 𝑓(𝑥𝑗 ))
𝑓(𝑥
𝜐∈𝑉
𝑗=1

Where 𝛿 𝑎, 𝑏 = 1 if 𝑎 = 𝑏 and 0 otherwise.

COMP9417 71
Distance function again

• The distance function defines what is learned.

Instance 𝑥𝑗 is described by a feature vector (list of attribute-value
pairs)

𝑥𝑗 = (𝑥𝑗1 ,…, 𝑥𝑗𝑑 )𝑇

Where 𝑥𝑗𝑟 denotes the value of the 𝑟th attribute/feature of 𝑥𝑗 .

• Most commonly used distance function is Euclidean distance . . .

o distance between two instances 𝑥𝑖 and 𝑥𝑗 is defined to be

𝐷𝑖𝑠 𝑥𝑖 , 𝑥𝑗 = ෍(𝑥𝑖𝑟 − 𝑥𝑗𝑟 )2

𝑟=1

COMP9417 72
Distance function again

Many other distance functions could be used . . .

o e.g., Manhattan also referred to as city-block distance (sum
of absolute values of differences between attributes)
𝐷𝑖𝑠 𝑥𝑖 , 𝑥𝑗 = σ𝑑𝑟=1 |𝑥𝑖𝑟 − 𝑥𝑗𝑟 |

Vector-based formalization – use norm 𝐿1 , 𝐿2 , …

COMP9417 73
KNN Example
• What is the predicted class for the green point given the data for?

k=12

hℎ𝑡𝑡𝑝𝑠://𝑡𝑜𝑤𝑎𝑟𝑑𝑠𝑑𝑎𝑡𝑎𝑠𝑐𝑖𝑒𝑛𝑐𝑒.
t t p s : over over t o w a. r d s d a. t a. s c i. e𝑐𝑜𝑚/𝑘𝑛𝑛
n c e . c o m over k n n minus
− 𝑢𝑠𝑖𝑛𝑔 u s i. n g minus
− 𝑠𝑐𝑖𝑘𝑖𝑡 s c i. k −
− 𝑙𝑒𝑎𝑟𝑛 i. t 𝑐6𝑏𝑒𝑑765𝑏𝑒75
minus l e a. r n minus
c 6 b e d 765 b e 75

COMP9417 74
Normalisation and other issues

• Different attributes measured on different scales (for example, one

attribute/feature may have a range of [0,100] and another have a
range of [−1,1])

So, attributes have to be normalised (why ?)

COMP9417 75
Normalisation and other issues

• Min-max normalisation:
′
𝑥𝑗𝑟 − min(𝑥𝑗𝑟 )
𝑥𝑗𝑟 =
m𝑎𝑥 𝑥𝑗𝑟 − min(𝑥𝑗𝑟 )
′
where 𝑥𝑗𝑟 is the actual value of attribute/feature 𝑟 and 𝑥𝑗𝑟 is the
normalised value.

• Z-score is another popular normalisation

′ 𝑥𝑗𝑟 − 𝜇𝑟
𝑥𝑗𝑟 =
𝜎𝑟

• For nominal (categorical) attributes with no inherent ordering:

Usually simple matching distances is used. E.g., 1 if they are not the
same and 0 otherwise.

COMP9417 76
When To Consider Nearest Neighbour

• Instances map to points in ℝ𝑑

• Less than 20 attributes per instance
o or number of attributes can be reduced . . .
• Lots of training data
• No requirement for “explanatory” model to be learned

COMP9417 77
K-Nearest Neighbour

Advantages:
• Statisticians have used KNN since early 1950s
• Can be very accurate
• Training is very fast
• Can learn complex target functions

COMP9417 78
K-Nearest Neighbour
Disadvantages:

o Slow at query time: basic algorithm scans entire training data

to derive a prediction
o “Curse of dimensionality”
o Assumes all attributes are equally important, so easily fooled
by irrelevant attributes
▪ Remedy: attribute selection or weights
o Problem of noisy instances:
▪ Remedy: remove from data set
▪ not easy – how to know which are noisy ?
o Needs homogenous feature type and scale
o Finding the optimal number of neighbors (𝑘) can be
challenging
COMP9417 79
Nearest-neighbour classifier

• 1NN perfectly separates training data, so low bias but high variance

• By increasing the number of neighbours 𝑘 we increase bias and

decrease variance (what happens when 𝑘 = 𝑚 (𝑚 is the number of
observations)? )

• Easily adapted to real-valued targets, and even to structured objects

(nearest-neighbour retrieval). It can also output (poor) probabilities
estimates when 𝑘 > 1

COMP9417 80
Distance-Weighted KNN

• Might want to weight nearer neighbours more heavily ...

• Use distance function to construct a weight 𝑤𝑖
• Replace the final line of the classification algorithm by:
𝑘
መ 𝑞 ) ← arg max ෍ 𝑤𝑖 𝛿(𝜐, 𝑓(𝑥𝑗 ))
𝑓(𝑥
𝜐∈𝑉
𝑖=1
Where,
1
𝑤𝑖 =
𝐷𝑖𝑠(𝑥𝑞 , 𝑥𝑖 )2

𝐷𝑖𝑠(𝑥𝑞 , 𝑥𝑖 ) is distance between 𝑥𝑞 , 𝑥𝑖

COMP9417 81
Distance-Weighted KNN

For real-valued target functions replace the final line of the algorithm
by:
𝑘
መ 𝑞 ) ← σ𝑖=1𝑘𝑤𝑖 𝑓(𝑥𝑖 )
𝑓(𝑥 σ 𝑖=1 𝑤𝑖

(denominator normalizes contribution of individual weights).

Now we can consider using all the training examples instead of just 𝑘:
o using all examples (i.e., when 𝑘 = 𝑚 and 𝑚 is number of
training samples) with the rule above is called Shepard’s
method

COMP9417 82
Evaluation

Lazy learners do not construct an explicit model, so how do we evaluate

the output of the learning process ?
o 1-NN – training set error is always zero !
▪ each training example is always closest to itself
o 𝑘-NN – overfitting may be hard to detect

Solution:
Leave-one-out cross-validation (LOOCV) – leave out each example and
predict it given the rest:
𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 , … , 𝑥𝑖−1 , 𝑦𝑖−1 , 𝑥𝑖+1 , 𝑦𝑖+1 , … , (𝑥𝑚 , 𝑦𝑚 )

Error is mean over all predicted examples. Fast – no models to be built !

COMP9417 83
KNN Computational Time

• KNN uses the training data as exemplars, so using simple search for
prediction is 𝑂(𝑛)!

• There are algorithms to search for neighbours more efficiently with 𝑂(log 𝑛)
but they do not work very well for above 10 dimensions (more than 10
features/attributes)

• For above 10 dimension, there are some approximate nearest neighbour

approaches that can improve computation by orders of magnitude

• In high dimensional space (e.g., above 20 dimensions) even with using

such algorithms, the KNN doesn’t work well

• In high-dimensional spaces everything is far away from everything and so

pairwise distances are uninformative (curse of dimensionality)

COMP9417 84
When is KNN meaningful?

You may think that this is an exceptional example, and this doesn’t really
happen in practice!!

COMP9417 85
Curse of Dimensionality

• It can be shown that as dimensions increase the effectiveness of distance

metrics decrease and the concept of proximity may not be qualitatively
meaningful as all points look equidistant

• This is one symptom of having high dimensional space (curse of

dimensionality)

• There are also other problems arising from curse of dimensionality:

– It becomes polynomially harder to estimate many parameters (e.g.,

covariances)

– It becomes more difficult to visualize data

– Enormous amount of data is needed to train a model

COMP9417 86
Curse of Dimensionality

Curse of Dimensionality

• number of “cells” in the instance space grows exponentially in the

• number
numberofoffeatures
“ cells” in the instance space grows exponentially in the
number
• with of features
exponentially many cells we would need exponentially many
• data
withpoints
exponentially
to ensure many
that cells
eachwecellwould need exponentially
is sufficiently many
populated to data
make
points to ensure that
nearest-neighbour each cellreliably
predictions is sufficiently populated to make
nearest-neighbour predictions reliably
COM P9417 M L & DM Classificat ion (1) Term 2, 2019 67 / 72

COMP9417 87
Curse of Dimensionality

• Bellman (1960) coined this term in the context of dynamic

programming

• Imagine instances described by 20 attributes, but only 2 are relevant

to target function — “similar” examples will appear “distant”.

• Curse of dimensionality: nearest neighbour is easily misleading when

dealing with high-dimensional 𝑥 in terms of the number of features –
problem of irrelevant attributes

COMP9417 88
Curse of Dimensionality

One approach:

o Stretch 𝑗th axis by weight 𝑧𝑗 , where 𝑧1 , … , 𝑧𝑑 chosen to

minimize prediction error

o Use cross-validation to automatically choose weights

𝑧1 , … , 𝑧𝑑

o Note, setting 𝑧𝑗 to zero eliminates this dimension altogether

COMP9417 89
Curse of Dimensionality

Some ideas to address this for instance-based (nearest-neighbour)

learning
o Euclidean distance with weights on attributes
𝑑

𝐷𝑖𝑠 𝑥𝑞 , 𝑥𝑖 = ෍ 𝑧𝑟 (𝑥𝑞𝑟 − 𝑥𝑖𝑟 )2

𝑟=1

o updating of weights based on nearest neighbour

classification error
▪ class correct/incorrect: weight increased/decreased
▪ can be useful if not all features used in classification

See Moore and Lee (1994) “Efficient Algorithms for Minimizing Cross Validation Error”

COMP9417 90
Instance-based (nearest-neighbour) learning

Recap – Practical problems of NN scheme:

o Slow (but fast k-dimensional tree-based approaches exist)
▪ Remedy: removing irrelevant data or features

o Noise (but KNN copes quite well with noise)

▪ Remedy: removing noisy instances

o All attributes deemed equally important

▪ Remedy: attribute weighting (or simply selection)

COMP9417 91
Dealing with noise

o Use larger values of k (why?); but how to find the “right” k?

o One way: cross-validation-based 𝑘-NN classifier (but slow)

o Different approach: discarding instances that don’t perform well

by keeping success records of how well an instance does at
prediction (IB3)

IB3 (Instance-Based Learning 3): store classification performance information with each instance &
only use in prediction if above a threshold

COMP9417 92
KNN Example

COMP9417 93
KNN Example

• Automated MS-lesion segmentation by

KNN

• They have used some manually labeled

image as the training set

• They used 4 features: Intensity and

voxel locations (x,y,z coordinates)

Ref: Anbeek et. Al, “Automated MS-lesion segmentation by K-nearest neighbor

classification”, MIDAS journal, 2008 COMP9417 94
Summary

• General frameworks for classification

• Logistic Regression models the probability of a class.

• Classification viewed in terms of distance in feature space

• Distance-based learning

• Nearest neighbour classifiers

COMP9417 95
Acknowledgements
• Material derived from slides for the book
“Elements of Statistical Learning (2nd Ed.)” by T. Hastie, R. Tibshirani & J. Friedman. Springer
(2009) [Link]
• Material derived from slides for the book
“Machine Learning: A Probabilistic Perspective” by P. Murphy MIT Press (2012)
[Link]
• Material derived from slides for the book “Machine Learning” by P. Flach Cambridge University
Press (2012) [Link]
• Material derived from slides for the book
“Bayesian Reasoning and Machine Learning” by D. Barber Cambridge University Press (2012)
[Link]
• Material derived from slides for the book “Machine Learning” by T. Mitchell McGraw-Hill (1997)
[Link] [Link]/~tom/[Link]
• Material derived from slides for the course “Machine Learning” by A. Srinivasan BITS Pilani, Goa,
India (2016)

COMP9417 96