5-KNN

Question 1

What is the KNN algorithm?

Answer 1

1. Store all training data points
2. Compute distance of test instance to all training data points
3. Find K closest data points
   4 . Compute concept based on nearest data points

Question 2

How are data points represented in KNN?

Answer 2

Each point is a feature vector

Question 3

What is hamming distance?

Answer 3

Number of differing elements in two strings of different elements. E.g. differences in nominal attributes once one-hot encoded

Question 4

What is simple matching distance?

Answer 4

1 - number of matching features / total features

Question 5

What is jaccard distance?

Answer 5

1 - | A ^ B | / |A U B|

If nominal features are one-hot encoded, sets are expressed as the elements encoded with 1

Question 6

What is manhatten distance?

Answer 6

d(a,b) = sum from i to N of |a_i - b_i|

Question 7

What is euclidean distance?

Answer 7

d(a,b) = sqrt(sum from i to N of (a_i - b_i)^2)

Question 8

What is cosine distance?

Answer 8

d(a,b) = 1 - cos(a,b)
= 1 - sum(a_ib_i)/(sqrt(sum(a_i^2))sqrt(sum(b_i^2)))

Question 9

What is normalised ranks?

Answer 9

For ordinal values:
1. Sort values and return rank
2. Map rank to evenly spaced values between 0 and 1, i.e. 1/4 if 4
3. Compare using distance function

Question 10

How can label be chosen?

Answer 10

Majority voting

Inverse distance weighting (usually with small epsilon in case instances match): 1/di + e

Inverse linear distance: (d_max - d_i)/(d_max - d_min)

Question 11

What is the impact of k in KNN?

Answer 11

Lower k generates jagged decision boundary. Higher k generates smooth decision boundary

Question 12

How if more than K neighbours share same distance?

Answer 12

Random

Change distance matrix

Question 13

How to break ties if two classes are equally as likely?

Answer 13

Avoid even K

Random tie break

Use class with highest prior probability

Question 14

What are the pros of KNN?

Answer 14

It is intuitive
Supports classification and regression
No assumptions
No training phase

Question 15

What are the cons of KNN?

Answer 15

Difficult to choose best distance function
Difficult to choose right K
Expensive with large data sets

Question 16

What is lazy learning?

Answer 16

Lazy learning are also known as instance-based learning.

Training data is stored and test instances are compared to the test data. There is no learning.

Question 17

What is eager learning?

Answer 17

Model is trained on training data using labelled instances. The model generalises from seen data to unseen data. The model then predicts the labels for test instances.