Supervised Learning
1
Supervised Learning
2
supervised learning
given a data set of input-output pairs, learn
a function to map inputs to outputs
3
classification
supervised learning task of learning a
function mapping an input point to a
discrete category
4
5
Date Humidity Pressure Rain
(relative humidity) (sea level, mb)
6
Date Humidity Pressure Rain
(relative humidity) (sea level, mb)
January 1 93% 999.7 Rain
January 2 49% 1015.5 No Rain
January 3 79% 1031.1 No Rain
January 4 65% 984.9 Rain
January 5 90% 975.2 Rain
7
f(humidity, pressure)
f(93, 999.7) = Rain
f(49, 1015.5) = No Rain
f(79, 1031.1) = No Rain
h(humidity, pressure)
8
humidity
pressure
9
humidity
pressure
10
humidity
pressure
11
humidity
pressure
12
humidity
pressure
13
nearest-neighbor classification
algorithm that, given an input, chooses the
class of the nearest data point to that input
14
humidity
pressure
15
humidity
pressure
16
humidity
pressure
17
humidity
pressure
18
humidity
pressure
19
humidity
pressure
20
K Nearest
Neighbors
21
Nearest Neighbour Rule
Consider a two class problem where
each sample consists of two
measurements (x,y).
For a given query point q, k=1
assign the class of the
nearest neighbour.
Compute the k nearest k=3
neighbours and assign the
class by majority vote.
19/06/2014 50 22
The K-Nearest Neighbour Algorithm
Who’s this?
Height
Weight
23
The K-Nearest Neighbour Algorithm
1. Measure distance to all
points
Height
Weight
24
The K-Nearest Neighbour Algorithm
1. Measure distance to all points
2. Find closest “k” points (here k=3, but it could be more)
Height
Weight
25
The K-Nearest Neighbour Algorithm
1. Measure distance to all points
2. Find closest “k” points (here k=3, but it could be more)
3. Assign majority class
Height
Weight
26
“Euclidean distance”
d (w w ) (h h ) 2 2
1
1
(w, h)
Height
d
(w1, h1)
Weight
27
The K-Nearest Neighbour Algorithm
for each testing point
measure distance to every training
point find the k closest points
identify the most common class among
those k
predict that class
end
• Advantage: Surprisingly good classifier!
• Disadvantage: Have to store the entire training
set in memory 28
Euclidean distance still works in 3-d, 4-d, 5-d, etc….
d (x x ) ( y y ) (z z )
2 2 2
1 1
1
x = Height
y = Weight
z = Shoe size
29
Choosing the wrong features makes it difficult,
too many and it’s computationally intensive.
Possible features:
- Shoe size
- Height
?
- Age
- Weight
Shoe size
Age
30
Nearest Neighbour Rule
Consider a two class problem where
each sample consists of two
measurements (x,y).
For a given query point q, k=1
assign the class of the
nearest neighbour.
Compute the k nearest k=3
neighbours and assign the
class by majority vote.
59 31
Nearest Neighbor Classifier
10
9
8
7
Antenna Length
6
5 If the nearest instance to the previously
4 unseen instance is a Katydid
class is Katydid
3 else
2 class is
1 Grasshopper
Katydids
1 2 3 4 5 6 7 8 9 10 Grasshoppers
Abdomen Length 32
The nearest neighbor algorithm is sensitive to outliers…
The solution is to… 33
We can generalize the nearest neighbor algorithm to
the K- nearest neighbor (KNN) algorithm.
We measure the distance to the nearest K instances, and
let them vote. K is typically chosen to be an odd number.
K=1 K=3
34
K-Nearest Neighbour Model
• Picking K
– Use N fold cross validation – Pick K to minimize the cross validation error
– For each of N training example
Find its K nearest neighbours
Make a classification based on these K neighbours
Calculate classification error
Output average error over all examples
– Use the K that gives lowest average error over the N training examples
35
63
K-Nearest Neighbour Model
• Example : Classify whether a customer will respond to a survey question
using a 3-Nearest Neighbor classifier
Customer Age Income No. credit Response
cards
John 35 35K 3 No
Rachel 22 50K 2 Yes
Hannah 63 200K 1 No
Tom 59 170K 1 No
Nellie 25 40K 4 Yes
David 37 50K 2 ?
K-Nearest Neighbour Model
• Example : 3-Nearest Neighbors
Customer Age
Age Income
Income No. credit Response
cards
John 35
35 35K
35K 3 No
Rachel 22
22 50K
50K 2 Yes
Hannah 63
63 200K
200K 1 No 15.16
Tom 59 59 170K 1 No 15
170K
25 40K 4 Yes 152.23
Nellie 25 122
15.74
40K
David 37 50K 2 ?
K-Nearest Neighbour Model
• Example : 3-Nearest Neighbors
Customer Age
Age Income
Income No. credit Response
Response
cards
John 35
35 35K
35K 3 3 No
No
Rachel 22
22 50K
50K 2 Yes
2
Hannah 63
63 200K
200K Yes
1 No 15.16
Tom 59 59 170K 1 No 15
170K
25 40K 4 Yes 152.23
Nellie 25 122
15.74
40K
David 37 50K 2 ?
Three nearest ones to David are: No, Yes, Yes
K-Nearest Neighbour Model
• Example : 3-Nearest Neighbors
Customer Age
Age Income
Income No. credit Response
Response
cards
John 35
35 35K
35K 3 3 No
No
Rachel 22
22 50K
50K 2 Yes
2
Hannah 63
63 200K
200K Yes
1 No 15.16
Tom 59 59 170K 1 No 15
170K
25 40K 4 Yes 152.23
Nellie 25 122
15.74
40K
David 37 50K 2 Ye??s
Three nearest ones to David are: No, Yes, Yes
K-Nearest Neighbour Model
• Example: For the example we saw earlier, pick the best K from the set {1, 2,
3} to build a K-NN classifier
Customer Age Income No.
[Link]
credit Response
cards
cards
John 35 35K 3 No
Rachel 22 50K 2 Yes
Hannah 63 200K 1 No
Tom 59 170K 1 No
Nellie 25 40K 4 Yes
David 37 50K 2 ?
Quiz
#1
• The diagram below shows a data set with 2 classes and 8 data
points, each with only one feature value, labeled f. Note that
there are two data points with the same feature value of 6.
These are shown as two x’s one above the other
1. Divide this dataset equally into 2 parts. Use 1st part as training and
2nd as testing. Using KNN classifier, for k=3, what would be the
predicted outputs for test samples? Show how you arrived at your
answer.
2. Compute the confusion matrix for this and calculate
accuracy, sensitivity and specificity values 41