Classification

CMT307 Session 4

Yuhua Li
liy180@[Link]

CMT307 1
Contents
• k-nearest neighbours
• Support Vector Machines
• Decision trees
• Hyperparameter Optimisation

CMT307 2
Classification: Definition
• Given a collection of records (training set )
◦ Each record contains a set of attributes, one of the attributes is the class.

• Find a model for class attribute as a function of the values of other attributes.
• Goal: previously unseen records should be assigned a class as accurately as
possible.
◦ A test set is used to determine the accuracy of the model. Usually, the given data set is
divided into training and test sets, with training set used to build the model and test set
used to evaluate it.

CMT307 3
 Classification Example

Refund
4 Marital Taxable
cal cal us Status Income Cheat
i i o
gor gor i nu
ate ate ont ass No Single 75K ?
c c c cl
Tid Refund Marital Taxable Yes Married 50K ?
Status Income Cheat
No Married 150K ?
1 Yes Single 125K No Yes Divorced 90K ?
2 No Married 100K No No Single 40K ?
3 No Single 70K No
No Married 80K ?
4 Yes Married 120K No
10

5 No Divorced 95K Yes

Test
6 No Married 60K No Set
7 Yes Divorced 220K No
8 No Single 85K Yes
Learn
No
Training Model
9 No Married 75K
Set Classifier
10 No Single 90K Yes
10

CMT307
Contents
• k-nearest neighbours
• Support Vector Machines
• Decision trees
• Hyperparameter Optimisation

CMT307 5
k-nearest neighbours
• A type of instance-based learning, or lazy learning
• A nonparametric method
• Can be used for both classification and regression, though
commonly used for classification.
• Learning is very fast (finding k or no training)
◦ Store training examples

CMT307 6
k-NN Classification
• Training Algorithm
◦ Store training data points
k=11
• Set the value for k
k=3
• Prediction Algorithm k=1
◦ To classify a new input vector x:
§ Calculate the distance from x to each of the data points in
training set
§ Find the k training data points which are nearest to x
§ Examine the k-nearest training data points to x and
assign x to the most frequently occurring class

• A commonly used distance metric for

continuous variables is Euclidean distance

CMT307 7
k -NN Classification
• Advantages
◦ Training is very fast (no training required)
◦ Learn complex target functions
◦ Simple and intuitive, easy to program
◦ Classification accuracy can be very good; can outperform more complex models

• Disadvantages
◦ Slow at query time
◦ Sensitive to noise and irrelevant attributes

