Introduction to texture description, segmentation and classification - Feature Extraction and Image Processing - page 304

The result of testing the k- nearest neighbour routine is illustrated on synthetic data in
Code 8.6. Here there are two different data sets. The first, Code 8.6 (a), has three classes of
which there are three samples (each sample is a row of data, so this totals nine rows) and
each sample is made up of three measurements (the three columns). As this is synthetic
data, it can be seen that each class is quite distinct: the first class is for measurements
around [1, 2, 3]; the second class is around [4, 6, 8]; and the third is around [8, 6, 3]. A
small amount of noise has been added to the measurements. We then want to see the class
associated with a test sample with measurements [4, 6, 8], Code 8.6 (b). The result is either
class 1, class 2 or class 3. Naturally, the 1-nearest nearest neighbour, Code 8.6 (c), associates
the test sample with the class with the closest measurements which is class 2 as the test
sample's nearest neighbour is the fourth row of data. The 3-nearest neighbour, Code 8.6 (d),
is again class 2 as the nearest three neighbours are the fourth, fifth and sixth rows and each
of these is from class 2.

123
1.1 2 3.1
1 2.1 3
468
3.9 6.1 8.1
4.1 5.9 8.2
8.8 6.1 2.8
7.8 5.9 3.3
8.8 6.4 3.1

2468
2.1 3.9 6.2 7.8
2.3 3.6 5.8 8.3
2.5 4.5 6.5 8.5
3.4 4.4 6.6 8.6
2.3 4.6 6.4 8.5

population1:=

population2:=

(a) 3 classes, 3 samples, 3 features (e) 2 classes, 3 samples, 4 features

test_point1:=(4 6 8) test_point2:=(2.5 3.8 6.4 8.3)

(b) First test sample (f) Second test sample

k_nn(test_point1,population1,1,3)=2 k_nn(test_point2,population2,1,2)=1
(c) 1-nearest neighbour

(g) 1-nearest neighbour

k_nn(test_point1,population1,3,3)=2 k_nn(test_point2,population2,3,2)=2
(d) 3-nearest neighbour (h) 3-nearest neighbour

Code 8.6 Applying the k -nearest neighbour rule to synthetic data

The second data set, Code 8.6 (e), is two classes with three samples each made up of four
measures. The test sample, Code 8.6 (f), is actually associated with class 1 by the 1-nearest
neighbour, Code 8.6 (g), but with class 2 for the 3-nearest neighbour, Code 8.6 (h). This is
because the test sample is actually closest to the sample in the third row. After the third
row, the next two closest samples are in the fourth and sixth rows. As the nearest neighbour