k-nearest neighbour Machine Learning.pdf

ML

1. K-Nearest Neighbor
CSE 4621 | Machine Learning| BScTE| Summer 22-23
Sabbir Ahmed
Assistant Professor, Dept of CSE, IUT
[email protected]
1

2. Nearest Neighbor Classifier
2
Memorizealldata
andlabels
Predict the label of
themostsimilar
training image

3. Distance Metric to compare images
3
L1distance:

4. •Memorize training data
•For each test image:
•Find nearest training image
•Return label of nearest
image
4
NearestNeighborClassifier
Q:WithNexamples,
howfastistraining?
A:O(1)
Q:WithNexamples,
howfastis testing?
A:O(N)

5. What does this look like?
5

6. What does this look like?
6

7. 7
NearestNeighborDecisionBoundaries

8. 8
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
x
0

9. 9
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
Points are training
examples; colors
givetraininglabels
x
0

10. 10
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
Points are training
examples; colors
givetraininglabels
Backgroundcolors
give the category
atestpointwould
beassigned
x
x
0

11. 11
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
Points are training
examples; colors
givetraininglabels
Decisionboundary
is the boundary
between two
classificationregions
Backgroundcolors
give the category
atestpointwould
beassigned
x
x
0

12. 12
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
Points are training
examples; colors
givetraininglabels
Backgroundcolors
givethecategory
atestpointwould
x
Decisionboundary
is the boundary
between two
classificationregions
beassigned
x
0
Decisionboundaries
can be noisy;
affectedbyoutliers

13. 13
NearestNeighborDecisionBoundaries
x
1
Nearestneighbors
intwodimensions
Points are training
examples; colors
givetraininglabels
Backgroundcolors
givethecategory
atestpointwould
x
Decisionboundary
is the boundary
between two
classificationregions
beassigned
x
0
Decisionboundaries
can be noisy;
affectedbyoutliers
How to smooth out
decision boundaries?
Usemoreneighbors!

14. 14
K-NearestNeighbors
K=1
Insteadofcopyinglabel fromnearestneighbor,
takemajority votefrom K closestpoints
K=3

15. 15
K-NearestNeighbors
K=1
Using more neighbors helps smooth
outrough decisionboundaries
K=3

16. 16
K-NearestNeighbors
K=1
Using more neighbors helps
reduce theeffectofoutliers
K=3

17. K-NearestNeighbors
K=1
WhenK>1therecanbe
tiesbetweenclasses.
Needtobreaksomehow!
K=3

18. K-NearestNeighbors:DistanceMetric
L1(Manhattan)distance L2(Euclidean)distance
K=1K=1

19. K-NearestNeighbors:
WebDemo
http://vision.stanford.edu/teaching/cs231n-demos/knn/
Interactivelymovepointsaround
and seedecisionboundarieschange
PlaywithL1 vsL2 metrics
Playwith changingnumber of
trainingpoints,valueofK

20. Hyperparameters
WhatisthebestvalueofKtouse?
Whatisthebestdistancemetrictouse?
These areexamplesofhyperparameters:choices about our
learningalgorithmthatwedon’tlearnfromthetraining
data;insteadwesetthematthestartof thelearning process

21. Hyperparameters
WhatisthebestvalueofKtouse?
Whatisthebestdistancemetrictouse?
These areexamplesofhyperparameters:choices about our
learningalgorithmthatwedon’tlearnfromthetraining
data;insteadwesetthematthestartof thelearning process
Veryproblem-dependent.In generalneedtotrythemalland
seewhatworksbestforourdata/task.

22. SettingHyperparameters
Idea#1:Choosehyperparametersthat
workbest onthedata
YourDataset

23. SettingHyperparameters
Idea#1:Choosehyperparametersthat
workbest onthedata
BAD: K = 1 always works
perfectlyontrainingdata
YourDataset

24. SettingHyperparameters
Idea#1:Choosehyperparametersthat
workbest onthedata
BAD: K = 1 always works
perfectlyontrainingdata
Idea #2: Split data into train and test, choose
hyperparametersthatworkbestontestdata
YourDataset
train test

25. SettingHyperparameters
Idea#1:Choosehyperparametersthat
workbest onthedata
BAD: K = 1 always works
perfectlyontrainingdata
Idea #2: Split data into train and test, choose
hyperparametersthatworkbestontestdata
BAD:Noideahowalgorithm
willperformonnewdata
YourDataset
train test

26. SettingHyperparameters
Idea#1:Choosehyperparametersthat
workbest onthedata
BAD: K = 1 always works
perfectlyontrainingdata
Idea #2: Split data into train and test, choose
hyperparametersthatworkbestontestdata
BAD:Noideahowalgorithm
willperformonnewdata
YourDataset
train test
Idea #3: Split data into train, val, and test; choose
hyperparameters onvalandevaluate ontest
Better!
train validation test

27. SettingHyperparameters
YourDataset
fold1 fold2 fold3 fold4 fold5 test
Idea#4:Cross-Validation:Splitdatainto folds,tryeach
foldasvalidationandaveragetheresults
fold1 fold2 fold3 fold4 fold5 test
fold1 fold2 fold3 fold4 fold5 test
Useful forsmall datasets,but(unfortunately)not usedtoofrequentlyindeeplearning

28. SettingHyperparameters
Exampleof5-foldcross-validationfor
thevalueof k.
Each point:singleoutcome.
Thelinegoesthroughthemean,bars
indicatedstandarddeviation
(Seemsthatk~7works best
forthisdata)

29. Mathematical explanation of K-Nearest
Neighbour
•It’s one of the Supervised learning algorithm mostly used for classification
of data on the basis how it’s neighbour are classified.
•KNN stores all available cases and classifies new cases based on a
similarity measure.
•K in KNN is a parameter that refers to the number of the nearest
neighbours to include in the majority voting process.
29

30. •How do we choose K?
•Sqrt(n), where n is a total number of data points(if in case n is even we have to
make the value odd by adding 1 or subtracting 1 that helps in select better)
•When to use KNN?
•We can use KNN when Dataset is labelled and noise-free and it’s must be small
because KNN is a “Lazy learner”. Let’s understand KNN algorithm with the help of
an example
30

31. 31

32. •Here male is denoted with numeric value 0 and female with 1.
•Let’s find in which class of people Angelina will lie whose k factor is 3 and
age is 5.
•So we have to find out the distance using
d=√((x2-x1)²+(y2-y1)²) to find the distance between any two points.
32

33. •So let’s find out the distance between Ajay and Angelina using formula
d=√((age2-age1)²+(gender2-gender1)²)
d=√((5-32)²+(1-0)²)
d=√729+1
d=27.02
Similarly, we find out all distance one by one.
33

34. 34

35. •So the value of k factor is 3 for Angelina. And the closest to 3 is 9,10,10.5
that is closest to Angelina are Zaira, Smith and Michael.

Zaira 9 cricket
Michael 10 cricket
Smith 10.5 football
•So according to KNN algorithm, Angelina will be in the class of people
who like cricket. So this is how KNN algorithm works.
35

36. Reference
•https://www.geeksforgeeks.org/mathematical-explanation-of-k-nearest-
neighbour/
36