CMT307 8
k-NN Issues
• Distance measure
◦ Most common: Euclidean distance
& %)
(
(

K=1
𝑑 𝐱 ! , 𝐱" = % 𝑥!,# − 𝑥",#
#$%

• Choosing k
◦ Increasing k reduces variance, increases bias

• Memory-based technique. Must make a pass through

the data for each classification. This can be
prohibitive for large data sets.

K=15
• Feature scaling is needed if features are not
commensurate

CMT307 9
Contents
• K nearest neighbours
• Support Vector Machines
• Hyperparameter Optimisation
• Decision trees

CMT307 10
Support Vector Machines f(x) = 1.5 x1 - x2 - 0.1

• Linear classifiers for binary classes

x 𝑦1 f(x) < 0
f .1=0
x2 -0
x 1
-
1.5
𝑓(𝑥,𝑤,𝑏)=𝑠𝑖𝑔𝑛(𝑤 * 𝑥+𝑏)
= 0 f(x) > 0
1.5𝑥! − 𝑥" − 0.1 = 0 f (x)
w=(1.5, -1), b=−0.1

For a point (-0.8, 1), sign(1.5*(-0.8) - 1 – 0.1) = sign(-2.3) = -1

For a point (0.1, -2), sign(1.5*0.1 - (-2) – 0.1) = sign(2.05) = +1

CMT307 11
ρ

CMT307 12
Support Vector Machines
• As the 2-d example shown on previous slide, the two classes can be separated
by different lines.
• The points nearest to the separation/decision line (or plane in 3-d or hyperplane
in higher dimension) define the margin(i.e., gap) between classes.
• Those points are called support vectors.
• Support vector machine aims to maximise the margin.

CMT307 13
 Sec. 15.1

Maximum Margin: Formalization

• 𝒘: decision hyperplane normal vector
• 𝒙𝒊 : data point i
• 𝑦$ : class of data point i (+1 or -1) NB: Not 1/0
• Classifier is: 𝑓 𝒙$ = 𝑠𝑖𝑔𝑛(𝒘% 𝒙$ + 𝑏)
• Functional margin of 𝒙$ is: 𝑦$ (𝒘% 𝒙$ + 𝑏)
◦ But note that we can increase this margin simply by scaling w, b….

• Functional margin of dataset is twice the minimum functional margin for any
point
◦ The factor of 2 comes from measuring the whole width of the margin

CMT307 14
 Sec. 15.1

Linear Support Vector Machine (SVM)

• Hyperplane
wT x + b = 0
wTxa + b = 1
ρ
wTxb + b = -1
• Extra scale constraint:
𝑚𝑖𝑛$&!,…,) 𝒘% 𝐱 $ + 1 = 1

• This implies:
𝒘% (𝐱 * −𝐱 + ) = 2
2
𝝆 = 𝐱 * −𝐱 + " =
‖𝒘‖" wT x + b = 0

CMT307 15
 Sec. 15.1

Linear SVMs Mathematically (cont.)

• Then we can formulate the quadratic optimization problem:
Find w and b such that
2
ρ=
w is maximized; and for all {(xi , yi)}
wTxi + b ≥ 1 if yi=1; wTxi + b ≤ -1 if yi = -1

• A better formulation (min ||w|| = max 1/ ||w|| ):

Find w and b such that

L(w) =½ wTw is minimized;

and for all {(xi ,yi)}: yi (wTxi + b) ≥ 1

CMT307 16
 Sec. 15.1

The Optimization Problem Solution

• The solution has the form:
w =Σαiyixi
b= yk- wTxk for any xk such that αk¹ 0
• Each non-zero αi indicates that corresponding xi is a support vector.

• Then the classifying function will have the form:

f(x) = ΣαiyixiTx + b
• Notice that it relies on an inner product between the test point x and the support vectors xi
◦ We will return to this later.

• Also keep in mind that solving the optimization problem involved computing the inner products
xiTxj between all pairs of training points.

CMT307 17
 Sec. 15.2.1

Soft Margin Classification

• If the training data is not linearly
separable, slack variables ξi can be added
to allow misclassification of difficult or
noisy examples.
• Allow some errors
◦ Let some points be moved to where they belong,
at a cost
ξi
• Still, try to minimize training set errors, and ξj
to place hyperplane “far” from each class
(large margin)

CMT307 18
 Sec. 15.2.1

Soft Margin Classification Mathematically

• The old formulation:

Find w and b such that

L(w) =½ wTw is minimized and for all {(xi ,yi)}
yi (wTxi + b) ≥ 1

• The new formulation incorporating slack variables:

Find w and b such that

L(w) =½ wTw + CΣξi is minimized and for all {(xi ,yi)}
yi (wTxi + b) ≥ 1- ξi and ξi ≥ 0 for all i

• Parameter C can be viewed as a way to control overfitting

◦ A regularization term

CMT307 19
Regularisation
• Support vector machines
◦ Training SVM involves regularization by default, its strength of regularization is determined by
the penalty parameter C>0.
+
1 *
min 𝑤 𝑤 + 𝐶 % 𝜉!
2
!$%
◦ Larger values of C: less regularization
§ Fit the training data as well as possible
§ Each individual data point is important to classify correctly
◦ Smaller values of C: more regularization
§ More tolerant of errors on individual data points

CMT307 20
 Sec. 15.1

Classification with SVMs

• Given a new point x, we can score its projection onto the hyperplane normal:
◦ i.e., compute score: wTx + b = ΣαiyixiTx + b
§ Decide class based on whether <0 or >0

◦ Can set confidence threshold t.

Score > t: yes
Score < -t: no
Else: don’t know

1
0
-1

CMT307 22
 Sec. 15.2.3

Non-linear SVMs
• Datasets that are linearly separable (with some noise) work out great:

0 x

• But what are we going to do if the dataset is just too hard?

0 x

• How about … mapping data to a higher-dimensional space:

x2

0 x

CMT307 24
 Sec. 15.2.3

Non-linear SVMs: Feature spaces

• General idea: the original feature space can always be mapped to some
higher-dimensional feature space where the training set is separable:

Φ: x → φ(x)

CMT307 25
Non-linear SVMs: Feature spaces
• SVM uses a kernel function (which is a similarity measure between data points)
to map data from input (feature) space to a higher-dimensional feature space
• Why use kernels?
◦ Make non-separable problem separable.
◦ Map data into better representational space

• Common kernels
◦ Linear 𝐾 x ! , x" = x !* x"
◦ Polynomial 𝐾 x ! , x" = (1 + x !* x" ),
$
x ! "x # $
◦ Radial basis function 𝐾 x ! , x" = 𝑒
-
$%$ =𝑒 -. x ! -x #

