K-Nearest Neighbours in Pattern Recognition
Pattern Recognition
Chapter 3: K Nearest Neighbours
Chumphol Bunkhumpornpat
Department of Computer Science
Faculty of Science
Chiang Mai University
Learning Objectives
•
What a nearest neighbour (NN) algorithm is
•
The different variants of NN algorithms like
–
The k nearest neighbour (kNN) algorithm
–
The modified k nearest neighbour (MkNN) algorithm
–
The r near algorithm
–
The fuzzy KNN algorithm
•
The different methods of prototype selection
used in classification like
–
The minimal distance classifier (MDC)
204453: Pattern Recognition
2
Nearest Neighbour Based Classifiers
•
Simplest Decision Procedures
•
Nearest Neighbour (NN) Rule
•
Similarity between a test pattern and every
pattern in a training set
•
Less than twice the probability of error
compared to any other decision rule
204453: Pattern Recognition
3
Nearest Neighbour Algorithm
•
The nearest neighbour algorithm assigns to a
test pattern the class label of its closest
neighbour.
204453: Pattern Recognition
5
Let the training set consist of the
following three dimensional patterns:
X
1
= (0.8, 0.8, 1),
X
2
= (1.0, 1.0, 1),
X
3
= (1.2, 0.8, 1)
X
4
= (0.8, 1.2, 1),
X
5
= (1.2, 1.2, 1),
X
6
= (4.0, 3.0, 2)
X
7
= (3.8, 2.8, 2),
X
8
= (4.2, 2.8, 2),
X
9
= (3.8, 3.2, 2)
X
10
= (4.2, 3.2, 2),
X
11
= (4.4, 2.8, 2),
X
12
= (4.4, 3.2, 2)
X
13
= (3.2, 0.4, 3),
X
14
= (3.2, 0.7, 3),
X
15
= (3.8, 0.5, 3)
X
16
= (3.5, 1.0, 3),
X
17
= (4.0, 1.0, 3),
X
18
= (4.0, 0.7, 3)
204453: Pattern Recognition
6
Let the training set consist of the
following three dimensional patterns:
(cont.)
•
Class 1: +
•
Class 2: X
•
Class 3: *
•
P = (3.0, 2.0)
•
d(X, P) =
(
X[1] – P[1])
2
+
(
X[2] – P[2])
2
•
d(X
1
, P) =
(0.8
–
3.0)
2
+ (0.8
–
2.0)
2
= 2.51
•
d(X
16
, P) =
(3.5
–
3.0)
2
+ (1.0
–
2.0)
2
= 1.12
204453: Pattern Recognition
7
Example Data Set
8
Variants of the NN Algorithm
•
k-Nearest Neighbour (kNN) Algorithm
•
The Modified k Nearest Neighbour (MkNN)
Algorithm
•
The r Near Algorithm
204453: Pattern Recognition
9
k-Nearest Neighbour (kNN) Algorithm
•
The majority class of the k nearest neighbours
is the class label assigned to the new pattern.
•
The value chosen for k is crucial.
•
With the right value of k, the classification
accuracy will be better than that got by using
the nearest neighbour algorithm.
204453: Pattern Recognition
10
Example Data Set (k = 5)
11
k-Nearest Neighbour (kNN) Algorithm (cont.)
•
It reduces the error in classification when
training patterns are noisy.
•
The closest pattern of the test pattern may
belong to another class, but when a number
of neighbours are obtained and majority class
label is considered, the pattern is more likely
to be classified correctly.
204453: Pattern Recognition
12
P can be correctly classified using
the kNN algorithm.
13
P can be correctly classified using
the kNN algorithm (cont.)
•
For larger data sets, k can be larger to reduce
the error.
•
k can be determined by experimentation,
where a number of patterns taken out from
the training set (validation set) can be
classified using the remaining training
patterns for different values of k.
•
It can be chosen as the value which gives the
least error in classification.
204453: Pattern Recognition
14
Example Data Set 2 (k = 5)
15
k = 1
16
k = 2
k = 3
17
k = 4
k = 5
18
k = 6
Problem with Class Imbalance
19
Modified k Nearest Neighbour (MkNN)
Algorithm
•
The Distance-Weighted k-Nearest Neighbour
Algorithm
•
k Nearest Neighbours are weighted according
to the distance from the test point.
204453: Pattern Recognition
20
Modified k Nearest Neighbour (MkNN)
Algorithm (cont.)
•
w
j
=
(d
k
– d
j
) / (d
k
– d
1
)
if d
k
d
1
1
if d
k
=
d
1
•
j = 1, …, k
•
w
j
varies from a maximum of 1 for the nearest
neighbour down to a minimum of 0 for the
most distant.
204453: Pattern Recognition
21
Modified k Nearest Neighbour (MkNN)
Algorithm (cont.)
•
It assigns the test pattern P to that class for
which the weights of the representatives
among the k nearest neighbours sums to the
greatest value.
•
It employs a weighted majority rule.
•
The outlier patterns have lesser effect on
classification.
204453: Pattern Recognition
22
Example Data Set (k = 5)
23
Example Data Set (k = 5) (cont.)
•
d(P, X
16
)
= 1.12
•
d(P, X
7
)
= 1.13
•
d(P, X
14
)
= 1.32
•
d(P, X
6
)
= 1.41
•
d(P, X
17
)
= 1.41
204453: Pattern Recognition
24
Example Data Set (k = 5) (cont.)
•
w
16
= 1
•
w
7
= (1.41 – 1.13) / (1.41 – 1.12) = 0.97
•
w
14
= (1.41 – 1.32) / (1.41 – 1.12) = 0.31
•
w
6
= 0
•
w
17
= 0
204453: Pattern Recognition
25
Example Data Set (k = 5) (cont.)
•
Class 1 sums to 0
•
Class 2 to which X
7
and X
6
belong sums to
0.97.
•
Class 3 to which X
16
, X
14
and X
17
belong sums
to 1.31.
•
The point P belongs to Class 3.
•
kNN and MkNN assign the same pattern a
same class label.
204453: Pattern Recognition
26
Example Data Set 2 (k = 5)
27
Example Data Set 2 (k = 5)
•
d(P, X
17
)
= 0.83
•
d(P, X
8
)
= 1.00
•
d(P, X
11
)
= 1.02
•
d(P, X
16
)
= 1.06
•
d(P, X
7
)
= 1.08
204453: Pattern Recognition
28
Example Data Set 2 (k = 5) (cont.)
•
w
17
= 1
•
w
8
= (1.08 – 1.00) / (1.08 – 0.83) = 0.32
•
w
11
= (1.08 – 1.02) / (1.08 – 0.83) = 0.24
•
w
16
= (1.08 – 1.06) / (1.08 – 0.83) = 0.08
•
w
7
= 0
204453: Pattern Recognition
29
Example Data Set 2 (k = 5) (cont.)
•
Class 1 sums to 0
•
Class 2 to which X
8
, X
11
and X
7
belong sums to
0.56.
•
Class 3 to which X
17
and X
16
belong sums to
1.08.
•
The point P belongs to Class 3.
•
kNN and MkNN assign the same pattern
different class labels.
204453: Pattern Recognition
30
r Near Neighbours (rNN)
•
All neighbours within some distance r of the
point of interest
•
They ignore very far away nearest neighbour
•
They identify outlier.
204453: Pattern Recognition
31
r Near Neighbours (rNN) (cont.)
•
Outlier
–
A pattern does not have any similarity with the
patterns within the radius chosen.
•
Radius r
–
Crucial
204453: Pattern Recognition
32
rNN Algorithm
STEP 1: Given the point P, determine the sub-set of
data that lies in the ball of radius r centred at P
B
r
(P) = {Xi
X s.t.
P – X
i
r}
STEP 2: If B
r
(P) is empty, then output the majority
class of the entire data set.
STEP 3: If B
r
(P) is not empty, output the majority
class of the data points in it.
204453: Pattern Recognition
33
Example Data Set (r = 1.45)
34
Fuzzy KNN
•
Elements have a degree of membership.
•
In fuzzy sets, the elements of the set have a
membership function attached to them which
is in the real unit interval [0, 1].
•
ij
gives the membership in the i
th
class of the
j
th
vector of the training set.
204453: Pattern Recognition
35
Fuzzy KNN (cont.)
204453: Pattern Recognition
36
Finding k NNs
204453: Pattern Recognition
37
X
1
= (0.8, 0.8, 1),
X
2
= (1.0, 1.0, 1),
X
3
= (1.2, 0.8, 1)
X
4
= (0.8, 1.2, 1),
X
5
= (1.2, 1.2, 1),
X
6
= (4.0, 3.0, 2)
X
7
= (3.8, 2.8, 2)
,
X
8
= (4.2, 2.8, 2),
X
9
= (3.8, 3.2, 2)
X
10
= (4.2, 3.2, 2),
X
11
= (4.4, 2.8, 2),
X
12
= (4.4, 3.2, 2)
X
13
= (3.2, 0.4, 3),
X
14
= (3.2, 0.7, 3)
,
X
15
= (3.8, 0.5, 3)
X
16
= (3.5, 1.0, 3)
,
X
17
= (4.0, 1.0, 3)
,
X
18
= (4.0, 0.7, 3)
P = (3.0, 2.0) ; k = 5 ; m = 2
Fuzzy KNN (cont.)
204453: Pattern Recognition
38
Prototype Selection
•
Prototype: Sample which would represent or
be a typical sample for a large number of
samples in the set
–
Centroid
–
Medoid
•
Process of reducing the training set used for
classification
204453: Pattern Recognition
39
Minimal Distance Classifier (MDC)
•
Each class is represented by the sample mean
or centroid of all samples in the class.
•
C
i
=
N
j=1
X
ij
/ N
•
X
i1
, X
i2
, …, X
iN
: N training patterns for the class i
•
If C
k
is the centroid closest to P, it is assigned
the class label k of which C
k
is the
representative pattern.
204453: Pattern Recognition
40
MDC (cont.)
•
n: The number of train patterns
•
m: The number of test patterns
•
C: The number of classes
•
MDC: O(n + mC)
–
O(n): Time required for computing the centroid
–
O(mC): Time required to search for the nearest
centroid of test patterns
•
NN: O(mn)
•
Large-Scale Applications: C << n
204453: Pattern Recognition
41
Classification Using MDC
42
Centroid
•
Class 1: (1.00, 1.00)
•
Class 2: (4.11, 3.00)
•
Class 3: (3.62, 0.72)
204453: Pattern Recognition
43
Classification Using MDC (cont.)
•
From P to the centroid of Class 1, the distance
is 2.24.
•
From P to the centroid of Class 2, the distance
is 1.49.
•
From P to the centroid of Class 3, the distance
is 1.42.
204453: Pattern Recognition
44
Image Classification
45
KNN Regression
46
References
•
Murty, M. N., Devi, V. S.: Pattern Recognition:
An Algorithmic Approach (Undergraduate
Topics in Computer Science). Springer (2012)
•
https://www.analyticsvidhya.com/blog/2018/
08/k-nearest-neighbor-introduction-
regression-python/
•
https://www.deepmind.com/blog/alphadev-
discovers-faster-sorting-algorithms
204453: Pattern Recognition
52
Explore the concepts of K-Nearest Neighbours (KNN) algorithm, its variants, and applications in pattern recognition. Learn about nearest neighbour based classifiers, prototype selection methods, and how the algorithm assigns class labels. Dive into examples and a detailed explanation of the algorithm with three-dimensional patterns.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Pattern Recognition Chapter 3: K Nearest Neighbours Chumphol Bunkhumpornpat Department of Computer Science Faculty of Science Chiang Mai University
Learning Objectives What a nearest neighbour (NN) algorithm is The different variants of NN algorithms like The k nearest neighbour (kNN) algorithm The modified k nearest neighbour (MkNN) algorithm The r near algorithm The fuzzy KNN algorithm The different methods of prototype selection used in classification like The minimal distance classifier (MDC) 2 204453: Pattern Recognition
Nearest Neighbour Based Classifiers Simplest Decision Procedures Nearest Neighbour (NN) Rule Similarity between a test pattern and every pattern in a training set Less than twice the probability of error compared to any other decision rule 3 204453: Pattern Recognition
Nearest Neighbour Algorithm The nearest neighbour algorithm assigns to a test pattern the class label of its closest neighbour. 5 204453: Pattern Recognition
Let the training set consist of the following three dimensional patterns: X1= (0.8, 0.8, 1), X4= (0.8, 1.2, 1), X7= (3.8, 2.8, 2), X10= (4.2, 3.2, 2), X11= (4.4, 2.8, 2), X12= (4.4, 3.2, 2) X13= (3.2, 0.4, 3), X14= (3.2, 0.7, 3), X15= (3.8, 0.5, 3) X16= (3.5, 1.0, 3), X17= (4.0, 1.0, 3), X18= (4.0, 0.7, 3) X2= (1.0, 1.0, 1), X5= (1.2, 1.2, 1), X8= (4.2, 2.8, 2), X3= (1.2, 0.8, 1) X6= (4.0, 3.0, 2) X9= (3.8, 3.2, 2) 6 204453: Pattern Recognition
Let the training set consist of the following three dimensional patterns: (cont.) Class 1: + Class 2: X Class 3: * P = (3.0, 2.0) d(X, P) = (X[1] P[1])2+ (X[2] P[2])2 d(X1, P) = (0.8 3.0)2+ (0.8 2.0)2= 2.51 d(X16, P) = (3.5 3.0)2+ (1.0 2.0)2= 1.12 7 204453: Pattern Recognition
Variants of the NN Algorithm k-Nearest Neighbour (kNN) Algorithm The Modified k Nearest Neighbour (MkNN) Algorithm The r Near Algorithm 9 204453: Pattern Recognition
k-Nearest Neighbour (kNN) Algorithm The majority class of the k nearest neighbours is the class label assigned to the new pattern. The value chosen for k is crucial. With the right value of k, the classification accuracy will be better than that got by using the nearest neighbour algorithm. 10 204453: Pattern Recognition
k-Nearest Neighbour (kNN) Algorithm (cont.) It reduces the error in classification when training patterns are noisy. The closest pattern of the test pattern may belong to another class, but when a number of neighbours are obtained and majority class label is considered, the pattern is more likely to be classified correctly. 12 204453: Pattern Recognition
P can be correctly classified using the kNN algorithm. 13
P can be correctly classified using the kNN algorithm (cont.) For larger data sets, k can be larger to reduce the error. k can be determined by experimentation, where a number of patterns taken out from the training set (validation set) can be classified using the remaining training patterns for different values of k. It can be chosen as the value which gives the least error in classification. 14 204453: Pattern Recognition
k = 2 k = 1 16
k = 4 k = 3 17
k = 6 k = 5 18
Modified k Nearest Neighbour (MkNN) Algorithm The Distance-Weighted k-Nearest Neighbour Algorithm k Nearest Neighbours are weighted according to the distance from the test point. 20 204453: Pattern Recognition
Modified k Nearest Neighbour (MkNN) Algorithm (cont.) if dk d1 if dk= d1 wj= (dk dj) / (dk d1) 1 j = 1, , k wjvaries from a maximum of 1 for the nearest neighbour down to a minimum of 0 for the most distant. 21 204453: Pattern Recognition
Modified k Nearest Neighbour (MkNN) Algorithm (cont.) It assigns the test pattern P to that class for which the weights of the representatives among the k nearest neighbours sums to the greatest value. It employs a weighted majority rule. The outlier patterns have lesser effect on classification. 22 204453: Pattern Recognition
Example Data Set (k = 5) (cont.) d(P, X16) = 1.12 d(P, X7) = 1.13 d(P, X14) = 1.32 d(P, X6) = 1.41 d(P, X17) = 1.41 24 204453: Pattern Recognition
Example Data Set (k = 5) (cont.) w16 w7 w14 w6 w17 = 1 = (1.41 1.13) / (1.41 1.12) = 0.97 = (1.41 1.32) / (1.41 1.12) = 0.31 = 0 = 0 25 204453: Pattern Recognition
Example Data Set (k = 5) (cont.) Class 1 sums to 0 Class 2 to which X7and X6belong sums to 0.97. Class 3 to which X16, X14and X17belong sums to 1.31. The point P belongs to Class 3. kNN and MkNN assign the same pattern a same class label. 26 204453: Pattern Recognition
Example Data Set 2 (k = 5) d(P, X17) = 0.83 d(P, X8) = 1.00 d(P, X11) = 1.02 d(P, X16) = 1.06 d(P, X7) = 1.08 28 204453: Pattern Recognition
Example Data Set 2 (k = 5) (cont.) w17 w8 w11 w16 w7 = 1 = (1.08 1.00) / (1.08 0.83) = 0.32 = (1.08 1.02) / (1.08 0.83) = 0.24 = (1.08 1.06) / (1.08 0.83) = 0.08 = 0 29 204453: Pattern Recognition
Example Data Set 2 (k = 5) (cont.) Class 1 sums to 0 Class 2 to which X8, X11and X7belong sums to 0.56. Class 3 to which X17and X16belong sums to 1.08. The point P belongs to Class 3. kNN and MkNN assign the same pattern different class labels. 30 204453: Pattern Recognition
r Near Neighbours (rNN) All neighbours within some distance r of the point of interest They ignore very far away nearest neighbour They identify outlier. 31 204453: Pattern Recognition
r Near Neighbours (rNN) (cont.) Outlier A pattern does not have any similarity with the patterns within the radius chosen. Radius r Crucial 32 204453: Pattern Recognition
rNN Algorithm STEP 1: Given the point P, determine the sub-set of data that lies in the ball of radius r centred at P Br(P) = {Xi X s.t. P Xi r} STEP 2: If Br(P) is empty, then output the majority class of the entire data set. STEP 3: If Br(P) is not empty, output the majority class of the data points in it. 33 204453: Pattern Recognition
Fuzzy KNN Elements have a degree of membership. In fuzzy sets, the elements of the set have a membership function attached to them which is in the real unit interval [0, 1]. ijgives the membership in the ithclass of the jthvector of the training set. 35 204453: Pattern Recognition
Fuzzy KNN (cont.) 36 204453: Pattern Recognition
Finding k NNs X1= (0.8, 0.8, 1), X4= (0.8, 1.2, 1), X7= (3.8, 2.8, 2), X10= (4.2, 3.2, 2), X11= (4.4, 2.8, 2), X12= (4.4, 3.2, 2) X13= (3.2, 0.4, 3), X14= (3.2, 0.7, 3), X15= (3.8, 0.5, 3) X16= (3.5, 1.0, 3), X17= (4.0, 1.0, 3), X18= (4.0, 0.7, 3) X2= (1.0, 1.0, 1), X5= (1.2, 1.2, 1), X8= (4.2, 2.8, 2), X3= (1.2, 0.8, 1) X6= (4.0, 3.0, 2) X9= (3.8, 3.2, 2) P = (3.0, 2.0) ; k = 5 ; m = 2 37 204453: Pattern Recognition
Fuzzy KNN (cont.) 38 204453: Pattern Recognition
Prototype Selection Prototype: Sample which would represent or be a typical sample for a large number of samples in the set Centroid Medoid Process of reducing the training set used for classification 39 204453: Pattern Recognition
Minimal Distance Classifier (MDC) Each class is represented by the sample mean or centroid of all samples in the class. Ci= Nj=1Xij/ N Xi1, Xi2, , XiN: N training patterns for the class i If Ckis the centroid closest to P, it is assigned the class label k of which Ckis the representative pattern. 40 204453: Pattern Recognition
MDC (cont.) n: The number of train patterns m: The number of test patterns C: The number of classes MDC: O(n + mC) O(n): Time required for computing the centroid O(mC): Time required to search for the nearest centroid of test patterns NN: O(mn) Large-Scale Applications: C << n 41 204453: Pattern Recognition
Centroid Class 1: (1.00, 1.00) Class 2: (4.11, 3.00) Class 3: (3.62, 0.72) 43 204453: Pattern Recognition
Classification Using MDC (cont.) From P to the centroid of Class 1, the distance is 2.24. From P to the centroid of Class 2, the distance is 1.49. From P to the centroid of Class 3, the distance is 1.42. 44 204453: Pattern Recognition