xi - xj
CMT307 27
SVM Reading
• Aurélien Géron. Hands-On Machine Learning with Scikit-Learn, Keras, and
TensorFlow, 2nd Edition, 2019.
Chapter 5, Appendix C for a rudimentary introduction.

• Christopher Bishop. Pattern Recognition and Machine Learning. Springer 2006.

[Link]
[Link]
Section 7.1 for a more rigorous introduction.

CMT307 28
Contents
• k-nearest neighbours
• Support Vector Machines
• Decision trees
• Hyperparameter Optimisation

CMT307 29
 Example of a Decision Tree

cal cal us
i i o
or or nu
t eg
t eg
nt i
ass Splitting Attributes
ca ca co cl
Tid Refund Marital Taxable
Status Income Cheat

1 Yes Single 125K No Refund

2 No Married 100K No Yes No
3 No Single 70K No {1,4,7} {2,3,5,6,8,9,10}
n,n,n NO MarSt n,n,y,n,y, n, y
4 Yes Married 120K No
Single, Divorced Married
5 No Divorced 95K Yes
{3,5,8,10} {2,6,9}
6 No Married 60K No n,y, y, y TaxInc NO n,n,n
7 Yes Divorced 220K No < 80K > 80K
8 No Single 85K Yes YES
NO
9 No Married 75K No {3} {5,8,10}
n y, y, y
10 No Single 90K Yes
Model: Decision Tree
10

Training Data
CMT307 30
Decision Tree
• A root node that has no incoming edges and zero or more outgoing edges
• An internal node is a test on an attribute
• A branch represents an outcome of the test
• A leaf or terminal node represents a class label
• At each node, one attribute is chosen to split training examples into distinct
classes as much as possible

• A new case is classified by following a matching path to a leaf node.

CMT307 31
 Example of Decision Tree

cal cal us
i i o
or or nu
t eg
t eg
nt i
ass Single,
ca ca co cl MarSt
Married Divorced
Tid Refund Marital Taxable
Status Income Cheat
NO Refund
1 Yes Single 125K No No
Yes
2 No Married 100K No
3 No Single 70K No NO TaxInc
4 Yes Married 120K No < 80K > 80K
5 No Divorced 95K Yes
NO YES
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
There could be more than one tree that
fits the same data!
10 No Single 90K Yes
10

CMT307 32
 Apply Model to Test Data

Test Data
Start from the root of tree. Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

CMT307 33
Apply Model to Test Data

Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

CMT307 34
Apply Model to Test Data

Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

CMT307 35
Apply Model to Test Data

Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

CMT307 36
 Apply Model to Test Data

Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

CMT307 37
 Apply Model to Test Data

Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married Assign Cheat to “No”

TaxInc NO
< 80K > 80K

NO YES

CMT307 38
Decision Tree Algorithms
• Many Algorithms:
◦ Hunt’s (one of the earliest)
◦ CART (Classification And Regression Tree)
◦ ID3 (Iterative Dichotomiser 3)
◦ C4.5 (successor of ID3)
◦ SLIQ (Supervised Learning In Quest), SPRINT

CMT307 39
Choosing the Splitting Attribute
• At each node, available attributes are evaluated on the basis of separating the
classes of the training examples. A Goodness function is used for this purpose.
• Typical goodness functions:
◦ information gain (Entropy ) used in (ID3/C4.5)
◦ GINI index (IBM Intelligent Miner)

CMT307 40
How to Specify Test Condition?
• Depends on attribute types
◦ Nominal: takes values from an unordered set. Marital status, Gender, Colour, etc.
◦ Continuous: takes values from ordered set. Age, Salary, etc.

• Depends on number of ways to split

◦ 2-way split
◦ Multi-way split

CMT307 41
Splitting Based on Nominal Attributes
• Multi-way split: Use as many partitions as distinct values.
CarType
Family Luxury
Sports

• Binary split: Divides values into two subsets.

Need to find optimal partitioning.

CarType CarType
{Sports,
{Family} OR {Family,
{Sports}
Luxury} Luxury}

CMT307 42
Splitting Based on Continuous Attributes

Taxable Taxable
Income Income?
> 80K?
< 10K > 80K
Yes No

[10K,25K) [25K,50K) [50K,80K]

(i) Binary split (ii) Multi-way split

CMT307 43
How to determine the Best Split

• Greedy approach:
◦ Nodes with homogeneous class distribution are preferred

• Need a measure of node impurity:

C0: 5 C0: 9
C1: 5 C1: 1
Non-homogeneous, Homogeneous,
High degree of impurity Low degree of impurity

CMT307 44
A criterion for attribute selection
• Which is the best attribute?
◦ The one which will result in the smallest tree
◦ Heuristic: choose the attribute that produces the “purest” nodes

• Popular impurity criterion: information gain

◦ Information gain increases with the average purity of the subsets that an attribute produces

• Strategy: choose attribute that results in greatest information gain

CMT307 45
Computing information
• Given a probability distribution, the information required to predict an event is
the distribution’s entropy (Shannon entropy)

• Generally, entropy refers to disorder or uncertainty

• Shannon entropy was introduced by Claude E. Shannon in 1948

CMT307 47
Splitting Criteria based on Information Gain
• Entropy at a given node t:
Entropy (t ) = - å p( j | t ) log2 p( j | t )
j

(NOTE: p( j | t) is the relative frequency of class j at node t).

◦ Measures homogeneity of a node.
§ Maximum entropy when records are equally distributed among all classes implying least
information
§ Minimum entropy (0.0) when all records belong to one class, implying most information

CMT307 48
 Examples for computing Entropy

Entropy(t ) = -å p( j | t ) log p( j | t )
j 2

C1 0 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

C2 6 Entropy = – 0 – 1 log2 1 = – 0 – 0 = 0

C1 1 P(C1) = 1/6 P(C2) = 5/6

C2 5 Entropy = – (1/6) log2 (1/6) – (5/6) log2 (5/6) = 0.65

C1 2 P(C1) = 2/6 P(C2) = 4/6

C2 4 Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = 0.92

CMT307 49
 Splitting Based on Information Gain
• Information Gain:
0
𝑛$
𝐺𝐴𝐼𝑁,-.$/ = 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑝) − E 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑖)
𝑛
$&!
Parent Node, p is split into k partitions;
ni is number of records in partition i

◦ Measures Reduction in Entropy achieved because of the split. Choose the

split that achieves most reduction (maximizes GAIN)
◦ Used in ID3 and C4.5

CMT307 50
Splitting based on Gini Index
• If a data set t contains examples from c classes, gini index, gini(t) is defined as
2
𝑔𝑖𝑛𝑖 𝑡 = 1 − E 𝑝1" Example:
1&! a node with 3 classes, each having samples [0, 49, 5]
gini(T) = 1 – (0/54)2 – (49/54)2 – (5/54)2 ≈ 0.168.
where pj is the relative frequency of class j in t.

• If a data set t of n points is split into two subsets t1 and t2 with sizes n1 and n2 respectively, the gini
index of the split data contains examples from c classes, the gini index gini(t) is defined as

𝑛! 𝑛"
𝑔𝑖𝑛𝑖,-.$/ 𝑡 = 𝑔𝑖𝑛𝑖 𝑡! + 𝑔𝑖𝑛𝑖 𝑡"
𝑛 𝑛
• The attribute provides the smallest ginisplit(t) is chosen to split the node (need to enumerate all
possible splitting points for each attribute).

51
 Weather Data: Play or not Play?
• Training Examples
Day Outlook Temp. Humidity Wind Play Tennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Weak Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Strong Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No

CMT307 52
 Decision Tree for PlayTennis
• Attributes and their values:
◦ Outlook: Sunny, Overcast, Rain
◦ Humidity: High, Normal
◦ Wind: Strong, Weak
◦ Temperature: Hot, Mild, Cool

◦ Target concept - Play Tennis: Yes, No

CMT307 53
Decision Tree for PlayTennis from ID3 Algorithm

Outlook

Sunny Overcast Rain

Humidity Yes Wind

[D3,D7,D12,D13]
High Normal Strong Weak

No Yes No Yes

[D1,D2] [D8,D9,D11] [D6,D14] [D4,D5,D10]

CMT307 54
 Converting a Tree to Rules

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

R1: If (Outlook=Sunny) Ù (Humidity=High) Then PlayTennis=No

R2: If (Outlook=Sunny) Ù (Humidity=Normal) Then PlayTennis=Yes
R3: If (Outlook=Overcast) Then PlayTennis=Yes
R4: If (Outlook=Rain) Ù (Wind=Strong) Then PlayTennis=No
R5: If (Outlook=Rain) Ù (Wind=Weak) Then PlayTennis=Yes

CMT307 55
Regression Trees

• Training of regression trees is the same as that of classification tree, except to

split the training set in a way that minimizes the MSE
• If a data set (node) tk of n points is split into two subsets (two nodes) t1 and t2
with sizes n1 and n2 respectively, then the cost function is
𝑛! 𝑛"
𝐽 𝑘, 𝑡0 = MSE/! + MSE/"
𝑛 𝑛
where

($) "
MSE3456 = ∑$∈3456 𝑦13456 −𝑦
L !
𝑦13456 = ) ∑$∈3456 𝑦 ($)
#$%&

CMT307 56
Remarks
• Pros
◦ Interpretable decision process: white box model
◦ Decision trees requires little data preparation: no need of
feature scaling or centering at all

• Cons
◦ Splits are perpendicular to an axis, so sensitive to training
set rotation
§ Solution: use PCA to get a better orientation of the training
data
◦ Very sensitive to small variations in the training data,
leading to different trees.
§ Solution: use Random Forest to limit instability

CMT307 57
Reading
• Aurélien Géron. Hands-On Machine Learning with Scikit-Learn, Keras, and
TensorFlow, 2nd Edition, 2019.
Chapter 6.

CMT307 58
Contents
• k-nearest neighbours
• Support Vector Machines
• Decision trees
• Hyperparameter Optimisation

CMT307 59
Hyperparameter Optimisation
• Model parameters vs. hyperparameters
SVM Example:
𝑓 𝒙$ = 𝑠𝑖𝑔𝑛(𝒘% 𝒙$ + 𝑏)
)
1 %
min 𝑤 𝑤 + 𝐶 E 𝜉$
2
$&!

• Machine learning models have hyperparameters that you must set in order to
customize the model to a given dataset,
◦ hyperparameter may take on integer-valued, real-valued, or categorical, e.g.,
§ k of k-NN: integer
§ C and r of SVM with RBF kernel: real
§ Kernel of SVM: categorical {‘linear’, ‘poly’, ‘rbf’, …}

CMT307 60
Hyperparameter Optimisation
• Machine learning programs usually provide default values for hyperparameters,
e.g.,
◦ k=5 in KNeighborsClassifier of sklearn
◦ C=1 and γ= 1 / (n_features * [Link]()) in SVC of sklearn

• Hyperparameter optimisation (a.k.a. hyperparameter tuning / search)

◦ Searches for a set of hyperparameter values that results in a model that achieves the best
performance on a given dataset

CMT307 61
Methods of hyperparameter optimization
• Grid search
• Random search
• Bayesian optimization
◦ Optuna
◦ Hyperopt See [Link]
◦ Scikit Optimize optimization-techniques-machine-learning/

CMT307 62
Grid search
• The most basic hyperparameter optimisation
method

• Defines a search space as a grid of

hyperparameter values and evaluate every
position in the grid

• Suffers from the curse of dimensionality

since the required number of function
evaluations grows exponentially with the
dimensionality of the configuration space

• Increasing the resolution of discretization

substantially increases the required number
of function evaluations Figure from Feurer & Hutter (2019)
DOI: 10.1007/978-3-030-05318-5_1

CMT307 63
Random search
• Define a search space as a bounded domain of
hyperparameter values and randomly sample
points in that domain
• Works better than grid search when some
hyperparameters are much more important
than others
• More efficient in terms of exploration. For B
!
evaluations, grid search only explores 𝐵 "

different values for each of N hyperparameter,

while random search will explore B different
values for each hyperparameter
• Easier parallelization (since workers do not
need to communicate with each other and
failing workers do not leave holes in the design) Figure from Feurer & Hutter (2019)
DOI: 10.1007/978-3-030-05318-5_1

CMT307 64
Summary
• k-NN is a simple but can produce good results for many complex problems
• SVM is an important and popular machine learning method with many
successful applications
• DT is a white box method with good interpretability
• All k-NN, SVM and DT can be used for both classification and regression

CMT307 65